A Tale of Hashery and Woe: How Mutable Hash Keys Led to an ActiveRecord Bug
Tags: rails, ruby, programming
Published: 2023-01-10 14:25:13

In the changelog of Active Record right after version 7.0.4 is a small little bugfix that would, if I wasn't about to quote it and follow it up with this whole article, probably not catch your attention:

> Fix a case where the query cache can return wrong values. See #46044
>
> Aaron Patterson

Behind this innocuous release note, though, is a fascinating tale of how hashes in Ruby _really_ work that will take us from the Rails codebase down to the MRI source code. And it starts with a simple question: 

## Will this Ruby snippet print "hit" or "miss"?

```ruby
key = {}
hash = { key => "hit" }
key[:foo] = rand(1e6)

puts hash[key] || "miss"
```

## Well... it depends.
The only correct answer is **"yes"**. It could print _either_ value! If you think that's crazy, well, let me prove it:

```ruby
# ruby 3.2; same results on 2.7
1_000_000.times.each_with_object(Hash.new(0)) do |_, result|
  key = {}
  hash = { key => "hit" }
  key[:foo] = rand(1e6)

  result[hash[key] || "miss"] += 1
end

=> {"miss"=>996050, "hit"=>3950}
```

Wild, right? To get to the bottom of this, we'll have to dig into the Ruby source code and find the Hash implementation. 

## Pop open the hood
Ruby hashes are implemented in the succinctly named [hash.c](https://github.com/ruby/ruby/blob/ruby_3_2/hash.c). This bug is happening when we _look up_ a value, which ultimately requires us to find the **entry** in the hash's underlying array. The `ar_find_entry` function is responsible for that.

The arguments to it are:
* `hash`: the hash object itself
* `hash_value`: the numerical hash of the key object (in Ruby, any object responds to `.hash` and produces a deterministic, numerical hash -- try it out! This hash value is critical to how hashes work, as we'll see.)
* `key`: the key object

```c
static unsigned
ar_find_entry(VALUE hash, st_hash_t hash_value, st_data_t key)
{
    ar_hint_t hint = ar_do_hash_hint(hash_value);
    return ar_find_entry_hint(hash, hint, key);
}
# https://github.com/ruby/ruby/blob/ruby_3_2/hash.c#L744-L749
```

Your first thought (other than "whoa, how long has it been since I worked in C?") is probably to wonder what a "hint" is. The `ar_do_hash_hint` method, plus a quick lookup of the type definition in `hash.h`, tells us:

```c
static inline ar_hint_t
ar_do_hash_hint(st_hash_t hash_value)
{
    return (ar_hint_t)hash_value;
}
# https://github.com/ruby/ruby/blob/ruby_3_2/hash.c#L403-L407
```

```c
typedef unsigned char ar_hint_t;
# https://github.com/ruby/ruby/blob/ruby_3_2/internal/hash.h#L20
```

This typecast to an unsigned char means that **a hint is just the last byte of the numerical hash.** So, a number from 0 to 255.

## Delving ever deeper
Armed with that knowledge, we can proceed to `ar_find_entry_hint`. I'll strip the debug code out of this for clarity:

```c
static unsigned
ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key)
{
    unsigned i, bound = RHASH_AR_TABLE_BOUND(hash);
    const ar_hint_t *hints = RHASH(hash)->ar_hint.ary;

    for (i = 0; i < bound; i++) {
        if (hints[i] == hint) {
            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
            if (ar_equal(key, pair->key)) {
                return i;
            }
        }
    }
    return RHASH_AR_TABLE_MAX_BOUND;
}
# https://github.com/ruby/ruby/blob/ruby_3_2/hash.c#L701-L742
```

There are two checks this code makes for each entry to decide if it's our value:

* `if (hints[i] == hint)` -- Ruby uses the hint as a way to **quickly** check if the key is likely to be our key or not.
* `if (ar_equal(key, pair->key))` -- but before we *actually* return the row as a hit, we check the actual equality of the given key and the one for this entry.

What this means is that two objects having keys with the same hint is perfectly normal: the code would spend a little wasted time before realizing the keys are different, but we wouldn't expect a false positive.

So when we mutate the hash key in the snippet at the top of this post, there's a **1 out of 256** chance that our hash still keeps the same hint.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/16wcn664g1i8nco1yfyq.png)

## But won't the equality check save us?

**No!** Even after we mutate a hash, the hash **always stays equal with any references to it** (because it's the same object and therefore still has the same memory address). And the hash table isn't storing the key object by value; it's only storing a pointer to it. So in the snippet above, the reference to `key` inside `hash` will always be equal to the that same `key` object no matter how much we mutate it; meaning the only thing standing between us and a false-positive hit is the hint check.

That gives us a 255 out of 256 chance to see our "expected behavior of a miss, and a 1 out of 256 chance to see the unexpected hit. I ran the snippet at the top of the post for 100,000,000 iterations -- where we'd expect to see 390,625 hits -- and got 390,956. I'm no statistician, but I think that proves our logic is correct.

## Big deal. Clearly mutating a hash key is just a bad idea.
Well, you're not wrong. Python doesn't let dictionaries use mutable keys, which is very sensible. Go and JavaScript do, but they don't exhibit this bug and instead will always produce a hit after the key is mutated (without investigating, I'll bet they're doing the hashing based purely on the pointer address). So Ruby seems to stand alone in both allowing this behavior and having a hash implementation that leads to this indeterminate behavior.

## How does this relate to Rails?
Ah, I almost forgot. This connects to Active Record because of how ActiveRecord::QueryCache is implemented:

```ruby
def cache_sql(sql, name, binds)
  @lock.synchronize do
    result =
        if @query_cache[sql].key?(binds)
          @query_cache[sql][binds]
        else
          @query_cache[sql][binds] = yield
        end
    result.dup
  end
end

# https://github.com/rails/rails/blob/v7.0.4/activerecord/lib/active_record/connection_adapters/abstract/query_cache.rb#L127-L141
```

If you don't remember what the query cache is, it's an enabled-by-default middleware for ActiveRecord that caches read queries to prevent suboptimal code from hammering the database unnecessary. It gets reset after every request, and for the most part, it works great with no need to notice it working. But at Enova, we saw a case where the cache was producing false positives, which led me down this whole path.

Anyway, taking a look at the code again, the key thing is that `binds` will (if `bound_parameters` is on) hold a reference to a hash passed into a `where` clause. So this snippet demonstrates the same actual Ruby hash bug that we've just solved:

```ruby
criteria = { thing: "one" }
results_one = MyModel.where(some_col: criteria)

criteria.merge!( other: "stuff" }
results_two = MyModel.where(some_col: criteria)
# 1/256 chance that results_two incorrectly gets the same data as results_one!
```

This is the bug that I reported in [rails/rails#46044](https://github.com/rails/rails/issues/46044):

{% embed https://github.com/rails/rails/issues/46044 %}

Tenderlove (aka Aaron Patterson) was able to quickly fix it, though, by dup-and-freezing any hash values passed into ActiveRecord query conditions:

{% embed https://github.com/rails/rails/pull/46048 %}

## Conclusion
Hopefully you found this entertaining and a little informative. Maybe you're wondering, is this actually a bug in Ruby itself? Certainly it feels like a design flaw. When I get around to it, perhaps soon, I plan to post this to the Ruby mailing list to at least see some core developers' thoughts on it.