Пятница, 26.04.2024, 18:16
Мой персональный сайт Добрым людям smart & sober

Главная Регистрация Вход
Приветствую Вас, Гость · RSS
Калькулятор


Меню сайта
Календарь
«  Февраль 2011  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
28


Форма входа


Архив записей
Мини-чат


Категории раздела


Наш опрос
В чем заключается ваш смысл жизни
Результаты | Архив опросов
Всего ответов: 154
 
Главная » 2011 » Февраль » 4 » Распараллеливание длительных операций
16:28
Распараллеливание длительных операций
Мне часто приходится сталкиваться с задачами, требующими от базы данных очень большой производительности при обработке больших массивов данных. Сегодня я расскажу об очень простом, но действенном приеме, который может вас выручить, если база уже не поспевает за тем количеством данных, которые скапливаются и должны быть обработаны. Метод не зависит от базы данных, но по привычке публикую в блог PostgreSQL, и пример будет именно на ней. Давайте сразу перейдем к примеру.

Сферический конь
Предположим, мы говорим о простейшем биллинге (понятно, что метод применим не только для биллинга, но с ним это будет выглядеть достаточно наглядно). Таблица, в которой скапливаются данные о звонках абонентов будет в нашем случае иметь такой формат:
CREATE TABLE billing.calls
(
call_id BIGINT,
call_time TIMESTAMP,
subscriber_id INTEGER,
duration INTERVAL
);

* This source code was highlighted with Source Code Highlighter.

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

Для тарификации у нас есть функция БД с такой сигнатурой:
FUNCTION calculate(IN subscriber_id INTEGER, IN duration INTERVAL, OUT status_code text) RETURNS void

* This source code was highlighted with Source Code Highlighter.

Тарификацию мы проводим запуская раз в 5 минут вот такой запрос:
SELECT calculate(subscriber_id, duration) FROM billing.calls;

* This source code was highlighted with Source Code Highlighter.

И в один прекрасный момент мы понимаем, что этот запрос просто не успевает выполниться за 5 минут. За это время набегает еще больше данных, потом еще, и вот мы сидим и ждем ночи, когда поток чуть-чуть ослабнет, и очередь наконец разгребется. Такая вот перспектива. Надо сказать, что сидели и ждали мы не в одиночку. Вместе с нами просиживали 3 (к примеру) оставшихся ядра нашего сервера, пока одно корпело над запросом. PostgreSQL, к сожалению, не умеет распараллеливать запросы сам, но в нашем случае этого и не нужно. Намного лучшие результаты даст очень простая и очевидная уловка. Создаем индекс по функции «остаток от деления subscriber_id на 4»:
CREATE INDEX billing.calls_subscriber_id_mod_idx ON billing.calls USING btree ((subscriber_id % 4));

* This source code was highlighted with Source Code Highlighter.

А теперь запускаем в четыре потока (например четыре разных джоба):
SELECT calculate(subscriber_id, duration) FROM billing.calls WHERE subscriber_id % 4 = @mod;

* This source code was highlighted with Source Code Highlighter.

где @mod равен 0,1,2 или 3 (для каждого потока свой).

В результате


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

Метод применим для любой базы, поддерживающей индекс по функциям (Oracle, Postgresql). В случае MSSQL можно создать calculated column и индекс по ней. В MySQL поддержки функциональных индексов нет, но, в качестве обходного пути, можно создать новый столбец с индексом по нему, и обновлять его триггером.

комментарии (65)

  • Как говорят: «дёшево и сердито». Хорошее решение всегда простое. Спасибо за заметку.
  • Спасибо за топик. Сам работаю c хранилищами данных, так что интересно узнать, как там с OLTP-системами люди работают, для расширения кругозора, так сказать :)

    Еще маленькое лирическое отступление, а то сферический конь получился хромым :)
    Все-таки должно быть поле, например, billed (false или true), которое заполняется по-умолчанию false и переводится в true внутри функции.
    Тогда функция должна работать только по тем записям, где billed = false. Ошибочка небольшая и вообще топик не о том, но она способствует некоторому непониманию.
    • Да, вы правы, так даже нагляднее. Индекс тогда выглядит как:
      CREATE INDEX billing.calls_subscriber_id_mod_idx ON billing.calls USING btree (subscriber_id % 4, billed);

      * This source code was highlighted with Source Code Highlighter.

      И выборка идет еще шустрее.
      • Не знаю, как это реализовано в Postgres, но в оракле я бы стал в данном случае использовать индекс по (billed, subscriber_id % 4), таким образом, чтобы range scan шел сначала по всем записям, у которых billed = 1, а затем уже делил на шарды по модулю.
        • Тьфу, то есть по остатку от деления. И в оракле это будет не subscriber_id%4, а mod(subscriber_id, 4).
          • Да, вы правы, спешил когда писал.
          • В постгре еще можно partial индекс создать, тогда вообще проблем никаких:
            CREATE INDEX billing.calls_subscriber_id_mod_idx ON billing.calls USING btree (subscriber_id % 4) WHERE billed = FALSE;

            * This source code was highlighted with Source Code Highlighter.
    • На самом деле этот прием я подглядел когда-то давно именно в биллинге (есть такой замечательный биллинг — БИС от петер-сервис, его Мегафон использует). У них отложенное применение скидок, и по таблице вызовов они идут в 8 или 16 потоков используя похожий индекс по полю % 8 или 16.
  • Хочу уточнить. Постгрес точно будет использовать индекс в случае запроса?

    SELECT calculate(subscriber_id, duration) FROM billing.calls WHERE subscriber_id % 4 = @mod;

    * This source code was highlighted with Source Code Highlighter.


    Самому проверить пока негде, а идея нравится. Думаю, дать ей шанс :)
    • Думаю, там имелось ввиду выражение call_id % 4, имеющее равномерное распределение.
      Если брать subscriber_id % 4, то в каждом «шарде» будет разное число записей, зависящее от трафика конкретных абонентов.
      • Нет, имелось в виду именно subscriber_id % 4. Смысл в том, чтобы один абонент обрабатывался всегда в одном потоке — иначе мы возможно встрянем на блокировке, например, когда два потока возьмутся баланс одному абоненту обновлять.
        • Понял. В принципе, если у нас тысячи/миллионы абонентов и мы разделим их на 4 равных по количеству «лагеря», то и суммарный трафик у них будет примерно одинаков. Зато действительно удастся избежать лишних блокировок и потерянных обновлений.
          • Ага, когда у вас каждый поток тарифицирует по 100 тысяч вызовов за раз, встрять на блокировке на каком-то несчастном абоненте никак нельзя.
    • Да, использует.
      • Да использует. Но толку от него никакого.

        Без индекса:
         Seq Scan on a (cost=0.00..186284.08 rows=47345 width=8) (actual time=0.025..9414.434 rows=2500000 loops=1)
         Filter: ((num % 4) = 0)
         Total runtime: 12837.127 ms
        (3 rows)


        С индексом:
         Bitmap Heap Scan on a (cost=944.32..47774.81 rows=47345 width=8) (actual time=10434.219..21909.066 rows=2500000 loops=1)
         Recheck Cond: ((num % 4) = 0)
         -> Bitmap Index Scan on a_idx (cost=0.00..932.48 rows=47345 width=0) (actual time=10423.375..10423.375 rows=2500000 loops=1)
         Index Cond: ((num % 4) = 0)
         Total runtime: 25484.070 ms

  • спасибо! попробуем применить на практике
  • Действительно, вызывает некоторое сомнение эффективность такого индекса
  • Сейчас стоит задача на постгресе — сделать апдейт 500 000 записей (информация о книгах) из одной таблицы импорта в 3 таблицы живых данных. На девелоперской машине занимает около 15 мин, а на VPS больше часа. Ваш пост открыл мне глаза на то как можно легко и изящно ускорить процесс импорта. Спасибо.
  • pg_try_advisory_lock() как раз для таких задач.
    dklab.ru/chicken/nablas/53.html
    • Обалденно, спасибо большое, не знал об этом)
  • Подправьте в статье
    CREATE INDEX billing.calls_subscriber_id_mod_idx ON billing.calls USING btree ((subscriber_id % 4));

    по крайней мере Postgres 8.4.1 так требует
    • Подправил, спасибо
  • имхо btree индекс с таким плохим распределением не будет хорошо работать, возможно даже без него будет лучше — попробуйте

    Если кстати процесса всего 4 и очень хочется индекс, то эффективнее будет сделать четыре индекса вида CREATE INDEX calls_idx$1 ON billing.calls WHERE id%4=$1
    • CREATE INDEX calls_idx$1 ON billing.calls (id) WHERE id%4=$1
      • Да, тоже правильно. Можно еще bitmap индекс создать. А вообще если мы каждый раз чешем по всей таблице, то индекс выигрыш даст минимальный, а вот если появляется поле billed (как выше в комментариях), то ситуация меняется. В примере billed нет чтобы не отвлекать внимание от сути.
        • если чесать по всей таблице, то sequence scan сильно дешевле перебора по индексу из-за отсутствия random seek. В идеале постгресс сам это понимает и не пользует индекс, на практике за этим надо следить, особенно на больших таблицах и/или функциональных индексах
          • Не, если потоков 16, то выигрыш есть:).

Просмотров: 704 | Добавил: Breger | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Copyright MyCorp © 2024