LibreSocial · Documentation

DDS — Distributed Data Structures

Sets, lists, trees and a prefix hash trie built out of bucketed PAST objects. Modifications are executed remotely by the node responsible for a bucket instead of shipping objects to the caller; integrity rests on a signature chain in the stored item plus per-element signatures and encryption. Bundle com.p2pframework, package com.p2pframework.DDS.

Purpose

PAST stores opaque, replicated content under a 160-bit key. Nearly every object a user owns in LibreSocial is a collection — the wall entries of a profile, the comments of one entry, the threads of a forum, the members of a group, the photos of an album, the ballots of a poll. A key/value store cannot express those: no ordering, no membership test, no incremental update, and a whole-object overwrite per change is a read-modify-write race. DDS supplies:

Out of scope here: replication and capacity-aware redirection (PAST storage, load balancing), the plugin-facing facade and social caching (StorageDispatcher, caching), group membership and key distribution (com.p2pframework.users, access control), overlay routing (overlay). Wire-level detail: DDS internals.

Current implementation (as of 2026)

Naming note. The component index lists com.p2pframework.DDS and .dds variants; the current tree has exactly one DDS package — bundle Source/com.p2pframework/, package com.p2pframework.DDS, 23 classes, 6 493 lines — and no com.p2pframework.dds. One duplicate to know about: the search engine class exists twice, as com.p2pframework.DDS.Search (instantiated by Framework.java:215) and com.p2pframework.search.Search (used by DataBackend, ProfilePluginComponent, SearchPlugin), differing only in their imports.

Class Path under Source/com.p2pframework/src/com/p2pframework/DDS/ Size Role
RemoteOperationClient RemoteOperationClient.java 407 L base for every DDS object: builds OperationMessage, registers WaitingMessageCallback, sends, waits, retries; getSignInfos, signChange, sendChanges; alongside it the enums RemoteOperation, RemoteOperationClientIdentifier and the RemoteConsolidate interface
DistributedSet DistributedSet.java 1415 L bucketed set and base class of the list: bucket key derivation, metadata object, ACL/crypto handling, consolidation, threshold trigger
DistributedLinkedList, DeletedDistributedItem same package 435 / 21 L List semantics: logical ↔ absolute position mapping around tombstones, consolidate(startPart); the tombstone written in place of a removed element
DistributedLinkedServer DistributedLinkedServer.java 871 L server side: applies each set/list operation to the stored bucket, hash precondition, bucket concatenation
DistributedDataBucket DistributedDataBucket.java 101 L the stored payload: Vector<E> list, its hash, splitsize, groupHash, lastConsolidateStatus
DistributedDataItemContainer DistributedDataItemContainer.java 224 L element envelope: writer public key, UUID nonce, signature over (previous nonce, element), verifyDataItem(oldPubKey, oldNonce)
SecureDistributedDataItem SecureDistributedDataItem.java 170 L ACL-managed element: symmetric ciphertext, user signature, group signature, pubPrivKeyVersion, secretKeyVersion
DistributedTree, DistributedTreeElementLinkList, TreeElement same package 353 / 519 / 76 L tree encoded as one link list per element (structureIdentifier + "_0" is the root's child list)
PrefixHashTree, PrefixHashTreeServer same package 635 / 497 L trie: split, merge, serial/parallel/iterating range scans, next/prev links between trie nodes
OperationMessage, DoneMessage, WaitingMessageCallback same package 51 / 47 / 105 L request (operationID, positionHash, object–object3, datastructure, responseCount), answer, blocking receiver with aggregation
DataBackend DataBackend.java 169 L one MessageCallback per node that instantiates the right server object on demand

Wiring

plugin  →  new DistributedLinkedList<T>(framework, listName)      (also DistributedSet / DistributedTree / PrefixHashTree)
  DistributedSet ctor: frame, structureIdentifier, splitSize (Configuration.getSplitSize()), retriever = framework.getGroupKeysRetriever()
  issueOperation(hash(i), RemoteOperation.addAll, data, signInfo)
    → framework.getChannel().sendMessageToResponsibleNode(hash, OperationMessage)   // channel com.p2pframework.Backend
      → PastryMessageChannel.sendMessageToResponsibleNode()      (…/message/scribe/PastryMessageChannel.java:154)
        route(buildId(hash))  →  the node responsible for that Id
          → DataBackend.messageArrived() → DistributedLinkedServer / PrefixHashTreeServer / …
             applies the operation, storage.storeServerItem(part, part.hash, sign, pubKey)
        ← DoneMessage(operationID, positionHash, continuationHash, result)
  WaitingMessageCallback.waitForCompletion(timeout)

Routing key and content id are deliberately identical: both are PastryIdFactory.buildId(structureIdentifier + "_" + n), so the operation message reaches the node holding the bucket and the answer is routed back to the caller's id. Retries can address a known peer directly (sendMessageDirect). DataBackend is registered once per node on channel com.p2pframework.Backend (backendChannelName) and lazily re-creates the server-side view of a structure; the same dispatch point also serves the unrelated AggregationServer, GroupServer, appstore data servers and JoinQueryEngineServer. DataBackend still contains leftover traffic instrumentation with the comment "remove this!!!!!".

Parameters as configured today

Parameter Source Value in 2026
bucket size dds_split_size (Source/org.lifesocial.core.utilities/resources/config/LibreSocialConfig.txt), mapped by Configuration.getSplitSize() (com.p2pframework/Configuration.java:395) -1 → Integer.MAX_VALUE, i.e. one bucket per structure, unless a caller overrides with setSplitSize(int); the search index uses 100, the trie default is 10
eager consolidation for lists dds_linkedlist_consolidation → Configuration.consolidateAfterDelete() true
threshold consolidation (all structures) DistributedSet.DEFAULT_CONSOLIDATION_THRESHOLD, setConsolidationThreshold(double), consolidateTimeout 0.25; acknowledgement timeout 10 s
operation timeout RemoteOperationClient.issueOperation(...) 60 000 ms; 5 000 ms in the search index
bucket replication replicationFactor (PAST) 4
capacity-aware redirection of bucket retrievals enableHeterogeneityAwareness, heterogeneityCacheSize, CanYouProvideTimeOut, providerListLength 1, 50, 7 000 ms, 1

Security state worth knowing (verified in 2026 source)

The secure-DDS machinery exists and is exercised by the ACL-managed paths, but two enforcement points are off on master:

Tests

Source/com.p2pframework.unittests/src/com/p2pframework/DDS/ holds nine JUnit 4 classes (DistributedSetTest, DistributedLinkedListTest, DistributedLinkedList_DistributionTest, DistributedTreeTest, PrefixHashTrieTest, SecureDistributedSetTest, SecureDistributedTreeTest, WriteProtectionDistributedList, UltimateEvaluation). They boot a six-node Pastry cluster inside one JVM (TestNode2, TemporaryFolder storage directories, splitSize = 3) with test timeouts. No DDS test is @Ignored, but no Gradle test task exists in build-logic/src/main/groovy/osgi-bundle-conventions.gradle, so they compile without running in a build. consolidationByNonMemberIsRejected() (added 2026-07-10) asserts that a non-member calling randomConsolidate() cannot reduce the tombstone count.

Design options and decision

The code carries no design rationale; the alternatives below come from the publications named with each option, and decisions inferred from code or commit history are marked reconstructed.

1. Ship whole objects vs. execute operations remotely. The first implementation (before the commit "Move DDS from storing to communicating", 2011-11-14) stored one DDS object, handed it to the caller and took the modified copy back — a read-modify-write race, the full collection transferred per modification, and no place to test membership or ordering. The current design sends an operation and receives a short answer; the 2014 paper measures roughly half the traffic for write operations on 1 kB items. Decision: remote operations. Trade-off: every call becomes a synchronous round trip — latency instead of bandwidth — and one node serialises writes to one bucket, which is why issueOperationAsynchron and parallel fan-out exist.

2. One large object vs. bucketing with splitSize. Bucketing spreads load across peers, bounds the payload of one operation and allows parallel reads; the price is n / splitSize lookups for indexed access, membership tests across several buckets, and tombstones that only consolidation removes. The 2014 evaluation calls splitSize = 20 a good compromise for 1 kB items, and the 2016 paper measures that broad structures beat deep ones (deep retrieve 130 s vs. 19 s without churn, 313 s vs. 104 s with churn). The shipped default -1 (one bucket) is a reconstructed convenience choice: correct and message-cheap for small structures, but it forgoes load spreading entirely — every operation of one wall list hits a single peer.

3. Deterministic placement vs. capacity-aware placement of replicas. Option A, a second capacity-keyed overlay (Adaptive Chord, Wette 2011: mirror the hottest objects to capacity-rich peers, one extra hop for the redirect, λ = 70 kB/s, ω = 150 kB/s, γ = 0.8, κ = 0.2·v_max, τ = 0.3, rebalance every 4 min, results 806.7 s → 85.9 s download time and 71.8 % → 97.1 % success; the rebuild-everything variant Re-Chord rejected as impractical under churn). Option B, chosen: keep DDS keys deterministic and confine capacity handling to PAST's retrieval path (heterogeneity cache, CanYouProvideMessage, provider list). The reason is structural — reconstructed: DDS addresses a bucket by routing message and content id alike, so a placement change in one place would break the other.

4. Recursive traversal vs. a root-side structure cache. A recursive trie read costs N · S overlay retrievals (N trie nodes, S replicas). The structure-cache paper (2016) proposes IStructureCache (CacheStructure(depth) / BuildStructureFromCache()) at the root object: collective retrieval falls to about 2 · S (190 s → 40 s with churn) for (C−1) · SizeOf(OverlayKey) of cache data, replication with the root, a recursive fallback if the cache is lost, and a single-item retrieval that becomes far more expensive (1.1–1.4 s → 18.4 s). Not implemented: no StructureCache appears in the source. The rationale for shipping the recursive variant is reconstructed — LibreSocial's tries and lists change continuously (wall, forum, search index), which is precisely the case the paper itself calls unsuitable, and the next/prev trie links already make range scans sequential instead of recursive.

5. Access control and encryption granularity. Three designs are on record: (a) secure DDS 2014 — signature chain per bucket plus per-element signature and nonce, symmetric group-key encryption; (b) the 2012–2014 distributed access-control work (branch 2012_Framework_PG12_Distributed-Access-Control-Iteration-2_Jens-Janiuk_stable, thesis 2014) — user lists, nested groups, group keys; (c) 2017 — one encrypted copy plus an ACL-patterned Access Control Map of signed access-control entries carrying the data key wrapped per authorized user, granular encryption and granular signature, an "Encryption Version" parameter, and lazy revocation (old versions are ignored rather than re-encrypted). The code implements (a) with the key management of (b): SecureDistributedDataItem inside DistributedDataItemContainer, keys fetched per version from GroupKeysRetriever/KeyContainer and cached, so an old element stays readable after rotation — the effect lazy revocation targets, reached by key versioning instead of an ACL map. com.p2pframework/storage/AccessControlList.java (HashMap<UserID, byte[]> readAccess of wrapped keys) belongs to the storage item model and is not used by DDS. The 2017 ACL map, the granular signature scheme and the "Encryption Version" parameter are not implemented. Trade-off of the chosen scheme: rotation forces a re-encryption pass over the structure, and readers must be able to fetch old key versions, which keeps revoked members able to read old data.

6. Delete semantics: tombstones and when to compact. Rewriting the structure on every delete costs a full pass per delete; tombstones defer the cost. Chosen: tombstones. Lists compact eagerly when dds_linkedlist_consolidation = true because gaps are visible to the List API; sets compact lazily, and since 2026 the lazy rule is a threshold (0.25) with pair-wise randomConsolidate() — two buckets, two storage peers, constant messages — instead of consolidateAll()'s full sweep. The 2014 paper reports the deleted-item share dropping from up to 0.3 to below 0.05 with that pair-wise protocol.

7. Concurrency: replicated merge vs. precondition + retry. No conflict-free replicated type is used. The writer submits the SHA-1 hash of the state it modified (RemoteOperationServer.getHash); DistributedLinkedServer compares it with the stored bucket and either applies the operation or returns the current state, after which sendChanges re-applies the local modification and retries. This is safe here because a bucket's replicas are redundant copies on one leaf set, not independent writers — the bucket is a single serialization point by construction. Trade-off: positions are stable only in the server's serialization order, and getInternElementPosition / getOuterElementPosition make a concurrent insert shift the index other readers see.

8. Trees: adjacency list per element vs. nested DDS objects. Each element owns its own child link list, so addChild is a normal list add and fan-out is unbounded, at the cost of depth structure retrievals per path access. Reconstructed from the 2016 depth measurements: the encoding keeps DDS nesting at one level and pushes application depth into sequential retrievals.

9. Monitoring of structures — not decided in this component. DDS has no monitoring: no bucket health checks, no gossip about structure state, no structure statistics (autoStartMonitoring = 0 belongs to the monitoring component). The centralized, gossip and DHT-tree alternatives discussed in SkyEye (2017) and Convex Hull Watchdog (2016) were decided there, over a separate tree-based over-overlay, and are orthogonal to DDS. That DDS could host such a tree — its next/prev trie links plus the aggregation channel — is reconstructed; nothing in the 2026 source does it.

Technical details

Bucketing and keys. DistributedSet.identifierToHash(identifier, partNumber) returns identifier + "_" + partNumber, fed to PastryIdFactory.buildId(String) — the same call that produces the PAST content id. Part numbers are handed out by numberOfNexts: addIntern targets the current last bucket, and when the server reports it full (sendChanges result 0) the index is incremented and the add retried on the next bucket. A set also stores itself as the metadata object under the bare structureIdentifier (operation setObject, stored as PastryStorageItem((DistributedSet) this, null, null)): that object carries size, numberOfNexts, splitSize, ACLManaged, groupHash and deletedElements, a rice.p2p.util.SortedLinkedList<Integer> of absolute positions of tombstones. setUpdateMetadataAutomaticly and setStoreMetadataAutomaticly control when autoMetaDataUpdate() / autoMetaDataStore() run.

Signature material. RemoteOperationClient.getSignInfos() returns an ArrayList<Object>: [0] the change signature over the previous version's nonce (signChange with the structure's or the group's private key), [1] the EC public key bytes, [2] the groupIdentifier (group hash) or null; sendChanges appends [3] the SHA-1 hash of the locally modified bucket. The server reads that list from msg.object2, compares [3] with its own hash, and stores with storeServerItem(part, part.hash, signInfo[0], signInfo[1]).

Ordering and consolidation. delete(i) writes a DeletedDistributedItem into the slot and records the absolute position in deletedElements; getInternElementPosition(i) and getOuterElementPosition(i) translate logical index ↔ absolute slot. DistributedLinkedList.consolidate(startPart) slides live items leftwards and issues RemoteOperation.delete on emptied buckets. On DistributedSet, randomConsolidate() picks a random bucket that contains a gap (skipping pairs of fully deleted buckets) and calls consolidateBuckets(hash(i), hash(i+1)); the two servers exchange items via concatenateBuckets and confirm via receiveConsolidateStatusFromBucket, with a per-hash Semaphore serialising concurrent consolidation and consolidateTimeout bounding the wait. The automatic trigger sits in autoMetaDataStore():

int total = this.size + this.deletedElements.size();
if (total > 0 && (double) this.deletedElements.size() / total >= consolidationThreshold) {
    this.randomConsolidate();
}

Trie. A node is a DDS object keyed structureIdentifier + "_" + prefixLabel, alphabet a Vector<Character>, leaf payload a Multimap<String, E>. Exceeding splitSize (default 10) calls split(): |alphabet| children are created and linked through setNext, neighbours receive asynchronous newNext / newPrev, and items are redistributed by their next character. Falling below splitSize / alphabet.size() calls merge(), which first confirms with lookup that every sibling is a leaf and then drives mergeWithParents / mergeWithYou with an outstandingMergeIns counter. Range queries: rangeSerial walks next, rangeParallel fans out once and aggregates with multiMapAddAbortIfLeafsComplete, rangeSerialIterate returns a page plus continuationHash. optimizeRetrieveForLatency and optimizeLookupForLatency trade messages for waiting time.

Encryption and membership tests. ACL-managed structures (ACLManaged, groupHash set from the group of the structure) wrap each element in SecureDistributedDataItem — payload encrypted with the current symmetric group key (secretKeyVersion), signed with the group private key (pubPrivKeyVersion) and by the writer — then in a DistributedDataItemContainer with the writer's public key, a fresh UUID nonce and a signature over the previous nonce, which is what makes replay of an old bucket version detectable (verifyDataItem(oldPubKey, oldNonce)). Key versions are cached in per-version Hashtables; a missing version triggers a fresh retrieveSymmetricGroupKey(version), and a failed verifyGroup discards the item as malicious storage. equals/hashCode of SecureDistributedDataItem are computed over the ciphertext, so a storage node can answer contains without decrypting. Nested groups resolve keys through the same retriever.

Operations handled. DistributedLinkedServer: addAll, delete, removeAll, remove, contains, containsAll, getAll, get, getObject, set, setObject, indexOf, concatenateBuckets, receiveConsolidateStatusFromBucket. PrefixHashTreeServer: newPHT, lookup, lookupAndAdd, rangeSerial, rangeParallel, rangeSerialIterate, newNext, newPrev, clear, mergeWithParents, mergeWithYou. Aggregation strategies in use: bool, smallestNonNegative, trueToHash, collectionRetainAll, multiMapAddAbortIfLeafsComplete, assign. WaitingMessageCallback matches answers by operationID, aggregates them, tracks outstanding addresses, and exposes getNeededMessages() so the caller can decide to resend.

Costs. One modification = one request plus one answer to the responsible node. Membership test in a set = up to n / splitSize requests; get(i) on a list = i / splitSize-ish requests reduced by the metadata's position maps; trie lookup = prefixLength + 1 retrievals; range scan = number of touched trie nodes (one round with rangeParallel). The 2016 evaluation reports ≈ 400 contacted nodes per 100-item structure and ≈ 600 forwarded messages per node at 102 000 item retrievals.

Consumers. WallPlugin (entries, one comment list per entry); Forum, ForumThread (thread and post lists); GroupsPlugin, Folder (DistributedSet<UserID> membership, folder contents); photosplugin, messagingplugin, voting, notifications; users/{Group,UserManager,GroupKeysRetriever}; search/Search (one list per category/tag with splitSize = 100, tries for indexes); appstore/server/AppstoreDataServer; message/aggregate/Aggregator; example com.p2pframework.examples/…/distributedtree/DistributedTreeApp.

Evolution and supersession

When Change Evidence
2007–2010 LifeSocial.KOM start; no DDS yet — data went through PAST objects 2008–2010 papers, framework overview (2013)
2011-11-07 first DDS commit, "Distributed Linked List starting point" git log …/com/p2pframework/DDS (254 commits)
2011-11-14 architecture pivot: "Move DDS from storing to communicating" same log
2011-11-21…27 bucket scheme "name_partNumber" introduced; communication factored into RemoteOperationClient; enums replace operation strings; trie started same log
2012 student branches in parallel: write protection, distributed access control (2 iterations), heterogeneity origin/2012_Framework_PG12_Distributed-Access-Control-Iteration-2_Jens-Janiuk_stable, …
2013-03/04 writeProtection merged (2013-04-09), consolidation bug fixes, monitoring correction same log
2014-03 secure DDS lands: signing update (03-26), single decryption per retrieval (03-24), 60 000 ms list timeout same log; 2014 paper
2016-09-19 dds_split_size and dds_linkedlist_consolidation become configuration keys commit "DDS Split Size and consolidation after delete are now configurable"; branch …_Patrick-Szewior_unstable_DDS_ConfigLoader
2016 structure model and evaluation published; structure cache proposed 2016 DDS, 2016 structure cache
2017 access-control redesign (ACL map, granular signature, lazy revocation) published; revises the 2014 key-distribution description; not implemented short paper, poster
2019-10-28 · 2020-07-13 social cache (M. Kanzler) merged on a separate branch — caching above DDS, not in it; "ported initial commit", the open-source LibreSocial port git log
2025 revival studies: error fixes, baseline evaluation, build/setup guide Reviving LibreSocial (2025), Setup Guide (2025)
2026-04/05 Gradle build (04-23); Java 8 spliterator() annex and autoboxing cleanups on refactor/2026_P2PframeworkDDS (05-13); OpenRewrite pass — @Serial, instanceof pattern matching (05-25) git, origin/refactor/2026_P2PframeworkDDS
2026-07-10 latest functional change: automatic bucket consolidation trigger (AC1 + AC6) — consolidationThreshold = 0.25, check inside autoMetaDataStore(), setConsolidationThreshold, test consolidationByNonMemberIsRejected() commit 4078970d0063bfa0a6d38e8531262578724db1a7

Reading the publications against today's code: the 2016 structure paper is the current description of the structure model (item layout, remote operations, evaluation on PeerfactSim.KOM/Chord with PAST: success ≈ 99–100 %, 5–6 hops, 0.45–0.75 s store time) and supersedes the structural parts of the 2014 paper. The 2014 paper still describes the implemented security model, but must be read with the two 2026 caveats above, and its recommended splitSize = 20 contradicts the shipped default -1. The 2017 papers revise 2014's key distribution at design level only. Wette (2011) and Adaptive Chord (2013) describe the capacity indirection that DDS benefits from through PAST — the indirection was adopted, the second overlay was not. The 2016 structure cache was never shipped; the 2020 caching paper's social cache (random/trend/socialscore selectors, SocialScoreLS = α · TieStrength + β · MIL, Dunbar limit 150, 50 s interval, 99.2 % hit ratio with PAST + social cache combined) lives in bundle com.p2pframework.storagedispatcher. The dissertation (2020) and framework paper (2020) are the consolidated platform descriptions; the 2025 studies document building and measuring it again on current systems.