7 ms·

> we run on Azure SQL Hyperscale, which we maxed out at 80 cores for almost two weeks the data challenge is interesting here. there's clearly a lot of data - b

by anonu 11mo ago

> we run on Azure SQL Hyperscale, which we maxed out at 80 cores for almost two weeks the data challenge is interesting here. there's clearly a lot of data - but really its just emails and passwords you need to keep track of. SQL feels like overkill that will be too slow and cost you too much. are there better solutions? 15 billion records of email+password, assume ~40bytes thats roughly 600GB should be searchable with a an off-the-shelf server. of course, im oversimplifying the problem. but I'm not clear why any solution to insert new records would take 2 weeks...

jiggawatts 11mo ago
> we run on Azure SQL Hyperscale Definitely the wrong technology, and was almost certainly picked only because Troy Hunt is a "Microsoft Regional Director and MVP". Many other technologies scale better for this kind of workload. Heck, you could ask ChatGPT to write a short C# CLI tool to process the data on one machine, you don't even need a huge box. This kind of thing comes up here regularly on HN for problems such as duplicate password detection, leaked password filtering, etc... After previous brainstorming sessions the general consensus was that it's really hard to beat a binary file that contains the sorted SHA hashes. I.e.: if you have 1 billion records to search and you're using a 20-byte SHA1 hash, then create a file that is exactly 20 billion bytes in size. Lookup is (naively) just binary search, but you can do even better by guessing where in the file a hash is likely to be by utilising the essentially perfectly random distribution of hashes. I.e.: a hash with a first byte value of "25" is almost certainly going to be 10% of the way into the file, etc... It's possible to create a small (~1 MB) lookup table that can guarantee lookups into the main file with only one I/O operation of a fixed size, such as 64 KB. Sorting the data is a tiny bit fiddly, because it won't fit into memory for any reasonably interesting data size. There's tricks to this, such as splitting the data into 65,536 chunks based on the first two bytes, then sorting the chunks using a very ordinary array sort function from the standard library. On blob storage this is super cheap to implement and host, about 50x cheaper than Azure SQL Hyperscale, even if it is scaled down to the minimum CPU count.
- zazaulola 11mo ago
  Try Blake3 instead SHA-1 https://github.com/BLAKE3-team/BLAKE3 https://github.com/BLAKE3-team/BLAKE3
  - jiggawatts 11mo ago
    The sorting is the slowest step by far. Hashing is so fast that you can hand-wave it away as zero cost relative to the time taken to read such a large amount of data. Also, you only have to do it once for the whole input, which means that it's O(n) time where 'n' is the gigabytes of passwords you have. Sorting is going to need about O(n * log n) time even if it's entirely in memory, but more if it has to spool to disk storage then it'll take much longer than the hashing step. PS: I just realised that 2 billion passwords is not actually that much data -- only 40 GB of hashes -- that's well within the range of what's "easy" to sort in-memory by simply creating an array of hashes that size and calling a standard library sort function.
    - zazaulola 11mo ago
      What other algorithms have you used? I'm really interested in big data streams. I would like to hear not only successful solutions, but also failed ones. Have you tried using Bloom filters? Is it possible to merge shards using the Min-Heap algorithm?
      - jiggawatts 11mo ago
        Algorithm choice depends on what you're optimising for. The discussion a few years ago was dozens of small web servers handling a large volume of password change traffic (10K/sec!) needing a cheap centralised service for verifying against "known bad" passwords. On a cloud hosting platform, the optimal solution is a blob store of sorted binary hashes with a small (~1 MB) precomputed index stored in-memory in the web server that lets you query the main store with 1 or at most 2 reads. This is an optimal "one round trip" request, and the per-server overhead at the front end is negligible. However, that approach assumes a slowly changing list where you don't mind that there's a delay of maybe a few hours to merge in a new list. Large lists of password leaks are infrequent, so this works fine for this usecase. A two-layer approach with a small frequently updated hash set on top of the large infrequently built sorted list is more generally applicable to a wider range of problems. Bloom filters are probabilistic, and aren't much faster to create than a sorted list. They also require 'k' random reads to test, where k is a small constant such as 3 to 5. If the filter is large (gigabytes), then you can't efficiently load it into many front-end web servers. If you query it over the network as a blob, you need 3-5x the I/O operations. You can wrap it in an API service that holds it in-memory, but that's still much more complex than simply storing and querying a blob in S3 or Azure Storage directly. "Clever" algorithms like min-heaps or whatever are likely not worth the trouble. My decade-old PC can sort 2 billion hashes in about 30 seconds using the Rust "Rayon" crate. There are cloud VMs available for about $2/hr that have about a terabyte of RAM that could sort any reasonable sized list (10s of billions) in a few minutes at most. The original article mention a week of 80 vCores of SQL Hyperscale, which is about $6,000 at PayG rates! Sure, developer time is expensive, blah blah blah, but waiting a week ain't cheap either, and these days an AI can bang out the code for a password file hashing and sorting utility in a minute or two.
enjaydee 11mo ago
Thought the same thing, and agree completely with jiggawatts. Troy does very well off the back of this relationship, and on that note I hate how confusing the marketing language of "Microsoft Regional Director and MVP" is.
bobmcnamara 11mo ago
> I'm not clear why any solution to insert new records would take 2 weeks... The article mentions some of the challenges, like 1.9e9 sha1 hashes. And 1.9e9 row updates performing poorly in-place, so they created a separate table for the results. Then they got rate limited by email providers when they wanted to tell people about their pwnage

by anonu 11mo ago

jiggawatts 11mo ago

> we run on Azure SQL Hyperscale Definitely the wrong technology, and was almost certainly picked only because Troy Hunt is a "Microsoft Regional Director and MVP". Many other technologies scale better for this kind of workload. Heck, you could ask ChatGPT to write a short C# CLI tool to process the data on one machine, you don't even need a huge box. This kind of thing comes up here regularly on HN for problems such as duplicate password detection, leaked password filtering, etc... After previous brainstorming sessions the general consensus was that it's really hard to beat a binary file that contains the sorted SHA hashes. I.e.: if you have 1 billion records to search and you're using a 20-byte SHA1 hash, then create a file that is exactly 20 billion bytes in size. Lookup is (naively) just binary search, but you can do even better by guessing where in the file a hash is likely to be by utilising the essentially perfectly random distribution of hashes. I.e.: a hash with a first byte value of "25" is almost certainly going to be 10% of the way into the file, etc... It's possible to create a small (~1 MB) lookup table that can guarantee lookups into the main file with only one I/O operation of a fixed size, such as 64 KB. Sorting the data is a tiny bit fiddly, because it won't fit into memory for any reasonably interesting data size. There's tricks to this, such as splitting the data into 65,536 chunks based on the first two bytes, then sorting the chunks using a very ordinary array sort function from the standard library. On blob storage this is super cheap to implement and host, about 50x cheaper than Azure SQL Hyperscale, even if it is scaled down to the minimum CPU count.

zazaulola 11mo ago
Try Blake3 instead SHA-1 https://github.com/BLAKE3-team/BLAKE3 https://github.com/BLAKE3-team/BLAKE3
- jiggawatts 11mo ago
  The sorting is the slowest step by far. Hashing is so fast that you can hand-wave it away as zero cost relative to the time taken to read such a large amount of data. Also, you only have to do it once for the whole input, which means that it's O(n) time where 'n' is the gigabytes of passwords you have. Sorting is going to need about O(n * log n) time even if it's entirely in memory, but more if it has to spool to disk storage then it'll take much longer than the hashing step. PS: I just realised that 2 billion passwords is not actually that much data -- only 40 GB of hashes -- that's well within the range of what's "easy" to sort in-memory by simply creating an array of hashes that size and calling a standard library sort function.
  - zazaulola 11mo ago
    What other algorithms have you used? I'm really interested in big data streams. I would like to hear not only successful solutions, but also failed ones. Have you tried using Bloom filters? Is it possible to merge shards using the Min-Heap algorithm?
    - jiggawatts 11mo ago
      Algorithm choice depends on what you're optimising for. The discussion a few years ago was dozens of small web servers handling a large volume of password change traffic (10K/sec!) needing a cheap centralised service for verifying against "known bad" passwords. On a cloud hosting platform, the optimal solution is a blob store of sorted binary hashes with a small (~1 MB) precomputed index stored in-memory in the web server that lets you query the main store with 1 or at most 2 reads. This is an optimal "one round trip" request, and the per-server overhead at the front end is negligible. However, that approach assumes a slowly changing list where you don't mind that there's a delay of maybe a few hours to merge in a new list. Large lists of password leaks are infrequent, so this works fine for this usecase. A two-layer approach with a small frequently updated hash set on top of the large infrequently built sorted list is more generally applicable to a wider range of problems. Bloom filters are probabilistic, and aren't much faster to create than a sorted list. They also require 'k' random reads to test, where k is a small constant such as 3 to 5. If the filter is large (gigabytes), then you can't efficiently load it into many front-end web servers. If you query it over the network as a blob, you need 3-5x the I/O operations. You can wrap it in an API service that holds it in-memory, but that's still much more complex than simply storing and querying a blob in S3 or Azure Storage directly. "Clever" algorithms like min-heaps or whatever are likely not worth the trouble. My decade-old PC can sort 2 billion hashes in about 30 seconds using the Rust "Rayon" crate. There are cloud VMs available for about $2/hr that have about a terabyte of RAM that could sort any reasonable sized list (10s of billions) in a few minutes at most. The original article mention a week of 80 vCores of SQL Hyperscale, which is about $6,000 at PayG rates! Sure, developer time is expensive, blah blah blah, but waiting a week ain't cheap either, and these days an AI can bang out the code for a password file hashing and sorting utility in a minute or two.

enjaydee 11mo ago

Thought the same thing, and agree completely with jiggawatts. Troy does very well off the back of this relationship, and on that note I hate how confusing the marketing language of "Microsoft Regional Director and MVP" is.

bobmcnamara 11mo ago

> I'm not clear why any solution to insert new records would take 2 weeks... The article mentions some of the challenges, like 1.9e9 sha1 hashes. And 1.9e9 row updates performing poorly in-place, so they created a separate table for the results. Then they got rate limited by email providers when they wanted to tell people about their pwnage