{"id":13191,"date":"2016-04-18T02:00:38","date_gmt":"2016-04-18T02:00:38","guid":{"rendered":"http:\/\/www.planetcassandra.org\/?p=13191"},"modified":"2017-10-30T19:16:39","modified_gmt":"2017-10-30T19:16:39","slug":"cassandra-native-secondary-index-deep-dive","status":"publish","type":"post","link":"https:\/\/www.doanduyhai.com\/blog\/?p=13191","title":{"rendered":"Cassandra Native Secondary Index Deep Dive"},"content":{"rendered":"

The native secondary index is the less known and most misused feature of Cassandra.<\/p>\n

In this article we’ll explain thoroughly the technical implementation of native secondary index
\nto highlight best use-cases<\/strong> and the worst anti-patterns<\/strong>.<\/p>\n

For the remaining of this post Cassandra == Apache Cassandra\u2122<\/p><\/blockquote>\n

\n

A General architecture<\/h2>\n

Let’s say that we have the following users<\/em> table:<\/p>\n

 CREATE TABLE users(\r\n     user_id bigint,\r\n     firstname text,\r\n     lastname text,\r\n     ...\r\n     country text,\r\n     ...\r\n     PRIMARY KEY(user_id)  \r\n );\r\n<\/pre>\n
Such table structure only allows you to lookup user by user_id<\/em> only. If we create a secondary index on the column country<\/em>, the index would be a hidden table with the following structure<\/p>\n
CREATE TABLE country_index(\r\n    country text,\r\n    user_id bigint,\r\n    PRIMARY KEY((country), user_id) \r\n);\r\n<\/pre>\n
The main difference with a normal<\/em> Cassandra table is that the partition of country_index<\/em> would not be distributed using the cluster-wide partitioner (e.g. Murmur3Partitioner<\/strong> by default).<\/p>\n
Secondary index in Cassandra, unlike Materialized Views<\/a><\/strong>, is a distributed index<\/strong>. This means that the index itself is co-located with the source data on the same node. See an example below:<\/p>\n
\"Distributed
Distributed Index<\/p><\/div>\n
The technical rationales to store index data along-side with original data are:<\/p>\n
    \n
  1. reduce index update latency and the chance of lost index update<\/li>\n
  2. avoid arbitrary wide partitions<\/li>\n<\/ol>\n
    Indeed if the index data has to be distributed across the cluster as normal data using the configured partitioner, we would face the same issue as with Materialized Views<\/strong> e.g. how to ensure that the index data has been written effectively to disk before acknowledging the mutation to the client.<\/p>\n
    A synchronous write of index data will definitely kill down the write latency and we’re not even considering Consistency Level<\/strong> into the game<\/p>\n
    By co-locating the index data on the same node as source data, a write to a table with index just costs an extra local mutation when flushing original data to SSTables (more details about it in the next chapter).<\/p>\n
    The second advantage of distributed index is to avoid arbitrary wide partitions. If we were to store in a single partition the country index, there will be 60 millions+ cells for the single FR<\/strong> country (assuming that we index all FR<\/strong> population). Imagine how wide the CN<\/strong> partition would be …<\/p>\n
    \n
    B Local write path<\/h2>\n
    The write path to a table having native secondary index is exactly the same as for a normal table with respect to commit log. Whenever a mutation is applied to base table in memory (memtable<\/strong>), it is dispatched as notification to all registered indices on this table so that each index implementation can apply the necessary processing.<\/p>\n
    The native secondary index implementation just creates an inverted index for the hidden index table. It handles 3 types of operations:<\/p>\n
      \n
    1. insert of new CQL row<\/li>\n
    2. update of CQL row<\/li>\n
    3. delete of CQL row<\/li>\n<\/ol>\n
      For scenario 1. the index just creates a new entry (partition key + clustering columns<\/em>) into the index table.<\/p>\n
      For scenario 2. it is a little bit more involved. This scenario only occurs IF AND ONLY IF<\/strong> the new mutation is replacing a value that is still contained in the memtable. In this case, because Cassandra still has the previous value to be indexed, it will pass the previous and new value to the secondary index. The index manager will then remove the entry for the previous indexed value and add a new one for the new indexed value.<\/p>\n
      Scenario 3. is pretty straightforward, the secondary index just writes a tombstone to the index entry<\/p>\n
      Index memtable and base memtable will generally be flushed to SSTables at the same time but there is no strong guarantee on this behavior. Once flushed to disk, index data will have a different life-cycle than base data e.g. the index table may be compacted independently of base table compaction.<\/p>\n
      An interesting details to know is that the compaction strategy<\/strong> of the secondary index table inherits from the one chosen for the base table.<\/p>\n
      \n
      C Index data model<\/h2>\n
      Now let’s look further in details how the schema for the inverse index is designed. Suppose we have a generic table<\/p>\n
      CREATE TABLE base_table(\r\n    partition1 uuid,\r\n    ...\r\n    partitionN uuid,\r\n    static_column text static,\r\n    clustering1 uuid,\r\n    ...\r\n    clusteringM uuid,\r\n    regular text,\r\n    list_text list,\r\n    set_text set,\r\n    map_int_text map<int, text>,\r\n    PRIMARY KEY((partition1, ..., partitionN), clustering1, ... , clusteringN)\r\n);\r\n<\/pre>\n
      1) Index on regular column<\/h4>\n
      Suppose that we create an index on regular text<\/em> column, the schema of the index table will be:<\/p>\n
      CREATE TABLE regular_idx(\r\n    regular text,\r\n    partitionColumns blob,\r\n    clustering1 uuid,\r\n    ...\r\n    clusteringM uuid,\r\n    PRIMARY KEY((regular), partitionColumns, clustering1, ..., clusteringM)\r\n);\r\n<\/pre>\n
      The partition key of regular_idx<\/em> is the indexed value (regular<\/em>) itself. The clustering columns are composed of:<\/p>\n