Как быстро сортировать в большой таблице по часто изменяемому полю?

Question

[Александр Кубинцев]

Прекрасно известно, что сортировать удобно по индексируемому полю.
Однако также известно, что использование индексов на часто изменяемых данных приводит к большой деградации производительности.
Ситуация такая.
Есть шарды с таблицами с игровых аккаунтов, где живёт порядка 50 млн записей. Среди разных полей имеется и поле с балансом игровой валюты. Баланс этот соответственно часто изменяется.

Есть фоновая задача с регулярным построением рейтинга/топа на основе данных о балансе раз в пару часов. Запрос включает в себя конечно же конструкцию "ORDER BY balance DESC". Интервал 2 часа - потому что построение идёт больше часа. Хотелось бы по возможности и чаще.

Проблема: создаётся очень серьёзная нагрузка на дисковую подсистему серверов базы данных, IOLA порядка 90%, доходит почти до 100%.
Возможные и нежелательные решения:
1) Сделать реплику БД на другом сервере и её мучать запросами. Но нужно и под неё делать резервирование. Так же возможно снижение частоты обновления, т.к. железо будет менее мощное.
2) Поставить ещё более производительный массив SSD - дорого
3) Использовать какое-то решение NoSQL конкретно под эту задачу. Добавит избыточности и вероятно неконсистентности. Опять же надо делать резервирование.

Хочется решить проблему более элегантно, на софтовом уровне с имеющейся инфраструктурой.
Может ли помочь использование MATERIALIZED VIEW? Допустим сделать отдельно представление нужных данных для постройки рейтинга и наложить на поле balance индекс, а обновлять допустим раз в полчаса?

Comments

[Сергей Соколов]

более часа занимает запрос с ORDER BY по 50 млн. записей? Это нормально?

[Сергей Соколов]

Интересует только топ-100 или именно позиция в рейтинге для каждого? Или достаточно по каждому активному игроку (из появлявшихся онлайн за последние сутки)

И ещё вопрос, чем готовы жертвовать? Например, так ли важна идеальная точность позиции в рейтинге или допустимы ошибки +-X пунктов. Все равно посчитанный рейтинг почти сразу же устаревает посл первого же обновления чьего-либо баланаса. Если можно считать позицию в рейтинге округленно, то до какого шага? Если несколько игроков окажутся в одном шаге, это плохо? Грубый вариант, всего 3 диапазона: мелочь, середина и топ. При каждом обновлении баланса пользователя назначать его в один из трёх.

[Александр Кубинцев]

Сергей Соколов, на самом деле там не один запрос, их много. Есть несколько игр, 2 вида рейтинга и разбиения по категориям, коих пара-тройка тысяч. Это и выливается в такое длительное время. Можно уменьшить интервал обновления до раза в сутки, но это не меняет сути. Нагрузка большая и запаса производительности в этот период остаётся мало - может увеличиться время отызвчивости приложений.

[devalone]

Теоретически, данные могут поместиться в раму и там можно обновлять бинарное дерево(самобалансируемое)

[Александр Кубинцев]

devalone, в принципе так и получается. Но как выяснилось мы упёрлись в проблему самой БД, где таблица распухла из-за особенностей её модели MVCC и произошла деградация производительности

Answer 1

[Дмитрий Свиридов]

А есть вариант хранить в redis значения ID пользователей и их баланса? Например, используя Sorted sets. При каждом изменении баланса каждого пользователя обновлять значения. То есть вытащить топ из редиса, по идее, проблемы не составит. И дёргать можно сколь угодно часто, а данные всегда актуальны.

Comments

[Александр Кубинцев]

Была такая идея.
Есть нюанс, который это решение делает не идеальным. На самом деле есть несколько игр + несколько видов топов. То есть получится несколько "срезов" с некоторой избыточностью. Предстоит оценить хватит ли места в хранилище. Но решение выглядит вполне рабочим в первом приближении. Спасибо.

[Дмитрий Свиридов]

Александр Кубинцев, учитывая, что это все топы, Вы, по идее, можете при изменении баланса какого-либо пользователя смотреть максимальный и минимальный элемент в редисе и, если баланс попадает в этот диапазон, то добавлять туда запись, а запись минимальным значением удалять (иначе, если не попадает в диапазон, не делать ничего). То есть ограничить количество элементов в списке в Redis. Вам же в любом случае не потребуется там все 80 миллионов пользователей держать.

[Mikhail Osher]

Был подобный опыт. Объёмы поменьше были, однако работало идеально и очень быстро.

Каждое изменение баланса попадало редиску. Так же, было много разных списков рейтингов. И был эндпоинт, который выдавал ZREVRANGEBYSCORE по нужным ключам.

[Александр Кубинцев]

Дмитрий Свиридов, да, всё верно, там достаточно только топ-3000

[Дмитрий Свиридов]

Александр Кубинцев, тогда вообще проблем не возникнет

Answer 2

[Melkij]

explain (analyze,buffers) с включенным track_io_timing покажите.

Варианты:
- вы проводите весь час времени не на сортировке, а где-то ещё о чём решили не писать. Соответственно вопрос неактуален и искать надо там где обронили, а не где светло.
- у вас несоответствующие настройки автовакуума (читай дефолтные)
- время занимает filesort, а от ssd у вас по ошибке стоят read-optimised.

Comments

[Александр Кубинцев]

Если решать в лоб, то выглядит так:

EXPLAIN (ANALYZE, BUFFERS) SELECT user_id, rating FROM accounts WHERE game_id = 123 ORDER BY rating DESC LIMIT 3000;
                                                                            QUERY PLAN                                                                            
------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2475021.96..2475029.46 rows=3000 width=12) (actual time=204038.913..204039.763 rows=3000 loops=1)
   Buffers: shared hit=79631 read=1385187 written=4601
   ->  Sort  (cost=2475021.96..2480821.74 rows=2319911 width=12) (actual time=204038.911..204039.447 rows=3000 loops=1)
         Sort Key: rating DESC
         Sort Method: top-N heapsort  Memory: 333kB
         Buffers: shared hit=79631 read=1385187 written=4601
         ->  Bitmap Heap Scan on accounts  (cost=549639.99..2329438.88 rows=2319911 width=12) (actual time=17485.007..202936.757 rows=2330230 loops=1)
               Recheck Cond: (game_id = 123)
               Rows Removed by Index Recheck: 1509171
               Heap Blocks: exact=363810 lossy=645363
               Buffers: shared hit=79631 read=1385187 written=4601
               ->  Bitmap Index Scan on uk_account_user_game  (cost=0.00..549060.02 rows=2319911 width=0) (actual time=17338.478..17338.478 rows=2685830 loops=1)
                     Index Cond: (game_id = 123)
                     Buffers: shared hit=51458 read=404187 written=4601
 Planning time: 0.170 ms
 Execution time: 204044.322 ms

Но я приделал пока костыль в виде частичного индекса по полю последнего визита в игру, чем уменьшил набор данных и немного ускорил:

EXPLAIN (ANALYZE, BUFFERS) SELECT user_id, rating FROM accounts WHERE game_id = 123 AND last_played > '2019-01-01 00:00:00' ORDER BY rating DESC LIMIT 3000;
                                                                             QUERY PLAN                                                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.43..11604.33 rows=3000 width=12) (actual time=1.270..2399.434 rows=3000 loops=1)
   Buffers: shared hit=79253 read=8879
   ->  Index Scan Backward using account_last_played_idx on accounts (cost=0.43..1797664.90 rows=464757 width=12) (actual time=1.269..2397.924 rows=3000 loops=1)
         Filter: ((last_played > '2019-01-01 00:00:00'::timestamp without time zone) AND (game_id = 123))
         Rows Removed by Filter: 11100
         Buffers: shared hit=79253 read=8879
 Planning time: 0.205 ms
 Execution time: 2400.207 ms
(8 строк)

Только всё равно это не сильно помогло.

[Melkij]

track_io_timing где? Я неслучайно его упомянул.

[Melkij]

костыль в виде частичного индекса по полю последнего визита в игру,

Однако также известно, что использование индексов на часто изменяемых данных приводит к большой деградации производительности.

Вы уже так и сделали. Ну и сделайте прямой индекс по балансу.

Sort (cost=2475021.96..2480821.74 rows=2319911 width=12) (actual time=204038.911..204039.447 rows=3000 loops=1)

Как легко заметить, сама сортировка вам на самом деле ничего не стоит.

written=4601

А вот чекпойнтер и bgwriter не справляются.
А так же на bitmap не хватает workmem. И, подозреваю, shared_buffers

Ну и ради всего 2.3 млн строк потрогали почти 12гб - с автовакуумом проблема точно.

[Александр Кубинцев]

Melkij,
> track_io_timing где? Я неслучайно его упомянул.

С этим есть сложности.

Спасибо за анализ, похоже есть ещё над чем поработать в текущей схеме.

[Александр Кубинцев]

Melkij, мы сделали деблоат - действительно всё стало заметно лучше.
У меня только вопрос: как вы посчитали объем прочитанных данных с диска?

[Melkij]

Александр Кубинцев,

Buffers: shared hit=79631 read=1385187 written=4601

shared hit - найдено и прочтено из shared_buffers
read - читали с файловой системы (возможно page cache системный, этого база не знает)
written - были вынуждены сами писать dirty блоки

Все эти числа измеряются блоками фиксированного размера в block_size байт. Может быть изменён только при сборке базы из исходников, потому с хорошей вероятностью можно считать что равен привычным 8кб.
(1 385 187+79 631)x8/1024 = 11 443 мегабайт

[Александр Кубинцев]

Melkij, благодарю

Answer 3

[Илья]

Вспомогательная таблица с полями "баланс", "user_id". Уникальный индекс по user_id, кластерный индекс(это важно!) по полю "баланс"
Триггер на изменение баланса в основной таблице исправляет значение во вспомогательной.

In cases where you are accessing single rows randomly within a table, the actual order of the data in the table is unimportant. However, if you tend to access some data more than others, and there is an index that groups them together, you will benefit from using CLUSTER. If you are requesting a range of indexed values from a table, or a single indexed value that has multiple rows that match, CLUSTER will help because once the index identifies the table page for the first row that matches, all other rows that match are probably already on the same table page, and so you save disk accesses and speed up the query.

https://www.postgresql.org/docs/9.1/sql-cluster.html

UPD

Я придумал другое решение.
1) разберитесь с размером основной таблицы, скорее всего её раздуло
https://www.youtube.com/watch?v=-GNHIHEHDmQ
2) сделайте индекс по полю Balance с опцией Include Columns и добавьте в него user_id. Тогда при запросе

select balance, user_id from your_table_name order by balance

все данные будут вычитаны из индекса, а это значительно сократит вам нагрузку

Comments

[Александр Кубинцев]

в принципе это и позволяет сделать materialized view

[Илья]

Александр Кубинцев, кластерный индекс?

[Александр Кубинцев]

Илья, пардон, прочитал целиком описание по ссылке. Сперва немного о другом подумал. Надо попробовать.

[Илья]

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

[Илья]

Александр Кубинцев, я вот еще что подумал. Сейчас у вас происходит довольно длинная транзакция по построению топа. Основная таблица не раздувается от этого? Имеется ввиду table bloat который в некоторых сценариях случается на postgres.

Ну и ради всего 2.3 млн строк потрогали почти 12гб - с автовакуумом проблема точно.

То что писал Melkij как раз может быть из-за этого

[Александр Кубинцев]

Илья, я правильно понимаю, что CLUSTER при выполнении блокирует таблицу? Тогда это может быть проблемой.

Да, видимо сперва придётся разобраться с настройками БД.

[Илья]

Александр Кубинцев, да может. Я сейчас уточнил в документации. Придется периодически выполнять эту команду.

Я придумал другое решение.
1) разберитесь с размером основной таблицы, скорее всего её раздуло
https://www.youtube.com/watch?v=-GNHIHEHDmQ
2) сделайте индекс по полю Balance с опцией Include Columns и добавьте в него user_id. Тогда при запросе

select balance, user_id from your_table_name order by balance

все данные будут вычитаны из индекса, а это значительно сократит вам нагрузку

[Илья]

Добавлю это в ответ

[Melkij]

все данные будут вычитаны из индекса, а это значительно сократит вам нагрузку

Баланс этот соответственно часто изменяется.

Потому сомненья большие у меня по рациональности покрывающего индекса. Очень вероятно что из-за быстро протухающего visibility map получится без разницы, есть там include или нет там его. Только с include ещё и сам индекс будет больше.

[Илья]

Melkij, возможно. Я не очень представляю как будет работать postgres в этом случае. Протухшая visibility map заставит все читать из таблицы или из таблицы будут читаться только строки с протухшим флагом?

[Melkij]

Будут читаться страницы данных, про которые visibility map не сказал что они достоверно видны всем. То есть index only scan в плане всегда может решить поднять страницу самой таблицы и проверить видимость тапла. В идеальном случае обращений к блокам таблицы не будет, в худшем - идентично index scan.

[Илья]

Александр Кубинцев, отпишитесь, пожалуйста, если проверите этот вариант. Интересно.

[Илья]

Melkij, спасибо за разъяснение

[Александр Кубинцев]

Илья, сейчас пока разбираемся как чинить table bloat. Видео по вашей ссылке оказалось очень познавательным, кейс №1 однозначно случался. Что касается кластеризации, то всё бы ничего, но надо оценить время работы. Если эксклюзивный лок висеть будет более 2 сек, то это неприемлемо.
Что касается Include Columns, то попробую, если лечение не даст желаемого результата, но думаю должно нормализоваться всё.

[Илья]

Александр Кубинцев, кластеризация уже не кажется мне хорошей идеей. Это был быстрый ответ, который не вполне учитывал специфику postgres, а именно то что полноценного cluster index в нём нет. Но вот идея с покрывающим индексом может помочь.

Answer 4

[Сергей Еремин]

Надо посмотреть как часто игроки сморят на рейтинг и попробовать организационно решить. Например отвязать рейтинг от очков в игре и ввести "магический" прогресс-параметр (темп набора очков) . Тогда, по сути, точно ли ты посчитал место в рейтинге или нет -- пользователю проверить уже невозможно. Кроме того, можно предположить, что те кто с 1-го по 1000-ое место, интересуются своим рейтингом более серьезно, чем те что с 100000-го по 500000-е... И тогда простор и раздолье, как все можно реорганизовать. Например, раздели пользователей на группы -- Гуру, Профи, Салаги, Микроорганизмы (причем поделить можно по частоте обращений к рейтингу) -- для каждой группы своя таблица (можно даже в БД на отдельной ноде), а в таблицу пользователей добавь указатель к какой группе он принадлежит... Соответственно очки пиши в обе таблицы (это быстро), но индекс будет только на той таблице, что поменьше... При запросе рейтинга показывать пользователю, место в рейтинге только в его группе, а делать "большую сортировку" и раскидывать по группам -- раз в день во время низкой активности...

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

Comments

[Александр Кубинцев]

Организационные меры уже сделаны, спасибо. Но их недостаточно оказалось.
Менять же схему таблицы - очень громоздкое решение, я не могу тут все нюансы проекта описать.

Answer 5

[mayton2019]

Зачем вам сортировать все 50 миллионов? Задача топа - чтобы взять например top 10.
Сделайте себе временную табличку и по триггеру сливайте в нее по правилу паретто или больше 95%
где баланс больше X. И там будет не 50 миллионов а 100 тыс.

И эта мелкая табличка легко отсортируется и опубликуется.

Comments

[Александр Кубинцев]

Здесь такой способ не прокатит, т.к. имеем не топ-10 или топ-100, а топ-3000. При чем этих топов порядка 2000 штук сейчас на каждую игру. И в принципе я не сторонник добавлять логику в БД без крайней необходимости - это превращается в магию, которую тестировать неудобно.

[mayton2019]

Александр Кубинцев, почитайте про шаблон CQRS. Это не относится к БД. Это про архитектуру систем в принципе. Может вы пересмотрите постановку.

[Александр Кубинцев]

mayton2019, CQRS подразумевает серьёзный рефакторинг. А у нас легаси-код, при чём операции по изменению баланса производятся через 2 разных сервиса.

[mayton2019]

Как будет угодно