Может ли кто-нибудь объяснить мне, как реализация дерева merkle работает в riak-core, пожалуйста?Riak, merckle tree, реализация
https://github.com/basho/riak_core/blob/develop/src/merkerl.erl
Я не понимаю, что это offfset, например.
Спасибо!
Дерево является деревом поиска K/V и деревом Merkle в одном, более или менее. Дерево определено, глядя на 160 бит sha1. 160 бит дает 20 байтов. На первом уровне дерева мы сохраняем до 256 поддеревьев в соответствии с 0-м байтом хэша. На следующем уровне это 1-й байт, затем 2-й и так далее.
Это называется цифровой древовидной схемой, где цифры в хеше кодируют путь к дереву. Это позволяет нам заменять данные в дереве. Альтернативно, взгляните на концепцию trie. В то же время мы подписываем каждый узел с помощью sha1 для отслеживания изменений в данном поддереве. При запуске для поиска diff мы можем игнорировать поддеревья с той же подписью, которые должны быть эквивалентны по построению.
Значение offset кодирует, как далеко в 160-битном ключе мы находимся сейчас. Функция offset_key/1 смещает правый байт в ключ, чтобы посмотреть.
И кажется, что высота дерева ограничена 20 (ключ - двоичный код 160b). Это правда? – andreych
Адрес, кажется, недействителен. –
Код теперь находится по адресу https://github.com/basho/riak_core/blob/1.4/src/merkerl.erl. Филиал 'develop' теперь настроен для разработки Riak 2.0. –