You pretty clearly haven't used MDBM because the MDBM I worked on at SGI (and still use to this day) gets to any key in two page faults (aka 2 disk seeks) at the most. That was the whole point of it.
If you want I'll go shove a few GB into an mdbm, drop caches, and time a lookup.
2 seeks at the most, are you talking about a 32 bit address space? The only way that's possible in 64 bits is to direct map a hash into e.g. 2 32 bit chunks and use the hash as an actual disk block address for the first chunk, and an index into a block list for the 2nd chunk.
2 seeks. Address space doesn't matter, you have one seek to read the directory (I'm assuming 100% cold cache), and one seek to get to the page in question.
Not only that, we watched the bus on an SGI Challenge and counted cache misses and TBL misses. 2 TBL misses to get a key.
Saying that it isn't possible on a 64 bit VM system makes no sense to me. If I have a 2TB file and I seek to location A and read it, then seek to location B and read it, you are saying that's not possible? Same thing with mmap, I set a pointer to the mapping, read p, p += <number>, read p. Two seeks, two page faults, whatever you want to call it, it does 2 and only 2 I/O's to get a key/value (unless the pages are bigger than disk blocks but then those are going to be sequential I/O's, no extra seeks).
I was actually thinking of a >2GB DB file on a 32 bit server. But leaving that aside, it sounds like you're assuming a perfect hash function with no collisions. If you have collisions, you have to deal with the possibility of a hash bucket overflowing and requiring an additional seek.
Anyway, I don't doubt that you can operate in 2 seeks in the normal case.
Comments
You pretty clearly haven't used MDBM because the MDBM I worked on at SGI (and still use to this day) gets to any key in two page faults (aka 2 disk seeks) at the most. That was the whole point of it.
If you want I'll go shove a few GB into an mdbm, drop caches, and time a lookup.
If you've already ported the levelDB benchmark driver, feel free to send it to me: https://github.com/hyc/leveldb/tree/benches/doc/bench
2 seeks at the most, are you talking about a 32 bit address space? The only way that's possible in 64 bits is to direct map a hash into e.g. 2 32 bit chunks and use the hash as an actual disk block address for the first chunk, and an index into a block list for the 2nd chunk.
2 seeks. Address space doesn't matter, you have one seek to read the directory (I'm assuming 100% cold cache), and one seek to get to the page in question.
Not only that, we watched the bus on an SGI Challenge and counted cache misses and TBL misses. 2 TBL misses to get a key.
Saying that it isn't possible on a 64 bit VM system makes no sense to me. If I have a 2TB file and I seek to location A and read it, then seek to location B and read it, you are saying that's not possible? Same thing with mmap, I set a pointer to the mapping, read p, p += <number>, read p. Two seeks, two page faults, whatever you want to call it, it does 2 and only 2 I/O's to get a key/value (unless the pages are bigger than disk blocks but then those are going to be sequential I/O's, no extra seeks).
I was actually thinking of a >2GB DB file on a 32 bit server. But leaving that aside, it sounds like you're assuming a perfect hash function with no collisions. If you have collisions, you have to deal with the possibility of a hash bucket overflowing and requiring an additional seek.
Anyway, I don't doubt that you can operate in 2 seeks in the normal case.
It is 2 seeks, at most, for 100% of lookups.
Care to share any details on the hashing scheme? Is it based on linear hashing, a la Litwin and Larson?
The hash is up to you, several are provided.