[bisq-network/bisq] [WIP] Use keyset delta algorithm to speed up GetData requests (#3896)

[Steven Barclay]

The bandwidth requirements are not really O(ln(N)) in the keyset size - its more or less proportional to the size of the symmetric difference of the keysets, that is the number of keys the seed node has that the peer doesn't (in the case that the peer doesn't somehow have any keys unknown to the seed node).

So as the datasets grow, the request shouldn't really grow in size. But if the peer has been offline for a while, the initial request will fail due to the difference in the keysets being too large for the initial default delta datastructure to handle. In that case, it will retry with a larger request datastructure that's highly likely to be able to accommodate the difference. So I think that's the main cost with this method - there's no guarantee the initial request to the seed nodes will succeed, which adds some extra delay to the startup of nodes that have been offline for a while (say for months, or maybe days/weeks in future if Bisq does 10x).

Perhaps its better to think of the algorithm to be like that of rsync rather than Bloom filters. (It doesn't use a rolling hash, but like rsync it uses linear coding to detect and locate differences between two datasets.)

Is it worth picking this up again soon to complement the approach taken in https://github.com/bisq-network/projects/issues/25, or leaving it a while perhaps?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/bisq-network/bisq/pull/3896#issuecomment-608971561
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-github/attachments/20200403/7df787b3/attachment.html>