Introduction
In our last lesson, we focused on improving system predictability by tackling tail latency with techniques like hedged requests. We optimized the system's response to slow components. Today, we continue our focus on performance, but shift from reactive mitigation to proactive design by examining how data is structured for access. When data is distributed across many machines, how we find it is as important as how we store it.
This brings us to our learning outcome: Analyze local versus global secondary indexing approaches and their performance trade-offs. We will investigate the two primary strategies for indexing data in a sharded database. Understanding this is fundamental to designing scalable systems at Google, as the choice between local and global indexing directly impacts query latency, write throughput, transactional complexity, and operational cost.
The Fundamental Challenge: Querying Sharded Data
In a distributed database, data is partitioned or "sharded" across many nodes based on a partition key (e.g., UserID). Queries that include this partition key are efficient; the system knows exactly which node to contact. But what happens when you need to query based on an attribute that isn't the partition key, like finding a user by their email address?
The naive approach is a "scatter-gather" or "fan-out" query: the request is broadcast to all shards, each shard searches its local data, and the results are aggregated. This is inefficient and scales poorly. The following video introduces this problem and sets the stage for the solutions we'll discuss.
How indexes work in Distributed Databases, their trade-offs, and challenges
This video clearly explains the problem of querying on non-partition key attributes in a sharded database, illustrating the performance drawbacks of the scatter-gather approach.
Please watch the first few minutes, from the beginning to the introduction of the fan-out problem and its risks. This will solidify your understanding of why specialized secondary indexing is not just an optimization but a necessity.
As the video demonstrates, scatter-gather introduces high latency, is vulnerable to slow nodes (increasing tail latency, as we discussed previously), and creates unnecessary network traffic. To solve this, distributed systems employ two principal secondary indexing strategies: local and global indexing.
Let's dissect each approach.
Local Secondary Indexes (Document-Partitioned)
A local secondary index (LSI) is an index on attributes within a single data partition. The key characteristic is that the index itself is partitioned by the same key as the base data. It lives on the same shard as the data it references.
A classic example is Amazon DynamoDB's Local Secondary Index. In this model, an LSI must share the same partition key as the table but can have a different sort key. This allows for different query and sort patterns within the scope of a single partition key.
DynamoDB Deep Dive w/ a Ex-Meta Staff Engineer
This video provides a concise explanation of DynamoDB's indexing model, which serves as an excellent concrete example of Local and Global indexes.
Watch the segment from Partition Keys and Sort Keys. Pay close attention to the distinction made between a Global Secondary Index (for querying by a new partition key) and a Local Secondary Index (for sorting by a new attribute within the same partition key).
The Google F1/Spanner Implementation
Google's F1 database, built on Spanner, provides a powerful example of local indexing that aligns with its hierarchical data model. The F1 paper is a foundational read for understanding database design at Google.
[PDF] F1: A Distributed SQL Database That Scales - Google Research
The F1 paper details a real-world, Google-scale implementation of local and global indexes. Reading this section will connect the abstract concepts to a concrete architecture you're likely to encounter.
First, read about the Hierarchical Schema in Section 3.1. This explains how F1 co-locates related data (e.g., a Customer and all their Campaigns) in a single Spanner "directory." This physical clustering is what makes local indexes so effective. Next, read Section 3.3 on Indexing, focusing on the definition of a local index. Note how it states that local index keys must contain the root row's primary key as a prefix, ensuring they are stored in the same directory as the data.
Performance Trade-offs of Local Indexes
As you've gathered from these resources, local indexes present a clear set of trade-offs.
Advantages:
- Strong Consistency & Fast Writes: Since the index data and the primary data reside in the same partition (and often the same transaction), updates can be performed atomically and with low latency. The F1 paper notes that "local index updates add little additional cost to any transaction." This avoids the need for distributed transactions for index maintenance.
- Efficient Partition-Scoped Queries: They are highly efficient for queries that already specify the partition key, but need to filter or sort by another attribute. For example, "Find all messages in chat
ABC, sorted by number of attachments."
Disadvantages:
- Inefficient Global Queries: They do not solve the scatter-gather problem for queries that don't know the partition key. To find a user by their email address, you would still have to scan every partition, because the email index is itself partitioned by
UserID. - Partition Size Constraints: Because all data and LSI entries for a given partition key must be co-located, systems may impose a size limit per partition (e.g., DynamoDB's 10 GB limit for item collections with LSIs).
Global Secondary Indexes (Term-Partitioned)
A global secondary index (GSI) takes the opposite approach. It is essentially a separate table, where the index itself is partitioned by the attribute you want to query. The value of this index entry is typically the primary key of the corresponding row in the base table.
This solves the scatter-gather problem for global queries. To find a user by email, you hash the email address to find the correct GSI partition, retrieve the corresponding UserID, and then make a targeted read to the base table partition for that UserID.
The Google F1/Spanner Implementation
Let's return to the F1 paper to see how this is implemented in a strongly consistent system.
[PDF] F1: A Distributed SQL Database That Scales - Google Research
This section of the F1 paper highlights the primary trade-off of global indexes in a transactional system.
Please re-read Section 3.3 on Indexing, this time focusing on the description of global indexes. Pay close attention to the performance implications: updating a global index requires a two-phase commit (2PC) because the index entry is on a different shard from the data row.
Performance Trade-offs of Global Indexes
The F1 paper illuminates the central trade-off of GSIs: powerful read flexibility at the cost of write complexity.
Advantages:
- Efficient Global Queries: This is their main purpose. They allow fast, targeted lookups on any attribute, regardless of the base table's partition key.
Disadvantages:
- Increased Write Latency: Every write to the base table that touches an indexed attribute must also update the GSI. Because the GSI is on a different partition, this requires a distributed transaction (like 2PC), which significantly increases write latency and reduces availability. The F1 paper notes that for bulk inserts, this can create transactions with hundreds of participants, making them "slower and more error-prone."
- Consistency vs. Performance Trade-off: This write-side cost leads to a major architectural decision:
- Synchronous Updates (Strong Consistency): Systems like F1/Spanner and CockroachDB update the GSI synchronously within the same transaction. This guarantees the index is always consistent with the data but incurs the full write latency penalty.
- Asynchronous Updates (Eventual Consistency): Systems like DynamoDB decouple the index update. The write to the base table returns quickly, and the GSI is updated in the background. This provides low write latency but means the index can be temporarily stale (replication lag).
A Framework for Decision-Making
The choice between these strategies is not about one being universally better; it's about matching the tool to the access patterns of your application. The following flowchart provides a useful mental model for classifying different database indexing strategies.
This framework, combined with the detailed analysis in the following article, can help you structure your thinking when designing a data model.
How do distributed databases handle secondary indexes? ...
This article by Alex DeBrie provides an excellent survey of the four primary implementations of secondary indexes in modern distributed databases, aligning perfectly with the flowchart above.
Read through the article, focusing on the four approaches described. Try to map each approach to the concepts we've discussed: Approach 1 & 2 are both types of Global Indexes, differing on the synchronous vs. asynchronous update trade-off. Approach 3 & 4 are types of Local Indexes, differing on whether they permit inefficient scatter-gather queries. You can read from the section four approaches.
Conclusion
In this lesson, we dissected the critical trade-offs between local and global secondary indexing in distributed databases. Your ability as a Principal Engineer to choose the right strategy is paramount for building high-performance, scalable, and cost-effective systems.
Here are the key takeaways:
- The Problem: Querying a sharded system on a non-partition key leads to inefficient and unscalable scatter-gather operations.
- Local Indexes (Document-Partitioned): Are co-located with the data. They offer strongly consistent, low-latency writes but can only optimize queries that are already scoped to a specific partition key. They do not solve the global query problem.
- Global Indexes (Term-Partitioned): Are sharded independently by the indexed attribute. They enable fast, targeted global queries but introduce significant complexity and cost on the write path.
- The Global Index Trade-off: The primary design decision for global indexes is choosing between synchronous updates (strong consistency, high write latency) and asynchronous updates (eventual consistency, low write latency). This is a direct application of the PACELC theorem.
- Query Patterns are King: The correct choice is always driven by the application's required access patterns and consistency needs.
In our next lesson, we will explore a common consequence of access patterns and data distribution: hotspots. We will explain hot-spot detection and mitigation strategies for distributed workloads, a problem that can arise from both data modeling choices and unpredictable user traffic.