<?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 Rahul Pradeep on Medium]]></title>
        <description><![CDATA[Stories by Rahul Pradeep on Medium]]></description>
        <link>https://medium.com/@rahulpradeep?source=rss-bab508154895------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*Jc4Vt-OxfZ_X8eGPsPPLKQ.jpeg</url>
            <title>Stories by Rahul Pradeep on Medium</title>
            <link>https://medium.com/@rahulpradeep?source=rss-bab508154895------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 16:27:06 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@rahulpradeep/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[Weekend experiments with Generative AI — Part 1]]></title>
            <link>https://rahulpradeep.medium.com/weekend-experiments-with-generative-ai-part-1-9858cd532cc8?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/9858cd532cc8</guid>
            <category><![CDATA[generative-ai]]></category>
            <category><![CDATA[chatgpt]]></category>
            <category><![CDATA[llm]]></category>
            <category><![CDATA[langchain]]></category>
            <category><![CDATA[gpt]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Mon, 29 May 2023 08:47:35 GMT</pubDate>
            <atom:updated>2023-05-29T10:00:45.859Z</atom:updated>
            <content:encoded><![CDATA[<h3>Weekend experiments with Generative AI — Part 1</h3><p>Generative AI has been blowing everyone’s mind. I am no exception. Like many others, I do my daily conversations with ChatGPT or Bard. They wrote me poems, stories and code. From “meaning of life” to “how do you combine general relativity and quantum mechanics”, I have asked them everything. For the most part, the answers were satisfactory. For some, it made things up (<a href="https://en.wikipedia.org/wiki/Hallucination_(artificial_intelligence)">hallucination</a>). Like humans, AI can make mistakes too! This remarkable progress in AI has got me excited, worried and confused all at the same time. I truly think this is going to disrupt the tech industry.</p><p>In this series of blog posts, I will jot down my learnings and thoughts from the various experiments I will be doing in the quest to understand GenAI deeply.</p><p>I have been playing around with <a href="https://python.langchain.com/en/latest/index.html">LangChain</a> this weekend. I asked my friend Bard to describe LangChain in about 50 words.</p><blockquote>LangChain is a software development framework that simplifies the creation of applications using large language models. It provides a standard interface for LLMs, a selection of LLMs to choose from, and examples of end-to-end applications.</blockquote><p>The one abstraction that stood out for me was Agents. Agents are essentially LLMs which are taught to think step-by-step and reason and act at each step. This prompting framework is <a href="https://www.promptingguide.ai/techniques/react">ReAct framework</a>. For a question, LLMs are prompted to think step-by-step and tries to reason about the next action to take. Agents are given access to a bunch of tools (e.g Google search, Calculator, Code Generator, etc) which lets them actually take those actions. The outputs of the actions taken are observed and the LLM reasons about the next action to take from those observations. This though-action-observation loop continues and it stops when there is no action to take and the question is answered.</p><p>To play around with this, I created a simple app based on LangChain agents which loads your CSV data and lets you chat with it. The agent used Pandas as the tool to do operations on the dataset. I used the Kaggle <a href="https://www.kaggle.com/datasets/loveall/clicks-conversion-tracking">sale conversion optimization dataset</a> for this experiment.</p><p>Here are some of the snippets of the chats I did with this agent. The verbose logs depicts how the agent arrives at the result.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1010/1*tMX9-hyxQe4PwKZsBktcSg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*irao1zFce6PEZfl6Vg0lIQ.png" /></figure><p>Here, the agent was able to understand what a <em>click through rate</em> means. This is sort of expected since it is a pretty common term and the LLM would have an understanding for this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1006/1*f6b4WP__TfLqUpLpygrrqA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A31lazsaxadet_4wUVbfcg.png" /></figure><p>The agent wasn’t able to understand what <em>conversion rates</em> meant. It instead did all the calculations based on <em>conversions</em>. An honest mistake I guess !</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1006/1*6d9XG_mBt12ybO0Qiq0C2w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*caDo7oFg3k825_05YGbgOA.png" /></figure><p>It is fascinating how the agent built up the Pandas query step by step. By this point, I am not at all surprised that the LLM understood that <em>CTR</em> and <em>click through rate</em> meant the same.</p><p>It seems prompting smartly makes an LLM smarter. Ideas like chain-of-thought reasoning forms the basis of ReAct. I also stumbled upon this — <a href="https://www.promptingguide.ai/">https://www.promptingguide.ai/</a> , which is a great guide into explaining some of these concepts with examples.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9858cd532cc8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Capacity estimation for compute heavy web applications]]></title>
            <link>https://rahulpradeep.medium.com/capacity-estimation-for-compute-heavy-web-applications-68be0b232a80?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/68be0b232a80</guid>
            <category><![CDATA[internet]]></category>
            <category><![CDATA[scaling]]></category>
            <category><![CDATA[web]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[cloud-computing]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Fri, 29 Jul 2022 17:46:13 GMT</pubDate>
            <atom:updated>2022-07-29T17:58:40.421Z</atom:updated>
            <content:encoded><![CDATA[<p>Estimating the number of cores, memory and disk your application needs is pivotal to ensuring optimal resource usage and minimising cost. To understand how capacity estimation can be done, we need to understand the kind of application we are dealing with. Broadly an application can be either compute heavy or I/O heavy. In this post, I will cover the key things to keep in mind while estimating capacity for compute heavy applications.</p><h3>Compute Heavy Applications</h3><p>Web applications which primarily deals with doing expensive computations with minimal or no I/O calls are classified as compute heavy. For example — given a user and their shopping cart, compute the total cart value, given a user and recommended products, score using an ML model and rank them, etc.</p><p>In such kind of applications, the most important physical resource are the CPU cores. So, how do you come up with the number of CPU cores required for your application ? Well, we need to look at the requirements.</p><p>Let’s say we need to build an e-commerce mobile app which needs to display a ranked list of recommended products to the user on its homepage. We are particularly interested in estimating capacity for the Ranking Service which takes a user and a set of products he recently interacted with as input and outputs a ranked list of products based on scoring and ranking the products using an ML model. Assuming that the ML model is stored in memory and there is no extra I/O required, this service is a compute heavy service. Let’s answer a few basic questions to understand the scale of the system.</p><blockquote><strong><em>What is the maximum no of concurrent users accessing the homepage?</em></strong><em> </em>Around 100K users at peak.</blockquote><blockquote><strong><em>What is the expected latency of a single homepage render for an optimal user experience?</em></strong><em> </em>Latency should be 500 ms or better.</blockquote><p>As per the requirement, 100K users will be concurrently opening the homepage. So, our application should be able to support 100K concurrency. To enable this, we need to have 100K application threads in our service. Here, a single application thread will independently handle a user at peak load. But how does application threads equate to physical cores?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/644/1*Fggtu25OrHFl2vcVt_svsg.png" /><figcaption>4 physical cores handling 4 concurrent users. Here, concurrency == parallelism</figcaption></figure><p>In a compute heavy application, all the work happens in the CPU core. This means, all of what a single application thread does in our example, will happen in a CPU core. So, can we allocate 100K physical cores to our application? Of course we can ! Would it be optimal? Well, depends on the compute workload. Let’s answer a few more questions.</p><blockquote><strong>What is the on-CPU time for the ranking computation?<em> </em></strong>Worst case, it can take around 300 ms of CPU time.</blockquote><p>Since our compute takes at most 300 ms on-CPU time, we still have around 200 ms to spare as our target homepage render latencies are around 500 ms. So, if we give 100K physical cores, each core will handle a single user request and the response will be returned in 300 ms. Since we have an extra 200 ms at hand, can we use lesser number of physical cores by trading off latencies? Of course, we can! So, how many physical cores can we save? Here is where it gets tricky.</p><h4>Concurrency != Parallelism</h4><p>Often we confuse between concurrency and parallelism. In our Ranking Service example, if we had allocated 100K cores to support 100K concurrency, we would have used a parallelism of 100K, by virtue of 100K cores, to support 100K concurrency. While this is totally acceptable, it may not be very optimal.</p><p>To understand this better, let’s refresh our memory on how threads are scheduled on CPU. In a typical OS, threads are given a time-slice of the CPU in a round robin manner. Every time a thread is taken out of the CPU, the context (operating data, instructions, etc) is saved so that it can be re-used the next time it is scheduled on the CPU. This is called thread context switch. There is a cost associated with a context switch and it often depends on the context itself.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/324/1*677_QLqE7MTM8NkRPcwbGA.png" /><figcaption>2 physical cores handling 4 concurrent users. . Here, concurrency != parallelism</figcaption></figure><p>Enough of OS theory ! So, how many cores should the Ranking Service use? The answer is — the number of cores at which off-CPU times (includes context switch times) of a thread aren’t exceeding 200 ms in a 500 ms window. That sounds complicated ! An easy way to determine the number is by performing a load test. We can perform a load test by iterating on the number of cores until your max latencies are 500 ms and concurrency supported is 100K. More often, this will be the limit of your system and CPU utilisation will be very high. Let’s say we performed the load test and the optimal number of cores came out to be 70K. So, we were able to support a concurrency of 100K using a parallelism of 70K.</p><h4>Load Distribution</h4><p>In our Ranking Service example, based on our load test, we can support a peak concurrency of 100K with 70K physical cores with a max (or 99th percentile) latency of 500 ms. What if the peak load happens only for 1 hour in a day and rest of the 23 hours, the peak never exceeds 50K? This means, for 23 hours in a day, most of our cores will be idle. This is never a good thing since we will paying for that compute unnecessarily.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/562/1*g4WZmi28ZwSLgob1iL7kVw.png" /></figure><p>If we know the times of the day when the peak load happens, we can spawn additional cores just before the peak hours and destroy the cores after that. This can even be done on demand when you detect extra load. These capabilities of auto / on-demand scaling are very common in pretty much every cloud service provider these days. This way, we can further decrease the overall physical cores footprint of our application.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=68be0b232a80" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Spark Streaming — the Good, the Bad and the Ugly]]></title>
            <link>https://rahulpradeep.medium.com/spark-streaming-the-good-the-bad-and-the-ugly-41272c0f1b8b?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/41272c0f1b8b</guid>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[spark-streaming]]></category>
            <category><![CDATA[stream-processing]]></category>
            <category><![CDATA[apache-spark]]></category>
            <category><![CDATA[apache-spark-streaming]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Mon, 25 Oct 2021 09:55:07 GMT</pubDate>
            <atom:updated>2021-10-25T11:22:00.351Z</atom:updated>
            <content:encoded><![CDATA[<h3>Spark Streaming — the Good, the Bad and the Ugly</h3><p>Stream processing systems have become increasingly popular in the last decade. It found its usage in a variety of real time systems across the industry. There are mainly two ways to implementing a stream processing system — Continuous Streaming and Micro-batches.</p><h4>Continuous<strong> streaming</strong></h4><p>The likes of Apache Storm and Apache Flink implements this approach. The idea is that the processing happens at the granularity of a single event in the stream. As soon as the event appears in the stream, the system reads it, processes it and moves it forward. Single event processing latencies are very low in this approach.</p><h4>Micro-batches</h4><p>This approach is born out of fitting a batch processing system into the streaming world. The key idea is to form batches of a small number of events and process them like a batch processing system would do. The system waits a certain duration to collect a batch of events before starting to process them.</p><p>Micro-batching approach is a natural evolution of a batch processing system. This extension was elegant and has a lot of positives going for it. But in certain scenarios, it starts to show weaknesses. For the remainder of the post, we will gloss over the good bit (because that is not interesting) and cover the bad bits (the interesting ones) fairly in detail.</p><h3>The Good</h3><h4>High throughput</h4><p>In most of the real life use cases like real time data processing systems, etc micro-batch based stream processing is good enough since we don’t really need the milli-second latencies. For real time data processing systems, we want higher throughput i.e maximum number of events passing through the system in a given time. But if we have a real time chat delivery, it might not be the best idea to implement it in Apache Spark.</p><h4>Interoperability with batch processing code</h4><p>With many minor changes, you could change your Spark stream processing workloads to batch processing and vice versa. All the key features available in the Spark batch processing world is also available in Spark streaming.</p><h3>The Bad and the Ugly</h3><p>While most of the drawbacks mentioned below are specifically based on my experience in Spark streaming but it should be equally true for any micro-batch based streaming system.</p><h4>Starvation while consuming from multiple stream sources</h4><p>Spark streaming allows you to write streaming applications which consumes from multiple streaming sources. For ex — a streaming application to generate real time recommendations can listen to <em>order</em> events and <em>product-view </em>events. While this can seem to be a good thing, it has a bunch of negatives which are hard to ignore. To understand this, let’s take a step back and understand how a Spark streaming application works when you have multiple streams involved.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/881/1*dEBbbxsFA6vYrwxEmRXbVg.jpeg" /></figure><p>If computation of the events in one of the streams is more expensive than the other, the throughput of the system with respect to the computationally cheaper stream suffers.</p><p>To workaround this, we will have to split this application into two, each consuming from one stream. This too has limitations.</p><ul><li>Splitting application based on stream sources can only be done if there are interactions between streams.</li><li>Additional overhead of managing and maintaining two applications instead of one even though the business logic is very similar.</li></ul><h4>Plethora of jobs scheduled for one micro-batch</h4><p>In spark, every <a href="https://spark.apache.org/docs/latest/rdd-programming-guide.html#actions"><em>action</em></a> results in a job getting scheduled for the micro-batch. Suppose your streaming application does the following:</p><pre>// pseudo code for generating popular products and user recommendations</pre><pre>// read events from stream sources<br>product_view_events = sparkContext.readStream(&#39;product_view&#39;);<br>order_events = sparkContext.readStream(&#39;product_view&#39;);</pre><pre>// group events for a user<br>grouped_product_view_events =    product_view_events.map(_business_logic_function_).groupBy(user_id);</pre><pre>// group product view events for a product id<br>pid_grouped_product_view_events =    product_view_events.map(_business_logic_function_).groupBy(product_id);<br>pid_grouped_product_view_events.foreach(_update_view_count_per_day_);</pre><pre>grouped_order_events =    order_events.map(_business_logic_function_).groupBy(user_id);</pre><pre>// update recommendations for a user in a database<br>grouped_product_view_events.foreach(_update_user_recommendations_);<br>grouped_order_events.foreach(_update_user_recommendations_);</pre><p>The above application will result in three jobs being scheduled, one for every action (calls to foreach function).</p><p>By default, Spark schedules these jobs sequentially. Which means, if the job corresponding to ‘<em>popular products</em>’ take a lot of time, user recommendations would be affected. Overall time taken for a single micro-batch to complete would be the sum of time taken by all the three jobs. Here, the total number of cores needed for the application will be the maximum required cores of all the jobs. But since job executions are sequential, some jobs which require lesser cores will bring down the utilisation of the total cores allocation. This isn’t very efficient.</p><p>There are ways to fix this, but it comes with its own challenges and drawbacks. Some of them are:</p><h4><strong><em>Running jobs within a micro-batch concurrently</em></strong></h4><p>There is a setting in spark which allows us to schedule and execute jobs within a micro-batch concurrently. Because of higher concurrency demand, we would need to allocate more cores to see the real benefit.</p><p>In our previous example, there are two jobs which originate from ‘product_view’ events. Running them concurrently would mean that there are multiple reads from the stream source and most of the compute is duplicated. In a sequential execution mode, we can eliminate this concern by <a href="https://spark.apache.org/docs/latest/rdd-programming-guide.html#rdd-persistence">caching</a> intermediate results.</p><h4>Breaking jobs into multiple applications</h4><p>Breaking applications based on stream number of jobs adds an additional overhead of managing the code and deployment for each of these applications. This particularly becomes painful when the multiplexing factor between stream source and dependent jobs is high.</p><p>Similar to concurrent job executions, this also has the issue of compute duplication.</p><h4>No HA during application upgrades</h4><p>When you deal with real-time applications, you <strong>cannot</strong> compromise on its availability. In case of simple web service where you have many machines running the same application code, any deployment strategy supporting high availability would have some machine up and running at all times. This ensures a smooth upgrade of the application.</p><p>In a real time streaming application based on Spark streaming, this is not really possible out of the box. This is because there is one component — spark driver which is responsible for determining and schedule the next micro-batch. The driver is really a single point of failure. So, any downtime of driver causes a downtime of the application. But Spark master limits the damage by supervising it. So, any driver failure will be noticed by the Spark master and it restarts it.</p><h3>Light at the end of the tunnel</h3><p>Some of the drawbacks of enabling concurrent job executions like higher resource demand and inability to use caching is a necessary evil. If the re-compute cost is fairly small and you have enough capacity for the higher resource demand, then simply enabling concurrent job executions in Spark streaming can improve your application’s overall performance.</p><p>Continuous streaming approach doesn’t have a single driver responsible for cutting a micro-batch. This means that every node / thread in your distributed continuous streaming application will independently be consuming and processing events. This approach seems to eliminate some of the concerns we have with micro-batch based streaming. Fortunately, Apache Spark has an experimental <a href="https://spark.apache.org/docs/latest/structured-streaming-programming-guide.html#continuous-processing">continuous streaming mode</a>, which do seem like a more suitable approach for real time streaming applications.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=41272c0f1b8b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The “I” in ACID — Weak Isolation Levels]]></title>
            <link>https://rahulpradeep.medium.com/the-i-in-acid-weak-isolation-levels-7e2dbbadd45e?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/7e2dbbadd45e</guid>
            <category><![CDATA[database]]></category>
            <category><![CDATA[mysql]]></category>
            <category><![CDATA[isolation-level]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Wed, 20 Oct 2021 16:34:19 GMT</pubDate>
            <atom:updated>2021-10-20T16:34:19.540Z</atom:updated>
            <content:encoded><![CDATA[<h3>The “I” in ACID — Weak Isolation Levels</h3><p>ACID is an acronym for<strong> A</strong>tomicity, <strong>C</strong>onsistency, <strong>I</strong>solation and <strong>D</strong>urability. ACID compliant databases provides</p><ul><li><strong>Atomicity</strong>, if it has the ability to group multiple statements together and execute it as if it were executing a single atomic statement. There can only be two outcomes for such an execution, either all the statements execute successfully or all statements fail. This atomic execution is called a <em>transaction</em>.</li><li><strong>Consistency</strong>, if it can uphold your data invariants. This is highly dependent on the data modelling. If the modelling takes care of defining these invariants using the integrity constraint mechanisms that the database provides, a consistent (as per ACID) database ensures that those invariants hold true always.</li><li><strong>Isolation</strong>, if the database guarantees that concurrent transactions don’t affect each other.</li><li><strong>Durability</strong>, if the database ensures that every transaction that is committed are not lost. Absolute durability is not possible of course (total failure scenarios), but a durable database ensures that it safeguards against known patterns of failures.</li></ul><p>In this post, we will pivot around <strong>Isolation</strong>. Absolute isolation is possible if all transactions are <strong><em>serializable</em></strong> i.e the final outcome will be the same as if all transactions were executed sequentially. The simplest way to achieve serializability is to force all transactions to execute on a single thread. This would, of course, incur a performance penalty and wouldn’t be suitable for real world applications. Before we look at better ways to achieve serializability, we will look at some of the weaker isolation levels that databases provide.</p><h4>Why do we need isolation at all ?</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*l6vscXb4mQdJ2r5LQI9HHw.png" /><figcaption>Dirty reads. Ref: “Designing Data-Intensive Applications” by Martin Kleppmann</figcaption></figure><p>Here, user 1 sends an email to user 2. Sending an email involves adding an entry for the new email for user 2 and incrementing the unread count for user 2. If there were no isolation at all, there is a possibility that user 2 would see stale unread count even after receiving the new email.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YrO1dXEGqBUApcJLV6hZlg.png" /><figcaption>Dirty writes. Ref: ‘Designing Data Intensive Systems’ by Martin Kleppman</figcaption></figure><p>This could happen because reads of un-committed records are possible. These reads are called <strong><em>dirty reads</em></strong>. Similar to dirty reads, there could be <strong><em>dirty writes </em></strong>as well, if a transaction overwrites an uncommitted value.</p><h3>Read Committed Isolation</h3><p>In a read-committed isolation level, dirty reads are prevented by making sure the database only allows reading committed entries.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d-sdBIkTUa_RvWa0bdUEiA.png" /><figcaption>No dirty reads. Ref: “Designing Data-Intensive Applications” by Martin Kleppmann</figcaption></figure><p>To prevent dirty writes, every transaction can take a row level lock which will prevent any other transaction to overwrite an uncommitted value.</p><p>Dirty reads can also be prevented by having the read transaction also taking the same lock but this could really hamper performance of read heavy systems. Any long running write transaction could block the read transactions for a long time. Ideally we don’t want writers to block readers or readers to block writers.</p><p>For every row, if we store both committed as well as uncommitted versions, any reader can just use the committed version while the writer continues its transaction by working on the uncommitted version. Once write transaction is complete, the previous committed version if replaced by the new one, seemingly atomically.</p><p>Although, there is a slight overhead of storing two version of every row, it pays off because of the significant improvement in performance.</p><h3>Snapshot Isolation</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-U1AzyzY1kW41N_wjHMzJQ.png" /><figcaption>Read skew in read-committed. Ref: “Designing Data-Intensive Applications” by Martin Kleppmann</figcaption></figure><p>This is a perfectly valid scenario in read-committed isolation. But from a user point of view, Alice sees a total of 900 in her bank accounts while she was expecting 1000. This expectation mismatch in Alice’s read query is called read skew or non-repeatable read. If Alice repeats her first read query, she will see 600 and a total of 1000 in her two bank accounts, which is consistent. The fact that Alice found the database to be in an inconsistent state needs to be fixed nevertheless.</p><p>We want the data to not change within a transaction i.e repeatable read. To achieve this, database provides a higher isolation level called <strong><em>Snapshot Isolation</em></strong>.</p><p>To achieve repeatable read, we have to ensure that read queries return the data which was last committed throughout the duration of a read transaction. From the read-committed implementation, we have the last committed data already which we can use here. But if we have a long running read transaction, we would need more than one version of committed data. This is because there could be multiple write transactions that could complete while the read transaction is in progress.</p><h4>Multi-version Concurrency Control (MVCC)</h4><p>Snapshot isolation is implemented using MVCC, where we have multiple versions of a row. Every new write, carries with it, the transaction id. For every read transaction, all reads will happen on the version of the data belonging to the latest transaction lower than the current read transaction id.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Tje55--GvuNvVLf5IM7unQ.png" /><figcaption>MVCC in action. Ref: “Designing Data-Intensive Applications” by Martin Kleppmann</figcaption></figure><p>Snapshot isolation did solve a lot of our issues but there are still many scenarios where it can lead to erroneous outcomes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zi-viBM5El1ke_yFyI6IRA.png" /><figcaption>Concurrent read-modify-write operations tend to lose updates even in a snapshot-isolation mode. Ref: “Designing Data-Intensive Applications” by Martin Kleppmann</figcaption></figure><p>Here, the final counter value should be 44, but we lost one of the update. To achieve this, we need to make sure both these transactions happen serially. We will discuss <strong><em>Serializability </em></strong>in a future blog post.</p><h3>References</h3><ul><li>“Designing Data-Intensive Applications” by Martin Kleppmann</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7e2dbbadd45e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Amazon Dynamo — a conceptual overview (Part 3)]]></title>
            <link>https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-3-86b51f985d98?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/86b51f985d98</guid>
            <category><![CDATA[gossip-protocol]]></category>
            <category><![CDATA[consistent-hashing]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[dynamodb]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Wed, 07 Jul 2021 19:56:08 GMT</pubDate>
            <atom:updated>2021-07-07T19:56:08.075Z</atom:updated>
            <content:encoded><![CDATA[<h3>Amazon Dynamo — a conceptual overview (Part 3)</h3><p>In <a href="https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-1-3bdb2e78f08b">Part 1</a> and <a href="https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-2-a9c88d6870">Part 2</a> of the series, I talked about all the cool concepts used in Amazon Dynamo. The key aspect of the system is the decentralised nature of its architecture. This enables it to be incrementally scalable. This architecture also brings in challenges in terms of choosing the nodes where the replicas will lie, how would cluster wide changes be propagated to all nodes, etc.</p><p>We will first look at how the data placement is done using Consistent Hashing and how this scheme drives the logical topology of the cluster. We will also see how cluster wide knowledge is made available to all nodes in the cluster in the absence of a centralised brain.</p><h3>Consistent Hashing</h3><p>Any get() or put() request for a key needs to be routed to the node which hold the partition which contains the key. But what is a <strong><em>partition</em></strong> exactly? A partition is a set of keys. As the dataset outgrows the capacity of a single machine, it is partitioned and spread across a number of machines. In this scheme, it is evident that for every request for a key, we need to be able to determine the partition and in-turn the node which holds the partition.</p><p>I will shamelessly plug in <a href="https://rahulpradeep.medium.com/consistent-hashing-6583836463c0">another post of mine describing the concept of consistent hashing</a>. As it is shown in this post, consistent hashing requires the nodes to be laid out logically as a ring. In fact, it won’t be outrageous to think that the ring topology in Amazon Dynamo is more inspired by this than anything else.</p><h3>Preference List</h3><p>In the consistent hashing algorithm, once the point on the ring is determined by hashing the key, the next node in the clockwise direction in the ring is the node which holds the desired partition.</p><p>In a system where there is one master replica and a few followers for a partition, usually the master replica will be the one that is determined from the consistent hashing algorithm. The followers are chosen such that those nodes lie in a different physical machine, rack or even data centre.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/988/1*RkYSaBEGKG4cBvNQLM4P3Q.png" /></figure><p>In a master-less system like Amazon Dynamo, all the N replicas are determined using the Consistent Hashing algorithm. The next N nodes that lie in the clockwise direction in the ring will hold the replicas for the key range.</p><p>This list of N nodes found using the Consistent Hashing scheme are called the <strong><em>preference list.</em></strong></p><h3>Gossip Protocol</h3><p>In the absence of a centralised brain, how are cluster wide knowledge, like cluster membership changes (node in or node out), etc notified to all nodes ?</p><p>Amazon Dynamo uses a protocol called <strong><em>gossip protocol</em></strong> to make information available across all nodes in the cluster. A node randomly chooses another peer node and propagates the information about the changes and this goes on until all the nodes are visited.</p><h3>References</h3><ul><li><a href="https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html">https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=86b51f985d98" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Amazon Dynamo — a conceptual overview (Part 2)]]></title>
            <link>https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-2-a9c88d6870?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/a9c88d6870</guid>
            <category><![CDATA[hinted-handoff]]></category>
            <category><![CDATA[dynamodb]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[high-availability]]></category>
            <category><![CDATA[merkle-tree]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Tue, 06 Jul 2021 13:35:23 GMT</pubDate>
            <atom:updated>2021-07-06T13:35:23.365Z</atom:updated>
            <content:encoded><![CDATA[<h3>Amazon Dynamo — a conceptual overview (Part 2)</h3><p>In <a href="https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-1-3bdb2e78f08b">Part 1</a> of this series, we saw the various techniques that Amazon Dynamo employs to achieve high availability for write requests. In this post, we will deep dive into the different failure handling techniques used by Dynamo.</p><h3>Quorum Failure</h3><p>In <a href="https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-1-3bdb2e78f08b">Part 1</a>, we saw how we can configure the values of R and W to achieve different levels of consistency in the system.</p><p>To achieve strong consistency, R and W values are configured such that R+W&gt;N, where N is the number of the replicas for a given partition. For example, let N = 5, R=3 and W=3. In this case, if there is a network partition causing 3 of the nodes to be unreachable, the system becomes unavailable for both reads and writes for the keys in that partition.</p><p>In an eventual consistency configuration, a reasonable configuration would be N=5, R=1 and W=3. In this mode, R+W≤N and hence there could be replicas with stale values. Even in this mode, writes can fail if a network partition causes 3 of the nodes to be unreachable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*k-W2ma3D2o4rM5ZAd1n72w.jpeg" /></figure><p>Didn’t we emphatically described Amazon Dynamo as an<strong><em> always writeable store</em></strong> ?</p><p>It sure is ! If majority of the replicas are unreachable, the system seeks help from the other live nodes. It uses a technique called <strong>hinted handoffs</strong>.</p><h3>Hinted Handoffs</h3><p>If nodes holding some of the replicas are unreachable, then Dynamo asks other live nodes to hold the data on behalf of the unreachable ones.</p><p>Let us suppose there are N replicas and 1 of the replicas are unreachable. In this case, when write arrives at one of the N-1 live nodes, it persists in its local disk and sends off the data to the other N-2 live replica nodes. It also sends off this data to 1 of the live nodes in the cluster, which is not the assigned replica for the partition. Along with the data, a context is also sent. This context contains information about the actual unreachable node. Since this node is not the assigned replica for the partition, it writes this in a separate location in its disk and periodically checks if the actual node is back online. Once that node is back online, it transfers the replicated data and deletes it from its local disk. This technique is called <strong><em>hinted handoff</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/952/1*Z8Ff5jbb_uLqxjBrOYHi2g.png" /></figure><h4>Hinted Replica Failure</h4><p>In the above example, Node 3 takes the hint and persists in its local temp storage. By the time Node 2 comes back online, Node 3 fails permanently. In this scenario, Node 2 replica will go out of sync with other replicas (Node 0 and Node 1) permanently.</p><p>Hence hinted handoff is not sufficient to handle such permanent failures. We would need a mechanism to synchronise the replicas periodically. One way to do it would be to exchange a hash value of the entire replica and in case of a mismatch, synchronise it by sending all the data from one node to another. The node which has the maximum number of writes (although it is not clear from the paper) can be the one who initiates the data transfer in case of a hash mismatch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/713/1*OWBfrzuh5UXWdy9r6XLO0g.png" /></figure><p>Since this involves a large amount of data to be transferred over network, this is not desired. Another strategy would be to do these round trips for every key in the replica. This is clearly expensive and not desired. Both of these strategies require a linear scan on all the keys in the replica to determine the mismatches.</p><p>Amazon Dynamo synchronises replicas by storing the hashes of each record in a data structure known as Merkle Trees.</p><h3>Replica Synchronisation using Merkle Trees</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GfKImZAfzpvxdPX4xNJKXg.png" /></figure><p>In Merkle Trees, each node contains the cryptographic hash of its children. Leaf nodes in the tree corresponds to the key:values pairs in the replica.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/401/1*WeTb4rcwMLU64S_6hOiMcQ.jpeg" /><figcaption>k4:v4 is a mismatch and it is found in log(n) time complexity</figcaption></figure><p>Using this data structure, mismatches can be found in logarithmic time complexity and hence it requires lesser data transfers between nodes.</p><p>Key set held by a node changes when the number of nodes in the cluster changes. This would require a re-calculation of Merkle Trees in those nodes.</p><h3>References</h3><ul><li><a href="https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html">https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html</a></li><li><a href="https://en.wikipedia.org/wiki/Merkle_tree">https://en.wikipedia.org/wiki/Merkle_tree</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a9c88d6870" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Amazon Dynamo — a conceptual overview (Part 1)]]></title>
            <link>https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-1-3bdb2e78f08b?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/3bdb2e78f08b</guid>
            <category><![CDATA[high-availability]]></category>
            <category><![CDATA[big-data]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[amazon-dynamodb]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Mon, 05 Jul 2021 17:54:00 GMT</pubDate>
            <atom:updated>2021-07-06T13:38:42.418Z</atom:updated>
            <content:encoded><![CDATA[<h3>Amazon Dynamo — a conceptual overview (Part 1)</h3><p>I happened to read the Amazon Dynamo paper recently. I have read it before but not nearly as intently. Its architecture manages to bring in multiple computer science concepts together and make it work in tandem to achieve the desired goals of the system.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*lB3tOXodwC8E49jzI0MzHg.png" /><figcaption>Ref: <a href="https://en.wikipedia.org/wiki/Amazon_DynamoDB">https://en.wikipedia.org/wiki/Amazon_DynamoDB</a></figcaption></figure><p>This will be a three part series of posts where each part will focus on a set of concepts used in the architecture of Amazon Dynamo.</p><ul><li><a href="https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-1-3bdb2e78f08b">Part 1</a> will focus on the challenges of building an <strong><em>always writeable store. </em></strong>We will discuss the concepts to overcome those challenges.</li><li><a href="https://rahulpradeep.medium.com/amazon-dynamo-a-conceptual-overview-part-2-a9c88d6870">Part 2</a> will mainly focus on the failure handling techniques like <strong><em>hinted handoffs </em></strong>and<strong><em> replica synchronisation using Merkle Trees.</em></strong></li><li>Part 3 will deep dive into the <strong><em>ring topology</em></strong> in Amazon Dynamo architecture.</li></ul><h3>An always writeable store !</h3><p>Writes are pristine in the world of an always writeable store. They should never go wrong. A typical e-commerce example that the paper mentions is of a shopping cart. Any cart edits done by the user should surely happen. The potential revenue impact of a failure in doing so can be huge in Amazon’s scale.</p><p>To understand what an always writeable store mean, let’s look at simple distributed data storage system where every record (key:value pair) is replicated across the cluster. This redundancy is mainly for fault tolerance as it lets us recover from a node failure by re-using one of the replicas. Redundancy also improves read scalability. We can scatter read requests for a key to all the replicas instead of overloading only one. One of the replicas is assigned master and other followers. Master replica is responsible for handling write requests and followers are updated either synchronously or asynchronously depending on the consistency mode we choose in the system.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*QWKAbmzdmVB5DjRtYc7iDw.jpeg" /></figure><p>In this architecture, let us examine if it is an ‘<em>always writeable store</em>’ by looking at some of the failure scenarios.</p><h4>Master replica failure</h4><p>Since there is a single node (the master) handling writes for a subset of records, this node becomes a single point of failure. Failure of this node can make our system unavailable to write requests. We can surely do better !</p><p>We can promote one of the follower replicas to be the new master and also bring up another follower replica to cover the loss. Is that enough ? Not quite! All the clients need to be notified of this change so that they update their local mappings (record to node mappings) and send all the future write requests to the new master instead of the old one which failed.</p><p>Till now, this system seems to be tolerant of failures towards write requests. What about the in-flight requests just moments before the master replica failure ? Those is inevitably fail and client would need to employ retries to and hope that before all the retries are exhausted, a new fully functional master comes up and client mappings are updated.</p><p>While such a system is fault tolerant towards node failures, there can still be some write request failures while the system is recovering. Retries could take a long time and can impact SLAs. This isn’t an always writeable system yet !</p><h4>Eliminating The Master !</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*vKVhuY9EXDRCYrMuN-QamQ.gif" /></figure><p>If there are no master replicas, who actually assumes the responsibility to handle write requests. The answer is — <em>everyone</em> !</p><p>This definitely invites more trouble. If multiple nodes handle writes, our data can go inconsistent pretty quickly. This might not be as bad as you think, if we are able to resolve the conflicts efficiently<strong> </strong>!</p><p>Either the server or the client can take the responsibility to resolve this conflict. Amazon Dynamo chooses to do this at client side. Clients will have the flexibility to have any strategy for conflict resolution. It could be as simple as ‘<em>last write wins</em>’ or a complex business logic.</p><p>Since every replica can handle writes, we will end up with multiple versions of the same record. We don’t necessarily need to keep around all versions. If we are able to establish causality relations between two versions of the same record, we can simply overwrite the ancestor with the child. The key to this is how we represent versions.</p><h4>Vector Clocks</h4><p>In a single machine, it is easy to establish causality relations if we use local time of the machine as the version. When we have multiple machines like in a typical distributed system, it becomes difficult to establish a causal relation between two events as local clocks might not be consistent with each other.</p><p>Vector clock is simply a vector of local clocks, where each of the machine in the cluster having its own local clock. Every source machine sends its own view of the vector clock at that point along with message to the destination machine. When the destination machine receives this message, it updates its vector clock using the following algorithm.</p><pre>for each clock in destination_vector_clock:<br>   destination_vector_clock[i] = <br>          max(destination_vector_clock[i], source_vector_clock[i])</pre><pre>// local clock of the destination machine <br>// corresponds to destination_vector_clock[k]</pre><pre>destination_vector_clock[k] = destination_vector_clock[k] + 1</pre><p>Amazon Dynamo uses vector clocks to represent versions of every record. If there is a causal relationship between two updates, then the older version is overridden by the later one. Otherwise, both the versions are persisted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q_7J80IBWK5-kcoH7jPBzA.png" /><figcaption>Version change over time. Ref : <a href="https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html">https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html</a></figcaption></figure><h3>Quorum reads and writes</h3><p>As we have seen above, to make the system highly available for writes, we need multiple nodes to participate in the write request. To offer sufficient redundancy, Amazon Dynamo allows us to configure the minimum number of nodes, <strong>W</strong>, that should accept a write request before it is deemed successful.</p><p>The same goes for read requests as well. Any read request is deemed successful only if at least <strong>R </strong>nodes return a valid response. If we set R+W&gt;N where N is the total number of replicas, it mimics a quorum like system. This is because if R+W&gt;N, then at least one node will be common between the read and the write. This gives us a strongly consistent system (CP).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*35fs6xT3P_tNTdOsAYvHnA.png" /><figcaption>R=2, W=2 and N=3</figcaption></figure><h3>Tuneable consistency and durability semantics</h3><p>Amazon Dynamo was built keeping in mind the need for flexibility. As per the <a href="https://en.wikipedia.org/wiki/CAP_theorem">CAP theorem</a>, we can choose <em>consistency</em> or <em>availability</em> in the event of a <em>network partition</em> in a distributed system.</p><p>As we have seen in the above section we can make Amazon Dynamo behave as a strongly consistent system (CP) by configuring the values of <em>R</em> and <em>W</em> such that <strong><em>R+W&gt;N</em></strong>.</p><h4>Eventual Consistency</h4><p>We can achieve eventual consistency if we keep a low value of <strong><em>R, </em></strong>say R=1 and R+W≤N. In this case, read request for a key will go to one of the N replicas but that replica could still hold a stale version of the key.</p><h4>Durable writes</h4><p>If <strong><em>W=1, </em></strong>writes will return as soon as it is persisted in one of the nodes. If that node goes down before replication is completed in at least one of the remaining replicas, we would lose that write. To make it durable, we should have <strong><em>W&gt;1</em></strong>.</p><h3>References</h3><ul><li><a href="https://en.wikipedia.org/wiki/CAP_theorem">https://en.wikipedia.org/wiki/CAP_theorem</a></li><li><a href="https://en.wikipedia.org/wiki/Amazon_DynamoDB">https://en.wikipedia.org/wiki/Amazon_DynamoDB</a></li><li><a href="https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html">https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html</a></li><li><a href="https://en.wikipedia.org/wiki/Vector_clock">https://en.wikipedia.org/wiki/Vector_clock</a></li><li><a href="https://en.wikipedia.org/wiki/Quorum_(distributed_computing)">https://en.wikipedia.org/wiki/Quorum_(distributed_computing)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3bdb2e78f08b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Thundering Herd and Stale Set Operations]]></title>
            <link>https://rahulpradeep.medium.com/thundering-herds-and-stale-sets-2423da2a8703?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/2423da2a8703</guid>
            <category><![CDATA[consistency]]></category>
            <category><![CDATA[thundering-herd]]></category>
            <category><![CDATA[cache]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[web-services]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Tue, 22 Jun 2021 15:16:08 GMT</pubDate>
            <atom:updated>2021-06-22T18:23:44.831Z</atom:updated>
            <content:encoded><![CDATA[<p>In the Internet, a lot of content is consumed on a daily basis. For global services like Google, Facebook, Netflix, etc serving this data to the end users in a seamless manner becomes a priority. To design a web service to satisfy these requirements, we need to be able to retrieve this data very fast at a very high scale. In this post, we will look at how <strong><em>caching</em></strong> can solve this problem and also understand the various problems that comes with it. We will also dig deep into two specific problems that come with caching — <strong><em>thundering herd</em></strong> and <strong><em>stale-sets</em></strong>.</p><h3>Demand-filled Look Aside Caches</h3><p>Web services which serves data from a database often use a cache on the side to prevent load on their DBs. Data in databases are usually stored in disk and serves as the sources of truth for the data.</p><p>As these databases are sources of truth, any modification to the data should be done directly in the DBs. There is escaping from writes. Write load needs to be handled by the DB itself. Can we do something about the read loads ?</p><p>Disk reads are typically slower than in-memory reads. This is because commodity disk hardware is made up of rotating disks, which involves position the head on the circular disk and then reading blocks of data. Solid-state drives offer random access but is way more expensive. RAMs, obviously, offer random-access and are way faster. Since RAMs are also expensive, we can cache a copy of the hot-data in it for faster access. Hot-data can be defined based on your use-case. Typically, we want to cache that subset of data which has the most probability of being read in the near future. A reasonable way to determine this subset is by simply caching recently read data.</p><p>Read requests in a web service can be made faster if we cache some subset of the data in RAM and always look into the RAM before querying the DB. This is called <strong><em>look-aside caching</em></strong>. What happens when the data changes ?</p><p>On any modification of the data, we can simply delete it from the cache. Any subsequent reads won’t find it in the RAM and fill fetch it from the DB. Since we want subsequent reads for this data to not go into the DB, we can fill the cache with this data to benefit in the near future. This type of a cache where the cache is filled on demand for making future reads faster, is called <strong><em>demand-filled look-aside caches</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/1*997nFI1se-bvxF_-h4hGqA.jpeg" /></figure><h3>Caching is powerful, but demands great responsibility !</h3><h4>Permanent in-consistency</h4><p>When multiple concurrent clients observe a cache miss for a key and both of them try to fill the cache, the cached data could become permanently inconsistent with the source of truth database.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/958/1*F7BWhB4w2hPnvjc2MYLsnA.jpeg" /></figure><p>The above diagram illustrates a scenario where we could end up with a permanently inconsistent cache. This scenario is called <strong><em>stale sets</em></strong>.</p><h4>Thundering Herd</h4><p>The above diagram also highlights another problem. Client A and B, both observe a cache miss and try to fill the cache with the latest data from the DB. In a highly concurrent system, many such clients could read from the DB for the same key in a very short span of time. This can create hot-spotting for the key and can bring down our database.</p><h3>Leases</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/958/1*YTCQUqoGZI2ox28GeZ9ndQ.jpeg" /></figure><p>To fix the stale-sets problem, we need to be able to discard the set operation initiated by Client A.</p><p>To do this, every time a client (A) observes cache miss for a key (k), our in-memory cache could be in one of these two states</p><ul><li>Client A is the first client to see this cache miss. In this case, the cache grants a <strong><em>lease</em></strong> to Client A. This lease tells A to go ahead and query the DB for the latest data and set it in the cache.</li><li>Another client already has an <strong><em>active lease</em></strong>. In this case, the cache responds with ‘cache-miss’ but also telling the client to try after after some time.</li></ul><p>This will make sure only one client goes to the database at a time. This will definitely solve the<strong> thundering herd</strong> problem.</p><p>But this still doesn’t solve the <strong><em>stale sets </em></strong>problem. In-memory cache should identify a set operation as stale or not-stale.</p><p>In line with our demand-filled model, we delete the key if it is updated in the DB. When we delete the key, we also expire the <strong><em>active lease</em></strong>, if any, for this key. Now, if we modify our set operation to carry the client’s lease along with the payload, our in-memory cache will be fully equipped to discard any set operation with an <strong><em>expired lease</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/999/1*pQxt3RwlVEjc7IzzAyNx5A.jpeg" /></figure><h3>References</h3><ul><li><a href="https://research.fb.com/wp-content/uploads/2016/11/scaling-memcache-at-facebook.pdf">https://research.fb.com/wp-content/uploads/2016/11/scaling-memcache-at-facebook.pdf</a></li><li><a href="https://instagram-engineering.com/thundering-herds-promises-82191c8af57d">https://instagram-engineering.com/thundering-herds-promises-82191c8af57d</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2423da2a8703" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Materialising de-normalised views from a relational dataset]]></title>
            <link>https://rahulpradeep.medium.com/materialising-de-normalised-views-from-a-relational-dataset-bbf2aba4fa8d?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/bbf2aba4fa8d</guid>
            <category><![CDATA[materializedviews]]></category>
            <category><![CDATA[denormalization]]></category>
            <category><![CDATA[change-data-capture]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[database]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Tue, 22 Jun 2021 12:34:21 GMT</pubDate>
            <atom:updated>2021-06-22T12:34:21.820Z</atom:updated>
            <content:encoded><![CDATA[<p>As the name suggests, Relation Databases are used to store entities and the relationships between them in a normalised manner. Addition to this, they also provide transactional support and indexing. There are many use cases in the industry where we would want to use the same set of relational data in multiple systems. Each of these system can be thought of as a web service responding to a particular kind of user request. Each of this request can be formulated as a query to the dataset. Let’s look at various ways of solving this problem.</p><h3>Stateless Service backed by a DB</h3><p>Every request to this service is re-formulated into a database query (SQL query) and these queries are executed remotely in the database. The service thread waits for the query to be completed in the database. Once the database is done processing the query, it responds back to the service with the ResultSet. This result set is then transformed to a response and sent back to the client.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/651/0*sOQkBfqW6VnkRVhE" /></figure><p>Database queries can be expensive, especially, if it involves processing a large amount of data using operations like joins, unions, groupBy, etc. This can negatively impact the throughout and the latency of the system. One easy way to scale our service would be to cache data in-memory which are frequently accessed. This will improve the throughput of the system. For cache-misses, requests will still take a long time to complete. To improve latency, we might want to store all the data from the relational database into a low latency data store.</p><h3>Storing Materialised Views</h3><p>Every service will be interested in a subset of entities that exists in our database. Each of these entities could be dependent on multiple other entities. So, we need to make sure that when we cache the data, we cache a de-normalised view of the entity. This will enable us to reduce the number of calls made from the service to our low latency data store. This de-normalised view is also called a <strong><em>materialised view</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/541/0*rkfEUgX5Sg7uO9bD" /></figure><h3>Change Data Capture (CDC)</h3><p>Relational databases like MySQL, PostgresDB, etc has <strong><em>binary logging</em></strong>. Every row changes are logged in a file, commonly known as <strong><em>binlog</em></strong>. To materialise views, we would need to listen to these log events and process it in real time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/731/0*idl9-DcYFObPbZ-N" /></figure><p>In the above design, we have a simple <em>Bin Log Processor</em>, which is responsible for doing two things</p><ul><li>One thread, say the <strong><em>I/O thread</em></strong>, which continuously polls for new events in the <em>binlog</em>. Every new event is handed over to the<strong><em> processing thread</em></strong>.</li><li>Processing thread, materialises views and writes them to the sink. Every view in the sink corresponds to a row in the sink. Writes to sink are always atomic for a single row.</li></ul><p>Please note that our <em>Bin Log Processor</em> is stateless.</p><h3>Computing Materialised View</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*nK2AIKlRJGkPfqK2" /></figure><p>In the above example, the materialised view <strong><em>View</em></strong> is dependent only on one entity <strong><em>Entity_1</em></strong>. One entity object of View depends on one row of Entity_1 table. To compute View using our CDC design, we would need the <em>I/O thread </em>to hand over every row read/modify/update event to the <em>processing thread</em>. The processing thread then created the View in-memory and persist it in the sink. It can be reasoned that system will remain in consistent state in any kind of failure scenarios. Let’s look at some of the failure scenarios in detail to understand this better.</p><ul><li><em>I/O thread receives event but hand-over to processing thread failed</em>. The sink will have a stale version (version 0) of our <strong><em>View</em></strong> entity. The view of the entity is delayed with respect to the DB but not wrong.</li><li><em>Processing thread fails processing mid way</em>. Since write to sink are always atomic for a single row, this failure can never leave the view entity in a wrong state. View version will be either 0 or 1.</li></ul><p>Let’s complicate things a bit now !</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*3BjG4AgPY26p3U6X" /></figure><p>In the above example, <strong><em>View</em></strong> update is complete only when both <strong><em>Entity_1</em></strong> and <strong><em>Entity_2</em></strong> are updated. A single transaction updates both the entities together.</p><p>Since our <em>Bin Log Processor</em> is stateless, single row event processing wouldn’t work in this case. We have to make <em>Bin Log Processor</em> transaction aware. We can do this by listening to two more events apart from the row events — START_TRANSACTION (TX_ID) event and COMMIT_TRANSACTION (TX_ID) event. When we encounter the former, we create a <strong><em>transaction</em></strong> <strong><em>event buffer</em></strong> for the TX_ID and start buffering all the events until we see a COMMIT_TRANSACTION (TX_ID) event. Once the processor sees this event, it can now start materialising the <strong><em>View</em></strong> entity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/801/0*Vpl59cN8Kxa8v0Qy" /></figure><p>The <strong><em>transaction event buffer</em></strong> is external to <em>Bin Log Processor</em> to keep the processing component stateless which helps in fault tolerance scenarios.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bbf2aba4fa8d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[SSTables and LSM Trees]]></title>
            <link>https://rahulpradeep.medium.com/sstables-and-lsm-trees-5ba6c5529325?source=rss-bab508154895------2</link>
            <guid isPermaLink="false">https://medium.com/p/5ba6c5529325</guid>
            <category><![CDATA[storage]]></category>
            <category><![CDATA[indexing]]></category>
            <category><![CDATA[distributed-database]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[hbase]]></category>
            <dc:creator><![CDATA[Rahul Pradeep]]></dc:creator>
            <pubDate>Mon, 21 Jun 2021 12:39:23 GMT</pubDate>
            <atom:updated>2021-06-21T12:39:23.119Z</atom:updated>
            <content:encoded><![CDATA[<p>SSTables and LSM-Trees are techniques which are used to efficiently store and retrieve data. In this post, we will limit our discussion to data retrieval based on a primary key. Before diving deeper into these techniques, let us understand a simplified storage engine, where the keys are stored in memory and values are stored in disk. We will understand the pros and cons of this engine and gradually work towards solving the cons of this approach by introducing SSTables and LSM-Trees.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*e6P4tkcyqktqI00a" /></figure><p>There are two primary components to this storage engine — <strong><em>hashTable</em></strong> and a <strong><em>log</em></strong> (append-only file). Let’s see how various operations work in this database</p><ul><li><strong><em>write</em></strong><em>(key, data)</em> : The data will be appended in the <strong>log</strong> at the latest offset, say, <em>offset1</em>. The first four bytes of the data will indicate the size of the data to be read. The key will be updated in the hashTable with the value in the <strong>hashTable</strong> being the offset to the data in the log.</li><li><strong><em>read</em></strong><em>(key) </em>: Offset to the data in <strong>log</strong> is found by doing a lookup in the <strong>hashTable</strong>. Once the offset is found, we seek to that offset in the file and start reading the data. Since the first four bytes indicate the size of the data, we would know when to stop reading.</li><li><strong><em>update</em></strong><em>(key, data)</em> : Since we are using <strong>log</strong>, we will never go and update the data for an already existing key. If we were to do that, we will have to possibly re-write all data from the offset. So, we will just append this to the log just like the write operation. And update the offset in our in-memory <strong>hashTable</strong>. There would be old data lying around in the old offset, but let’s worry about that later.</li><li><strong><em>delete</em></strong><em>(key)</em> : Delete is trickier. We will append a special record in the <strong>log</strong>, also called a <strong><em>tombstone</em></strong> in the log indicating that we need to delete data belonging to the specified offset. We will also remove the entry for the key from the <strong>hashTable</strong>.</li></ul><p>So far, so good. All the operations run in constant time complexity. What about the data growth in our log ?</p><h3>Log-structured Storage Segments</h3><p>Data in our log is ever growing, since we are never really deleting anything. We will soon run into disk issues. One way to keep this data growth in check would be to have a background thread do the compaction of the log file. This will work but we cannot serve any requests while this is happening. This will compromise the availability of our system.</p><p>To make our system available for serving online requests, we can cut a snapshot of our current log file and create a new one instead of that by ignoring old and deleted data. These snapshots are also called <strong><em>segments</em></strong> While this is happening, another log file and hashTable can accept online requests. How would our write and read requests change in this approach ?</p><ul><li><strong><em>write</em></strong><em>(key, data) </em>: Same as before except that we will append the data to the latest log file. The in-memory hashTable will have to store log file path along with the offset for a key as there can be multiple log files at a time in our system.</li><li><strong><em>read</em></strong><em>(key)</em> : Determine the log file path and the offset for the given key and read the data in the same way we did in our previous approach.</li></ul><p>To make sure this background cleanup operation happens more frequently we would need to limit our segment size. We can create these segments after a threshold size and do the <strong>compaction and merging</strong> in a background thread periodically.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*kC324v5QrRz8FRHc" /></figure><p>This approach seems to have kept our data size on disk in check. The Achilles heal in our design is really the hashTable now.</p><ul><li><em>Fault-tolerance</em> : In case of node failures, we will lose our hashTable. To fix this, we can persist our hashTable every time we cut a log segment. To recover from this fault, we can simply read the latest persisted hashTable and re-build our in-memory hashTable.</li><li><em>Large number of keys </em>: After a point our keys wouldn’t fit in memory. To maintain a hashTable on disk is possible but complicated and not very performant.</li><li><em>Range queries</em> : Scanning all keys between a given range will require us to look at all keys.</li></ul><h3>Sorted String Tables (SSTables)</h3><p>Sorting is a powerful technique. Sorting all the keys allows us to reduce the size of our <strong>hashTable</strong>. Extending our previous idea of diving our file into multiple segments, we do the same here, only difference being that each of the file contains keys in a sorted manner.</p><pre><strong>Segment-0</strong>: [&quot;aaabc&quot;:0, &quot;aabc&quot;:980, &quot;bbcd&quot;:1500]<br><strong>Segment-1</strong>: [&quot;bcd&quot;:2000, &quot;ccc&quot;;2200, &quot;ccd&quot;:2500]<br><strong>Segment-2</strong>: [&quot;cde&quot;:3000]</pre><p>In this approach , we can limit the the in-memory hashTable to have only some of the keys. This is called a <strong><em>sparse-index</em></strong>. For example, sparse index will contains the following keys. <strong>“aaabc”:0, “bcd”:2000, “cde”:3000</strong>. Each of the keys in this index will be start of a<strong> segment file.</strong> This segment file is called <strong>SSTable</strong>. Any read operation for a key will require us to first determine the segment where the key would lie. This can be done by a binary search on the sparse-index. Once we know the segment, we simply read the segment sequentially from disk and return the data once we find the matching key.</p><p>We still need to scan through all the keys in a segment, which could make reads slow if segments are big enough. One possibility is to make the segments smaller. The con of this is that there would be far too many small segment files, which could be detrimental in our <strong>compaction and merging</strong> phase. If we make our segments larger, our sparse index becomes way smaller. In practise, we should be able to use more memory, if we remove the coupling of keys in the sparse-index to our segments. We can have our sparse-index have one key for every <em>X</em> KB of data. Scanning through few KBs of data is fast enough.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Sh01G47cxQPOBAWx" /></figure><h3>Keeping it Sorted !</h3><p>The million dollar question is how do we keep the keys sorted on disk efficiently. To maintain keys sorted in-memory can be done using any of the balanced binary search tree implementations (AVL trees, RB trees, etc). All writes can be done in memory until a certain threshold of size is reached. After which, we can flush it onto disk. This in-memory data structure is called a <strong><em>memTable</em></strong>.</p><p>Keeping it sorted in memory is easy and flushing it periodically onto disk seems efficient. But how do we handle fault tolerance here. Any node failure can cause all un-flushed data to be lost forever. To prevent this, we can use a <strong><em>write-ahead-log (WAL)</em></strong>. Any write operation, first appends the operation into the log and then written into memTable. The WAL writes are very fast as they are sequential writes. We can recover from any fault by building our memTable by scanning this WAL. We can limit the size of WALs by periodically rolling it since already flushed data needn’t be maintained in the WAL.</p><p>Every time a memTable is flushed onto disk, it creates a new segment file. Over time this can create many segment files. Again, borrowing ideas from our simplified storage engine, we can have a background thread to periodically do <strong><em>compaction and merging</em></strong>.</p><h3>Log Structured Merge Trees (LSM Trees)</h3><p>SSTables are periodically compacted and merged into larger SSTables. The idea is to keep a small number SSTable. We will see how small number of SSTables are key to having a good read performance. This cascading list if SSTables is the key idea of LSMTrees.</p><p>For each of the SSTable file, we have a sparse in-memory index. And each of these SSTable file can be ordered from oldest to latest. With this in mind, let us see how read and write operations work.</p><ul><li><strong><em>write(key, data)</em></strong> : Writes the key:data into WAL and then writes it into the memTable.</li><li><strong><em>read(key) </em></strong><em>:</em> First look at the sparse-index for the memTable. If the key doesn’t exist, it could mean two things</li><li>The key was updated/written long time back and could be present in an older SSTable file. In this case, we will have to go through all SSTables from latest to oldest. We return the data as soon as we find the key.</li><li>The key is deleted. We can only say that a key is deleted after going through all the SSTables.</li></ul><h3>Performance of LSMTrees</h3><p>As the writes involve one sequential write to <strong>WAL</strong> and an in-memory update to <strong>memTable</strong>, LSMTrees can give a very high write throughput.</p><p>For reads, we have to go through all the SSTables in the worst case. To get a high read throughput, it is important to keep a low number of SSTables. We can do this by doing a size based compaction. In this, newer SSTables are merged into older and larger SSTables.</p><p>For deleted keys, it still takes scanning all of SSTables to even determine if that key is deleted. One optimisation we can do is using a <a href="https://en.wikipedia.org/wiki/Bloom_filter">BloomFilter</a>. BloomFilter is an in-memory data structure which approximates the contents of a set. It can tell you with 100% certainty if a key isn’t present in the set.</p><h3>Range Queries</h3><p>One advantage of storing keys in a sorted fashion is that it enables us to do range queries efficiently. For any range of keys <strong><em>[key_x, key_y]</em></strong>, we can determine the exact SSTables to look for and hence limiting the key space to scan for.</p><h3>Conclusions</h3><p>This approach of storage and retrieval is used in several database systems like Google BigTable, Apache HBase, Apache Cassandra, etc.</p><h3>References</h3><ul><li><a href="https://dataintensive.net/">https://dataintensive.net/</a></li><li><a href="https://hbase.apache.org/book.html#arch.overview">https://hbase.apache.org/book.html#arch.overview</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5ba6c5529325" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>