<?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 KK XX on Medium]]></title>
        <description><![CDATA[Stories by KK XX on Medium]]></description>
        <link>https://medium.com/@morefree7?source=rss-10a6d1b6b34c------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*QggGZFsHjCgSr6SO.</url>
            <title>Stories by KK XX on Medium</title>
            <link>https://medium.com/@morefree7?source=rss-10a6d1b6b34c------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 16:28:25 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@morefree7/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 twitter timeline]]></title>
            <link>https://medium.com/@morefree7/design-twitter-timeline-e8f77acfbd06?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/e8f77acfbd06</guid>
            <category><![CDATA[facebook-newsfeed]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[twitter-timeline]]></category>
            <category><![CDATA[database]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Thu, 13 Jun 2019 23:03:09 GMT</pubDate>
            <atom:updated>2019-06-13T23:03:09.304Z</atom:updated>
            <content:encoded><![CDATA[<h4>problem statement</h4><blockquote>Design the backend for twitter timeline / facebook newsfeed.</blockquote><h4>how to approach</h4><p>Unlike my other posts, for this design problem there’s already <a href="https://www.infoq.com/presentations/Twitter-Timeline-Scalability/">an excellent talk given by Twitter’s engineer</a>. This post is a summary of the contents from the talk.</p><h4>Design goal</h4><p>here are some numbers that affects the architecture :</p><ul><li>150M active users.</li><li>300K QPS for pull-based timeline query.</li><li>up to 800 tweets could be displayed on the timeline.</li><li>low latency on read : 1ms for p50 and 4ms for p95.</li><li>allowing relatively high on write.</li><li>5K new tweets per second on average. (12K at peak).</li><li>users can have up to tens of millions of followers.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/586/1*PsgS0wkm_c6lXHAiXwqARA.png" /><figcaption>architecture of twitter home timeline (source from the talk : <a href="https://www.infoq.com/presentations/Twitter-Timeline-Scalability/">timelines at scale</a>)</figcaption></figure><h4>Life of a tweet</h4><p>The diagram above (taken from the slides of the talk) gives all the high-level components. Briefly, the life of a newly-published tweet can be summarized as :</p><ol><li>whenever a new tweet is published, it reaches the fanout service, the fanout service queries the social graph service, find out all the followers (target timelines), then it inserts the tweet id into the Redis cluster in the format <em>(tweet_id, author_id, meta_data)</em>. The social graph service keeps track of all the followers / followees information.</li><li>Redis cluster replicates its data on other Redis machines. Each replica stores a partition of users and the tweets that should appear in their timeline, like <em>(user_id, [tweet1, tweet2, …]),</em> where tweetN has the format of <em>(tweet_id, author_id, meta_data)</em>. It leverages the native list structure supported by Redis. It’s a product call to decide the max number of tweets that should show in the timeline (in the talk, it mentions the number is 800).</li><li>Tweets are persisted by the timeline service only. For home timeline, tweets are stored in memory of the Redis cluster only. This is to satisfy the low-latency requirement of read (Remember that a random IO against SSD disk may take a few ms). If any of the machine crashes, it reconstructs the timeline data by querying social graph service and timeline service again. Each Redis instance is replicated 3 times, and on the read side, the timeline service finds out the closest Redis machine through a hash ring lookup (details are not mentioned in the talk, but I will discuss a bit more below). The key design tradeoff here is : it’s designed in favor of read, while allowing write to have a relatively higher latency. In the architecture above, the read is just O(1) (while write takes O(n), where n is the number of followers).</li><li>the problem with the architecture above is, the fanout service is slow, especially for those user who has millions of followers (call high-volume users). the remaining part of the talk presents an optimization : do not fanout tweets to high-volume users. Instead, merge them on the read path. It’s a tradeoff between high read latency and high write latency.</li></ol><p>One implementation detail not mentioned in the talk is, how to replicate the Redis instance, how to partition the data, and how to locate the closest instance for a given read query. These are common problems for data-intensive systems, and can be solved with some common techniques( some of them are described in my other posts). For example, one potential solution is the consistent hashing algorithm : map all the Redis instances on a ring, where one physic node is mapped to 3 virtual nodes randomly and uniformly. A tweet will be stored on the first 3 instances it encounters when it talks through the ring clockwise starting from its own hash value. Note that the consistent hashing algorithm is easy to yield unbalanced partition without careful tuning. On the read path, since each node on the ring encodes it geo-location information, the client could easily choose the one that is closest to its own geo-location.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e8f77acfbd06" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design a system that tracks the number of “likes”]]></title>
            <link>https://medium.com/@morefree7/design-a-system-that-tracks-the-number-of-likes-ea69fdb41cf2?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/ea69fdb41cf2</guid>
            <category><![CDATA[big-data]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[facebook-interview]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Wed, 12 Jun 2019 19:34:24 GMT</pubDate>
            <atom:updated>2019-06-12T19:34:24.598Z</atom:updated>
            <content:encoded><![CDATA[<h4>problem statement</h4><blockquote>Design a system that tracks the number of “likes” (posts / tweets / photos) at scale.</blockquote><h4>how to approach</h4><p>This is an interesting problem that looks very simple at first, but actually requires careful thoughts to make it “right”. I will show my thoughts below and demonstrate how the architecture evolves when requirement changes.</p><p>The simplest design we can come up with is :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*diLJqbqJ2SugJ_gOIzU1Ig.png" /><figcaption>Fig 1. use a single table</figcaption></figure><p>Here are the pros and cons of this simple design :</p><ul><li>+ strong consistency guarantee. any read-after-write is guaranteed to return the latest number of counts. the client would never see a stale read.</li><li>- it doesn’t not scale well. millions of concurrent insertions might slow down the DB. We can shard the DB by post_id, but that doesn’t mitigate the high volume of concurrent insertions.</li><li>- it’s expensive to count the rows on-the-fly (note that engines Innodb doesn’t maintain a count internally, instead, queries like “SELECT COUNT(*) FROM LIKES WHERE …” almost always re-scan the table). We can introduce another component, either a cache or another table to store the count number, if we do that, the key problem is how to make the “likes” table and the “like-count” table consistent.</li></ul><p>To overcome the last two issues, we have to relax the consistency model a little bit : now after user clicks “like” on a post, it returns immediately without waiting for the entry being inserted into the DB. We also introduce some additional components below :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*IOK-Fi53a_0t3777_ouS8Q.png" /><figcaption>Fig 2. MQ, Batch updater, Cache.</figcaption></figure><ul><li>MQ : a message queue is used as a buffer for async update, and for reliably “broadcast” the (post_id, user_id) pair to multiple consumers. Apache Kafka is a popular choice in industry.</li><li>Updater : this is just a consumer that consumes message and insert it into the “likes” table.</li><li>Batch updater: by relaxing the consistency model, we are able to batch the updates with the same post_id to reduce the write load to DB. The downside is that it requires introducing additional infrastructure, like a stream processing cluster (ex. Apache Flink, Apache Storm, etc.), to do the “batch update” reliably.</li><li>A cache is used to store the latest count of likes of posts.</li></ul><p>The pros and cons of the second design are :</p><ul><li>+ by using MQ as a buffer, it reduces the write load to DB.</li><li>+ by using batch updater, it further reduces the write load on some popular posts.</li><li>- The data in “likes” table and “like-count” table may become inconsistent. This can happen even without component failure — most MQ cannot guarantee exactly-once processing. we might see more “likes” than the real number.</li></ul><p>To overcome the inconsistency, one approach we can use is to re-compute the count from the “likes” table periodically. Since “likes” table always holds the source of truth, the recomputed result could be used confidently. To get the real-time number of likes for a post, such result must be merged with the “likes” on-the-fly. As illustrated in the figure below :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*ogdn1U4vexbJePwNVnoYmA.png" /><figcaption>Fig 3. Online + offline</figcaption></figure><p>In the figure above, we calculate the likes from the “likes” table with a daily cron job, that would give us the accurate number, before 12am every day. On the other hand, the “real time events” table should keep track of all the “likes” happen after 12am (12am — now). By reading from both table, we should get a pretty accurate and up-to-date count number. This design often refers as the <a href="https://en.wikipedia.org/wiki/Lambda_architecture">Lambda Architecture</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ea69fdb41cf2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design a picture service]]></title>
            <link>https://medium.com/@morefree7/design-a-picture-service-357abb050d23?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/357abb050d23</guid>
            <category><![CDATA[facebook-interview]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[web-development]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Tue, 11 Jun 2019 19:42:51 GMT</pubDate>
            <atom:updated>2019-06-17T18:37:19.545Z</atom:updated>
            <content:encoded><![CDATA[<h4>problem statement</h4><blockquote>Design a picture sharing service similar to Instagram.</blockquote><h4>how to approach</h4><p>in the following discussion, I will present a simple solution that provides the basic picture sharing functionality; I will avoid using the term “Instagram” because at that scale, everything becomes different (for example, you may need <a href="https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Beaver.pdf">a specialized picture store</a>).</p><p>As other system design problems, we should always start with briefly discussing the basic use cases (described in terms of API or read-write workflow) with the interviewers to narrow down the problem. Let’s assume we agree on the simplified requirements below :</p><p><strong><em>write flow</em></strong> : a user is allowed to upload a local picture to the server, the server should return a unique id to the user. Later the user can view or delete the picture with the unique id.</p><p><strong><em>read flow</em></strong> : whoever visits a user’s page should have access to the all the pictures uploaded by that user — shown in pagination.</p><p><strong><em>consistency</em></strong> : eventual consistency. seconds of delays are allowed between “upload” and “view the picture”.</p><p><strong><em>scalability</em></strong> : the system should scale to millions of users and billions of pictures. there might be “hotspot” — a user’s main page might be accessed by millions of other users at the same time. the upload traffic is relatively low. assume that the average size of the picture is 1MB.</p><p><strong><em>authentication</em></strong> : we omit the authentication part in the system.</p><p>Ideally these decisions shouldn’t take more than 10 minutes (otherwise you won’t leave enough time explaining the interesting part). Briefly write them down on the side of the whiteboard, and make sure the system you design satisfy all the requirements.</p><p>Next, let’s draw a basic architecture. Though it’s simple, it’s quite similar to the real architecture used in a few popular internet companies.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*Aeh1PvmoZmVUXZNEU17IsA.png" /><figcaption>a simple architecture</figcaption></figure><p>In the architecture above, on the write path,</p><ol><li>the user upload new images to the frontend web server, via http(s) call.</li><li>upon receiving the whole picture, the web server saves the picture to Image Store.</li><li>If 2 succeeds, the web server then saves the meta data to the Meta Store. The meta data may include author, timestamp, the path to Image Store, uid, etc.</li><li>If 3 succeeds, the web server sends back the generated url to the client. the url typically consists of the host name (usually point to CDN), path and the uid of the picture.</li></ol><p>On the read path,</p><ol><li>the client reads the new picture from CDN.</li><li>CDN calls the original web server on behalf of the user to fetch the original pictures and store locally.</li></ol><h4>Image Store</h4><p>we use a file system or an object store to save the picture data (after compression), such as HDFS, AWS S3, etc. The path to HDFS / S3 will be stored in Meta Store. Both options can scale to PB level of data.</p><h4>Meta Store</h4><p>the first choice is to use a RDBMS to store the meta data and generate the uid. Per assumption above there might be up to billions of rows to store. A powerful AWS RDS instance type is sufficient to handle the data at that scale. If we exceed that scale, we need to replace the Meta Store with some scalable system, for example, a UUID generator service, plus a distributed key-value store.</p><h4>Latency</h4><p>remember that the latency of these operations are at millisecond level : randomly read a picture (1MB) from SSD; send the picture over network within the same data center; randomly read KB-level of data (meta data) from billions of rows with index in RDBMS. Though the accurate number can never be told without repeated performance test, a millisecond-level (&lt; 1 second) latency is still a reasonable estimation. The end-to-end latency will most likely be bounded by the data communication between the client and the CDN.</p><h4>Hot Spot</h4><p>Even though CDN can shed a lot traffic, it’s still worth setting up your own cluster between server and the stores, especially the Meta Store. When a user’s main page is accessed by millions of other users at the same time, it might cause the <a href="https://en.wikipedia.org/wiki/Cache_stampede">Thurdering Herd</a> problem. To mitigate that, a randomly-chosen expiration time is a useful idea : let’s assume that a cached entry was inserted at timestamp 1000, and will expire at 2000. when reading it, each server generates a small number as the “early expiration value”. for example, whenever server 1 reads the entry, it generates a small number 250, that tells server 1 the actual expiration time of that entry will be at 1750 instead of the original value 2000. By enforcing that, no more entries will expire at timestamp 2000; another approach is to make the cache server returns a lease to the client, and only the client who holds the lease is allowed to modify the key; by doing so, at most one of the concurrent writes will succeed at the same time, the remaining writes will have to retry in a short period. The second approach was proposed in <a href="https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf">this paper</a> and requires some modification of existing open source cache solution.</p><h4>Newsfeed generation</h4><p>The last remaining topic is how to present a user’s main page — assume that on it should include a list of recent pictures the user uploaded. This feature is similar to Twitter’s timeline generation, which is discussed in <a href="https://medium.com/@morefree7/design-twitter-timeline-e8f77acfbd06">my other post</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=357abb050d23" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design the auto-complete/type-ahead backend]]></title>
            <link>https://medium.com/@morefree7/design-the-auto-complete-type-ahead-backend-dc7ec56dc1df?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/dc7ec56dc1df</guid>
            <category><![CDATA[big-data]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[autocomplete]]></category>
            <category><![CDATA[typeahead]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Sun, 09 Jun 2019 05:59:01 GMT</pubDate>
            <atom:updated>2019-06-17T20:09:23.074Z</atom:updated>
            <content:encoded><![CDATA[<h4>problem statement</h4><blockquote>Design the backend for an auto-complete system, like Google or Amazon.</blockquote><h4>design goal</h4><p>as usual, we first need to make the design goals more explicit. Spend 2 minutes asking your interviewers questions like :</p><ul><li>what is the volume of queries the system need to handle (per second) ?</li><li>what is the expected latency ?</li><li>are the queries unbounded free text (like Google), or bounded by some predefined catalog (like Amazon products suggestions) ?</li><li>how we would like to show the suggestions ?</li><li>etc.</li></ul><p>The answer to the questions will guide all the design choices, for example :</p><ul><li>let’s say it’s designed for a popular website where the queries can be as high as up to 100K per second. This is already a very high number in real life. The number tells us : 1. the system needs to scale to 100K queries. That’s usually not a number that a single machine could handle. 2. the system needs to digest 100K queries to store and update the auto-complete system. this usually can be done in async fashion.</li><li>the auto-complete system is usually latency-sensitive. Let’s say we expected a P95 latency of 10 ms. The number indicates that it doesn’t necessarily require us to cache everything in memory — remember that both an inter-datacenter network call and a random access to SSD is at a few ms level; however, we should still try to use as much memory as possible, as it reduces the both the latency and the load to DB. As a side notes, if you are using RDBMS like MySQL, you need a pretty good DB instance, ex., db.r4.8xlarge from <a href="https://aws.amazon.com/rds/instance-types/">AWS RDS</a>, and a few replicas to handle 100K queries per second.</li><li>Let’s assume we are dealing with free text like Google’s auto-complete. That indicates a potentially much larger word space.</li><li>Let’s say that we will show the top N suggestions when user types 1 to M letters. The value of N and M guides the design. For example, when N = M = 5, even if we decide to pre-compute all the suggestions, that only indicates a max space of <em>(26 + 26² + 26³ + 26⁴ + 26⁵) * 5 * avg_len_of_word</em>, less than 0.5GB. The result shows we can easily hold everything in memory. On the other handle, when N = M = 10, the result will be larger than 1K TB. In the following discussion we assume we need multiple machines to hold all data in memory.</li></ul><h4>One approach</h4><p>One possible architecture may looks like below :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*toS_P-G-LC_fV_nYuV3dqQ.png" /><figcaption>the architecture</figcaption></figure><h4>K-V pairs</h4><p>Given the latency constraints, it’s impractical to generate the suggestions on-the-fly. Instead, we need to precompute the results, and save it as key-value pairs, where the key is the prefix typed by user, the values are lists of most popular suggestions. For example, (“mic”, [“michael jordan”, “microsoft”]) is a key value pair that means for the prefix “mic”, two of the most popular suggestions are the “michael jordan” and “microsoft”. The reason I choose key-value pair instead of some space-saving data structure like <a href="https://en.wikipedia.org/wiki/Trie">Trie</a> is, it’s more convenient to persist key-value pairs.</p><h4>Search log</h4><p>search log keeps the raw data generated by user. It’s the source of truth, and will be used to compute the K-V pairs. For example, from the same session, if user types “mic”, and eventually the user searched the term “microsoft”, then it’s a signal that new users who type “mic” might actually be interested in “microsoft”. The algorithm behind this intuition is <a href="https://en.wikipedia.org/wiki/Bayesian_inference">Bayesian inference</a>.</p><h4>Offline Job</h4><p>now we need an offline job to transform the search log into key value pairs. This is often achieved by running a map-reduce style batch processing job. We then push the generated key-value pairs to a distributed key-value store, such as Redis or HBase; and we also push the key-value pairs to the upfront servers, to update their cache. In practice we can rely on some message queue like Kafka to reliably publish the results. The reason we need to update the server directly is because it can reduce the load to DB for some popular search terms.</p><h4>The Servers</h4><p>The servers are responsible for caching the precomputed search term, and handling all the user queries. When the term is missed in its local cache, it queries the backend distributed key-value store. If the data exceeds the capacity of a single machine’s memory, we partition the prefixes with a hash function; also, to scale it out, we also need replicas for each partition as illustrated below. these techniques are common, and similar to other design questions. you can find more about partition / replication from my other posts.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0azzZh-WrZSnp7986fhztA.png" /><figcaption>server partition and replication</figcaption></figure><p>In the diagram above, we assume we use the first letter to partition the search terms (this may result in imbalanced partitions). we store all K-V pairs whose key is “a” on node 1 and 2, all K-V pairs whose key is “b” on node 2 and 3, and all K-V pairs whose key is “c” on node 1 and 3. We write these meta data to a registry. In practice the registry can be any server cluster that runs Paxos-like protocol (including Zab and Raft). The routing layer hides the complexity of data partition by reading and caching the meta data from the registry first, then it sends the request to the nodes in charge in a round-robin fashion. For example, it routes search terms starting with “a” to 1 and 2 repeatedly.</p><h4>Personalized data</h4><p>What we didn’t touch in the architecture is the personalized data. If you search from google, the result takes your personal interest into consideration. This is generated by merging the results of your search history with the K-V pairs.</p><h4>CDN</h4><p>Another design choice we usually make in real-world project is introducing the CDN to reduce the latency. I will omit the discussion in this post — you can refer to <a href="https://www.imperva.com/learn/performance/what-is-cdn-how-it-works/?utm_campaign=Incapsula-moved">this article</a> to understand the hows and whys about CDN.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dc7ec56dc1df" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design facebook posts search]]></title>
            <link>https://medium.com/@morefree7/design-facebook-posts-search-10c9aceb6f39?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/10c9aceb6f39</guid>
            <category><![CDATA[facebook-interview]]></category>
            <category><![CDATA[search-engines]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Wed, 05 Jun 2019 02:10:42 GMT</pubDate>
            <atom:updated>2019-06-05T02:10:42.020Z</atom:updated>
            <content:encoded><![CDATA[<p>problem statement (source from internet)</p><blockquote>Design the backend of the facebook posts search bar.</blockquote><p>Note that given the statement we should immediately notice that :</p><ul><li>at facebook level, the number of posts is too large to fit in a single machine.</li><li>the number of posts is increasing constantly, our design needs to take this into consideration.</li><li>as a design goal, we probably want to minimize the latency, while a relaxed consistency model might be acceptable.</li></ul><p>Typically, an industrial-level search backend might look like this :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*gG9kq5l2DfvitxOSBQ-Eeg.png" /><figcaption>an architecture for a search backend</figcaption></figure><p>A lot details involved in the diagram above. I will explain each of them below.</p><h4>Query layer</h4><p>The query node layer is typically a stateless layer. Its main job is to translate the query request to the calls to the index layer. The raw keyword typed by user might be processed through a bunch of steps, like text normalization, query expansion, etc. The query node layer may also contact other services, like the service that provides user preferences, geo-location, or search history, which are all signals that help the translation.</p><p>The response from each index node below may contain a list of ranked post ids. A query node is also responsible for aggregating the partial results to present a final result to the users.</p><h4>Index layer</h4><p>An index node stores index data locally. Each post has a unique post id, 1, 2, 3… An index maps a keyword to a list of post ids, with a ranking score. The index layer answers the question : given a list of keywords, and a ranking algorithm, what’s the top K post ids ? Popular libraries like <a href="https://lucene.apache.org/core/">Lucene</a> does this work for you.</p><p>Even the size of an index might be much smaller than the original posts (the index only stores post id, it doesn’t store the entire post), it still may exceed the capacity of a single machine. For example, assume each post has a size of 1KB, a billion of posts cost about 1TB data, a typical size of indexing could be about 30% of the post size, so approximately it may cost 300GB. An index file of 300GB can be easily stored in a single storage optimized AWS EC2 machine; however, applying sharding also opens the possibility of accelerating the queries. For example, if we partition the index data to 30 shards, each of them holds 10GB of data, then we can use the memory-mapped file to make most data stay in memory. Given that, in the remaining part of the post we assume a partition (or sharding) is necessary.</p><p>When it comes to sharding, some typical questions may be raised, as we design other distributed systems, like : how to partition the data ? how do we query each shard ? what if a shard fails ? etc. As usual, we can partition the data by <em>hash(post id) % number_of_shards. </em>The query layer is responsible for sending the requests to all shards and aggregate the results. Also, to tolerate shard failure, a shard should be replicated on other nodes (replicas). Depends on the consistency model we choose, we also need to choose the right replication algorithm to keep all replicas in sync.</p><p>Each index node relies on the current index data, and a customized ranking model to answer a query. As shown in the diagram, ideally the index data should be updated to reflect the latest change in real-time. We will explore this part in more details below. Before returning the results to the query node, the index node also uses its own ranking model to give a ranking score to each post. The results from all index nodes will be aggregated and ranked again on the query layer, before returning a final result to user.</p><p>Popular solutions, like the <a href="https://www.elastic.co/">elasticsearch</a>, uses similar architecture above. By default, it uses a hash based sharding, and a primary-secondary replication (each update is forwarded to a primary replica first, then to all other replicas).</p><h4>Index update</h4><p>One challenge we have to address is, keep the index data up-to-date since new posts are creating, old posts are updating all the time. We assume the real posts data are stored in a key-value store such as Apache Cassandra, which used to be used widely in Facebook. The posts can be queried / updated by a wrapper Post service (a side note : in industry it’s common to build a data service on top of the database, even though the data service itself does nothing more than forwarding the request to DB. by doing so we don’t have to affect users if we decide to switch to another DB). A common techniques used in industry to export the data from DB incrementally is called the <a href="https://en.wikipedia.org/wiki/Change_data_capture">Change Data Capture</a>. Using this technique, any change on DB could be captured by the real-time updater, and translated to index update request, and sent to the index layer, in near real-time.</p><p>As a companion to the real-time updater, we often need an offline update pipeline, to update the index data in batch mode. This is mainly because 1. it’s usually hard to make the real-time updater 100% reliable, there might be important data loss or incorrect update, due to hardware failure or race condition (ex., two updates are sent to the index data in reversed order, where the stale data is updated later); 2. sometimes we just want to index the docs differently, so we need to re-compute the index and roll it out to all index nodes. In general, having such offline pipeline makes the index layer more robust — if we have a daily offline job to update the index as a whole, any mistake we made wouldn’t last for more than one day.</p><h4>Query Frontend</h4><p>Finally, since the query layer returns post ids only, the query frontend should query the Post service by the ids, and do proper aggregation. It’s often called the presentation layer.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=10c9aceb6f39" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Design a distributed web crawler]]></title>
            <link>https://medium.com/@morefree7/design-a-distributed-web-crawler-f67a8ebb8336?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/f67a8ebb8336</guid>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[web-crawler]]></category>
            <category><![CDATA[web-crawling]]></category>
            <category><![CDATA[facebook-interview]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Mon, 03 Jun 2019 19:06:55 GMT</pubDate>
            <atom:updated>2019-06-17T21:47:10.589Z</atom:updated>
            <content:encoded><![CDATA[<h4>The Problem</h4><p>statement 1 (source from internet) :</p><blockquote>Download all urls from 1000 hosts. Imagine all the urls are graph. Requirement: Each host has bad internet connection among each other, Has to download url exactly once.</blockquote><p>statement 2 (source from internet) :</p><blockquote>Use 10k IOT machine (limited cpu, bandwidth) to crawl wikipedia. 1. don’t repeat same URL; 2. Minimize traffic. 3. save webpage locally (no storage problem).</blockquote><h4>Single machine</h4><p>On a single machine, this problem is deduced to a simple graph search problem, which can be solved with a simple BFS algorithm :</p><pre>seed = { ... }  # initial url set<br>seen = {}<br>for url in seed : <br>   break if goes too deep<br>   page = download(url)<br>   urls = extract_url(https://medium.com/page)<br>   for url in urls :<br>     if url not in seen : <br>        seen.add(url)<br>        seed.add(url)</pre><h4>Multiple machines</h4><p>Let’s assume that the machines are within the same data center. When it comes to multiple machines, here are some problems we need to consider :</p><ol><li><strong>how to distribute work ?</strong> Basically each machine should be responsible for a subset of urls, we need to divide the entire url set into subsets, such that :</li></ol><ul><li>Machines might be heterogeneous. that means some machines might be faster than other machines. Ideally the partition algorithm should be able to assign partitions according to a machine’s capacity.</li><li>Maximize network usage. If we assign urls belonging to the same domain to the same machine, we may save time rebuilding TCP connections; also, in real world that the servers most likely have some rate limit mechanism, which means we need to control the speed for sending requests to the same server. Sending urls belonging to the same domain on the same machine makes it much easier to control such speed. This may not be a problem if we are asked to download Wiki pages (since all of those urls belong to the same domain).</li><li>Tolerable to membership change. In a real system when network partition occurs, or a hardware fails, some machines might not be available; on the other hand, we can always add more machines to even the workload. The partition algorithm should try to minimize the work when membership change happens.</li></ul><p>In practice we can first map each url to a non-negative 64-bit integer, and divide the whole range into Q sections (Q &gt;&gt; M, the number of machines). Then we randomly assign each section to machines based on machine’s capacity. When a new machine joins, it “steals” some partitions from existing machines. The “stealth” is a good chance of balancing the workload of the cluster— for example, it can simply steal partitions from the machines with the highest workload.</p><p>Note that a common term mentioned in literature or distributed system blogs is “consistent hashing”. However, it’s very easy to get misused without tuning it carefully. One can refer to [1][2] for how to tune consistent hashing correctly.</p><p>Also note that the even distribution of urls may not result in even workload on different machines, because the size of the page, the geo-location of the servers, and the workload of the servers may all be different. To achieve a real even workload, we need to rebalance workload when necessary. Technically the process of “rebalance” can be the same as “stealth” (when membership change happens), and it’s a manual process in a lot real-world systems.</p><p>2. <strong>how to coordinate ?</strong> Each machine may download urls that need to be handled by other machines. When it happens, how to forward such urls to other machines ?</p><p>The answer to this question would affect the architecture of the system. In a master-slave system where a single master exists for all the coordination work, while all the slave nodes can be simply stateless, all urls should be forwarded to the master, and the master will forward urls to machines. There’s no communication between slave nodes at all; On the other hand, in a peer to peer system, there is no single master, all nodes have to know where to forward a url.</p><p>It would be a long list to compare the pros and cons of these two architectures. However, the problem gives a good hint : minimize the traffic between nodes. This indicates that a peer-to-peer architecture would be a better one since its overall traffic is only half of a master-slave architecture.</p><p>3. <strong>how to make sure each URL is downloaded exactly once ?</strong></p><p>Since we already decide to forward url based on hash partition, that means the same url will always be handled by the same machine (given no machine failure). In a single machine we can use either a hash table or a bloom filter (if the number of urls to download is huge) to achieve this.</p><p>So far we got a rough design that works. There are a few follow-up domains to further discuss (you can briefly discuss with interviewers during interview). In this article I will focus on a common follow-up problem : fault tolerance. i.e., what happens if a node fails ?</p><p>4. <strong>how to make it fault tolerant ?</strong></p><p>A node can fail at any time, and recover later (ex., restart, temporary network partition). When such failure happens, we need to find other nodes to continue the work of the failed node; also for those nodes who are forwarding urls to the failed node, they should forward to a different one.</p><p>The second case is relatively easy to solve. We can borrow the idea of “consumer group” from [3], i.e., two or more nodes can form a group, ex., node 1, 2, 3 forms a group. Normally node 4 is sending urls to node 1, when it finds that node 1 is unreachable, it may chooses another node from the group, say node 2, and always forward new urls to 2 going forward (even though node 1 recovers later). This preserves the “exactly once downloading” property.</p><p>The first case is more difficult : how can we find a node to continue node 1’s work when it fails ? and what should we do when it recovers ? Unfortunately, to detect a node failure, and to find a new node to replace the failed node while preserving the “exactly once downloading” property, we need a master node. A master node plays two roles, first, it sends the heartbeat periodically to all worker nodes, so it can detect a node failure; second, each worker node should check out its current progress to some external system (or to master node), so its work can be continued when it fails. Keeping a master node simplifies the architecture.</p><p>Note that “exactly once downloading”, as described in the problem cannot be achieved accurately with the architecture described above. In practice we cannot distinguish between “downloaded the page successfully, but failed to check out the progress” and “failed to download the page”. It’s better to avoid using the term “exactly once” here.</p><h4>Put it together</h4><p>The description above yields a simple architecture below :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d1zwA5zbr0Sx0ma3aEdfWw.png" /></figure><p>0. start up stage : deploy metadata to all workers. meta data include seed urls, and decisions about how to divide urls to partitions, assign partitions to each worker, and which workers form a group.</p><ol><li>worker 2 downloads the page <em>wiki/apple</em>, and extract <em>wiki/banana</em> and <em>wiki/pineapple.</em></li><li>based on the meta data, worker 2 decides to forward <em>wiki/banana</em> to worker 1, and forward <em>wiki/pineapple</em> to worker 3. If either worker 2 or worker 3 does not respond, worker 2 marks them as “fail” locally, and choose another group member to forward.</li><li>after downloading <em>wiki/apple</em>, worker 1 checks this progress out to master 1.</li><li>master 1 replicates the data to master 2, in case itself fails.</li><li>master 1 sends heartbeat to all workers regularly to detect node failure. Once detected, it assigns the work left on the failed node to another node, and update meta data on all workers.</li></ol><h4>Implementation</h4><p>Coming soon…</p><p>All details should make sense when it’s presented in code.</p><h4>References</h4><p>[1] Dynamo paper : <a href="https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf">https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf</a></p><p>[2] Consistent hashing with bounded loads : <a href="https://ai.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html">https://ai.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html</a></p><p>[3] Kafka design : <a href="https://kafka.apache.org/documentation/#design">https://kafka.apache.org/documentation/#design</a></p><p>[4] Web crawling survey : <a href="http://infolab.stanford.edu/~olston/publications/crawling_survey.pdf">http://infolab.stanford.edu/~olston/publications/crawling_survey.pdf</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f67a8ebb8336" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Map-Reduce notes]]></title>
            <link>https://medium.com/@morefree7/map-reduce-notes-97824ccd07d6?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/97824ccd07d6</guid>
            <category><![CDATA[big-data]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Sun, 26 May 2019 22:48:52 GMT</pubDate>
            <atom:updated>2019-05-26T22:48:52.898Z</atom:updated>
            <content:encoded><![CDATA[<p>A common misunderstanding by reading the original <a href="https://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf">Map-Reduce paper</a> is, the master node is considered a single point of failure. Actually it’s not true. In the original paper, it mentions that a client job is submitted to a scheduler (also in the “acknowledge” section it mentions that a cluster management system was developed to support mapreduce at Google). Such scheduler should be very similar to today’s YARN or Mesos — as what we saw in today’s Hadoop stack.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iDrh5-U6N_lJsWE5ibEVng.png" /></figure><p>With YARN, the workflow of submitting a Hadoop job looks like these :</p><ol><li>client contacts the resource manager, requesting the resource manager to launch an Application Master. The resource manager is a node in YARN that monitors the resources (cpus, memories, etc) of all worker nodes, and offer the worker nodes based on the resources requested by the client. The Application Master is a client-specific instance (it’s not a special node, instead, it can be run on any worker node), and it serves as the “master” node described in the original paper, for that specific Hadoop job.</li><li>Once the Application Master is launched, the client no longer interacts with the resource manager. Instead, it contacts the Application Master directly, and the Application Master requests worker nodes to launch map and reduce jobs on behalf of the client.</li><li>On any job failure, the Application Master re-request resources and re-execute the failed jobs.</li><li>If the Application Master itself fails, the resource manager simply launches another instance of Application Master. That implies :</li></ol><ul><li>the resource manager has more than one roles : it serves as a scheduler, as well as monitoring all application masters.</li><li>the Application Master has to be implemented in a way that fast-failover is possible.</li></ul><p>If you think of the whole cluster as a single computer, the resource manager will be your operating system that schedules processes on shared cpus and memories; each map reduce job is like a process, which is independent of other processes; finally, application master and worker nodes are like threads in the process.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=97824ccd07d6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Google File System notes]]></title>
            <link>https://medium.com/@morefree7/google-file-system-notes-baf0c57b9713?source=rss-10a6d1b6b34c------2</link>
            <guid isPermaLink="false">https://medium.com/p/baf0c57b9713</guid>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[big-data]]></category>
            <dc:creator><![CDATA[KK XX]]></dc:creator>
            <pubDate>Sat, 04 May 2019 01:14:50 GMT</pubDate>
            <atom:updated>2019-05-26T22:49:39.664Z</atom:updated>
            <content:encoded><![CDATA[<p>Google File System notes</p><p>In this blog I outline some important, general ideas from the classic paper <a href="https://static.googleusercontent.com/media/research.google.com/en//archive/gfs-sosp2003.pdf">Google File System</a>. Note that the term “general” means, these ideas are not limited in the distributed file system domain, instead they can apply to other distributed systems as well.</p><p>In general, GFS consists of two types of nodes, master and chunk-server. the master stores all meta data about the system, while the chunk-server stores the real file data.</p><p>Typical GFS operations can be outlined as follows :</p><h4>on start up</h4><ol><li>when master starts, it starts to send heart-beat messages to all known chunk-servers. note that when master starts, it doesn’t know any chunk-server. instead, the chunk-servers have to register” themselves to master (the reason is described in section 2.6.2 in the original paper).</li><li>a chunk server knows the address of master server when it starts. once it’s running, it “registers” it self to master. after that, the master knows the existence of the chunk-server, and it will send heart-beat to the chunk-server periodically.</li></ol><p>notes :</p><ul><li>it’s not really a single-master system. the master actually can be treated as stateless — datas on the master are saved in write ahead logs and the logs are shipped to other machines in case the master fails. In section 5.1.3 it describes an extra infrastructure that monitors the single master and replaces it with a new master if necessary. since the client contacts the master by cname, they are unaware of the change.</li><li>by making chunk-servers register themselves to the master, it greatly simplifies the complexity of dealing with membership change, like a chunk-server’s leave and re-join.</li></ul><h4>on write a file</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/926/1*BO_dggd86QcVt9l0nabEVQ.png" /><figcaption>GFS write flow</figcaption></figure><ol><li>the client contacts the master with metadata like the file path.</li><li>the master decides which chunk-servers to put the new file (described in section 4.3 of the original paper, but lack of details), and returns the decision to the client, the response also includes other information like among the chosen chunk-servers which one is the primary (used on step 4).</li><li>the client starts to push the mutation data to all chunk-servers. this replication process is optimized with a “chain-replication” process described in section 3.2.</li><li>once all chunk-servers receive the client data, the client now contacts the primary chunk-server, to let it determine the order of applying those mutation data — this is because a chunk-server might receive concurrent mutation from different clients, and a unique order has to be determined across all the mutation data. Once the primary chunk-server determines the order, it sends the order to other chunk-servers to really apply the mutations.</li></ol><p>notes :</p><ul><li>the client contact chunk-servers at least twice to complete a write. that indicates the process is not ideal for a write-heavy system.</li><li>by using the master + primary chunk-server, it uniquely determines the mutation order. This is equivalent to a two-phase commit process. note that this is also doable without using master, but just rely on the chunk-servers themselves, however that requires much more efforts to implement a Paxos-like protocol.</li><li>step 2 can be optimized by the using a lease (section 3.1). briefly a lease is similar to http cache control, it’s used to reduce the communication between master and other nodes.</li></ul><h4>on read a file</h4><ol><li>the client contacts the master server about the location of the file.</li><li>the master server replies with a list of chunk-servers. for each chunk, the master choses a replica that is close to the client’s location.</li><li>the client reads file directly from that chunk-servers.</li></ol><h4>fault tolerance</h4><ol><li>on master failure : the master node in GFS is a single point of failure. The entire system might be unavailable in a short time on master failure. All operations applied on master are saved in a Write-Ahead-Log (WAL), which is replicated to a backup node. GFS relies on a monitoring infrastructure 5.1.3) to detect the master failure, and switch the traffic to the backup node. — Imagine that the master node and the backup nodes are two records under the same CNAME.</li><li>on primary replica failure : consider a network partition between the master node and one of the primary replica. when that happens, the master node detects the failure (no heartbeat), and wait for the current lease to expire (in case the primary replica is still serving traffic from clients directly), and then assign the lease to a new node. the old primary replica, when recovers from the network partition, will be detected as “stale” by the master node, by checking the version number of the chunks. The master node will pick new nodes to replace the stale node, and garbage-collect it before it can join the group again.</li><li>on secondary replica failure : a replica failure would cause a client mutation operation to fail. when this happens, the client would retry a few times, if all of the retries fail, it reports failure. note that will probably leave the secondary replica inconsistent because it misses some mutations. As described above, stale nodes will be replaced by a new node picked by master, and be garbage-collected eventually.</li></ol><p>notes :</p><ul><li>we can see any of the three nodes (master, primary replica, secondary replica) fails, the system can be unavailable in a short time.</li><li>stale replicas might be exposed to clients. It depends on the application programmer to deal with this stale reads. GFS doesn’t guarantee strong consistency on chunk reads.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=baf0c57b9713" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>