#26: Оптимизируем B+tree: копирование, пакетирование

[00:21] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает, как они работают, и делится знаниями со слушателями. Сегодня поговорим про проблемы B-деревьев и посмотрим, как их решают инженеры. Эти техники работают не только для баз данных, но и в любой другой программе. А ещё заглянем под капот MongoDB. Поехали!

[00:58] В 24-м выпуске мы познакомились с такой структурой данных, как B-tree и B+tree. Если вдруг вы не слышали этот выпуск — прямо сейчас ставьте на паузу текущий, включайте 24-й эпизод, а потом запрыгивайте сюда. B-дерево — прекрасная структура данных, она отлично работает с дисками. Именно поэтому большинство баз данных отдают предпочтение B-дереву и используют его в качестве индексов. Однако реальные системы, которые крутятся на серверах и обслуживают большое количество запросов, скорее всего используют модифицированную версию B+tree. Получается, лучшая структура данных на самом деле не лучшая? Ну, в какой-то степени да. Чтобы понять, как устроены модифицированные индексные структуры, давайте сначала разберёмся, какие проблемы есть у обычного B-дерева.

[01:48] Первая проблема — это блокировки. Есть забавный факт: в программировании мы используем термин «блокировка» (или lock на английском) вообще для всего. В Java, например, есть reentrant lock или read-write lock — это примитивы, которые помогают синхронизировать доступ к ресурсам в конкурентной среде. Ещё в Java есть примитив CountDownLatch — штука для обратного отсчёта: когда мы доходим до нуля, так называемая защёлка закрывается. Бывает полезно в конкурентном коде. Ирония в том, что в мире баз данных у нас тоже есть блокировки и защёлки, но обозначают они другие вещи.

[02:23] Смотрите. Блокировки в базах данных используются для синхронизации пользовательских транзакций — они работают на более высоком уровне, чем защёлки, которые как раз нужны, чтобы синхронизировать потоки. То есть защёлки в базах данных — это блокировки из языков программирования, а блокировки в базах данных — это про синхронизацию транзакций. Такие чудеса наименования. Мы сегодня говорим исключительно про защёлки. И каждый раз, когда я буду использовать термин «защёлка» или «блокировка», это одно и то же в рамках текущего эпизода — и обозначает это защёлку из мира баз данных, и ничего больше.

[03:06] Защёлки могут быть реализованы несколькими способами. Первый, самый очевидный — это mutex. Всё, что поток может с ним делать, — это либо захватить, либо отпустить, либо ждать, пока другой поток держит этот mutex. По сути, это ключевое слово synchronized в Java. Традиционная реализация — pthread mutex. Второй способ — это read-write lock. С ним поток может делать то же самое, что и с mutex, только каждое взаимодействие должно обладать атрибутом чтения или записи.

[03:35] Чтобы лучше понять разницу между mutex и read-write-блокировкой, представьте себе торговый центр. В холле стоит новенькая машина, на которую любуются посетители. А ещё эту машину можно взять в аренду и покататься полчаса по городу — эта опция не для всех. Так вот, те люди, которые смотрят на машину, — это аналоги потоков, которые захватывают блокировку на чтение: смотреть на машину одновременно может большое количество людей, и они даже мешать друг другу не будут. Но как только появляется желающий на ней покататься, он должен взять блокировку на запись. Таким образом, он дождётся всех, кто сейчас смотрит на машину, потом сядет и уедет кататься. А новые посетители — и те, кто хочет посмотреть, и те, кто хочет покататься, — вынуждены ждать. Другого варианта нет. Это аналог взятия блокировки на запись. А mutex? Это когда доступ к машине одновременно есть только у одного человека, вне зависимости от того, хочет ли он просто посмотреть или настроен покататься.

[04:32] Если подвести итог: read-write-блокировка позволяет многим потокам читать одновременно, но одному — писать; и пока он пишет, никто не сможет ни читать, ни писать. А mutex — это эксклюзивная блокировка, и захватывать её может один поток в один момент времени.

[04:50] B-деревья активно используют защёлки, и чаще всего это read-write lock. Нужны они для контроля одновременного доступа к дереву. Представьте: 100 потоков интенсивно взаимодействуют с одним деревом — читают, пишут, потом опять читают и снова пишут. При такой нагрузке дерево неизбежно будет разрастаться, а это приводит к структурным изменениям. Вначале дерево выглядело как кустик, а потом выросло до огромных размеров, и у него появились новые указатели на ноды, а старые уже недействительны. Получается, что пока один поток гуляет по указателям внутри дерева, другой поток в это же время может перезаписать указатели — и указатель на родителя, например, может стать недействительным.

[05:31] Так как они делают это одновременно, может произойти следующее: один поток считал адрес страницы и заснул, другой поток перезаписал указатель на эту страницу — вообще стёр старую и создал новую, — а первый поток проснулся и пошёл по указателю на уже несуществующую страницу. Это пример гонки данных, которая происходит из-за структурных изменений внутри дерева. Ещё у нас есть гонка данных в рамках одной страницы, когда оба потока модифицируют её содержимое. Защёлки помогают решить обе проблемы — но какой ценой? Смотрите.

[06:06] Представьте, что вы поток, который хочет что-то прочитать из дерева. Очевидно, он будет захватывать read-блокировки и блокировать каждую страницу отдельно, потому что, ну, он читает. Как он это будет делать? Представим себе дерево сверху: у него есть корень, у корня есть несколько дочерних нод, у тех — ещё несколько дочерних, а в конце — листовые ноды. Задача потока — пройти от корня до листовой ноды и считать оттуда данные. Он берёт блокировку на чтение на корень, потом берёт блокировку на чтение уже у одного потомка, потом у потомка этого потомка — и так у него получается путь сверху вниз до листа из блокировок на чтение. Это наивный подход к тому, как потоку безопасно пройти от верха к низу.

[06:52] Вообще, для чего они нужны этому потоку — он же может просто пройти без всяких блокировок? Как раз потому, что пока он там ходит, в это время могут произойти структурные изменения. Например, он думает, что в этом поддереве находится нужный ему элемент, а другой поток уже поменял структуру дерева, и в этом поддереве нужного элемента нет. Из-за того, что дерево постоянно балансируется, нужный элемент мог переехать в другое поддерево, про которое читающий поток не знает, потому что он ходит ещё по старой версии дерева. Поэтому ему обязательно нужно ставить блокировки на чтение, чтобы никто не мог перезаписать то, что он прочитал.

[07:27] Чтение — операция ещё более-менее несложная. Что будет при операции на запись? То же самое: поток идёт сверху и берёт блокировки уже на запись, потому что собирается записывать — делать insert или, например, delete. Потенциально он может изменить структуру дерева: перезаписать указатели, поменять содержимое страницы, — и ему нужно делать блокировки на запись. Основная проблема в том, что, когда таких потоков много, у нас появляется узкое место в виде рута и ближайших его чайлдов. Потому что этот корень постоянно находится под какой-то блокировкой: чтобы прочитать или записать, мы всегда берём блокировку. Получается, это одна точка, на которую каждый поток берёт блокировку и держит до тех пор, пока не сделает своё дело. По сути, мы превращаемся в однопоточную структуру данных. Это не оптимальный вариант, и так никто не делает — ни одна база данных такие блокировки не использует.

[08:24] А какие же всё-таки используют? Они используют метод так называемого крабинга (crabbing), и название у него не просто так — это действительно выглядит и представляется в голове как крабик. Представьте себе краба: у него есть как бы две ножки, и вот на этих двух ножках он прыгает, бегает. Когда мы берём блокировку на рут, держать мы её будем не всё время, пока доходим до листов, а только до тех пор, пока не взяли блокировку на следующего ребёнка. Почему? Смотрите: мы берём блокировку на чтение на рут, потом — так, в какое поддерево идти? Условие говорит, что в самое правое. Мы идём в самое правое поддерево, берём блокировку на чтение там — и вот мы, как крабик, встали на две ноды, заблокировали две read-блокировки: рут и один из его детей. Крабик стоит.

[09:10] Потом крабик поднимает свою ногу с рута, то есть отпускает блокировку, держит блокировку на ребёнке и оттуда принимает решение, куда идти дальше. И вот куда он пойдёт дальше — там он берёт блокировку. С этого момента он принимает решение, куда идти ещё, отпускает вторую, верхнюю блокировку и идёт вниз. И получается, что крабик сверху, от рута, шаг за шагом, один к одному, спускается вниз, там свои дела делает — и всё. Таким образом, рут у нас заблокирован только в момент принятия решения. Это небольшое количество времени, и узкое место перестаёт быть настолько узким.

[09:46] Но всё ещё им является, потому что иногда нам нужно взять и держать блокировку на запись на руте — ведь потенциально структурные изменения могут пройти вверх по дереву, от листа до рута. Если у нас дерево почти переполнено, то вставка последнего элемента приведёт к тому, что внизу одна страница расплитится на две; её сплит приведёт к сплиту верхней страницы, потому что указатель некуда будет писать; потом ещё верхней, ещё верхней. И вот это структурное изменение может дойти до рута — и тогда нам нужно держать блокировку на запись на руте, потому что такое может быть. Но, как показывает практика и статистика, происходит это крайне редко. И это неудивительно.

[10:28] Поэтому что делают алгоритмы? Они крабиком спускаются донизу с помощью блокировок на чтение. И если понимают, что всё, структурные изменения необходимы — то есть «я сейчас буду делать это структурное изменение», — мы возвращаемся назад в рут и проходим ещё раз, но уже с блокировкой на запись. Это так называемый оптимистичный подход к программированию вообще: когда мы предполагаем, что конкуренции не будет. В нашем конкретном случае мы предполагаем, что структурных изменений в дереве делать не будем, потому что оно плюс-минус сбалансированное, и нам нужно в один момент времени держать блокировку только на два узла, а не на всё дерево. А если это не так — идём вверх и уже всё блокируем жёстко: говорим «стоянка, всем стоять, я сейчас буду дерево сплитовать», и там происходит обслуживание. Но это случается крайне редко, поэтому это работает.

[11:19] Что обойти очень сложно — так это то, что у нас могут быть взаимные блокировки. Каждый раз, когда мы говорим про эти многопоточные блокировки, всегда всплывает термин deadlock. Казалось бы, если мы обходим дерево сверху вниз каждый раз, то deadlock не будет — дерево в целом можно представить как граф без циклов, а раз в нём нет циклов, то и взаимных блокировок быть не может. Но на самом деле в B+tree оно как бы зациклено. Каким образом? У нас могут быть указатели у детей на родителей, а ещё — указатели между листовыми узлами. Помните, мы разбирали в 24-м выпуске: чтобы делать fullscan, тот самый sequential access, и не прыгать по указателям, мы держим указатели на нижнем уровне — по сути, там лежит linked list, который можно обходить в две стороны. Поэтому циклы в дереве есть, и deadlock’и возможны.

[12:16] Один взял блокировку на запись, другой взял блокировку на запись — и они друг друга ждут. Одному нужно сделать структурное изменение, которое задействует два узла — текущий и рядом лежащий, — а рядом лежащий заблокирован, и ему самому нужно структурное изменение на этот узел. Ну вот, они друг на друга завязались. Во-первых, от этого никуда не уйти при такой организации, а во-вторых, это можно решить с помощью таймаутов. Думаю, кто-то когда-то наталкивался на такие проблемы — что-то вроде «fail to acquire lock»: смотря какая база данных, такое будет сообщение. То есть не получилось взять блокировку — надо ещё раз попробовать, делаем просто retry. Стандартная ситуация, её вот так решают и в языках программирования, и в базах данных: deadlock решается таймаутами.

[12:59] Итак, мы разобрали первую проблему B-деревьев — конкурентный доступ. Решение у этой проблемы есть, но оно не идеально. Вторая проблема B-деревьев — это огромное количество структурных изменений при интенсивной записи. А структурное изменение — это поход на диск. Давайте разберём несколько техник, которые позволяют прокачать ванильные B-деревья с защёлками.

[13:21] Есть такой подход. Вообще, в Java, например, у нас есть структуры данных, которые начинаются с префикса copy-on-write, а дальше что-то — CopyOnWriteArrayList. В базах данных есть такое понятие, как copy-on-write B+tree. Это обычная структура данных, B+tree, которую мы себе все представляем, но она не делает мутирующих изменений внутри страниц. Одним словом, copy-on-write значит, что мы, да, делаем копирование при записи, но ещё это явно говорит, что элементы структуры данных иммутабельны. Таким образом, эти внутренние ноды или страницы нельзя изменить.

[13:55] А тот факт, что их нельзя изменить, означает, что мы можем читать их в любой момент времени и не бояться, что кто-то конкурентно изменит состояние страницы — например, перезапишет ссылки на другие страницы или изменит содержимое, удалит какие-то ключи. Если мы прочитали эту структуру данных — она существует, её никто не поменяет. Это круто, потому что тогда нам не нужны блокировки: не нужно брать блокировку на запись, если мы хотим что-то записать, и не нужно брать блокировку на чтение, если мы хотим прочитать. Потому что если мы читаем — мы никого не боимся и никому не должны об этом говорить, структура неизменяемая. А если мы записываем — мы не можем записать в существующую страницу, и таким образом никому не мешаем читать.

[14:37] Но записывать-то как-то надо, поэтому страницы просто копируются с добавлением какого-то нового элемента. Если мы вставляем — копируем соседнюю и вставляем туда элемент; если удаляем — копируем соседнюю и удаляем оттуда элемент. Таким образом обеспечивается многоверсионность дерева: пока один поток читает, другой пошёл, записал, создал новую версию дерева со скопированными туда указателями, — а старые ветки поддерева, которые были скопированы и модифицированы в процессе, становятся устаревшими. Но их никто не удаляет, сборщик мусора их не собирает, потому что кто-то их пока ещё читает.

[15:14] Правда, читающий поток при таком подходе, естественно, может читать данные, которые во времени уже устарели. Это такое ограничение — не серебряная пуля. Если мы что-то прочитали через такую структуру данных и нигде не взяли блокировку, никому не сказали «не записывай, пока я читаю» — это может быть проблемой. Мы потом разберём в следующих выпусках, почему и в каких случаях, но такое ограничение у структуры данных, конечно, есть. И поэтому, возможно, есть и более удачные способы того же самого подхода — не copy-on-write, а что-то другое; но это мы тоже разберём потом.

[15:50] В проекте OpenLDAP, насколько я знаю и насколько пишут в книжках, используется как раз такое copy-on-write B+tree. OpenLDAP использует движок хранения данных внутри себя, и этот движок использует copy-on-write B+tree. Называется движок LMDB — Lightning Memory-Mapped Database. Кроме LDAP, я, вроде бы, не знаю, кто ещё использует LMDB — если кто-то знает, пишите. Но даже прецеденты в продакшене есть: OpenLDAP — довольно матёрая система, её много кто использует, поэтому copy-on-write B+tree уже применяется в реальном продакшене. То есть если до этого мы изучали только структуры данных, которые кто-то когда-то придумал, но в чистом виде их сейчас в продакшене никто не использует — потому что время не стоит на месте, мы изобретаем новые алгоритмы и улучшаем существующие, — то вот сейчас мы познакомились с версией B+tree, которая используется в реальном продакшене.

[16:46] А что ещё используется в реальном продакшене? Это система, тоже storage engine, которая называется WiredTiger. Думаю, некоторые из вас краем уха слышали про WiredTiger, RocksDB — про них иногда говорят в контексте storage engine. Так вот, storage engine под названием WiredTiger используется в MongoDB. Там есть несколько вариантов сториджа, WiredTiger — один из них, и он представляет как построчное, так и поколоночное хранение. Сейчас мы говорим о построчном.

[17:20] Там есть интересная внутренняя структура данных, которая называется Lazy B-tree или Buffered B-tree — не суть, как её назвать. Это такая версия B+tree, которая решает проблему интенсивных записей и интенсивных походов на диск при большом количестве запросов на запись. Решается это следующим образом. Представьте: у вас есть B+tree — корень, у него дети, у детей дети, и где-то там листовые страницы. Когда мы пишем какое-то обновление в страницу, мы должны когда-то отправить её на диск — вот в такой парадигме работаем. А что если писать не в страницу напрямую — не в этот байтовый массив дописывать что-то или стирать, — а работать в языке программирования с некоторой абстракцией?

[18:08] Назовём её, например, BufferedPage. Внутри себя она имеет ссылку на реальную страницу, но ещё имеет буфер — пакеты апдейтов, или дельты. Назвать можно по-разному, но суть в том, что это буфер изменений, и каждое изменение — это некоторая дельта. Условно, когда я добавляю единичку, я не иду в страницу и не мутирую слот массива, не дописываю туда новое значение. Нет — я говорю, что кладу в буфер, по сути в маленькую-маленькую очередь: «добавить элемент один», «добавить элемент два», «удалить элемент два», «добавить элемент три». Такая вот очередь, довольно маленькая, но она хранит локальные для страницы апдейты — эти дельты, операции.

[18:53] И когда мы работаем с этой абстракцией, с BufferedPage, мы говорим ей: «дай-ка мне содержимое страницы» или «запиши туда что-то». То есть такие верхнеуровневые методы; во внутреннее устройство мы уже не влезаем. При чтении, помимо того что у нас есть source-страница — та, что на диске и представлена в памяти, реально хранит данные, так называемый initial page, — есть ещё вот этот буфер дельт. И во время чтения буфер дельт каждый раз накладывается на содержимое, и возвращается уже актуальная версия страницы. Получается, под капотом при чтении каждый раз производится дополнительная работа: мы применяем эти дельты к странице и отдаём актуальное состояние.

[19:34] Это дополнительная работа каждый раз при чтении. Но зато при записи в страницу мы вообще не паримся: ничего не мутируем, не перезаписываем, не идём на диск — просто забрасываем в буфер. Это стандартный подход оптимизации на запись: у нас есть буфер, мы в него закидываем, но при чтении платим цену накладывания дельт. Так вот, этот буфер может довольно быстро разрастись. И в какой-то момент, когда он достигает порогового значения, фоновый процесс обходит все страницы, записывает их содержимое, схлопывает эти буферы и складывает все дельты в initial-страницу, в сорцовую, на диск, и обнуляет буфер. То есть перезаписывает содержимое страницы, но делает это очень редко, и делает это фоновый процесс.

[20:19] Таким образом, потоки на чтение читают сколько угодно, потоки на запись пишут сколько угодно, а некоторый демон обходит дерево, схлопывает буферы и перезаписывает страницы. Делает он это, чтобы в какой-то момент — представим, буфер разросся довольно большой, а мы там делаем плюс один, минус один, плюс один, минус один — вот дофига таких операций, которые, если схлопнуть, дают, по сути, ничего: получается динамическое пустое множество. А мы, однако, будем делать computation, нагружать CPU, чтобы всё это провернуть, потому что не знаем, какие ещё операции за этим последуют. Это накладные расходы на CPU, и поэтому буфер нужно периодически схлопывать — что и делает фоновый процесс.

[20:59] На таком принципе работает storage engine WiredTiger, который используется в MongoDB. Теперь вы знаете. Но не только он там может использоваться — про это мы потом поговорим; и не только такое представление B+tree, есть ещё колоночные представления внутри WiredTiger, которые работают по-другому. Но если, например, вас на собеседовании спросят — вы можете блеснуть такими знаниями, и с высокой вероятностью собеседующий не будет знать таких деталей, а вы будете.

[21:28] На этом выпуск подошёл к концу. Мы неплохо забурились в проблемы B-дерева и рассмотрели способы их решения — копирование при записи и пакетирование обновлений. Эти техники распространены не только в базах данных, но и в языках программирования, фреймворках, библиотеках. Я искренне надеюсь, что вы провели время с пользой. В следующих выпусках пойдём ещё дальше и познакомимся с новыми структурами данных. Будет интересно. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!