...
- + O(1) lookup
- Just keep a table, shift the address to get the shard number, then lookup host by shard id
- Table is too large initally or too small eventually
Assuming 64 bit addrs, 32 bit host addrs, 4 replicas
log_2 # shards | log_2 # addrs/shard | index size |
|---|---|---|
30 | 34 | 16GB |
40 | 24 | 16TB |
- - Size of a shard can never grow beyond capacity of the largest machine
- Might not always be able to store even when there is excess capacity in the system
- Could do something hackish; have saturated host forward requests it doesn't have the entries for to another host with a different part of the same shard
- - Nearly impossible to determine address range chunk size initially
- - Nightmare if we decide we need a new address range chunk size
- Requires "rehashing" the whole thing
- - Adding and removing hosts
- Some of these issues are addressable with linear hashing techniques.
...