Синхронизация данных дерева Меркле Ложные срабатывания
Деревья Меркле (или хеш-деревья) используются для синхронизации данных как в "Кассандре", так и в "Динамо".
Как и для любой хеш-функции, существует вероятность того, что разные данные могут иметь одинаковое хеш-значение:
Существуют x и y, где [y!= X], но [hash(x) = hash(y)]
По мере роста "больших данных" в NOSQL вероятность обнаружения таких данных становится выше.
Это означает, что по мере того, как наборы данных становятся больше, почти наверняка, что разные узлы в дереве Меркле будут давать один и тот же родительский хеш.
В таком случае, когда две разные машины в кластере пересекают свои деревья Merkle, они получат ложное срабатывание, что их данные непротиворечивы. Если в эту ветвь дерева не будет записано больше данных, машины останутся несинхронизированными навсегда.
Как это обрабатывается?
1 ответ
Большинство систем не справляются с этим. Зачем? Потому что вероятность наличия двух разных входных данных, имеющих одинаковое хеш-значение, очень и очень мала. С хорошей хэш-функцией (которую, я думаю, вы используете), это должно приблизиться к 1/2^{hash-bits}. А поскольку большинство хэшей для этих целей имеют длину не менее 128 бит, вы получаете вероятность 1/2^128 такого коллизии. Что составляет около 2,9387359e-39 (0.{38 нулей}29387359).
Использование 160-битного хэша (который используется в большинстве этих систем, хэши SHA-1) достаточно для того, чтобы в вашей базе данных было столько объектов, сколько песчинок в мире. То, что у вас все еще меньше 1/2 вероятности такого столкновения. Таким образом, я не буду беспокоиться о случае, когда происходит столкновение. Вероятность этого действительно слишком мала.