It seems to me that the problem could actually be solved by using a 64GB SSD. Given that the storage is 1TB and each of the keys and values are 128Bytes (and hence the disk is full to capacity), and assuming the keys are unique, which it would need to be to have all the keys unique, then we can safely say that every possible value in the 2^32 space is used. Therefore, we could read the data from the 1TB disk, and for each key we find, use the value of the key as the address of a memory location on the 64GB SSD. Net effect is we essentially remove all the key info from the hard disk and compress the storage into 16GB. ie, no need for the hard disk, just a 64GB SSD.