Модель репликации и конфликтов

Репликация CouchDB

CouchDB работает с документами JSON в базах данных. Репликация баз данных выполняется через HTTP и может быть однонаправленной: «pull» или «push». Поэтому самый простой способ выполнить полную синхронизацию — сначала сделать «push», а затем «pull» (или наоборот).

Итак, Алиса создаёт v1 и синхронизирует её. Она обновляет документ до v2a на одной стороне и до v2b на другой, а затем выполняет репликацию. Что произойдёт?

Ответ прост: обе версии будут существовать с обеих сторон!

DESKTOP                          LAPTOP
+---------+
| /db/bob |                                     INITIAL
|   v1    |                                     CREATION
+---------+

+---------+                      +---------+
| /db/bob |  ----------------->  | /db/bob |     PUSH
|   v1    |                      |   v1    |
+---------+                      +---------+

+---------+                      +---------+  INDEPENDENT
| /db/bob |                      | /db/bob |     LOCAL
|   v2a   |                      |   v2b   |     EDITS
+---------+                      +---------+

+---------+                      +---------+
| /db/bob |  ----------------->  | /db/bob |     PUSH
|   v2a   |                      |   v2a   |
+---------+                      |   v2b   |
                                 +---------+

+---------+                      +---------+
| /db/bob |  <-----------------  | /db/bob |     PULL
|   v2a   |                      |   v2a   |
|   v2b   |                      |   v2b   |
+---------+                      +---------+

В конце концов, это не файловая система, поэтому ничто не запрещает существование нескольких документов с именем /db/bob. Это просто «конфликтующие» редакции с одним и тем же именем.

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

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

Теперь возникает вопрос: что произойдёт при попытке прочитать /db/bob? По умолчанию CouchDB выбирает одну произвольную редакцию в качестве «победившей», используя детерминированный алгоритм, благодаря которому все узлы сделают одинаковый выбор. То же самое происходит с представлениями: в функцию map передаётся только детерминированно выбранная победившая редакция.

Предположим, что победила v2a. На настольном компьютере, прочитав документ, Алиса увидит v2a — ту версию, которую она там сохранила. Но после репликации на ноутбуке она также увидит только v2a. Может показаться, что сделанные там изменения потерялись, но на самом деле это не так: они просто скрыты в виде конфликтующей редакции. Однако со временем эти изменения нужно будет объединить с визитной карточкой Боба, иначе фактически они будут потеряны.

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

Предотвращение конфликтов

При работе с одним узлом CouchDB предотвращает создание конфликтующих редакций, возвращая ошибку 409 Conflict. Это происходит потому, что при отправке PUT-запроса с новой версией документа необходимо указать _rev предыдущей версии. Если эта _rev уже была заменена, обновление отклоняется с ответом 409 Conflict.

Представим, что два пользователя на одном узле одновременно получают визитную карточку Боба, обновляют её и записывают обратно:

USER1    ----------->  GET /db/bob
         <-----------  {"_rev":"1-aaa", ...}

USER2    ----------->  GET /db/bob
         <-----------  {"_rev":"1-aaa", ...}

USER1    ----------->  PUT /db/bob?rev=1-aaa
         <-----------  {"_rev":"2-bbb", ...}

USER2    ----------->  PUT /db/bob?rev=1-aaa
         <-----------  409 Conflict  (not saved)

Изменения пользователя 2 отклоняются, поэтому приложению нужно снова получить /db/bob и либо:

1. применить те же изменения, что были внесены в предыдущую редакцию, и отправить новый PUT-запрос;

2. снова показать документ, чтобы пользователь отредактировал его;

3. просто перезаписать его ранее сохранённым документом (это не рекомендуется, поскольку изменения пользователя 1 будут незаметно потеряны).

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

Дерево редакций

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

,--> r2a
r1 --> r2b
  `--> r2c

Затем история каждой ветви может продолжаться — например, если прочитать редакцию r2b, а затем выполнить PUT с ?rev=r2b, новая редакция появится именно в этой ветви.

,--> r2a -> r3a -> r4a
r1 --> r2b -> r3b
  `--> r2c -> r3c

В этом примере (r4a, r3b, r3c) — набор конфликтующих редакций. Чтобы разрешить конфликт, нужно удалить конечные узлы остальных ветвей. Поэтому при объединении (r4a+r3b+r3c) в один документ слияния вы замените r4a и удалите r3b и r3c.

,--> r2a -> r3a -> r4a -> r5a
r1 --> r2b -> r3b -> (r4b deleted)
  `--> r2c -> r3c -> (r4c deleted)

Обратите внимание, что r4b и r4c по-прежнему существуют как конечные узлы дерева истории, но в виде удалённых документов. Их можно получить, но они будут помечены как "_deleted":true.

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

Работа с конфликтующими документами

Базовая операция GET /{db}/{docid} не показывает информацию о конфликтах. Вы видите только детерминированно выбранную победившую редакцию и не получаете сведений о том, существуют ли другие конфликтующие редакции:

{
    "_id":"test",
    "_rev":"2-b91bb807b4685080c6a651115ff558f5",
    "hello":"bar"
}

Если выполнить GET /db/test?conflicts=true, а документ находится в состоянии конфликта, вы получите победившую редакцию и член _conflicts, содержащий массив идентификаторов других конфликтующих редакций. Затем каждую из них можно получить отдельно с помощью последующих операций GET /db/test?rev=xxxx:

{
    "_id":"test",
    "_rev":"2-b91bb807b4685080c6a651115ff558f5",
    "hello":"bar",
    "_conflicts":[
        "2-65db2a11b5172bf928e3bcf59f728970",
        "2-5bc3c6319edf62d4c624277fdd0ae191"
    ]
}

Если выполнить GET /db/test?open_revs=all, вы получите все конечные узлы дерева редакций. Это позволит увидеть все текущие конфликты, а также конечные узлы, которые были удалены (то есть части истории конфликтов, которые уже разрешены). Их можно исключить, отфильтровав документы с "_deleted":true:

[
    {"ok":{"_id":"test","_rev":"2-5bc3c6319edf62d4c624277fdd0ae191","hello":"foo"}},
    {"ok":{"_id":"test","_rev":"2-65db2a11b5172bf928e3bcf59f728970","hello":"baz"}},
    {"ok":{"_id":"test","_rev":"2-b91bb807b4685080c6a651115ff558f5","hello":"bar"}}
]

Тег "ok" — это артефакт open_revs, который также позволяет перечислять конкретные редакции в виде массива JSON, например open_revs=[rev1,rev2,rev3]. В таком виде можно запросить редакцию, которая уже отсутствует, поскольку база данных была уплотнена.

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

Как описано выше, нужно обновить одну редакцию и явно удалить все конфликтующие редакции. Это можно сделать одним запросом POST к _bulk_docs, задав "_deleted":true для редакций, которые нужно удалить.

API для нескольких документов

$ curl -X POST http://adm:pass@127.0.0.1:5984/dbname/_find \
    -d '{"selector": {"_conflicts": { "$exists": true}}, "conflicts": true}' \
    -Hcontent-type:application/json

{"docs": [
{"_id":"doc","_rev":"1-3975759ccff3842adf690a5c10caee42","a":2,"_conflicts":["1-23202479633c2b380f79507a776743d5"]}
],
"bookmark": "g1AAAABheJzLYWBgYMpgSmHgKy5JLCrJTq2MT8lPzkzJBYozA1kgKQ6YVA5QkBFMgKSVDHWNjI0MjEzMLc2MjZONkowtDNLMLU0NzBPNzc3MTYxTTLOysgCY2ReV"}

$ curl -X POST http://adm:pass@127.0.0.1:5984/dbname/_index \
    -d '{"index":{"fields": ["_conflicts"]}}' \
    -Hcontent-type:application/json

$ curl 'http://adm:pass@127.0.0.1:5984/conflict_test/_all_docs?include_docs=true&conflicts=true'

{
    "total_rows":1,
    "offset":0,
    "rows":[
        {
            "id":"test",
            "key":"test",
            "value":{"rev":"2-b91bb807b4685080c6a651115ff558f5"},
            "doc":{
                "_id":"test",
                "_rev":"2-b91bb807b4685080c6a651115ff558f5",
                "hello":"bar"
            }
        }
    ]
}

$ curl 'http://adm:pass@127.0.0.1:5984/conflict_test/test?conflicts=true'

{
    "_id":"test",
    "_rev":"2-b91bb807b4685080c6a651115ff558f5",
    "hello":"bar",
    "_conflicts":[
        "2-65db2a11b5172bf928e3bcf59f728970",
        "2-5bc3c6319edf62d4c624277fdd0ae191"
    ]
}

Функции map представлений

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

function(doc) {
    if (doc._conflicts) {
        emit(null, [doc._rev].concat(doc._conflicts));
    }
}

и возвращает следующий результат:

{
    "total_rows":1,
    "offset":0,
    "rows":[
        {
            "id":"test",
            "key":null,
            "value":[
                "2-b91bb807b4685080c6a651115ff558f5",
                "2-65db2a11b5172bf928e3bcf59f728970",
                "2-5bc3c6319edf62d4c624277fdd0ae191"
            ]
        }
    ]
}

В этом случае можно создать отдельный процесс «проверки», который будет периодически сканировать базу данных, искать документы с конфликтами, получать конфликтующие редакции и разрешать конфликты.

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

Кроме того, можно забыть запустить этот процесс или реализовать его неправильно, что приведёт к странному поведению, которое будет сложно отследить.

Алгоритм выбора «победившей» редакции в CouchDB может привести к тому, что информация исчезнет из представления до разрешения конфликта. Снова рассмотрим визитную карточку Боба: предположим, что у Алисы есть представление, которое возвращает номера мобильных телефонов, чтобы её приложение телефонии могло отображать имя звонящего по идентификатору вызывающего абонента. Если существуют конфликтующие документы со старым и новым номерами мобильного телефона Боба, и конфликт разрешается в пользу старого номера, представление не сможет распознать новый номер. В этом случае приложению, возможно, было бы полезнее добавить в представление информацию из обоих конфликтующих документов, но сейчас это невозможно.

Предлагаемый алгоритм получения документа с разрешением конфликтов:

1. Получить документ с помощью запроса GET docid?conflicts=true.

2. Для каждого элемента массива _conflicts вызвать GET docid?rev=xxx. Если на этом этапе возникнет ошибка, начать заново с шага 1. (Возможно состояние гонки: кто-то уже разрешил этот конфликт и удалил эту редакцию.)

3. Выполнить слияние с учётом логики приложения.

4. Записать _bulk_docs, обновив первую редакцию и удалив остальные.

Это можно делать при каждом чтении (в таком случае все вызовы GET в приложении можно заменить вызовами библиотеки, выполняющей описанные действия) или включить в код процесса проверки.

Вот пример на Ruby с использованием низкоуровневого клиента RestClient:

require "rubygems"
require "rest_client"
require "json"

DB = "http://adm:pass@127.0.0.1:5984/db"

# Write multiple documents
def writem(docs, new_edits)
  JSON.parse(
    RestClient.post(
      "#{DB}/_bulk_docs",
      {:docs => docs, :new_edits => new_edits}.to_json,
      {content_type: :json, accept: :json}
    )
  )
end

# Write one document, return the rev
def write1(doc, id = nil, rev = nil)
  doc["_id"] = id if id
  doc["_rev"] = rev if rev

  if rev
    writem([doc], false)
  else
    writem([doc], true).first["rev"]
  end
end

# Read a document, return *all* revs
def read1(id)
  retries = 0
  loop do
    # FIXME: escape id
    res = [JSON.parse(RestClient.get("#{DB}/#{id}?conflicts=true"))]

    if revs = res.first.delete("_conflicts")
      begin
        revs.each do |rev|
          res << JSON.parse(RestClient.get("#{DB}/#{id}?rev=#{rev}"))
        end

      rescue
        retries += 1
        raise if retries >= 5
        next
      end
    end

    return res
  end
end

# Create DB
RestClient.delete(DB) rescue nil
RestClient.put(DB, {}.to_json)

# Write a document
rev1 = write1({"hello" => "xxx"}, "test")
p(read1("test"))

# Make three conflicting versions
(1..3).each do |num|
  write1({"hello" => "foo"}, "test", rev1 + num.to_s)
  write1({"hello" => "bar"}, "test", rev1 + num.to_s)
  write1({"hello" => "baz"}, "test", rev1 + num.to_s)
end

res = read1("test")
p(res)

# Now let's replace these three with one
res.first["hello"] = "foo+bar+baz"
res.each_with_index do |r, i|
  unless i == 0
    r.replace({"_id" => r["_id"], "_rev" => r["_rev"], "_deleted" => true})
  end
end

writem(res, true)
p(read1("test"))

Приложению, написанному таким образом, никогда не придётся обрабатывать PUT 409, и оно автоматически сможет работать в режиме «мультимастер».

Как видите, если знать, что делать, всё достаточно просто. Просто в CouchDB пока нет удобного HTTP API для «получения всех конфликтующих редакций» или «выполнения PUT-запроса для замены этих N редакций», поэтому такую функциональность нужно реализовать самостоятельно. На момент написания этого текста неизвестно о клиентских библиотеках, поддерживающих эту функциональность.

Слияние и история редакций

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

Некоторые стратегии слияния учитывают изменения объекта по сравнению с предыдущей версией. Так работает функция слияния в Git.

Например, чтобы объединить версии визитной карточки Боба v2a и v2b, можно сравнить v1 и v2b, а затем применить эти изменения и к v2a.

В CouchDB иногда можно получить старые редакции документа. Например, если получить /db/bob?rev=v2b&revs_info=true, вы увидите список идентификаторов предыдущих редакций, которые привели к редакции v2b. Сделав то же самое для v2a, можно найти их общего предка. Однако если база данных была уплотнена, содержимое этой редакции документа будет потеряно. revs_info всё ещё покажет, что v1 была предком, но отметит её как «отсутствующую»:

BEFORE COMPACTION           AFTER COMPACTION

     ,-> v2a                     v2a
   v1
     `-> v2b                     v2b

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

Сравнение с другими реплицируемыми хранилищами данных

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

main               -- my local branch
remotes/foo/main   -- branch on peer 'foo'
remotes/bar/main   -- branch on peer 'bar'

---------- desktop ----------           ---------- laptop ----------
main: AAAAAAAA                        main: AAAAAAAA
remotes/laptop/main: AAAAAAAA         remotes/desktop/main: AAAAAAAA

---------- desktop ----------           ---------- laptop ----------
main: BBBBBBBB                        main: CCCCCCCC
remotes/laptop/main: AAAAAAAA         remotes/desktop/main: AAAAAAAA

---------- desktop ----------           ---------- laptop ----------
main: BBBBBBBB                        main: CCCCCCCC
remotes/laptop/main: CCCCCCCC         remotes/desktop/main: AAAAAAAA

---------- desktop ----------           ---------- laptop ----------
main: DDDDDDDD                        main: CCCCCCCC
remotes/laptop/main: CCCCCCCC         remotes/desktop/main: AAAAAAAA

---------- desktop ----------           ---------- laptop ----------
main: DDDDDDDD                        main: CCCCCCCC
remotes/laptop/main: CCCCCCCC         remotes/desktop/main: DDDDDDDD

---------- desktop ----------           ---------- laptop ----------
main: DDDDDDDD                        main: DDDDDDDD
remotes/laptop/main: CCCCCCCC         remotes/desktop/main: DDDDDDDD

main: AAAAAAAA
remotes/foo/main: BBBBBBBB
remotes/bar/main: CCCCCCCC
remotes/baz/main: AAAAAAAA