Go language spec violations during iteration

[prattmic]

As promised in golang/go#54766 (comment), some issues I discovered with this design while creating the Go runtime version.

As a reminder, the language spec states: "The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. If a map entry that has not yet been reached is removed during iteration, the corresponding iteration value will not be produced. If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next. If the map is nil, the number of iterations is 0."

For what it's worth, your All just states "The map can be mutated during iteration, though there is no guarantee that the mutations will be visible to the iteration." which is less restrictive as written, but for the purposes of this issue I am assuming the spec definition.

Entries deleted after grow may be produced

Suppose:

1. Start iteration
2. Add new entries to the map, enough to trigger the map to grow.
3. Delete an entry that existed prior to iteration start.
4. Continue iteration; deleted entry may be produced.

Per the spec above, deleted entries must not be produced during iteration.

This occurs because iterations snapshots the groups in the current bucket during iteration.

Snapshotting makes handling ordering across resize/split simple. Resize will replace the groups, and the entries will be shuffled in the new groups. By continuing to iterate over the old groups, we don't need to worry about the shuffling. This takes advantage of "If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped." because new entries will go into the new groups and iteration will skip them entirely.

But deletion will also target only the new groups, so iteration will still see the deleted entries.

In the runtime, iteration still snapshots the groups. I handle this problem by making iteration detect if the bucket (called a table in the runtime) has grown, and if so we consult the grown table to see if the entry still exists before returning the entry. Things get complicated for NaNs, but otherwise it is straightforward.

Entries updated after grow may be stale

Same issue as above, except instead of deleting an entry after grow, you change its value. Because iteration is using the old groups snapshot it won't see the new value and will return the old one instead.

The fix is the same as above, but it is important to return the value from the new groups, not just check existence.

While writing this bug report I realized that the spec doesn't explicitly guarantee that iteration won't produce stale entries. I think that is an oversight in the spec and I'll look into fixing it.

Rehash in place shuffles groups

Resize and split allocate new groups, so iteration snapshots work fine. However, rehash in place uses the same groups (hence "in place"), reordering the entries to eliminate tombstones.

If this occurs in the middle of iteration on a bucket, the entry order will be completely shuffled and iteration may miss entries or produce duplicate entries.

I did not find a good solution to this problem and eliminated rehashing in place from the runtime implementation. An alternative would be "same size resize", which allocates new groups of the same size, copying the entries over to eliminate tombstones. I have not done this in the runtime, but it is a potential follow-up.

[petermattis]

Thanks for the detailed report, @prattmic. I had notifications turned off on this repository accidentally so didn't notice when this was filed. Let me give some thought to whether this is worth fixing in cockroachdb/swiss given that most folks should probably just rely on the Go maps implementation at this point. That is, it might be easier to just redefine the iteration behavior in cockroachdb/swiss to match the implementation and note how it differs from the Go spec.

[thepudds]

In case it helps, I had put together a small test program a while ago that shows entries that are present in a swiss.Map can be skipped during an iteration or seen twice (because a bunch of tombstones not related to those entries are created in the middle of the iteration). In other words, the iteration is not representative of a snapshot for those keys.

https://go.dev/play/p/CdvNGlkS6nH?v=goprev

It's runnable as a test on the playground. Here's a sample result:

=== RUN   TestSwissIteration
    prog_test.go:75: key 7 was always in swiss.Map but not seen during iteration. seed=0 rehash=37 startSize=100
    prog_test.go:75: key 89 was always in swiss.Map but not seen during iteration. seed=0 rehash=37 startSize=100
    prog_test.go:75: key 39 was always in swiss.Map but not seen during iteration. seed=0 rehash=37 startSize=100
    prog_test.go:75: key 72 was always in swiss.Map but not seen during iteration. seed=0 rehash=37 startSize=100
    [...]
    prog_test.go:45: duplicate key 91 during swiss.Map iteration
--- FAIL: TestSwissIteration (0.00s)

(I think that shows behavior that might also be partially or fully covered in #33 and #20).

[thepudds]

Hi @petermattis, just to briefly close the loop -- I had mentioned back in October or so in #33 (comment) that I had looked into fixing the spec compliance shortly after you first published your map.

My WIP approach was basically:

• use an iterated atomic.Bool to track if an iteration had ever occurred
• when about to do a in place rehash, check that bool. If false, rehash as today. If true, do a same-size grow.

The bool was tracked on the table, including so that a table that had been iterated could naturally age out (e.g., in case iteration was not continually happening).

I paused that, but now have a draft CL for the runtime map that takes a similar approach. (I haven't sent that CL yet, but plan to do so soon-ish, but it needs some clean up and some additional benchmarking to see that a one-time atomic load for most table iterations was reasonable).

Feel free to point it out if that sounds like a fatally flawed approach 😅, though if it is flawed, I'm sure others will point that out on the Go issue tracker or Gerrit.

And something I didn't tackle for the map here was getting the golden data if a key was updated. (The pre-swiss runtime map would do lookups in the current table as needed to find latest data, and so would thepudds/swisstable, though the approach there was a bit different).

In any event, it seems highly reasonable to redefine the API here to exactly match the implementation. (From some brief grepping/searching the CockroachDB repos at the time, I didn't see any instances of this map being used to iterate, so I thought it might be an academic problem from the CockroachDB perspective).

And of course, your implementation has now evolved into the runtime standard map, and many gophers will benefit from it there. 🚀 From one random gopher, I'll just say thanks again for doing this and taking the time to set up your implementation to work well as the runtime map, and it was truly a pleasure reading your implementation.

[petermattis]

I don't see any issue with what you're describing, but I've paged out the details of the implementation so I could be missing something. I'm pretty sure the usage of cockroachdb/swiss in Pebble doesn't have an issue with the current implementation. We may switch to using the Go runtime map implementation at some point which suggests fixing the implementation here isn't worth the effort.

Thanks for taking the time to write this all up and help with the Go runtime map implementation.