3 ms·

1. The raw array solution doesn't work if you can't fit the entire thing in memory. You could try mmap'ing the file and letting the kernel do the paging for you

1. The raw array solution doesn't work if you can't fit the entire thing in memory. You could try mmap'ing the file and letting the kernel do the paging for you, I guess. 2. There's nothing over engineered about a B-Tree. It's a simple, well understood data structure which solves this exact problem. 3. There are meaningful differences in what you can do with a solution that gives you answers in microseconds vs milliseconds, as the blogger mentions.

jiggawatts 7y ago
> The raw array solution doesn't work if you can't fit the entire thing in memory. Of course it works. You don't have to literally load the whole file into memory as an array. That's not how file I/O works! Just fseek() to the desired multiple-of-20 address and read 20 bytes. > You could try mmap'ing the file You'd only try that if you haven't read the documentation for mmap, just like a bunch of Rust programmers did. They started on 64-bit machines and never noticed that mmap is limited to a ~256MB window on most 32-bit architectures. Certainly less than the 11GB needed for this problem! > There's nothing over engineered about a B-Tree. Yes there is. This guy hand-rolled 400+ lines of low-level data structure manipulation code just for the B-Tree manipulation. How much do you want to bet that he's got zero memory safety issues or other unsafety in that thing? Would you link this to your web app? Really, a C++ library? > That gives you answers in microseconds vs milliseconds I don't want to call him a liar... but now I have to. At the very least, he's made fatal mistakes in his benchmarking. There is no way that he can do random password lookups from on-disk structures in under 50 microseconds, unless he's got an Intel Optane SSD, and even then I would be highly suspicious. He's either cached the entire data structure in memory (at which point why bother with such a complex solution), or he's used the same set of passwords over and over for testing (which will falsely show a much lower latency than you would get with real passwords). So answer me this: How would this solution work on a typical auto-scale cluster of stateless web server VMs? Do you replicate 5-12GB to every VM every time this database changes? Or do you put one copy on a network share? Congratulations, you now have 1ms latency minimum! That fancy microsecond optimisation has just gone out the window... To be blunt: If your password-testing is the bottleneck to the point that a 50 microsecond latency is needed, then you're running a service that gets 20,000 password resets per second. At this point you're bigger than Office 365 and G Suite... combined, and you likely have much more important scaling concerns.
- haberman 7y ago
  > You'd only try that if you haven't read the documentation for mmap, just like a bunch of Rust programmers did. They started on 64-bit machines and never noticed that mmap is limited to a ~256MB window on most 32-bit architectures. Do you have a reference for that? I've never heard of this and I can't imagine the reason for such a limitation.
  - unilynx 7y ago
    Having done a lot with mmap on 32bit systems I can't remember such a technical limitation either.. ..although in practive it might be hard to find 256MB of contiguous memory in a 4GB virtual memory space due to fragmentation of other allocations and shared libraries, especially with ASLR.
  - jiggawatts 7y ago
    https://stackoverflow.com/questions/5518084/memorymappedfiles-how-much-memory-can-be-allocated-for-files https://stackoverflow.com/questions/5518084/memorymappedfile... There's the hard limit of 2GB for most versions of 32-bit Windows and 4GB for any operating system. Couple that with the requirement for a contiguous address space as well as various page table entry (PTE) limits, you get all sorts of "soft" limits way before 2GB. From what I've heard, 256MB is relatively safe to map, but anything much larger than that is increasingly likely to fail. Correctly written code should be able to work with moveable "windows" into the file as small as 32MB to be properly robust, especially if the process memory is already fragmented. Lots of software crashes with large files on 32-bit machines because of this. E.g.: https://www.monetdb.org/pipermail/users-list/2009-January/002473.html https://www.monetdb.org/pipermail/users-list/2009-January/00... As a more recent example, ripgrep had issues on 32-bit platforms because of a bug in the way the underlying mmap library worked in Rust. Even on 64-bit platforms you can run into trouble. For example: https://jira.mongodb.org/browse/SERVER-15070 https://jira.mongodb.org/browse/SERVER-15070 In that example, Windows Server 2008 R2 has an 8 TB limit. You could hit that if using a tool like ripgrep to do "forensic analysis" of disk images from a SAN, where virtual disks typically have 16 TB limit. So if you mount a SAN snapshot and open the disk as a file to scan it, you will hit this limit! Programmers make all sorts of invalid assumptions...

jiggawatts 7y ago

> The raw array solution doesn't work if you can't fit the entire thing in memory. Of course it works. You don't have to literally load the whole file into memory as an array. That's not how file I/O works! Just fseek() to the desired multiple-of-20 address and read 20 bytes. > You could try mmap'ing the file You'd only try that if you haven't read the documentation for mmap, just like a bunch of Rust programmers did. They started on 64-bit machines and never noticed that mmap is limited to a ~256MB window on most 32-bit architectures. Certainly less than the 11GB needed for this problem! > There's nothing over engineered about a B-Tree. Yes there is. This guy hand-rolled 400+ lines of low-level data structure manipulation code just for the B-Tree manipulation. How much do you want to bet that he's got zero memory safety issues or other unsafety in that thing? Would you link this to your web app? Really, a C++ library? > That gives you answers in microseconds vs milliseconds I don't want to call him a liar... but now I have to. At the very least, he's made fatal mistakes in his benchmarking. There is no way that he can do random password lookups from on-disk structures in under 50 microseconds, unless he's got an Intel Optane SSD, and even then I would be highly suspicious. He's either cached the entire data structure in memory (at which point why bother with such a complex solution), or he's used the same set of passwords over and over for testing (which will falsely show a much lower latency than you would get with real passwords). So answer me this: How would this solution work on a typical auto-scale cluster of stateless web server VMs? Do you replicate 5-12GB to every VM every time this database changes? Or do you put one copy on a network share? Congratulations, you now have 1ms latency minimum! That fancy microsecond optimisation has just gone out the window... To be blunt: If your password-testing is the bottleneck to the point that a 50 microsecond latency is needed, then you're running a service that gets 20,000 password resets per second. At this point you're bigger than Office 365 and G Suite... combined, and you likely have much more important scaling concerns.

haberman 7y ago
> You'd only try that if you haven't read the documentation for mmap, just like a bunch of Rust programmers did. They started on 64-bit machines and never noticed that mmap is limited to a ~256MB window on most 32-bit architectures. Do you have a reference for that? I've never heard of this and I can't imagine the reason for such a limitation.
- unilynx 7y ago
  Having done a lot with mmap on 32bit systems I can't remember such a technical limitation either.. ..although in practive it might be hard to find 256MB of contiguous memory in a 4GB virtual memory space due to fragmentation of other allocations and shared libraries, especially with ASLR.
- jiggawatts 7y ago
  https://stackoverflow.com/questions/5518084/memorymappedfiles-how-much-memory-can-be-allocated-for-files https://stackoverflow.com/questions/5518084/memorymappedfile... There's the hard limit of 2GB for most versions of 32-bit Windows and 4GB for any operating system. Couple that with the requirement for a contiguous address space as well as various page table entry (PTE) limits, you get all sorts of "soft" limits way before 2GB. From what I've heard, 256MB is relatively safe to map, but anything much larger than that is increasingly likely to fail. Correctly written code should be able to work with moveable "windows" into the file as small as 32MB to be properly robust, especially if the process memory is already fragmented. Lots of software crashes with large files on 32-bit machines because of this. E.g.: https://www.monetdb.org/pipermail/users-list/2009-January/002473.html https://www.monetdb.org/pipermail/users-list/2009-January/00... As a more recent example, ripgrep had issues on 32-bit platforms because of a bug in the way the underlying mmap library worked in Rust. Even on 64-bit platforms you can run into trouble. For example: https://jira.mongodb.org/browse/SERVER-15070 https://jira.mongodb.org/browse/SERVER-15070 In that example, Windows Server 2008 R2 has an 8 TB limit. You could hit that if using a tool like ripgrep to do "forensic analysis" of disk images from a SAN, where virtual disks typically have 16 TB limit. So if you mount a SAN snapshot and open the disk as a file to scan it, you will hit this limit! Programmers make all sorts of invalid assumptions...