We have an application that has groups and entities. A group has many entities and an entity has a bunch of (attribute, value) pairs. A common access pattern is to select some number of entities within a group with attribute X equals to x and ordered by attribute Y. For efficiency, we want to build a secondary index for each group and collocate a group and its secondary index on the same node. Our current approach is to map a group to a row in Cassandra and each entity to a column in a column family (CF). Within the same row, we use a separate CF (ordered by name) to implement a secondary index, say on attribute X and Y. In this family, each column name has the form of X:x:Y:y:entityID. We extended the get_slice() function so that it can get a slice of columns starting from a given column. The extended function uses the column-level index to locate the starting column quickly. (We'd be happy to contribute this extension back to Cassandra if people find this useful). Using the extended get_slice(), we were able to access the entities through the simulated secondary index.
We see a couple of problems with the current approach. First, our application has to maintain the index. This is inefficient and could leave the index inconsistent when failure occurs. Second, mapping each entity to a column may not be a good idea. Often, there is some sort of locking for each row access. Putting many entities per row limits concurrency. Today, in Cassandra, a full row is deserialized into memory during compaction. This limits the number of entities that can be put in a single row. Also, intuitively, an entity is more naturally represented as a row with attributes stored as columns. To address the above problems, we are thinking of the following new implementation. Each entity is mapped to a row in Cassandra and uses a two-part key (groupID, entityID). We use the groupID to hash an entity to a node. This way, all entities for a group will be collocated in the same node. We then define a special CF to serve as the secondary index. In the definition, we specify what entity attributes need to be indexed and in what order. Within a node, this special CF will index all rows stored locally. Every time we insert a new entity, the server automatically extracts the index key based on the index definition (for example, the index key can be of the form "hash(rowkey):attribute1:attribute2:rowkey) and add the index entry to the special CF. We can then access the entities using an extended version of the query language in Cassandra. For example, if we issue the following query and there is an index defined by (attributeX, attributeY), the query can be evaluated using the index in the special CF. (Note that AppEngine supports this flavor of queries.) select attributeZ from ROWS(HASH = hash(groupID)) where attributeX="x" order by attributeY desc limit 50 We are in the middle of prototyping this approach. We'd like to hear if other people are interested in this too or if people think there are better alternatives. Jun IBM Almaden Research Center K55/B1, 650 Harry Road, San Jose, CA 95120-6099 [email protected]
