Розробка системи рейтингів: Фон
Коли я почав розробку сервісу у 2022 році, було задумано систему щоденних місій та нарахування балів для залучення користувачів, і мені було доручено розробити функціонал за цим планом. Спочатку передбачалося, що бали будуть зберігатися прямо в таблиці користувачів, тому коли я писав перший код, я не мав досвіду роботи з великим навантаженням на бекенд і майже не мав знань у цій сфері. Тому для реалізації функції рейтингу я просто використовував SQL. В результаті, той функціонал можна було б назвати системою рейтингів лише з натяжкою.
Але, незважаючи на все, функція працювала, і після запуску сервісу, коли кількість користувачів почала різко зростати, жодних проблем не виникало. Час минав, і ми не планували вдосконалення системи, але згодом почали з’являтися проблеми з продуктивністю. Оскільки дані про бали в таблиці користувачів часто змінювались, створення індексів було проблематичним.
Зрештою, навіть при тому, що кількість записів не перевищувала 10 мільйонів, запити для перегляду топ-100 рейтингів почали займати 2-3 секунди, а в день значного збільшення одночасних підключень функція перегляду рейтингу перестала працювати взагалі. Тому я тимчасово вимкнув цю функцію й почав шукати способи її вдосконалення.
Redis і Sorted Set
Ідеальним рішенням для побудови системи рейтингів став Redis з його структурою даних Sorted Set, яка дозволяє зберігати унікальні рядки, впорядковані за балами. У Redis є можливість зберігати кілька елементів у межах одного ключа з балами (score) та користувачами (member), причому за замовчуванням елементи сортуються за значенням балів. Якщо бали однакові, елементи сортуються в лексикографічному порядку за членами.
На перший погляд це може виглядати не особливо унікальним, але порівнявши часова складність SQL-запитів з використанням ORDER BY і Redis ZRANGE для отримання відсортованих даних, можна побачити, наскільки це різні підходи. Часова складність звичайного SQL-запиту з ORDER BY становить O(N logN), а у Redis, використовуючи ZRANGE, складність складає O(logN + M). Вже з цих цифр можна зрозуміти, наскільки значна різниця між ними, і якщо подивитись на графік складності, ця різниця стане очевидною.
Графік порівняння складності часу O(N logN) vs O(logN + M)
Як обробляти випадки з однаковими балами
Використання Sorted Set дозволяє зручно будувати систему рейтингів, але є ще один момент, який потрібно врахувати. Це ситуації з однаковими балами у кількох користувачів. Через відсутність дублювання в Redis елементи з однаковими балами сортуються за алфавітним порядком, тому при використанні команди ZRANK для отримання індексу можуть виникати помилки в підрахунку правильного місця в рейтингу.
Тому для таких випадків є кілька варіантів вирішення проблеми:
- Використовувати сортування без додаткової обробки
Цей метод полягає в тому, що ми просто використовуємо результат запиту Redis без додаткової обробки на сервері. - Спільні місця у рейтингу
Коли користувачі мають однакові бали, можна присвоїти їм спільне місце. Для цього замість ZRANK потрібно рахувати кількість користувачів з більш високими балами і додавати до цього значення одиницю. - Коригування рейтингу за допомогою десяткових чисел
Замість цілих чисел можна використовувати дробові значення для балів, що дозволяє точніше налаштувати рейтинг. Однак для відображення рейтингу користувачу потрібно буде додатково видаляти десяткові дроби.
Реалізація системи рейтингів у середовищі Node.js
Тепер давайте перейдемо до практичної частини та побудуємо систему рейтингів за допомогою Redis.
Коли система балів постійно оновлюється, необхідно врахувати ці зміни й у Redis. Для оновлення балів використовується команда ZADD.
const updatePoint = async (userId: string, point: number) => {
// SQL запит для оновлення балів
...
// Оновлення в Redis
await redis.zadd('ranking', point, userId);
...
}
Щоб отримати рейтинг за зменшенням балів, можна використати команду ZREVRANGE. Я, наприклад, у своїй реалізації обробляв випадки з однаковими балами, присвоюючи спільні місця.
import { chunk } from 'lodash';
type RankingItemType = {
userId: string;
point: number;
rank: number;
}
const getRanking = async (n: number) => {
// Якщо додати параметр WITHSCORES, результат виглядатиме так:
// ['user_a', '1500', 'user_b', '1200', 'user_c', '1000', ...]
const ranking = await redis.zrevrange('ranking', 0, n - 1, 'WITHSCORES');
return chunk(ranking, 2).reduce>(
(result, [userId, point], index) => {
if (index === 0) return [{ userId, point: parseInt(point), rank: 1 }];
else {
// Оскільки результат вже впорядкований за спаданням балів, можна використовувати індекс для визначення місця
// Якщо попередній користувач має такий самий бал, присвоюється спільне місце
const rank = result[index - 1].point === parseInt(point) ? result[index - 1].rank : index + 1;
return [...result, { address, point: parseInt(point), rank }];
}
},
[],
);
}
Якщо ви хочете дізнатися рейтинг конкретного користувача, можна використовувати таку техніку: підрахуйте кількість користувачів з більшими балами й додайте одиницю.
const getRankingByUserId = async (userId: string) => {
const user = await getUser(userId);
// Використовуємо команду ZCOUNT для підрахунку кількості користувачів з більшими балами
const count = await redis.zcount('ranking', user.point + 1, '+inf');
return count + 1;
}
Після впровадження системи рейтингів з Redis
Коли я використовував SQL-запити, на отримання списку топ-10 користувачів із найвищими балами йшло близько 2-3 секунд, але після впровадження системи рейтингів на основі Redis, середній час запиту зменшився до 0.2 секунди, що дозволило збільшити швидкість на понад 90%.
Крім того, були усунуті вузькі місця в базі даних, що дозволило більш стабільно працювати при високих навантаженнях, і система стала набагато надійнішою.
Однак дані, збережені в Redis, нараховують близько 5-6 мільйонів записів і займають приблизно 700 МБ. Це виявилося більше, ніж я початково розраховував, тому в разі обмеженої кількості пам'яті, під час побудови системи рейтингів варто уважно проводити розрахунки споживаної пам'яті.
Джерела
Перекладено з: Redis Sorted Set을 활용하여 랭킹 시스템 개발하기