<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Hari Krishna Sunder on Medium]]></title>
        <description><![CDATA[Stories by Hari Krishna Sunder on Medium]]></description>
        <link>https://medium.com/@hari-db?source=rss-a91680219e18------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*1F9qm2FHi4LCpcZYBpsdvw@2x.jpeg</url>
            <title>Stories by Hari Krishna Sunder on Medium</title>
            <link>https://medium.com/@hari-db?source=rss-a91680219e18------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 03:14:28 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@hari-db/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[How to Make a Database Highly Available]]></title>
            <link>https://medium.com/@hari-db/how-to-make-a-database-highly-available-0276c0fdc3b4?source=rss-a91680219e18------2</link>
            <guid isPermaLink="false">https://medium.com/p/0276c0fdc3b4</guid>
            <category><![CDATA[raft]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[relational-databases]]></category>
            <dc:creator><![CDATA[Hari Krishna Sunder]]></dc:creator>
            <pubDate>Mon, 06 Jul 2026 00:54:59 GMT</pubDate>
            <atom:updated>2026-07-06T01:03:24.719Z</atom:updated>
            <content:encoded><![CDATA[<p>Databases are the critical components of any software stack. This requires them to have extremely high availability and resilience. Historically this was achieved by running them on expensive dedicated hardware that was highly reliable, but as modern technology has moved to the cloud and uses less reliable rack hardware, the responsibility of guaranteeing availability has shifted to the database software, and modern cloud-native databases were born. In this article, we will look at the two broadly used techniques to make a database highly available, Per Shard Leader Election (SLE) and Centralized Leader Election (CLE), and evaluate their pros and cons.</p><h3>Key Concepts</h3><h4>What is a Database?</h4><p>Honestly, I don’t have a good simple engineering answer for this. Claude says “A database is an organized collection of data that can be efficiently stored, queried, and updated.” That’s too broad. Does it mean a set of integers is a database?</p><p>We are more interested in database management systems. Meaning it does a lot more stuff than a simple database. Things like access control, backups, auditing, and high availability. <a href="https://db-engines.com/en/ranking">DB-Engines</a> ranking tracks 387 of these! These are some of the most complex software programs in the world. More complex than operating systems.</p><h4>What is High Availability?</h4><p>Traditionally databases ran on a single machine (most still do). These were not the typical “off the rack” servers we get in the cloud today. They were enterprise grade servers with a much lower failure rate. Mainframe machines from IBM, Sun Microsystems that have uptimes measured in years! But all hardware eventually fails: rats eat your power cords, sharks eat your network cables, your disks get headaches and stop spinning, or a ⚡ decides to help warm up your data center. But much more common than rats and sharks is everyone’s most and least favorite thing about software… Upgrades! Upgrades to the OS, drivers, networks, and the database itself. So, despite best efforts, these applications go offline. And when that happens, the impact is massive because important stuff is kept in databases. <a href="https://en.wikipedia.org/wiki/High_availability">High availability</a> of a database in a broad sense just means the database system can handle the failure of a machine, or some of its network, and still keep running. These are closed systems, so we need not worry about bad actors, hallucinating networks, or other exotic failure models.</p><p>The typical way to measure availability is by measuring the percentage of uptime, like 99.99%. That’s roughly a 4-minute outage every month. Most commercially managed databases offer 99.995% or even 99.999%, which is just 26 seconds of outage every month! This is our goal.</p><p>Oh, and we cannot lose data. Customers don’t like “shark ate your rows” Root Cause Analysis.</p><h4>Replication</h4><p>The smartest brains on the planet have concluded that the best way to survive the loss of a node (or machine) is to have a hot standby node with an identical copy of the data. Standby meaning it can fully take over when the primary node goes offline, and hot means it can do so quickly. The less physical elements these machines share, like power cords, network cables, buildings, zip codes, or even country, the better for availability. The challenge is in keeping an identical copy, meaning if you change the data, then you must do so on two nodes. This means actively replicating the data and its changes to the standby machine.</p><p>Why not just store the data in S3, NFS, or any other Blob storage that does this already? Of course, the easiest way to do something is by making someone else do that work for you. But these systems have the same underlying challenges and use similar techniques to keep their data highly available and consistent. In the broad definition, these storage systems are databases themselves, they just store bytes too.</p><h4>Leader Election &amp; Consensus</h4><p>Now that you have two identical nodes, you have the hardest problem in software. Naming things! One, and only one must be called a leader (or primary), and the other(s) a follower (or standby). If you have more than two copies, then we shall name everything that is not the leader a follower to simplify our problem. Having more than one leader will result in a split brain and weird dilemmas. Only the leader can make changes to the data and only it can server the latest committed data. The standbys can only provide slightly stale reads.</p><p>Consensus is the act of deciding who to elect as the leader, in a manner that everyone agrees. This seemingly simple statement masks profound complexity. When you have multiple nodes that can fail independently, communicate over unreliable networks, and may have different views of the system state, the system must reach a consensus on electing the leader.</p><h4>The CAP Theorem</h4><p>The <a href="https://en.wikipedia.org/wiki/CAP_theorem">CAP</a> theorem states that in the presence of network partitions, distributed systems must choose between Consistency and Availability. For databases that guarantee ACID properties (CP systems), we need consensus algorithms to ensure that all nodes agree on the current state of the data even when networks fail or machines crash.</p><p>The challenge is profound. The <a href="https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf">FLP</a> (Fischer, Lynch, Paterson) impossibility result proves that in an asynchronous distributed system, it’s impossible to guarantee consensus if even a single process can fail. However, practical consensus algorithms like Paxos and Raft work around this by making reasonable assumptions about timing (eventual message delivery) and using timeouts to detect failures.</p><h4>Consensus of Commit</h4><p>If data integrity and consistency are not hard requirements, then you can perform the replication asynchronously and skip the multi-node quorum commits. You don’t even need the concept of a single leader for these systems. Any node can serve writes, and there will be a best effort to replicate the changes to the other nodes. These systems have the highest level of availability and are classified as AP in the CAP theorem. The applications using these databases do not care about these transient inconsistencies and have extra logic to eventually reconcile the data across the nodes.</p><p>On the other end of the spectrum (CP), we have synchronous replication with a single leader. Here, the leader needs to work with its followers to commit the changes across nodes before it can acknowledge back to the client. With a full commit, every node has to persist the change. Quorum or majority commit requires a majority of machines to persist the change. When electing a new leader, we make sure to pick the one that was part of this majority. Consensus of the committed data is a must to guarantee consistency and high availability!</p><h4>Quorum Mathematics</h4><p>To tolerate f node failures, you need 2f + 1 total nodes. Here’s why:</p><p>● With 2f + 1 nodes, a majority quorum is f + 1 nodes</p><p>● If f nodes fail, you still have f + 1 nodes available to form a quorum</p><p>● Any two quorums must overlap by at least one node, preventing split brain</p><p>Example: To survive 1 failure (f=1), you need 3 nodes (2×1 + 1 = 3). A quorum is 2 nodes. If one node fails, the remaining 2 can still form a quorum. If the network partitions into groups of 2 and 1, only the partition with 2 nodes can operate.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/918/1*U7ytw7kqS1UXxK_GILkxnw.png" /><figcaption><em>Figure 1 — During a network partition, only the majority side keeps a quorum and stays writable.</em></figcaption></figure><h4>Shards and Replication Units</h4><p>Typically customers have more than one database that can share the nodes. Database vendors who offer databases as a service (DBaaS), manage millions of databases running on thousands of machines. A replication unit can be a group of databases, an individual database, an individual table, or a subset of the table. For our discussion, we don’t care about the dependency and relationship between these units so I am going to refer to each of these replication units as a shard.</p><p>Each shard has its own leader, followers, and one replication stream. Each copy of a shard on a node is called a peer. The leader peer replicates to the follower peer(s). This guarantees ACID properties only within a shard. To ensure atomicity across multiple shards, you need a transaction system at a higher layer.</p><h3>Two Types of Leader Election</h3><p>So essentially the problem is that of leader election. All the nodes must come to a consensus about who is the current leader for each shard. Consensus algorithms like Paxos or Raft provide the mechanism to achieve this. Since a database system typically manages multiple shards, this gives you two architectural options for where to run these consensus algorithms: Per Shard Leader Election (SLE), where each shard runs its own independent consensus group, or Centralized Leader Election (CLE), where a single consensus group manages leader assignment for all shards.</p><h4>Per Shard Leader Election (SLE)</h4><p>Each shard is responsible for picking its own leader. To do this they each run the consensus algorithm independently. These algorithms are very complex. So complex that if you decide to implement them from scratch, no one is going to easily trust that you did it correctly. The consensus algorithm can handle both the leader election and replication problem. But if you want to, you can split them and do the replication yourself (Ex. Neon).</p><p>The consensus algorithms use heartbeats between peers to detect the failure of the leader and run an election amongst the remaining peers to pick a new leader. No external entity is needed to tell the shard when and what to do.</p><h4>SLE Implementation Examples</h4><h4>Google Spanner</h4><p>Spanner uses Paxos for replication across datacenters. Each Paxos group manages a tablet (horizontal partition). The most innovative aspect is TrueTime:</p><p>● TrueTime API provides a time interval with guaranteed error bounds using GPS and atomic clocks</p><p>● Commit wait: transactions wait out the uncertainty before committing to ensure external consistency</p><p>● Typical uncertainty is &lt;7ms, making linearizable reads at a timestamp feasible</p><h4>YugabyteDB</h4><p>YugabyteDB uses Raft for both its PostgreSQL-compatible (YSQL) and Cassandra-compatible (YCQL) APIs. Data is partitioned into tablets, with each tablet replicated using Raft:</p><p>● Default replication factor: 3 (configurable)</p><p>● Tablet splitting: tablets automatically split when they exceed a threshold (typically 32–100 GB), distributing load</p><p>● Leader balancing: algorithm to evenly distribute Raft leaders across nodes for optimal load distribution</p><p>Examples of databases using SLE:</p><p>● Aurora DSQL</p><p>● CockroachDB</p><p>● CosmosDB</p><p>● DynamoDB</p><p>● MongoDB</p><p>● Neon</p><p>● Redpanda</p><p>● Spanner</p><p>● TiDB</p><p>● YugabyteDB</p><p>Most SLE systems have one or more special shards that perform operations like load balancing of other shard leaders, data load balancing of shard peers, and storing global metadata like the location of all shard leaders.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/918/1*-ynzNDf8ywLBrU6MwBekFA.png" /><figcaption><em>Figure 2 — In SLE, every shard runs its own consensus group; the metadata shard only balances load and tracks leaders.</em></figcaption></figure><h4>Centralized Leader Election (CLE)</h4><p>As the name suggests, there is one central decision maker (Leader Manager), who is responsible for assigning leaders for all the individual shards. On the failure of one shard leader, the Leader Manager will talk with all remaining shard peers and pick the peer with the most caught-up data as the new leader.</p><h4>CLE Implementation Examples</h4><h4>AWS Aurora</h4><p>Aurora uses a unique architecture that separates compute and storage:</p><p>● Storage layer: Data is replicated across 6 storage nodes in 3 availability zones (2 copies per AZ)</p><p>● Write quorum: 4/6 nodes must acknowledge writes</p><p>● Read quorum: 3/6 nodes must respond for reads</p><p>● Compute layer: Single writer instance with up to 15 read replicas</p><p>The control plane (Aurora’s Leader Manager) monitors the compute instances and storage nodes. On primary failure:</p><p>● Control plane detects failure via heartbeat timeout (typically 10–30 seconds)</p><p>● Promotes a read replica to primary (if available) or launches new instance</p><p>● Updates DNS endpoint to point to new primary</p><p>● Total failover time: typically 30–120 seconds</p><p>Aurora’s storage nodes do not run full consensus — instead they use quorum writes. The storage layer automatically repairs replicas that fall behind, and the control plane handles failover of the compute tier.</p><h4>Azure SQL Database</h4><p>Azure SQL uses the Fabric Controller for centralized orchestration:</p><p>● Each database has 1 primary and 3+ secondary replicas</p><p>● Replicas send heartbeats to Fabric Controller</p><p>● Primary holds a lease from Fabric Controller (renewed every few seconds)</p><p>● If primary fails or lease expires, Fabric Controller promotes most caught-up secondary</p><p>● Gateway layer automatically redirects connections to new primary</p><p>Replication uses SQL Server Always On Availability Groups technology with quorum commit. The Fabric Controller itself runs on a distributed consensus platform for high availability.</p><p>Examples of databases using CLE:</p><p>● Apache Kafka</p><p>● AWS Aurora</p><p>● Azure SQL, Azure Synapse DW, Azure Fabric DW</p><p>● CitusDB</p><p>● Clickhouse</p><p>● ElasticSearch</p><p>● FoundationDB</p><p>● HDFS</p><p>● MemSQL/SingleStore</p><p>● Redshift</p><p>● PlanetScale</p><p>● Postgres</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/918/1*NemUiJMdrwg6OG-vvL77Gw.png" /><figcaption><em>Figure 3 — In CLE, a single Leader Manager assigns and monitors the leader of every shard.</em></figcaption></figure><h3>Which is Better?</h3><p>Finally! Let’s look at how the two compare.</p><h4>Number of Copies of Data</h4><p>Consensus needs 2f + 1 nodes to survive the loss of f nodes. So SLE requires 2f + 1 peers for every shard. CLE only needs f+1 peers for the shards with a full commit policy. So CLE needs fewer copies of data than SLE. But, CLE Azure SQL has 4 copies, and Aurora has 6, whereas most of the SLE databases like Yugabyte only have 3 copies. SQL Server Always On and Postgres with <a href="https://github.com/patroni/patroni">Patroni</a> let you run with only 2 copies. But these are on the enterprise-grade machines where the failure rate is low. In the cloud, the failure rates are much higher. And more importantly, you (or something you depend on) upgrade all the time! If you want to keep the database running while 1 node is taken down for an upgrade, you need at least 2 more copies, since there is a high chance that one of the two is going to have a permanent disk failure. With 3 copies, one transient fault and one permanent fault mean a slightly longer outage. With only 2 copies, it’s data loss! The extra node is well worth the added cost.</p><p>The other reason is latency. Cloud nodes and networks slow down transiently. You pack a lot of apps across customers with under allocated resources on a bet that not all of them will spike at once. But sometimes they do, and your p99 latency suffers. With a full commit, even if one node is slow, the p99 must take a hit. Quorum commit is more forgiving. So, you are going to need at least 3 nodes for both SLE and CLE.</p><p>If reducing cost is the priority, then you can use heterogeneous nodes. 2 big nodes and 1 small node. If the big node fails, then you failover to the most caught-up one, and if that happens to be a small node, then gracefully switch to the bigger node. This can be done in both SLE and CLE. The complexity of implementation depends on the consensus algorithm, replication algorithm, and other factors. But the operational complexity of managing heterogeneous nodes can get far more difficult in the long term.</p><h4>Time to Recover from a Failure</h4><p>SLE should be faster to recover from the failure of the leader node. But CLE is not that far off. The difference between the shards themselves electing a leader vs. a central leader manager would only be a few milliseconds (network latency between shard peers and leader manager). But some consensus algorithms will have to perform multiple rounds of election to break ties or add random sleeps. So, there won’t be any significant difference here.</p><p>If all peers are caught up (read heavy workloads), then CLE will be better at picking the optimal leader on the first attempt. SLE would pick a random leader and then require a load balancer to rebalance leaders evenly across nodes. 2 leader moves mean longer unavailability and more failed queries.</p><p>Based on published benchmarks and production experience:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9b3Uqn_-vD9zPB4H0CSd2g.png" /><figcaption>Failover time comparison (from leader failure to new leader ready)</figcaption></figure><p>Note: Failover times vary based on configuration, workload, and whether read replicas are pre-provisioned. These are typical values for automated failover.</p><h4>Network Partition Handling</h4><p>How each approach handles network partitions:</p><p>SLE (Per Shard Leader Election):</p><p>● Each shard independently handles partitions</p><p>● Partition with majority quorum continues operations</p><p>● Minority partition blocks writes (followers cannot elect new leader without quorum)</p><p>● Recovery: When partition heals, followers sync from leader and catch up</p><p>CLE (Centralized Leader Election):</p><p>● If shard is partitioned from Leader Manager but has internal connectivity, the leader can continue if it holds a valid lease</p><p>● Once lease expires, shard blocks writes even if peers can communicate</p><p>● If Leader Manager can reach some peers but not leader, it may promote a new leader creating temporary split brain until old leader’s lease expires</p><p>● Lease-based fencing prevents dual writes during this window</p><h4>Simpler Design</h4><p>If you had to build these databases from scratch, which solution is simpler? Sadly, both are extremely complex to implement and run. Even though Raft helps simplify things quite a bit, it still takes years to get a working product out and even longer to squeeze out the bugs.</p><h4>Replication Technology</h4><p>This, in my opinion, is the deal breaker. Building a replication technology for a database from scratch is HARD. But even harder than building a new replication technology is integrating a preexisting one with a different consensus algorithm (and trust me, it’s not fun)!</p><p>If you have existing replication technology, then reuse it with CLE. It’s easier to integrate any replication technique with CLE. No point throwing away the hard work and good code that is known to work well.</p><p>If you must build one from scratch, you can choose either option. Raft handles both consensus and replication, which is what makes it so compelling. It’s so good that all the newer databases use it and end up in the SLE camp.</p><h4>Extensible Design</h4><p>CLE is usually better to extend with additional capabilities. Let’s take disaster recovery (DR) as an example:</p><p>Eventually you are going to have to build asynchronous replication for DR purposes. DR replication differs fundamentally from the synchronous consensus replication used for high availability within a region. While consensus replication prioritizes consistency and immediate failover (typically across availability zones within a single region with low latency), DR replication prioritizes geographic distribution and survives complete region failures, often tolerating seconds or even minutes of replication lag across continents.</p><p>Asynchronous replication is far simpler to implement than synchronous consensus replication. With async replication, the leader doesn’t wait for acknowledgment before committing transactions. It simply ships transaction logs or changes data to remote replicas on a best effort basis. There’s no quorum voting, no leader election across regions, and no blocking on network round trips to distant datacenters. The complexity of handling network partitions, split brain scenarios, and coordinating commits across nodes simply doesn’t exist in the async model.</p><p>This is where the architectural difference between CLE and SLE becomes significant. With CLE, your existing replication technology (the mechanism that ships data from leader to followers) is decoupled from the consensus algorithm. The Leader Manager coordinates who is the leader, but the actual replication of data happens through a separate replication layer. This same replication layer can be reused for DR with minimal modifications. You simply point it at a remote datacenter and configure it to run asynchronously instead of synchronously. The replication protocol, log shipping mechanism, conflict resolution (if any), and monitoring infrastructure are all shared between your high availability replication and your DR replication.</p><p>In contrast, SLE systems tightly couple replication with consensus. Algorithms like Raft handle both leader election and log replication as a single integrated protocol. The AppendEntries RPC in Raft doesn’t just replicate data; it also serves as heartbeats and enforces log consistency checks required for safety guarantees. This tight coupling means you cannot simply reconfigure Raft to run asynchronously across regions without breaking its safety properties. You must build a separate async replication system for DR. Now you’re maintaining two distinct replication codebases: the Raft-based sync replication for high availability and a custom async replication for disaster recovery. Each has its own bugs to fix, performance characteristics to tune, monitoring metrics to track, and operational runbooks to maintain.</p><p>The operational burden multiplies. Engineers must understand two different replication architectures. Debugging replication lag requires different tools and approaches depending on whether the issue is in the sync or async path. Performance optimization work doesn’t transfer between the two systems. Security patches and protocol upgrades must be applied to both independently. Over the multi-year lifecycle of a database product, this duplication of effort becomes a significant maintenance tax that SLE systems must pay.</p><h3>Conclusion</h3><p>Both Per Shard Leader Election (SLE) and Centralized Leader Election (CLE) are proven approaches for building highly available databases. The choice between them largely depends on your starting point:</p><p>If you are starting with a database that already has a solid and performant replication solution, then use CLE. If not, then pick Raft, hence SLE.</p><p>You are in for a challenging and wild ride!</p><h4>5 Key Takeaways</h4><p>● <strong>Two Core Architectures:</strong> Database high availability relies on two main leader election strategies for sharded systems: <strong>Per Shard Leader Election (SLE)</strong>, where each shard runs its own consensus protocol (like Raft or Paxos), and <strong>Centralized Leader Election (CLE)</strong>, where a single Leader Manager assigns and monitors leaders for all shards.</p><p>● <strong>Raft for Simpler Consensus:</strong> Consensus algorithms like <strong>Raft</strong> and <strong>Paxos</strong> are used to ensure consistency. Raft is favored in newer databases for its design focused on understandability and complete specification, often leading to the SLE architectural choice.</p><p>● <strong>Extensibility vs. Coupling Trade-off:</strong> <strong>CLE</strong> offers a more extensible design, particularly for <strong>Disaster Recovery (DR)</strong>, by decoupling replication from consensus, allowing the same replication layer to be reused for simpler asynchronous DR. <strong>SLE</strong> systems (like Raft) tightly couple these two, requiring a separate, custom asynchronous replication system for DR.</p><p>● <strong>Failover Performance:</strong> In typical automated failover scenarios, <strong>SLE</strong> systems (e.g., YugabyteDB, CockroachDB) generally demonstrate <strong>faster recovery times</strong> (e.g., 3–10 seconds) compared to <strong>CLE</strong> systems (e.g., Azure SQL, AWS Aurora), which can range from 10 to 120 seconds.</p><p>● <strong>Choice Depends on Starting Point:</strong> The ultimate decision is driven by development context: <strong>Choose CLE</strong> if you have an existing, solid, performant replication technology you wish to reuse. <strong>Choose SLE</strong> (via Raft) if you are building the database from scratch, as Raft provides a single, integrated protocol for both consensus and replication.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=0276c0fdc3b4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Index is the Database]]></title>
            <link>https://medium.com/@hari-db/the-index-is-the-database-338c06ea4954?source=rss-a91680219e18------2</link>
            <guid isPermaLink="false">https://medium.com/p/338c06ea4954</guid>
            <category><![CDATA[database]]></category>
            <category><![CDATA[gis]]></category>
            <category><![CDATA[vector-database]]></category>
            <category><![CDATA[ai]]></category>
            <dc:creator><![CDATA[Hari Krishna Sunder]]></dc:creator>
            <pubDate>Tue, 30 Sep 2025 14:05:01 GMT</pubDate>
            <atom:updated>2025-10-01T01:58:19.986Z</atom:updated>
            <content:encoded><![CDATA[<p>The hidden workhorse of your database</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/914/1*XnkjT0RivK-DvgdCw5MZ1Q.png" /></figure><p>There’s a well-known saying in database systems: <strong>“The WAL is the database.”</strong></p><p>That’s partially true. The Write-Ahead Log (WAL) is critical for durability. Having worked on the WAL layer of databases for a decade I used to think this too. Because without it, a database can’t guarantee recovery after a crash. But durability is not the primary reason people use databases.</p><p>The real selling point of a database lies elsewhere: <strong>the index.</strong></p><p>Without indexes, a database is just a heap — a raw pile of bytes, no different than a flat file. Indexes are what differentiate a simple file from a database.</p><h3>What is an index?</h3><p>An index points you to the location of information.</p><p>That’s the generic definition and the same applies to databases. The only difference from an index in a book is that the database indexes are hidden. You never query an index directly, the query specifies the table, and the database automatically makes use of the index that offers the most efficient query plan.</p><p>If you don’t need an index, then you don’t need a database for it!</p><h3>There is an index for that</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/368/1*Dht0Lk5VWsJiCwzCKcCXwA@2x.jpeg" /></figure><p>Let’s look at the most common classes of indexes encounter today. An easy way to understand these is to look at the questions they help answer.</p><h3>1. B-Trees: The Workhorse</h3><p>The most common index in relational systems. B-Trees are balanced search trees where keys are sorted, making them perfect for:</p><ul><li><em>What’s the phone number of a user?</em> (WHERE id = 123)</li><li><em>How many people are in their 20s?</em> (WHERE age BETWEEN 20 AND 30)</li><li><em>What are the last 5 orders?</em> (ORDER BY timestamp)</li></ul><p>In Postgres, SqlServer, and most relational databases, your default CREATE INDEX is a B-Tree. Without it, even simple queries would degrade into full table scans.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/994/1*ChV3F3r9bGB_0sKc29DdkA.png" /></figure><h3>2. GIS Indexes: Making Maps Work</h3><p>When working with geospatial data, B-Trees aren’t enough. Structures like <strong>R-Trees</strong>, <strong>Quadtrees</strong>, and Postgres’s <strong>GiST indexes</strong> allow spatial queries like:</p><ul><li><em>Find all restaurants within 5 miles.</em></li><li><em>Which polygons overlap this region?</em></li></ul><p>Without these specialized indexes, every geospatial query would require scanning entire datasets of coordinates and shapes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9WIxjUaDZ7LKxpRYupoyBw.png" /></figure><h3>3. LSM Trees: Memory became cheap</h3><p>Modern databases like RocksDB, LevelDB, Cassandra, and YugabyteDB rely on <strong>Log-Structured Merge Trees (LSMs). It</strong> takes advantage of the tremendous price reduction of main memory storage in recent years. They are very similar to B-Trees in capability.</p><p>Instead of updating rows in place, LSMs:</p><ol><li>Buffer writes in memory (a memtable).</li><li>Flush them sequentially to disk as immutable files (SSTables).</li><li>Periodically compact those files into larger, sorted structures.</li></ol><p>This design turns random writes into sequential ones, making it ideal for SSDs. Indexing happens across these sorted files, allowing reads to remain efficient while sustaining massive write throughput.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1019/1*QKl6PWX615mzvT19OIh_qA.png" /></figure><h3>4. Vector Indexes: Fueling the AI Era</h3><p>The latest evolution is <strong>vector indexes</strong>, powering similarity search in embeddings. Structures like <strong>HNSW (Hierarchical Navigable Small World graphs)</strong> or <strong>IVF (Inverted File Indexes)</strong> make it possible to:</p><ul><li><em>Get me images that contain a dog</em></li><li><em>What are the documents that talk about the NFL?</em></li></ul><p>Without vector indexes, every similarity search would require brute-force scanning across millions of vectors — completely impractical in real-world AI systems.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*paNMHcCXlVA37n4E1ffCeA.png" /></figure><h3>Even NoSQL Runs on Indexes</h3><p>A decade ago, the NoSQL movement positioned itself as <em>“simpler, faster, schema-less, and superior”</em> to traditional databases. The sales pitch was that you didn’t need the complexity of relational indexes — just store JSON or key-value pairs and scale horizontally.</p><p>But reality caught up quickly. Even NoSQL databases discovered that without indexes, they couldn’t support real-world workloads.</p><ul><li><strong>MongoDB</strong> added B-Tree and geospatial indexes early on, and later secondary, text search, wildcard and vector indexes.</li><li><strong>Cassandra</strong> uses LSM-based SSTables but still relies on secondary indexes for non-primary key queries.</li><li><strong>DynamoDB</strong> markets itself as “index-free,” yet depends heavily on <strong>Global Secondary Indexes (GSIs)</strong> and <strong>Local Secondary Indexes (LSIs)</strong> to serve anything beyond simple key lookups.</li></ul><p>The lesson? No matter how revolutionary the branding, a database needs indexes.</p><h3>Indexes are expensive</h3><p>Indexes require extra disk space.</p><p>Indexes slow down writes.</p><p>Reindexing is a pain!</p><p>Indexes are a copy of the data that’s already in the underlying table, so you are increasing the disk space, and memory usage of the system. It’s thus crucial to choose the right indexes and not have unused indexes. But that’s not an easy task either. The data is constantly changing, and so are the apps, so the queries that need to be optimized are fluid and ever evolving. Ai the struggle to keep the right indexes is constant.</p><p>Indexes are not free, so choose them wisely.</p><h3>Indexes are hard to build!</h3><p>That’s an understatement!</p><p>The trouble with an index is that it is automatically managed by the database. So, all the heavy lifting must happen within the database. Index consistency violation is data consistency violation.</p><ul><li>The index that’s missing a row results in data loss.</li><li>The index that has multiple copies of the same row results in duplication of data.</li><li>The index that points to the wrong row results in data corruption.</li></ul><p>And the index needs to be atomically updated with the base table. There is absolutely no room for error in managing indexes. They are unforgiving and some of the hardest things to build in a database.</p><h3>The one to rule them all</h3><p>Is there one index that can do everything? No.</p><p>Is there one database that can do everything? Yes.</p><p>It’s of course the database which has the most versatile set of indexes — <strong>PostgreSQL</strong></p><p>In addition to the native indexes and PostGiS there are companies like Mooncake(DuckDB) and ParadeDB(BM25) with a primary focus on adding new index capabilities to Postgres.</p><p>Decades ago when <strong><em>Michael Stonebraker</em></strong> and <strong><em>Lawrence A. Rowe</em></strong> wrote the <a href="https://dsf.berkeley.edu/papers/ERL-M85-95.pdf">design</a> for Postgres they chose index (access method) extensibility as a core design element of the project.</p><p><em>“Our second goal is to allow new data types, new operators and new access methods to be included in the DBMS. Moreover, it is crucial that they be implementable by non-experts which means easy-to-use interfaces should be preserved for any code that will be written by a user.”</em></p><p>That decision is one of the key reasons why Postgres is the most popular database today.</p><h3>Closing Thought</h3><p>The evolution of databases is inextricably linked to the evolution of the index. As we’ve moved from simple record-keeping to navigating vast geospatial terrains and now to searching the abstract dimensions of AI embeddings, indexes have been the critical innovation enabling each leap forward.<br> So, the next time you marvel at a query that executes in milliseconds across billions of rows, take a moment to appreciate the hidden workhorse that made it possible. It’s not just an add-on for performance; it’s the fundamental structure that defines a database’s power — <strong>the index <em>is</em> the database.</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=338c06ea4954" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Database Architectures]]></title>
            <link>https://medium.com/@hari-db/database-architectures-750297f5d6f4?source=rss-a91680219e18------2</link>
            <guid isPermaLink="false">https://medium.com/p/750297f5d6f4</guid>
            <category><![CDATA[database-development]]></category>
            <category><![CDATA[architecture]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[database-architecture]]></category>
            <dc:creator><![CDATA[Hari Krishna Sunder]]></dc:creator>
            <pubDate>Thu, 09 Jan 2025 05:47:53 GMT</pubDate>
            <atom:updated>2025-02-02T20:58:02.485Z</atom:updated>
            <content:encoded><![CDATA[<p>The following is a collection of architecture designs of the major databases.<br>This data is also available on <a href="https://github.com/hari90/db-architectures">GitHub</a>.</p><p><a href="https://pages.cs.wisc.edu/~yxy/cs764-f20/papers/aurora-sigmod-17.pdf">Amazon Aurora</a></p><p><a href="https://www.youtube.com/watch?v=huGmR_mi5dQ&amp;ab_channel=AWSEvents">Amazon DSQL</a></p><p><a href="https://www.usenix.org/system/files/atc22-elhemali.pdf">Amazon DynamoDB</a></p><p><a href="https://assets.amazon.science/93/e0/a347021a4c6fbbccd5a056580d00/sigmod22-redshift-reinvented.pdf">Amazon Redshift</a></p><p><a href="https://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf">Apache Cassandra</a></p><p><a href="https://www.usenix.org/legacy/event/hotcloud10/tech/full_papers/Zaharia.pdf">Apache Spark</a></p><p><a href="https://docs.citusdata.com/en/stable/get_started/concepts.html">Citus</a></p><p><a href="https://www.cockroachlabs.com/docs/stable/architecture/overview">CockroachDB</a></p><p><a href="https://docs.databricks.com/en/getting-started/overview.html">Databricks</a></p><p><a href="https://docs.datomic.com/datomic-overview.html">Datomic</a></p><p><a href="https://duckdb.org/docs/internals/overview.html">DuckDB</a></p><p><a href="https://www.foundationdb.org/files/fdb-paper.pdf">FoundationDB</a></p><p><a href="https://cloud.google.com/blog/products/data-analytics/new-blog-series-bigquery-explained-overview">Google BigQuery</a></p><p><a href="https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf">Google Spanner</a></p><p><a href="https://www.ibm.com/docs/en/db2/11.5?topic=architecture-db2-process-overview">IBM Db2</a></p><p><a href="https://github.com/google/leveldb/blob/main/doc/impl.md">LevelDB</a></p><p><a href="https://mariadb.com/kb/en/understanding-mariadb-architecture/">MariaDB</a></p><p><a href="https://azure.microsoft.com/en-us/blog/a-technical-overview-of-azure-cosmos-db/">Microsoft Azure Cosmos DB</a></p><p><a href="https://www.geeksforgeeks.org/microsoft-azure-azure-sql-database/">Microsoft Azure SQL Database</a></p><p><a href="https://learn.microsoft.com/en-us/azure/synapse-analytics/sql/overview-architecture">Microsoft Azure Synapse Analytics</a></p><p><a href="https://www.geeksforgeeks.org/intro-to-sql-server-architecture/">Microsoft SQL Server</a></p><p><a href="https://www.geeksforgeeks.org/mongodb-architecture/">MongoDB</a></p><p><a href="https://www.geeksforgeeks.org/architecture-of-mysql/">MySQL</a></p><p><a href="https://www.oracle.com/webfolder/technetwork/tutorials/architecture-diagrams/19/pdf/db-19c-architecture.pdf">Oracle</a></p><p><a href="https://www.geeksforgeeks.org/postgresql-system-architecture/">PostgreSQL</a></p><p><a href="https://architecturenotes.co/p/redis">Redis</a></p><p><a href="https://github.com/facebook/rocksdb/wiki/RocksDB-Overview">RocksDB</a></p><p><a href="https://www.scylladb.com/product/technology/">ScyllaDB</a></p><p><a href="https://docs.singlestore.com/db/v8.9/introduction/distributed-architecture/">SingleStore</a></p><p><a href="https://docs.snowflake.com/en/user-guide/intro-key-concepts">Snowflake</a></p><p><a href="https://www.sqlite.org/arch.html">SQLite</a></p><p><a href="https://docs.pingcap.com/tidb/stable/tidb-architecture">TiDB</a></p><p><a href="https://docs.yugabyte.com/preview/architecture/">YugabyteDB</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*T_RMgd8mIEvXhgRJIYUM0A@2x.jpeg" /></figure><p>Happy <a href="https://www.cs.jhu.edu/~jason/advice/how-to-read-a-paper.html">readings</a>!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=750297f5d6f4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A look at Aurora DSQL’s architecture]]></title>
            <link>https://medium.com/@hari-db/a-look-at-aurora-dsqls-architecture-93a5dbc3b856?source=rss-a91680219e18------2</link>
            <guid isPermaLink="false">https://medium.com/p/93a5dbc3b856</guid>
            <category><![CDATA[database]]></category>
            <category><![CDATA[aurora]]></category>
            <category><![CDATA[distributed-database]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <dc:creator><![CDATA[Hari Krishna Sunder]]></dc:creator>
            <pubDate>Wed, 11 Dec 2024 05:35:07 GMT</pubDate>
            <atom:updated>2024-12-11T14:50:09.294Z</atom:updated>
            <content:encoded><![CDATA[<p>Amazon has now entered the elite club of distributed databases with the <a href="https://aws.amazon.com/blogs/database/introducing-amazon-aurora-dsql/">announcement</a> of DSQL!</p><h3>What is DSQL?</h3><p>DSQL is a serverless distributed SQL database for online transaction processing (OLTP). It’s Postgres compatible (with <a href="https://docs.aws.amazon.com/aurora-dsql/latest/userguide/working-with-postgresql-compatibility-unsupported-features.html">limitations</a>) with atomic clocks. It’s sweet spot is new geo-distributed apps that require ACID compliance and low latency reads.</p><h3>DSQL architecture</h3><p>The architecture of DSQL is explained here</p><ul><li><a href="https://youtu.be/huGmR_mi5dQ?si=uXXCWqSzh_l1YKTH">AWS re:Invent 2024 — Deep dive into Amazon Aurora DSQL and its architecture (DAT427-NEW)</a></li><li><a href="https://brooker.co.za/blog/2024/12/04/inside-dsql.html">DSQL Vignette: Reads and Compute</a></li><li><a href="https://brooker.co.za/blog/2024/12/05/inside-dsql-writes.html">DSQL Vignette: Transactions and Durability</a></li><li><a href="https://brooker.co.za/blog/2024/12/06/inside-dsql-cap.html">DSQL Vignette: Failovers</a></li></ul><p>This diagram shows it in all it’s glory</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/855/0*cAel0W2jj_Cg9eQw.jpg" /><figcaption>Aurora DSQL architecture</figcaption></figure><p>But, wait! This does not look like a database. Whats this Adjudicator and Journal. And where is my WAL? How does this give me access to a table? Even our typical distributed database building block, the shard is missing!</p><h3>DSQL architecture simplified</h3><p>I shall try to simplify this and replace the component names with more standard ones like Shards, WALs, and Leaders.</p><p><strong>NOTE</strong>: This is a very crude simplification. Remember, the DSQL team has picked different names for good reasons. This is just a way to map it to existing systems to help make it a little bit easier to understand.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hG2pMBkPRh0jOingPI73yw.jpeg" /><figcaption>Aurora DSQL architecture simplified</figcaption></figure><p>Now this looks more similar to Spanner, CockrachDB, YugabyteDB,...</p><ul><li>Router/Load Balancer: Authentication and routing of new connections to a QP.</li><li>QP: Query Processors per region sitting close to the app.</li><li>Adjudicator/Shard Leader: Each of these is responsible for ensuring the consistency of a portion of the database. No actual data is stored here.</li><li>Journal/WAL(s): The god of durability and high availability.</li><li>Storage/Shard follower: This is where the data actually resides.</li></ul><p>DSQL has split up the shard into its fundamental building blocks. This makes it a microservice-based distributed system. Each component can scale independently of the other, and they are all highly available. Depending on the size of the data, its rate of change, and the percentage of data that is changed, they can scale up or down individual components. This is what makes it serverless.</p><p>Query Processors can be spun up and down as needed, which makes connection limits a thing of the past.</p><p>The reads go straight to Storage (Shard followers) and skip locks, which gives them very low latency. The tradeoff is that it limits the database to only Snapshot Isolation with fail-on-conflict behavior. The apps have to retry the writes on these failures and model the schema to avoid hot spots.</p><p>When you write, you need to ensure concurrent inserts, updates, and deletes to the same row get synchronized. For this, the writes get sent to Adjudicators, each of which is assigned one part of the database. If in one transaction you modify multiple rows that are served by multiple Adjudicators, then they perform something like a 2-phase commit across them.</p><p>Once the write has been approved, it gets persisted in the Journal. And from there they get applied to Storage, completing the cycle.</p><p>One issue with reading from a follower is that it can only provide stale data since it takes time for the change to get there from the leader. DSQL circumvents this by using a combination of atomic clocks, stable networks and incurring the penalty of the delay on writes. The exact details of this have not yet been fully disclosed yet.</p><p>As a distributed system, this is a very unique architecture and definitely a very cool one! There just isn&#39;t anything else like it. But is this a good architecture for an OLTP database that is trying to replace Postgres?</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=93a5dbc3b856" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>