Page Comparison

...

• Each table can have one or more named indexes associated with it.
• An index maps from a key to one or more object identifiers.
• An index knows nothing about the actual objects and never touches them; it deals exclusively in keys and object identifiers, which are provided to it.
• Indexes take two forms:
  • Exact match (based on hash table)
  • Ordered (based on trees, with keys that can be strings, integers, or floating-point numbers)
    • Provide an extension mechanism for custom comparison functions?
• Operations:
  • addIndexEntry(objectId, index, key)
    • Creates a new entry in an index associated with a particular table.
    • "index" name and index associated with objectId's table.
    • "key" is the value associated with this index entry (string, integer, etc.)
  • findEntries(table, index, key1, key2)
    • Returns object identifiers for all objects in a particular index for a particular table whose keyis in the range between "key1" and "key2".
    • May want additional options to exclude endpoints of range (or, just filter on the client side?).
  • deleteEntry(table, index, key)
• With this approach, indexing is explicit:
  • The application must explicitly request the creation of an index entry, either
    at the same time that it creates/updates the corresponding object, or in a separate operation.
  • The application must also explicitly request the deletion of an index entry when it believes the corresponding object.
  • The keys used for indexes need not necessarily consist of data fields from the objects in the table, and not every object in a table necessarily must be indexed.
  • The same object can appear multiple times in a single index, under different keys.
• This approach makes indexes almost completely separate from objects:
  • No need for them to be stored in the same place, for example.
  • But, can't store the objects inline in the index, so an additional RPC will be required to fetch the objects once the index has returned their identifiers.
  • May not be able to guarantee consistency between index and table.

...

• The client-side library should be smart enough to figure out which servers it needs to contact.
  • For a range-based index, there will be enough configuration information to identify the range of keys stored on each server, so the client-side library can pick relevant server(s).
  • For an exact-match index the configuration information will include enough information about the hashing function for the client-side library to compute the hash and map it to a particular server. In fact, perhaps servers do not even have to know what the hash function is: incoming requests include a hash value plus the original key.
• It should be possible to use the same approach to configuration consistency here as for name-based lookups.

Other issues related to indexes that are split across multiple servers:

• Is this a good idea? Would it be better to keep an index entirely on a single machine if possible?
• How to decide when to change the server assignments for an index?
• How to make these changes while the system is running?

What about consistency between objects and their indexes?

• Approach #1: no help from RAMCloud: the client-side library first creates an object, then creates indexes for it. Same for updates and deletions.
  • Hard to maintain consistency (e.g., the client might crash between creating the object and creating its index entries).
• Approach #2: servers manage consistency:
  • During a create or update or delete, the client can provide key values and index names.
  • The server automatically updates the index(es) along with the object.
  • The server logs this information along with other data about the operation, so it will be recovered properly after a crash.

What about crash recovery for indexes?

• If index changes are logged by the object servers, this can help with crash recovery.
• But, don't want to reread entire logs to reconstruct an index.
• Will need some sort of checkpointing mechanism for indexes.

Miscellaneous Notes