by 盛楠、邓侃

1。Primary Index

假设我们有这么一个 ColumnFamily, 它是一个地址本，包含 5 行记录，例子如下。

AddressBook = { // 这是一个 ColumnFamily，每一行包含 4 个 columns。

  "John"：{ //第一行数据的 Row-key。
            {name: "street", value: "Howard street", timestamp: 123456789}, // 这是一个 Column
            {name: "zip", value: "94404", timestamp: 123456789},
            {name: "city", value: "Forest", timestamp: 123456789},
            {name: "state", value: "VA", timestamp: 123456789}
          }, // 第一行数据结束。
  "friend1":  {   //第二行数据的 Row-key
            {name: "street", value: "8th street", timestamp: 123456789},
            {name: "zip", value: "90210", timestamp: 123456789},  
            {name: "city", value: "Beverley Hills", timestamp: 123456789},
            {name: "state", value: "CA", timestamp: 123456789}
         }, // 第二行数据结束。
  "Kim"： {   //第三行数据的 Row-key
            {name: "street", value: "X street", timestamp: 123456789},
            {name: "zip", value: "87876", timestamp: 123456789},
            {name: "city", value: "Balls", timestamp: 123456789},
            {name: "state", value: "VA", timestamp: 123456789}
         }， // 第三行数据结束。  
  "William"：{  // 第四行数据的 Row-key
            {name: "street", value: "Armpit Dr", timestamp: 123456789},
            {name: "zip", value: "93301", timestamp: 123456789},
            {name: "city", value: "Bakersfield", timestamp: 123456789},
            {name: "state", value: "CA", timestamp: 123456789}
         }, // 第四行数据结束。
  "joey"：{  // 第五行数据的 Row-key
            {name: "street", value: "A ave", timestamp: 123456789},
            {name: "zip", value: "55485", timestamp: 123456789},
            {name: "city", value: "Hell", timestamp: 123456789},
            {name: "state", value: "NV", timestamp: 123456789}
         }  // 第五行数据结束
} // "AddressBook" ColumnFamily 结束。


假如当初在建这个 ColumnFamily 的时候，我们设定它按 UTF8Type 排序,那么这个 CF 在硬盘上的存储顺序为，

AddressBook = { // 这是一个 ColumnFamily，每一行包含 4 个 columns。
  "friend1":  {{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},   
  "John"：{{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},   
  "joey"：{{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},
  "Kim"： {{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},  
  "William"：{{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}}
}


先假设这个 ColumnFamily 的所有数据，都存放在同一台服务器的硬盘里。如果要搜索“John”的地址，那将是一件很容易的事情。

这是因为，在 AddressBook 这个 ColumnFamily 中，所有的行，都已经以 row-key 为基准，按顺序排列。所以无论是二分查找，还是使用其它什么搜索算法，实现起来都不是难事儿。

但是假如这个 AddressBook CF 有很多行，单台服务器的硬盘存放不下。解决的办法是把AddressBook CF 按行分割，某些行存放在一台服务器中，另一些行存放在另一台服务器中，依此类推。

按行分割的办法有两种，一个是 OrderPreservingPartitioner 另一个是 RandomPartioner。

如果按 OrderPreservingPartitioner 分割，“John”所在的行，与“joey”所在的行，很有可能被存放在同一台服务器的硬盘里。

如果按 RandomPartioner 分割，先对“John”和“joey”这些 Row-Keys 进行哈希，根据哈希的结果，决定在哪一台服务器，存放该行记录。这样做，“John”所在的行，与“joey”所在的行，很有可能被存放在不同的服务器的硬盘里。

小结一下，按 Row-Key 建索引，以便搜索，这叫 Primary Index。


2。Secondary Index

假如我们想在这个 AddressBook CF 中搜索，有哪些人居住在“CA”州？那么我们需要另建一个索引，即 Secondary Index。

有三种构建 Secondary Index 的方法。沿用 AddressBook CF 这个例子，解释如下。

  2.1. Wide Row

给每个州设一行，每行中包含若干 Columns，每个 Column 对应着 AddressBook CF 中的某一行的 Row-Key，细节如下。

ResidentialIndex = { // 这是一个 ColumnFamily。

  "CA"：{ //第一行数据的 Row-key。
          {name: "friend1", value: null, timestamp: null}, // 这是一个 Column
          {name: "William", value: null, timestamp: null}  // 这也是一个 Column
        }, // 第一行数据结束。

  "NV"：{   
          {name: "joey", value: null, timestamp: null}
        }, // 第二行数据结束。

  "VA"：{   
          {name: "John", value: null, timestamp: null},
          {name: "Kim",  value: null, timestamp: null}
        } // 第三行数据结束。

} // "ResidentialIndex" ColumnFamily 结束。

假如我们想搜索某个州，例如“CA”， 居住着哪些人。 我们只需要在 ResidentialIndex CF 中，按“CA” ，找到相应的行。然后取出这一行包含的所有 Columns 即可。


  2.2. SuperColumn

前述的办法，为每一个州设立一行。由于 Cassandra 是一个分布式系统，它可能会按行，把 ColumnFamily 分割，并把分割后的各个行，分别存放到不同的服务器上。

如果想把ResidentialIndex CF的所有数据，都存放在同一台服务器上，办法是不要为每一个州设立一行，而是把所有州的数据，通通合并成一行。

我们可以用 SuperColumn 的实现方式，来达到这个目的。

ResidentialIndex = { // 这是一个 ColumnFamily。

  "StateIndex"：{ // 一行数据可以存放所有州的居民。
      "CA": {   // 第一个 SuperColumn 数据。
          {name: "friend1", value: null, timestamp: null}, // 这是一个 Column
          {name: "William", value: null, timestamp: null}  // 这也是一个 Column
        }, // 第一个 SuperColumn 数据结束。

      "NV"：{   // 第二个 SuperColumn 数据。
          {name: "joey", value: null, timestamp: null}
        }, // 第二个 SuperColumn 数据结束。

      "VA"：{   // 第三个 SuperColumn 数据。
          {name: "John", value: null, timestamp: null},
          {name: "Kim",  value: null, timestamp: null}
        } // 第三个 SuperColumn 数据结束。
   },  // 第一行 Index 数据结束。

  "CityIndex"：{ ... } // 同一个 ResidentialIndex CF 可以存放多个 Indices。

} // "ResidentialIndex" ColumnFamily 结束。

SuperColumn 的办法，优点在于，可以使所有 ResidentialIndex CF 的数据，基本存放在同一台服务器中，但是也存在一些缺点。在[1]的第25页，提及使用 SuperColumn 来构建索引，可能对系统的性能，会造成较大损害。

虽然[1]没有深入并且定量地分析 SuperColumn Index对于系统性能的损害，但是借鉴前人的经验， 如果能够使用其它方式构建Index，我们就应当尽量避免使用SuperColumn Index 这种方式。

  2.3. CompositeColumn

正如前边所说的，SuperColumn存在一些问题。作为一个变通的办法，可以把 SuperColumn 的 Name，与 SuperColumn 下每个 Column 的 Name，组合起来，形成一个复合的 Column Name，即 CompositeColumnName。延续前面的例子。

ResidentialIndex = { // 这是一个 ColumnFamily

  "StateIndex"：{ // 只用一行数据，来存放所有州的所有居民。
      {name: "CA-friend1", value: null, timestamp: null}, // 这是一个 Column
      {name: "CA-William", value: null, timestamp: null}, // 这也是一个 Column
      {name: "NV-joey", value: null, timestamp: null},
      {name: "VA-John", value: null, timestamp: null},
      {name: "VA-Kim",  value: null, timestamp: null}
   },  // 第一行 Index 数据结束。

  "CityIndex"：{ ... } // 同一个 ResidentialIndex ColumnFamily 可以存放多个 Indices。

} // ResidentialIndex CF  结束。

要取出所有 CA 州的居民，只需要找到相关的 Columns，它们的 Column Name 以 “CA”开头。

同时，由于在存放 CF 时，每一行中的所有的 Columns，都是以 Column Name 来排序的。换句话说，每一行中所有的 Columns，基本上是存放在一段连续的硬盘空间里。所以，在查询 ResidentialIndex CF 这样的索引时，查询效率得到大大提升。


3. 输入及更新。

虽然在 Cassandra 中，读取 Index 的效率很高，但是如果要增删改 AddressBook CF 中的数据时，ResidentialIndex CF 中的数据，也要做相应修改。

沿用前例，

AddressBook = { // 这是一个 CF，共有 5 行，每一行包含 4 个 columns。
  "friend1":  {{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},   
  "John"：{{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},   
  "joey"：{{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},
  "Kim"： {{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}},  
  "William"：{{"city": ..}, {"state": ..}，{"street": ..}, {"zip": ..}}
}

假如我们想在 AddressBook CF 中，把 "friend1" 这一行中 "state" 的值，从原先的 "CA"，改成 "NV"。我们需要连续做两件事情，

a. 我们需要更改 AddressBook CF 中，"friend1" 这一行中的 {"state": ..} 这个 column。

b. 我们还要更改 ResidentialIndex CF 中，相应的数据。

更改 AddressBook CF 包含两个动作，

a.1. 删掉 AddressBook CF 中，"friend1" 这一行的 {"state": ..} column。

a.2. 把新的 {"state": ..} column，插入到 AddressBook CF 的 "friend1" 这一行中去。

更改 ResidentialIndex CF也包含两个动作，

假如我们用 CompositeColumn 的方式，来构建 ResidentialIndex CF。原先的 ResidentialIndex CF 如下，

ResidentialIndex = { // 这是一个 ColumnFamily
  "StateIndex"：{ // 一行数据可以存放所有州的所有居民
      {name: "CA-friend1", value: null, timestamp: null}, // 这是一个 Column
      {name: "CA-William", value: null, timestamp: null}, // 这也是一个 Column
      {name: "NV-joey", value: null, timestamp: null},
      {name: "VA-John", value: null, timestamp: null},
      {name: "VA-Kim",  value: null, timestamp: null}
   },  // 第一行 Index 数据结束

  "CityIndex"：{ ... } // 同一个 ResidentialIndex CF 可以存放多个 Indices
} // ResidentialIndex ColumnFamily 结束。

更改 ResidentialIndex 的两个动作依次是，

b.1. 删掉 ResidentialIndex CF 中，"StateIndex" 这一行的{"CA-friend1": ..} column。

b.2. 构建新的 {"NV-friend1": ..} column，并插入到 ResidentialIndex CF 的 "StateIndex" 这一行中去。

从 a.1、a.2 到 b.1、b.2,这四个动作不仅要连续地、依次地进行，而且这四个动作必须全部完成，但凡一个动作没完成，前面已经完成的动作要回滚。即，

BEGIN BATCH

DELETE {"state": "CA"} FROM AddressBook WHERE KEY =‘friend1’;
DELETE {"CA-friend1": ..} FROM ResidentialIndex WHERE KEY =‘StateIndex’;

UPDATE AddressBook SET ‘state’ = ‘NV’ WHERE KEY = ‘friend1’;
UPDATE ResidentialIndex SET ‘NV-friend1’ = null WHERE KEY = ‘StateIndex’;
 
APPLY BATCH


[1][2] 认为以上办法不稳妥。理由是，同一份数据在 Cassandra 中，被保存了多个备份。万一上述四个步骤中，有个别步骤出现错误，需要回滚时，由于存在多个备份数据，哪些数据需要回滚，哪些不需要，非常混乱。同时，应该回滚到哪个版本的旧数据，也很混乱。

[1][2] 提出的办法，是另建一个 ColumnFamily，类似于日志一样，记录最近发生的更改记录。依照这个办法，我们另外再构建一个 ColumnFamily。

AddressBook_ResidentialIndex_Log = {
  "friend1":  {
     {"state" + timestamp_1 : "CA"}
  }
}

更改 "state" 的值时，我们先对 AddressBook_ResidentialIndex_Log CF 进行修改，然后再对 AddressBook CF 和 ResidentialIndex CF 进行修改。万一需要回滚时，以 AddressBook _ResidentialIndex_Log CF 的数据为基准。

SELECT * FROM AddressBook_ResidentialIndex_Log WHERE KEY = ‘friend1’;

BEGIN BATCH

DELETE {"state" + timestamp_1: "CA"} FROM AddressBook_ResidentialIndex_Log WHERE KEY = ‘friend1’;
DELETE {"state": "CA"} FROM AddressBook WHERE KEY = ‘friend1’;
DELETE {"CA-friend1": ..} FROM ResidentialIndex WHERE KEY = ‘StateIndex’;

UPDATE AddressBook_ResidentialIndex_Log SET {"state" + timestamp_2: "NV"} WHERE KEY = ‘friend1’;
UPDATE AddressBook SET {"state": "NV"} WHERE KEY = ‘friend1’;
UPDATE ResidentialIndex SET {"NV-friend1": null} WHERE KEY = ‘StateIndex’;

APPLY BATCH

[1]中的操作顺序，和上边的操作一致，我们只是把例子的内容换了一下。

但是这里有一个问题，AddressBook_ResidentialIndex_Log CF的作用是，如果没有成功完成所有步骤的操作，可以根据AddressBook_ResidentialIndex_Log CF的记录，来进行回滚。

但是根据上述操作顺序，首先删除了AddressBook_ResidentialIndex_Log中的内容。如果这样做，那么假如在执行过程中出现问题，就没有办法进行回滚了，因为AddressBook_ResidentialIndex_LogCF 中的相应内容，已经被删除了。

因此我们认为，不妨等到其它 CF 的数据，都被更新以后，到那时再更新AddressBook_ResidentialIndex_Log CF 中的内容，可能更合理。如下所示，

SELECT * FROM AddressBook_ResidentialIndex_Log WHERE KEY =‘friend1’;

BEGIN BATCH

DELETE {"state": "CA"} FROM AddressBook WHERE KEY =‘friend1’;
DELETE {"CA-friend1": ..} FROM ResidentialIndex WHERE KEY = ‘StateIndex’;

UPDATE AddressBook SET {"state": "NV"} WHERE KEY =‘friend1’;
UPDATE ResidentialIndex SET {"NV-friend1": null} WHERE KEY =‘StateIndex’;

DELETE {"state" + timestamp_1: "CA"} FROM AddressBook_ResidentialIndex_Log WHERE KEY =‘friend1’;
UPDATE AddressBook_ResidentialIndex_Log SET {"state" + timestamp_2: "NV"} WHERE KEY = ‘friend1’;

APPLY BATCH


4. Native Secondary Index。

很显然，构建 Secondary Index，以及更改 Secondary Index，是一件非常麻烦的事情，所以在 Cassandra 0.7 以后的版本中，有自动构建并更改 Secondary Index 的 APIs。

这些表面上看似简单的 APIs，封装了上述这些 Secondary Index 和 Log 等等 ColumnFamilies。

问题在于，根据前面的分析，我们知道构建 Secondary Index的办法有多种。每种构建方法，各有优缺点，应当根据不同的应用场景，选用最恰当的方法。

在前面的例子中，如果用 2.1 所述的 Wide Row 的办法，去构建 Secondary Index，为每一个州设立一行。由于 Cassandra 是一个分布式系统，它可能会按行，把 ColumnFamily 分割，并把分割后的各个行，分别存放到不同的服务器上。

如果用 2.3 所述的 CompositeColumn 的办法，把所有州的数据，通通合并成一行，这样所有 ResidentialIndex CF的所有数据，大致都存放在同一台服务器上。

把一个 ColumnFamily 的数据，集中存放在同一个服务器上，还是先把它分割，然后把各个部分，分别存放在不同的服务器上。集中存放与分布式存放，这两个办法各有优缺点。

当一个 ColumnFamily 的数据量不太大的时候，不妨把它集中存放在同一个服务器上，避免分布式存储，所导致的服务器之间的网络流量，从而提高整个系统的运行效率。

当一个ColumnFamily 的数据量很大的时候，为了避免系统性能瓶颈，以及避免单点故障，更稳妥更高效的做法，是采用分布式的办法，即，先分割 ColumnFamily，然后把各个部分，分别存放在不同的服务器上。

所以，当 ResidentialIndex CF 数据量很大的时候，2.1 的 Wide Row 的办法最适用，因为它采用的是分布式存储。

但是当ResidentialIndex CF 数据量不大的时候，最好采用 2.3 的CompositeColumn的办法，把所有居民的记录，都放在同一行中，从而在实际存储时，它们基本上被存放在同一台服务器上。

但是无论何种应用场景，Cassandra 似乎都无差别地选用在 2.3 段落中介绍的 CompositeColumn 的办法，去构建 Secondary Index。

所以，选用 Cassandra APIs，去自动构建和更新 Secondary Index，好处是使用方便，坏处是有可能会对系统效率造成影响。


Reference，

[1] Cassandra Indexing Techniques
http://www.slideshare.net/edanuff/indexing-in-cassandra

[2] Secondary indexes in Cassandra
http://www.anuff.com/2010/07/secondary-indexes-in-cassandra.html

[3] Indexing in Cassandra
http://www.anuff.com/2011/02/indexing-in-cassandra.html

[4] Cassandra Basics, Indexing.
http://www.slideshare.net/benjaminblack/cassandra-basics-indexing