Каузальная согласованность на сайте MariaDB

MariaDB - это ветка MySQL. 

У них на сайте нашел неплохую статью про каузальную согласованность (causal consistency). 

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

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

Кроме того, две записи, выполненные одним узлом, будут связаны. Ведь записав значение v в объект x узел будет знать, что чтение x даст v, поэтому более поздняя запись будет (потенциально) зависеть от более раннего.

  

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

Векторные часы описываются так. Каждый узел хранит вектор длины N , где N - число узлов.

Элемент с номером i содержит число, равное количеству сообщений, принятых с i-го хоста (хмм, по-моему, это расходится с классическим определением). Использование часов позволяет упорядочивать сообщения или откладывать прием сообщений.

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

В качестве приложений рассматриваются MMORPG и Facebook - но это как-нибудь потом.