Doug Hoyte on Nostr: Hi all! I have just pushed a major update to the negentropy project. It implements ...
Hi all! I have just pushed a major update to the negentropy project. It implements protocol version 1 (previous was version 0).
The protocol has been simplified: ID size is no longer configurable, there are no more continuation ranges, and the output can be constructed in the same input-scan pass.
There is a new fingerprint function, based on an incremental hash. This allows fingerprints to be pre-computed and stored in a tree structure. The C++ implementation includes a B+Tree implementation that allows fingerprints to be computed without collecting IDs from the entire DB.
I have written a comprehensive article that goes over the theory of RBSR and the negentropy implementation:
https://logperiodic.com/rbsr.htmlComments are appreciated!
Finally, I have integrated the new version of negentropy and the B+Tree with strfry. It's in a development branch and not quite ready for production, but my testing indicates this will be a massive improvement for full-DB syncs, especially on relays with very large DBs. In-sync or nearly in-sync relays should sync almost instantly with negligible resource usage. Relays will also use the B+Tree for filters that contain only until and/or since, meaning that date-range full-DB syncs are also efficient. Syncing arbitrary filters works as before (but I have begun work to make these more efficient as well).
Unfortunately, this is a breaking change for the negentropy protocol (this really should be the last one!) and will also require a new DB version.
I'm going to take this opportunity to make a few more breaking DB changes, and plan to release strfry 1.0 after a beta testing period.
Published at
2023-12-07 05:05:27Event JSON
{
"id": "4e89b8e124924424eaa97e9fd47f0c14d5b1c742aa2accd321571dabead8e617",
"pubkey": "218238431393959d6c8617a3bd899303a96609b44a644e973891038a7de8622d",
"created_at": 1701925527,
"kind": 1,
"tags": [
[
"t",
"oddbean"
],
[
"client",
"oddbean"
]
],
"content": "\nHi all! I have just pushed a major update to the negentropy project. It implements protocol version 1 (previous was version 0).\n\nThe protocol has been simplified: ID size is no longer configurable, there are no more continuation ranges, and the output can be constructed in the same input-scan pass.\n\nThere is a new fingerprint function, based on an incremental hash. This allows fingerprints to be pre-computed and stored in a tree structure. The C++ implementation includes a B+Tree implementation that allows fingerprints to be computed without collecting IDs from the entire DB.\n\nI have written a comprehensive article that goes over the theory of RBSR and the negentropy implementation:\n\nhttps://logperiodic.com/rbsr.html\n\nComments are appreciated!\n\nFinally, I have integrated the new version of negentropy and the B+Tree with strfry. It's in a development branch and not quite ready for production, but my testing indicates this will be a massive improvement for full-DB syncs, especially on relays with very large DBs. In-sync or nearly in-sync relays should sync almost instantly with negligible resource usage. Relays will also use the B+Tree for filters that contain only until and/or since, meaning that date-range full-DB syncs are also efficient. Syncing arbitrary filters works as before (but I have begun work to make these more efficient as well).\n\nUnfortunately, this is a breaking change for the negentropy protocol (this really should be the last one!) and will also require a new DB version.\n\nI'm going to take this opportunity to make a few more breaking DB changes, and plan to release strfry 1.0 after a beta testing period.",
"sig": "5dee41f6f5c8618bfc6d27c2bc86b4a3fe87edd81b15c65e3c48476c6996650bece5987a12da764d021fb7db7091ebfc2fb576a0367fc6060b55daeeb264da96"
}