Многое в этом заключается в том, чтобы найти ваши точные требования, а ваши все еще звучат довольно расплывчато. Вам просто нужно поддерживать такие операции?
- Обновить ключ K до значения V.
- Посмотрите на недавнее значение ключа K.
Вы упомянули, что вам нужна возможная последовательность. Так что, если вы сделаете одно обновление, оно в конечном итоге будет повторяться везде. Если вы делаете два почти одновременных обновления, вас волнует, какое из них выиграет? Если одна реплика сообщает, что обновление было успешно завершено, вас волнует, может ли значение быть потеряно, если вскоре после этого реплика временно потерпит крах? Или, если эта копия была навсегда уничтожена?
Насколько точным должно быть несколько недавнее? Если есть netsplit или что-то еще, поиск может вернуть очень устаревший результат или просто потерпит неудачу. Вас это волнует?
Вам когда-нибудь нужно поддерживать более сложные операции, такие как ...
- Получить абсолютное последнее значение ключа K?
- Обновить значение ключа K до значения V ', если последнее значение в данный момент равно V?
Есть ли у вас жесткие требования к надежности, задержке и / или пропускной способности? Как далеко друг от друга находятся ваши реплики / насколько хороша сеть? Это влияет, если вы можете иметь связь между репликами при каждом обновлении и даже при каждом поиске; или даже если вы можете / должны переключать операции на удаленную реплику, если локальная не работает.
В зависимости от ваших ответов, я работал с несколькими различными схемами, которые могут соответствовать вашим требованиям. Есть несколько возможных вариаций на них.
- Самое простое, чтобы приложение всегда общалось с локальной репликой. Реплицируйте значения меток времени (используя синхронизированные по NTP часы) и общайтесь друг с другом только для асинхронной репликации. Самая высокая отметка времени побеждает в репликации. Конечно, если приложения на двух разных репликах выполняют чтение / изменение / запись почти одновременно, одна из модификаций может быть легко потеряна. (На самом деле, без схемы условного обновления то же самое справедливо даже для почти одновременных изменений в одной и той же реплике.) Если реплика постоянно терпит неудачу, недавние обновления могут быть потеряны. Это более или менее то, что делает встроенная репликация Bigtable. В статье, на которую вы ссылаетесь, это будет ветвь «Оптимистичный - Мультимастер», но если не заботиться о потере некоторых обновлений, это будет проще, чем они предлагают.
- В некоторых базах данных используется алгоритм Paxos (см., Например, «Управление данными для единого входа в масштабе Интернета» здесь , чтобы сделать более интересные вещи возможными. Каждая реплика может знать, насколько далеко позади это может быть так Вы можете сказать «дайте мне значение, которое не старше 1 минуты» или «дайте мне абсолютное последнее значение». Обновление не считается завершенным до тех пор, пока кворум реплик его не примет, поэтому «дайте мне абсолютное последнее значение» "определенно всегда будет возвращать это значение до тех пор, пока не произойдет другое обновление. Вы можете выполнить операцию условного обновления, о которой я упоминал, чтобы не допустить одновременной записи друг друга. Это, похоже, не вписывается ни в оптимистическую, ни в пессимистическую категорию, как определено этим автором потому что обновления реплицируются синхронно в кворум, но реплики, которые не голосовали в последнем раунде Paxos, все еще могут отвечать на некоторые запросы. Хотя схема может быть очень сложной ...