Шардирование

1.1 Что такое шардирование?

Если упорно гуглить, то выяснится, что между так называемым партиционированием и так называемым шардингом достаточно размытая граница. Каждый называет все, что хочет, чем хочет. Одни люди различают горизонтальное партиционирование и шардинг. Другие говорят, что шардинг — это определенный вид горизонтального партиционирования.

Единого терминологического стандарта, который был бы одобрен отцами-основателями и в ISO сертифицирован, я не нашел. Личное внутреннее убеждение примерно такое: Partitioning в среднем — это «режем базу на куски» произвольно взятым образом.

• Vertical partitioning — поколоночно. Например, есть гигантская таблица на пару миллиардов записей в 60 колонок. Вместо того, чтобы держать одну такую гигантскую таблицу, держим 60 не менее гигантских таблиц по 2 млрд записей — и это не поколоночная база, а вертикальное партиционирование (как пример терминологии).
• Horizontal partitioning — режем построчно, может быть, внутри сервера.

Неловкий момент здесь в тонком отличии между горизонтальным партиционированием и шардированием. Меня можно на куски резать, но я уверенно вам не скажу, в чем оно заключается. Есть ощущение, что шардирование и горизонтальное партиционирование — это примерно одно и то же.

Шардирование — это в целом, когда большая таблица в терминах баз или проколлекция документов, объектов, если у вас не совсем база данных, а document store, режется именно по объектам. То есть из 2 млрд объектов выбираются куски не важно, какого размера. Объекты сами по себе внутри каждого объекта не разрезаем на куски, на отдельные колонки не раскладываем, а именно пачками раскладываем в разные места.

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

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

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

1.2 Делим неделимое

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

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

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

Это приводит к следующему:

• Увеличивается bandwidth — пропускная способность.
• Latency не меняется, то есть каждый, так сказать, worker или consumer в данном случае, получает свое. Разные запросы обслуживаются примерно за одно время.
• Либо и то, и другое, и еще high availability (репликация).

Зачем bandwidth? У нас иногда могут возникать такие объемы данных, которые не влазят — не понятно куда, но не влазят — на 1 {ядро | диск | сервер | ...}. Просто не хватает ресурсов и все. Для того, чтобы с этим большим датасетом работать, надо его нарезать.

Зачем latency? На одном ядре просканировать таблицу из 2 млрд строк в 20 раз медленнее, чем просканировать 20 таблиц на 20 ядрах, делая это параллельно. Данные слишком медленно обрабатываются на одном ресурсе.

Зачем high availability? Либо нарезаем данные, для того чтобы делать и одно, и другое одновременно, и заодно несколько копий каждого шарда — репликация обеспечивает высокую доступность.

1.3 Простой пример «как сделать руками»

Условный шардинг можно выпилить посредством тестовой таблицы test.documents на 32 документа, и генерацией из этой таблицы 16 тестовых таблиц примерно по 2 документа test.docs00, 01, 02, ..., 15.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Почему примерно? Потому что априори мы не знаем, как распределены id, если от 1 до 32 включительно, то будет ровно по 2 документа, иначе — нет.

Делаем мы это вот зачем. После того, как мы сделали 16 таблиц, мы можем «захавать» 16 того, что нам нужно. Вне зависимости от того, во что мы уперлись, мы можем на эти ресурсы распараллелиться. Например, если не хватает дискового пространства, будет иметь смысл разложить эти таблицы по отдельным дискам.

Все это, к несчастью, не бесплатно. Подозреваю, что в случае с каноническим SQL-стандартом (давно не перечитывал SQL-стандарт, возможно, его давно не обновляли), нет официального стандартизированного синтаксиса для того, чтобы любому SQL-серверу сказать: «Дорогой SQL-сервер, сделай мне 32 шарда и разложи их на 4 диска». Но в отдельно взятых реализациях зачастую есть конкретный синтаксис для того, чтобы сделать в принципе то же самое. В PostgreSQL есть механизмы для партиционирования, в MySQL MariaDB есть, Oracle наверняка это все сделал уже давным-давно.

Тем не менее, если мы это делаем руками, без поддержки базы данных и в рамках стандарта, то платим условно сложностью доступа к данным. Там, где было простое SELECT * FROM documents WHERE id=123, теперь 16 x SELECT * FROM docsXX. И хорошо, если мы пытались доставать запись по ключу. Значительно более интересно, если мы пытались доставать ранний диапазон записей. Теперь (если мы, подчеркиваю, как бы дураки, и остаемся в рамках стандарта) результаты этих 16 SELECT * FROM придется объединять в приложении.

Какого изменения производительности ожидать?

• Интуитивно — линейного.
• Теоретически — сублинейного, потому что Amdahl law.
• Практически — может быть, почти линейно, может быть, нет.

На самом деле, правильный ответ — неизвестно. Ловким применением техники шардирования можно добиться значительного сверхлинейного ухудшения работы вашего приложения, да еще DBA прибежит с раскаленной кочергой.

Посмотрим, как этого можно добиться. Понятно, что просто поставить настройку в PostgreSQL shards=16, а дальше оно само взлетело — это не интересно. Давайте подумаем, как можно добиться того, чтобы от шардирования в 16 раз мы бы затормозили в 32 — это интересно с той точки зрения, как бы этого не делать.

Наши попытки ускориться либо затормозить всегда будут упираться в классику — в старый добрый закон Амдала (Amdahl law), который говорит, что не бывает идеальной распараллелизации любого запроса, всегда есть некая последовательная часть.

1.4 Amdahl law

Всегда есть serialized часть.

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

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

Кроме того, её влияние меняется и может ощутимо подрасти, например, если мы нарежем нашу таблицу — давайте поднимем ставки — из 64 записей на 16 таблиц по 4 записи, эта часть изменится. Конечно же, судя по таким гигантским объемам данных, мы работаем на мобильном телефоне и 86 процессоре 2 МГц, у нас и файлов-то не хватает, которые можно одновременно держать открытыми. Видимо, с такими вводными, мы по одному файлу за раз открываем.

• Было Total = Serial + Parallel. Где, например, parallel — это вся работа внутри DB, а serial —отправка результата в клиента.
• Стало Total2 = Serial + Parallel/N + Xserial. Например, когда общий ORDER BY, Xserial>0.

Этим нехитрым примером я пытаюсь показать, что появляется некое Xserial. Кроме того, что всегда есть сериализованная часть, и того, что мы пытаемся работать с данными параллельно, появляется дополнительная часть для обеспечения этой нарезки данных. Грубо говоря, нам может понадобиться:

• найти во внутреннем словаре базы данных эти 16 таблиц;
• открыть файлы;
• аллоцировать память;
• разаллоцировать память;
• смерджить результаты;
• синхронизироваться между ядрами.

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

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

Предположим, что у нас есть некая сериализованная часть обработки запроса, которая занимает всего 5%: serial = 0.05 = 1 / 20.

Интуитивно казалось бы, что при сериализованной части, которая занимает всего 1/20 от обработки запроса, если мы распараллелим обработку запроса на 20 ядер, она станет примерно в 20, в худшем случае в 18, раз быстрее.

На самом деле математика — штука бессердечная:

wall = 0.05 + 0.95/num_cores, speedup = 1 / (0.05 + 0.95/num_cores)

Оказывается, что если аккуратно посчитать, при сериализованной части в 5%, ускорение будет в 10 раз (10,3), а это 51% по сравнению с теоретическим идеальным.

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

Когда остается только 1% сериализованной работы, а 99 % параллелится, значения ускорения несколько улучшаются:

Для совершенно термоядерного запроса, который натурально часами исполняется, и подготовительная работа и сборка результата занимают очень мало времени (serial = 0.001), мы увидим уже хорошую эффективность:

Обратите внимание, 100% мы не увидим никогда. В особо хороших случаях можно увидеть, например, 99,999%, но не ровно 100%.