These are mostly notes from the 2009-12-03 mtg.

Terminology

An index maps from keys to object identifiers (a.k.a. primary keys, but that's confusing in this context).

Note that this is distinct from the hash table that maps from OIDs to objects.

All 4 types of functions might appear in a RAMCloud application:

1. Not injective, not surjective - Keys may correspond to more than one OID, and not every OID corresponds to a key.
2. Not injective, surjective - Keys may correspond to more than one OID, but every OID corresponds to at least one key.
3. Injective, not surjective - Every key corresponds to exactly one OID, but not every OID corresponds to a key.
4. Injective, surjective (bijective; one-to-one) - Every key corresponds to exactly one OID, and every OID corresponds to exactly one key.

Multi indexes handle the not injective cases (1 and 2), while unique indexes handle the injective cases (3 and 4).

Requirements

Claim: Though multi indexes are more general, server-side unique indexes are also necessary

Consider everyone's favorite example of an employees table in which no two employees have the same employee ID, SSN, or username. ...

Claim: Given both multi and unique indexes, an application can use all 4 types of functions efficiently.

...

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

...

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

...

Server-side API

...

Exploring Relaxed Consistency

...