> 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.
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.