...

Claim: It is useful to know at index creation whether an index will be unique or multi.

...A multi index is probably best implemented as a hash table or tree of key/list-of-OID pairs, while a unique index is probably best implemented as simply a hash table or tree of key/OID pairs.

Hypothesis: Range-queryable indexes are best implemented as trees, while other indexes are best implemented as hash tables.

..We seem to think hash tables are faster, since we use them for the primary indexes. If this turns out not to be the case for secondary indexes, all indexes will be range-queryable.

Server-side API

...

Exploring Relaxed Consistency

...

Unique Indexes:

Insert(key, oid) -> err on duplicate key
Remove(key, oid) -> err on nonexistent key/OID pair
Lookup(key) -> oid or err on nonexistent key

Multi Indexes:

Insert(key, oid)
Remove(key, oid) -> err on nonexistent key/OID pair
Lookup(key) -> list of OIDs

Range Queries (same for unique and multi)

RangeQuery(key start (optional), bool inclusive, key end (optional), bool inclusive, int limit, oid start_after_oid (optional)) -> list of key/OID pairs or list of OIDs only (sorted by keys, then OIDs), whether more data was available and not returned

Exploring Relaxed Consistency

Insert in the unique case throws an error if there's a concurrent transaction with the same key

Lookup and RangeQuery return candidate OIDs