Wyjaśnij drzewka Merkle do użycia w ostatecznej spójności

Drzewa Merkle są używane jako mechanizm antyentropii w kilku rozproszonych, replikowanych magazynach klucza / wartości:

• Dynamo
• Riak
• Cassandra

Bez wątpienia mechanizm antyentropii jest Dobrą Rzeczą - w produkcji po prostu zdarzają się przejściowe awarie. Nie jestem tylko pewien, czy rozumiem, dlaczego drzewa Merkle są popularnym podejściem.

• Wysłanie pełnego drzewa Merkle do peera obejmuje wysłanie lokalnej przestrzeni kluczy do tego peera wraz z hashami każdej wartości klucza, przechowywanymi na najniższych poziomach drzewa.

• Odróżnianie drzewka Merkle wysłanego od rówieśnika wymaga posiadania własnego drzewka Merkle.

Skoro obaj rówieśnicy muszą już mieć pod ręką posortowane miejsce na hash klucza / wartości, dlaczego nie wykonać scalenia liniowego w celu wykrycia rozbieżności?

Po prostu nie jestem przekonany, że struktura drzewa zapewnia jakiekolwiek oszczędności, jeśli weźmie się pod uwagę koszty utrzymania, a fakt, że liniowe przejścia nad liśćmi drzewa są już wykonywane tylko po to, aby serializować reprezentację przez drut .

Aby to uziemić, alternatywą może być wymiana węzłów macierzy trawienia hash, które są przyrostowo aktualizowane i grupowane według pozycji pierścienia modulo.

czego mi brakuje?

Drzewa Merkle ograniczają ilość danych przesyłanych podczas synchronizacji. Ogólne założenia są następujące:

1. Sieciowe operacje we / wy są droższe niż lokalne operacje we / wy + obliczanie skrótów.
2. Przeniesienie całej posortowanej przestrzeni kluczy jest droższe niż stopniowe ograniczanie porównania w kilku krokach.
3. Kluczowe przestrzenie mają mniej rozbieżności niż podobieństw.

Wymiana drzewa Merkle wyglądałaby tak:

1. Zacznij od korzenia drzewa (lista zawierająca jedną wartość skrótu).
2. Źródło wysyła listę skrótów na bieżącym poziomie.
3. Miejsce docelowe porównuje listę skrótów ze swoimi własnymi, a następnie żąda różnych poddrzew. Jeśli nie ma różnic, żądanie może zostać zakończone.
4. Powtarzaj kroki 2 i 3, aż do osiągnięcia węzłów liści.
5. Źródło wysyła wartości kluczy w wynikowym zestawie.

W typowym przypadku złożoność synchronizacji przestrzeni kluczy będzie wynosić log (N). Tak, w skrajnym przypadku, gdy nie ma wspólnych kluczy, operacja będzie równoznaczna z wysłaniem całej posortowanej listy skrótów O (N). Koszt budowy drzew Merkle można zamortyzować, budując je dynamicznie w miarę napływania zapisów i zachowując serializowaną formę na dysku.

Nie mogę mówić o tym, jak Dynamo lub Cassandra używają drzew Merkle, ale Riak przestał ich używać do synchronizacji wewnątrz klastra (w większości przypadków wystarczające jest wskazanie przekazywania i naprawy odczytu). Planujemy dodać je później, po zmianie niektórych elementów architektury wewnętrznej.

Aby uzyskać więcej informacji o Riak, zachęcamy do dołączenia do listy mailingowej: http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com