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

UnixForum

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

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

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

Поведение данных и жизненный цикл

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

Как мы уже обсуждали, данные в мире археологии на самом деле никогда не меняются. После того, как они будут созданы, они существуют вечно и могут быть скрыты от мира только данными нового слоя. Здесь решающее значение имеет термин "скрыть". Более старые данные не "исчезают" — они будут "засыпаны" новым слоем и к ним можно добраться, если "раскопать" старый слой. Наоборот, обновление данных означает, что старый слой будет поверх засыпан новым слоем, в котором будет что-то другое. Точно также можно "удалить" данные, добавив поверх слой, в котором ничего нет.

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

Углубляемся в детали

Жизненный цикл данных состоит из трех основных операций:

  • добавления сущности с помощью функции add-entity
  • удаления сущности с помощью функции remove-entity
  • обновления сущности с помощью функции update-entity

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

Добавление сущности

Добавление сущности потребует от нас выполнить следующие три действия:

  • подготовить сущности для добавления (задав для нее идентификатор и временную метку)
  • разместить объект в хранилище
  • изменить индексы так, как надо

Эти шаги выполняются в функции add-entity.

(defn add-entity [db ent]
   (let [[fixed-ent next-top-id] (fix-new-entity db ent)
         layer-with-updated-storage (update-in 
                            (last (:layers db)) [:storage] write-entity fixed-ent)
         add-fn (partial add-entity-to-index fixed-ent)
         new-layer (reduce add-fn layer-with-updated-storage (indexes))]
    (assoc db :layers (conj (:layers db) new-layer) :top-id next-top-id)))

Подготовка сущности осуществляется с помощью вызова функции fix-new-entity и ее вспомогательных функций next-id, next-ts и update-creation-ts. Эти две последние вспомогательные функции ответственны за поиск следующей временной метки базы данных (выполняется с помощью next-ts) и обновление созданной временной метки данной сущности (выполняется с помощью update-creation-ts). Обновление созданной временной метки сущности означает изменение атрибутов сущности и обновления их полей :ts.

(defn- next-ts [db] (inc (:curr-time db)))

(defn- update-creation-ts [ent ts-val]
   (reduce #(assoc-in %1 [:attrs %2 :ts ] ts-val) ent (keys (:attrs ent))))

(defn- next-id [db ent]
   (let [top-id (:top-id db)
         ent-id (:id ent)
         increased-id (inc top-id)]
         (if (= ent-id :db/no-id-yet)
             [(keyword (str increased-id)) increased-id]
             [ent-id top-id])))

(defn- fix-new-entity [db ent]
   (let [[ent-id next-top-id] (next-id db ent)
         new-ts               (next-ts db)]
       [(update-creation-ts (assoc ent :id ent-id) new-ts) next-top-id]))

Чтобы добавить сущность в хранилище, мы ищем самый последний слой в базе данных и обновляем хранилище в этом слое с помощью нового слоя. Результаты такой операции назначаются локальной переменной layer-with-updated-storage.

Наконец, мы должны обновить индексы. Это означает, что для каждого из индекса (выполняется с помощью комбинации reduce и фрагментов add-entity-to-index в функции add-entity) мы должны сделать следующее:

  • Найти атрибуты, которые должны быть проиндексированы (смотрите комбинацию filter с usage-pred индекса, которая работает на атрибутах add-entity-to-index)
  • Построить индекс-путь от идентификатора сущности (смотрите комбинацию фрагментов update-entry-in-index с функцией update-attr-in-index)
  • Добавить этот путь к индексу (смотрите функцию update-entry-in-index)
(defn- add-entity-to-index [ent layer ind-name]
   (let [ent-id (:id ent)
         index (ind-name layer)
         all-attrs  (vals (:attrs ent))
         relevant-attrs (filter #((usage-pred index) %) all-attrs)
         add-in-index-fn (fn [ind attr] 
                                 (update-attr-in-index ind ent-id (:name attr) 
                                                                  (:value attr) 
                                                                  :db/add))]
        (assoc layer ind-name  (reduce add-in-index-fn index relevant-attrs))))

(defn- update-attr-in-index [index ent-id attr-name target-val operation]
   (let [colled-target-val (collify target-val)
         update-entry-fn (fn [ind vl] 
                             (update-entry-in-index 
                                ind 
                                ((from-eav index) ent-id attr-name vl) 
                                operation))]
     (reduce update-entry-fn index colled-target-val)))

(defn- update-entry-in-index [index path operation]
   (let [update-path (butlast path)
         update-value (last path)
         to-be-updated-set (get-in index update-path #{})]
     (assoc-in index update-path (conj to-be-updated-set update-value))))

Все эти компоненты добавляются в качестве нового слоя в данную базу данных. Все, что осталось, это обновить временные метки базы данных и поля top-id. Это последний шаг выполняется в последней строке функции add-entity, которая также возвращает обновленную базу данных.

Мы также предоставляем удобную функцию add-entities, которая добавляет несколько сущностей к базе данных за один вызов с помощью итеративного применения функции add-entity.

(defn add-entities [db ents-seq] (reduce add-entity db ents-seq))

Удаление сущности

Удаление сущности из нашей базы означает добавление слоя, в котором ее не существует. Чтобы это сделать, мы должны:

  • Удалить саму сущность
  • Обновить все атрибуты других сущностей, которые ссылаются на нее
  • Убрать сущность из наших индексов

Этот процесс "конструкция-без" выполняется с помощью функции remove-entity, которая выглядит очень похожей на функцию add-entity:

(defn remove-entity [db ent-id]
   (let [ent (entity-at db ent-id)
         layer (remove-back-refs db ent-id (last (:layers db)))
         no-ref-layer (update-in layer [:VAET] dissoc ent-id)
         no-ent-layer (assoc no-ref-layer :storage 
                                   (drop-entity  
                                          (:storage no-ref-layer) ent))
         new-layer (reduce (partial remove-entity-from-index ent) 
                                 no-ent-layer (indexes))]
     (assoc db :layers (conj  (:layers db) new-layer))))

Удаление ссылки осуществляется с помощью функции remove-back-refs:

(defn- remove-back-refs [db e-id layer]
   (let [reffing-datoms (reffing-to e-id layer)
         remove-fn (fn[d [e a]] (update-entity db e a e-id :db/remove))
         clean-db (reduce remove-fn db reffing-datoms)]
     (last (:layers clean-db))))

Мы начинаем с использованием функции reffing-datoms-to, которая ищет все сущности, ссылающиеся на данный слой; она возвращает последовательность троек, содержащих идентификатор сущности, на которую осуществляется ссылка, а также имя атрибута и идентификатор удаленной сущности.

(defn- reffing-to [e-id layer]
   (let [vaet (:VAET layer)]
         (for [[attr-name reffing-set] (e-id vaet)
               reffing reffing-set]
              [reffing attr-name])))

Затем мы применяем функцию update-entity к каждой тройке с тем, чтобы обновить атрибуты, которые ссылаются на нашу удаленную сущность. (В следующем разделе мы будем изучать, как работает функция update-entity).

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

Обновление сущности

По своей сути обновление является модификацией значения атрибутов сущности. Сам процесс модификации зависит от кардинальности атрибута: атрибут с кардинальностью :db/multiple содержит набор значений, поэтому мы должны сделать так, чтобы можно было добавлять элементы в этот набор и удалять их из него, либо заменять этот набор полностью. Атрибут с кардинальностью :db/single имеет одно значение, и, следовательно, допускается только замена.

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

Когда мы пользуемся функциями add-entity и remove-entity, мы, в действительности, не изменяем нашу сущность прямо на месте, а вместо этого добавляем новый слой, который содержит обновленную сущность.

(defn update-entity
   ([db ent-id attr-name new-val]
    (update-entity db ent-id attr-name new-val :db/reset-to))
   ([db ent-id attr-name new-val operation]
      (let [update-ts (next-ts db)
            layer (last (:layers db))
            attr (attr-at db ent-id attr-name)
            updated-attr (update-attr attr new-val update-ts operation)
            fully-updated-layer (update-layer layer ent-id 
                                              attr updated-attr 
                                              new-val operation)]
        (update-in db [:layers] conj fully-updated-layer))))

Чтобы обновить атрибут, мы найти его с помощью функции attr-a, а затем используем функцию update-attr для выполнения фактического обновления.

(defn- update-attr [attr new-val new-ts operation]
    {:pre  [(if (single? attr)
            (contains? #{:db/reset-to :db/remove} operation)
            (contains? #{:db/reset-to :db/add :db/remove} operation))]}
    (-> attr
       (update-attr-modification-time new-ts)
       (update-attr-value new-val operation)))

Мы используем две вспомогательные функции для выполнения обновления. Функция update-attr-modification-time обновляет временные метки, что на рис.1 показано в виде черных стрелок:

(defn- update-attr-modification-time  
  [attr new-ts]
       (assoc attr :ts new-ts :prev-ts (:ts attr)))

Функция update-attr-value на самом деле обновляет значение:

(defn- update-attr-value [attr value operation]
   (cond
      (single? attr)    (assoc attr :value #{value})
      ; now we're talking about an attribute of multiple values
      (= :db/reset-to operation) 
        (assoc attr :value value)
      (= :db/add operation) 
        (assoc attr :value (CS/union (:value attr) value))
      (= :db/remove operation)
        (assoc attr :value (CS/difference (:value attr) value))))

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

Транзакции

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

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

Мы можем выполнить эти требования с помощью интерфейса, который берет базу данных и набор операций, которые будут выполняться, и выдает базу данных, состояние которой отражает данные изменения. Все изменения, выполняемые последовательно, должны быть применены с помощью добавления только одного слоя. Но у нас есть проблема: Все функции, которые мы написали в нашем API низкого уровня, добавляют к базе данных новый слой. Если мы выполним последовательность из n операций, мы из-за этого увидим n новых слоев, хотя все, что нам действительно надо, это иметь ровно один новый слой.

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

Все это делается в функции transact-on-db, которая получает начальное значение базы данных и пакета операций, которые нужно выполнить, и возвращает его обновленное значение.

(defn transact-on-db [initial-db ops]
    (loop [[op & rst-ops] ops transacted initial-db]
      (if op
          (recur rst-ops (apply (first op) transacted (rest op)))
          (let [initial-layer  (:layers initial-db)
                new-layer (last (:layers transacted))]
            (assoc initial-db :layers (conj initial-layer new-layer) 
                              :curr-time (next-ts initial-db) 
                              :top-id (:top-id transacted))))))

Здесь следует отметить, что мы использовали термин значение, что означает, что только тот, кто вызывает эту функцию, получит обновленное состояние; все остальные пользователи базы данных не знают об этом изменении (как база данных является значением, и, следовательно, не может быть изменена). Для того чтобы иметь систему, где пользователи могут получать доступ к изменениям, выполненными другими, пользователи не должны обращаться непосредственно к базе данных, а использовать для этого другой уровень косвенности. Этот дополнительный уровень реализуется с помощью ссылочного типа Atom языка Clojure. При этом мы используем три основные ключевые особенности типа Atom, к которым относятся следующие:

  • Это ссылка на значение.
  • Можно обновить ссылку Atom другим значением, если выполнить транзакцию (с помощью программных средств работы с транзакциями Software Transaction Memory, которые есть в языке Clojure). В качестве входных данных для выполнения транзакции используется Atom и функция. Эта функция оперирует со значением, получаемым через Atom, и возвращает новое значение. После совершения транзакции Atom ссылается на значение, которое было возвращено функцией.
  • Получить значение, на которое ссылается Atom, можно путем его разыменования; в результате будет возвращено состояние Atom на данный момент времени.

Между ссылочным типом Atom языка Clojure и работой, выполняемой функцией transact-on-db, есть еще некоторый промежуток, который нужно преодолеть; а именно — выполнить транзакцию с правильными входными данными.

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

Такое преобразование происходит в виде следующей цепочки транзакционных вызовов:

transact →  _transact → swap! → transact-on-db

Пользователе вызывают функцию transact со значением Atom (то есть, коннектором к базе данных) и операциями, которые должны быть выполнены; все это преобразуется во входные данные для функции _transact и добавляется имя функции, которая обновляет Atom (swap!).

(defmacro transact [db-conn & txs]  `(_transact ~db-conn swap! ~@txs))

Функция _transact подготавливает вызов функции swap!. Это делается при помощи создания списка, который начинается со swap!, за которым следует информация о коннекторе к базе данных (Atom), затем идет символ transact-on-db и список операций.

(defmacro  _transact [db op & txs]
   (when txs
     (loop [[frst-tx# & rst-tx#] txs  res#  [op db `transact-on-db]  accum-txs# []]
       (if frst-tx#
           (recur rst-tx# res#  (conj  accum-txs#  (vec frst-tx#)))
           (list* (conj res#  accum-txs#))))))

Функция swap! При выполнении транзакции вызывает функцию transact-on-db (с заранее подготовленными аргументами), а функция transact-on-db создает новое состояние базы данных и его возвращает.

На данный момент мы видим, что с помощью небольших ухищрений мы также можем предоставить способ задать вопрос "что, если". Это может быть сделано путем замены функции swap!на функцию, которая не будет делать никаких изменений в системе. Этот сценарий реализуется с помощью цепочки вызовов what-if:

what-if  →  _transact  →  _what-if  →  transact-on-db

Пользователь вызывает функцию what-if со значением базы данных и операциями, которые должны быть выполнены. Затем эти входные данные перенаправлются в функцию _transact — к ним добавляется функция, которая имитирует работу интерфейса API функции swap!, но не выполняет никаких действий (вызывается функция _what-if).

(defmacro what-if [db & ops]  `(_transact ~db _what-if  ~@ops))

Функция _transact подготавливает вызов функции _what-if. Она делает это путем создания списка, который начинается с функции _what-if, затем в нем следует база данных, затем - символ transact-on-db и последовательность операций. Функция _what-if вызывает функцию transact-on-db, которая точно также, как функция swap!, реализует сценарий транзакции, но не изменяет состояние системы.

(defn- _what-if [db f txs]  (f db txs))

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

Описанный выше процесс можно рассмотреть на следующих примерах.

Для того, чтобы выполнить транзакцию, пользователь вызывает:

(transact db-conn  (add-entity e1) (update-entity e2 atr2 val2 :db/add))

Происходят изменения: 

(_transact db-conn swap! (add-entity e1) (update-entity e2 atr2 val2 :db/add))

а затем все это преобразуется в:

(swap! db-conn transact-on-db [[add-entity e1][update-entity e2 atr2 val2 :db/add]])

Чтобы использовать функцию what-if , пользователь вызывает:

(what-if my-db (add-entity e3) (remove-entity e4))

Происходят изменения: 

(_transact my-db _what-if (add-entity e3) (remove-entity e4))

затем:

(_what-if my-db transact-on-db [[add-entity e3] [remove-entity e4]])

и, в конечном итоге:

(transact-on-db my-db  [[add-entity e3] [remove-entity e4]])

Продолжение статьи смотрите здесь