Задумалось мне сделать в игрушке, о которой я раньше писал, простую вещь — подсчитывать, какое место человек занимает в общем рейтинге:
Как я писал, для различных статистик игра использует AppEngine. Подкатом я расскажу об оптимизациях, которые пришлось применить для этой простой фичи.
Очевидно, что подсчитывать место в рейтинге «налету» довольно ресурсоемкая задача — нужно каждый раз сортировать всех пользователей и при внушительном их количестве страница начнет тормозить. Поэтому я решил денормализовать это значение и добавил соответствующее поле к классу пользователя:
Каждый раз, когда игрок получает или теряет очки, его место пересчитывается следующим образом. Допустим, таблица игроков выглядит так:
Теперь, если User 5 набирает 21 очко и всего имеет 121, я пересчитываю места всех игроков с очками между 100 и 121. До пересчета:
После пересчета:
К моему удивлению, такой нехитрый алгоритм дал высокую нагрузку на AppEngine (CPU зашкаливает):
Удивился я, и решил, что проблема в более чем 30-ти полях в классе Player, а апдейта без выборки всех этих полей в AppEngine не существует. Решил я тогда отцепить поле rank от класса Player и сделать отдельную «табличку» для подсчета мест.
Пересчет теперь происходил только для класса PlayerRank с двумя полями. Что ж, чем-то это конечно существенно помогло, но результат не назовешь удовлетворительным:
Очевидно, что AppEngine который тратит все свои ресурсы на пересчет места в рейтинге — плохой AppEngine. Проблема оказалась в слишком большом числе операций. Например, если игрок имеет 1 очко рейтинга, а еще 1000 игроков имеют 2 очка, то набрав этот игрок всего пару очков приходится пересчитывать всех 1000 остальных игроков, которым теперь нужно понизить место. Пришлось оптимизировать дальше следующим образом.
Хранить занимаемое место не для игрока, а для количества очков. Т.е. если 1000 игроков имеют 2 очка, то у всех у них будет одно место (скажем 3000-ое).
Таким образом пересчитывать надо не тысячу записей игроков, а всего две.
Свойство ScoreRank.count добавлено для контроля, сколько игроков имеют данное количество очков. Если этот count становится 0, то запись ScoreRank для данного количества очков удаляется.
AppEngine отреагировала:
С одной стороны, AppEngine вынуждает разработчика писать запутанные алгоритмы, в которых отпала бы нужда, используй разработчик реляционную базу данных и традиционный скажем LAMP. С другой стороны, алгоритмы таким образом получаются быстрые, страницы летают, в иных подходах эти страницы возможно были бы узким местом и тормозами (вспомните тормозные интернет-магазины на php+mysql). Со стороны третьей, квоты AppEngne удивляют. 10 тыс. запросов на выборку объекта с 30-тью полями и его апдейта выкинули приложение за бесплатную квоту. Приходит понимание, что AppEngine это дорого, вопреки популярному мнению.
Ссылка на игрушку: www.vkubiki.ru
Как я писал, для различных статистик игра использует AppEngine. Подкатом я расскажу об оптимизациях, которые пришлось применить для этой простой фичи.
Очевидно, что подсчитывать место в рейтинге «налету» довольно ресурсоемкая задача — нужно каждый раз сортировать всех пользователей и при внушительном их количестве страница начнет тормозить. Поэтому я решил денормализовать это значение и добавил соответствующее поле к классу пользователя:
class Player(db.Model):
name = db.StringProperty()
scores = db.IntegerProperty() # очки
#...
rank = db.IntegerProperty() # <-- занимаемое место
Каждый раз, когда игрок получает или теряет очки, его место пересчитывается следующим образом. Допустим, таблица игроков выглядит так:
Имя | Очки | Место |
---|---|---|
... | ||
User 1 | 123 | 50 |
User 2 | 121 | 51 |
User 3 | 111 | 52 |
User 4 | 105 | 53 |
User 5 | 100 | 54 |
User 6 | 99 | 55 |
... |
Теперь, если User 5 набирает 21 очко и всего имеет 121, я пересчитываю места всех игроков с очками между 100 и 121. До пересчета:
Имя | Очки | Место |
---|---|---|
... | ||
User 1 | 123 | 50 |
User 5 | 121 | 54 |
User 2 | 121 | 51 |
User 3 | 111 | 52 |
User 4 | 105 | 53 |
User 6 | 99 | 55 |
... |
После пересчета:
Имя | Очки | Место |
---|---|---|
... | ||
User 1 | 123 | 50 |
User 5 | 121 | 51 |
User 2 | 121 | 52 |
User 3 | 111 | 53 |
User 4 | 105 | 54 |
User 6 | 99 | 55 |
... |
К моему удивлению, такой нехитрый алгоритм дал высокую нагрузку на AppEngine (CPU зашкаливает):
Удивился я, и решил, что проблема в более чем 30-ти полях в классе Player, а апдейта без выборки всех этих полей в AppEngine не существует. Решил я тогда отцепить поле rank от класса Player и сделать отдельную «табличку» для подсчета мест.
class Player(db.Model):
#... более 30-ти полей ...
rank = db.ReferenceProperty(reference_class=PlayerRank)
class PlayerRank(db.Model):
score = db.IntegerProperty()
rank = db.IntegerProperty()
Пересчет теперь происходил только для класса PlayerRank с двумя полями. Что ж, чем-то это конечно существенно помогло, но результат не назовешь удовлетворительным:
Очевидно, что AppEngine который тратит все свои ресурсы на пересчет места в рейтинге — плохой AppEngine. Проблема оказалась в слишком большом числе операций. Например, если игрок имеет 1 очко рейтинга, а еще 1000 игроков имеют 2 очка, то набрав этот игрок всего пару очков приходится пересчитывать всех 1000 остальных игроков, которым теперь нужно понизить место. Пришлось оптимизировать дальше следующим образом.
Хранить занимаемое место не для игрока, а для количества очков. Т.е. если 1000 игроков имеют 2 очка, то у всех у них будет одно место (скажем 3000-ое).
Очки | Место | |
---|---|---|
... | ||
2 | 3000 | |
1 | 3001 | |
... |
Таким образом пересчитывать надо не тысячу записей игроков, а всего две.
class Player(db.Model):
#... более 30-ти полей ...
def rank(self):
return ScoreRank.all().filter('score =', self.score).get().rank
class ScoreRank(db.Model):
score = db.IntegerProperty()
rank = db.IntegerProperty()
count = db.IntegerProperty()
Свойство ScoreRank.count добавлено для контроля, сколько игроков имеют данное количество очков. Если этот count становится 0, то запись ScoreRank для данного количества очков удаляется.
AppEngine отреагировала:
Вывод
С одной стороны, AppEngine вынуждает разработчика писать запутанные алгоритмы, в которых отпала бы нужда, используй разработчик реляционную базу данных и традиционный скажем LAMP. С другой стороны, алгоритмы таким образом получаются быстрые, страницы летают, в иных подходах эти страницы возможно были бы узким местом и тормозами (вспомните тормозные интернет-магазины на php+mysql). Со стороны третьей, квоты AppEngne удивляют. 10 тыс. запросов на выборку объекта с 30-тью полями и его апдейта выкинули приложение за бесплатную квоту. Приходит понимание, что AppEngine это дорого, вопреки популярному мнению.
Ссылка на игрушку: www.vkubiki.ru