Amazon Dynamo: синхронизация антиэнтропийных реплик с использованием деревьев Меркель - PullRequest
0 голосов
/ 27 февраля 2020

Контекст: Я пытаюсь реализовать синхронизацию реплик Amazon Dynamo, которая использует деревья Меркель для обнаружения расхождений между репликами.

Как упомянуто в веб-версии статьи здесь ,

Динамо использует деревья Меркле для антиэнтропии следующим образом: каждый узел поддерживает отдельное дерево Меркле для каждого диапазона ключей (набора ключей, охватываемых виртуальным узлом) он размещается. Это позволяет узлам сравнивать, являются ли ключи в диапазоне ключей современными. В этой схеме два узла обмениваются root дерева Меркле, соответствующего диапазонам ключей, которые они размещают совместно. Впоследствии, используя схему обхода дерева, описанную выше, узлы определяют, есть ли у них какие-либо различия, и выполняют соответствующее действие синхронизации.

Я не понимаю, что означает " соответствующее действие синхронизации ". Используя соответствующий обход, предположим, что мы обнаружили несоответствие между двумя узлами дерева Меркель root - как мы узнаем, какой из них правильный? Всегда ли мы выбираем более обновленный в соответствии с его логической отметкой времени?

1 Ответ

0 голосов
/ 27 февраля 2020

Документ Dynamo, который вы связали (обратите внимание, что это , а не такой же, как сегодняшний продукт DynamoDB, поэтому я удалил тег DynamodB, который вы добавили в свой вопрос), объясняет, как происходит согласование между двумя версиями готово, используя векторные часы (которые не так просты, как «отметка времени»):

Динамо использует векторные часы для захвата причинно-следственных связей между различными версиями одного и того же объекта. Векторные часы фактически представляют собой список пар (узел, счетчик). Один вектор часов связан с каждой версией каждого объекта. Можно определить, находятся ли две версии объекта на параллельных ветвях или имеют причинное упорядочение, изучив их векторные часы. Если счетчики на часах первого объекта меньше или равны всем узлам на вторых часах, то первый является предком второго и может быть забыт. В противном случае два изменения считаются конфликтующими и требуют согласования.

Другими словами, обычно «Динамо» может определить, какое значение является более новым, на основе векторных часов (в документе поясняется, что это означает подробно), но также возможно, что существует конфликт - представьте, что один и тот же элемент был прочитан и изменен одновременно и по-разному двумя разными и не связанными друг с другом репликами. В этом случае обе версии данных будут сохранены в базе данных и возвращены клиенту, и клиенту необходимо будет согласовать их, используя определенные клиентом c logi c. Например, в примере корзины покупок Amazon, если одной из модификаций было добавление продукта A в корзину покупок, а второй модификацией - добавление продукта B в корзину покупок, выверка будет включать добавление обоих продуктов - A и B - к корзина.

...