Распараллеливание длительных операций - 4 Февраля 2011

Калькулятор

Меню сайта

Календарь

Форма входа

Архив записей

Мини-чат

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

Наш опрос

Главная » » Распараллеливание длительных операций

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)

- skyogre,
- 25 ноября 2009, 10:56
- #
- ↓
- - +2
Как говорят: «дёшево и сердито». Хорошее решение всегда простое. Спасибо за заметку.
- nblxa,
- 25 ноября 2009, 11:11
- #
- ↓
- - +1
Спасибо за топик. Сам работаю c хранилищами данных, так что интересно узнать, как там с OLTP-системами люди работают, для расширения кругозора, так сказать :)

Еще маленькое лирическое отступление, а то сферический конь получился хромым :)
Все-таки должно быть поле, например, billed (false или true), которое заполняется по-умолчанию false и переводится в true внутри функции.
Тогда функция должна работать только по тем записям, где billed = false. Ошибочка небольшая и вообще топик не о том, но она способствует некоторому непониманию.
- - aymeshkov,
  - 25 ноября 2009, 12:06
  - #
  - ↑
  - ↓
  - - +1
  Да, вы правы, так даже нагляднее. Индекс тогда выглядит как:
  
  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.
  
  И выборка идет еще шустрее.
  - - nblxa,
    - 25 ноября 2009, 12:12
    - #
    - ↑
    - ↓
    - 0
    Не знаю, как это реализовано в Postgres, но в оракле я бы стал в данном случае использовать индекс по (billed, subscriber_id % 4), таким образом, чтобы range scan шел сначала по всем записям, у которых billed = 1, а затем уже делил на шарды по модулю.
    - nblxa,
      25 ноября 2009, 12:15
      #
      ↑
      ↓
      
      +1
      Тьфу, то есть по остатку от деления. И в оракле это будет не subscriber_id%4, а mod(subscriber_id, 4).
      - aymeshkov,
        25 ноября 2009, 12:18
        #
        ↑
        ↓
        
        +1
        
        Да, вы правы, спешил когда писал.
      - aymeshkov,
        25 ноября 2009, 12:20
        #
        ↑
        ↓
        
        +2
        
        В постгре еще можно 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.
- - aymeshkov,
  - 25 ноября 2009, 12:10
  - #
  - ↑
  - ↓
  - - +1
  На самом деле этот прием я подглядел когда-то давно именно в биллинге (есть такой замечательный биллинг — БИС от петер-сервис, его Мегафон использует). У них отложенное применение скидок, и по таблице вызовов они идут в 8 или 16 потоков используя похожий индекс по полю % 8 или 16.
- pasha_golub,
- 25 ноября 2009, 11:12
- #
- ↓
- - 0
Хочу уточнить. Постгрес точно будет использовать индекс в случае запроса?

SELECT calculate(subscriber_id, duration) FROM billing.calls WHERE subscriber_id % 4 = @mod; * This source code was highlighted with Source Code Highlighter.

Самому проверить пока негде, а идея нравится. Думаю, дать ей шанс :)
- - nblxa,
  - 25 ноября 2009, 11:43
  - #
  - ↑
  - ↓
  - - 0
  Думаю, там имелось ввиду выражение call_id % 4, имеющее равномерное распределение.
  Если брать subscriber_id % 4, то в каждом «шарде» будет разное число записей, зависящее от трафика конкретных абонентов.
  - - aymeshkov,
    - 25 ноября 2009, 11:59
    - #
    - ↑
    - ↓
    - +1
    Нет, имелось в виду именно subscriber_id % 4. Смысл в том, чтобы один абонент обрабатывался всегда в одном потоке — иначе мы возможно встрянем на блокировке, например, когда два потока возьмутся баланс одному абоненту обновлять.
    - nblxa,
      25 ноября 2009, 12:05
      #
      ↑
      ↓
      
      0
      Понял. В принципе, если у нас тысячи/миллионы абонентов и мы разделим их на 4 равных по количеству «лагеря», то и суммарный трафик у них будет примерно одинаков. Зато действительно удастся избежать лишних блокировок и потерянных обновлений.
      - aymeshkov,
        25 ноября 2009, 12:12
        #
        ↑
        ↓
        
        0
        
        Ага, когда у вас каждый поток тарифицирует по 100 тысяч вызовов за раз, встрять на блокировке на каком-то несчастном абоненте никак нельзя.
- - aymeshkov,
  - 25 ноября 2009, 11:59
  - #
  - ↑
  - ↓
  - - 0
  Да, использует.
  - - potapuff,
    - 25 ноября 2009, 12:14
    - #
    - ↑
    - ↓
    - 0
    Да использует. Но толку от него никакого.
    
    Без индекса:
    
    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
    - nblxa,
      25 ноября 2009, 12:17
      #
      ↑
      ↓
      
      +1
      коммент выше — habrahabr.ru/blogs/postgresql/76309/#comment_2217268
      в таком случае использование индекса будет оправдано
- mazy,
- 25 ноября 2009, 11:26
- #
- ↓
- - 0
спасибо! попробуем применить на практике
- potapuff,
- 25 ноября 2009, 11:26
- #
- ↓
- - +1
Действительно, вызывает некоторое сомнение эффективность такого индекса
- Gotaxe,
- 25 ноября 2009, 11:41
- #
- ↓
- - 0
Сейчас стоит задача на постгресе — сделать апдейт 500 000 записей (информация о книгах) из одной таблицы импорта в 3 таблицы живых данных. На девелоперской машине занимает около 15 мин, а на VPS больше часа. Ваш пост открыл мне глаза на то как можно легко и изящно ускорить процесс импорта. Спасибо.
- phoebus,
- 25 ноября 2009, 12:05
- #
- ↓
- - +3
pg_try_advisory_lock() как раз для таких задач.
dklab.ru/chicken/nablas/53.html
- - aymeshkov,
  - 25 ноября 2009, 12:23
  - #
  - ↑
  - ↓
  - - 0
  Обалденно, спасибо большое, не знал об этом)
- potapuff,
- 25 ноября 2009, 12:07
- #
- ↓
- - +1
Подправьте в статье
CREATE INDEX billing.calls_subscriber_id_mod_idx ON billing.calls USING btree ((subscriber_id % 4));

по крайней мере Postgres 8.4.1 так требует
- - aymeshkov,
  - 25 ноября 2009, 12:13
  - #
  - ↑
  - ↓
  - - +1
  Подправил, спасибо
- maxcom,
- 25 ноября 2009, 12:10
- #
- ↓
- - 0
имхо btree индекс с таким плохим распределением не будет хорошо работать, возможно даже без него будет лучше — попробуйте

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

Просмотров: 742 | Добавил: Breger | Рейтинг: 0.0/0

Всего комментариев: 0

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]