...
Tried this with off-the-shelf radix tree that claims to be fast and cache optimized (Judy): with 2^20 nodes average lookup time of about 3300 cycles on an AMD64 and 524 cycles on a Core 2 Duo, allocated 15 MB of RAM during inserts
B-Trees
- + Supports range queries on totally ordered keys
- +/- Allows several records from the same table to be returned with a single request
- Can give control over placement if they can take advantage of it for locality
- May cause a server to become a hot spot
- Is this anymore true than with hashing?
- - Latency (at least as bad as DHT)
...
- Reqs/sec
- MTBF if considering Reliability
Questions
- How do we update the address mapping when a host fails?
- Clients that detect the failed node initiate an update of the mapping
- Where, to whom?
- Clients that detect the failed node initiate an update of the mapping
Locality
Effects
- + Network traffic
- + Latency for serial requests
- + Performance isolation in multi-tenant environments
- + Economy of metadata
- For example, only access control information for data which resides on a host must be replicated to that host
...