Глибоке дослідження лідербордів з бактетами у Nakama.
“Fire Buckets” | Steve Greer
Лідерборди — це зовсім не просте завдання, і важко пояснити чому.
Я кілька ночей тому їв морозиво в місцевій крамниці морозива (мені сумно, що вони не використовують HTTPS), і намагався пояснити цю складність другу, який не є програмістом. Ось як я сформулював це:
“Уяви, що у тебе є мільйон гравців, і ти хочеш розділити їх на групи по 20 осіб, щоб у кожній групі всі 20 гравців мали рівні шанси на перемогу — як це зробити?”
Одразу він згадав, що так працюють всі онлайн покерні турніри. Чорт, так, я знаю, що це вже зроблено раніше, але це складна проблема, блін (пардон за мій жаргон). Для порівняння, Royal Match робить дещо подібне, але на шалено великому масштабі для чогось на кшталт 14 поточних подій одночасно, і, ймовірно, ще й для більшої кількості A/B когорт.
Це так поширено, що це, напевно, має бути простою задачею — так?
Я намагався переконати друга: “Так, так, звісно, так працюють покерні турніри але як ти це зробиш?” І тут він спокійно згадав про розподіл гравців за їх “рейтингом майстерності”. О, добре, у нас тепер є ці магічні “рейтинги майстерності”, так?
Я зрозумів, що я його втрачаю.
Що ще гірше, так, насправді, це не просто хороше припущення, а точно те, як це робиться — але почекайте, тому що я відчуваю, що деякі ДЕТАЛІ тут замовчуються, і не в останню чергу — гравці повинні мати ці рейтинги майстерності на початку (“як працюють рейтинги майстерності, мудрець?”) і — о так, а що з алгоритмічним дизайном: як ти будеш ітеративно обходити користувачів і формувати ці групи (“ти взагалі знаєш Big-O, брате?”) і ще й реальний діапазон майстерності в кожній групі: чи не треба порахувати середнє значення майстерності кожної групи і переконатися, що користувачі знаходяться в межах 1 стандартного відхилення чи щось таке? Статистика! І середнє значення кожної групи змінюватиметься, коли ти переставлятимеш користувачів, чи не так?
Труднощі, трудності. Можливо, навіть потрібно вивчати калькулюс.
Ми швидко змінили тему, бо я не зміг пояснити всі складнощі.
Steve Greer
Як Nakama реалізує лідерборди?
Давайте повернемося до початку.
Ми використовуємо Nakama (я, ймовірно, достатньо рекламував це, щоб бути співзасновником) і Nakama має систему лідербордів «з коробки». Вона досить проста, але “достатньо гнучка”, щоб бути ефективною для багатьох випадків використання.
Для запису, це насправді дуже висока похвала з мого боку. Я колись сказав Тиму Суїні на телефонній конференції, що його двигун поганий (це не правда) і він не може застосувати ООП навіть до мокрого паперового пакета. Ось чому Тім Суїні тепер полює на бідного Бена (це я), з того часу, як він випустив хіт 1992 року: Jill of the Jungle.
Лідерборди Nakama зберігають записи в одній таблиці з одним записом на кожного користувача та лідерборд. Ось як це виглядає (ID користувачів приховано):
З нашого різдвяного тестування, де ми розігрували $50!
Go API для Nakama надає методи для створення, оновлення та видалення записів. Також можна запитувати список цих записів. Повертаючись до питання про бактетовані лідерборди, ми могли б легко використовувати цю таблицю бази даних для зберігання груп лідербордів, просто змінивши спосіб запиту. Припустимо, у нас є список ID користувачів для певної групи.
Ми можемо просто додати умову where, щоб фільтрувати:
Це досить ефективно, якщо є хороші індекси і “достатньо малі” групи. Фактично, ми створюємо View. Це настільки логічно, що Nakama насправді реалізує це саме таким чином і вони також надають це як частину свого Go API. Ось як це виглядає у вихідному коді Nakama:
Вони використовують ANY замість IN, але суть та сама.
Ті з нас, хто уважно стежить за деталями, повинні також помітити, що записи лідербордів Nakama містять і userId, і username. Це означає, що запити до лідербордів не будуть містити найактуальніші імена користувачів (які знаходяться в таблиці users). Це дублювання даних і, ймовірно, є корисним з точки зору продуктивності. Подумай, якби для отримання найсвіжіших імен користувачів, запити лідербордів вимагали б з'єднання таблиць.
Остання «крута» особливість лідербордів Nakama — це система планувальника. Власне, ти можеш запланувати виконання функції, яка може виконати деякі операції з лідербордом: включаючи розподіл винагород і/або його скидання. Семантика на кшталт cron дуже класна (Веселого 0 0 25 12 *, до речі), але я б віддав перевагу більш загальній системі планування — наприклад, cron-рядку і функції. Було б непогано мати час початку, щоб ми могли визначити все заздалегідь. Не зовсім розумію, чому це має бути прив'язано саме до лідербордів (але я відволікаюсь)...
Врешті-решт, основна система лідербордів для Nakama досить міцна. Вона має основні елементи, необхідні для створення бактетованих лідербордів. Однак, хоча загальна система непогана, на жаль, посібники Nakama трохи відходять від теми у тому, як її використовувати.
Сподобалося, що ви читаєте? Подумайте про лайк або аплодування.
Спробуйте гру Hangman Clash або слідкуйте за нашою пригодою на X!
“Fail” | Junda JK
Як НЕ створювати бактети
Heroic Labs має посібник під назвою “Bucketed Leaderboards”, де вони розповідають, як створити погану систему бактетованих лідербордів (я попереджав, що я суворий критик). Але я буду чесний: хоча посібник отримує оцінку F-, він все ж таки відповів на кілька запитань щодо того, як можна створити хорошу систему (що, ймовірно, було його метою). Ось сила відкритого програмного забезпечення, друзі: поганий приклад плюс повний доступ до вихідного коду, і я вже готую!
У посібнику рекомендується генерувати бактет для користувача, вибираючи випадкову групу користувачів з бази даних за допомогою UUID-півоту. Це об'єктивно погано з кількох причин:
- Я не хочу занадто багато критикувати розподіл UUID, але генерувати UUID і використовувати > або < для вибору “випадкових” користувачів не дає вам випадкових користувачів. UUID не розподіляються рівномірно. Підхід з півотом справді працює, якщо півот розподілений правильно. Наприклад, якщо б на всіх записах були рівномірно розподілені числа, тоді можна було б вибрати випадкове число і витягнути 10 записів навколо нього.
- Крім того, цей посібник не відповідає реальним вимогам. Жодна гра в світі не використовує перекриваючі випадкові когорти користувачів на лідерборді.
- Бактети для кожного користувача замість лідерборду. Це означає, що кожен користувач бачитиме різні лідерборди.
Чому це має бути бажано для когось? - Отримані лідерборди ігнорують найбільшу складність: чесні матчі.
На щастя, у мене є всі відповіді.
“Answer” | Aftab Uzzaman
Кращі бактетовані лідерборди: Передумови
Є кращий спосіб, але для цього є кілька вимог.
Мій друг, який не є експертом, мав рацію: вам потрібні рейтинги майстерності, і не просто які-небудь рейтинги — вам потрібні такі, які гарантують певні математичні властивості. На початку цього року я проводив досить глибоке дослідження теми рейтингів майстерності (щасливо для вас), і це може бути надзвичайно складно. Достатньо сказати, що “хороші рейтинги майстерності” забезпечують необхідні гарантії, щоб ваші бактети було дуже легко генерувати.
Уявіть 100 користувачів, яких ви хочете розподілити на 10 бактетів. Для кожного користувача у вас є число, яке представляє його майстерність.
Кожен користувач має потрапити в бактет, а кожен бактет має бути “досить тісним” — це означає, що в ньому має бути якнайменший діапазон майстерності, який ми можемо забезпечити. Це необхідно, щоб всі користувачі в бактеті мали рівні шанси потрапити на вершину лідерборду. Ми не хочемо, щоб гравець опинився в бактеті з тим, хто в 10 разів кращий за нього.
Це може здатися складною проблемою, тому що це справді СКЛАДНА проблема. Ви могли б подумати, що для цього вам потрібна гістограма. А може, ітераційний підхід, коли ви створюєте кілька бактетів і потім перерозподіляєте їх. Ви можете уявити, що для кожного згенерованого бактета буде деяка частотна крива від найнижчого до найвищого балу.
Якщо уявити розподіл усіх цих рейтингів майстерності, можливо, він виглядатиме як ґудзикова крива? Було б чудово, якби ви могли використати це для створення тісних бактетів. Ми повернемося до цієї ідеї тісних бактетів, але спершу давайте поговоримо про цей elusive рейтинг майстерності.
Це глибока тема, і я лише коротко згадаю поверхню (тому що я сам розумію тільки поверхню). Достатньо сказати, що 1v1 характер наших ігор значно спрощує математику (групова динаміка ускладнює це набагато більше), і що матчмейкінг 1v1 вивчений уже десятиліттями в добре профінансованій грі шахи.
Для Hangman Clash ми вибрали систему рейтингів Glicko2, яка є вдосконаленням оригінальної шахової системи Elo. Ми вибрали її як тому, що відомі ігри використовують її (наприклад, TF2 і навіть chess.com), так і тому, що коли я шукав Go-реалізації, знайшов одну досить просту, щоб я міг її використати.
Після кожного матчу ми зчитуємо рейтинги майстерності зі сховища, оновлюємо їх результатами матчу, а потім записуємо. Просто.
Зчитування і записування використовують API зберігання Nakama для зчитування та запису записів в БД. Ці рейтинги майстерності з часом дають нам досить класну криву:
Мої рейтинги Hangman Clash з часом.
Крім того, ми відправляємо бал на лідерборд. Зверніть увагу, що ми нічого не робимо з бактетами на цьому етапі.
Пам'ятайте: бактети впливають лише на запити, до яких ми зараз і перейдемо.
Вам подобається те, що ви читаєте? Подумайте про те, щоб виділити або поставити лайк.
Зіграйте у гру Hangman Clash або слідкуйте за нашими пригодами на X!
Генерація бактетів за допомогою Glicko2
Тепер, коли у нас є хороша система рейтингів майстерності і ми записали записи в таблицю лідерборду, нам потрібно з'ясувати, як генерувати хороші бактети, щоб ми могли здійснювати запити. Як нагадування, ми хочемо, щоб бактети були консистентними (не різними для кожного користувача) і націленими, щоб кожен гравець у бактеті мав хороші шанси на перемогу. Коли ми минулого разу зупинялися, ми ще не були впевнені, як саме підходити до генерації бактетів.
Ось як ми це вирішили.
Коли лідерборд планується для старту, ми генеруємо всі бактети заздалегідь. Ми не робимо цього на вимогу, як рекомендує посібник (і насправді, ми блокуємо подання до лідерборду, поки бактети ще створюються). Бактети — це прості структури даних, які виглядають ось так:
type Bucket struct {
Id string `json:"id"`
CreatedAt int64 `json:"createdAt"`
Capacity int `json:"capacity"`
UserIds []string `json:"userIds"`
Min int64 `json:"min"`
Max int64 `json:"max"`
}
Min і Max відносяться до рейтингів майстерності користувачів у бактеті. Визначення структури даних бактета таким чином дозволяє нам створювати бактети та зберігати їх за допомогою сховища Nakama. Потім ми маємо функцію, яка завантажує їх з БД або генерує нові. Вона виглядає ось так:
func loadOrCreateBuckets(ctx context.Context, nk runtime.NakamaModule, db *sql.DB, lb *LeaderboardHandle) error {
util.Info(ctx, "Preparing buckets for leaderboard.")
buckets, err := readBuckets(ctx, nk, lb.Definition.Id)
if err != nil {
util.Error(ctx, "Could not read buckets for leaderboard: @Error. Creating new ones", err)
buckets = []*Bucket{}
}
if len(buckets) == 0 {
util.Info(ctx, "No buckets found for leaderboard. Creating...")
// there will be questions about this function... but it loads ALL user ids into memory
if users, err := readAllUsersSkill(ctx, db, lb.Definition.BucketGameType); err != nil {
return err
} else {
util.Info(ctx, "Loaded @Count users for leaderboard. Splitting into buckets...", len(users))
// creates the buckets
buckets, err = bucketUsers(lb.Definition.BucketSize, lb.Definition.BucketFillPercentage, lb.Definition.BucketMaxEloDiff, users)
if err != nil {
util.Error(ctx, "Could not create buckets for leaderboard: @Error.", err)
return err
}
util.Info(ctx, "Created created @Count buckets for leaderboard.", len(buckets))
// write buckets to storage
if err := writeBuckets(ctx, nk, lb.Definition.Id, buckets); err != nil {
util.Error(ctx, "Could not write buckets for leaderboard: @Error.", err)
return err
} else {
util.Info(ctx, "Successfully wrote @Count buckets for leaderboard.", len(buckets))
}
}
} else {
util.Info(ctx, "Loaded @Count buckets for leaderboard.", len(buckets))
}
lb.Buckets = buckets
return nil
}
Ця функція трохи довга — це просто Go для вас. Вам варто подивитися на вихідний код Nakama... Усі ці Java-інженери в Google (Боже благослови їх) були в захваті від можливості написати ще більше надмірно подробного коду.
У будь-якому разі, основна ідея проста: зчитати бактети зі сховища. Якщо їх немає, створити і записати їх у сховище.
Спершу давайте зупинимося на функції readAllUsersSkill. Нам потрібно, щоб ця функція завантажувала ВСІ користувачів і їх рейтинги майстерності, а потім повертала їх у величезному відсортованому списку:
type UserAndSkill struct {
UserId string
Skill float64
}
// readAllUsersSkill зчитує всіх користувачів та їх рейтинги майстерності з бази даних, відсортованих за рейтингом майстерності.
func readAllUsersSkill(ctx context.Context, db *sql.DB, ns string, gameType string) ([]UserAndSkill, error) {
// запит
rows, err := db.QueryContext(ctx, `select user_id, value from storage where collection = $1 and key = $2`,
"skill", "versus")
if err != nil {
util.Error(ctx, "Не вдалося отримати маніфести: @Error.", err)
return nil, err
}
defer rows.Close()
// знаходимо всіх користувачів з рейтингами Elo
users := make([]UserAndSkill, 0)
// оголошуємо один раз
var userId, value string
// ітерація по рядках
for rows.Next() {
if err := rows.Scan(&userId, &value); err != nil {
util.Error(ctx, "Не вдалося відсканувати маніфест Elo: @Error.", err)
return nil, err
}
// пропускаємо будь-які системні значення
if userId == "00000000-0000-0000-0000-000000000000" {
continue
}
// сортування вставкою
user := UserAndSkill{UserId: userId, Skill: strconv.Atoi(value)}
inserted := false
for i, u := range users {
if u.Skill > r {
users = append(users[:i], append([]UserAndSkill{user}, users[i:]...)...)
inserted = true
break
}
}
if !inserted {
users = append(users, user)
}
}
// перевірка на помилки
if err := rows.Err(); err != nil {
util.Error(ctx, "Не вдалося отримати рейтинги майстерності: @Error.", err)
return nil, err
}
return users, nil
}
Цей метод отримує рейтинг майстерності кожного користувача та парить його з ідентифікатором. Я знаю, що ви думаєте:
- Сортування вставкою?
- Цей запит занадто великий, не треба тримати всі ці дані в пам'яті одночасно.
Ви праві в обох випадках, але хочу зазначити, що цей підхід абсолютно працюватиме для десятків тисяч користувачів. З часом, ймовірно, вам слід буде використовувати пагінацію і стрімінг всього цього. Я, мабуть, робив би це, передаючи сторінки через канали Go і обробляючи кожну сторінку окремо (наприклад, 10 тисяч користувачів на сторінку), але оскільки Go робить таку задачу досить простою, я залишаю це як вправу для читача. Якщо ви справді параноїк, виведіть це повністю з процесу Nakama і зробіть це асинхронним процесом.
Тепер до останньої частини: я повністю пропустив функцію, яку дуже вдало названо bucketUsers. Це те, що бере список усіх користувачів і розбиває їх на бактети. Це той момент, якого ми чекали. Це тут ми будемо розбирати неймовірний алгоритм, який визначає чудові бактети за допомогою статистики або чогось подібного.
Давайте зануримося в це:
func newBucketFor(id string, capacity int, maxDiff int64, user UserAndSkill) *Bucket {
return &Bucket{
Id: id,
CreatedAt: time.Now().Unix(),
Capacity: capacity,
UserIds: []string{user.UserId},
Min: int64(user.Skill),
Max: int64(user.Skill) + maxDiff,
}
}
// Передбачається, що користувачі відсортовані за майстерністю.
func bucketUsers(targetBucketSize int, percentageFull float64, maxDiff int64, users []UserAndSkill) ([]*Bucket, error) {
if percentageFull > 1 || percentageFull < 0 {
return nil, fmt.Errorf("percentageFull має бути між 0 і 1")
}
if maxDiff < 1 {
return nil, fmt.Errorf("maxDiff має бути більшим за 1")
}
if targetBucketSize < 10 {
return nil, fmt.Errorf("targetBucketSize має бути щонайменше 10")
}
usersToFill := (float64(targetBucketSize) * percentageFull)
if usersToFill < 1 {
return nil, fmt.Errorf("targetBucketSize або percentageFull занадто малі")
}
// створюємо бактети
buckets := make([]*Bucket, 0)
// створюємо по ходу
var currentBucket *Bucket = nil
for i, user := range users {
if currentBucket == nil ||
// чи бактет заповнений?
len(currentBucket.UserIds) >= int(usersToFill) ||
// чи бактет занадто малий?
currentBucket.Max < int64(user.Skill) {
// створюємо новий бактет
currentBucket = newBucketFor(strconv.Itoa(i), targetBucketSize, maxDiff, user)
buckets = append(buckets, currentBucket)
} else {
currentBucket.UserIds = append(currentBucket.UserIds, user.UserId)
}
}
return buckets, nil
}
Це насправді не так вже й погано. Ми просто проходимо по користувачах і — почекайте, ми ж не розподіляємо це рівномірно! А що щодо розподілу за майстерністю в кожному бактеті? Де ж гаусівська крива?!
Ось чому все це залежить від “хороших рейтингів майстерності”. Саме тому це одночасно і дратує, і смішно, що мій друг припустив, що ви просто “групуєте їх за рейтингом майстерності” і залишили це на тому. Саме тому ви не можете просто розрахувати все про бактети в момент їх створення: вам потрібні рейтинги майстерності заздалегідь.
З точки зору математики Elo та Glicko2, відмінні розподіли вже вбудовані в набір відсортованих користувачів.
Конкретно, в нашому списку гравців, відсортованих за майстерністю, гравець 1152 не має кращих суперників, ніж гравці 1151 і 1153. Це вже найкращі можливі гравці для нього, з якими можна грати, і вони будуть в результатних бактетах на таблиці лідерів!
Подивіться, як сильно він думає. | “Society of the Query” by Anne Helmond
І нарешті: Запити до таблиць лідерів
У нас є бактети і є подача балів. Остання частина цієї вправи — коли гравець хоче насправді подивитися таблицю лідерів (ми надаємо RPC для цього) або коли ми хочемо зробити щось з переможцями таблиці лідерів.
// отримати бактет користувача
bucket := getBucket(ctx, nk, handle, userId)
_, lb, _, _, listErr := nk.LeaderboardRecordsList(ctx, handle.LbName, bucket.UserIds, bucket.Capacity, "", 0)
if listErr != nil {
return nil, listErr
}
Це дійсно виглядає анти-кліматично після стільки роботи. Все, що нам потрібно зробити, це отримати бактет для користувача і передати його в API Nakama. Nakama автоматично додасть умову WHERE IN, і ви отримаєте результати таблиці лідерів за бактетами.
Руки вгору та останні думки
Я дещо спростив деякі моменти.
По-перше, я не говорив про користувачів, які були створені після створення бактетів. Ось чому ці бактети мають окрему capacity, яка не дорівнює len(userIds). По суті, ми залишаємо трохи місця в кожному бактеті, щоб можна було вставити нових користувачів у найближчий бактет. Звісно, нові користувачі будуть мати однаковий початковий рейтинг майстерності — базовий рівень, тому, коли нам доведеться створювати нові бактети, вони будуть створюватися навколо цього базового рівня.
Крім того, користувачі можуть теоретично бути підвищені, поки таблиця лідерів ще працює. Тобто, що якщо таблиця лідерів триває досить довго і користувач справді стає значно кращим (або гіршим), ніж усі інші в бактеті? Знову ж таки, ця ємність дозволяє нам перерозподіляти, якщо потрібно.
Останнє, що ми не згадали, це те, що нам довелося побудувати свій власний планувальник. Уф. Це трохи шкода, але планувальник таблиць лідерів Nakama просто занадто слабкий.
Ви, на жаль, не можете запланувати час початку, і всі таблиці лідерів повторюються. Ми хотіли запланувати одноразові таблиці лідерів, які стартують і закінчуються в конкретні часи. Можливо, це стане темою для майбутнього посту.
Сподіваюся, вам сподобалося це, буду радий почути ваші думки. О, і чи згадував я, що ми збираємося розіграти $50,000 дуже скоро?
Залишайтеся з нами.
Сподобалося те, що ви прочитали? Подумайте про те, щоб відзначити або похвалити.
Пограйте в гру Hangman Clash або слідкуйте за нашими пригодами на X!
Перекладено з: Nakama Deep Dive: Leaderboards