<?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 Junaid NZ on Medium]]></title>
        <description><![CDATA[Stories by Junaid NZ on Medium]]></description>
        <link>https://medium.com/@junaidnz?source=rss-c9f9b307a64a------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*vzr9hik6MQKnwoREr4hZmA.jpeg</url>
            <title>Stories by Junaid NZ on Medium</title>
            <link>https://medium.com/@junaidnz?source=rss-c9f9b307a64a------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 14:37:00 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@junaidnz/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[Design a collaborative editing tool (Google Docs)]]></title>
            <link>https://medium.com/@junaidnz/design-a-collaborative-editing-tool-google-docs-3dcb1bcacf0b?source=rss-c9f9b307a64a------2</link>
            <guid isPermaLink="false">https://medium.com/p/3dcb1bcacf0b</guid>
            <category><![CDATA[google-docs]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[grpc]]></category>
            <dc:creator><![CDATA[Junaid NZ]]></dc:creator>
            <pubDate>Sun, 09 Apr 2023 12:16:39 GMT</pubDate>
            <atom:updated>2023-04-12T00:10:16.886Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>Requirements:</blockquote><ul><li>Multiple users should be able to edit the document simultaneously.</li><li>Latency for saving edits should be as low as possible</li><li>Active users should receive concurrent updates from other users as soon as possible.</li></ul><blockquote>High level service abstraction</blockquote><p>2 basic requirements we have are the following,</p><ol><li>Once a user opens a document and starts editing the content, we have to sent the edits he/she has done to the backend servers.</li><li>When a user edits anything in the document, this edit information has to be propagated to other active users.</li></ol><p>For 1, we could always make a new api call whenever a user makes an update in the document and for 2, client can poll every few seconds to check it there are any updates done on the same document. But making tcp connections are expensive (which can result in an increased latency). Client polling every few seconds means there will be a delay in the time between the actual concurrent updates happening and a user receiving them. We would ideally want these updates to reach as soon as possible with minimum delay.</p><p>Using a persistent tcp connection is a better solution here. <a href="https://grpc.io/docs/languages/go/basics/#bidirectional-streaming-rpc">GRPC streaming</a> can be used to achieve this(Web sockets is another option). Using a GRPC bi-directional streaming connection, we can use the same tcp connection to send updates from client and publish any concurrent updates from other clients back to the user.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/562/1*tiqX0GnD0L5ycazy50lyYw.jpeg" /></figure><p><strong>Gateway Service</strong>: Gateway service sits behind a load balancer and is the direct point of contact with the client. The persistent tcp connection is made between the client and the gateway. We will use GRPC for Gateway Server as it supports streaming RPCs.</p><p><strong>Docs Service:</strong> This service deals with apis needed and related to documents. We will use GRPC for Docs Server as it supports streaming RPCs.</p><p><strong>Zookeeper/Consul</strong>: <br>We are using Zookeeper/Consul for <a href="https://developer.hashicorp.com/consul/docs/concepts/service-discovery">service discovery</a>. Whenever each instance of a Docs Service Server spins up, it sends its private ip address to registers itself with Zookeeper/Consul. Each Gateway Service Server instance will have a <a href="https://developer.hashicorp.com/consul/docs/dynamic-app-config/watches">watcher</a> that listens to Zookeeper/Consul to get any updates when a new Docs Service Server spins up and fetches the private ip address’ of all healthy Docs Service Server instances to initiate a GRPC connection with each of them. At a time there will just be a single tcp connection between a Gateway Service Server and a Docs Service Server . This single TCP connection will be re-used by multiple requests. This is possible as GRPC makes use of HTTP2 which supports multiplexing.</p><p>Now the question that arises is <strong>W<em>hy is service discovery need?</em></strong> There are majorly 2 reasons. The first one is that it is needed for publishing edits in the document to all active users (We will discuss this in the coming sections). The second reason is that we use it for client side load balancing.</p><p>Now the next question is <strong><em>Why is client side load balancing needed?</em></strong> We could have just used another load balancer and let Docs Service sit behind that. Then Gateway service could just invoke the url of load balancer to invoke docs service. This will work of-course, but is not recommended when we use GRPC as it uses a persistent tcp connection. This <a href="https://majidfn.com/blog/grpc-load-balancing/">blog</a> explains why client side load balancing is needed.</p><p><strong>Redis:</strong> Redis is used to cache data that needs fast reads. Will discuss its use in upcoming sections.</p><p><strong>S3:</strong> S3 buckets will be used to store raw documents</p><blockquote>How to handle conflicts during concurrent edits?</blockquote><p>When multiple users edit the same document concurrently, conflicts can happen. Operational Transformation is a method used for this. <a href="https://medium.com/coinmonks/operational-transformations-as-an-algorithm-for-automatic-conflict-resolution-3bf8920ea447">This</a> blog explains it in detail.</p><p>To achieve Operational Transformation, we need to store the history of edits that gets done. These edits needs a consistent ordering (<a href="https://stackoverflow.com/questions/46568765/can-someone-please-explain-the-concept-of-causality-in-distributed-computing">causality</a>) which as explained by the blog can be solved using <a href="https://en.wikipedia.org/wiki/Vector_clock">vector clocks</a>. Practically, causality can be easily achieved by using <a href="https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/DynamoDBMapper.OptimisticLocking.html">optimistic locking</a>.</p><blockquote>Edit Document flow</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/472/1*4Efd0tEySS6CT4le0B_kdg.jpeg" /></figure><p>1) User sends the edit document request via an already created GRPC bi-directional streaming connection. The request is basically an array of insert/delete operation and the current revision number of the document. For eg: a sample request will look like <br><strong>{[[“insert”, “hello”, 0], [“delete”, 1], [“insert”, “!”, 3]], “revisionNumber”: 0}<br></strong>This translates to insert “hello” at index 0, delete character at index 1 and insert “!” at index 3 , which together results in adding “hllo!” at index 0 to the raw document . RevisionNumber is used for optimistic locking. For a document that is just created and newly and edits are yet to be done, revison number will be 0.</p><p>2) Load balancer would redirect the request to the instance of the gateway to which tcp connection was initiated.</p><p>3) Gateway instance does a client side round-robin load balancing and passes the request to any random instance of Docs Service.</p><p>4) Gateway instance need to write the edit information into the database now. We will use 2 tables here, one to store the revision number of the document called <strong>document_revision</strong> and another to store the edit operations called <strong>document_edit_history</strong>.</p><pre>document_revision:<br><br>+-------------+-----------------+<br>| document_id | revision_number |<br>+-------------+-----------------+<br>|         123 |               1 |<br>|         785 |               6 |<br>+-------------+-----------------+</pre><p>Now a query like <strong>update document_revision where document_id = request.documentID and revision_number &lt; request.revisionNumber</strong> <br>will be performed. Only if this query is successful, we will allow updates in <strong>document_edit_history</strong> table. document_revision table here acts as a lock to access <strong>document_edit_history</strong> table.</p><p>If this query is not successful, then it means that client doesn’t have latest copy of updates done concurrently by other clients as revision_number gets updated sequentially with every edit. If this query is not successful, then we can read all the edits that has happened between the current version in the <strong>document_revision</strong> table and the version that client has and sent these edit operations back to the client. Client can then use Operational Transformation to merge these and sent back a new edit request again after incrementing the revision_number.</p><p>If this query is successful, then it can directly go ahead and write in <strong>document_edit_history </strong>table.</p><pre>document_edit_history:<br>+-------------+-----------------+---------------------------------------------------------------+<br>| document_id | revision_number |                        edit_operations                        |<br>+-------------+-----------------+---------------------------------------------------------------+<br>|         123 |               5 | {[[&quot;insert&quot;, &quot;hello&quot;, 0], [&quot;delete&quot;, 1], [&quot;insert&quot;, &quot;!&quot;, 3]]} |<br>|         123 |               6 | {[[&quot;insert&quot;, &quot;hi&quot;, 3]]}                                       |<br>+-------------+-----------------+---------------------------------------------------------------+</pre><p>Now, which databases can we use for these tables? <strong>document_revision</strong> is a key value store that gets updated frequently. DynamoDB is a good option for this. <strong>document_edit_history </strong>is a table that generally deals with many new writes and no updates. Reads are needed rarely during conflicts. So, Cassandra which is built for fast writes is a good option for this.</p><p>6) Once the DB writes are done, we push a packet to an SQS queue</p><p>7) A lambda function will read this message from the SQS. It builds the new updated raw document from the edit operations and existing raw file in S3 using Operational Transformation.</p><p>8) This newly built file is written back to s3. Any new client starting a new session can directly read this file instead of fetching multiple entries from DB and constructing it at run-time to improve latency.</p><blockquote>Publish Updates Flow</blockquote><p>The requirement here is that when ever a document gets edited, this edit information has to be passed out to all the active clients.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*P19ZuXSh6jAckHh3xwXF9w.jpeg" /></figure><p>One option is that Docs Service can blindly send updates for a document to all Gateway Service nodes and give the responsibility to Gateway Service nodes to stream it to clients. But this can be optimised if Docs service has visibility on which all Gateway Service nodes have connections with client that is meant for the given document.</p><p>A solve for this is that, we can store a map in Redis, where the key is the documentID and value is a list of private ip address’ of the Gateway Server nodes that has connections with the client that is meant for the given document. When ever a client opens a connection with a Gateway Server instance to view/edit a document, we can update this map in the Redis. The already established bi-directional streaming connection from each Gateway Server to each Docs Server will be reused to send this information.</p><pre>{<br>  &quot;123&quot;: [192.168.1.4, 192.178.1.4] <br>  &quot;456&quot;: [192.188.1.4, 192.178.1.4]<br>}<br><br>This is a sample structure of the redis map. This means that <br>there are users viewing document with id &quot;123&quot; using connections with<br>gateway servers with private ip address&#39; 192.168.1.4 and 192.178.1.4 and<br>that there are users viewing document with id &quot;456&quot; with private ip address&#39; <br>192.188.1.4, 192.178.1.4.</pre><p>Once an instance of gateway server receives update documents information, it has to sent this back to all clients with an active connection for viewing/editing the same document. This is simple. Each instance of the gateway server will have a global static map of the form map&lt;documentID, list&lt;*connectionObject&gt;&gt; where key is the documentID and value is a list where each element of the list is a connection object with a client. The connection object will have a “<strong>send</strong>” function using which data can be send to the respective client(<a href="http://pb.routeguide_routechatserver/">Refer</a>). When ever a new connection happens or an existing connection is disconnected, the list for a document is updated.</p><p>Now, coming back to the question on <strong>W<em>hy is service discovery need?.</em></strong> To publish updates from docs server to gateway server, a docs server needs to have connections with all gateway servers. These connections are initiated by Gateway servers. For this, gateway servers needs to know about all active servers of Docs Service. To solve this, service discovery is needed.</p><p>This is inspired from how Linkedin streams real-time likes to clients (<a href="https://www.youtube.com/watch?v=yqc3PPmHvrA">Talk link</a>).</p><p>With this, once a client/user makes an update, other concurrent clients will get this instantly with very less delay. Delay will be majorly because of the <strong>latency to write to DynamoDB + latency to write to Cassandra + latency to publish</strong>. This total should generally be less than 200 ms.</p><blockquote>References:</blockquote><ol><li><a href="https://serverfault.com/questions/418393/why-is-creating-a-new-tcp-connection-regarded-as-expensive">https://serverfault.com/questions/418393/why-is-creating-a-new-tcp-connection-regarded-as-expensive</a></li><li><a href="https://grpc.io/docs/languages/go/basics/#bidirectional-streaming-rpc">https://grpc.io/docs/languages/go/basics/#bidirectional-streaming-rpc</a></li><li><a href="https://developer.hashicorp.com/consul/docs/concepts/service-discovery">https://developer.hashicorp.com/consul/docs/concepts/service-discovery</a></li><li><a href="https://developer.hashicorp.com/consul/docs/dynamic-app-config/watches">https://developer.hashicorp.com/consul/docs/dynamic-app-config/watches</a></li><li><a href="https://majidfn.com/blog/grpc-load-balancing/">https://majidfn.com/blog/grpc-load-balancing/</a></li><li><a href="https://medium.com/coinmonks/operational-transformations-as-an-algorithm-for-automatic-conflict-resolution-3bf8920ea447">https://medium.com/coinmonks/operational-transformations-as-an-algorithm-for-automatic-conflict-resolution-3bf8920ea447</a></li><li><a href="https://stackoverflow.com/questions/46568765/can-someone-please-explain-the-concept-of-causality-in-distributed-computing">https://stackoverflow.com/questions/46568765/can-someone-please-explain-the-concept-of-causality-in-distributed-computing</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://docs.aws.amazon.com/amazondynamodb/latest/developerguide/DynamoDBMapper.OptimisticLocking.html">https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/DynamoDBMapper.OptimisticLocking.html</a></li><li>Streaming Real-Time likes: <a href="https://www.youtube.com/watch?v=yqc3PPmHvrA">https://www.youtube.com/watch?v=yqc3PPmHvrA</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3dcb1bcacf0b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design A Proximity Search Service (Yelp)]]></title>
            <link>https://medium.com/@junaidnz/design-a-proximity-search-service-yelp-ea5c8923202f?source=rss-c9f9b307a64a------2</link>
            <guid isPermaLink="false">https://medium.com/p/ea5c8923202f</guid>
            <dc:creator><![CDATA[Junaid NZ]]></dc:creator>
            <pubDate>Sat, 01 Apr 2023 16:29:05 GMT</pubDate>
            <atom:updated>2023-04-01T16:29:05.818Z</atom:updated>
            <content:encoded><![CDATA[<p>A proximity service is used to search for nearby business’ like restaurants, theatres etc..</p><blockquote>Requirements</blockquote><ol><li>Return all businesses taking user’s latitude, longitude and search radius as input.</li><li>Business’ data can be added, deleted and updated.</li></ol><blockquote><em>High level system abstractions</em></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/651/1*vMOGrh2g3TWHRM0Ay2qfnQ.png" /></figure><ul><li>Gateway: All tcp connections by a user/browser/mobile-device is made to the gateway. This helps as a single point for authenticating the session information of the user.</li><li>Load balancer: This is internet facing and helps in load balancing requests to the gateway server instances.</li><li>Location Search Service and Business Service are the micro-services that logically separate out informations related to each domain.</li></ul><blockquote>Business Service</blockquote><p>The requirement of business service is simple. Admin/Business owners should be able to add, delete, update details of a business. If any meta data of the business gets updated, then we need to send a notification to location service for it to take action on the same.</p><p><strong>Data Storage Requirements: </strong>Given a business id, we should be able to get all the meta-data related to that business. So, this is a use case for a key-value storage. We can use any no-sql distributed db like dynamoDB for scalability easily here.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/331/1*W3Cdv6jZE3GY409SmKrO5w.png" /></figure><blockquote>Location Search Service</blockquote><p><strong>Requirements:</strong></p><ol><li>Store location data of businesses</li><li>Query near by businesses’ for a given (latitude, longitude) with very small latency.</li></ol><p>The main problem here is that we have to search in a 2 dimensional space which is hard. One option is to build an index on latitude and use that to search. This will be very in-efficient as when we search with a given latitude, DB will have to load all the business’ for all possible longitudes which has the given input latitude which will be spread across continents.(Vice-Versa if we built an index on longitude).</p><p>We will discuss a couple of ways to solve this,</p><blockquote><strong>Geo Hash:</strong></blockquote><p>We can divide our 2 dimensional space into 4 quadrants. Each quadrant is represented by a 2 digit binary number. This is a level-1 division.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/431/1*vU21PB_AFhpNZmHYOrwQzA.png" /></figure><p>Each quadrant can again be divided into 4 sub-quadrants. The first 2 digit of the sub-quadrant(prefix) would be same as that of the level 1 quadrant from which this was divided.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/431/1*FW00Qox7wiznrGt79aBMKQ.png" /></figure><p>We can recursively do this till the quadrant size represents a precision that we need.</p><p>Now, geo-hash generally uses base 32 representation. Instead of dividing to 4 quadrants, it divides the 2 dimensional space into 32 grids. Each grid can recursively be divided into 32 grids again (<a href="https://www.youtube.com/watch?v=UaMzra18TD8">Geo Hash</a>). Now, based on the geo-hash length, we can approximate the area that the grid represents(<a href="https://www.elastic.co/guide/en/elasticsearch/reference/6.8/search-aggregations-bucket-geohashgrid-aggregation.html#_cell_dimensions_at_the_equator">link</a>).</p><p>Now, how do we use this for searching? We can build a table with the following structure (let’s name this table as business_locations),</p><pre>+------------+------------+---------+-------------------------------------------+<br>| LocationID | BusinessID | GeoHash |             MetaData                      |<br>+------------+------------+---------+-------------------------------------------+<br>| L1         | B1         | 9vg5    | {Name:&quot;B1&quot;, Category: &quot;C1&quot;, Rating: &quot;R1&quot;} |<br>| L2         | B2         | 9vg5    | {Name:&quot;B2&quot;, Category: &quot;C1&quot;, Rating: &quot;R2&quot;} |<br>+------------+------------+---------+-------------------------------------------+</pre><p>Now, if we have an index on GeoHash column, then it is easy to do a prefix search on the geoHash column. For eg: if a user gives a pair of (latitude, longitude) as input, we will first figure out the geoHash to which it belongs to, then we will just run a query like</p><pre>select * from business_locations where GeoHash like ‘9vg5%’. </pre><p>We can build a paginated api around this to serve search. We are using like query here because we could store the geoHash at a deeper level and search for any parent level as well. Say we store locations for a GeoHash level 6 then using prefix search, we can search at GeoHash levels 1, 2 ,3, 4, 5 and 6.</p><p><strong>Boundary issues with GeoHash: </strong>It can happen that 2 locations are very close, but have different GeoHash values. This can be solved by querying not just one grid, but neighbouring grids as well and merging the data.</p><p>This is a good talk on GeoHash -&gt; <a href="https://www.youtube.com/watch?v=sYnRUDGXwNM">Link</a></p><p><strong>How Do we Scale Data Base here</strong>: If we do a calculation of one row in table business_location, then we could easily say that one row will take less than 500 Bytes in the worst case. Now, if we need to support 50 million business’ in total then it will take 50 * 10 ^6 * 500 = 2,50,00,00,000 Bytes ~= 25GB. This can be easily supported by a single database server. So, theoretically, there might not be a use case to shard the data base for this particular use case. We can have multiple read replicas to scale the reads though. But if we still want to shard it, then a simple solution is to use something like dynamoDB with the partition key as the GeoHashValue. But then, when we make queries in nearby grids to solve the boundary problem, then it is likely that the query goes to multiple servers to fetch the data as we have hash-partitioning in dynamoDB.</p><p>If we were building this for a different use-case like Uber or Swiggy, then we might need to design this differently as driver locations can keep constantly changing every few seconds or minutes. We will explore that in a separate blog.</p><p>We can improve the latency further by caching the geo-hash id to list of business ids using redis.</p><p><strong>Google S2</strong></p><p>S2 is a framework created by google for spatial data. This <a href="https://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/">blog</a> explains well on how it works.</p><p>I will quickly summarise. Just like how GeoHash tries to divide the spatial data into grids, s2 divides also divides spatial data into grids. But the difference is that the grids are numbered incrementally with the help of <a href="https://www.youtube.com/watch?v=nXvSyKcnJy0">Hilbert Curve</a>. If 2 cells are nearby on the hilbert curve path, then they will have nearby cell ids. S2 provides a function to convert a given latitude and longitude to a cell id. Since nearby cell-ids are incremental, it is easy to index it for range queries.</p><p>Similar to how boundary issues are there in GeoHash, in s2 also, even if 2 locations are very close, they might not have very close cell ids. But this can easily be solved by increasing your search space.</p><p><strong>How Do we Scale Data Base here</strong>: Similar to the GeoHash approach, we don’t really need to shard the database for this particular use case. But again, in the worst case even if we need to do it, we can shard by the cell id. But instead of hash sharding, we will need to do range sharding here since the requirement is to search for similar ranges. Cockroach DB or Vitess can be used for this.</p><p>We can improve the latency further by caching the cell-id to list of business ids using redis.</p><blockquote>References:</blockquote><ol><li>GeoHash: <a href="https://www.youtube.com/watch?v=UaMzra18TD8">https://www.youtube.com/watch?v=UaMzra18TD8</a></li><li>GeoHash:<a href="https://www.elastic.co/guide/en/elasticsearch/reference/6.8/search-aggregations-bucket-geohashgrid-aggregation.html#_cell_dimensions_at_the_equator">https://www.elastic.co/guide/en/elasticsearch/reference/6.8/search-aggregations-bucket-geohashgrid-aggregation.html#_cell_dimensions_at_the_equator</a></li><li>GeoHash: <a href="https://www.youtube.com/watch?v=sYnRUDGXwNM">https://www.youtube.com/watch?v=sYnRUDGXwNM</a></li><li>GeoHash: <a href="https://aws.amazon.com/blogs/compute/implementing-geohashing-at-scale-in-serverless-web-applications/">https://aws.amazon.com/blogs/compute/implementing-geohashing-at-scale-in-serverless-web-applications/</a></li><li>S2: <a href="https://s2geometry.io/devguide/s2cell_hierarchy.html">https://s2geometry.io/devguide/s2cell_hierarchy.html</a></li><li>S2: <a href="https://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/">https://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/</a></li><li>Hilbert Curve: <a href="https://www.youtube.com/watch?v=nXvSyKcnJy0">https://www.youtube.com/watch?v=nXvSyKcnJy0</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ea5c8923202f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design of an E-Commerce Platform (Amazon/Flipkart)]]></title>
            <link>https://medium.com/@junaidnz/design-of-an-e-commerce-platform-77d3ec1641f9?source=rss-c9f9b307a64a------2</link>
            <guid isPermaLink="false">https://medium.com/p/77d3ec1641f9</guid>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[ecommerce]]></category>
            <category><![CDATA[online-shopping]]></category>
            <category><![CDATA[microservices]]></category>
            <dc:creator><![CDATA[Junaid NZ]]></dc:creator>
            <pubDate>Sun, 26 Mar 2023 14:21:08 GMT</pubDate>
            <atom:updated>2024-01-09T20:36:23.699Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>Requirements / Assumptions</blockquote><ul><li>System should be horizontally scalable</li><li>Sellers should be able to add items and update quantities</li><li>Concurrency: If 2 users tries to purchase a product for which only a single quantity of item is left concurrently, then payment should get debited and order should get placed for only for one of the users. Basically, we don’t want to place more orders than the quantity of a product.</li></ul><blockquote>High level system abstractions</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/671/1*CxHm1ITIG4XTtSxkDU8z2w.png" /></figure><ul><li>Gateway: All tcp connections by a user/browser/mobile-device is made to the gateway. This helps as a single point for authenticating the session information of the user.</li><li>Load balancer: This is internet facing and helps in load balancing requests to the gateway server instances.</li><li>Catalogue Service, Shopping Cart, OrderManager, Payment <br>micro-services logically separate out informations related to each domain.</li><li>We will not go in-depth to payment service in this blog.</li></ul><blockquote><strong>Catalogue Service</strong></blockquote><p>Catalogue service deals with all the APIs related to catalogue/product of our shopping portal. It is a stateless horizontally scalable service behind a load balancer.</p><p>Basic Requirements:</p><ol><li>Create a product: This will be done by the seller.</li><li>Update ProductInfo and Status of a given product. This will be done by the seller</li><li>Decrement/Increment a quantity of a product. This can either be done by the seller, or the system needs to do this when users places an order or cancels an already placed order.</li></ol><p>Let’s take a structure with bare minimum information needed to represent a product in the catalogue for simplicity and come up with the requirements to zero in on a database choice needed for catalogue service.</p><pre>+-----+--------------------------------+----------+-----------+<br>| ID  |          ProductInfo           | Quantity |  Status   |<br>+-----+--------------------------------+----------+-----------+<br>| 123 | {&quot;Name&quot;: &quot;MacBook Pro Laptop&quot;} |      100 | Available |<br>+-----+--------------------------------+----------+-----------+</pre><h4>SQL vs NOSQL</h4><p>Point 1 and 2 can be supported by most of the traditional SQL and noSQL databases. Duplicate entry creations can be prevented by unique indexes and concurrent updates to prevent dirty writes can be handled either by using database transactions(in sql) or using an optimistic concurrency control mechanism (<a href="https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/DynamoDBMapper.OptimisticLocking.html">Good reference</a> for optimistic concurrency control)</p><p>For point 3, the query we need to support is something like this</p><p>update quantity=quantity-10 where id = &#39;123&#39;;</p><p>Now, consider this case where the database committed the change and reduce the quantity by 10, but the client didn’t get the successful response because of a temporary network issue. Now, the client doesn’t know if the quantity was updated or not, if it does a retry, it would reduce the quantity by 10 again, which results in reducing the quantity by 20 in total which is not expected. The problem here is that the update operation is not idempotent.</p><p><strong>How can we make this update idempotent?:</strong> A simple way to do this is to create a new tabled named catalogue_updates and every-time the quantity of catalogue table is updated we need to add a corresponding entry in catalogue_updates in a single atomic transaction. A composite unique index on (client, client_request_id) can be used where (client, client_request_id) is the Idempotence key for updates here. So, now if there is a network failure after transaction commit and client application performs a retry, we can first check in catalogue_updates table if an entry is present and if it is already there, then we don’t need to update the entry in catalogue table.</p><pre><br>+------+------------------------+-------------+---------------+---------------+<br>|  ID  |     Client Client      |  RequestID  |  CatalogueId  |  UpdatedValue |<br>+------+------------------------+-------------+---------------+---------------+<br>| 456  |  OrderManagerService   |        789  |          123  |            -5 |<br>| 467  |  Seller                |        754  |          123  |            10 |<br>+------+------------------------+-------------+---------------+---------------+</pre><p>Since we need the support of database transactions here to support our requirements, a traditional relational database like Mysql or Postgres best suits our use-case.</p><p><strong>How do we scale here?:</strong> If we are using a traditional relational database like Mysql or Postgres, our database will become the bottle-neck for writes as there is a single master. Reads can still be scaled to an extend by increasing the number of read-replicas. There are a couple of options to scale writes,</p><ol><li>Use a distributes sql database like <a href="https://www.cockroachlabs.com/">CockroachDB</a> or <a href="https://www.yugabyte.com/">Yugabyte</a> which gives us distributed transactions support.</li><li>Use a sharded relational database system like <a href="https://vitess.io/">Vitess</a> to help you shard your mysql database that gives you support for atomic transactions for a given shard key. Primary key identifier `ID` can be used as the shard key. <a href="https://www.flipkart.com/">Flipkart</a> seems to be using Vitess from their website though I am not sure if they use it for this use-case.</li></ol><p>We have designed a horizontally scalable catalogue system now.</p><blockquote>Shopping-Cart Service</blockquote><p>Shopping Cart Service helps in all apis related to shopping cart. To keep things simple, we only need to store the active cart details.</p><p><strong>Requirements:</strong></p><ol><li>The only api we need here is <strong>createOrUpdateCart</strong> that takes in a user id as input and updates the items in the cart.</li><li>We need a <strong>getItemsInCart</strong> api that takes in a user id and returns details of items present in the cart</li></ol><p>We just need to store a key value pair for this use-case where partition key is the UserID and value a list of catalogueIDs. Sort key is not needed here. We could choose any highly scalable No-Sql/SQL database here. AWS DynamoDb is a database that amazon built for this use case(<a href="https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf">Paper link</a>), so let’s use that directly here as it satisfies the requirements and it is easy to setup with no infra over-head.</p><p>We have a horizontally scalable shopping cart service now.</p><p><strong>Supplementary Information</strong><em>: In the dynamoDB paper, it is written that the application will need to have logic to resolve write conflicts, but that is not needed anymore. This is because they used multi-master writes are needed for each partition as part of quorum consensus when the paper was written but they have later migrated to use a single master write with Paxos for replication (</em><a href="https://youtu.be/yvBR71D0nAQ?t=352"><em>Tech Talk link</em></a><em>). </em><a href="https://youtu.be/yvBR71D0nAQ?t=2686"><em>Global Tables</em></a><em> still uses multi-master writes though!!</em></p><blockquote>Order Manager Service</blockquote><p>Order Manager Service deals with all the order related apis. When you proceed with the checkout process, an api called proceedWithCheckout is invoked that does the following things.</p><p><strong>Database storage and query requirements:</strong></p><ol><li>Need to store details of an order placed by a user.</li><li>Need to fetch details of orders placed by the user sorted by time</li></ol><p>Looking at the basic requirements, we can make use of any sql/nosql database that supports secondary indexes and is highly scalable. Have already mentioned a couple of options available to scale an sql database in the catalogue manager section.</p><p>Now, Apart from storing the order details in the database, order service</p><ul><li>Take a lock on the given quantities for each product present in the order so that we don’t place more orders than the quantity of items in the stock in case of concurrent orders from different users. Note that if a user drops out without paying in a pre-defined amount of time, then we need to remove the lock so that other users will be able to use those quantities.</li><li>Delete items from the shopping cart service.</li><li>Invoke Payment service to get the redirection url for the 2 factor authentication page of the preferred payment method and return back the url.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/452/1*5HUx8DUb6VwOsIEnY6hAfA.png" /></figure><p>The following steps will be done as part of proceedWithCheckout api</p><ol><li>User makes a proceedWithCheckout api call to the gateway</li><li>gateway does validations and passes the request to orderManager</li><li>orderManager creates an entry in order table</li><li>A message is put to delay queue with a delay of few minutes. If the customer drops off without doing payment, then this message can be used to fail the order after checking payment status and release lock on the quantity if needed.</li><li>UpdateQuantity api of catalogue is invoked to take a lock on the products</li><li>Clear the items from the shopping cart</li><li>Payment api is called to get the 2FA url and it is redirected to customer to proceed with the payment.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/1*pl2uYAGnqrk-UZAivSzE7A.png" /></figure><p>After Customer does payment, orderManager service can listen to events from payment to update the order status. It can release the lock on the catalogue if payment fails and mark order as failed. If payment succeeded then, order can me move to successful state.</p><p>After few minutes, orderManager will also get a notification from the delay queue. If the payment has still not been done when orderManager gets this event, then order manager can choose to fail the order and release the lock on catalogue.</p><blockquote>Handling Flash Sales</blockquote><p>Say we are launching a new smart phone through our portal for the first time. The number of users trying to buy the product would be much higher than the the number of items of the product available. Our design takes care of this problem by reducing the quantity before proceeding with payment. But still, if too many users are trying to place the same object at once (which generally happens in a flash sale), then it can can cause high load on that particular database instance which us basically called the hot partition problem.</p><p>First thing needed to solve this is to make use of a cache like redis for all the reads. When ever any DB write happens, the quantity can be updated async using a distributed queue like sqs/kafka. This will help us in scaling reads and reduce calls to the database. Catalogue database calls only needs to be made in ProceedWithCheckout api call.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/252/1*LopDmkO7A_oVL6Xze2mcGA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/451/1*SyazY_o6luLZYB9Gn7nhHg.png" /></figure><p>Adding a cache solves our problem to an extend, but the number of database calls would still be high as part of proceedWithCheckout api call.</p><p>One solution here is to throttle the number of write calls per product. We could return a throttle page url that has a messaging on the lines of “<strong>You’re In Line To Check Out</strong>”. This page can keep on polling proceedWithCheckout api every few seconds to see if it is able to go through the checkout. We can make use of R<a href="https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/">edis sorted sets to rate limit</a> calls. Each product will have its own sorted set here.</p><p>Another option is to split a product into multiple rows. For eg: if there are 3000 quantities of products, we could say divide it by 3 and store it as 3 rows in the table each row having a quantity of thousand. We can put these in 3 different shards as well using the primary key as a shard key. Now we can do a weighted round robin on the remaining quantities and load balance writes to each of these rows. We will need to keep track of this split in a separate table as well. We will also need to schedule a job that runs at low traffic time that can merge these splits if when merging can result in rows that are lesser than the threshold as well.</p><p>A combination of both these solutions together can be used to handle flash sales.</p><blockquote>References</blockquote><ol><li><a href="https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/DynamoDBMapper.OptimisticLocking.html">https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/DynamoDBMapper.OptimisticLocking.html</a></li><li><a href="https://www.cockroachlabs.com/docs/stable/architecture/overview.html">https://www.cockroachlabs.com/docs/stable/architecture/overview.html</a></li><li><a href="https://vitess.io/docs/">https://vitess.io/docs/</a></li><li>Dynamo Paper — <a href="https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf">https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf</a></li><li>DynamoDB — <a href="https://www.youtube.com/watch?t=352&amp;v=yvBR71D0nAQ&amp;feature=youtu.be">https://www.youtube.com/watch?t=352&amp;v=yvBR71D0nAQ&amp;feature=youtu.be</a></li><li>RateLimiting — <a href="https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/">https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=77d3ec1641f9" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>