4 ms·

Great intro to hashing but if the concept of mmhash3’s seed is going to be brought up I think it’s only natural to mention its design limitations and why you st

Great intro to hashing but if the concept of mmhash3’s seed is going to be brought up I think it’s only natural to mention its design limitations and why you still need something actually ddos resistant like SIP hash (even if we don’t get into the details of the latter). Also, it’s important to distinguish between hashing, hashing, and hashing. That is, hashing to map input to buckets, hashing to obscure the original string, and hashing to find similarities in the input data. They’re all called hashing but they have different (and conflicting!) requirements. There’s a reason you want mmhash3 to be fast but scrypt to be slow, and a reason why you want mmhash3 to avalanche but certainly don’t want your perceptual hashing algo of choice to do the same.

aappleby 3y ago
If I ever write Murmur4 it's going to be the smallest function that I can prove (via sat solver) to have no seed-independent collisions :D
- ComputerGuru 3y ago
  I approve of the use of relative metrics, Austin! Just be prepared for mmhash4 to be a few megabytes in size ;)
samwho 3y ago
I did have the distinction between cryptographic and non-cryptographic in there originally but found when junior folks read it they’d get confused about which use-case was being discussed. So I decided to focus on just one. With more time, I would have liked to cover at least scrypt. I’ll be honest, I don’t know what the design limitations of the seeding in murmur3 are. What I wanted to show is the concept of seeding and what it’s there to prevent. I’m hoping that comes across, even without any deeper exploration of seeding.
- ComputerGuru 3y ago
  Seeding is kind of a hack. It doesn’t guarantee you’ll avoid a (or even the same) collision, and quite a few “popular” hashes only change the output (but don’t change whether or not there is a collision) when you change the seed. Thanks for the article, though!
  - samwho 3y ago
    Ahh I see, the limitation you’re talking about is that there isn’t any inherent guarantee that a different seed will mean two values no longer collide? It’s just likely (in the case of murmur3 at least).
    - ComputerGuru 3y ago
      Yes, but it's not just that there's only "a chance" that the collision is avoided - that would be enough if it was actually just a random probability (after all, everything about hashing and collisions - in the best textbook case - is just chance). The problem is that there are methods for obtaining what we call "seed-independent collisions" where by analyzing the hashing algorithm itself you can actually determine a priori values that will collide regardless of the seed. If you have half an hour to spare, I really recommend you take the time to read this: http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash...
      - samwho 3y ago
        Oh damn, I didn’t know that. Have bookmarked that post, thank you so much for your comments. I’ve been very fortunate in my writing that the comment sections are always full of people with awesome insight that I missed during my own reading on the topic.
Solvency 3y ago
One thing I wish the original article would explain is the use case of buckets. I'm sort of imagining weird use cases where the buckets represent different servers or storage systems for the purpose of spreading out data efficiently...but I'm totally guessing here. Because I would assume a proper load balancer would be based on the dynamics of real-time server performance, not because of some simple hash function. What are common hash to bucket use cases?
- samwho 3y ago
  The buckets, in the context of hash maps, are typically lists. Either arrays or linked lists. They're used to store the key-value pairs. Some load balancers do use hashing in much the same way hash maps do. Usually they'll take a combination of: source IP, source port, destination IP, destination port, and hash it. They'll then use that hash to pick a server. The practical impact of this is that each user always gets mapped to the same server. This is typically called "session sticky load balancing" because it means session information about that user can live on the server, safe in the knowledge that the user will always end up on that server and not get routed to any others.
- koromak 3y ago
  The idea of "buckets" here is purely to speed up search time, at a very low level. Don't think about it in the context of a web server or database storage, its way more base than that. Its literally just arrays in memory. The idea is: if you don't have a Hash or Map already implemented in your language, how would you build a fast one? You cant write my_object['my_key'], that doesn't exist, you don't have Key-Value storage. You need instead to somehow store those pieces of information, and find them later. Obviously, you could just stick every value inside one big array. Then when you call MyHash.get('key'), you simply do an array search. But that would be slow. Instead, you can hash the 'key', stick it into a smaller bucket based on the hash, and then more quickly search for it later. In the future, you know the hash of 'key', so you know which bucket to look in. The author does make it confusing, since in their example each bucket contains Entry (entry['value']), meaning they are already using a JS HashMap implementation in their rebuilding of a HashMap, but you could rewrite the example to do it without any objects. The code would be harder to read though.

aappleby 3y ago

If I ever write Murmur4 it's going to be the smallest function that I can prove (via sat solver) to have no seed-independent collisions :D

ComputerGuru 3y ago
I approve of the use of relative metrics, Austin! Just be prepared for mmhash4 to be a few megabytes in size ;)

samwho 3y ago

I did have the distinction between cryptographic and non-cryptographic in there originally but found when junior folks read it they’d get confused about which use-case was being discussed. So I decided to focus on just one. With more time, I would have liked to cover at least scrypt. I’ll be honest, I don’t know what the design limitations of the seeding in murmur3 are. What I wanted to show is the concept of seeding and what it’s there to prevent. I’m hoping that comes across, even without any deeper exploration of seeding.

ComputerGuru 3y ago
Seeding is kind of a hack. It doesn’t guarantee you’ll avoid a (or even the same) collision, and quite a few “popular” hashes only change the output (but don’t change whether or not there is a collision) when you change the seed. Thanks for the article, though!
- samwho 3y ago
  Ahh I see, the limitation you’re talking about is that there isn’t any inherent guarantee that a different seed will mean two values no longer collide? It’s just likely (in the case of murmur3 at least).
  - ComputerGuru 3y ago
    Yes, but it's not just that there's only "a chance" that the collision is avoided - that would be enough if it was actually just a random probability (after all, everything about hashing and collisions - in the best textbook case - is just chance). The problem is that there are methods for obtaining what we call "seed-independent collisions" where by analyzing the hashing algorithm itself you can actually determine a priori values that will collide regardless of the seed. If you have half an hour to spare, I really recommend you take the time to read this: http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash...
    - samwho 3y ago
      Oh damn, I didn’t know that. Have bookmarked that post, thank you so much for your comments. I’ve been very fortunate in my writing that the comment sections are always full of people with awesome insight that I missed during my own reading on the topic.

Solvency 3y ago

One thing I wish the original article would explain is the use case of buckets. I'm sort of imagining weird use cases where the buckets represent different servers or storage systems for the purpose of spreading out data efficiently...but I'm totally guessing here. Because I would assume a proper load balancer would be based on the dynamics of real-time server performance, not because of some simple hash function. What are common hash to bucket use cases?

samwho 3y ago
The buckets, in the context of hash maps, are typically lists. Either arrays or linked lists. They're used to store the key-value pairs. Some load balancers do use hashing in much the same way hash maps do. Usually they'll take a combination of: source IP, source port, destination IP, destination port, and hash it. They'll then use that hash to pick a server. The practical impact of this is that each user always gets mapped to the same server. This is typically called "session sticky load balancing" because it means session information about that user can live on the server, safe in the knowledge that the user will always end up on that server and not get routed to any others.
koromak 3y ago
The idea of "buckets" here is purely to speed up search time, at a very low level. Don't think about it in the context of a web server or database storage, its way more base than that. Its literally just arrays in memory. The idea is: if you don't have a Hash or Map already implemented in your language, how would you build a fast one? You cant write my_object['my_key'], that doesn't exist, you don't have Key-Value storage. You need instead to somehow store those pieces of information, and find them later. Obviously, you could just stick every value inside one big array. Then when you call MyHash.get('key'), you simply do an array search. But that would be slow. Instead, you can hash the 'key', stick it into a smaller bucket based on the hash, and then more quickly search for it later. In the future, you know the hash of 'key', so you know which bucket to look in. The author does make it confusing, since in their example each bucket contains Entry (entry['value']), meaning they are already using a JS HashMap implementation in their rebuilding of a HashMap, but you could rewrite the example to do it without any objects. The code would be harder to read though.