What's ahead

• Introduction
• Index layout
• Index building process
• Parallelizing work
• FAQs

Introduction

• building a new index
• populating it with data from existing entities
• deleting an existing index
• removing existing index rows; similar process

Index building process

1. add new index definition (metadata) to app
2. mark index definition "write only"
• write to it on puts and deletes
• don't use it for queries
3. map over existing entities and populate index rows
4. mark index definition "read/write"

Index deleting process

Similar to building:

1. mark index definition "deleted"
• don't write to it on puts or deletes
• don't use it for queries
2. map over existing entities and remove index rows
3. delete index definition

Index layout

• internally, we call them "composite" indexes
• distinguishes from the built-in indexes
• composite because they're compose of multiple property values
• four bigtable tables total for indices, across all apps
• one each for three built-in indices
• kind, single prop asc, single prop desc
• one for all composite indices
• all index data is in row name, prefixed by app id
• composite indices also have secondary prefix: index id

Index building

• put/delete optimized to only calculate and update index deltas
• put/delete also incorporate composite indices automatically
• this makes index building easy:
• map over all of app's data
• read each entity and write it back, unchanged, in tx

Index deleting

• index deleting is the same process
• on write, datastore automatically detects composite indexes marked "deleted" and removes their index rows

Parallelizing work

• want to split up mapping over app's datastore among many workers, in parallel.
• want small, shorter-running chunks of work so that work is checkpointed frequently and retries are small and short
• each worker takes out a lease on a chunk of work

Parallelizing work

• unfortunately, by design, bigtable doesn't provide an offset operation
• ie can't say e.g. "give me the 1000th row after this one"
• makes it hard to split up work into equal sized chunks
• so we approximate: split up data by bigtable tablet
• each tablet can be handled by a separate worker, in parallel.

Parallelizing work

• also need to split the entities within each tablet
• split tablets into n pieces, each with sharding parameter k in [0, n)

Parallelizing work

note that each worker is still scanning over the entire tablet. however, this is relatively cheap compared to the multiple reads and writes required to build or delete the new index(es) for each entity. remember, disk bandwidth (ie large contiguous disk reads) are cheap, disk seeks are expensive!

FAQs

• Q: why do indexes get stuck in Building or Deleting?
• A: most often, work chunks are too big for the lease period
• we increased the lease period, which helped, but wasn't sustainable
• long term solution is the k modulo n sharding, which was added recently

FAQs

• Q: why do indexes go into the "Error" state?
• A: see Big Entities and Exploding Indexes

FAQs

• Q: why map over the app's whole datastore instead of just the entities of the index's kind, using the built-in kind index?
• A: entity writes are READ_CONSISTENT (see the tx isolation article), but indices aren't, so the kind index might miss some entities.

FAQs

• Q: when a composite index is deleted, why can't we just delete its index rows directly? we could do a bigtable prefix scan with the app id and index id, right?
• A1: we wish it was that easy! the entities themselves also store metadata about the composite indices that apply to them, so we need to update that metadata too.
• A2: also, composite indexes are subject to the same tx isolation caveats mentioned before.

FAQs

• Q: when a composite index is deleted, why can't we just delete its index rows directly? we could do a bigtable prefix scan with the app id and index id, right?
• A1: we wish it was that easy! the entities themselves also store metadata about the composite indices that apply to them, so we need to update that metadata too.
• A2: also, composite indexes are subject to the same tx isolation caveats mentioned before.

Questions? (also see the article)