Синхронизация данных дерева Меркле Ложные срабатывания

Деревья Merkle (также известные как хеш-деревья) используются для синхронизации данных как в «Cassandra», так и в amp; "Динамо".

Как и в случае с любой хеш-функцией, существует вероятность того, что разные данные могут иметь одно и то же хеш-значение:

Существуют x и y, где [y! = x], но [hash (x) = hash (y)]

По мере роста «больших данных» в NOSQL вероятность появления таких данных возрастает.

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

В таком случае, когда две разные машины в кластере пересекают свои деревья Merkle, они получат ложное срабатывание, что их данные непротиворечивы. Если в эту ветвь дерева не будет записано больше данных, машины останутся несинхронизированными навсегда.

Как это обрабатывается?

7 голосов | спросил eshalev 7 Jpm1000000pmMon, 07 Jan 2013 17:38:34 +040013 2013, 17:38:34

1 ответ


0

Большинство систем не справляются с этим. Зачем? Потому что вероятность наличия двух разных входов с одинаковым значением хеш-функции очень и очень мала. С хорошей хэш-функцией (которую, я думаю, вы используете) это должно приблизиться к 1/2 ^ {hash-bits}. А поскольку большинство хэшей для этих целей имеют длину не менее 128 бит, вы получаете вероятность 1/2 ^ 128 такого коллизии. Что составляет около 2,9387359e-39 (0. {38 нулей} 29387359).

Использование 160-битного хэша (который в большинстве этих систем используют хэши SHA-1) достаточно для того, чтобы в вашей базе данных было столько объектов, сколько песчинок в мире. То, что у вас все еще меньше 1/2 вероятности такого столкновения. Таким образом, я не буду беспокоиться о случае, когда происходит столкновение. Вероятность того, что это произойдет, действительно слишком мала.

ответил kokx 7 Jpm1000000pmMon, 07 Jan 2013 18:01:16 +040013 2013, 18:01:16

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132