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)
- Capacities are discretized into capacity classes per dimension (CPU, memory, bandwidth) → a capacity tuple; queries are K-Search (exactly k peers meeting a threshold) or Full-Search (all peers in a range).
- The index is a static kd-tree — branching factor
bFper dimension, heightΣ⌈log_bF(k_i)⌉— but tree nodes are not peers: each node is a DHT object keyed by the hash of its bit-string address, so the whole path is locally reconstructible and one DHT lookup retrieves the relevant leaf list. - Deterministic construction (no leader, no tree protocol): peers publish their capacity tuple into the leaf covering them; maintenance is O(d) messages per capacity change (d = number of capacity dimensions) with refresh/timeout; in the reference config a publication takes ≥ 28 messages (tree height 27 + 1), average publication time 1.7 s.
- Extensions discussed: update bundling, combined-capacity filters (Bloom-like ARF), meta-info broadcast; leaf traversal uses a spanning tree (bF = 4) — the main runtime factor for Full-Search.
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
- Packages
com.p2pframework.search(+datacollection,ring,network.freepastry) and the search plugin; current compile/run state in revival build notes, API notes in search component. - The 2017 evaluation gap (keyword search over plugin content) remains unaddressed — a good thesis topic; the capacity-search side is needed by work item #55 (reputation-driven placement) and by the replication work in security roadmap blog.