Это нужно сказать вместе с BTree.Все мы знаем, что BTree — это Дерево Баланса.Чтобы сохранить характеристики Балансировки, дерево нужно корректировать каждый раз, когда оно читается, что является значительной потерей времени. В некоторых сценариях использования (например, при сканировании веб-страниц Google) требуется высокопроизводительная запись, в то время как требования к чтению не так высоки. Поэтому дерево LSM разработано на основе этого фона, и для LSM было предложено множество мер по оптимизации в аналогичных сценариях.
Сценарии применения
Чтобы привести еще несколько общих примеров: HBase, LevelDB, RocksDB
Возможно, вы знакомы с HBase, LevelDB и RocksDB были запущены Google и FaceBook соответственно, и они также имеют открытый исходный код. Для студентов с хорошим английским можно напрямую ознакомиться с официальными документами, и у вас будет более глубокое понимание промышленной реализации LSM.
Зачем смотреть на разные реализации БД? Поскольку, несмотря на то, что это одна и та же структура данных, различные методы реализации могут значительно повысить ее эффективность с помощью таких средств, как фильтр Блума в реализации, поэтому необходимо понимать реализацию дерева LSM в разных компаниях.
Основы LSM-дерева
Дерево LSM, дерево слияния с полной записью, структурированное журналом. По сути, за счет последовательной записи логов производительность записи значительно повышается, а структурные свойства NoSQL помогают ему естественным образом подходить для Shard.
Основная операция
1. Запишите данные в память memtable (одновременно скопируйте копию на жесткий диск, чтобы данные не потерялись при сбое системы) 2. Когда данные достигают определенной емкости, сбросьте данные на жесткий диск SStable и одновременно объедините данные на жестком диске.
Осложнения: уплотнение
Увеличение количества SStables на жестком диске приведет к огромному давлению на чтение. В настоящее время необходимо уникальное значение «структуры данных».Построение различных структур данных с помощью различных уплотнений может эффективно снизить эффективность чтения. Обмен места на время — это реальная разница между HBase, LevelDB и RocksDB.
Реализация LSM в HBase
Давайте сначала посмотрим на реализацию в HBase, как показано на рисунке.
Фильтр Блума
Фильтры Блума и динамические кэши немного похожи, но они оба являются типичными примерами структур данных, а использование пространства значительно сокращает использование времени.
Блум использует большую битовую таблицу и несколько хеш-функций.Например, на рисунке три хэш-функции {x, y, z} сопоставлены с битовой таблицей. Тогда в таблице битов есть n позиций, отмеченных цифрой 1 (3
- Если в это время приходит w, w проходит через 3 хеш-функции, и есть отображенное значение 0, соответствующее позиции в битовой таблице, то это означает, что w точно не находится в {x, y, x}.
- Если все три хэш-функции w отображаются в 1, это не означает, что w находится в {x, y, z}. Это может быть похоже на сетки с 4, 5 и 6 позициями на приведенном выше рисунке, и эти сетки отображаются с разными значениями.
Уплотнение HBase
Как упоминалось выше, уплотнение является ядром дерева LSM. В HBase есть два типа:
- Minor Compaction
- Major Compaction
Оба являются объединенными SStables (SStables называются HFiles в HBase). Основное уплотнение удаляет некоторые ключи с истекшим сроком действия при слиянии, которое длится долгое время и обычно запускается вручную в периоды низкой пиковой нагрузки. (Hbase.offpeak.start.hour и hbase.offpeak.end.hour можно использовать для настройки периода низкой пиковой нагрузки)
В то же время разные версии HBase также предоставляют пользователям разные стратегии сжатия:
- RatioBasedCompactionPolicy
- ExploringCompactionPolicy
См. два конкретных введения: http://hbasefly.com/2016/07/13/hbase-compaction-1/
Поскольку у автора нет опыта реального использования HBase, я не осмеливаюсь делать какие-либо необдуманные комментарии, вы можете увидеть более профессиональное введение по приведенной выше ссылке. Однако для деловой стороны, такой как автор, HBase не предоставляет индекс, а использует Scanner для запроса данных.Похоже, эта структура данных не «идеальна».
LevelDB and RocksDB
RocksDb — это обновленная версия LevelDB, разработанная командой facebook на основе Google, которая предоставляет множество функций, которых нет в LevelDB. (Кроме того, TiDB — это новая база данных SQL, а ее нижний уровень основан на RocksDb. В Интернете уже есть много компаний, которые загрузили TiDB в производственную среду, и группа обработки данных моей компании также загрузила некоторые данные в оттенках серого в TiDB.Объясните RocksDb Он тоже вполне надежен.) Документации по LevelDB относительно мало, поэтому давайте взглянем на реализацию RocksDB.
Адрес документации LevelDB: https://github.com/google/leveldb/blob/master/doc/impl.md Адрес документации RocksDB: https://github.com/facebook/rocksdb/wiki
Compactions
RocksDB также предлагает различные стратегии:
- Leveled style compaction
- Universal style compaction
- FIFO Compaction
Здесь мы в основном вводим уплотнение в стиле Leveled, потому что оно произошло от LevelDB, которое всем удобно понимать вместе с LevelDB.
Leveled style compaction
Как показано на рисунке выше, вы можете видеть, что стиль Leveled делит SStable на разные уровни.За исключением возможных дубликатов ключей на уровне 1, дубликатов ключей после уровня 2 не будет. В то же время в каждом SStable ключи упорядочены.Не стоит недооценивать функцию порядка.Вы узнаете его магию, когда увидите его.
Как показано на рисунке выше, процесс уплотнения на самом деле относительно прост.Когда количество определенного уровня больше, чем емкость, будет выбрана SStable, и данные уровня +1 будут объединены. Выбранная таблица SStable уровня+1 имеет тот же ключ, что и текущая таблица SStable. Если сгенерированный SStable приводит к тому, что емкость уровня +1 превышает лимит, продолжайте слияние вниз.
Еще интереснее то, что, за исключением слияния уровня 0 и уровня 1, другие слияния могут выполняться несколькими потоками вместе, потому что нет дублирующегося ключа, поэтому не нужно беспокоиться о проблемах параллелизма.
найти
Как упоминалось выше, упорядочение может значительно повысить эффективность поиска ключа.Поиск проходит в два этапа:
- Двоичный поиск начала и конца всех файлов, чтобы найти файл, который может иметь ключ
- Бинарный поиск всех ключей, содержащихся в файле
Все поиски выполняются бинарным поиском.
Суммировать
Эта статья начинается с введения в LSM и содержит обзор некоторых инженерных реализаций LSM. Поскольку я не очень хорошо разбирался в исходном коде таких БД, я могу найти в документах только ценный контент для всеобщего обозрения. Магия структуры данных. Если содержание неправильное или вы хотите обменять, пожалуйста, не стесняйтесь обращаться ко мне ~