Distributed Data Structures — Internals
Deep-dive page: how sets, lists and trees work as replicated objects on a DHT, and what the current source actually contains.
Sources in order of authority: the current source tree (
Source/com.p2pframework/src/com/p2pframework/DDS/) is authoritative; the sets/lists/trees paper (IPCCC 2016) is the design description; Graffi & Xu (CTS 2014) quantifies the remote-operation and consolidation mechanisms; Masinde's dissertation (2020) measures DDS load in production plugins.
Design in one paragraph
A DDS object (set, list, tree) is not one DHT record but a tree of buckets: entries live in
DistributedDataBucket objects addressed by hash and part number; buckets split when they
exceed a configurable splitsize, and deleted entries linger as tombstones until a
consolidation pass merges them
(CTS 2014).
Readers/writers talk to the bucket chain through remote operations instead of fetching whole
structures.
What the code has today (verified against source)
com.p2pframework.DDS contains, among others:
| Class | Role |
|---|---|
DistributedSet |
the set primitive (friends, group membership, wall posts) |
DistributedLinkedList / DistributedLinkedServer |
ordered list primitive — partially a stub |
DistributedTree, TreeElement, DistributedTreeElementLinkList |
tree primitive (forum threads) |
DistributedDataBucket |
bucket with identifier, partNumber, splitsize, groupHash |
RemoteOperation, RemoteOperationClient/Server, RemoteConsolidate |
server-side ops + consolidation |
DeletedDistributedItem |
tombstone representation |
SecureDistributedDataItem |
signed/encrypted items (see access control) |
PrefixHashTree, PrefixHashTreeServer |
hash-prefix structure reused by search/BloomJoin |
DataBackend, DistributedDataItemContainer |
StorageDispatcher-facing plumbing |
The stub is real and current: in DistributedLinkedList.java lines ~396–423 five interface
methods carry //TODO: Implement and throw UnsupportedOperationException — add, addAll,
listIterator (two variants) and subList. The GitLab tracker mirrors this exactly:
#37 add, #41 addAll, #38/#39 listIterator, #40 subList (all open). Unit-test scaffolding
exists (DistributedLinkedListTest, DistributedLinkedList_DistributionTest in
com.p2pframework.unittests), and SecureDistributedSetTest / SecureDistributedTreeTest
cover the secure variants
(testing methodology).
Measured behaviour
- Remote operations roughly halve traffic compared to whole-object fetch/republish; bucket layout improves it further (PG 2012 evaluation, CTS 2014).
- Consolidation lowers the share of deleted entries in buckets from up to 0.3 to usually
< 0.05;
splitsize = 20was a good trade-off in the tests (CTS 2014). Consolidation is triggered viaRemoteConsolidate; automatic consolidation is open work item #36 (Low Prio). - In a live overlay, plugins that lean on DDS generate 100–15,000 messages/s, second only to file storage's 500–23,000 msg/s class (dissertation plugin analysis).
Design choice: why buckets + remote ops?
A social feed changes with every post and is read by many friends; naive whole-object storage would re-encrypt and re-replicate the entire wall on each write and force readers to download it all. Bucketing bounds the object churn (only the touched bucket moves), remote operations bound the read traffic, and tombstones make concurrent writes converge — at the price of consolidation housekeeping, which is why #36 exists. Supersession note: the CTS 2014 security wrapper (group hashes, signed buckets) was the state of the art until the LANMAN 2017 access-control model refined key management on top; the bucket mechanics themselves are unchanged.
Open work worth doing
- #37–41 finish
DistributedLinkedList(correctness bar:java.util.LinkedListsemantics under distribution) — see blog: finishing the DDS. - #36 automatic bucket consolidation (policy: when tombstone share justifies a pass).
- #45 migrate deprecated storage access to the current StorageDispatcher API.
- #46 split oversized communication interfaces along DDS/StorageDispatcher boundaries — a Bndtools-friendly first step (revival build).
Related
DDS component page · caching · data synchronization · feature overview