...
- How do durability and reliability tie in to the discussion?
Approaches
Mapping/Address Space Paritioning
TradeoffTradeoffs: Capacity, Throughput (via parallel requests) vs Latency (lookup time client->host, host->addr+metadata)
...
Objects may need to relocate due failures, load, or capacity.
Fixed Number of Objects per Shard
- + O(1) lookup
- Just keep a table, shift the address to get the shard number, then lookup host by shard id
- - 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
Some of these issues are addressable with linear hashing techniques, but it will erode the O(1) time.
DHT
- + Simple
- + Natural replication
- Partition address space (needed for distribution anyway), multiple servers cover each partition
- - Latency
- Address to shard mapping has log(# shards) time in general, if shards are not fixed width
- Can be mitgated for index space tradeoff using radix tree or tries
- How many levels is too deep? Even 2-3 in the face of cache misses?
- + Load sharing
- - More difficult to co-locate related data on a single machine
- Probably the case that we want to intentionally distrbute related data (more network overhead, but reduces latency because lookups happen on independent machines)
...