<?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 Manthan chauhan on Medium]]></title>
        <description><![CDATA[Stories by Manthan chauhan on Medium]]></description>
        <link>https://medium.com/@manthanchauhan913?source=rss-6cd6e93cb39f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*yCuvWy-xJdHAISL9gUuxCg.jpeg</url>
            <title>Stories by Manthan chauhan on Medium</title>
            <link>https://medium.com/@manthanchauhan913?source=rss-6cd6e93cb39f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 21:58:31 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@manthanchauhan913/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[How to craft a database engine]]></title>
            <link>https://blog.devgenius.io/how-to-craft-a-database-engine-7c7996ddde84?source=rss-6cd6e93cb39f------2</link>
            <guid isPermaLink="false">https://medium.com/p/7c7996ddde84</guid>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[platform-engineering]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Manthan chauhan]]></dc:creator>
            <pubDate>Fri, 23 Feb 2024 18:17:54 GMT</pubDate>
            <atom:updated>2024-05-06T15:04:42.413Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j-HLB4x_l4g099mPkhnKNg.png" /></figure><p>Platform tools like database engines have always fascinated me as they provide a base upon which other applications are built and studying these tools provides deeper insights into these engineering marvels.</p><p>In this post I’ll describe how we can implement a <strong>persistent key-value database engine</strong>. We’ll explore the underlying complexities of data storage, indexing, durability and data fragmentation.</p><p>The design that we are going to implement is based on <strong>bitcask</strong>, a persistent key-value store designed for high write throughput and fast read operations. You can learn more about it in <a href="https://riak.com/assets/bitcask-intro.pdf">the original paper</a>.</p><p>I used Golang but the concepts discussed are applicable across programming languages. For those interested, Golang code is available on GitHub.</p><p>Explore the code repository here: <a href="https://github.com/manthanchauhan/key_val_db_engine/tree/hashIndex">https://github.com/manthanchauhan/key_val_db_engine/tree/hashIndex</a></p><h3>Architecture Overview</h3><p>We are using the <strong>log-structured hash table</strong> design for data storage due to its simplicity. In this design, data is stored in a sequence of append-only logs or files. When new data is written, it is appended to the end of the latest file.</p><p>Why append-only?</p><ol><li>Because appending a file is efficient compared to searching the file and updating the existing record.</li><li>Better concurrency handling. Since we never modify an existing record, chances are less that a thread might read any record in a partially-overwritten inconsistent state.</li><li>Better data durability as older data is never modified and can be recovered in the event of system crashes or mid-write failures.</li></ol><blockquote>This also means that writing a key several times will not clear the older values associated to that key hence wasting disk space. But we’ll deal with this garbage collection later.</blockquote><p>It is important to note that at any instance there could be multiple data files but only the latest one would be open to writes and the rest would be read-only forever.</p><p>Data is also indexed using a hash table, where each key is mapped to the filename and the <strong>byte offset</strong> of its latest entry. The byte offset refers to the distance, measured in bytes, from the beginning of the file to the respective data entry. Hence, with filename and byte-offset available we can locate any entry on disk in O(1) time.</p><p>This allows for fast key-based lookups, as the hash table provides direct access to the location of the data on disk.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fsdfMwKfYmBy8j7Qm4m-vg.png" /></figure><p>Note that the hash table resides inside the volatile memory and hence needs to be re-built at every program startup. This can be easily achieved by reading all the data files sequentially and adding each key to the hash table.</p><h3>Implementing CRUD</h3><p>Having understood the underlying data storage architecture, CRUD operations can now be implemented as follows.</p><h3><strong>CREATE (key, value)</strong></h3><p>First add the new record to the active data file and then to the hash table specifying the file and the byte-offset where the value is stored.</p><pre>// https://github.com/manthanchauhan/key_val_db_engine/blob/hashIndex/disk/disk.go#L37<br><br>func Create(key string, val string) string {<br>    logFileName: = LatestSegmentName<br><br>    // Open the active data file<br><br>    f, deferFunc: = GetLogFile(logFileName, os.O_APPEND | os.O_WRONLY)<br>    defer deferFunc(f)<br><br>    // Write into the active data file<br>    // get number of bytes written in return<br><br>    byteCount: = dataSegment.Write(key, val, f)<br>    fileSize: = GetSegmentFileSize(logFileName)<br><br>    // calculate byte offset <br>    // Note that the record we just added is the last record in the file<br>    // Hence just subtract the byteCount from total bytes in file<br><br>    byteOffset: = fileSize - int64(byteCount)<br>    dataLocation: = utils.GetDataLocationFromByteOffset(logFileName, byteOffset)<br><br>    // If the current file is full, create new active file<br><br>    if fileSize &gt;= constants.LogFileMaxSizeBytes {<br>        createNextDataSegment()<br>    }<br><br>    // this data location will be stored in hash table<br><br>    return dataLocation<br>}</pre><h3><strong>READ (key)</strong></h3><p>Get the file name and byte offset from the hash index. Read the record from the file using the byte offset.</p><pre>// https://github.com/manthanchauhan/key_val_db_engine/blob/hashIndex/disk/disk.go#L18<br><br>// Read &quot;file_name:byte_offset&quot; from hash index<br>// Get data stored at the &quot;file_name:byte_offset&quot;<br>func Read(dataLocation string) string {<br>    <br>    // Get fileName &amp; byteOffset from the value of hash table<br>    fileName, byteOffset: = ExtractFileNameAndOffset(dataLocation)<br>    <br>    // Open the file and seek to the byte offset<br>    f, deferFunc: = GetLogFile(fileName, os.O_RDONLY)<br>    defer deferFunc(f)<br>    <br>    // read the data at the byte offset<br>    _, err: = f.Seek(byteOffset, 0)<br>    if err != nil {<br>        panic(err)<br>    }<br>    <br>    scanner: = bufio.NewScanner(f)<br>    scanner.Split(dataSegment.SplitAt(constants.LogNewLineDelim))<br>    scanner.Scan()<br>    s: = scanner.Text()<br>    <br>    // return the data read<br>    return s<br>}</pre><h3>UPDATE(key, value) and DELETE(key)</h3><p>Both UPDATE and DELETE operations will be same as CREATE. For DELETE we’ll use a special tombstone value and handle that value in code. If this value is received while reading any data file, the key will be considered deleted.</p><pre>func Update(key string, val string) string {<br>  return Create(key, val)<br>}<br><br>func Delete(key string) string {<br>  return Create(key, &quot;#!DEL!#&quot;) // The value #!DEL!# is special tombstone value<br>}</pre><h3>Making It Efficient</h3><p>Having implemented the CRUD operations over a persistent storage, we have a working but un-optimal database engine. The engine has two problems,</p><ol><li>The storage needed is proportional to the number of WRITES performed which is much larger than the size of the actual data.</li><li>The in-memory index stores all the keys and hence needs large amount of expensive in-memory storage.</li></ol><p>Let’s now solve these problems one-by-one.</p><h3>Garbage Collection</h3><p>The problem is,</p><blockquote>writing a key several times will not clear the older values associated to that key hence wasting disk space.</blockquote><p>To solve this problem we’ll use the technique called “<strong>compress and merge</strong>”.</p><h3>Compression</h3><p>We’ll focus on the read-only data files and remove their garbage data to reduce the storage requirement of the database.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*64mtmjFkKldf4lOeOXKTdA.png" /></figure><p>To check if a record is active and in use, match the byte-offset of the record with the byte-offset stored in the hash index for the respective key. In case the two values match we can conclude that the record is active.</p><p>For each read-only segment,</p><ol><li>We’ll create a new blank data segment.</li><li>We’ll then iterate over the original data segment record-by-record, if a record is active we’ll copy it to the newly created data segment else, we’ll ignore it and move to the next one.</li><li>Once all the active records are copied into the new data segment we’ll iterate over this new data segment and for each record update the byte-offset stored in the hash index for the respective key. By doing this we have removed all the references of the original data segment.</li><li>We can now delete the original data segment.</li></ol><p>This way we have removed all the garbage data from the given data segment we’ll repeat this process for all the read-only data segments.</p><pre>// https://github.com/manthanchauhan/key_val_db_engine/blob/hashIndex/compressAndMerge/compress.go<br><br>// Call this for all the read-only data segments<br>func compressSegment(fileName string) {<br>    // create the new compressed segment<br>    newFileName: = createCompressedSegment(fileName)<br>    <br>    isCompressed: = disk.GetSegmentFileSize(fileName) &gt; disk.GetSegmentFileSize(newFileName)<br>    newFileIsEmpty: = disk.GetSegmentFileSize(newFileName) == constants.DataSegmentMetaDataByteSize<br>    <br>    if isCompressed {<br>        if newFileIsEmpty {<br>            disk.DeleteSegment(newFileName)<br>        } else {<br>            // Update the hash index to use the compressed segment<br>            hashIndex.ImportDataSegment(newFileName, hashMapImportSegmentInitValCheckForCompression(fileName))<br>        }<br>        disk.DeleteSegment(fileName)<br>    } else {<br>        disk.DeleteSegment(newFileName)<br>    }<br>}<br><br>func createCompressedSegment(originalSegmentFileName string) string {<br>    newFileName: = disk.CreateNewDataSegment()<br>    <br>    f, deferFunc: = disk.GetLogFile(newFileName, os.O_WRONLY | os.O_APPEND)<br>    defer deferFunc(f)<br>    <br>    // Iterate the originalSegmentFileName<br>    // Write each record into the new data segment<br>    <br>    disk.ParseDataSegment(originalSegmentFileName, func(k string, v string, byteOffset int64) {<br>        dataLocation: = utils.GetDataLocationFromByteOffset(originalSegmentFileName, byteOffset)<br>        isUsed: = dataLocation == hashIndex.GetDataLocation(k)<br>        if isUsed {<br>            dataSegment.Write(k, v, f)<br>        }<br>    })<br>    <br>    return newFileName<br>}</pre><h3>Merging</h3><p>With time, our database engine will continue to create more and more data segments most of which will be smaller than the set size limit due to the <strong>compression</strong> process described above. Thus, we’ll have tiny data segments scattered across the persistent storage.</p><p>This way our database engine will eventually face the problem of <strong>External Fragmentation</strong> and consequently <strong>File System Fragmentation.</strong></p><blockquote><a href="https://en.wikipedia.org/wiki/Fragmentation_(computing)#External_fragmentation">External Fragmentation </a>occurs when data is scattered across the storage in very small chunks leaving only small holes of available storage. The result is that, although free storage is available, it is effectively unusable because it is divided into pieces that are too small individually.</blockquote><blockquote>When a storage system has external fragmentation, inserting data causes it to be stored in scattered pieces instead of close together, slowing access due to seek time and rotational latency of the read/write head, and incurring additional overhead to manage additional locations. This is called <a href="https://en.wikipedia.org/wiki/File_system_fragmentation">File System Fragmentation.</a></blockquote><p>To contain this situation, we’ll periodically merge together small data segments into a larger data segment of reasonable size.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AoZ_ba5tmZw_cQX1C7ymFA.png" /></figure><p>Here is an overview of how we can do this. Suppose the desired segment size is 5MB.</p><ol><li>Retrieve the list of read-only segments along with their respective file sizes i.e[(s1.log: 2MB), (s2.log: 2MB), (s3.log: 3MB), (s4.log: 1MB)]</li><li>Identify the first <em>n</em> segments such that the total file size is either equal or just exceeds the desired segment size <em>(i.e. 5 MB)</em>. For the given example, we’ll pick the first 3 segments with total file size of 7 MB.</li><li>Create a new data segment and copy the records from each of the selected <em>n </em>segments into the new segment. Then we’ll iterate over this new data segment and for each record update the byte-offset stored in the hash index for the respective key.</li><li>Now we can safely delete the initial <em>n </em>segments.</li><li>Note that, if the total file size of selected <em>n</em> segments is greater than the desired segment size (i.e. 5 MB) then copy the last segment partially only and exempt this last segment from deletion. This segment will eventually be compressed and then merged in further iterations.</li><li>Repeat this process from the <em>n+1</em>th<em> </em>segment.</li></ol><p>This way we have merged together many small data segments into few data segments of reasonable size.</p><pre>func merge() {<br>    fileNames: = getReadOnlySegmentFileNames()<br><br>    if len(fileNames) &lt; 2 {<br>        return<br>    }<br>    for i: = 0;i &lt; len(fileNames); {<br>        <br>        // Find the segement range [i, j) to merge together<br>        start: = i<br>        var end int<br>        var j int<br>        var mergedSegmentSize int64 = 0<br>        <br>        // Considering `constants.LogFileMaxSizeBytes` as the desired segment size<br>        for j = i + 1;j &lt;= len(fileNames) &amp;&amp; mergedSegmentSize &lt; constants.LogFileMaxSizeBytes;j++{<br>            mergedSegmentSize += disk.GetSegmentFileSize(fileNames[j - 1])<br>        }<br>        if mergedSegmentSize &gt; constants.LogFileMaxSizeBytes {<br>            end = j - 2<br>        } else {<br>            end = j - 1<br>        }<br>        <br>        // Prepare merged segment<br>        mergedSegmentFileName: = mergeSegments(fileNames[start: end])<br>        <br>        // Update the references in hash index<br>        hashIndex.ImportDataSegment(mergedSegmentFileName, hashMapImportSegmentInitValCheckForMerging(fileNames[start: end]))<br>        <br>        // Delete the original data segments<br>        deleteSegments(fileNames[start: end])<br>        i = end<br>    }<br>}</pre><p>We’ll schedule the compress &amp; merge processes to run periodically in the background so that our data is organised neatly in more or less uniform segments without any garbage.</p><p>This can be done in Go using Go-routines &amp; channels with ticker.</p><pre>func CompressionAndMergingGoRoutine() {<br>    <br>    // create a ticker which receiver an event every 10s<br>    ticker: = time.NewTicker(10 * time.Second)<br>    for {<br>        select {<br>            case &lt;-ticker.C:<br>                <br>                // compress then merge whenever an event is received<br>                compress()<br>                merge()<br>        }<br>    }<br>}</pre><h3>Sparse Indexing</h3><p>The last problem that we are yet to solve is that our in-memory index stores all the keys, this is called dense indexing which needs large amount of in-memory storage.</p><blockquote>A <a href="https://www.javatpoint.com/indexing-in-dbms#:~:text=and%20Sparse%20index.-,Dense%20index,-The%20dense%20index">dense index</a> contains an index record for every key in the data file hence the number of records in the index table is same as the number of records in the entire data.</blockquote><p>The alternative to dense indexing is called sparse indexing.</p><blockquote>A <a href="https://www.javatpoint.com/indexing-in-dbms#:~:text=on%20the%20disk.-,Sparse%20index,-In%20the%20data">sparse index</a> contains index records only for a few items. Each index record points to a block of data. Thus, sparse index uses less memory as compared to a dense index.</blockquote><p>To implement sparse indexing in our database we can use <a href="https://www.geeksforgeeks.org/introduction-to-log-structured-merge-lsm-tree/">SSTables and LSM-Trees</a> but these concepts exceed the scope of this post.</p><p>In conclusion, diving into building a database engine offers insights into its workings. If you found this journey enlightening, consider showing support with some claps. Your appreciation fuels further exploration.</p><p>Thank you for joining me.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7c7996ddde84" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/how-to-craft-a-database-engine-7c7996ddde84">How to craft a database engine</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[All about DNS Hierarchy]]></title>
            <link>https://blog.devgenius.io/all-about-dns-hierarchy-36fabfcdc1f1?source=rss-6cd6e93cb39f------2</link>
            <guid isPermaLink="false">https://medium.com/p/36fabfcdc1f1</guid>
            <category><![CDATA[dns]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[how-internet-works]]></category>
            <category><![CDATA[systems-engineering]]></category>
            <category><![CDATA[internet]]></category>
            <dc:creator><![CDATA[Manthan chauhan]]></dc:creator>
            <pubDate>Fri, 19 Jun 2020 05:21:43 GMT</pubDate>
            <atom:updated>2022-08-14T07:46:09.445Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*cj1sOiA8p1aUXeac" /><figcaption>Photo by <a href="https://unsplash.com/@jordanharrison?utm_source=medium&amp;utm_medium=referral">Jordan Harrison</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Probably all of us know the fact that whenever we try to reach something.com, this “something.com” has to be converted into an IP address like “103.217.135.125” so that our browser, say Chrome, gets to know which server to contact.</p><p>In this post, we’ll be discussing how that conversion from “something.com” to “103.217.135.125” actually happens.</p><h3>DNS Cache</h3><p>So, you open any web browser say Chrome, and search for “docs.google.com”. As you already know, to show you the content at “docs.google.com”, your browser needs to know the IP address of the server, which serves the “docs.google.com” domain. At the very first step, your computer looks in the local (your own computer’s ) DNS cache to see if it already stores the IP address of “docs.google.com”. Whenever you try to reach a domain name, like “docs.google.com”, your computer finds the respective IP address through a DNS query which we’re gonna discuss, and stores the IP address in its <strong>local DNS cache</strong> for some predefined time period, after which it is removed. It is possible that you have visited “docs.google.com” in the near past and its IP address is available in the local cache, in that case, your browser will simply get the IP address from your local DNS cache, and we are done.</p><p>But, suppose the local cache doesn’t store the IP address of “docs.google.com”, what now? In that case, your computer will contact your <a href="https://whatismyipaddress.com/isp">ISP</a>’s <strong>Recursive DNS Resolver</strong>. The purpose of this DNS resolver is to get you the IP address of any domain, say, “docs.google.com”. If the DNS resolver already knows the answer in its own local cache (stored while serving another user of your ISP, or you, in the past), it’ll simply return the desired IP address to you. However, in the other case, it’ll perform a <strong>DNS query</strong> and get you the desired IP address.</p><blockquote>It is optional to use your ISP’s DNS resolver and you can always use any publically available DNS. Google’s DNS resolver can be used by setting DNS to “8.8.8.8” and secondary DNS to “8.8.4.4” in your network settings.</blockquote><h3>DNS Query</h3><p>When your ISP’s DNS resolver does not know the IP address associated with a domain, it makes a <strong>DNS query</strong> to the <strong>Authorative DNS server hierarchy</strong>. This DNS hierarchy will surely know the IP address associated with any domain available on the internet, because, each domain to be used by any organization, say Google, has to be registered with one of the Internet Registrars. Internet Registrars (like <a href="https://clarivate.com/markmonitor">MarkMonitor</a>), can be considered as ICANN accredited wholesalers of domain names, who communicate with the interested organization, like Google in this case, and get the appropriate <strong>DNS record</strong> into the desired <strong>TLD registry</strong>, through the registry operator (like <a href="https://en.wikipedia.org/wiki/Verisign">Verisign</a>). Now when the DNS record for google.com is in place, a DNS query can be made to get the desired IP address. In the rest of the post, we’ll understand how this DNS query works.</p><h4>Top Level Domains</h4><p>Any domain name like “docs.google.com” is made up of different components called domains, for example, “com”, “google” and “docs” are the constituent domains for “docs.google.com”. The rightmost domain (com) is the <strong>top-level</strong> domain, after that comes the <strong>secondary domain</strong> (google), and then comes the <strong>domain</strong> (docs). This structure can be extended infinitely with secondary subdomains, ternary subdomains, and so on, but since large domain names are difficult to remember, they lose the purpose, as remembering IP address might actually be easier in that case.</p><p>The top-level domains (or TLDs) can be divided into two groups, <strong>Country-code TLDs</strong> (or ccTLDs) and <strong>Generic TLDs</strong> (or gTLDs). ccTLDs are top-level domains which are reserved for a particular country, for example, .in(India), .uk(UK) or .jp(Japan). On the other hand, gTLDs are generic top-level domains, like, .com, .edu, .org, or .net, and can be used by anyone.</p><p>These top-level domains are globally maintained by the <strong>Internet Corporation for Assigned Names and Numbers</strong> <strong>(ICANN)</strong>. Each of these top-level domains has its own set of name servers which help in the DNS resolution. For example, a group of name servers is there to resolve “.com” domains <strong>only</strong>, while another group of name servers will resolve <strong>only</strong> “.org” domains.</p><blockquote>The set of available TLDs is not static, ICANN registers new namespaces periodically. Here you can find a <a href="https://data.iana.org/TLD/tlds-alpha-by-domain.txt">list of all available TLDs</a>.</blockquote><h4>Root Name Servers</h4><p>One level above these “top-level name servers” are <strong>Root Name servers</strong>. The sole purpose of these root name servers is to know, which top-level name servers can resolve a particular TLD say, “.com”, so that if someone contacts these root name servers to resolve “google.com” or “amazon.in”, the root name servers can direct them towards “.com” and “.in” name servers respectively. So, for resolving any domain name, the DNS resolver will contact one of the nearest root name servers and the following process will take place.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xC5nV5mVQup70VJOlYCPvA.png" /></figure><blockquote>There are more than 1000 root name servers, using only 13 address labels, placed at different locations across the globe. Each address label can be considered to be a pair of an IPv4 and an IPv6 address, and points to a cluster of root name servers sharing the label. These root name servers are managed by various organisations like NASA, US Army (Research Lab) and Internet Systems Consortium, Inc etc. Here is a list of the <a href="https://www.iana.org/domains/root/servers">13 root name server IPs</a>.</blockquote><h4>DNS Resolution</h4><p>For now, we can say that we’ve resolved the top-level domain and we know which server to ask for all the “.com” domains, do note that the process till now would be the same for all the “.com” domains, say “google.com”, “amazon.com” etc. Now we’ll see how to move further and resolve the secondary domain, which is “google” in our example “docs.google.com”. While ICANN manages the top-level domains, secondary domains are managed by the organizations which own them, for example, Google manages “google.com” while Amazon manages “amazon.com” &amp;“amazon.in”. Most organizations these days have their own secondary domain, unlike top-level domains which are shared among various organizations. Also, all the organizations will need to have a private or shared DNS, why? we’ll discuss it in a while.</p><p>Whenever an organization, for example, Google, wants to provide its services using a domain name say “google.com”, it has to register the domain with ICANN. We can say that after a legal process ICANN will register the Google name server’s IP address with all the “.com” name servers. After this registration, all the “.com” name servers will know the IP address of Google’s DNS (not “8.8.8.8” which is a DNS resolver) and hence the domain “google.com” or sub-domain “docs.google.com” can be resolved. The secondary domain will be resolved like this,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-CTP31aC4GDl2GN3bd0rxA.png" /></figure><blockquote>To use “google.in”, Google has to register with ICANN for “.in” name servers.</blockquote><p>Great!! so, while looking for “docs.google.com”, we’ve finally reached Google’s own domain name server (or DNS). Most organizations these days, within their ecosystem, manage a single root domain (“google.com”) and multiple sub-domains (“docs.google.com” or “mail.google.com”). The organization’s DNS will know the IP addresses associated with all these sub-domains, so the final step of our DNS resolution journey will be,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/884/1*w_d-chWvHik99KzlFuIJaw.png" /></figure><p>Now when the DNS resolver knows the IP address of “docs.google.com”, it’ll cache the same in its local memory for a predefined time period, called TTL (time to live), and then return the IP address to your computer. Note that, this TTL period is specified by the domain owner (Google, in the case of “docs.google.com”). Your computer will also save the IP address in its own local cache for the<strong> same</strong> TTL period. This way, if you frequently visit the same domain name, it’ll load a little faster as compared to other domain names which are rarely visited by any user.</p><p>I’ll end this already large post here, thank you for reading. Don’t forget to give some claps (out of <strong>50</strong>).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=36fabfcdc1f1" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/all-about-dns-hierarchy-36fabfcdc1f1">All about DNS Hierarchy</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Maximum Subarray Sum]]></title>
            <link>https://medium.com/@manthanchauhan913/maximum-subarray-sum-60d601a88b6e?source=rss-6cd6e93cb39f------2</link>
            <guid isPermaLink="false">https://medium.com/p/60d601a88b6e</guid>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[kadanes-algorithm]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[c-programming]]></category>
            <dc:creator><![CDATA[Manthan chauhan]]></dc:creator>
            <pubDate>Sun, 03 Mar 2019 09:00:08 GMT</pubDate>
            <atom:updated>2019-03-03T09:00:08.099Z</atom:updated>
            <content:encoded><![CDATA[<h4>Kadane’s Algorithm</h4><p>In this story, we will learn how to find the Maximum Subarray Sum using Kadane’s Algorithm. First of all, what is a subarray?</p><blockquote>A subarray is a contiguous part of an array. Or, an array that is inside a parent array. “<strong>Subarray sum”</strong> is the sum of all the elements of the subarray.</blockquote><blockquote>An array of length <strong>N </strong>will have <strong>N*(N+1)/2 </strong>non-empty subarrays.</blockquote><p>For example, let us suppose we have an array <strong><em>[1, 2, -3, 4]</em></strong>. The possible <strong>subarrays </strong>will be,<br><em>[], [1], [2], [-3], [4], [1, 2], [2, -3], [-3, 4], [1, 2, -3], [2, -3, 4] and [1, 2, -3, 4]</em><br>These subarrays will have the respective <strong>subarray-sums</strong>,<br><em>0, 1, 2, -3, 4, 3, -1, 1, 0, 3, 4<br></em>The subarray having the maximum sum will be called <strong>Maximum Sum Subarray</strong>.</p><blockquote>Let us denote a subarray containing the elements A[i], A[i + 1]……A[j-1] by <strong>A[i, j)</strong>.</blockquote><p>Having all the prerequisites, let us now discuss <strong>Kadane’s Algorithm </strong>to find the maximum sum a subarray can have.</p><h4>Understanding Kadane’s Algorithm</h4><p>Consider an array <strong>A</strong> of length <strong>n</strong>. Now consider a function <strong>M(i) </strong>which returns the maximum subarray-sum among all the subarrays ending at index <strong>i</strong>, ie.<strong> A[0, i)</strong>, <strong>A[1, i)</strong>, <strong>A[i-1, i)</strong> or <strong>A[i, i)</strong> etc. It should be noted that <strong>A[i, i)</strong> will not contain any element and hence it will be an empty subarray [].</p><p>Since all the subarrays of <strong>A</strong> must end at one of the indices, <em>0, 1, 2 …..n</em> of the array A. Hence <strong>maximum subarray sum</strong> will be <strong>max{M(0), M(1), M(2)…….M(n)}</strong>. It should be noted that,</p><blockquote>subarrays ending at index ‘<strong>i’</strong> are either empty or contain ‘<strong>A[i-1]’ </strong>for sure.</blockquote><p>Having acquired the complete information about the function <strong>M(i), </strong>Let us deduce an important relation. We know,</p><ol><li>Subarrays ending at index <strong>i</strong> are, <strong>A[0, i), A[1, i), A[2, i)………A[i, i)</strong>.</li><li>M(i) = <strong>max{sum{A[0, i)}, sum{A[1, i)}, sum{A[2, i)}……sum{A[i-1, i)}, sum{A[i, i)}}</strong></li><li>Or we can say, <br>M(i) = max{<strong>max{sum{A[0, i)}, sum{A[1, i)},…….sum{A[i-2, i)}sum{A[i-1, i)}}</strong>, <em>sum{(A[i, i))}</em>}</li><li>Notice that,<br>sum{A[0, i)} = sum{A[0, i-1)} + A[i-1]<br>sum{A[1, i)} = sum{A[1, i-1)} + A[i-1]<br>.<br>.<br>.<br>sum{A[i-1, i)} = sum{A[i-1, i-1)} + A[i-1]</li><li>Hence, <br>max{sum{A[0, <strong>i</strong>)}, sum{A[1, <strong>i</strong>)},…….sum{A[i-1, <strong>i</strong>)}}=<br>max{sum{A[0, <strong>i-1</strong>)}, sum{A[1, <strong>i-1</strong>)}………sum{A[i-1, <strong>i-1</strong>)}}<strong>+A[i-1]</strong></li><li>Using step 2 and 5, <br>max{sum{A[0, i)}, sum{A[1, i)},…….sum{A[i-1, i)}}= M(i-1)+A[i-1]</li><li>Substituting step 6 in step 3, <strong>M(i) = max {M(i-1) + A[i-1], 0}</strong></li></ol><p>Too much maths? Just remember that,</p><blockquote><strong>M(0) = 0 and M(i) = max {M(i-1) + A[i-1], 0} for 0 &lt; i ≤ N.</strong></blockquote><p>Having all the M(i)’s we just need to calculate their max. Let’s write the code to find <strong>maximum subarray sum </strong>using Kadane’s Algorithm.</p><ol><li>Create two integer variables, <strong>M_i</strong> and <strong>ans</strong>.</li><li>Since M(0)=0,<strong> initialize M_i with 0</strong>.<br>since minimum possible of M(i)’s is 0, <strong>initialize ans with 0</strong>.</li><li>Write a <strong>for </strong>loop for, <strong>i in range 1 to N</strong>.</li><li>Inside the for loop, write,<strong><br>find new M_i as max(M_i + A[i-1], 0)</strong><br><strong>if M_i &gt; ans, ans = M_i;</strong> //<em>finds max of all M(i)’s</em></li><li>Final value of <strong>ans</strong> will the <strong>maximum subarray sum</strong> for the given array A.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/683/1*wy6gpw0Elzh1rW3Dkh_sQg.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=60d601a88b6e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Loops N Lists:]]></title>
            <link>https://medium.com/@manthanchauhan913/loops-n-lists-5e803c3eaa1b?source=rss-6cd6e93cb39f------2</link>
            <guid isPermaLink="false">https://medium.com/p/5e803c3eaa1b</guid>
            <category><![CDATA[linked-lists]]></category>
            <category><![CDATA[python3]]></category>
            <category><![CDATA[floyd-cycle]]></category>
            <category><![CDATA[loop]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Manthan chauhan]]></dc:creator>
            <pubDate>Sun, 23 Sep 2018 08:29:57 GMT</pubDate>
            <atom:updated>2018-09-23T08:38:21.750Z</atom:updated>
            <content:encoded><![CDATA[<h4><strong>Working of the Floyd Cycle</strong></h4><p>The Aim of this story is to explain how to detect the presence of a loop in a linked list using the famous algorithm, “<strong>Floyd Cycle</strong>”. Observe the following figure,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4JsBtd1mAL-BnVLcdkH4Nw.jpeg" /></figure><p>The figure shows a linked list with length 8 and having a loop at the node <strong>N4</strong>. Let us introduce two pointers <strong>Fast </strong>and <strong>Slow </strong>both initially pointing to the <strong>Head </strong>of the linked list. The pointers <strong>Fast </strong>and <strong>Slow </strong>are simultaneously used to traverse the linked list. In one jump <strong>Fast moves forward by 2 nodes</strong> and <strong>slow moves forward by 1 node</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MEQRa-WR9EN4-dnkztIdPw.jpeg" /></figure><p>It is obvious that at some point in time each pointer will enter the loop and never come out. The idea behind Floyd Cycle is, once both the pointers are inside the loop they will surely meet after moving finite number of steps. Suppose that there are <strong>L</strong> nodes in the loop of a linked list. Obviously <strong>Fast</strong> will enter the loop before <strong>Slow</strong>. Suppose that at the moment Slow enters the loop, there are <strong>X</strong> nodes between <strong>Fast</strong> and <strong>Slow</strong>. After each step the distance between pointers increases by 1 node. Hence, after one more step there will be <strong>X+1</strong> nodes between <strong>Fast</strong> and <strong>Slow</strong>. Hence, after <strong>L-X-1</strong> steps there will be <strong>X+(L-X-1)=L-1</strong> nodes between <strong>Fast</strong> and <strong>Slow </strong>which is possible only when <strong>Slow</strong> and <strong>Fast</strong> coincide as shown.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wr-jX5fwfCmrxOE00HS33A.jpeg" /></figure><p>Let us now write the code to detect loop in a linked list using Floyd Cycle.</p><ol><li>Create a function <strong>floydCycle()</strong> which will take the <strong>head </strong>of the linked list as it’s only argument and return <strong>true, </strong>if loop exists or <strong>false, </strong>if loop doesn’t exits in the linked list.</li><li>Now, in the function body, create two <strong>Node </strong>pointers <strong>Fast</strong> and <strong>Slow</strong> both initialized to the <strong>head</strong> of the linked list.</li><li>Create an infinite <strong>while </strong>loop and add two <strong>if-return </strong>statements in it as,<br><strong>a)</strong> if <strong>Fast-&gt; next </strong>or <strong>Fast-&gt;next-&gt;next </strong>does not exists, <strong>return false</strong>. This is to detect the <strong>end</strong> of the linked list.<br><strong>b) </strong>if <strong>Fast </strong>is equal to <strong>Slow,</strong> and<strong> Fast</strong> is not equal to <strong>head</strong>, <strong>return true</strong>. This detects loop taking care of the fact that both pointers are initialized to <strong>head</strong>.</li><li>To move the pointers, add these two statements in the <strong>while </strong>loop,<br><strong>Slow</strong>=<strong>Slow</strong>-&gt;<strong>next</strong>; (jump by 1)<br><strong>Fast=Fast</strong>-&gt;<strong>next</strong>-&gt;<strong>next</strong>; (jump by 2)</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/666/1*1HOC4v6edTXiTuKcsPElBA.png" /><figcaption><strong>Code for Floyd Cycle in Python 3.</strong></figcaption></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5e803c3eaa1b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[‘L’ length cycles:]]></title>
            <link>https://medium.com/@manthanchauhan913/l-length-cycles-31f9e0d86487?source=rss-6cd6e93cb39f------2</link>
            <guid isPermaLink="false">https://medium.com/p/31f9e0d86487</guid>
            <category><![CDATA[cycle]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[Manthan chauhan]]></dc:creator>
            <pubDate>Sat, 04 Aug 2018 03:51:39 GMT</pubDate>
            <atom:updated>2018-08-14T10:50:46.410Z</atom:updated>
            <content:encoded><![CDATA[<h4>Finding the number of ‘<strong>L’ </strong>length cycles in an undirected graph</h4><p>The task of finding the total number of squares, pentagons or any other geometric figure in an undirected graph might seem difficult to lots of people. But they have huge significance in real world networks like internet or feedback mechanisms. After reading this post the reader will be able to accomplish this task easily and efficiently. Without further delay let’s jump right into the solution.</p><p>Each of the above described geometrical figure is a subset of “<strong>L </strong>length cycles”. A <strong>L </strong>length cycle is just a path consisting of <strong>L </strong>edges, which begins from a vertex <strong>V </strong>and ends at the same vertex <strong>V</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dIIPlOPO2XY-FPUJ0JhfRw.jpeg" /></figure><p>Let us break down our task into smaller steps and find the number of only those <strong>L </strong>length cycles which contain a vertex <strong>V1</strong>. A <strong>L </strong>length cycle which contains the vertex <strong>V1 </strong>can be viewed as a path of length <strong>L </strong>which originates from <strong>V1</strong> and ends at <strong>V1</strong>. But wait, two such paths represent a single cycle as shown in the figure below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4Sx78lEnXeVvDpC2svgqag.jpeg" /><figcaption>As shown in above figure, path V1-A-B-C-D-V1 and path V1-D-C-B-A-V1 represent a common cycle.</figcaption></figure><p>Let us say that <strong>p</strong>(<strong>V1</strong>, <strong>V2</strong>, <strong>L</strong>) represents path from <strong>V1 </strong>to <strong>V2 </strong>and having length <strong>L</strong>. So currently we are looking for total number of paths <strong>p</strong>(<strong>V1</strong>, <strong>V1</strong>, <strong>L</strong>). Suppose that <strong>V1 </strong>has neighbors <strong>N1</strong>, <strong>N2 </strong>and <strong>N3</strong>. Then,</p><blockquote>Number of paths <strong>p</strong>(<strong>V1</strong>, <strong>V1</strong>, <strong>L</strong>)= Number of paths <strong>p</strong>(<strong>N1</strong>, <strong>V1</strong>, <strong>L</strong>-1)+ Number of paths <strong>p</strong>(<strong>N2</strong>, <strong>V1</strong>, <strong>L</strong>-1)+ Number of paths <strong>p</strong>(<strong>N3</strong>, <strong>V1</strong>, <strong>L</strong>-1)</blockquote><p>If <strong>N1</strong> has neighbors <strong>N11</strong> and <strong>N12</strong> then,</p><blockquote>Number of paths <strong>p</strong>(<strong>N1</strong>, <strong>V1</strong>, <strong>L</strong>-1)= Number of paths <strong>p</strong>(<strong>N11</strong>, <strong>V1</strong>, <strong>L</strong>-2)+ Number of path <strong>p</strong>(<strong>N12</strong>, <strong>V1</strong>, <strong>L</strong>-2)</blockquote><p>Can you can smell the presence of recursion? See the function below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/828/1*ztSxYpEfjRALyP6L2gyFgQ.png" /><figcaption>2 * total number of <strong>L</strong> length cycles containing <strong>V1</strong> = <strong>paths(</strong>graph, n, <strong>V1</strong>, <strong>V1</strong>, <strong>L</strong>, traversed<strong>)</strong></figcaption></figure><p>Confused why resetting <strong>traversed[src] </strong>to<strong> false </strong>in line 22? If we exclude this statement, each node will be traversed only once and after that it will be marked as <strong>traversed</strong>. Consider the last graph again, after traversing the given cycle, vertices <strong>A</strong>, <strong>B</strong>, <strong>C </strong>and <strong>D </strong>would be marked as traversed. Hence, any other cycle in the graph containing one or more of these vertices will be discarded.</p><p>So most of our work is complete after writing the function <strong>paths()</strong>. Let cycles(v, l) = paths(graph, n, v, v, l, traversed) / 2. Note that,</p><blockquote>Total number of <strong>L </strong>length cycles is <strong>not equal </strong>to cycles(V1, L) + cycles(V2, L) + cycles(V3, L) + ……………+ cycles(Vn, L).</blockquote><p>Because any <strong>L</strong> length cycle of vertices <strong>V1</strong>, <strong>V2</strong>…….<strong>Vl</strong> will be considered <strong>L</strong> times. Once in each cycles(<strong>Vi</strong>, <strong>L</strong>) for i = 1, 2, 3….l. For further clarification consider the graph below and calculate number of 4 length cycles.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xXezzHooHdCjnHwt_odD-Q.jpeg" /></figure><p>Suppose we start from <strong>1 </strong>then,<br>cycles(1, 4) = 1<br>cycles(2, 4) = 2<br>cycles(3, 4) = 1<br>cycles(4, 4) = 1<br>Hence, cycle 1–2–3–4–1 is considered 4 times. Therefore,</p><blockquote>Total number of <strong>L </strong>length cycles = cycles containing <strong>V1</strong> + cycles containing <strong>V2</strong> but not <strong>V1 </strong>+ cycles containing <strong>V3 </strong>but neither V1 nor V2 +……….</blockquote><p>So once we calculate the number of cycles containing a vertex <strong>V</strong>, we should avoid <strong>V </strong>while calculating number of cycles containing other vertices. To avoid a vertex permanently, set traversed[<strong>V</strong>] = <strong>true </strong>permanently. The following function calculates the total number of <strong>L</strong> length cycles in an undirected graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/821/1*ocAMxiAOYQYL4KtPhMeR2A.png" /><figcaption>Total number of <strong>L</strong> length cycles = <strong>countcycles</strong>(graph, n, <strong>L</strong>)</figcaption></figure><blockquote>The algorithm is greedy and has a worst case time complexity of O(N^L). Worst case being the case of a complete graph.</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=31f9e0d86487" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Bipartition: Detecting Odd Length Cycles in Graphs]]></title>
            <link>https://medium.com/@manthanchauhan913/bipartition-detecting-odd-length-cycles-in-graphs-699d1b25ffab?source=rss-6cd6e93cb39f------2</link>
            <guid isPermaLink="false">https://medium.com/p/699d1b25ffab</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[Manthan chauhan]]></dc:creator>
            <pubDate>Tue, 17 Jul 2018 01:27:14 GMT</pubDate>
            <atom:updated>2018-07-17T01:27:14.163Z</atom:updated>
            <content:encoded><![CDATA[<p>A bipartite graph is a graph whose vertices can be divided into two disjoint sets A and B such that <strong>every edge of the graph connects a vertex in set A to a vertex in set B, no edge connects the vertices of the same set</strong>. Let’s see how we can perform the Bipartition of a graph.</p><ol><li>Chose any vertex of the graph as starting vertex and assign it to any set A or B(say A).</li><li>Now, all the neighbors of the starting node should belong to set B. Because, every edge connects the vertices of different sets.</li><li>Similarly, moving in a Breadth First manner, the neighbors of the nodes which were assigned to set B in step 2 should belong to set A.</li><li>After all the connected vertices have been traversed, we are left with three groups of vertices, vertices belonging to set A, vertices belonging to set B and disconnected vertices.</li><li>Any set can be assigned to any of the disconnected vertex as it won’t affect the property that every edge of the graph connects two vertices of different sets.</li><li>Now, the two sets A and B represent the bipartition of the graph.</li></ol><p>If the two sets represent two colors, a Bipartite Graph will look like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1LzjNNtHstcmNf7NRpjbBg.jpeg" /><figcaption>Note that every edge connects two vertices of two different colors.</figcaption></figure><p>Now, what is the relation between bipartition and odd length cycles?<br>Bipartite graphs do not contain odd length cycles, or graphs with odd length cycles are not bipartite. Let us see why.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/968/1*klMak1u1w7RaPreJ9TlLVg.jpeg" /><figcaption>An odd length cycle, part of a bigger graph.</figcaption></figure><p>Suppose that while performing the bipartition of the graph, vertex 1 is assigned set A. It means that vertices 2 and 3 should be assigned set 2. But the vertices 2 and 3 are connected and hence cannot be assigned the same set. No matter what vertex among the three you start with, it is impossible to obtain the bipartition of such a graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/806/1*Nm97eveCfBHRTHJQkitpmw.jpeg" /><figcaption>Another non-bipartite graph, notice the presence of odd length cycle</figcaption></figure><blockquote>Thus, we conclude that bipartite graphs do not contain odd length cycles.</blockquote><p>But is the converse also true? Do all non-bipartite graphs contain odd length cycles? YES. Here is the proof.</p><p>In any bipartite graph, all the nodes at odd distances from the starting vertex belong to the same set (say set A). And, all the nodes at even distances from the starting vertex also belong to the same set (say set B).</p><p>If a graph is surely non-bipartite, there must be at least one edge connecting two nodes either both of set A, or both of set B. Which means there must be at least one edge connecting either two vertices of odd distance from starting vertex, or two vertices of even distance from starting vertex.</p><p>Let us say that one edge connects two vertices each having an even distance form starting vertex. Then, the length of the cycle including the starting vertex and the two vertices will be, Even + Even + 1 = odd. Thus we have an odd length cycle. A similar proof can be constructed using two vertices, each having an odd distance from starting vertex. Thus,</p><blockquote>Every non-bipartite graph contains at least one odd length cycle.</blockquote><p>Hence,</p><blockquote>If a graph is bipartite it doesn’t contains any odd length cycles, but, if a graph is non-bipartite it surely contains at least one odd length cycle.</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=699d1b25ffab" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>