Petabyte Dictionary Lookup

Question

What is the cheapest and most efficient way to make a map from keys to values at very large scale, perhaps several petabytes?When you query, the results are allowed to be a little stale.It should be available to several boxes on a datacenter. Services that provide this are acceptable.

nikonyrh · Accepted Answer

Well the theory tells us that lookups are O(1) anyway, so the implementation doesn't matter ;)Will the dataset change over time, or is it immutable? I have some thoughts on this, but I have no idea how it would scale to terabyte-scale and even further.

icsa · Answer

Extendible hashing or Minimal perfect hashing

Petabyte Dictionary Lookup

What is the cheapest and most efficient way to make a map from keys to values at very large scale, perhaps several petabytes?
When you query, the results are allowed to be a little stale.
It should be available to several boxes on a datacenter. Services that provide this are acceptable.

Well the theory tells us that lookups are O(1) anyway, so the implementation doesn't matter ;)
Will the dataset change over time, or is it immutable? I have some thoughts on this, but I have no idea how it would scale to terabyte-scale and even further.

Extendible hashing or Minimal perfect hashing