LibreSocial · Documentation

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

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

DDS component page · caching · data synchronization · feature overview