Re: [Tarantool-patches] [PATCH vshard 6/7] router: make discovery smoother in a big cluster

[Konstantin Osipov <kostja.osipov@gmail.com>]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [20/05/08 22:57]:

Here's a good description of how a merkle tree can be used:

https://docs.datastax.com/en/ddac/doc/datastax_enterprise/dbArch/archAntiEntropyRepair.html

With a merkle tree, you will only need to transfer the tree itself
and then the ranges which have actually changed.

> On 08/05/2020 00:45, Konstantin Osipov wrote:
> > * Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [20/05/01 22:16]:
> > 
> > Why not use merkle trees to only fetch the changed subset?
> 
> This is what I found: https://en.wikipedia.org/wiki/Merkle_tree
> "Every leaf node is labelled with the cryptographic hash of a data
> block, and every non-leaf node is labelled with the cryptographic
> hash in the labels of its child nodes. They can help ensure that
> data blocks received from other peers in a peer-to-peer network
> are received undamaged and unaltered, and even to check that the
> other peers do not lie and send fake blocks."
> 
> Correct me if I found something wrong.
> 
> Firstly, hashes has nothing to do with that. Discovery fetches
> bucket ids (in ranges, usually). And I still need to fetch bucket
> ids. It can't dehash a value, received from the storage, into a
> range of buckets.
> 
> Secondly, storage does not depend on router and can't keep a state
> of every router on it. If you meant, that the storage should keep
> something on it.
> 
> Thirdly, there is no in-place change, which would mean you just need
> to fetch a new version of a bucket from the same storage. Change means
> the bucket was moved to a different replicaset (in 99.99999% cases).
> Deleted from one, and added on another. So you need to download it from
> the new place.
> 
> Otherwise I probably didn't understand what you meant.

-- 
Konstantin Osipov, Moscow, Russia