Secondary Indices

[ashwin153]

Indexed fields of type F of a struct T are added and removed from an index of type Map[F, Reference[T]] on object creation and deletion. You could search and iterate the index to perform range queries. Related to #72.

struct Foo {
  x: Indexed[String]
}

[ashwin153]

We can build indexes using a radix tree. Caustic tries to make sure that related values have related keys. For example, fields foo and bar of an object xyz will have keys xyz$foo and xyz$bar. Because keys often have common prefixes, a radix tree is a good candidate for an indexing structure.

We can implement radix trees in Caustic as a hierarchical Map, and we can use Caustic's transactional guarantees to safely build and update these indexes on demand. Consider the following object.

struct Foo {
  bar: Int
}

Let level0 = Map[String, String]&("$Foo$bar") be the first level of the index. Once a particular level reaches a certain size, keys with common prefixes will be grouped together into a new level. Keys in a level are values of bar and values are either keys at which the corresponding Foo object for particular value of bar can be found or at which another level of the index can be found. To distinguish between the two, we'll suffix the key with a $ when its value points to another level.

Lookups, updates, and deletions have straightforward implementations once the index is constructed. However, the initial construction of the index is not trivial. In order to prevent modifications to fields while an index is being built for it, we'll use a special indexing key for each field to determine when an index build is in progress. Write operations on the field will implicitly read the indexing key, and will fail if it is true. To build an index on a field, a transaction to set indexing = true is committed. Then, a quorum scan is performed for all values of the field. Finally, a transaction that constructs the index and sets indexing = false is committed. This procedure blocks values from being created or modified while the index is built, without impacting performance in the general case.