Changes in the KeyRange and KeySelector API

[KrzysFR]

After using this for quite a while, I'm making a few changes to the KeyRange and KeySelector API.

Rationale

The main issue is when trying to model open ranges, like [ 'SOME_KEY', <MAX> ) or ( <MIN>, 'SOME_KEY' ], when combined with the notion of KeySpace that restrict the keys to all that have a common prefix.

For example you want to simply do a range on "all the keys in a subspace", you have to be careful to craft a Key Range that does not escape the bounds of the current Subspace, which is a purely client-side notion introduced by the Directory Layer. The database doesn't care about subspaces and will let you happily escape into the neighboring subspaces, which is a BAD THING ™️ .

In practice, there is some sort of protection at the Partition level in the .NET binding, where all GetRanges will be bounded to the range of the Directory Partition that was used to open the IFdbDatabase instance. This at least protects you against seeing or mutating the data of another partition (for multi-tenant instances), but won't help you for subspaces within this partition.

The ideal way would be to have a way to describe an open-ended "virtual range" like [ 'KEY', +Infinity ), and then intersect it with a subspace, to obtain the actual "physical range", like [ 'KEY', ~END_OF_THE_SUBSPACE~ ) without having to do the bound checking yourself.

That way, it would be easy for the application to decide the "scope" of the range (the IKeySpace used by the Layer) while also having an implicit "global scope" (the top level partition) which act as a safeguard.

note: these changes originated from a custom embedded key/value store similar to FDB at the API level, but that was using sub-trees to model "subspaces" instead of a common key prefix. This helped solve the issue of cross-contamination between adjacent subspaces in range queries, but still exposed the "from the start" / "until the end" issue.

Changes

KeyRange

For the KeyRange struct this means that both bounds can either be a byte string literal, OR Slice.Nil to mean "open ended".

Examples;

• KeyRange.Create(begin: "A", end: "Z") defines the range "A" <= k < "Z"
• KeyRange.Create(begin: Slice.Nil, end: "K") defines the range k < "Z"
• KeyRange.Create(begin: "K", end: Slice.Nil) defines the range k >= "K"
• KeyRange.Create(begin: Slice.Nil, end: Slice.Nil) defines the empty set.
• KeyRange.Create(begin: Slice.Empty, end: Slice.Nil) selects all the keys

There is a slight difference between Slice.Empty and Slice.Nil (similar to the empty string vs null).

• For the Begin key this is usually transparent, since the empty key ('') IS the first key in the database, but you can create a range that starts "before" the first key, or "at" the first key. The only difference would be with offset, were "before the first key + 1" is the first key, while "the first key + 1" is the second key in the database.
• The same apply for the End key, where Slice.Empty would probably not make a lot of sense anyway.

In order to simplify the logic of creating selectors that maps to the Begin and End key, we add KeyRange.GetBeginSelector() and KeyRange.GetEndSelector(bool reverse) helpers which handle all cases. The later method has a bool reverse parameter which helps resolve forward vs reverse Range Reads, that have slightly different semantics (End key being included or not).

Bonus: default(KeyRange) will be the range with Begin and End equal to Slice.Nil and so represent the empty set, which fits well with the usual way empty structs are defined.

KeySelector

For the KeySelector struct, the most visible change is the introduction of "special" selectors like KeySelector.Zero() which represents the first possible key in the database, and KeySelector.Infinity() which points to "after" the last possible key in the database (the end key is usually excluded in range queries, so this will include the last key in practice).

These special selectors would be represents by having the Key equal to Slice.Nil, and then using the value of the offset has an enumeration (0 for Zero, int.MaxValue for Infinity). We could then use other values to encode other special selectors in the future.

This selectors would be automatically resolved client side, because they are not understood by FoundationDB itself: the native handler code MUST convert them into a valid bound if the user forgot to do it, either using the Directory Partition range, or in the last resort, bound them to [ \x00, \xFF ) which is the "legal" key ranges for FoundationDB. Or maybe to [ \xFF, \xFFFF ) for ranges operating in the System Key Space.

IKeySpace

We need an easy way to intersect an open-ended range like [ 'KEY', +Infinity ) with a key space, to return the truncated range [ 'KEY', FirstEqualOrGreater(KeySpace.ToRange().End ).

All implementation of FdbDirectorySubspace and FdbDirectoryPartition would use their defined ranges to do this transformation, but the user could create its own custom KeyRange to achieve something similar.

I think that we could use a set of methods similar to ToRange() on subspaces, but that creates a KeySelector or KeySelectorPair. The keys of the selectors passed to it could also automatically be expanded/encoded and prefixed with the keyspace key?

A few possible candidates:

KeyRange range = location.StartsWith([SOMEPREFIX]);
KeySelector sel = location.FirstGreaterThanOrEqual([SOME_KEY]);
KeySelector sel = location.LessThan([SOME_KEY]);