From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp37.i.mail.ru (smtp37.i.mail.ru [94.100.177.97]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 7AB8F469710 for ; Fri, 8 May 2020 22:56:53 +0300 (MSK) References: <80bacfc685233ad047f6a80ddadd72b8903eae5b.1588292014.git.v.shpilevoy@tarantool.org> <20200507224535.GA14285@atlas> From: Vladislav Shpilevoy Message-ID: <908c2496-cf78-9286-c175-95046d4195f6@tarantool.org> Date: Fri, 8 May 2020 21:56:48 +0200 MIME-Version: 1.0 In-Reply-To: <20200507224535.GA14285@atlas> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Subject: Re: [Tarantool-patches] [PATCH vshard 6/7] router: make discovery smoother in a big cluster List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Konstantin Osipov , tarantool-patches@dev.tarantool.org, olegrok@tarantool.org On 08/05/2020 00:45, Konstantin Osipov wrote: > * Vladislav Shpilevoy [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.