Таблица отсортированных строк (SSTable) или дерево B + для индекса базы данных?

Question

Использование двух баз данных для иллюстрации этого примера: CouchDB и Cassandra .

CouchDB

CouchDB использует дерево B + для индексов документов (используя умное изменение для работы в их среде только для добавления) - более конкретно, при изменении документов (вставка / обновление / удаление) они добавляются к запущенный файл базы данных, а также полный путь Leaf -> Node из дерева B + всех узлов, на которые повлияла обновленная ревизия, сразу после документа.

Эти пересчитанные по частям ревизии индекса встроены рядом с модификациями, так что полный индекс представляет собой объединение самых последних модификаций индекса, добавленных в конце файла, вместе с дополнительными фрагментами, находящимися далее в файле данных, которые все еще актуальны и еще не были изменены.

Поиск по дереву B + - это O (logn).

Cassandra

Кассандра хранит ключи записей, отсортированные в памяти, в таблицах (давайте подумаем о них как о массивах для этого вопроса) и время от времени записывает их как отдельные (отсортированные) таблицы с отсортированными строками .

Мы можем рассматривать коллекцию всех этих таблиц как «индекс» (насколько я понимаю).

Кассандре требуется время от времени компактировать / комбинировать эти таблицы отсортированных строк , создавая более полное представление файла индекса.

Поиск отсортированный массив - это O (logn).

Вопрос

Предполагая схожий уровень сложности между поддержанием частичных кусков дерева B + в CouchDB и частичных индексов отсортированных строк в Cassandra и с учетом того, что оба обеспечивают время поиска O (logn), которое, по вашему мнению, улучшило бы представление базы данных Индекс и почему?

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

Спасибо за мысли.

Answer 1

При сравнении индекса BTree с индексом SSTable следует учитывать сложность записи:

• При произвольной записи в BTree-копию-при записи вы будете выполнять случайное чтение (для копирования конечного узла и пути). Таким образом, в то время как записи могут быть последовательными на диск, для наборов данных, больших, чем RAM, эти случайные чтения быстро станут узким местом. Для SSTable-подобного индекса при чтении не происходит такого чтения - будут только последовательные записи.

• Вы также должны учитывать, что в худшем случае каждое обновление BTree может повлечь log_b N IO - то есть вы можете в итоге написать 3 или 4 блока для каждого ключа. Если размер ключа намного меньше размера блока, это очень дорого. Для индекса, подобного SSTable, каждая запись ввода-вывода будет содержать столько свежих ключей, сколько может, поэтому стоимость ввода-вывода для каждого ключа больше равна 1 / B.

На практике это делает SSTable-подобный в тысячи раз быстрее (для случайной записи), чем BTrees.

При рассмотрении деталей реализации мы обнаружили, что намного проще реализовать SSTable-подобные индексы (почти) без блокировок, в то время как стратегии блокировки для BTrees стали довольно сложными.

Вам также следует пересмотреть свои расходы на чтение. Вы правы, чем BTree - это O (log_b N) случайных операций ввода-вывода для случайных операций чтения точек, но индекс, подобный SSTable, фактически равен O (#sstables. Log_b N). Без приличной схемы слияния #sstables пропорционален N. Существуют различные приемы, чтобы обойти это (например, с использованием Bloom Filters), но они не помогают при запросах с маленьким случайным диапазоном. Вот что мы нашли с Кассандрой:

http://www.acunu.com/blogs/richard-low/cassandra-under-heavy-write-load-part-ii/

Вот почему Castle, наш (GPL) механизм хранения, выполняет слияния немного по-другому и может достичь гораздо лучшей (O (log ^ 2 N)) производительности запросов диапазона с небольшим компромиссом в производительности записи (O (log). ^ 2 Н / Б)). На практике мы обнаруживаем, что он быстрее, чем индекс SSTable Кассандры для записей.

Если вы хотите узнать больше об этом, я рассказал о том, как это работает:

• http://skillsmatter.com/podcast/nosql/castle-big-data
• http://www.slideshare.net/acunu/in-the-brain-of-tom-wilkie

Answer 2

Я думаю, что фрактальные деревья, используемые Tokutek , являются лучшим индексом для базы данных.Они предлагают реальные 20-80-кратные улучшения по сравнению с b-деревьями.

Здесь есть отличные объяснения того, как работают индексы фрактальных деревьев здесь .

Answer 3

Некоторые вещи, которые также следует упомянуть о каждом подходе:

B-деревья

• Операции чтения / записи должны быть логарифмическими O(logn). Однако одна запись в базу данных может привести к нескольким записям в системе хранения . Например, когда узел заполнен, его нужно разделить, а это означает, что будет 2 записи для 2 новых узлов и 1 дополнительная запись для обновления родительского узла. Вы можете увидеть, как это может увеличиться, если родительский узел также будет заполнен.
• Обычно B-деревья хранятся таким образом, что каждый узел имеет размер страницы. Это создает явление, называемое усиление записи , когда даже если требуется обновить один байт, записывается целая страница.
• Запись обычно случайная (не последовательная), , таким образом, медленнее , особенно для магнитных дисков.

SSTables

• SSTables обычно используются в следующем подходе. Как вы описали, существует структура в памяти, называемая memtable. Время от времени эта структура сбрасывается на диск в SSTable. В результате все записи отправляются в таблицу памяти, но операции чтения могут отсутствовать в текущей таблице, и в этом случае они ищутся в постоянных таблицах SSTable .
• В результате записи составляют O(logn). Однако всегда имейте в виду, что они выполняются в памяти, поэтому они должны быть на порядки быстрее, чем логарифмические операции на диске B-деревьев. Для полноты картины следует упомянуть, что записи также записываются в журнал опережающей записи для восстановления после сбоя. Но, учитывая, что все это последовательных записей, ожидается, что они будут намного более эффективными, чем случайные записи B-деревьев .
• При подаче из памяти (из памяти), считывания также будут выполняться намного быстрее . Но когда нужно искать в старых дисковых SSTables, чтение может стать намного медленнее, чем B-деревья. В связи с этим существует несколько оптимизаций, таких как использование фильтров Блума, чтобы проверить, содержит ли SSTable значение без чтения с диска.
• Как вы упомянули, есть также фоновый процесс, называемый compaction , используемый для объединения SSTables. Это помогает удалить удаленные значения и предотвратить фрагментацию, но может вызвать значительную нагрузку записи, влияющую на пропускную способность записи входящих операций.

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

• SSTables обеспечивают намного лучшую пропускную способность записи, чем B-деревья. Однако ожидается, что они будут вести себя менее стабильно из-за продолжающихся уплотнений. Пример этого можно увидеть в этом сравнительном сравнении .
• B-деревья обычно предпочтительны для случаев использования, где необходима семантика транзакции. Это происходит потому, что каждый ключ может быть найден только в одном месте (в отличие от SSTable, где он может существовать в нескольких SSTable с устаревшими значениями в некоторых из них), а также потому, что можно представлять диапазон значений как часть дерево. Это означает, что проще выполнять механизмы блокировки на уровне ключа и на уровне диапазона.

---

Ссылки

[1] Сравнение производительности LevelDB и MySQL

[2] Разработка приложений с интенсивным использованием данных

Answer 4

LSM-Trees лучше, чем B-Trees по структурированному механизму хранения.Он конвертирует случайную запись в aof таким образом.Вот источник LSM-Tree: https://github.com/shuttler/lsmtree