Всем привет, меня зовут Михаил, я работаю Java/Kotlin разработчиком в ОТП Банке.

Все мы знаем про Redis. Часто используем его для in-memory кэша. В основном это ключ и значение. Но что, если можно пойти дальше и, как в том фильме, раскрыть все возможности Redis на 100%?

Сегодня я хочу поговорить о Sorted Set в Redis. Что это за зверь и как его использовать.

Буду показывать на примере таблицы лидеров. Это можно использовать для разных задач, но я выбрал именно эту.

Будем замерять время, ресурсы при нагрузках - все, как мы любим.

Присаживайтесь, будет интересно!

Какую проблему мы сегодня решаем?

Давайте представим, что в нашем приложении есть топ пользователей с самым большим балансом(рейтингом, сейчас неважно). Его нужно показывать всем, кто заходит в приложение. При этом баланс может часто меняться.

Класс сущности:

Класс сущности

@Getter
@Setter
@Entity
@Builder
@NoArgsConstructor
@AllArgsConstructor
@Table(name = "users", schema = "public")
public class User implements Serializable {

  @Id
  @Column(name = "id")
  private UUID id;

  @Column(name = "name", nullable = false)
  private String name;

  @Column(name = "email", nullable = false, unique = true)
  private String email;

  @Column(name = "balance")
  private int balance;
}

И есть простой код:

public interface UserRepository extends JpaRepository<User, Long> {
  List<User> findTop10ByOrderByBalanceDesc();
}

Давайте посмотрим, сколько у нас записей в бд:

SELECT COUNT(*) FROM users
-- 1 017 087

На текущий момент у нас чуть больше 1 млн записей.

Также у нас имеется следующий индекс

CREATE INDEX idx_users_balance ON users(balance);

Вот с этими данными мы сейчас и будем работать.

Первый тест

Я буду использовать для замера времени и ресурсов либу, которую когда-то описывал тут - https://habr.com/ru/articles/1035238/ можно использовать все, что вашей душе угодно.

По ресурсам у меня apple m4 и выделено 4 гб на хип.

Все тесты подключены сейчас к нашей базе данных. Сначала я буду тестировать обычные SELECT:

  @Test
  public void checkPostgresTimeOneRequest() {
    LoadTestReport loadTestReport = RunnableChecker.run(userService::findTop10);
    System.out.println(loadTestReport.toString());
  }

Total duration: 135 ms

Метод выполнился за 135 мс. Думаю, кто-то уже готов закрыть статью. Но не спешите - самое интересное впереди!

Теперь, когда мы поняли, что наш код уже работает быстро, давайте добавим нагрузки.В качестве requestCount используются виртуальные потоки для имитации одновременной нагрузки:

  @Test
  public void checkPostgresTimeRps() {
    LoadTestReport loadTestReport = RunnableChecker.run(
        RunnableTesting.builder()
            .requestCount(Кол-во запросов)
            .task(userService::findTop10)
            .build()
    );
    System.out.println(loadTestReport.toString());
  }

Кол-во запросов	Время ответа мс	Memory
5 000	679 ms ≈ 0,67 секунды	158 MB
10 000	1239 ms ≈ 1,2 секунды	331 MB
50 000	4277 ms ≈ 4,2 секунды	1547 MB
100 000	6301 ms ≈ 6,3 секунды	2827 MB

Как мы видим, с поиском Postgres справляется отлично, но что если мы хотим взять данные из середины? Или мы будем часто вставлять в базу значения

Второй тест

Теперь давайте доставать данные из середины, а не первые 10:

  @Query(value = """
      SELECT * FROM users
      ORDER BY balance DESC
      OFFSET :offset
      LIMIT :limit
      """, nativeQuery = true)
  List<User> findPageByBalanceDesc(@Param("offset") long offset, @Param("limit") int limit);

  private static final long MIDDLE_OFFSET = 500_000L;
  private static final int PAGE_SIZE = 10;

  public List<User> findFromMiddle() {
    return userRepository.findPageByBalanceDesc(MIDDLE_OFFSET, PAGE_SIZE);
  }

  @Test
  public void checkPostgresGetMiddleTime() {
    LoadTestReport loadTestReport = RunnableChecker.run(
        RunnableTesting.builder()
            .requestCount(Кол-во запросов)
            .task(userService::findFromMiddle)
            .build()
    );
    System.out.println(loadTestReport.toString());
  }

Давайте замерять:

Кол-во запросов	Время ответа	Heap
1 000	22737 ms ≈ 22 секунды	83 MB
5 000	121552 ms ≈ 2 минуты	203 MB
10 000	262514 ms ≈ 4,3 минуты	329 MB
50 000	1509625 ms ≈ 25 минут	1418 MB

Здесь уже все гораздо хуже, конечно, тут еще проблема в том, что мы используем не keyset пагинация, а offset, но сейчас немного опустим это.

Но и поиск из середины будем честны выполняется не часто.

Третий тест

Теперь давайте более реальную картину, у нас много пользователей и они постоянно меняют свои балансы, также создаются новые пользователи:

  @Modifying
  @Transactional
  @Query(value = """
      UPDATE users
      SET balance = :balance
      WHERE id = (
        SELECT id FROM users TABLESAMPLE SYSTEM (1) LIMIT 1
      )
      """, nativeQuery = true)
  int updateRandomBalance(@Param("balance") int balance);

  public List<User> findRandomPage() {
    long offset = ThreadLocalRandom.current().nextLong(MIN_RANDOM_OFFSET, MAX_RANDOM_OFFSET + 1);
    return userRepository.findPageByBalanceDesc(offset, PAGE_SIZE);
  }

  public void updateRandomBalance() {
    int balance = ThreadLocalRandom.current().nextInt(1, 10_001);
    userRepository.updateRandomBalance(balance);
  }

  public void insertUser() {
    userRepository.save(buildUser());
  }

  public User buildUser() {
    Random random = new Random();
    int number = random.nextInt(10000) + 1;
    return User.builder()
        .id(UUID.randomUUID())
        .email(UUID.randomUUID() + "@gmail.com")
        .balance(number)
        .name("Легенда")
        .build();
  }

И теперь я запущу тест, который будет делать 10 операций чтения из рандомной страницы + 1 вставку/обновления:

  @Test
  public void checkPostgresRandomPageWithWrites() {
    AtomicInteger step = new AtomicInteger();
    LoadTestReport loadTestReport = RunnableChecker.run(
        RunnableTesting.builder()
            .requestCount(Кол-во запросов)
            .task(() -> battle(
                step,
                userService::findRandomPage,
                userService::insertUser,
                userService::updateRandomBalance
            ))
            .build()
    );
    System.out.println(loadTestReport.toString());
  }

  protected void battle(AtomicInteger step, Runnable read, Runnable insert, Runnable update) {
    if (step.getAndIncrement() % 11 == 10) {
      if (ThreadLocalRandom.current().nextBoolean()) {
        insert.run();
      } else {
        update.run();
      }
    } else {
      read.run();
    }
  }

Кол-во запросов	Время ответа мс	Memory
1 100	13339 ms ≈ 13,3 секунд	88 MB
5 500	75199 ms ≈ 1,25 минуты	267 MB
11 000	196320 ms ≈ 3,2 минуты	336 MB
55 000	2183521 ms ≈ 36 минут	2318 MB

Конечно, здесь все зависит от рандома, какая будет выбрана страница, какой глубины, но и я не стал доставать страницы после половины offset.

На настоящем проекте никогда не узнаешь, как им будут пользоваться

Выход на сцену redis sorted set

Sorted Set в Redis - это как обычный Set, но у каждого элемента есть числовой вес (score). Элементы всегда хранятся в отсортированном порядке по этому весу. Это идеально для таблиц лидеров, рейтингов, очередей с приоритетом -любых задач, где важен порядок. Добавление элемента: одна команда, Redis сам поддерживает сортировку.

Метод	Описание	Сложность
`ZADD`	Добавляет элемент с указанным весом (score)	O(log N)
`ZRANK`	Возвращает позицию элемента по возрастанию (индекс)	O(log N)
`ZREVRANK`	Возвращает позицию элемента по убыванию	O(log N)
`ZRANGE`	Возвращает элементы по индексам (по возрастанию веса)	O(log N + M), где M - количество возвращаемых элементов
`ZREVRANGE`	Возвращает элементы по индексам (по убыванию веса)	O(log N + M), где M - количество возвращаемых элементов
`ZSCORE`	Получает вес (score) элемента	O(1)
`ZREM`	Удаляет элемент из коллекции	O(log N)
`ZINCRBY`	Увеличивает вес элемента на заданное значение	O(log N)

Sorted Set внутри работает как сбалансированное дерево. Почти все операции - O(log N). Это как бинарный поиск: даже с 1 миллионом записей нужно всего около 20 шагов, чтобы найти позицию элемента.

Ну что, поехали тестировать!

Первый тест

По сути все будет один в 1, только будет вызываться redisService.

Давайте получим первые 10 элементов:

  public List<User> getTop10() {
    return toUsers(redisTemplate.opsForZSet().reverseRange(LEADERBOARD_KEY, 0, 9));
  }

  private List<User> toUsers(Set<String> members) {
    if (members == null) {
      return List.of();
    }
    return members.stream()
        .map(this::getUser)
        .toList();
  }

  @SneakyThrows
  private User getUser(String s) {
    return objectMapper.readValue(s, User.class);
  }

  @Test
  public void shouldRedisTop10Time() {
    LoadTestReport loadTestReport = RunnableChecker.run(
        RunnableTesting.builder()
            .requestCount(Кол-во запросов)
            .task(redisUserService::getTop10)
            .build()
    );
    System.out.println(loadTestReport.toString());
  }

Кол-во запросов	Время ответа мс	Memory
5 000	334.80 ms ≈ 0,3 секунды	147 MB
10 000	607 ms ≈ 0,6 секунды	288 MB
50 000	1786 ms ms ≈ 1,7 секунды	1167 MB
100 000	3074 ms ≈ 3 секунды	1674 MB
200 000	5876 ms ≈ 5,8 секунд	2719 MB

Видим, что прирост есть. Но будем честны - сейчас он не прям вау, чтобы бежать и переписывать всё на Redis.

Хотя с ростом нагрузки картина меняется. Postgres начинает задыхаться, а Redis продолжает работать стабильно. И вот тут уже видно: 100 000 запросов в Postgres ≈ 200 000 в Redis.

А это уже очень хороший результат.

Второй тест

Сейчас мы будем получать данные из центра:

  private static final long MIDDLE_START = 500_000L;
  private static final long MIDDLE_END = 500_009L;
  
  public List<User> getFromMiddle() {
    return toUsers(
        redisTemplate.opsForZSet().reverseRange(LEADERBOARD_KEY, MIDDLE_START, MIDDLE_END));
  }

  @Test
  public void checkRedisMiddleRpsTime() {
    LoadTestReport loadTestReport = RunnableChecker.run(
        RunnableTesting.builder()
            .requestCount(Кол-во запросов)
            .task(redisUserService::getFromMiddle)
            .build()
    );
    System.out.println(loadTestReport.toString());
  }

Кол-во запросов	Время ответа	Heap
1 000	217 ms ≈ 0,2 секунды	89 MB
5 000	431 ms ≈ 0,4 секунды	153 MB
10 000	590 ms ≈ 0,6 секунды	268 MB
50 000	1724 ms ≈ 1,7 секунды	1113 MB
100 000	3113 ms ≈ 3,1 секунды	1790 MB
500 000	15235 ms ≈ 15 секунд	3842 MB

Здесь уже видно колоссальное преимущество.

Postgres обрабатывал 50 000 записей за 14 минут. А Redis - 500 000 записей за 15 секунд.

Вдумайтесь: 50 тысяч за 14 минут против 500 тысяч за 15 секунд. Причём записей в 10 раз больше, а время - в 56 раз меньше.

Это другой уровень.

Третий тест

По факту третий тест самый интересный, так как он проверяет настоящую нагрузку, непонятно куда тыкнет пользователь, также все может меняться и создаваться новые пользователи:

 private static final long MIN_RANDOM_OFFSET = 1L;
  private static final long MAX_RANDOM_OFFSET = 1_000_000L;
  
  public List<User> getRandomPage() {
    long offset = ThreadLocalRandom.current().nextLong(MIN_RANDOM_OFFSET, MAX_RANDOM_OFFSET + 1);
    return toUsers(
        redisTemplate.opsForZSet().reverseRange(LEADERBOARD_KEY, offset, offset + PAGE_SIZE - 1));
  }
  
  @SneakyThrows
  public void addUser() {
    User user = userService.buildUser();
    String userJson = objectMapper.writeValueAsString(user);
    redisTemplate.opsForZSet().add(LEADERBOARD_KEY, userJson, user.getBalance());
  }
  
  @SneakyThrows
  public void updateRandomUser() {
    String member = redisTemplate.opsForZSet().randomMember(LEADERBOARD_KEY);
    if (member == null) {
      return;
    }
    User user = getUser(member);
    int newBalance = ThreadLocalRandom.current().nextInt(1, 10_001);
    user.setBalance(newBalance);
    redisTemplate.opsForZSet().remove(LEADERBOARD_KEY, member);
    redisTemplate.opsForZSet().add(LEADERBOARD_KEY, objectMapper.writeValueAsString(user), newBalance);
  }

Здесь я уже не боюсь проходить до самого низа редиса, ставлю лимит 1_000_000(знаю, что данных чуть больше, но сейчас это не так важно)

@Test
  public void checkRedisRandomPageWithWrites() {
    AtomicInteger step = new AtomicInteger();
    LoadTestReport loadTestReport = RunnableChecker.run(
        RunnableTesting.builder()
            .requestCount(Кол-во запросов)
            .task(() -> battle(
                step,
                redisUserService::getRandomPage,
                redisUserService::addUser,
                redisUserService::updateRandomUser
            ))
            .build()
    );
    System.out.println(loadTestReport.toString());
  }

Кол-во запросов	Время ответа мс	Memory
1 100	237 ms ≈ 0,2 секунды	78 MB
5 500	424 ms ≈ 0,4 секунды	213 MB
11 000	696 ms ≈ 0,7 секунды	307 MB
55 000	2311 ms ≈ 2,3 секунды	1225 MB
110 000	3660 ms ≈ 3,6 секунды	2294 MB
550 000	19867 ms ≈ 20 секунд	3906 MB

Postgres на 55 000 записей - 36 минут. Redis на 550 000 записей - 20 секунд.

Вывод

Сегодня я показал вам такого зверя, как Redis Sorted Set.

Конечно, применять его везде не получится. Всё зависит от ваших задач. И, как мы знаем, преждевременные оптимизации - зло.

Смотрите исходя из вашей нагрузки и потребностей пользователей. Иногда можно отделаться малой кровью - сделать простое решение на PostgreSQL, и оно будет отлично работать при своих нагрузках.

И важный момент: Redis не является основным хранилищем данных. Он не держит данные на диске как реляционная база. По умолчанию он хранит всё в памяти. Персистентность можно включить, но это не делает его полноценной заменой PostgreSQL. Держите это в голове, когда выбираете инструмент.

Выбирайте ваше решение от контекста и требований!

Всем хорошего дня и спасибо за чтение!)

Как я ускорил работу с топом-пользователей с 36 минут до 20 секунд, используя Redis Sorted Set