Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняРаздел IX распределенных системстатья.
Содержимое, которым с вами сегодня поделились, — это дерево LSM, его английский —Log-structed Merge-tree. Выглядит немного устрашающе, но на самом деле в принципе несложно, по сравнению с Б-три, это почти педиатр.
И это тоже очень классическая структура данных, имеющая очень широкий спектр приложений в системах больших данных. Есть много известных классических систем, а нижний слой реализован на базе LSM-дерева. Поэтому сегодня давайте вместе с вами подробно изучим его принципы.
жизненный опыт
Во-первых, давайте начнем с фоновых знаний. Когда мы ранее представили дерево B+, мы сказали, что самая большая разница между деревом B+ и деревом B заключается в том, что все данные размещаются в листовых узлах. Таким образом, мы оптимизируем эффективность нашей пакетной вставки и пакетного запроса, а основная логика оптимизации заключается в том, что независимо от того, какой носитель данных,Последовательное хранение должно быть более эффективным, чем случайное хранение, а высота даже не чуть-чуть. Это клише, и, если я правильно помню, я уже третий раз упоминаю об этом в статье.
Недавно я видел график, который хорошо иллюстрирует неэффективность как случайного, так и последовательного чтения, давайте взглянем на график ниже. Зеленая часть указывает на максимальную скорость последовательного чтения с жесткого диска, а красная — на скорость случайного чтения.
Глядя на ординату, мы видим, что разница между ними не маленькая, разница уже на порядок. И дело не только в величине,минимум на три порядка, что, очевидно, очень страшно. Кроме того, этот разрыв существует не только на традиционных механических жестких дисках, но и на более совершенных твердотельных накопителях SSD. То есть зазор не зависит от среды.
Интуитивная оптимизация
Поскольку эффективность случайного чтения и последовательного чтения намного хуже, это не может не радовать людей. Если мы сможем изобрести структуру данных, которая сможет в полной мере воспользоваться этим преимуществом, наша система будетпропускная способностьДолжен быть в состоянии сделать шаг вперед. Для многих технологических компаний, особенно компаний, работающих с большими данными, накладные расходы на машины из-за объема данных составляют большую часть ежедневных расходов. Если эта проблема может быть решена хорошо, очевидно,Сэкономьте много ресурсов.
Наивная идея состоит в том, чтобы спроектировать все операции чтения и записи как последовательные операции чтения и записи, напримерлог-системаявляется типичным примером. Когда мы регистрируемся, он всегда добавляется в конец файла, а не вставляется в его середину. Поскольку мы всегда добавляем в конец файла, это последовательное чтение и запись на диск. Но мы проектируем чтение и запись так, чтобы они были последовательными, а это означает, что когда искомое содержимое находится в середине файла, мыВсе в файле должно быть прочитано.
Есть два места, где эта идея наиболее широко используется, одно из них — журнал базы данных. Когда мы используем базу данных для выполнения операций записи или изменения, база данных будет записывать все изменения в журнал и записывать их. Другойпромежуточное ПО для системы сообщенийнапример, кафка.
Однако в сложных сценариях добавления, удаления, проверки и изменения, особенно с пакетным чтением и записью, простое последовательное чтение и запись файлов не может удовлетворить требованиям. Конечно, мы можем ввести структуры данных, такие как хэш-таблицы или B+-деревья, для достижения функций, но эти сложные структуры данных не могут избежать относительно медленных случайных операций чтения и записи, и мы надеемся,Случайные операции чтения и записи могут быть сведены к минимуму, именно по этому принципу был изобретен LSMT. LSMT использует уникальный механизм, который жертвует производительностью некоторых операций чтения, чтобы обеспечить возможность операций записи.Он может сделать все операции сериализованными и почти полностью избежать случайных операций чтения и записи.
Прежде чем мы представим принцип LSMT, давайте сначала представим егоПодконструкция SSTable.
SSTable
Когда я впервые вижу это слово, я смущаюсь. Полное имя SSTable —Sorted String Table, который по сути является файлом, в котором структура KV упорядочена. Давайте посмотрим на картинку ниже:
Самый простой SSTable — это правая часть рисунка выше, то есть пары ключ-значение ключа и значения сортируются в соответствии с размером значения ключа и сохраняются в файле. Когда нам нужно найти данные, соответствующие значению ключа, мыпрочитает весь файл в память, найти его. Аналогично, то же самое верно и для записи.Мы выполним операцию вставки в память.Получив результат, мы сразу перезапишем исходный файл, не изменяя его в файле, потому что это потребует перемещения большого количества данных.
Если объем данных в файле слишком велик, нам нужно создать еще одининдексный файл, сохраните смещение, соответствующее разным значениям ключа, чтобы мы могли быстро найти нужный файл при чтении файла. Индексный файл — это левая часть рисунка выше.
Следует отметить, что SSTable не поддается изменению, мы будем использовать новый SSTable только для перезаписи старого и не будем изменять его на исходной основе. Потому что модификация потребует случайных операций чтения и записи, чего мы не хотим.
CRUD LSM
Разобравшись с SSTable, давайте рассмотрим основной принцип реализации LSM.
На самом деле, самый основной принцип LSM очень прост, по сути Memtable добавляется на основе SSTable, Memtable, как следует из названия,структура таблицы хранится в памяти. Конечно, это не обязательно должна быть табличная структура, это также может быть древовидная структура, которая на нее не влияет.Короче говоря, это структура данных, которую можно быстро добавлять, удалять, изменять и проверять, например красно-черное дерево и SkipList. Во-вторых, нам также нужен файл журнала, такой как журнал в базе данных, для записи изменений в данных. Удобно извлекать при сбое системы или потере данных, поэтому общая структура выглядит следующим образом:
найти
Давайте сначала посмотрим на ситуацию поиска.Когда нам нужно найти элемент, мыСначала буду искать Memtable. Причина тоже понятна.Он в памяти и не требует чтения дополнительных файлов.Если он не найден в Memtable,будем искать SSTable по одному.Так как данные в SSTable тоже хранятся последовательно , мы можем использовать бинарный поиск, скорость поиска также будет очень высокой. Но одно,Поскольку количество SSTables может быть большим, и мы должны искать последовательно, поэтому, когда количество SSTables велико, это также повлияет на скорость поиска. Для решения этой проблемы мы можем ввестиФильтр Блумаоптимизировать. Мы создаем фильтр Блума для каждой SSTable, который может быстро определить, находится ли элемент в определенной SSTable. Фильтр Блума точно определяет, что элемент не существует, и может быть небольшая вероятность ошибки при оценке существования элемента, но эту частоту ошибок можно контролировать Мы можем установить разумные параметры, чтобы снизить частоту ошибок. достаточно.
Операция поиска после добавления фильтра Блума выглядит следующим образом:
Звездочка на картинке выше представляет фильтр Блума, а это значит, что мы сначала судим о существовании элемента через фильтр Блума, а затем ищем.
Фильтр Блума был представлен вам в предыдущих статьях. Студенты, которые забыли или недавно заинтересовались, могут щелкнуть ссылку ниже, чтобы просмотреть его.
Алгоритмы больших данных — фильтры Блума
Добавления, удаления и модификации
Все операции, кроме поиска, происходят в Memtable, например, когда мы хотимПри добавлении элемента мы напрямую добавляем его в Memtable, вместо записи в файл. Это также гарантирует, что скорость увеличения может быть сделана очень быстро.
Кроме того, модификация и удаление одинаковы.Если элемент, который нужно изменить, находится в Memtable, сказать нечего, и мы можем изменить его напрямую. Если его нет в Memtable, если мы хотим его сначала найти, а потом модифицировать, то неизбежно потребуется чтение и запись на диск, что будет потреблять много ресурсов. Так что мы по-прежнему работаем в Memtable, будем вставлять этот элемент, отмечать его как измененный или удаленный.
так что мы можемТри операции добавления, удаления и модификации считаются добавлениями., но это приносит проблему.Эта операция скоро приведет к накоплению большого количества данных в Memtable, а наши ресурсы памяти также ограничены, очевидно, что ее нельзя расширять бесконечно. Чтобы решить эту проблему, нам нужно периодически сохранять содержимое Memtable на диск как SSTable. Это также источник SSTable.Данные в SSTable не появляются из воздуха, а генерируются LSM.
Точно так же, поскольку мы продолжаем размещать диски, количество SSTables также будет увеличиваться.Как мы уже проанализировали, увеличение количества SSTables повлияет на эффективность нашего поиска, поэтому мы не можем допустить, чтобы оно увеличивалось бесконечно. Кроме того, мы также храним много измененной и удаленной информации, которую нам нужно поставить на место. Для этого нам нужно периодически объединять все SSTables, а в процессе объединения мы завершаем удаление и модификацию данных. Другими словами, предыдущие операции удаления и модификации только записываются и фактически не выполняются до слияния.
Весь процесс слияния не сложный, аналогичныйОперация слияния в сортировке слиянием, но нам нужно добавить суждение государства.
Суммировать
Давайте рассмотрим весь процесс LSMT, Хотя это дерево, древовидная структура не очевидна. Но если мы посмотрим на порядок запросов при поиске элементов, на самом деле этоИз Memtable, затем вниз в порядке SSTable, что согласуется с древовидной структурой и может рассматриваться как относительно «узкое» дерево. Если вы все еще считаете нормальным, что эта структура данных не похожа на дерево, нам не о чем беспокоиться. Кроме того, с принципиальной точки зрения, это просто слишком просто и грубо, но, судя по фактическим результатам, эффект от него очень хороший, и он широко используется в Hbase и kudu.
Давайте сравним его с деревом B+.В дереве B+ мы используем многостороннее сбалансированное дерево для быстрого чтения, чтобы мы могли быстро найти узел, соответствующий ключу. Нам нужно только прочитать содержимое узла, но также из-за структуры сбалансированного дерева, когда мы записываем данныеизменения в древовидной структуре, который также включает в себя случайное чтение и запись нескольких файлов. Когда пропускная способность наших данных велика, это приведет к огромным накладным расходам. А вот с LSMT дело обстоит иначе: эффективность чтения у нас ниже, чем у B+-дерева, но лучше поддерживает запись больших данных. В сценариях с большими данными многие предъявляют высокие требования к пропускной способности данных, например, системы сообщений и распределенное хранилище. В это время дерево B+ несколько бессильно, но опять же, если нам нужно обеспечить эффективность поиска, то LSMT не подходит, поэтомуНа самом деле ни один из двух не лучше другого, но для разных сценариев.
Наконец, о LSMT, на самом деле есть много вариантов.Более известный из них — Leveldb, написанный Джеффом Дином.Он внес некоторые изменения на основе LSMT для дальнейшего повышения производительности.Мы поместим соответствующий контент в следующую статью.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.