Как я уже писал выше - перечитываю 'Высоконагруженные приложен | dev notes
Как я уже писал выше - перечитываю "Высоконагруженные приложения" и кидаюсь в вас конспектами с самым соком. К слову, зачем читать книгу второй раз? Лично для себя открыл, что второе чтение оставляет в памяти максимальное количество полезной информации (а параллельное конспектирование основных тем - цементирует прочитанное). Прочитав же 1 раз - в течении пары месяцев 90% забывается.
Итак, сегодня у нас 3-я глава: подсистемы хранения данных. Клеппман описывает, как и на основе чего устроены индексы в современных СУБД и раскрывает 2 основные структуры данных, на основе которых индексы строятся. Зачем это знать? Во-первых, на больших нагрузках нужно понимать, как оптимизировать или скорость, или чтение индексов, в зависимости от задачи. Во-вторых, понимание того, как устроены индексы полезно для выбора СУБД на очередной проект. В-третьих, это просто очень интересно :)
Глава большая, поэтому ниже - конспект первой половины.
Любые индексы в реляционных СУБД, как правило, замедляют запись. Индексы надо подбирать так, чтобы чтение было быстрым, но и запись осталась быстрой.
При любой записи на диск - индекс тоже обновляется, всегда.
Хеш-индексы - индексы, на основе hash-таблицы - один из самых распространённых типов индексов. Например, так работает подсистема хранения Bitcask в NoSQL СУБД Riak.
Уплотнение (compaction) сегментов журнала - операция, отбрасывающая дублирующиеся ключи и сохраняющая только последний ключ, тем самым уменьшая дисковое место, занимаемое файлами журнала. Уплотнённые сегменты, если их размер значительно уменьшился - можно слить между собой.
SS-таблица
Отсортированная строковая таблица (sorted string table, SS-таблица) - отсортированная по ключу таблица, хранимая на диске, где каждый ключ встречается 1 раз (благодаря автоматическому процессу уплотнения и слияния сегментов). Преимущества перед журнальными сегментами с хеш-индексами:
1. Объединение сегментов выполняется просто и эффективно, благодаря тому, что сегменты отсортированы. При слиянии мы читаем сразу все сегменты, и оставляем последний записанный ключ в результирующем сегменте.
2. Чтобы найти в файле конкретный ключ, не нужно хранить индекс всех ключей в оперативной памяти. Если мы знаем индекс соседних ключей от искомого - точно можно сказать, что он будет между ними, и нам достаточно посмотреть срез данных между соседями.
3. Блоки, на которые есть индексы в ОП можно сжимать пачками по несколько килобайт, так как расжать и просмотреть несколько Кб данных можно очень быстро.
Красно-чёрные деревья или AVL-деревья позволяют записывать ключи в любом порядке, а читать только в нужном.
Процесс записи в SS-таблицу выглядит так:
1. При поступлении записи помещаем её в оперативной памяти в сбалансированную структуру данных, например в красно-чёрное дерево.
2. Когда размер записи превышает определённое пороговое значение, например несколько мегабайт, записываем его на диск в фиде файла SS-таблицы. Это операция выполняется достаточно быстро, так как записи на выходе отсортированы. Файл становится последним сегментов базы данных.
3. При поиске данных сначала ищем их в memory-сегменте, если там нет, то в последнем, затем в предпоследнем и так далее.
4. В фоне время от времени запускается процесс уплотнения и слияния данных.
5. Так же на диске нужно держать отдельный журнал - копию со всеми записанными в memory-таблицу данными, чтобы в случае фатального сбоя восстановить memory-таблицу.
А это вообще где-то применяется, спросишь ты? Да, например в levelDB и rocksDB - библиотеках, которые можно юзать сами по себе, а можно в рамках других СУБД. Так, levelDB используется в СУБД Riak. Аналогичные системы используются так же в Cassandra и HBase.
Подсистемы хранения, основанные на принципах слияния и уплотнения, часто называют LSM (Log-Strucrured Merge-Tree) подсистемами.
Часто с LSM-системами используют фильтры Блума - структуру данных, позволяющую узнать, есть ли в множестве заданный элемент. Это позволяет не просматривать все сегменты в поисках элемента, которого в них нет.
