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

Mon Jan 13 07:21:57 UTC 2020

<!-- 
- make yourself familiar with the CONTRIBUTING.md if you have not already (https://github.com/bisq-network/bisq/blob/master/CONTRIBUTING.md)
- make sure you follow our [coding style guidelines][https://github.com/bisq-network/style/issues)
- pick a descriptive title
- provide some meaningful PR description below
- create the PR
- in case you receive a "Change request" and/or a NACK, please react within 30 days. If not, we will close your PR and it can not be up for compensation.
- After addressing the change request, __please re-request a review!__ Otherwise we might miss your PR as we tend to only look at pull requests tagged with a "review required".
-->

When Bisq starts it sends simultaneous `PreliminaryGetDataRequest` packets to two seed nodes to sync the latest trade statistics, offer book, mailbox and other data, followed by a later `GetUpdatedDataRequest` packet. The requests contain a list of keys of all the data to exclude (as we already have it) and are consequently about 2MB each. The responses to the first two `GetData` requests are typically around 3MB, it seems, usually consisting mostly of offer and mailbox items (as those are not persisted and have high turnover anyway).

Thus there is typically about 10MB (in total) being sent/received in the preliminary `GetData` requests/responses to/from the seed nodes. On slow networks, this appears to frequently result in timeouts and difficulty starting up the application, as the 3MB response arrives after the 90s timeout window and gets rejected.

In an attempt to alleviate the problem, this PR replaces the `excluded_keys` list in the `GetData` requests with a delta structure (that is a sort of binary checksum/linear code syndrome), which is XORed with a version computed equivalently at the receiving node, to obtain a decodable list of keys. This is the symmetric difference of the two sets of keys at each node, which tells the responding node which keys are missing from the peer.

The delta is decodable provided the symmetric difference isn't too large compared to the physical delta size (powers-of-two from 8KB to 128KB). With the data structure I used, an 8KB delta can reliably decode up to 550 keys and a 128KB delta can reliably decode up to 10450 keys. Since this holds true only when the keys are randomised, they are all hashed to a fixed 64-bit width using a randomly seeded secure PRF (in this case SipHash) - 64 bits is enough to ensure a very low probability of collision per request and deliberately causing collisions is impossible since the random seed/hash-salt is an ephemeral shared secret.

In case decoding fails, the responding peer estimates the size of the undecodable delta and sends that information back, so that the requesting peer can retry with a delta structure big enough to accommodate the expected symmetric difference. The keys can also be restricted to an arbitrary range of 64-bit values, which effectively filters out items out at random, ensuring that the symmetric difference will be reliably decoded in the next request. The code will keep retrying until it gets everything.

The above requires new fields to be added to the `PreliminaryGetDataRequest`, `GetUpdatedDataRequest` and `GetDataResponse` proto definitions. I've tried to do this in a way which is backwards compatible by adding a provisional `GET_DATA_KEY_SET_DELTA` capability and only using the new delta structure in requests to peers which flag the capability.

This PR is a draft and still needs some work (e.g. to the unit tests and commit messages). I'm also considering making the following possible further enhancements:

- In the initial requests to the pair of seed nodes, use the range filter to split the keyset in two and send a different half to each pair, so each one only sends back approximately 1.5 MB, cutting the network load in half again. After getting one response, wait a little while (rather than the usual 90s) to get the other response before retrying.

- Now that the requests are cheap, it might make sense to limit the responses to 1MB or less and make repeated requests to sync everything, rather than getting it all in one go. This should make startup more reliable on very slow networks. Also possibly add a corresponding progress bar to the splash screen.

- Optimistically persist/cache the offer book and mailbox entries for faster startup next time, in case the application was only shut down for a few hours or days. Since the response now contains a list of unrecognised keys, any items that don't match can be purged from the cache and the rest promoted to the protected store (as the seed node definitely still has them).

I'm not sure whether it would be best to include the above in this PR or consider them for later PRs.
You can view, comment on, or merge this pull request online at:

  https://github.com/bisq-network/bisq/pull/3896

-- Commit Summary --

  * Temp changes

-- File Changes --

    M common/src/main/java/bisq/common/app/Capability.java (3)
    M common/src/main/proto/pb.proto (12)
    M core/src/main/java/bisq/core/dao/governance/blindvote/network/RepublishGovernanceDataHandler.java (2)
    M core/src/main/java/bisq/core/setup/CoreNetworkCapabilities.java (3)
    M monitor/src/main/java/bisq/monitor/metric/P2PMarketStats.java (2)
    M monitor/src/main/java/bisq/monitor/metric/P2PSeedNodeSnapshot.java (2)
    M p2p/src/main/java/bisq/network/p2p/P2PService.java (2)
    M p2p/src/main/java/bisq/network/p2p/peers/PeerManager.java (8)
    A p2p/src/main/java/bisq/network/p2p/peers/getdata/KeySetDelta.java (284)
    M p2p/src/main/java/bisq/network/p2p/peers/getdata/RequestDataHandler.java (29)
    M p2p/src/main/java/bisq/network/p2p/peers/getdata/RequestDataManager.java (6)
    M p2p/src/main/java/bisq/network/p2p/peers/getdata/messages/GetDataRequest.java (6)
    M p2p/src/main/java/bisq/network/p2p/peers/getdata/messages/GetDataResponse.java (33)
    M p2p/src/main/java/bisq/network/p2p/peers/getdata/messages/GetUpdatedDataRequest.java (13)
    M p2p/src/main/java/bisq/network/p2p/peers/getdata/messages/PreliminaryGetDataRequest.java (13)
    M p2p/src/main/java/bisq/network/p2p/storage/P2PDataStorage.java (147)
    A p2p/src/test/java/bisq/network/p2p/peers/getdata/KeySetDeltaTest.java (131)
    M p2p/src/test/java/bisq/network/p2p/storage/P2PDataStorageBuildGetDataResponseTest.java (4)
    M p2p/src/test/java/bisq/network/p2p/storage/P2PDataStorageGetDataIntegrationTest.java (8)
    M p2p/src/test/java/bisq/network/p2p/storage/P2PDataStorageProcessGetDataResponse.java (4)
    M p2p/src/test/java/bisq/network/p2p/storage/P2PDataStorageRequestDataTest.java (8)

-- Patch Links --

https://github.com/bisq-network/bisq/pull/3896.patch
https://github.com/bisq-network/bisq/pull/3896.diff

-- 
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-github/attachments/20200112/d1795cb7/attachment.html>