vk-com / kphp-kdb
branch: master kphp-kdb / docs / ru / DBMS_Storage_Comparison.wiki
Vkontakte 19 hours ago Fix ‘pre’ tag usage in docs.
0 contributors
file 196 lines (136 sloc) 56.928 kb Open EditRawBlameHistory Delete
Для простоты мы будем рассматривать хранение одной таблицы в одной базе данных, расположенной на одном сервере.
Table of Contents
Структуры, используемые для баз данных
Пример
Хранение баз данных
Журнал
Образ в памяти
Журнал + образ в памяти
Динамический снимок
Статический снимок
Статический снимок + журнал + частичный образ в памяти
Переиндексирование
Сравнение разных способов
Преимущества и недостатки систем, основанных на журнале и статическом снимке
Структуры, используемые для баз данных
Список структур данных, которые могут быть использованы для хранения описания или данных таблицы:
схема (schema) — описание структуры пустой таблицы, содержащее список названий и типов полей записей, описание индексов, и, возможно, список основных операций изменения (update) или получения (select) данных, разрешенных для данной таблицы. В действительности схема может описывать сразу несколько таблиц и взаимосвязи между ними; для простоты будем рассматривать только случай одной таблицы.
журнал (log) — список записей (log entries), характеризующих все (элементарные) операции изменения (update), произведенные с таблицей с момента ее создания, в хронологическом порядке.
снимок (snapshot) — набор данных, отражающий только текущее состояние таблицы, без какой-либо предыстории. Обычно хранится в одном или нескольких файлах на диске из-за большого объема данных, хранимых в таблице (или во всех таблицах, расположенных на одном сервере). Снимок может быть динамическим и статическим.
динамический снимок (dynamic snapshot) — снимок, оптимизированный под хранение на диске с возможностью эффективного внесения изменений. Использует структуры данных, оптимизированные под эти цели (т.е. минимизирующие количество запросов к диску), типичный пример — B+-дерево. Часто к каждой записи приписывается уникальный идентификатор (первичный ключ) и два timestamp’а (создания и удаления) для нужд MVCC, что позволяет хранить несколько версий одной и той же записи с целью обеспечения целостности транзакций.
статический снимок (static snapshot) — снимок, оптимизированный под хранение на диске и максимально быстрое исполнение SELECT’ов, но не приспособленный для изменения хранимых данных. Это позволяет применять более простые, компактные и эффективные структуры данных (например, индексы можно реализовывать с помощью упоряденных линейных списков id записей с нужным значением нужного поля; эти индексы можно эффективно паковать, как, впрочем и текстовые поля, используя один словарь на всю таблицу; и т.п.). Это приводит к гораздо меньшему количеству обращений к диску на один SELECT и гораздо более эффективно расходует дисковый кэш.
Предыдущие структуры данных могут быть использованы для хранения данных на диске. Кроме того, следующие структуры, располагающиеся в оперативной памяти, могут быть полезны для работы с таблицей:
метаиндекс (metaindex) — часть статического или динамического снимка, полностью загружаемая в память и используемая для быстрого доступа к основной части снимка, хранимого на диске.
образ в памяти (in-core image) — набор структур данных, хранимый в оперативной памяти и представляющий все данные из (небольшой) таблицы. Отличается от динамического снимка тем, что оптимизирован под размещение в оперативной памяти, и потому может интенсивно использовать такие структуры данных, как массивы, связные списки, хэш-списки, декартовы деревья и т.п.
частичный образ в памяти (partial in-core image) — структура данных, предназначенная для хранения в оперативной памяти только части данных таблицы, например, всех строк, измененных после определенного момента времени. Может также содержать отрицательные записи, означающие, что запись с данным идентификатором была удалена.
временная таблица (temporary table) — используется, например, для хранения результатов SQL-запроса SELECT до их отправки пользователю.
Еще несколько терминологических замечаний: таблица маленькая, если она легко помещается в оперативную память и в адресное пространство процесса; именно в этом случае с ней можно работать с помощью образа в памяти. В противном случае, если таблица заведомо не помещается в оперативную память, говорим, что она большая.
В дальнейшем обновление (update) будет обозначать любую операцию, изменяющую состояние таблицы (например, SQL-операции UPDАTЕ, DELЕTЕ и INSERT), а выборка (select) — это любая операция, получающая часть данных из таблицы, но не изменяющая их. Чистое обновление (pure update) — это обновление, для выполнения которого не нужно делать выборки данных. Атомарное обновление (atomic update) — это обновление, соответствующее одной записи в журнале; тогда чистые обновления — это те обновления, которые можно разложить в одно или несколько атомарных обновлений, причем это разложение не должно зависеть от состояния таблицы.
Пример
В качестве примера рассмотрим базу данных, состоящую из одной таблицы details. Каждая строка этой таблицы будет содержать два целочисленных 64-битных поля: doc и word. В тех случаях, когда необходим уникальный первичный ключ (скажем, для представления в MySQL+InnoDB), будем считать, что этим ключом является еще одно 64-битное поле id.
Смысл этой таблицы — поиск по ключевым словам в большом количестве документов: каждая запись (doc,word) означает, что документ с идентификатором doc содержит слово с хэшем word. В качестве основных операций (т.е. операций, которые должны эффективно выполняться) возьмем следующие:
1) Поиск по одному ключевому слову с составлением списка doc по возрастанию:
SELECT doc FROM details WHERE word=x ORDER BY id, или кратко Search(x).
2) Удаление всех слов из документа:
DELЕTЕ FROM details WHERE doc=y, или DelDoc(y).
3) Добавление слова в документ:
INSERT INTO details SET word=x, doc=y, или Add(x,y). Будем предполагать, что если пара (x,y) уже есть, эта операция игнорируется, т.е. на нашу таблицу наложено ограничение уникальности всех пар (word,doc), и этот INSERT дополнен чем-то вроде ON DUPLICATE KEY IGNORE.
На практике может оказаться, что операции 3) всегда встречаются после операции 2); в этом случае можно заменить 2) и 3) на одну операцию
4) Renew(y;x_1,…,x_m) — эквивалентно DelDoc(y), Add(x_1,y), …, Add(x_m,y).
Такая таблица может быть описана следующим образом на SQL:
CREATE TABLE details (
id BIGINT(20) NOT NULL auto_increment,
doc BIGINT(20) NOT NULL,
word BIGINT(20) NOT NULL,
PRIMARY KEY (id),
UNIQUE KEY word_doc_idx (word, doc),
KEY doc_idx (doc)
);
Условия эффективности выполнения операций 1), 2), 3) в данном случае преобразованы в описание индексов. Отметим, что это описание на SQL есть только часть схемы в нашем понимании, поскольку не указано явно, что мы собираемся выполнять только запросы 1),2),3); a priori MySQL или любая другая СУБД морально готовы выполнять любые SQL-запросы.
Отметим еще, что мы можем добавлять в нашу схему операции, не имеющие простых аналогов для реляционных БД, например:
1*) MSearch(word_1,word_2,…,word_N) — поиск всех документов, содержащих указанные слова; ответ должен быть отсортирован по возрастанию doc.
Ясно, что в SQL этому соответствует N-1-кратный JOIN таблицы details к себе.
В дальнейшем мы будем пользоваться этим примером для сравнения различных способов хранения баз данных.
Хранение баз данных
Журнал
Теоретически состояние любой таблицы (или «базы данных», состоящей из нескольких таблиц) полностью задается ее схемой (schema), т.е. набором типов и названий полей, информацией о их связях и индексах, и т.п., и журналом (log), т.е. хронологически упорядоченным списком всех операций, совершенных с таблицей, с момента ее создания.
Плюсом такой схемы является минимальный расход ресурсов на каждую операцию обновления (update): надо всего лишь добавить в конец журнала новую запись. В этой связи полезно различать элементарные или атомарные обновления (atomic update), которые соответствуют одной записи в журнале, и составные. Описание элементарных обновлений также является частью схемы. Они должны быть подобраны таким образом, чтобы часто выполняемые операции обновления соответствовали одному или небольшому количеству элементарных обновлений. Так, если в примере атомарной является только операция удаления DelById(id) по первичному ключу (id), то операция DelDoc(y) не будет ни атомарным, ни чистым обновлением, поскольку должна будет преобразовываться в последовательность операций DelById(id_k), причем эта последовательность зависит от текущего состояния таблицы. Обеспечить целостность транзакции в этом случае будет довольно сложно.
В ситуации примера естественно выбрать в качестве элементарных обновлений операции 2) и 3) (DelDoc и Add), либо 4) (Renew). В последнем случае удобно хранить в журнале список x_i в порядке возрастания.
Главным недостатком системы, основанной на журнале, является необходимость чтения всего журнала для выполнения любого запроса выборки. В самом деле, естественной стратегией выполнения запроса типа SELECT … WHERE (condition) является следующая:
Создать пустую временную таблицу для хранения результата; в ней будут храниться строки таблицы, удовлетворяющие условию (condition).
Сканировать записи журнала с самого начала и применять их к временной таблицы, учитывая только строки, удовлетворяющие условию (condition).
Так, в ситуации примера (где в качестве элементарных обновлений используются только запросы 4) = Renew()), запрос Search(x) или даже MSearch(x_1,…,x_k) выполняется так. В качестве временной таблицы будем использовать любую структуру данных, пригодную для хранения упорядоченных списков чисел doc, например, декартово дерево. Далее для каждой записи журнала Renew(y;x’_1,…,x’_m) мы проверяем, содержатся ли все x_i в списке x’_j; если да, то y добавляется в декартово дерево, иначе оно оттуда убирается. После завершения сканирования журнала декартово дерево будет содержать ответ.
Отметим, что не для всех запросов и схем достаточно хранить в каждый момент времени только строки, удовлетворяющие условию запроса: если в схеме есть обновления, могущие перевести строку, не удовлетворяющие условию запроса, в строку, удовлетворяющую этому условию, то во временной таблице придется хранить и все такие потенциально подходящие строки. В худшем случае (например, если разрешены произвольные SQL-запросы) придется хранить все строки вообще.
Образ в памяти
Система, основанная на хранении образа в памяти, при использовании надлежащих структур данных (выбранных на основе операций, разрешенных схемой), выполняет select’ы максимально быстро, а update’ы — за время, сопоставимое со временем, используемым системой с журналом или быстрее (поскольку записи на диск не требуется вообще).
Основной недостаток: данные полностью теряются при перезапуске или аварии, поэтому такую систему нельзя считать полноценной СУБД. Кроме того, такая система работает лишь для небольших таблиц (помещающихся в память). Ее возможное применение — кэширование данных и промежуточных результатов, которые при необходимости можно восстановить из других источников. Пример такой системы — memcached.
Журнал + образ в памяти
Поскольку система, основанная на журнале, в состоянии выполнять SELECT’ы за приемлемое время только на небольших и не слишком интенсивно изменяемых таблицах, можно ее расширить, добавив образ таблицы в памяти, оптимизированный под быстрое выполнение запросов из схемы. Такая система обладает большим временем запуска (поскольку нужно прочитать весь журнал и по нему заново построить образ таблицы в памяти), зато после этого все операции выборки (select) выполняются максимально быстро, а атомарные обновления (update) лишь ненамного дольше, чем для системы, основанной на журнале (поскольку требуется обновление образа в памяти). Основной ограничение: этот метод годится только для небольших таблиц, целиком помещающихся в память.
Динамический снимок
Работать с большой таблицей, заданной с помощью схемы и журнала, довольно сложно, а журнал + образ в памяти эффективны лишь для небольших таблиц и к тому же обладают огромным временем загрузки, поэтому практически все существующие СУБД не используют журнал или используют его (точнее, его небольшой фрагмент) только для вспомогательных целей (а именно, для репликации и восстановления после сбоев), а собственно для работы используют динамический снимок базы (dynamic snapshot). Такой снимок по существу является структурой данных, в которой хранятся только записи, ныне присутствующие в таблице, без какой-либо предыстории. Поскольку такой динамический снимок может быть очень большим (порядка нескольких гигабайтов), и на одном сервере может храниться несколько таблиц одновременно, обычно динамические снимки хранятся на диске, и потому используются структуры данных, оптимизированные по числу обращений к дискам (типичный пример — B+-деревья). В итоге операции изменения (update/insert) довольно сложны и требуют нескольких обращений к диску, операции получения данных (select) тоже обычно требуют интенсивного дискового ввода/вывода, и из-за возникающих задержек оказывается необходимым либо полностью блокировать таблицу (table lock) на время ее изменения (так работают MyISAM-таблицы в MySQL) что, очевидно, возможно только на системах с небольшой нагрузкой), либо использовать систему хранения различных версий одной строки (MVCC/TSCC + row-based locking), что еще больше усложняет и увеличивает объем хранимых данных, но зато позволяет выдерживать довольно большие нагрузки (InnoDB-таблицы в MySQL, Oracle, большинство коммерческих СУБД).
Таким образом, эта линия развития приводит к динамическим снимкам на диске, снабженными индексами на основе B+-деревьев, и обладающими системой контроля версий строк (MVCC), позволяющей блокировать только нужную часть таблицы на время выполнения запроса (на самом деле MVCC хранит старые версии записей, пока они заблокированы на чтение какой-либо транзакцией, и создает новые с большим номером версии, если их надо перезаписать; настоящее построчное блокирование необходимо не для самих записей, а для соответствующих элементов индексов). Такой подход позволяет интенсивно работать с довольно большими объемами данных, но требует интенсивного дискового ввода-вывода на любую операцию, соответственно, ограничивающим фактором для серверов становится скорость доступа к диску, которая растет очень медленно (гораздо медленнее, чем объем тех же дисков или производительность процессора).
Статический снимок
Если начиная с некоторого момента нам известно, что база данных не будет больше изменяться (например, все документы уже были проиндексированы и теперь будут только поисковые запросы), можно построить на диске статический снимок — структуру данных, оптимизированную под хранение на диске и максимально быстрое выполнение select’ов. При этом вместо B+-деревьев, типичных для динамических снимков, можно использовать более компактные структуры данных, например, простые упорядоченные списки, которые к тому же можно сжимать специальными алгоритмами. Кроме того, текстовые поля при таком подходе тоже могут быть эффективно сжаты. Обычно небольшая часть статического снимка (метаиндекс) предназначена для хранения в оперативной памяти; она позволяет быстро находить, в какой части дискового файла со статическим снимком нужно искать требуемую информацию.
В ситуации нашего примера в качестве статического снимка можно использовать набор списков WList(x)=(n,y_1,…,y_n), состоящих из номеров документов, содержащих данное слово. Эти списки можно хранить подряд, скажем, в порядке возрастания x, а метаиндекс будет состоять из наборов (x_i,n_i,pos_i) — слова, длины соответствующего списка и позиции его начала в файле. В итоге для выполнения запроса MSearch(x_1,…,x_n) надо всего лишь прочитать с диска упорядоченные списки WList(x_i), найдя их с помощью метаиндекса, и пересечь, а запрос Search(x) сводится к чтению WList(x) с диска. Это гораздо проще, чем то, что должна будет сделать система, основанная на динамическом снимке. К тому же, некоторое количество последних использованных списков WList(x) может кэшироваться в оперативной памяти, что приводит к дальнейшему увеличению производительности.
Получающаяся система в состоянии максимально быстро выполнять select’ы (перечисленные в схеме), работая при этом с очень большими таблицами. Дисковый ввод-вывод минимален, размер файлов на диске (т.е. статического снимка) также в 2-4 раза меньше соответствующего динамического снимка, что приводит к более эффективному использованию дискового кэша и потому к дальнейшему уменьшению количества обращений к диску.
Основной недостаток системы, основанной на статическом снимке: невозможность внесения изменений. Поэтому их основная область применения — поисковые системы. После существенного изменения набора индексируемых документов статический снимок просто пересоздается заново, а старый уничтожается.
Статический снимок + журнал + частичный образ в памяти
Можно ли совместить преимущества систем, основанных на журнале (быстрые update, очень медленные select), на образах в памяти (очень быстрые update и select, но для небольших таблиц) и на статических снимках (быстрые select даже на очень больших таблицах, но невозможность изменения данных вообще)?
Ответ на этот вопрос положительный: используя одновременно статический снимок, журнал и частичный образ в памяти, можно построить специализированную СУБД, в 20-30 раз более эффективную, чем распространенные СУБД на основе динамических снимков (таких, как Oracle, MySQL, PostgreSQL, MS SQL). Специализированность такой СУБД заключается в том, что создаваемые таблицы должны принадлежать определенному ограниченному набору схем, и добавление каждой новой схемы (или класса схем) является нетривиальной задачей, после чего можно будет выполнять только те update и select, которые принадлежат схеме.
Рассмотрим общую структуру такой системы; конкретный пример реализации — это KittenDB.
Итак, помимо журнала хранится еще и последовательность статических снимков, привязанных к позициям в журнале (точкам сохранения или savepoints). Такой статический снимок содержит состояние таблицы в соответствующий момент времени; в его заголовке хранится время создания, позиция в журнале точки сохранения и порядковый номер. Точка сохранения может быть представлена отдельной записью в журнале, содержащей ссылку на соответствующий статический снимок, а может быть просто позицией без каких-либо записей. Кроме того, СУБД хранит в оперативной памяти метаиндекс от активного (обычно самого нового) статического снимка, и частичный образ в памяти, содержащий информацию об изменениях, проделанных после создания используемого статического снимка. Важно отметить, что помимо новых записей и записей, измененных после этого момента времени, частичный образ может содержать отрицательные записи, означающие, что соответствующие записи существовали ранее, но были удалены. Конкретный вид частичного образа зависит от конкретной схемы и интенсивности запросов каждого типа; помимо множества записей, организованных с помощью декартовых деревьев, могут использоваться хэш-списки, простые списки (массивы) и т.п.; может также использоваться хранение в виде отрезка журнала с момента создания снимка.
При запуске СУБД происходит следующее:
Открывается самый новый статический снимок, по нему определяется соответствующая точка сохранения в журнале.
Инициализируется пустой частичный образ в памяти.
Сканируются записи в журнале, начиная с точки сохранения; соответствующие действия применяются к частичному образу в памяти.
Метаиндекс статического снимка читается в оперативную память.
После этого система готова исполнять запросы. Несложно видеть, что ее время загрузки пропорционально числу записей в журнале после последнего «сохранения», и размер частичного образа, который должен помещаться в оперативной памяти, также пропорционален этому числу; поэтому точки сохранения должны располагаться достаточно часто (в типичных ситуациях они создаются 1-5 раз в сутки).
Для выполнения запроса обновления (update) он преобразуется в последовательность атомарных обновлений, каждое из которых пишется с журнал и применяется к частичному образу в памяти. Поэтому обновления выполняются очень эффективно, примерно с той же скоростью, что и в системах на основе журнала с образом в памяти.
Запросы выборки данных выполняются следующим образом. Прежде всего, они выполняются на статическом снимке, для чего с помощью метаиндекса из статического снимка читаются нужные данные и затем обрабатываются. Затем частичный образ в памяти используется для выполнения того же запроса, однако при этом может модифицироваться и часть ответа, полученная из статического снимка (например, при обнаружении в частичном образе отрицательной записи, соответствующей записи, найденной через статический снимок). В итоге требуется ровно столько же обращений к диску, как и для системы со статическим снимком, а общее время исполнения запроса равно сумме времени его исполнения по статическому снимку и по частичному образу в памяти. При правильном выборе структур данных второе слагаемое гораздо меньше первого.
В итоге получается система с такой же скоростью обновлений (update), как у системы на основе журнала и образа в памяти, и практически с такой же скоростью выборки (select), как у систем на основе статического снимка. Требования к диску (по запросам и по объему) примерно такие же, как у систем на основе статического снимка, поскольку достаточно хранить только последний статический снимок и отрывок журнала, начиная с соответствующей позиции сохранения (обычно он гораздо меньше статического снимка). Конечно же, для надежности можно хранить два последних статических снимка (и журнал, начиная с самой старой из этих точек сохранения), и/или хранить копию статического снимка и журнала на другом диске. Очевидно, это почти не замедлит работу: единственное, что обновления журнала придется сбрасывать сразу на два диска, но они обычно очень небольшие и хорошо локализованные.
При этом такая система не только обходит стандартные системы с динамическими снимками (MySQL, Oracle) по скорости работы, эффективности использования диска и надежности (в системах с динамическим снимком дублирование на два диска, программное или через raid, фактически уменьшает вдвое пропускную способность), но и обеспечивает целостность транзакций (если используются только атомарные или чистые update), в том числе и на чтение.
Переиндексирование
Справедливости ради следует отметить, что, в отличие от систем на основе динамического снимка, системы на основе журнала и статического снимка нуждается в постоянном создании новых статических снимков (и удалении старых, но это как раз просто). Необходимость в этом возникает, когда отрезок журнала после последней позиции сохранения становится слишком большим (поскольку время чтения этого куска с диска определяет время запуска СУБД), либо когда размер частичного образа в памяти становится слишком большим (скажем, превышает 70% от размера буфера). В этих случаях СУБД может инициировать запуск процесса переиндексации, который может быть реализован отдельной программой. Кроме того, может иметь смысл запускать переиндексацию в момент суточного минимума нагрузки, особенно если естественный интервал между переиндексациями оказывается больше суток. На одном сервере может быть запущено несколько копий СУБД, управляющих разными таблицами; в этом случае разумно обеспечить между ними минимальную синхронизацию, чтобы два разных переиндексирующих процесса не запускались одновременно.
Переиндексирующий процесс фактически повторяет действия СУБД при старте (находит самый новый статический снимок, сканирует журнал с соответствующей точки сохранения, строит частичный образ в памяти, возможно, со своей спецификой), после чего создает новый статический снимок, исходя из старого статического снимка и частичного образа в памяти. В оптимальном случае для этого достаточно последовательно читать старый статический снимок, дополнять прочитанные данные согласно частичному образу, и записывать результат в новый статический снимок (который лучше всего создавать на другом диске). Например, в ситуации нашего примера можно последовательно читать списки WList(x), модифицировать их и записывать в новый снимок, не забывая уничтожать списки, ставшие пустыми, и добавлять ранее не существовавшие списки, после чего дописать метаиндекс в конец файла. В других ситуациях могут понадобиться более сложные технологии вроде многопроходной сортировки на диске.
После создания нового статического снимка основной процесс СУБД должен быть перезапущен. Это можно сделать с помощью специального сигнала, после получения которого основной процесс прочитает в новый буфер новый метаиндекс, и когда он будет (асинхронно) прочитан — очистит частичный образ в памяти, переключится на новый метаиндекс, и прочитает и заново применит все записи из журнала, созданные после новой точки сохранения.
Процесс переиндексирования (создания нового статического снимка) может быть достаточно трудоемким; однако, во-первых, поскольку всегда запущено не более одного процесса (на все копии СУБД на данном сервере), он использует не более одного процессора, и к тому же может использовать больше оперативной памяти для работы, чем обычная копия СУБД; во-вторых, несмотря на интенсивный дисковый ввод-вывод, обычно преобладает последовательное чтение/запись, гораздо более эффективное, чем случайный доступ, используемый системами с динамическим снимком, и к тому же можно создавать новый снимок на другом диске; в-третьих,во многих случаях можно устроить переиндексирование в момент суточного минимума, когда побочное влияние на работающие процессы СУБД (за счет использования процессора и памяти, а также дискового ввода-вывода) будет минимальным.
Как это ни странно, наличие процесса переиндексирования имеет свои положительные стороны. Например, можно модифицировать схему (скажем, добавить столбец в существующую таблицу), просто указав, что при запуске переиндексирующего процесса новый статический снимок должен быть записан в новом формате и в новой схеме. Конечно же, для этого должна быть совместимость снизу вверх на уровне записей в журнале. Кроме того, после создания статического снимка можно сразу создать его резервную копию на другом диске (либо параллельно записывать новый снимок на два диска). Это потребует определенного количества последовательного дискового ввода-вывода, но только при переиндексировании.
Сравнение разных способов
Далее приводится сравнение разных способов хранения данных в СУБД по пятибалльной шкале: 1 означает «ужасно» (т.е. очень много или очень мало в зависимости от параметра), 5 означает «очень хорошо» (система работает быстро, диск почти не использует, позволяет работать с очень большими таблицами и т.д.). Значение «5+» означает, что параметр соптимизирован до предела (скажем, дисковый ввод-вывод вообще не нужен), значение «0″ означает, что функционал не поддерживается.
Тип системы / Характеристика
Тип системы скорость select скорость update диск select диск update скорость загрузки размер таблиц размер файлов исп. памяти
log 1 5 5+ 5 5+ 3 2 5+
memory image 5 5 5+ 5+ 5+ 2 - 3
log + image 5 5 5+ 5+ 1 2 2 3
dynamic snapshot 4 4 4 3 4 4 3 4
static snapshot 5 0 5 0 5 5 5 5
log + static snapshot + image 5 5 5 5 4 5 4 4
В общем и целом видно, что для неизменяющихся больших таблиц оптимальным является использование статического снимка (пример: поисковые системы), а для изменяющихся больших таблиц оптимально использование журнала со статическим снимком и частичным образом в памяти (пример: KittenDB); единственной альтернативной является динамический снимок (практически все СУБД: Oracle, MySQL, PostgreSQL,…).
При выборе между этими двумя вариантами следует учесть, что системы, основанные на динамических снимках (распространенные СУБД общего назначения) могут выполнять широкий круг SQL-запросов, не слишком сильно зависящих от схемы (однако наличие или отсутствие индексов может очень сильно повлиять на время исполнения запроса), и создание таблиц с новой схемой довольно несложно (надо составить подходящий CREATE TABLE …). В то же время системы, основанные на журнале и статических снимках показывают превосходящие результаты только при условии аккуратного составления схемы и выбора правильных структур данных, и допускают эффективное выполнение только запросов, изначально указанных в схеме. Создание таблицы с новой схемой крайне трудоемко (в случае с KittenDB требуется написание нового модуля на языке C, и является творческим, а не рутинным процессом).
В связи с этим представляется разумным использовать системы вроде KittenDB только в тех ситуациях, когда распространенные СУБД вроде MySQL уже по каким-либо причинам не в состоянии обеспечить нужный результат (на приемлемом количестве серверов), т.е. для отдельных высоконагрузочных подсистем, в которых хранятся большие объемы данных. Характерные примеры: обработка поисковых запросов, хранение большого объема текстов (например, сообщений).
Преимущества и недостатки систем, основанных на журнале и статическом снимке
Преимущества:
Больший объем хранимых данных, более эффективное использование диска и дискового кэша (в 1.5—3 раза).
Быстрые select’ы (по схеме), требующие минимума дискового ввода-вывода; при этом обеспечивается целостность транзакции (возвращается результат, соответствующий конкретному моменту времени).
Быстрые update’ы (по схеме), требующие еще меньше дискового ввода-вывода (в типичных ситуациях несколько десятков байтов на запрос, и несколько десятков килобайтов в секунду, причем в соседние сектора диска).
Сопоставимое время штатной загрузки; более быстрое восстановление после аварии.
Возможность дублирования всей информации (снимков и журнала) на два диска, при этом загрузка системы увеличивается незначительно (update требуют двойного количества записи на диск, но она невелика).
Возможность легкого создания бэкапов (достаточно списать последний снимок и кусок журнала, не останавливая СУБД).
Возможность получения согласованного полного дампа одной таблицы или всей БД (надо всего лишь запомнить позиции во всех журналах на момент дампа, затем по очереди для каждой таблицы запускать аналог основной программы СУБД, указав, до какой позиции надо читать журнал и куда надо сохранить дамп).
Простота репликации (достаточно отсылать все изменения журнала на другой сервер); впрочем, это аналогично тому, как репликация работает на традиционных СУБД, с той разницей, что в данном случае стоимость update гораздо меньше стоимости select, и потому становится оправданной репликация и в тех случаях, когда традиционные СУБД уже не могут справиться с обновлениями.
Простота создания резервных копий, готовых к запуску: для этого надо запустить реплику на другом сервере, указав, что она должна отрабатывать только update, но не select; тогда репликация будет требовать минимум памяти и дискового ввода-вывода на реплицирующем сервере, основные затраты будут на периодическое создание новых снимков; если основная копия таблицы поломается, достаточно перезапустить копию СУБД на реплике в обычном режиме. Поэтому один сервер в состоянии хранить резервные копии (реплики) от нескольких других серверов, что редко возможно для систем с динамическими снимками (из-за большого количества обращений к диску на один update). В итоге можно добиться резервирования всех данных и на уровне дисков, и на уровне серверов, лишь незначительно увеличив их общее количество и нагрузку на них.
Недостатки:
Сложность добавления в СУБД таблиц с новой схемой. Этот процесс становится творческим, а не рутинным процессом: в KittenDB требуется написать новый модуль на C, предварительно аккуратно составив схему, выбрав правильный набор атомарных обновлений, наиболее эффективные структуры данных для статического снимка и образа в памяти и реализовав наиболее эффективные алгоритмы для работы с ними. После этого требуется определенный период отладки. А в традиционных СУБД достаточно набрать нужный CREATE TABLE …, и вся сложность сводится к придумыванию правильных индексов.
vk-com / kphp-kdb
branch: master kphp-kdb / docs / ru / Interface.wiki
Vkontakte 19 hours ago Fix ‘pre’ tag usage in docs.
1 contributor
file 126 lines (92 sloc) 9.381 kb Open EditRawBlameHistory Delete
Table of Contents
Использование KittenDB/Engine
Запуск движка
Создание бинлога
Работа с запущенным движком
Memcache-интерфейс
RPC-интерфейс
MC-Proxy и RPC-Proxy
Использование KittenDB/Engine
KittenDB/Engine состоит из большого количества независимых утилит со схожими опциями командной строки и интерфейсом. Каждая такая утилита обычно называется «движком» и представляет из себя специализированную нереляционную БД, построенную по принципу «бинлог» + «образ в памяти» + «снимок на диске». Например, text-engine используется для хранения большого количества текстов и поиска по ним, «lists-engine» — для хранения большого количества списков чисел, и т.д.
Запуск движка
Для компиляции и запуска нужен Linux с ядром не менее 2.6.18, желательно не менее 3.0. Другие операционные системы на данный момент не поддерживаются, например, из-за явного использования системного вызова epoll().
Запускаемые файлы создаются `make` в подкаталог `objs/bin`. Нужные из них удобно скопировать в какой-нибудь общедоступный каталог, например, `/usr/share/engine/bin/` . Если используется Debian, полезно использовать init.d-файл и logrotate-файл из каталога `scripts`. Там же есть скрипт `start-engine`, который тоже полезно положить в `/usr/share/engine/bin/`.
Конфигурационные файлы хранятся в `/etc/engine`. Они называются `/etc/engine/engine.$id.conf`, где $id — не более чем трёхсимвольный идентификатор экземпляра движка (обычно используются числа 1—99, а также латинские буквы a,b,c…).
Такой конфигурационный файл обычно содержит название движка, его основной параметр (префикс имени бинлога) и прочие опции командной строки. Например:
Файл /etc/engine/engine.1.conf:
execute lists-engine
arg1 groups23
-p 11200
-vvv
При запуске /etc/init.d/engine start 1 или просто /etc/init.d/engine start (который легко сделать автоматическим при загрузке) будет запущен
/usr/share/engine/bin/lists-engine groups23 -u kitten -p 11200 -vv -l /var/log/engine/engine-1.log >> /var/log/engine/engine-1.log 2>&1
из домашнего каталога /var/lib/engine/
Этот экземпляр lists-engine будет использовать /var/lib/engine/groups23.bin в качестве бинлога (основного хранилища данных) и будет отвечать на memcache или rpc-запросы по tcp-порту 11200.
Кроме того, если его запустить под root’ом, он будет работать под пользователем kitten (которому лучше всего прописать /var/lib/engine в качестве домашнего каталога и uid 239). Желательно, чтобы у этого пользователя были права rwx на каталог /var/lib/engine, или нужные подкаталоги.
Внимание: перед запуском под Линукс желательно сделать
echo 1 > /proc/sys/vm/overcommit_memory
либо прописать vm.overcommit_memory = 1 в /etc/sysctl.conf.
Создание бинлога
Как уже отмечалось, движки используют бинлоги в качестве основного хранилища данных. Если бинлога нет, они его не создают, а аварийно завершают работу. Поэтому перед первым запуском нужно создать «пустой» бинлог, состоящий из 24 байтов (запись LEV_START). Для lists-engine он выглядит примерно так:
+0 int LEV_START = 0x044c644b; // общий заголовок для всех KDB-бинлогов
+4 int type = 0x6ef20101; // формат бинлога (свой у каждого движка)
+8 int extra_bytes = 0;
+12 int split_mod = 128; // модуль для дробления
+16 int split_min = 98;
+20 int split_max = 99; // обычно 0 <= split_min < split_max <= split_mod, и split_max = split_min + 1
+24 дополнительные байты в количестве extra_bytes штук, дополненные до границы 4 байт (в данном случае не нужны)
$ hexdump -C /var/lib/engine/groups23.bin
00000000 4b 64 4c 04 01 01 f2 6e 00 00 00 00 80 00 00 00 |KdL....n........|
00000010 62 00 00 00 63 00 00 00 |b...c...|
Параметры дробления означают, что этот экземпляр lists-engine будет обрабатывать запросы к спискам с list_id, удовлетворяющим
abs(list_id) % 128 == 98.
После того, как бинлог создан и передан пользователю kitten, можно запускать lists-engine -- из командной строки или через механизм запуска демонов ( /etc/init.d/engine start 1 ).
Работа с запущенным движком
Memcache-интерфейс
Почти все движки поддерживают вариант memcache-интерфейса. Поэтому к ним можно подключиться из PHP или другого языка высокого уровня через обычный memcache-интерфейс:
$MC_Lists = new Memcache ('127.0.0.1', 11200);
$MC_Lists->add («entry98_239″, «1,0″);
$MC_Lists->add («entry98_666″, «2,66666″);
$MC_Lists->add («entry226_77″, «7,4″);
var_dump ($MC_Lists->get («list98″);
Либо даже через telnet:
$ telnet localhost 11200
version
VERSION/2.3.9
set entry98_17 0 0 3
3,0
STORED
get list98
3,17,239,666
Через telnet особенно интересно вводить команду stats.
RPC-интерфейс
Это более прогрессивный метод, однако он требует установки расширения vkext для PHP (в KittenPHP поддержка RPC встроена). В конфигурации vkext надо указать путь к файлу combined.tlo, генерируемому при компиляции движков через make в каталоге objs/TL .
После этого можно будет слать запросы примерно так:
$RPC_Lists = new_rpc_connection («localhost», 11200);
var_dump (rpc_tl_query_result (rpc_tl_query ($RPC_Lists, array (array («lists.setEntry», 1, 1, array (98), (1 << 15) + (1 << 6), array ("flags" => 3, «object_id» => array (17)))))));
var_dump (rpc_tl_query_result (rpc_tl_query ($RPC_Lists, array (array («lists.getList», 1, 1, array (98), (1 << 15))))));
--
array ("_" => «rpcQueryResult», «result» => true);
array («_» => «rpcQueryResult», «result» => array («total» => 3, «vector» => array (array (17), array (239), array (666))));
MC-Proxy и RPC-Proxy
В каких-то случаях полезно мультиплексировать все запросы с сервера к различным кластерам движков (например, 128 экземпляров lists-engine для хранения «groups» образуют один кластер; другие 64 экземпляров lists образуют кластер «friends»; ещё 256 экземпляров text-engine образуют кластер «msg», и т.д.) через специальный софт, называемый mc-proxy (для memcache-интерфейса) или rpc-proxy (для rpc-интерфейса).
Такой прокси создаёт несколько кластеров (каждый на своём порту), и мультиплексирует поступающие (обычно через localhost) запросы на сервера, перечисленные в конфигурации кластера, в зависимости от значения параметра дробления (вроде list_id) в теле запроса. Тем самым каждому PHP-worker’у не нужно самостоятельно держать соединения ко всем используемым движкам и отслеживать, куда нужно отправлять какой запрос.
Комментарии закрыты.