LibreSocial · Documentation

Search — user and content discovery over the DHT

Two coexisting mechanisms: an attribute-index query engine that fans out one DHT message per Soundex-normalised attribute tag and joins the returned buckets client-side (AND/OR), and a legacy ticket-based lookup of group membership lists. A range-search facade over DDS structures and the capacity-based CapSearch design round out the picture; CapSearch itself was never merged into this code base. Bundles com.p2pframework (package com.p2pframework.search) and org.lifesocial.plugin.searchplugin.

Purpose

In a serverless SNS nobody can be asked "who matches this query". Search must be expressible as DHT-addressable keys. LibreSocial solves this by inverting the query: every searchable attribute is written as an index entry under a key derived from the attribute itself ("ProfileCity = 2276"), so a search is a lookup of the attribute, not a scan of users. Concretely the component provides:

Current implementation (as of 2026)

All paths under Source/. The tree builds with Gradle + Bndtools on Java 17 (2026 migration); the search sources were touched by the OpenRewrite modernisation (May 2026, @Serial fields) and the OSGi Declarative Services binding fixes (June–November 2026). No functional protocol change.

Framework layer — com.p2pframework/src/com/p2pframework/search/

Class Role
Search.java Facade: indexTag/searchTag/removeTag map a category + "/" + tag onto a DistributedLinkedList (split size 100); indexRange/searchRange map onto a PrefixHashTree with a binary alphabet (int keys padded to 32 bits) plus arbitrary alphabets; searchTag(Collection,…) (Bloom-filter multi-tag search) is a stub returning null.
QueryEngine.java Interface: indexItemWithTags/Attributes, searchAllItemsWithTags/Attributes(…, andStrategy), getFirstAnswerTimes(); the removeItemIndex… and searchItem… methods are declared but unimplemented everywhere.
JoinQueryEngine.java The live implementation. RemoteOperationClient subclass registered as RemoteOperationClientIdentifier.JoinSearch. TIMEOUT = 5000 ms. Records first-answer and answer timings per query.
JoinQueryEngineServer.java Server side, instantiated lazily by com.p2pframework.DDS.DataBackend (case JoinSearch in the operation-message switch, DataBackend.java ≈ line 160). Handles addIndex, removeIndex, getIndex on AttributeBucket objects through the StorageDispatcher.
AttributeBucket.java The stored index node: String hash + HashSet<Serializable> items (StorageItem, replicated by PAST via the storage dispatcher).
QueryAttribute.java name/value pair; getTag() yields the index key text name + " = " + value; equals/hashCode make a Set of attributes a legal join input.
ScribeQueryEngine.java Pub/Sub variant (see Design options). Not wired into any plugin.
XMLAttributeConverter.java XML/attribute parsing helper (appstore metadata side; unused on the people-search path).

Note a duplication: com.p2pframework.DDS.Search is a byte-for-byte near-copy of com.p2pframework.search.Search; both are compiled, the DDS one is the older location.

Plugin layer — org.lifesocial.plugin.searchplugin/src/org/lifesocial/searchplugin/

Producers and consumers of the index

Design options and decision

The documents below state the alternatives explicitly for the 2008 and 2011 generations; where a rationale is not written down, the reconstruction is marked as such.

  1. Criteria lists (2008). Podrajanski's diploma thesis models search as reading the membership lists (SharedItemUserList) of groups matching the criteria — cheap, reuses the storage/dispatcher stack, but only answers "who is in group X", never "who has attribute Y". This survives today as the ticket-based plugin API and explains the group-key construction.
  2. Attribute buckets + client-side join (2011/12, chosen). The UPB project group 2011 introduced the QueryEngine abstraction with two implementations: - JoinQueryEngine (chosen): one DHT-routed OperationMessage per attribute tag; the responsible node maintains an AttributeBucket under buildId(tag); the client's Aggregator folds the per-attribute result sets with joinCollection (retainAll, AND) or orCollection (union, OR). Chosen because it composes multi-attribute queries out of plain DHT lookups and the already-built DDS remote-operation machinery, needs no new overlay structure, and supports both boolean strategies. - ScribeQueryEngine (not adopted): each indexer subscribes its node to the topic named after the tag; a query publishes on one tag's topic and every subscriber filters locally (tags.containsAll). Not wired into any plugin; the source itself carries a TODO that the AND/OR strategy is unimplemented and it "at the moment … is never used". Reconstruction: publish/subscribe gives no bucket aggregation (results never intersected in the tree), only single-attribute queries are implemented, and answer collection is a 1 000 × 10 ms sleep loop — the join engine was the more honest fit for the message-channel/DDS stack.
  3. Range and multi-keyword search (open in 2017 → DDS direction). Kanzler's evaluation (2017) audited the stack against five search categories and found only exact, keyword and substring coverage (3 of 5); range and true multi-attribute search were missing despite PrefixHashTree and Search existing in the framework. He lists Prefix Hash Trees, NetLocJoin/OptimizedRangeJoin and Scribe as the candidate directions. The framework's Search facade (tag→DLL, range→PHT, incl. 32-bit binary encoding of int keys and getRangeIterator) is the implemented substrate; Kanzler also confirmed the two practical defects — no filtering of private profiles/blocked users, and the fixed 5 s timeout making the GUI sluggish.
  4. Join placement in DDS trees (2016/2020). Graffi's dissertation devotes a chapter ("Search Algorithms for Distributed Data Structures") to where joins execute: Simple LocalJoin, Parallel LocalJoin, asynchronous NetworkJoin (join pushed into the overlay) and BloomJoin, evaluated against Binary Tree, Deep Tree and Customized Broad Tree layouts. Conclusion: LocalJoin/BloomJoin perform best on binary trees but load the initiating node; the search technique, join algorithm and DDS tree must be chosen jointly. This refines, not replaces, the 2011 JoinQueryEngine — the plugin still performs the join at the client (Aggregator), i.e. LocalJoin.
  5. Capacity-based search — CapSearch (2017, simulated only). Disterhöft & Graffi index multi-dimensional capacity classes (CPU, memory, bandwidth) in a static kd-tree realised as DHT objects (tree nodes are hashed bit-string addresses, not peers): one DHT lookup yields the relevant leaves; K-Search (exactly k nodes above a capacity) and Full-Search (all nodes in a capacity range); maintenance is O(d) per capacity change (≥ 28 messages at tree height 27), with refresh/timeout instead of push updates under churn. Related work it argues against: centralised indexes (single point of failure), gossip-based capability discovery (SCRAP/MURK, Carlini et al./DRAGON — redundant traffic under churn) and Baton-style numeric-key overlays. This rationale is explicit in the paper; its application to LibreSocial's search plugin is reconstructed — no CapSearch class exists in Source/ (grep-verified); evaluation ran in PeerfactSim.KOM.

Technical details

Index key space. A QueryAttribute("ProfileCity","2276") becomes the tag string "ProfileCity = 2276". PastryMessageChannel.sendMessageToResponsibleNode(hash,…) calls network.getPastryIdFactory().buildId(hash), i.e. the tag text is hashed into a 160-bit Pastry Id; the node responsible for that Id services the bucket. Replication and persistence are inherited from the StorageDispatcher/PAST layer — search never talks to the overlay directly.

Write path. JoinQueryEngine.indexItemWithTags(hash, tags) → RemoteOperationClient.issueParallelOperation(tags, RemoteOperation.addIndex, hash, …, TIMEOUT); per tag: OperationMessage(addIndex, positionHash=tag, object=item). Server addIndex: storage.retrieveItem(positionHash) → if absent or wrong type, new AttributeBucket(tag) → bucket.items.add(msg.object) on a processing thread → storeItem → DoneMessage(0) back (-1 on StorageException). The indexed object is the whole SearchContainer, so query results carry raw values for client-side ranking without a second lookup.

Read path. searchAllItemsWithTags(tags, andStrategy) picks AggregationStrategy.joinCollection (AND, result.retainAll(v)) or orCollection (union). issueParallelOperation re-sends to still missing addresses every waitForCompletion(5000) until the deadline (JoinQueryEngine passes 5 000 ms; the DDS default overload is 60 000 ms) — this is the fixed timeout Kanzler measured. Return is the aggregated Collection<Serializable> of SearchContainers.

Fuzzy layer. Index side: one Soundex code per token (a multi-word field yields several tags — the N-gram-ish effect Kanzler observed as "substring search"). Query side: same Soundex function, so exact phonetic hits return from the DHT; near hits beyond Soundex are not retrieved — Levenshtein (WeightedLevenshteinDistance in com.common.utilities) only ranks and prunes the returned set (threshold factor 1.4 × max length in the web handler).

Legacy group path. search(criteria) → spelling-variant expansion (4× cost) → buildGroupItemKey → SearchEngine.lookupUsers issues lookupSharedItem per key and creates a SearchRequestItem thread per key; UserListWaiter polls isAvailable every 30 ms and publishes partial results into the plugin's ticket table; completion = criteria-key list exhausted.

DDS facade parameters. DLL split size 100, PHT split size 10 (field default), binary alphabet {0,1}, toString(key,2,32) zero-padding — integer range keys become 32-symbol words for the trie; getRangeIterator(low,high) walks trie leaves in order. Prefix-hash-tree structure itself is documented in the DDS component doc.

Monitoring integration. JoinQueryEngineServer feeds MeasuringStorageImpl under class name SEARCH (gate measuringData); the plugin feeds SocialDataCollectionImpl with NUMBEROFSEARCH per call (gate socialMetricCollection); the SkyEye over-overlay can aggregate these (see monitoring component doc).

Integration points. ProfilePlugin (index producer), webprovider (REST query handler and ranking), commands/console (SearchPlugin.*), tester (TestCaseSearch), DDS (RemoteOperationClient/Server, DataBackend dispatch, DistributedLinkedList, PrefixHashTree), storagedispatcher/PAST (persistence + replication), FreePastry (Id routing), Scribe (unused ScribeQueryEngine path).

Evolution and supersession