search

earthstar-project / willowprotocol.org

The Willow Protocol website.
https://willowprotocol.org
23 stars 2 forks source link

Change sorting order in WGPS #88

Closed AljoschaMeyer closed 2 months ago

AljoschaMeyer commented 3 months ago

In the WGPS, the will_sort field of the ReconciliationAnnounceEntries currently uses ordering by the newer relation on entries.

This is unsound, since two entries at different path/subspaces can have identical timestamps, digests and payload lengths.

Even if this was sound, that relation is not a good choice for many storage architectures: it is natural to model willow data as a mapping from SubspaceId-Path pairs to entry data, and such a mapping is not sorted by timestamp.

Suggested solution: make the will_sort field refer to ordering by SubspaceId, with Path as a tiebreaker.

AljoschaMeyer commented 3 months ago

CC @sgwilym @frando

AljoschaMeyer commented 2 months ago

@sgwilym @Frando I fixed this and pushed to the web version. https://willowprotocol.org/specs/sync/index.html#ReconciliationAnnounceEntriesWillSort