Наши партнеры

Библиотека сайта rus-linux.net

База с "археологическим" принципом хранения данных

Оригинал: An Archaeology-Inspired Database
Автор: Yoav Rubin
Дата публикации: 20 October 2015
Перевод: Н.Ромоданов
Дата перевода: июль 2016 г.

Архитектура движка запросов

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

Выполнение запроса состоит из следующих фаз:

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

Фаза 1: Преобразование

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

Часть :find запроса преобразуется в набор заданных имен переменных:

(defmacro symbol-col-to-set [coll] (set (map str coll)))

Часть :where запроса сохраняет свою структуру вложенных векторов. Но каждый элемент в каждом предложении заменяется предикатом согласно таблицы 2.

(defmacro clause-term-expr [clause-term]
   (cond
    (variable? (str clause-term)) ;variable
      #(= % %) 
    (not (coll? clause-term)) ;constant 
      `#(= % ~clause-term) 
    (= 2 (count clause-term)) ;unary operator
      `#(~(first clause-term) %) 
    (variable? (str (second clause-term)));binary operator, 1st operand is variable
      `#(~(first clause-term) % ~(last clause-term))
    (variable? (str (last clause-term)));binary operator, 2nd operand is variable
      `#(~(first clause-term) ~(second clause-term) %)))

Также в каждом предложении вектор с именами переменных, используемых в этом предложении, преобразуется в метаданные.

(defmacro clause-term-meta [clause-term]
   (cond
   (coll? clause-term)  (first (filter #(variable? % false) (map str clause-term))) 
   (variable? (str clause-term) false) (str clause-term) 
   :no-variable-in-clause nil))

Мы используем функцию pred-clause для перебора элементов каждого предложения:

(defmacro pred-clause [clause]
   (loop [[trm# & rst-trm#] clause exprs# [] metas# []]
     (if  trm#
          (recur rst-trm# (conj exprs# `(clause-term-expr ~ trm#)) 
                       (conj metas#`(clause-term-meta ~ trm#)))
          (with-meta exprs# {:db/variable metas#}))))

Перебор предложений происходит самостоятельно внутри функции q-clauses-to-pred-clauses:

(defmacro  q-clauses-to-pred-clauses [clauses]
     (loop [[frst# & rst#] clauses preds-vecs# []]
       (if-not frst#  preds-vecs#
         (recur rst# `(conj ~preds-vecs# (pred-clause ~frst#))))))

Мы снова полагаться на то, что макросы не проверяют свои аргументы. Это позволяет нам определить простой интерфейс API, в котором пользователи задают имена переменных как символов (например, ?name) и им не требуется понимать внутреннее устройство движка запросов и передавать имена переменных в виде строк (например, "?name") или, что еще хуже, указывать ссылку на имя переменной (например, '?name).

В конце этой фазы в нашем примере в части :find будет получен следующий результат:

#{"?nm" "?bd"}

и в части :where следующая структура, показанная в таблице 3. Каждая ячейка в столбце Predicate Clause содержит метаданные, найденные с помощью запроса, указанного в колонке Meta Clause.

Таблица 3: Предложения

Query Clause (Предложение - запрос)	Predicate Clause (Предикативное предложение)	eta Clause (Метапредложение)
[?e :likes "pizza"]	[#(= % %) #(= % :likes) #(= % "pizza")]	["?e" nil nil]
[?e :name ?nm]	[#(= % %) #(= % :name) #(= % %)]	["?e" nil "?nm"]
[?e :speak "English"]	[#(= % %) #(= % :speak) #(= % "English")]	["?e" nil nil]
[?e :birthday (birthday-this-month? ?bd)]	[#(= % %) #(= % :birthday) #(birthday-this-month? %)]	["?e" nil "?bd"]

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

Фаза 2: Создание плана запроса

На этой фазе мы проверяем запрос с тем, чтобы создать хороший план получения результата по сделанному запросу.

В общем, это будет связано с выбора соответствующего индекса (Таблица 4) и построения плана в виде функции. Мы выбираем индекс, основанный на одной соединительной переменной (который может работать только на один вид элемента).

Таблица 4: Выбор индекса

Объединяющая переменная использует	Используемый индекс
Идентификаторы сущностей	AVET
Имена атрибутов	VEAT
Значения индексов	EAVT

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

Выбор индекса, соответствующего объединяющей переменной, выполняется с помощью функции index-of-joining-variable:

(defn index-of-joining-variable [query-clauses]
   (let [metas-seq  (map #(:db/variable (meta %)) query-clauses) 
         collapsing-fn (fn [accV v] (map #(when (= %1 %2) %1)  accV v))
         collapsed (reduce collapsing-fn metas-seq)] 
     (first (keep-indexed #(when (variable? %2 false) %1)  collapsed))))

Мы начинаем с извлечения метаданных из каждого предложения в запросе. Извлекаемые данные будут представлять собой вектор, состоящий из трех элементов; каждый элемент в векторе является либо именем переменной, либо значением nil. Обратите внимание на то, что в этом векторе будет не более одного имени переменной. После того, как вектор будет извлечен, мы создаем из него (просто уменьшаем его) одно значение, которое будет либо именем переменной, либо значением nil. Если будет получено имя переменной, то оно присутствует во всех векторах с метаданными одного и того же индекса; т.е. это объединяющая переменная. Таким образом, мы можем согласно таблице, приведенной выше, выбрать индекс, соответствующий используемой объединяющей переменной.

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

(defn build-query-plan [query]
   (let [term-ind (index-of-joining-variable query)
         ind-to-use (case term-ind 0 :AVET 1 :VEAT 2 :EAVT)]
      (partial single-index-query-plan query ind-to-use)))

В нашем примере выбран индекс AVET, т.к. в объединяющей переменной используются идентификаторы сущностей.

Фаза 3: Исполнение плана

На предыдущей фазе мы видели, что план запроса, который мы создали, завершается вызовом функции single-index-query-plan. Эта функция будет выполнять следующее:

Применит каждое предикатное предложение с выбранным индексом (каждый предикат применяется на соответствующем уровне индекса).
Выполнит операцию AND (логическое И) со всеми результатами.
Объединит результаты в более простую структуру данных.

(defn single-index-query-plan [query indx db]
   (let [q-res (query-index (indx-at db indx) query)]
     (bind-variables-to-query q-res (indx-at db indx))))

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

Таблица 5: Примеры сущностей

Идентификатор сущности	Имя атрибута	Значение атрибута
1	:name :likes :speak :birthday	USA Pizza English July 4, 1776
2	:name :likes :speak :birthday	France Red wine French July 14, 1789
3	:name :likes :speak :birthday	Canada Snow English July 1, 1867

Теперь настало время проникнуть в кроличью нору и взглянуть на функцию query-index, в которой наш запрос, наконец, начинает давать некоторые результаты:

(defn query-index [index pred-clauses]
   (let [result-clauses (filter-index index pred-clauses)
         relevant-items (items-that-answer-all-conditions (map last result-clauses) 
                                                          (count pred-clauses))
         cleaned-result-clauses (map (partial mask-path-leaf-with-items 
                                              relevant-items)
                                     result-clauses)] 
     (filter #(not-empty (last %)) cleaned-result-clauses)))

Эта функция начинается с применения предикатного предложения с ранее выбранным индексом. Каждое применение предикатного предложения с индексом возвращает результирующее предложение.

Основные характеристики получаемого результата:

Он строится из трех элементов, каждый из которых создается на разных уровнях индекса и для каждого из которых выполняется соответствующий предикат.
Порядок элементов соответствует структуре уровней индекса. Предикатные предложения всегда соответствуют порядку индекса EAV. Переупорядочивание происходит, когда функция from-eav, работающая индексами, применяется на предикативном предложении.
К результату присоединяются метаданные предикативного предложения.

Все это делается в функции filter-index.

(defn filter-index [index predicate-clauses]
   (for [pred-clause predicate-clauses
         :let [[lvl1-prd lvl2-prd lvl3-prd] (apply (from-eav index) pred-clause)] 
         [k1 l2map] index  ; keys and values of the first level
         :when (try (lvl1-prd k1) (catch Exception e false))

         [k2  l3-set] l2map  ; keys and values of the second level
         :when (try (lvl2-prd k2) (catch Exception e false))
         :let [res (set (filter lvl3-prd l3-set))] ]
     (with-meta [k1 k2 res] (meta pred-clause))))

Предполагая, что запрос был выполнен на 4 июля, результаты его выполнения для приведенных выше данных показаны в таблице 6.

Таблица 6: Результаты запросов

Результирующее предложение	Результирующие метаданные
[:likes Pizza #{1}]	["?e" nil nil]
[:name USA #{1}]	["?e" nil "?nm"]
[:speak "English" #{1, 3}]	["?e" nil nil]
[:birthday "July 4, 1776" #{1}]	["?e" nil "?bd"]
[:name France #{2}]	["?e" nil "?nm"]
[:birthday "July 14, 1789" #{2}]	["?e" nil "?bd"]
[:name Canada #{3}]	["?e" nil "?nm"]
[:birthday "July 1, 1867" {3}]	["?e" nil "?bd"]

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

(defn items-that-answer-all-conditions [items-seq num-of-conditions]
   (->> items-seq ; берем items-seq
         (map vec) ; делаем каждую коллекцию (в действительности, множество) вектором
         (reduce into []) ;преобразуем все вектора в один вектор
         (frequencies) ;для каждого элемента подсчитываем, в каком количестве коллекций (множеств) он находится
         (filter #(<= num-of-conditions (last %))) ;элементы, которые отвечают всем условиям
         (map first) ; берем сами элементы
         (set))) ; возвращаем их в виде множества

В нашем примере, результатом этого этапа является множество, содержащее значение 1 (идентификатор субъекта из США).

Теперь мы должны удалить элементы, которые не соответствуют всем условиям:

(defn mask-path-leaf-with-items [relevant-items path]
     (update-in path [2] CS/intersection relevant-items))

Наконец, мы удаляем все результирующие предложения, которые "пусты" (то есть, их последний элемент пустой). Мы делаем это в последней строке функции query-index. В нашем примере остаются следующие результаты:

Таблица 7: Результаты запроса после фильтрации

Результирующее предложение	Результирующие метаданные
[:likes Pizza #{1}]	["?e" nil nil]
[:name USA #{1}]	["?e" nil "?nm"]
[:birthday "July 4, 1776" #{1}]	["?e" nil "?bd"]
[:speak "English" #{1}]	["?e" nil "?nm"]

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

Чтобы понять преобразование, мы должны сначала ввести понятие связной пары (binding pair), которая является парой, связывающей имя переменной и значение. Имя переменной является именем, которое используется в предикатных предложениях, а значением является значение, полученное в в результирующих предложениях.

Преобразование к индексной структуре заключается в том, что теперь держим связную пару идентификатора сущности / имени атрибута / значения там, где в индексе были идентификатор сущности / имя атрибута / значение:

(defn bind-variables-to-query [q-res index]
   (let [seq-res-path (mapcat (partial combine-path-and-meta (from-eav index)) 
                               q-res)       

         res-path (map #(->> %1 (partition 2)(apply (to-eav index))) seq-res-path)] 
     (reduce #(assoc-in %1  (butlast %2) (last %2)) {} res-path)))

(defn combine-path-and-meta [from-eav-fn path]
    (let [expanded-path [(repeat (first path)) (repeat (second path)) (last path)] 
          meta-of-path (apply from-eav-fn (map repeat (:db/variable (meta path))))
          combined-data-and-meta-path (interleave meta-of-path expanded-path)]
       (apply (partial map vector) combined-data-and-meta-path)))

В конце фазы 3 выполнения нашего примера мы получаем следующую структуру:

 {[1 "?e"] {
        [:likes nil]    ["Pizza" nil]
        [:name nil]     ["USA" "?nm"]
        [:speaks nil]   ["English" nil] 
        [:birthday nil] ["July 4, 1776" "?bd"]} 
    }}

Фаза 4: Унификация и отчет

На данный момент, мы подготовили больше результатов, чем первоначально запросил пользователь. На этой фазе мы извлекаем значения, которые нужны пользователю. Этот процесс называется унификацией (unification): именно здесь мы унифицируем структуру связных пар с вектором имен переменных, которые пользователь определяется в запросе в предложении :find.

(defn unify [binded-res-col needed-vars]
   (map (partial locate-vars-in-query-res needed-vars) binded-res-col))

Каждый шаг унификации выполняется функцией locate-vars-in-query-result, которая перебирает результат запроса (структурированного как указатель, а не как связные пары) для того, чтобы найти все переменные и значения, которые запросил пользователь.

(defn locate-vars-in-query-res [vars-set q-res]
   (let [[e-pair av-map]  q-res
         e-res (resultify-bind-pair vars-set [] e-pair)]
     (map (partial resultify-av-pair vars-set e-res)  av-map)))

(defn resultify-bind-pair [vars-set accum pair]
   (let [[ var-name _] pair]
      (if (contains? vars-set var-name) (conj accum pair) accum)))
(defn resultify-av-pair [vars-set accum-res av-pair]
   (reduce (partial resultify-bind-pair vars-set) accum-res av-pair))
At the end of this phase, the results for our example are:
[("?nm" "USA") ("?bd" "July 4, 1776")]

Итог

Наконец мы собираем все компоненты, которые нужны для реализации механизма пользовательского запроса, в виде макроса q, который получает в качестве аргументов базу данных и запрос.

(defmacro q
  [db query]
  `(let [pred-clauses#  (q-clauses-to-pred-clauses ~(:where query)) 
         needed-vars# (symbol-col-to-set  ~(:find query))
         query-plan# (build-query-plan pred-clauses#)
         query-internal-res# (query-plan# ~db)]
     (unify query-internal-res# needed-vars#)))

Заключение

Наше турне началось с рассмотрения концепции баз данных различного вида и закончилось следующим:

Поддержкой транзакций ACI (возможность длительного хранения данных была потеряна, когда мы решили работать только с данными, хранящимися в памяти).
Поддержкой взаимодействий вида "what if" ("что, если").
Ответами на вопросы, касающиеся времени.
Обработкой простых запросов datalog, оптимизированных за счет использования индексов.
Предложением интерфейса API для запросов в виде графов.
Введением и реализацией понятия эволюционирующих запросов.

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

Тем не менее, наш итоговый продукт может делать очень многое и размер его реализации равен 488 строк исходного кода на языке Clojure, 73 из которых являются пустыми, а 55 являются строками документации.

Наконец, есть одна вещь, которая до сих пор отсутствует: название СУБД. СУБД, которая хранит данные только в памяти, оптимизирована с использованием индексов, поддерживает работу с запросами, имеет библиотечную архитектуру и в 360 строках языка Clojure, называется CircleDB.

Дополнение

Перевод данной главы сделан по тексту преварительной публикации. 12 июля 2016 был выпущен и опубликован на сайте AOSA окончательный вариант сборника "500 строк или меньше", четвертой книги из серии книг "Архитектура приложений с открытым исходным кодом". Окончательный вариант данной главы можно найти по следующей ссылке.

Вернуться к началу статьи.