SSCAN returns incorrect results if items are removed from the set between executions

[daniel-wise-ansys]

Describe the bug

If you perform an SSCAN and get a cursor, then remove items from the set, then do another SSCAN using the previously returned cursor you can get incorrect results. It looks like this is because the returned cursor is simply the position in the set for the last entry returned, so if the size of the set changes it refers to the wrong position.

Steps to reproduce the bug

1. Create a set with 2 entries: SADD test-set entry-a entry-b
2. Perform an SSCAN: SSCAN test-set 0 COUNT 1 - this returns cursor 1
3. Remove the first entry: SREM test-set entry-a
4. Perform another SSCAN using the previously returned cursor: SSCAN test-set 1 COUNT 1 - this returns no results instead of the expected entry-b

Expected behavior

Using the cursor returned before the set was modified should return the remaining set entries - this is the behaviour in other Redis-like datastores.

Screenshots

No response

Release version

No response

IDE

No response

OS version

No response

Additional context

No response

[kevin-montrose]

My read of Redis's documentation around SCAN/SSCAN/HSCAN/etc. is that this is expected behavior.

Full quote:

The SCAN command, and the other commands in the SCAN family, are able to provide to the user a set of guarantees associated to full iterations.

• A full iteration always retrieves all the elements that were present in the collection from the start to the end of a full iteration. This means that if a given element is inside the collection when an iteration is started, and is still there when an iteration terminates, then at some point SCAN returned it to the user.
• A full iteration never returns any element that was NOT present in the collection from the start to the end of a full iteration. So if an element was removed before the start of an iteration, and is never added back to the collection for all the time an iteration lasts, SCAN ensures that this element will never be returned.

However because SCAN has very little state associated (just the cursor) it has the following drawbacks:

• A given element may be returned multiple times. It is up to the application to handle the case of duplicated elements, for example only using the returned elements in order to perform operations that are safe when re-applied multiple times.
• Elements that were not constantly present in the collection during a full iteration, may be returned or not: it is undefined.

Emphasis on the last line added by me.

[daniel-wise-ansys]

I disagree, I think the first bullet point in that quote is what applies in this situation:

• A full iteration always retrieves all the elements that were present in the collection from the start to the end of a full iteration. This means that if a given element is inside the collection when an iteration is started, and is still there when an iteration terminates, then at some point SCAN returned it to the user.

In my example, entry-b is present in the set before the SSCAN starts, and is still there when it ends, so at some point it should have been returned.

[kevin-montrose]

In my example, entry-b is present in the set before the SSCAN starts, and is still there when it ends, so at some point it should have been returned.

You're correct, I misread your example as removing entry-a.

---

Source of the bug is probably right here, which assumes HashSet enumeration order is stable.

[MatanTsach]

Hi, I'd like to take a crack at this.

As @kevin-montrose identified, the bug is in the Scan method in SetObject.cs — the cursor is a simple positional index into the HashSet enumeration, so removals (or additions) between SSCAN calls shift element positions and cause the cursor to skip or re-visit elements.

Proposed fix: Replace the positional cursor with a hash-code-based cursor. Instead of tracking "I'm at position N in the enumeration," the cursor will represent a boundary in the hash-code space. On each SSCAN call, elements are collected by hash code range (>= cursor), sorted by hash code for deterministic ordering, and returned in batches. This makes the cursor resilient to set mutations between calls, matching Redis's guarantee that elements present throughout a full iteration are always returned.

Note: the same pattern exists in HashObject.Scan and SortedSetObject.Scan — I'll focus on the Set fix first and can follow up with the others if desired.

[badrishc]

This would be quite expensive as we have to materialize the entire iteration in memory and sort it, plus how would we handle hash code duplicates that cross the boundary?

[MatanTsach]

Thx for feedback @badrishc — you're right on both points. Sigh, The hash-code approach is O(n log n) per call (materialize + sort), and hash collisions crossing the boundary would need special grouping logic. After digging deeper, I don't think it's the right path.

I spent some time researching how Redis, Dragonfly, KeyDB, and Valkey handle this, and the fundamental challenge is that all correct SCAN implementations rely on direct access to hash table bucket internals:

• Redis/KeyDB/Valkey use reverse-binary-iteration over power-of-2 bucket arrays — O(1) per call, zero server-side state
• Dragonfly uses DashTable with extendible hashing — cursor packs (segment_id, bucket_id) with depth-adaptive extraction

None of these approaches can be ported to C#'s HashSet<T> because:

1. .NET uses prime-sized buckets (not power-of-2), so Redis's bit-reversal trick doesn't apply
2. HashSet<T> doesn't expose its internal _buckets or _entries arrays — CollectionsMarshal support for HashSet was closed as not-planned
3. UnsafeAccessor can reach the fields on .NET 9+, but Entry is a private nested type (not fully accessible until .NET 10's UnsafeAccessorType)

The alternatives that don't touch HashSet internals all have significant trade-offs:

• Parallel sorted structure (e.g., List<(uint hash, byte[])> maintained alongside the HashSet): O(log n + count) per scan, but adds O(log n) write overhead to every SADD/SREM and O(n) persistent memory
• Snapshot on first scan: O(n) one-time allocation, but leaks memory if the client abandons the scan mid-iteration
• Positional cursor (current approach): O(cursor) per call, broken under mutation — but this is what HashObject and SortedSetObject also use today

Given this, I think fixing SSCAN (and HSCAN/ZSCAN, which have the same positional cursor bug) properly may require replacing HashSet<byte[]> with a scan-friendly data structure that exposes bucket-level access — likely a custom power-of-2 hash table or something similar to Dragonfly's DashTable approach. That's a bigger architectural decision best driven by the core team.

Happy to help with implementation if there's a direction you'd prefer — just didn't want to push a half-fix without surfacing the full picture.