Implement the SCAN Redis command

[hengestone]

In order to make searching more useful.

[hectorgcr]

Thanks for the input @hengestone

I will be writing a design document for this feature and will share it here once it's ready.

[rahuldesirazu]

SCAN cursor [MATCH pattern] [COUNT count]

https://redis.io/commands/scan

Overall Notes

In a nutshell, SCAN is a cursor based function that returns all redis keys in a cluster. Here are a few important pieces from the spec:

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 only returns elements that were present at some point during the 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.

Calling SCAN with a broken, negative, out of range, or otherwise invalid cursor, will result into undefined behavior but never into a crash. What will be undefined is that the guarantees about the returned elements can no longer be ensured by the SCAN implementation.

It is important to note that the Match filter is applied after elements are retrieved from the collection, just before returning data to the client.

Count is just a hint for the implementation, however generally speaking this is what you could expect most of the times from the implementation.

Count

The Redis default is 10, and we will default to the same value. The specified count cannot be too large, or else the proxy might end up processing too many keys at once. Therefore, we should have some threshold gflag such that if count is larger than this number, we default to the threshold.

Match

Most importantly, the match filter is applied after all the elements have been retrieved and right before the set is returned to the client. With this in mind, we will designate the tserver to apply the filter, and return as part of the response to the proxy, both the number of total keys seen, and the list of keys that match the filter. This will result in less memory used on the proxy for processing, especially if the filter matches very few keys and the count is high.

Cursor

The return value of the cursor is a string representing an unsigned 64 bit number. Some redis clients take a string parameter for the cursor, while others take an unsigned long. For the current implementation, we plan to designate the first 2 bytes for the hash code, and the next 6 bytes representing the first 6 characters of the next key to start at. When we iterate using the cursor, we use to the first 2 bytes to find the appropriate hash partition and then seek to the smallest key starting with those 6 bytes. This could potentially end up repeated keys if multiple keys with the same 6 byte prefix

In a future implementation, we could have a string cursor implementation that returns : so that we can seek directly to the key just larger than the last key and not repeat any elements. Some clients only support long cursors, so depending on the format received by the redis server, the server will either do the long SCAN as described above or the string SCAN which would directly seek to the next largest key. The string cursor for the start of the collection would be represented as “0:” instead of “0”.

In the case of a corrupted cursor being used, we should error out to the client.

We need to worry about SCAN not terminating if one hash value has more keys with a certain prefix than the count specified in the query, since it can keep repeating the same keys on each iteration without moving on the next hash value. Since count is an implementation hint and not a requirement, to work around this we can process more keys than count until we are at a prefix greater than what we started at. As long as the cursor changes between calls, we are making progress and SCAN will eventually return to 0.

[mbautin]

@rahuldesirazu: I think we could do some optimizations for the pattern case. We could restrict the range of primary keys to scan in case the pattern does not start with a *. For each tablet, we can start scanning, find an existing hash value, and immediately seek to the earliest key with that hash value that could match the pattern. When we scan all the keys with this hash value that match the pattern, we will seek to the incremented hash value.