NoSQL СУБД, часть вторая, «KVS»

29 январь, 2014 - 17:32Андрей Зубинский

В комментариях к предыдущей статье этого цикла было высказано примерно в такой форме следующее мнение: «весь этот ваш NoSQL — всего лишь ключ-значение». Мне пришлось отдать немало времени, чтобы разъяснить для самого себя это самое «всего лишь». Затраты времени не были напрасными, и теперь мы можем попытаться разобраться — почему они вообще возникли и зачем они вообще, эти «всего лишь» Key-Value Storage (KVS), а также вообще настолько они «всего лишь».

Начнём с одной очень важной работы, датируемой далёким 1996 годом и написанной небольшой группой учёных и практиков (строго поровну разделённой) — представителями академической computer science и двух «монстров» IT — DEC и Oracle. Причём от академической науки выступили люди более чем известные — Патрик и Элизабет О’Нейл, научные статьи которых всегда отличались высочайшими показателями цитирования, кроме того, они являются авторами известной и популярной фундаментальной книги, посвящённой теории баз данных. К слову, комментарии к этой книге на сайте Amazon наводят на печальные мысли о слабости корреляции между работой в IT и умственными способностями. Например, отдельные «герои IT» там демонстрируют возмущение отсутствием в изданной в 2000 году книге глав, посвящённых CouchDB (первый релиз — в 2005 году) и MySQL (первый релиз — в середине 2000 года). Что наглядно убеждает нас в отсутствии у автора комментария чего-то важного, а у авторов книги — машины времени. Но. Даже если авторы не могут перемещаться в будущее и возвращаться обратно в своё время, они могут отправить в будущее свои работы. Именно о такой работе мы и говорим — «The Log-Structured Merge-Tree» (или сокращённо в дальнейшем — LSM-Tree). Увы, даже Википедия предлагает всего одну короткую запись об этой очень интересной структуре данных, и, ещё более увы, — только англоязычную версию.

В 1996 году IT мир был ещё миром «больших СУБД» и «большого железа». Неудивительно, что в те времена правило «пяти минут» (я о нём писал раньше) использовалось не столько для оптимизации производительности систем хранения и доступа к данным разной «температуры», сколько для обеспечения максимально высоких показателей производительности (в терминах TPC) при реалистичных затратах на очень дорогие дисковые накопители мейнфреймов. В решениях такой актуальной для своего времени (и не только) задачи была одна весьма специфическая область, связанная с обеспечением возможности восстановления базы данных. А именно, — журналирование (logging). Каждая транзакция предполагает две специфических операции — добавление записи (строки, если речь идёт о реляционной СУБД) в таблицу истории (для отслеживания последовательности транзакций) и одновременно — записи журналирования для восстановления базы данных в случае ошибочных, незавершённых и прочих «нехороших» транзакций. Естественно, таблица (или база данных) истории транзакций растёт очень быстро, и обеспечение высокой скорости работы всей СУБД в целом с учётом этой невидимой, но обязательной функции, по мере роста таблицы истории становится весьма непростой и «в лоб» не решаемой задачей. Де-факто стандартные и по сей день низкоуровневые механизмы работы с дисковыми накопителями (такие как B и B+ деревья) удваивают число медленных операций дискового ввода-вывода, что актуально и сейчас для высокопроизводительных систем, а во времена написания обсуждаемой статьи это означало практически 50% увеличение стоимости и без того очень дорогой дисковой подсистемы (впоследствии мы немного поговорим об одной K-V СУБД, достойной представляющей реализацию B±деревьев). Назначение предложенного в статье алгоритма и структур данных лучше всего пересказать максимально точным переводом: «алгоритм существенно сокращает движение головок дисков по сравнению с традиционными методами, такими как B-деревья, и улучшает соотношение цена-производительность в областях, где стоимость движений дисковых головок для выполнения операций записи сводит на «нет» расходы на дисковую подсистему».

В реализацию алгоритма и структур данных LSM-Tree мы вдаваться не будем, нас более интересует логическая модель LSM-Tree, но о кое-чем низкоуровневом надо упомянуть. В основе оригинальной концепции LSM-Tree лежат две (или более) древовидные структуры данных, схожие с B/B±деревьями, узлами которых являются достаточно «страницы» (блоки) памяти. Одна из этих структур хранится в быстрой оперативной памяти (S0), вторая — в любой медленной энергонезависимой памяти (S1). Естественно, так как медленная энергонезависимая память до сих пор существенно дешевле быстрой оперативной, размеры этих древовидных структур подчиняются логичному неравенству S0<<S1:

NoSQL СУБД, часть вторая, «KVS»

Упоминание о древовидном характере этих структур данных сделано для тех, кто собирается «нырнуть» в системы, основанные на LSM-Tree, намного глубже, чем позволяет это сделать объём статьи. В реальности это может оказаться нужным даже для эффективного использования кажущихся на первый взгляд простыми систем. Нам же будет достаточно добавить к этому упоминанию о низкоуровневых структурах данных всего ещё одну низкоуровневую деталь – несмотря на расположение «в» медленной долговременной памяти дерева S1, часто используемые узлы (страницы или блоки внешней памяти) традиционно буферируются в той же оперативной памяти для ускорения доступа. Эта деталировка достаточна, а мы попробуем взглянуть на логическую организацию этого «леса из двух деревьев», что нам куда важнее для понимания целого класса KVS СУБД. Так что давайте посмотрим на эти же конструкции «с высоты птичьего полёта» (то есть забыв о всех буферированиях и деталях реализации).

Базовая конструкция долговременной памяти — сортированная таблица строк (SST, Sorted String Table). Несмотря на слово «строки», которое любому программисту сразу напоминает о типе данных, точнее было бы называть её «сортированной таблицей блобов». Представляет собой она именно то, чем и называется, упорядоченную последовательность пар «ключ-значение» (key-value), в которых что ключ, что значение являются в общем случае просто блобами (то есть, массивами байтов), и никаких требований к уникальности ключей не предъявляется:

NoSQL СУБД, часть вторая, «KVS»

Если мы будем последовательно считывать такую структуру данных с внешнего накопителя, мы получим упорядоченную последовательность KV-пар. Для ускорения таких процедур используется дополнительная логическая структура данных — индекс, назначение которой понятно из следующего рисунка (индекс — справа вверху):

NoSQL СУБД, часть вторая, «KVS»

Такая организация даёт нам возможность очень быстро упорядоченно (последовательно) «выкачивать» из подобной простой базы данных большие информационные массивы и быстро «перемещаться» по блобам, хранящим полезную информацию (мгновенный поиск в индексе, если он в оперативной памяти — и данные доступны за одно обращение к диску, без дополнительных дисковых поисков). Если вспомнить модную терминологию и представить себе, что мы говорим о действительно больших информационных объемах (например, о терабайтах) и о возможности многоступенчатой обработки этих объёмов разными программами, сравнительно простая логическая структура SST даёт нам возможность быстро выполнять задачи не только класса Map-Reduce, а и вовсе последовательности Map-Reduce.

Но что происходит с операциями записи? Особенно если они не последовательные, а произвольные? Мы же до сих пор ни разу не упомянули о каких-то ограничениях на размер блобов, например. Потому что этих ограничений нет. И если, например, необходимо обновить содержимое блоба для имеющегося в SST ключа, и новый блоб больше записанного на диск, или необходимо для поддержания упорядоченности «вставить» в последовательность новую пару ключ-блоб, очевидные способы не сработают — безусловно, можно попытаться переместить кусок файла SST, но при больших его размерах это займёт бездну времени (даже при всех ускорениях, обеспечиваемых нижним уровнем древовидной реализации, о котором упоминалось выше). Но если вся таблица «ключ-блоб» помещается в оперативную память с запасом, проблем с производительностью произвольной записи очевидно не будет. Однако, мы предполагаем, что говорим о действительно больших объёмах данных.

Для решения задачи обеспечения высокой производительности одновременно операций чтения и записи с последовательным и произвольным доступом, SST нужны серьёзные дополнения. Во-первых, если мы говорим о проблемах с модификацией уже имеющихся данных (вставки, изменения), мы уже знаем единственный радикальный способ этих проблем избежать: сделать самые «тяжёлые» и «медленные» данные immutable, нас этому научила практика функционального программирования. Во-вторых, почему бы не применить классический приём из области кеширования и не разместить часть тех самых «больших и медленных» данных (SST) в памяти с быстрым произвольным доступом? Комбинация этих двух приёмов может выглядеть так:

NoSQL СУБД, часть вторая, «KVS»

На этом рисунке всё, что находится в «тёплых» розовых прямоугольниках — находится в дорогой и быстрой оперативной памяти. Всё, что в серых — неизменяемые (immutable) фрагменты дешёвой медленной долговременной памяти. И не забываем, что под всей этой моделью — быстрые древовидные низкоуровневые механизмы.

Добавим к модели динамику, а именно, высокоуровневое описание следующего алгоритма:

  • все операции чтения-записи выполняются с верхним на рисунке «куском» SST, который располагается в оперативной памяти, любые записи возможны только в него, любые чтения предваряются проверкой ключа на наличие в этом «кэше», и, естественно, если ключ там есть — оттуда же выбирается и блоб, без обращения к диску;

  • по мере заполнения операциями записи размер кэша растёт и доходит до какого-то заданного предела, после чего весь фрагмент SST из кэша оперативной памяти «сбрасывается» (flush) на диск и становится новым неизменяемым (immutable) фрагментом дисковой SST;

  • периодически дисковые immutable фрагменты SST отдельными механизмами «сливаются воедино».

Что мы получили в итоге? Производительность последовательного и произвольного чтения в такой архитектуре остаётся очевидно очень высокой. Последовательная запись тоже характеризуется отличными показателями и вообще идеальна для всей логики работы — кэш последовательно заполняется, слияние immutable копий содержимого кэша крайне простая задача. Произвольная запись также достаточно быстрая, потому что первый этап любой операции записи всегда с быстрой кэш-памятью. И, наконец, все служебные механизмы упрятаны от потребителя всего этого удовольствия в его реализации, для работы с такой довольно сложной системой очевидно достаточно минимального API, который даже по идее может быть почти всегда асинхронным (очередной запрос записи в область кеширования может прийти в такой момент времени, когда кэш почти заполнен и для новой K-V пары просто нет места, тогда сработает механизм «сбрасывания» содержимого кэша на диск и, естественно, запрос записи будет заблокирован до освобождения кэша).

Собственно говоря, мы восстановили то, что называется LSM-Tree (Log-Structured Merge-Tree). Остаётся добавить, что именно эта структура данных и сопутствующие ей алгоритмы лежат в основе не распространяемой за пределы Google системы хранения и доступа к данным BigTable. И в основе СУБД Cassandra, о которой шла речь в предыдущей статье. И, наконец, в основе исходящей из недр Google симпатичной «СУБД на уровне библиотеки» LevelDB (к слову, разрабатывали LevelDB те же люди, которые работали и над BigTable). И, наконец, через LevelDB, — в основе разрабатываемой в Facebook тоже «библиотеки-СУБД» RocksDB. Больше того, принятые в этих системах названия (и даже имена переменных в коде реализации) полностью соответствуют картине, с которой вы уже знакомы — SST-кэш в оперативной памяти называется непременно похоже на memtable, часть SST, которая immutable данные на диске — sstfile.

Много говорить о двух этих похожих (и не очень) системах нет нужды. Но кое-что сказать следует сразу тем, кто захочет их попробовать «руками» (игра стоит свеч, потому что системы весьма хороши). Это не готовые СУБД, а библиотеки с очень компактным API. LevelDB «не любит» ОС Windows, не очень любит Mac OS X (есть нюансы, связанные с реализацией в этой ОС некоторых системных вызовов Unix, что проявляется, например, в работе LevelDB в «Биткойн кошельке» для этой ОС), она любит ОС Linux (и, опять же, не совсем любит в Linux файловую систему ext4). Также система требует хорошего понимания механизмов синхронизации, которые не очень хорошо документированы. Всё это значит ровно то, что может значить — Windows-программистам лучше воспользоваться форком этой системы от Bureau 14, Linux-программистам, прежде чем развенчивать записями в блогах не так, как надо проявляющиеся характеристики производительности системы, разумно предварительно «раскопать» нюансы её работы с файловой системой ext4, ну и, наконец, не следует забывать, что, несмотря на свои корни из мира «больших данных», разработчики LevelDB не задавались задачей создать «Google BigTable для самых маленьких» с размером упакованного дистрибутива исходных текстов и документации 350KB. LevelDB явно делалась для служебных задач (она используется в Chromium/Chrome и ChromeOS), но довольно неплохо ведёт себя при весьма немаленьких объёмах данных (скажем, при размере базы данных порядка 10-20 GB). При увеличении объёмов у LevelDB начинаются проблемы, и это уже область многочисленных разработок на основе её кодовой базы. Например, RocksDB, которая создавалась совершенно для других задач. Причём RocksDB, совсем недавно «отпущенная» Facebook в open source плавание, по явным сообщениям из самой Facebook, используется в «боевой» реализации их собственного сервиса.

RocksDB отличается от основы своей кодовой базы прежде всего подходом к проектированию. Если LevelDB — продукт «сугубо программирования», представленный монолитным C++ кодом, то RocksDB — уже настоящая развитая система, допускающая облегченную замену своих ключевых узлов (в какой-то степени их можно считать плагинами, что отображено множественными элементами на рисунке):

NoSQL СУБД, часть вторая, «KVS»

Из названий в рисунке нам уже известны memtable, плагин filesystem в базовом дистрибутиве системы реализует SST, специально «настроенный» на возможности быстродействующих накопителей на флеш-памяти (но никто не запрещает пробовать создавать усовершенствованные механизмы на основе общей идеи LSM-Tree и для традиционных дисковых накопителей), также возможна самостоятельная реализация разных механизмов «сливания воедино» неизменяемых фрагментов LSM-Tree на диске (на рисунке — compacter). Ну и, конечно, вспоминая самое начало статьи, и в LevelDB, и в RocksDB есть журналы (log) для восстановления данных.

Самые значительные усовершенствования разработчиков Facebook, которые превращают RocksDB в очень серьёзную систему (несмотря на всё равно смешной размер дистрибутива) — реализация раздельных «каналов» чтения и записи, а также управление конкурентным доступом с помощью многоверсионности (MVCC) в канале чтения, что упрощает применение RocksDB в многопользовательских системах (MVCC по сути избавляет от взаимных блокировок транзакции записи и чтения).

Чтобы понять, насколько отличаются параметры систем одного класса («K-V СУБД, реализованная на уровне библиотеки»), но основанных на LSM-tree и классических B+-деревьях, в следующей части мы кратко рассмотрим достойный продукт многолетней эволюции, систему Kyoto Cabinet. И к ней обстоятельнее добавим совершенно замечательную KVS совсем «новой волны».