Part 2 of 8 · 2 min read
The secondary index problem
Searching by a value that is not the key, when the data is split into partitions.
Think of a library that shelves its books in 20 rooms by the ID number on the spine. A reader who knows the ID goes to one room. A reader who wants "all books about bridges" has no way to know which rooms hold them.
The book "Designing Data-Intensive Applications" explains: a secondary index usually does not identify a record uniquely. It is a way of searching for occurrences of a value: all actions by user 123, all articles containing a word, all red cars. Secondary indexes are the bread and butter of relational databases, and common in document databases. Many key-value stores, such as HBase and Voldemort, avoided them because of the complexity, though some, such as Riak, added them because they are so useful. They are also the reason for search servers such as Solr and Elasticsearch to exist (Level 2, module 3 introduced indexes on one machine).
Secondary index
A secondary index is an extra lookup structure on a field other than the primary key, so that records can be found by that field.
Example: a used-car site keys listings by listing ID. A secondary index on colour lists the IDs of all red cars.
The problem: records are placed by primary key, so cars of the same colour are spread across partitions. There are two main designs.
If a key-value store has no index feature, one may be tempted to build the index in application code as a mapping from values to IDs. The book warns that keeping it consistent with the data is hard. Race conditions and partial write failures can easily put the index out of step with the data.
A worked example for the rest of this module. A used-car site has 4 partitions by listing ID, 0 to 3999 in total (partition 0 holds IDs 0 to 999, and so on). It holds 4,000 listings and 20 percent are red: 800 red cars, about 200 per partition (the colour is unrelated to the ID).
Check yourself:
- Why can a record not be found through a secondary index by looking at only one partition?
- What risk does an application-built index carry?