LibreSocial · Documentation

Search & CapSearch

Deep-dive page: two different "search" problems in one system — finding content/people in the DHT, and finding peers by capacity (CPU, storage, bandwidth) for placement decisions.

Supersession note: capacity search began inside the SkyEye tree (ICPADS 2008); the current, dedicated mechanism is CapSearch (AINA 2017), and the application-level search behaviour was evaluated separately (student study 2017).

1. Content/person search in the app

LifeSocial/LibreSocial searches operate on the distributed data model: users, profiles and friend relations are DHT objects addressed by ID (user ID = numeric public key, see access control), so "searching for a person" is a structured lookup, and searching within a user's data means walking the linked lists of small objects (CCNC 2011). The 2017 student study measured this mechanism in LibreSocial and found the keyword search limited to traversing locally indexed plugin data — a gap flagged for rework; the search plugin (org.lifesocial.plugin.searchplugin) is described on the search component page.

2. Why capacity search exists

Placement decisions — which peer stores a replica, relays a stream, takes over load — need answers like "give me k peers with upload ≥ x, free disk ≥ y, CPU ≥ z". The SkyEye tree answered this while walking upward (monitoring deep-dive), but the capacity part of update payloads does not aggregate: with list-based aggregation the bandwidth towards the root "increases exponentially", so nodes near the root are likely to fail and the approach "will not scale" without filter mechanisms or incremental updates (Groß 2009). CapSearch was built to make this cheap and churn-resilient.

3. CapSearch design (authoritative: AINA 2017)

4. Measured behaviour (PeerfactSim.KOM)

Scenario Result
No churn recall > 99 % (σ < 1 %); K-Search 0.14 s, Full-Search 0.31 s; maintenance ≤ 5 B/s per peer; search < 0.1 B/s (K) / 1 B/s (Full); per-peer storage ≤ 610 DHT objects ≈ 250 kB
With churn K-Search avg 0.92 s, ~93 % precision, < 3 % false positives; Full-Search avg 7.74 s, recall drops 80 % → 64 %
5 capacity dimensions (instead of 3) height 27 → 45; 101.75 msgs per tree update; update takes 10 s; 610 → 1350 objects (250 → 470 kB); K-Search 1.19 s
Maintenance stress (capacity change every 10 min) Full-Search precision 64 % → 58 %; K-Search quality and false-positive rate unchanged

Take-away for implementation: K-Search is robust to churn and maintenance load; Full-Search is the expensive mode — prefer threshold queries, keep capacity dimensions low, and batch capacity changes.

5. Code state & open work

Sources