Part 3 of 8 · 3 min read
Local indexes: partitioned by document
Each partition keeps its own index of its own records.
Think of 20 library rooms, each with its own card box that lists only the books in that room. Adding a book means updating one box in one room. Looking for books about bridges means visiting every room and reading every box.
Local (document-partitioned) index
In a local index, each partition keeps a secondary index covering only the records stored in that partition. It is also called a document-partitioned index, since the partition is chosen by the document (record) ID.
Example: in the car site, partition 0 has its own list "colour:red" for its own 200 red cars. Partition 1 has another for its own.
The book describes how it works. Each partition is separate and keeps its own indexes. To add, remove or update a record, only the partition that holds that record is involved. That is why it is also called a local index, as opposed to a global one.
Reading is the difficulty. Unless the document IDs were chosen with care, cars of one colour are in all partitions. A search for red cars must be sent to all partitions and the answers combined. This is called scatter/gather.
Scatter/gather
Scatter/gather means sending one query to every partition and combining the answers.
Example: "all red cars" goes to partitions 0, 1, 2 and 3. Each returns its 200 red cars. The coordinator joins them into 800.
Even when the partitions are queried in parallel, scatter/gather suffers from tail latency amplification: the slowest partition decides the time of the whole query. The book refers back to its discussion of percentiles. MongoDB, Riak, Cassandra, Elasticsearch, SolrCloud and VoltDB use document-partitioned secondary indexes. Vendors advise structuring the partitioning so that a secondary index query can be served by one partition, but this is not always possible, especially when several indexes are used in one query (colour and make together).
A worked example of tail latency. Each partition answers within 50 ms in 99 percent of requests, and takes over 500 ms in 1 percent.
| Partitions queried | Chance that all are fast | Chance the query is slow |
|---|---|---|
| 1 | 0.99 | 1 percent |
| 4 | 0.99⁴ = 0.961 | 3.9 percent |
| 20 | 0.99²⁰ = 0.818 | 18.2 percent |
| 100 | 0.99¹⁰⁰ = 0.366 | 63.4 percent |
With 100 partitions, nearly two queries in three take over 500 ms, though each partition is slow only one time in a hundred. Scatter/gather turns rare slowness into frequent slowness.
Another cost is load. Each secondary query touches all N partitions, so N partitions each do work for every query. Adding partitions to a cluster does not raise the number of such queries per second the cluster can serve, since every query still uses every partition.
| Strength | Weakness |
|---|---|
| Writes touch one partition | Reads touch all partitions |
| Index always in step with the record | Slow tail latency |
| Simple | Query load does not shrink with more partitions |
Check yourself:
- With 50 partitions and a 1 percent chance that each is slow, what is the chance that a scatter/gather query is slow?
- Why is a write cheap with a local index?