When Write Performance Matters More Than Read Performance
Traditional database indexes use B-trees: sorted tree structures that support fast point lookups and range queries. B-trees are excellent for reads. They are mediocre for writes because every insert or update must update the index in-place on disk, causing random I/O. Random I/O on spinning disks is 100 to 1000 times slower than sequential I/O.
In 1996, Patrick O'Neil and colleagues published the Log-Structured Merge-Tree (LSM-tree), which trades read performance for dramatically better write performance. Instead of updating the index in place, buffer writes in memory and flush them to disk in large sorted sequential batches. Merge the on-disk segments periodically in the background. Sequential writes are fast. The trade-off: reads might need to check multiple segments.
How LSM-Trees Work
- Writes go to an in-memory structure (MemTable) sorted by key. Extremely fast.
- When the MemTable fills (typically 64MB-256MB), it is flushed to disk as a sorted file called an SSTable (Sorted String Table).
- SSTables are immutable. New writes never modify old files. Compaction merges multiple SSTables into larger ones, removing deleted keys.
- Reads check the MemTable first (newest data), then SSTables from newest to oldest until the key is found.
- Bloom filters sit in front of each SSTable. A bloom filter can definitively say 'this key is not in this SSTable,' eliminating most unnecessary reads.
LSM-trees power the storage engines of nearly every modern write-heavy database: Cassandra, HBase, RocksDB, LevelDB, InfluxDB, CockroachDB. When an interviewer mentions a write-heavy workload (metrics collection, IoT sensor data, log ingestion, activity tracking), LSM-tree storage is the right data structure to reference.
B-trees optimize for reads. LSM-trees optimize for writes. This choice at the storage layer cascades through your entire architecture. Get the data structure right before everything else.
Elasticsearch and the Inverted Index (2010)
Shay Banon built Elasticsearch because he wanted to help his wife find recipes. He was already building a search library (Compass) and decided to make it distributed with a REST API. The result was Elasticsearch, which made Apache Lucene's search capabilities accessible to any developer with an HTTP client.
The core data structure is the inverted index: a mapping from words to documents (the inverse of a normal index that maps documents to their contents). When you search for 'circuit breaker,' the inverted index instantly returns all documents containing those terms, ranked by relevance using BM25 scoring. Building this index as documents are ingested makes writes more expensive but reads extremely fast even across billions of documents.
- Inverted index: maps terms to document IDs and positions. Full-text search is a lookup, not a scan.
- Near-real-time indexing: new documents are searchable within about 1 second of ingestion.
- Sharding and replication: Elasticsearch distributes shards across a cluster automatically. Adding nodes increases both capacity and throughput.
- Aggregations: not just search, but analytics. Group by, histogram, top-N, percentiles. The ELK stack (Elasticsearch, Logstash, Kibana) became the standard for log analytics.
- Schema flexibility: documents can have arbitrary JSON fields. No pre-defined schema required.
When to Use Elasticsearch vs a Database
Elasticsearch is a search engine, not a database. Use it for: full-text search, log aggregation and analysis, autocomplete and suggestions, and faceted search (filter by category, price range, rating). Do not use it as your primary data store. Elasticsearch prioritizes search performance over strict consistency. Writes are eventually indexed. Transactions are not supported. The pattern in production: primary data lives in PostgreSQL or your relational database of choice. Elasticsearch gets a copy for search via a change data capture pipeline or application-level dual writes.
Further Reading
- O'Neil et al. (1996): 'The Log-Structured Merge-Tree (LSM-Tree)'
- Elasticsearch documentation: elastic.co/guide
- Martin Kleppmann's 'Designing Data-Intensive Applications', Chapter 3 for storage engines including LSM-trees and B-trees
- RocksDB documentation for an LSM-tree implementation used by Facebook, CockroachDB, and many others
LSM Compaction Strategies: Size-Tiered vs Leveled
As SSTables accumulate, reads must check more and more files for a given key. Compaction merges SSTables to reduce this overhead and reclaim space from deleted keys. The compaction strategy fundamentally shapes the performance profile of the database. Size-tiered compaction (Cassandra default) groups similarly-sized SSTables together and merges them when a size threshold is reached. It is write-optimized: few compaction operations, high write throughput. The trade-off: reads become slower over time as tiers accumulate, and space amplification is high (the new merged file coexists with the old files until the merge completes, temporarily doubling disk usage). Leveled compaction (RocksDB/LevelDB default, optional in Cassandra) maintains sorted levels where each level is 10x larger than the previous. New data enters L0, then gets compacted into L1, then L2 progressively. Reads are much faster (each level is a sorted run with minimal overlap), but write amplification is higher.
- Size-tiered: fewer, larger compaction operations. High write throughput. High read amplification and space amplification.
- Leveled: continuous smaller compactions into sorted levels. Low read amplification. Higher write amplification.
- TWCS (Time-Window Compaction Strategy): Cassandra strategy for time-series. Groups SSTables by time window, compacts within windows. Low write and read amplification for append-heavy workloads.
- Write amplification: the ratio of data written to disk vs data written by the application. Critical for SSD wear and throughput.
- Read amplification: number of disk reads per logical read. Bloom filters and level structure minimize this.
Elasticsearch Production Pitfalls
Elasticsearch is easy to get started with and surprisingly difficult to operate at scale. The most common production failures follow predictable patterns. Deep pagination (requesting page 10,000 of search results) triggers a distributed merge sort across all shards and can OOM your cluster. Use search-after pagination with a sort key instead. Mapping explosion happens when dynamic mapping encounters fields with high cardinality (like user-submitted JSON keys): Elasticsearch creates a mapping entry for every unique field name, potentially creating millions of mappings that exhaust heap. Use explicit mappings and disable dynamic mapping for untrusted data.
- Deep pagination: use search_after with a tiebreaker sort field instead of from/size. Avoids the distributed merge-sort penalty.
- Mapping explosion: set dynamic: 'strict' or dynamic: false in your index mapping for fields derived from user input.
- Hot shard problem: if your shard key is a timestamp and you are writing time-series data, all writes go to the current shard. Use index aliases with time-based rollover.
- Heap pressure: Elasticsearch uses half of available memory for the JVM heap. The other half is for OS file cache. Exceeding 32GB heap disables compressed object pointers and dramatically increases GC pressure.
- Refresh interval: default 1-second refresh makes new documents searchable quickly but is expensive under heavy write load. Increase to 30 seconds or more during bulk indexing.
What Interviewers Test About Storage Engines and Search
Storage engine questions usually come up in the context of database selection or system design for high-throughput write scenarios. The interviewer wants to see that you can trace system behavior back to storage layer decisions.
- Know: why Cassandra is not a good fit for read-heavy workloads with arbitrary query patterns
- Know: the three levels of read amplification mitigation in LSM: MemTable (free), bloom filters (probabilistic), block cache (hot SSTable blocks in memory)
- Know: when to use Elasticsearch vs a database for search (Elasticsearch for full-text and analytics, database for transactional and structured queries)
- Know: Elasticsearch's eventual consistency model (near-real-time indexing, 1-second default refresh) and its implications
- Know: why Elasticsearch is not a primary datastore (no transactions, possible data loss on poor configuration, operational complexity)
LSM Compaction Strategies: Size-Tiered vs Leveled
As SSTables accumulate, reads must check more and more files for a given key. Compaction merges SSTables to reduce this overhead and reclaim space from deleted keys. The compaction strategy fundamentally shapes the performance profile of the database. Size-tiered compaction (Cassandra default) groups similarly-sized SSTables together and merges them when a size threshold is reached. It is write-optimized: few compaction operations, high write throughput. The trade-off: reads become slower over time as tiers accumulate, and space amplification is high (the new merged file coexists with the old files until the merge completes, temporarily doubling disk usage). Leveled compaction (RocksDB/LevelDB default, optional in Cassandra) maintains sorted levels where each level is 10x larger than the previous. New data enters L0, then gets compacted into L1, then L2 progressively. Reads are much faster (each level is a sorted run with minimal overlap), but write amplification is higher.
- Size-tiered: fewer, larger compaction operations. High write throughput. High read amplification and space amplification.
- Leveled: continuous smaller compactions into sorted levels. Low read amplification. Higher write amplification.
- TWCS (Time-Window Compaction Strategy): Cassandra strategy for time-series. Groups SSTables by time window, compacts within windows. Low write and read amplification for append-heavy workloads.
- Write amplification: the ratio of data written to disk vs data written by the application. Critical for SSD wear and throughput.
- Read amplification: number of disk reads per logical read. Bloom filters and level structure minimize this.
Elasticsearch Production Pitfalls
Elasticsearch is easy to get started with and surprisingly difficult to operate at scale. The most common production failures follow predictable patterns. Deep pagination (requesting page 10,000 of search results) triggers a distributed merge sort across all shards and can OOM your cluster. Use search-after pagination with a sort key instead. Mapping explosion happens when dynamic mapping encounters fields with high cardinality (like user-submitted JSON keys): Elasticsearch creates a mapping entry for every unique field name, potentially creating millions of mappings that exhaust heap. Use explicit mappings and disable dynamic mapping for untrusted data.
- Deep pagination: use search_after with a tiebreaker sort field instead of from/size. Avoids the distributed merge-sort penalty.
- Mapping explosion: set dynamic: 'strict' or dynamic: false in your index mapping for fields derived from user input.
- Hot shard problem: if your shard key is a timestamp and you are writing time-series data, all writes go to the current shard. Use index aliases with time-based rollover.
- Heap pressure: Elasticsearch uses half of available memory for the JVM heap. The other half is for OS file cache. Exceeding 32GB heap disables compressed object pointers and dramatically increases GC pressure.
- Refresh interval: default 1-second refresh makes new documents searchable quickly but is expensive under heavy write load. Increase to 30 seconds or more during bulk indexing.
What Interviewers Test About Storage Engines and Search
Storage engine questions usually come up in the context of database selection or system design for high-throughput write scenarios. The interviewer wants to see that you can trace system behavior back to storage layer decisions.
- Know: why Cassandra is not a good fit for read-heavy workloads with arbitrary query patterns
- Know: the three levels of read amplification mitigation in LSM: MemTable (free), bloom filters (probabilistic), block cache (hot SSTable blocks in memory)
- Know: when to use Elasticsearch vs a database for search (Elasticsearch for full-text and analytics, database for transactional and structured queries)
- Know: Elasticsearch's eventual consistency model (near-real-time indexing, 1-second default refresh) and its implications
- Know: why Elasticsearch is not a primary datastore (no transactions, possible data loss on poor configuration, operational complexity)