<?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 Amit Davidson on Medium]]></title>
        <description><![CDATA[Stories by Amit Davidson on Medium]]></description>
        <link>https://medium.com/@amitdavidson234?source=rss-9269be8f37e4------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*a0mlM0qyBHBlYrugdrAuEQ.jpeg</url>
            <title>Stories by Amit Davidson on Medium</title>
            <link>https://medium.com/@amitdavidson234?source=rss-9269be8f37e4------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 14:32:01 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@amitdavidson234/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[Shamir’s Secret Sharing Algorithm: Principles and Blockchain Applications]]></title>
            <link>https://medium.com/coinmonks/shamirs-secret-sharing-algorithm-principles-and-blockchain-applications-175a0ee71d69?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/175a0ee71d69</guid>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[crypto]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Sat, 12 Jul 2025 14:41:47 GMT</pubDate>
            <atom:updated>2025-08-15T15:32:16.274Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="Nuclear launch codes (often called the “Gold Codes”) are also split" src="https://cdn-images-1.medium.com/max/634/0*D39fD7OqsP8CLCbv.jpg" /><figcaption>Nuclear launch codes (often called the “Gold Codes”) are also split</figcaption></figure><h3>Introduction</h3><p>Shamir’s Secret Sharing (SSS) is a cryptographic scheme invented by Adi Shamir in 1979 to solve the problem of safeguarding a secret without a single point of failure. It allows a <strong>secret</strong> (e.g. a password, private key, or vault code) to be split into multiple parts called <strong>shares</strong>, which are distributed to different participants or locations. The critical property is that only when a sufficient number of these shares are combined (reaching a predetermined <strong>threshold</strong>) can the original secret be reconstructed. Any group with fewer than the threshold number of shares learns nothing useful about the secret. In essence, SSS ensures that no single person or small colluding group can compromise the secret — a minimum quorum is required to unlock it.</p><p><strong>Key properties of Shamir’s <em>(k,n)</em> secret-sharing scheme</strong> (where <em>n</em> shares are created and <em>k</em> is the threshold to reconstruct):</p><ul><li><strong>Threshold requirement:</strong> Any <em>k </em>or more shares together can fully reconstruct the secret. In other words, the secret can be recovered from <em>any</em> combination of <em>k</em> shares.</li><li><strong>Perfect secrecy:</strong> Any <em>k-1</em> or fewer shares provide <strong>no information</strong> about the secret. Even an attacker who steals some shares (below the threshold) is no closer to guessing the secret than someone with zero shares.</li></ul><p>This means the scheme is <em>information-theoretically secure</em> — knowledge below the threshold doesn’t just make it hard to get the secret; it gives <strong>zero advantage</strong>. Each share by itself appears random and “useless” without enough other pieces to decode it. By distributing trust among multiple people or devices, SSS eliminates single points of failure: no single person, device, or location holds the entire secret. This guards against theft, loss, or misuse by any one party, a critical benefit for sensitive data like cryptographic keys.</p><h3>How Shamir’s Secret Sharing Works</h3><p>At its core, Shamir’s scheme relies on the mathematics of <strong>polynomial interpolation</strong> over a finite field. The key insight is that a polynomial of degree <em>k-1</em> is uniquely determined by <em>k</em> points, but with fewer than <em>k</em> points the polynomial (and its missing values) is <em>underdetermined</em>. In practical terms, this means: with enough shares (points) you can solve for the secret, but with too few shares, the secret could literally be anything consistent with those few points. Shamir’s algorithm uses this property to encode the secret in a polynomial so that any <em>k</em> shares reveal the one true secret, while any fewer shares are compatible with infinitely many possible secrets.</p><p><em>Illustration:</em> If a secret is encoded in a polynomial of degree 2 (meaning a 3-share threshold scheme), any 2 shares (points) are insufficient to pinpoint the secret. In fact, infinitely many distinct quadratic curves can pass through the same two points, each corresponding to a different possible secret value (the polynomial’s intercept). Only when a third point (share) is available is the polynomial uniquely determined, allowing the secret to be recovered. Thus, <strong>no unique secret can be derived from only 2 shares when 3 are required</strong>, reflecting perfect secrecy.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/0*7ITin6RM0G1__-lX.png" /><figcaption>One can draw an infinite number of polynomials of degree 2 through 2 points. 3 points are required to uniquely determine a polynomial of degree 2. This image is for illustration purposes only — Shamir’s scheme uses polynomials over a finite field, which are not easy to represent in a 2-dimensional plane.</figcaption></figure><p><strong>Secret sharing via polynomial:</strong> To actually implement this, we work over a finite field (usually integers modulo a large prime <em>q</em>) to keep values bounded and secure. Suppose we have a secret number <em>S</em> (for example, a big integer representing an encryption key). We choose parameters <em>n</em> (total shares) and <em>k</em> (threshold). The steps are:</p><ol><li><strong>Form a random polynomial:</strong> Pick a random polynomial <em>f(x)</em> of degree <em>k-1</em> such that <em>f(0) = S </em>This is done by choosing <em>k-1</em> random coefficients <em>a</em>₁, a₂, …, <em>a</em>ₖ₋₁ in a finite field (e.g. integers mod <em>q</em>), and setting <em>a</em>₀<em> = S</em> where <em>S</em> is the secret (constant term). All arithmetic is done modulo <em>q</em> (with <em>q</em> larger than to allow <em>n</em> distinct points). The random coefficients ensure that different share sets will be generated each time even for the same secret, and that no subset of fewer than <em>k</em> points yields information about <em>a</em>₀.</li><li><strong>Splitting the secret to shares:</strong> Evaluate the polynomial at <em>n</em> distinct, non-zero points <em>x=1,2…n</em>. Each participant is given the pair <em>(x,f(x))</em> as their <strong>share</strong>. Importantly, we do <strong>not</strong> give out <em>f(0)</em> since that is the secret itself. Now each share looks like random data — <em>f(x)</em> — and by itself reveals nothing about <em>S</em> due to the random polynomial components.</li><li><strong>Reconstructing the secret:</strong> Given <strong>any k shares</strong> <em>(x</em>₁<em>, f(x</em>₁<em>)), (x</em>₂<em>,f(x</em>₂<em>)), …, (x</em>ₙ<em>,f(x</em>ₙ<em>))</em> one can recover <em>f</em> — in particular <em>f(0)</em> — using polynomial interpolation. We know <em>f(x)</em> is a polynomial of degree <em>k-1</em>, so <em>k</em> points determine it exactly. One straightforward method is Lagrange interpolation, which provides a formula to compute <em>f(0)</em> from the <em>k</em> known points. I’m not going to over Lagrange interpolation as it’s technical but you can find the formula on <a href="https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing#Mathematical_formulation">wikipedia</a>.</li></ol><p>If fewer than <em>k</em> shares are available, any attempt at interpolation yields infinitely many solutions — there isn’t enough information to pin down <em>f(0).</em> This is the mathematical underpinning of SSS’s security: <em>no unique secret can be determined without the threshold number of shares</em>. Even someone holding multiple shares below the threshold (say <em>k-1</em> shares) cannot derive the secret or even reduce its uncertainty. Thus, the secret remains completely undetermined (uniformly random from the attacker’s perspective) until the threshold is met.</p><h3>Example: 3-out-of-6 Secret Sharing</h3><p>Let’s walk through a concrete example to solidify how SSS works. Suppose our secret is S = 1234 (Think of this as a secret number that could represent something like a private key. Essentially everything can be encoded into a number using UTF-8 or any other encoding method). We decide on a threshold of <em>k = 3</em> and will generate <em>n = 6 shares</em> in total. That means any 3 shares can reconstruct the secret, but 1 or 2 shares cannot.</p><ul><li><strong>Polynomial selection:</strong> Because <em>k-1 = 2</em>, we need a random quadratic polynomial. We set the constant term <em>a</em>₀= 1234 (the secret). Now we pick two random coefficients: say <em>a</em>₁<em>= 166</em> and a₂<em>= 94</em> (these would typically be random mod <em>q</em>, but for this illustrative example we’ll use small integers). This yields the polynomial: <em>f(x) = 1234 + 166x + 94x². </em>Here <em>f(0)=1234</em> is our secret.</li><li><strong>Generating shares:</strong> We compute <em>f(x)</em> for <em>x=1</em> through <em>6</em> to get six share points:<br><em>– f(1) = 1234 + 166(1) + 94(1) = 1494<br>– f(2) = 1234 + 166(2) + 94(4) = 1942<br>– f(3) = 1234 + 166(3) + 94(9) = 2578<br>– f(4) = 1234 + 166(4) + 94(16) = 3402<br>– f(5) = 1234 + 166(5) + 94(25) = 4414<br>– f(6) = 1234 + 166(6) + 94(36) = 5614</em></li><li>So the six shares distributed to participants are the pairs:<br><em>(1, 1494), (2, 1942), (3, 2578), (4, 3402), (5, 4414), (6, 5614)</em>. Each participant gets a unique share. By design, any two of these shares are not enough to recover <em>1234</em>— there are infinitely many quadratics through any two points, as illustrated earlier. But any three shares will let us solve for the polynomial and find the secret.</li><li><strong>Reconstructing the secret:</strong> Now imagine down the line, three of the share-holders come together to recover the secret. Suppose we have shares at <em>x=2,4,5</em> which are <em>(2, 1942), (4, 3402), (5, 4414)</em>. Using those three points, we set up the Lagrange interpolation to determine <em>f</em>. Without going into all algebra here, the interpolation will find the unique quadratic <em>f(x) = 1234 + 166x + 94x²</em> that fits those points. Evaluating this polynomial at <em>x=0</em> indeed gives <em>f(0) = 1234</em>. Thus, the secret is recovered correctly. Any other trio of shares would yield the same result. For example, if we took <em>(1,1494), (3,2578), (6,5614)</em>, we would find the same <em>f(0) = 1234</em> after interpolation (you can verify this as an exercise).</li></ul><p>If only two shares were available say <em>(1,1494)</em> and <em>(2,1942)</em> and no third, the equations would be underdetermined — there would be many possible values for <em>S</em> consistent with those two points. In fact, an eavesdropper with those two points could try to solve for <em>S</em> but would find that <em>S</em> could be any number.</p><h3>Uses in Blockchain and Key Management</h3><p>Shamir’s Secret Sharing has important applications in cryptocurrency and blockchain security, particularly for managing private keys and other sensitive secrets. A blockchain private key (or a wallet’s recovery seed phrase) is essentially the “master secret” that controls access to funds — losing it means loss of funds, and having it stolen means someone can abscond with your assets. SSS provides a way to <strong>back up a private key and distribute its shares among multiple parties</strong> such that no single party holds the complete key, yet the rightful owner can still recover it when needed. This helps address two major concerns in crypto key management: theft and loss.</p><p><strong>Secure key backup:</strong> In personal crypto wallet backups, Shamir’s scheme can split a recovery seed phrase into multiple shares to be stored in different places or entrusted to different people. If one share is lost, you can still recover your funds with the remaining two; and if one share is stolen, the thief gets nothing useful without a second share. In a <strong>2-of-3 Shamir backup</strong> scheme, any two shares reconstruct the wallet, but a single share on its own is useless — your assets remain secure. This dramatically reduces the risk of a single point of failure compared to keeping one seed phrase written on paper (which could be lost or taken). Even in the case of disaster or forgetfulness, as long as the threshold number of shares survive, the owner can restore the wallet. Crypto industry experts consider SSS-based backups a robust way to safeguard recovery keys against both accidents and attacks.</p><p><strong>Caution:</strong> One should note that when using SSS for operational keys (not just backups), the secret <strong>does get reconstructed</strong> when used — meaning there must be a secure process or device where shares are combined to produce the private key for signing a transaction, for example. That moment requires high security (often a dedicated hardware device) because the full key exists at reconstruction time. In contrast, advanced techniques like MPC can perform cryptographic operations without ever assembling the full key in one place. Still, for many purposes like key backup, Shamir’s scheme provides a straightforward and time-tested solution. It does not rely on any special hardware or trusted third-party — its security comes purely from math and the honesty of a threshold of participants.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=175a0ee71d69" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/shamirs-secret-sharing-algorithm-principles-and-blockchain-applications-175a0ee71d69">Shamir’s Secret Sharing Algorithm: Principles and Blockchain Applications</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Permissioned vs Permissionless Blockchains: Lessons from Ethereum and Hyperledger]]></title>
            <link>https://itnext.io/permissioned-vs-permissionless-blockchains-lessons-from-ethereum-and-hyperledger-2b55cf9c892f?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/2b55cf9c892f</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[blockchain-technology]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[bitcoin]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Sat, 05 Jul 2025 14:41:41 GMT</pubDate>
            <atom:updated>2025-07-06T22:59:14.119Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/768/0*hYUlc_SonXls2OYk.png" /></figure><p>When I first dove into blockchain development, I assumed every blockchain was like Bitcoin — open to anyone, anonymous, and running “magic internet money.” It turned out that not all blockchains play by the same rules. In fact, there are <strong>permissionless blockchains</strong> (open to everyone, like Bitcoin or Ethereum) and <strong>permissioned blockchains</strong> (restricted access, often used by businesses, like Hyperledger Fabric).</p><h3>What is a Permissionless Blockchain? (Ethereum’s World)</h3><p>A <strong>permissionless blockchain</strong> is a public network that <em>anyone</em> can join and participate in. No one grants you access — you just create an account (often just a cryptographic keypair) and you’re in. For example, <strong>Ethereum</strong> is a permissionless blockchain: it’s a <em>borderless, trustless, decentralized public network</em> that anyone can access, validate, and build on. You don’t need to reveal your real identity or get approval from an authority. In these networks, users are usually pseudonymous — known only by their addresses (random-looking strings) rather than personal info. This anonymity (or pseudo-anonymity) is a key feature.</p><p>Because nobody trusts anybody in a global open network, permissionless blockchains use technical tricks to secure the system. They rely on <strong>consensus mechanisms</strong> like Proof of Work or Proof of Stake to validate transactions. These mechanisms reward participants (with cryptocurrency) for doing the heavy lifting of securing the network. For instance, Ethereum (which started with Proof of Work and now uses Proof of Stake) incentivizes miners or stakers with Ether, its native coin, to keep the network honest. The design is <em>trustless</em> — you don’t have to trust other participants, just the code and consensus rules. The upside is strong security and decentralization: no single company controls Ethereum, and it’s resilient because thousands of independent nodes validate everything.</p><p>However, the open nature of permissionless blockchains has trade-offs. They can be slower and less scalable. Ethereum’s global network (in its early days) could handle only ~15 transactions per second, and transaction fees spiked when the network got busy. (Innovations like Layer 2 networks are improving this, but the point remains that open networks sacrifice some speed for decentralization.) Also, everything on a public chain is transparent. That’s great for openness, but not ideal if you’re, say, a business that doesn’t want its transactions visible to the whole world.</p><p>To summarize, permissionless blockchains like Ethereum are the wild open plains of the blockchain world — <strong>anyone can ride</strong>. They are public, <strong>decentralized networks</strong> where participants remain anonymous or pseudonymous, and no central authority is in charge. This makes them powerful for use cases like decentralized finance (DeFi), NFTs, open-source projects, and public digital money. I love the freedom they offer: when I deploy a DApp on Ethereum, I know <em>anyone</em> from anywhere can interact with it without asking permission.</p><h3>What is a Permissioned Blockchain? (Hyperledger’s World)</h3><p>In contrast, a <strong>permissioned blockchain</strong> is more like an exclusive club — you need an invitation or credentials to join. These blockchains aren’t free-for-all; participants are <em>known and vetted</em>. <strong>Hyperledger Fabric</strong> is a prime example of a permissioned blockchain platform. It’s designed for enterprise and business use, where a group of known organizations might want to share data on a ledger <strong>but with privacy, security, and access control in place</strong>.</p><p>In Fabric’s world, every participant is issued an identity by a Membership Service — basically a digital certificate proving who they are. Only approved members (like companies or specific individuals) can run the nodes and validate transactions. The data on the network can be restricted so that only the relevant parties see certain transactions. For instance, two banks transacting on a Fabric network can keep their deal confidential, visible only to them, and not to other network members. This <em>privacy</em> and fine-grained control is a big draw for permissioned ledgers.</p><p>Another key difference is that permissioned blockchains <strong>often don’t need a cryptocurrency</strong> to function. Hyperledger Fabric doesn’t have a native coin like Ether — and it doesn’t require mining or token staking for security. Why? Because if only known parties are participating, you don’t need to bribe strangers with tokens to behave. You can use more traditional and efficient consensus methods (like voting or rotating leadership among known nodes) to agree on the ledger state. Fabric, for example, can use protocols like RAFT or PBFT (Practical Byzantine Fault Tolerance) to quickly reach consensus in a closed group of nodes, rather than burning electricity on proof-of-work. In plain terms, a permissioned network trades the extreme trustlessness of public chains for a bit of <strong>real-world trust</strong> — since members are vetted, you assume they won’t all be bad actors, and if someone misbehaves, you can identify them and kick them out if needed.</p><p>Industries like finance, supply chain, healthcare, and governments are drawn to permissioned blockchains because they can enforce rules, privacy, and compliance. For example, in a supply chain built on Fabric, only the companies involved (manufacturer, shipper, retailer, etc.) have nodes on the network, and they can tightly control who sees which data. This controlled approach wouldn’t be possible on a fully public chain where <em>everything</em> is transparent.</p><p>In short, permissioned blockchains like Hyperledger Fabric are the <strong>gated communities</strong> of the blockchain world. They’re <strong>private or consortium networks</strong>, where <strong>participants must be approved</strong> and are usually identified (no anonymous users). They prioritize privacy, speed, and governance at the expense of the open participation that public chains celebrate.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2b55cf9c892f" width="1" height="1" alt=""><hr><p><a href="https://itnext.io/permissioned-vs-permissionless-blockchains-lessons-from-ethereum-and-hyperledger-2b55cf9c892f">Permissioned vs Permissionless Blockchains: Lessons from Ethereum and Hyperledger</a> was originally published in <a href="https://itnext.io/">ITNEXT</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[UTXO vs. Account-Based Blockchains: A Clear Comparison]]></title>
            <link>https://itnext.io/utxo-vs-account-based-blockchains-a-clear-comparison-963872e5a6ea?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/963872e5a6ea</guid>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[crypto]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Sat, 28 Jun 2025 15:51:56 GMT</pubDate>
            <atom:updated>2025-06-29T10:05:10.764Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*UcY9PmMeZrhcsjqV" /></figure><p>Imagine two friends settling a lunch bill: one pulls out cash from their wallet and makes change, while the other opens a banking app to transfer money. These approaches mirror the two fundamental ways blockchain networks track value: the UTXO model and the account-based model. Each model originates from a different blockchain paradigm (Bitcoin vs. Ethereum) and comes with unique structures and behaviors. In this article, we’ll explain what UTXOs and account-based systems are, highlight how they differ in design and functionality, and explore the pros, cons, and ideal use cases for each. We’ll avoid heavy jargon and use real-world examples (like cash versus bank accounts) to keep things accessible to a general tech reader.</p><p>For instance, consider a marketplace analogy. In one corner, traders use the UTXO system — each trader carries a sack of “coins” (say gemstones) of specific values, and whenever they buy something they hand over certain gems whose total equals or exceeds the price, receiving new gemstones as <strong>change</strong> for any excess. On the other side, traders use an account-based system — instead of juggling individual coins, each trader has an account balance recorded in a ledger, and when a purchase is made the ledger simply deducts the amount from the buyer’s account and credits it to the seller’s, much like a bank updating balances after a transfer. This story illustrates, in a nutshell, how UTXO-based blockchains operate more like cash, whereas account-based blockchains operate more like bank accounts.</p><h3>The Account-Based Model</h3><p>The account-based model takes a more straightforward, <em>bank-like</em> approach. In an account-based blockchain, the state of the ledger is a set of accounts, each with a current balance. Transactions directly modify these balances by subtraction and addition, rather than shuffling around coin units. This model was popularized by Ethereum in 2015 and is used by many modern smart contract platforms.</p><p><strong>How Account Transactions Work:</strong> If Alice wants to send 3 tokens to Bob using an account-based system, the blockchain will deduct 3 from Alice’s account balance and credit 3 to Bob’s account balance. There is no need to pick specific “coins” to spend or make change, as in the UTXO model. Any fraction of an account balance can be sent, as long as the sender has enough to cover the amount. The ledger’s global state is then updated to reflect the new balances. This design is similar to a bank ledger that records debits and credits: when Alice transfers $100 to Bob via online banking, her account is debited $100 and Bob’s is credited $100, with the bank keeping track of each account’s total. Likewise, in Ethereum and other account-model chains, each address (account) has a balance that increases with incoming transactions and decreases with outgoing ones.</p><p>One consequence of the account model is that <strong>each user (address) is typically tied to a single account identity</strong> on the chain. All of Alice’s activity might occur through one account address that accumulates and spends funds over time. This is convenient — users don’t have to manage multiple outputs or addresses — and it enables direct interaction with smart contracts that also have their own account addresses and balances. The account model’s simplicity in updating a single shared state (balances table) makes it well-suited for complex applications. In fact, it’s considered more <em>developer-friendly</em> for building decentralized apps: maintaining and querying an account’s state is easier than handling numerous UTXOs. Ethereum’s design leverages this, allowing smart contracts to store variables and track state within accounts. As a result, <strong>programmability</strong> is a strong suit of account-based systems — but as we’ll see, this comes with other trade-offs.</p><h3>The UTXO Model (Unspent Transaction Outputs)</h3><p>In a UTXO-based blockchain, there are no long-lived account balances at the protocol level — instead, the system tracks <em>coins</em> as discrete units called <strong>unspent transaction outputs (UTXOs)</strong>. Each UTXO is a chunk of cryptocurrency (an “output” from a prior transaction) that has not yet been spent and thus can be used as input in a future transaction. When you own bitcoins, for example, what you really control are one or more UTXOs associated with your addresses (each UTXO has a value, like 0.5 BTC, 1.2 BTC, etc.). Your wallet software sums these UTXOs to display your total balance, but the blockchain itself treats them individually.</p><p><strong>How UTXO Transactions Work:</strong> A transaction in the UTXO model consumes some of your UTXOs and creates new UTXOs in their place. <em>You must spend UTXOs in whole units.</em> If a UTXO’s value exceeds what you need to pay, the transaction will send the required amount to the recipient and return the leftover “change” to you as a new UTXO. For example, if Bob wants to pay 10 tokens but he only has a single UTXO worth 20 tokens, he will spend that 20-token output entirely — 10 tokens go to the payee, and the remaining 10 tokens come back to Bob as change (a new UTXO he controls). This is analogous to using a $20 bill to buy a $10 item and getting $10 back in cash change. If the amount owed exactly matches your UTXO values, no change output is needed; otherwise, making change is an inherent part of UTXO transactions.</p><p>Critically, each UTXO can be <strong>spent only once</strong>. Once it’s used as an input in a transaction, it is considered consumed and cannot be reused, just like you can’t spend the same physical coin twice. The blockchain validates every transaction to ensure that all inputs were unspent (preventing double-spending) and that the total value of inputs <strong>equals</strong> the total value of outputs (including change). This input-output balance keeps the ledger consistent and auditable. Notably, there is no central account tally — the <strong>network does not track balances by identity</strong>. Instead, ownership is determined by who holds the private keys to unlock specific UTXOs. In fact, UTXO blockchains like Bitcoin have <strong>no concept of a personal account balance</strong> at the protocol level; the ledger just records UTXOs tied to addresses, and a user’s “balance” is the sum of all unspent outputs they control. This means identity is abstracted: if you control the keys for a given address’s outputs, you control those funds, regardless of who you are.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DmJvKcBGY1QDv3CZ6PLewQ.png" /></figure><h3>Performance and Scalability</h3><p><strong>Transaction Throughput:</strong> The UTXO model has an inherent advantage in parallelizing transaction processing. Because UTXOs are independent units of value, a blockchain node can validate multiple transactions at the same time <em>as long as they don’t try to spend the same UTXO</em>. Two different transactions using two different sets of outputs have no direct interaction, so in principle they could be processed concurrently. This ability to handle transactions in parallel can improve throughput on UTXO systems — the network can clear many non-conflicting transfers simultaneously, increasing the number of transactions per second in high-volume scenarios. Bitcoin takes some advantage of this by letting miners and nodes verify separate transactions concurrently (since each transaction explicitly lists which past outputs it spends, making conflicts easy to detect). UTXO’s “multiple little pieces” nature is amenable to sharding and other scaling techniques as well, because different chunks of the ledger (the UTXO set) can be split or processed in subsets.</p><p>Account-based blockchains, in contrast, must be more careful about parallel execution. The <strong>global state</strong> (all account balances and contract data) is like a single database that everyone is updating. If two transactions try to modify the same account or the same contract at once, they can’t both proceed in parallel — one must be processed before the other to avoid inconsistent results. Even transactions touching different accounts still share some global resources, and a blockchain typically processes a block of transactions in a specific order to update the state step by step. Thus, account systems often execute transactions <strong>sequentially</strong> (especially transactions from the same account), which can become a throughput bottleneck. As the network gets busier, this sequential processing can slow things down if many operations are contending to update popular accounts or contracts at the same time.</p><h3>Security Considerations</h3><p>At a basic level, both models enforce the same rule: you shouldn’t be able to spend funds you don’t have, and no coin should be spent twice. They achieve this with different approaches:</p><ul><li><strong>Double-Spend Prevention:</strong> UTXO chains excel at preventing double-spending <em>by construction</em>. Since each UTXO can only appear as an input to one transaction ever, the system simply refuses any transaction that tries to reuse an already-spent output. Every full node independently verifies that an input corresponds to a currently unspent output in the UTXO set; if not, the transaction is invalid. This one-use-only rule, plus digital signatures proving ownership of each output, provides strong protection against fraudulent spending. Account-based systems prevent double spends by checking the sender’s balance (you can’t send more than you have) and typically using a <strong>nonce</strong> or sequence number for transactions. For instance, Ethereum requires each transaction from an account to include a monotonically increasing nonce; if two transactions from the same account have the same nonce, or if a nonce is skipped, it’s considered invalid or a potential replay. This ensures each transaction is applied in order and only once. The end result is that both models effectively stop double-spend attempts, but UTXO does it by enforcing unique consumption of outputs, while account models rely on global state checks and ordering.</li><li><strong>Key Security and Access Control:</strong> In an account-based model, control of an account (and all its funds) is all-or-nothing: if someone gains access to your private key, they can authorize transfers of everything in that account. It’s vital to secure your keys because the account model doesn’t inherently compartmentalize funds — it’s one big pot under one key. UTXO models also rely on private keys for spending outputs, but there is a bit more granularity: your holdings might be spread across many UTXOs, potentially even with different keys or scripts controlling them. Compromising one key could steal the UTXOs associated with it, but UTXOs associated with a different address/key would remain safe. In practice, most users use a single key or a set of keys managed in a wallet, so the distinction may be minor. Both models are compatible with advanced security measures like multi-signature authorization (e.g., requiring 2-of-3 keys to sign off a spend) — Bitcoin supports this via script on UTXOs, while Ethereum supports it via smart contracts or special account types. UTXO’s model of embedding spending conditions in each output script allows for <strong>native</strong> multi-signature and time-lock conditions on coins. The account model can achieve the same but typically through higher-level constructs (like contract wallets).</li></ul><p>In summary, both models are <strong>secure</strong> when properly implemented, but the threat surfaces differ. UTXO’s transparency and simplicity make it easy for the network to validate transactions and hard to cheat the system (everyone can verify a chain of ownership of each coin). The account model’s reliance on a global state means careful coordination (order of transactions, prevention of replay attacks) and strong key security are paramount. Neither model prevents the most common security issues (like private key theft or user error) — those have to be managed off-chain with best practices and wallet security.</p><h3>Privacy Implications</h3><p>Privacy — or more precisely, anonymity — in blockchain transactions is another area where UTXO and account models behave quite differently. Blockchains are typically public ledgers, but the ease of linking transactions to identities varies between the models.</p><p><strong>UTXO Model and Privacy:</strong> The UTXO model can offer a higher degree of privacy <em>if users take advantage of it</em>. Because a new UTXO can be created with a brand-new address (public key) that has no prior history, users can keep generating fresh addresses for each transaction. This makes it harder for an outside observer to definitively connect two transactions to the same entity. Your funds aren’t all sitting in one easily identifiable bucket. They’re split among many outputs, and those outputs can be spread across many addresses. If Bob pays Alice in Bitcoin, Alice might receive that payment at a one-time address. When Alice later pays Charlie, her wallet might use a different UTXO (from a different address) altogether, making it non-trivial for someone scanning the blockchain to link Alice’s receipt from Bob to her payment to Charlie. In essence, UTXO systems by default <strong>distribute activity across lots of pseudonymous addresses</strong>, especially if users avoid reusing addresses. This gives a form of privacy through obscurity — not complete anonymity, but a degree of separation between transactions.</p><p>However, UTXO privacy is not absolute. The public nature of the ledger means that, with sophisticated chain analysis, patterns can emerge. For instance, if a user combines two UTXOs (from different addresses) as inputs in a single transaction, it likely reveals those two addresses were controlled by the same person. Analyses can cluster addresses that frequently transact together or track the trail of UTXOs that eventually appear as inputs to known exchange addresses, etc. Still, compared to account model, UTXO offers more opportunities for users to <em>anonymize their activity</em> by using techniques like CoinJoin mixing or simply one-off addresses.</p><p><strong>Account Model and Privacy:</strong> Account-based ledgers tend to be <strong>more transparent and easier to analyze</strong> from a privacy standpoint. Since all activities of a given account occur on one address, it’s trivial to look up that address on a block explorer and see its entire transaction history and current balance. If an account is associated with a real-world identity (say Alice’s exchange account or ENS domain is known), then <em>all</em> of that account’s blockchain activity is linked to Alice. Even if the identity isn’t initially known, analysts can often piece together clues (for example, noticing that a certain account transacts with known addresses or interacts with particular contracts) to de-anonymize users. The account model is thus less private by default: it’s like having one wallet that you always use — anyone can observe money in and out of that wallet and get a pretty complete picture.</p><p>Interestingly, the account model does have one <em>fungibility</em> advantage: once funds from various sources are pooled into a single account, those coins lose any individual “identity” — they become just part of the account’s balance. In other words, the account functions like a mixer of all incoming values. Suppose Alice’s account received 5 ETH from Bob and 5 ETH from Carol on different days. Later, Alice sends 8 ETH to Dave. On Ethereum’s ledger, it’s recorded simply as a debit of 8 ETH from Alice and a credit of 8 ETH to Dave. An outside observer can’t easily tell how much of that 8 ETH came from Bob’s deposit vs. Carol’s deposit — it’s all just Alice’s balance being reduced. By contrast, in a UTXO system, if Alice received two separate UTXOs (one from Bob, one from Carol) and later spent them together in a transaction to Dave (with some change back), an observer could see <em>which specific outputs</em> were used for the payment, potentially linking Dave’s payment to both Bob and Carol’s earlier payments. Account balances thus provide a slight mixing effect by default: every deposit is just added to the pot, and withdrawals come out of that pot without explicit linkages to particular deposits. Of course, this doesn’t solve privacy — if Alice’s address is known, everything is visible — but it means the origin of funds is somewhat blurred within the account.</p><p>Overall, UTXO systems can be said to offer <strong>better privacy for the careful user</strong> (especially if new addresses are constantly used and outputs are managed to avoid linking), while account systems are <strong>more transparent</strong> (all activity tied to persistent identities). If privacy is a priority, UTXO chains like Bitcoin or Zcash (which is UTXO-based and adds encryption to outputs) have an edge in obscuring transaction trails. That said, there are privacy enhancements for account systems too (for example, Ethereum mixers like Tornado Cash or upcoming privacy-focused account-model chains). And conversely, if users don’t use the UTXO model wisely (e.g., always reusing the same address), they can negate many of its privacy advantages. In both cases, on-chain privacy is pseudonymous at best — external information (KYC at exchanges, IP addresses, etc.) can still unravel anonymity.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=963872e5a6ea" width="1" height="1" alt=""><hr><p><a href="https://itnext.io/utxo-vs-account-based-blockchains-a-clear-comparison-963872e5a6ea">UTXO vs. Account-Based Blockchains: A Clear Comparison</a> was originally published in <a href="https://itnext.io/">ITNEXT</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An Academic Method to Solve LeetCode Dynamic Programming Questions]]></title>
            <link>https://itnext.io/a-method-to-solve-leetcode-dynamic-programming-questions-5faba8dad554?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/5faba8dad554</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Fri, 10 Mar 2023 09:26:08 GMT</pubDate>
            <atom:updated>2023-03-26T10:56:30.091Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*fTGWE0iRa2XxHhnO" /><figcaption>Photo by fauxels from Pexels: <a href="https://www.pexels.com/photo/man-and-woman-near-table-3184465/">https://www.pexels.com/photo/man-and-woman-near-table-3184465/</a></figcaption></figure><p>Like it or not, Leetcode questions are a part of every programming interview process. Leetcode questions can be divided into many categories: Dynamic Programming, Greedy, Bit manipulation, Arrays, etc.</p><p>I’m a self-taught senior software engineer who decided to take a break and pursue a degree at the university. While practicing Leetcode for interviews, I was amazed at how top leet-coders solve complex questions elegantly.</p><p>During my algorithm class this year, I pieced together an approach to solve Dynamic programming questions. Parts are based on proven academic knowledge, and parts are from my experience interviewing.</p><h3>The method</h3><p>The method consists of only three steps:</p><ol><li>Define subproblems</li><li>Write down a recursion formula</li><li>Tabulation/Memoization</li></ol><h4>Sub-problems</h4><p>If you are here, you probably know what Dynamic programming is. Formally, it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.</p><p>Subproblems are built on each other to obtain a solution for the problem. A problem can depend on a single sub-problem, or you might have to solve half of the dataset, then the second half, and merge the result.</p><h4>Recursion formula</h4><p>In this step, we write a concrete formula for how to compute a problem based on its subproblems. You might also know it as a transition formula. We should remember to handle stopping condition.</p><h4>Tabulation vs. Memoization</h4><p>This step is tied to the implementation itself. It is possible to solve using either top-down with Memoization or bottom-up with Tabulation. Tabulation is preferable.</p><p>We should consider how to extract the solution. Can we extract it directly from one of the cells, or would we have to iterate over the table and process the results?</p><p>Let’s take a look at a medium difficulty <a href="https://leetcode.com/problems/maximal-square/">problem</a> from leetcode.</p><h3>Maximal Square</h3><p>Given an m x n binary matrix filled with 0’s and 1’s find the largest square containing only 1’s and return its area.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/404/0*Ywq72xtuD2rQmgAW.jpg" /></figure><p><strong>Sub-problems: </strong>for every cell (i,j), find the largest square (the side length) such that (i,j) is the top left corner of the square.</p><p><strong>Recursion formula:</strong> To find the largest square starting at the current cell (i,j), we need to know the number of consecutive 1’s to the right of (i,j) , the number of consecutive 1 ‘s under (i,j) , and the size of the largest square in (i+1, j+1) . Then, we would have to take a minimum of the three to get the actual square size.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/333/1*ys6VaTrrnmAch_tlZoxQwg.jpeg" /><figcaption>We take the minimum of the purple, blue and orange rectangles. The result is the green rectangle.</figcaption></figure><p>At first sight, we don’t know the number of consecutive 1 ‘s below and to the right of (i,j), since we compute the square size of each cell. Notice it’s possible to deduce the number of consecutive 1 ‘s by using the square size located in (i+1,j) and (i,j+1) for rows and columns accordingly. <br>Don’t forget to handle entries with 0 and the base case. Therefore, we can write the following formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/642/0*ZWiuw1MHZ_8bTOSO" /></figure><p>How do we arrive at the final answer without passing through unoptimized solutions such as brute force or a less optimized DP solution? By defining what we look for in the sub-problems step, it’s clear <strong>what</strong> we need to calculate; in this step, we only need to find <strong>how </strong>to calculate it.</p><p><strong>Tabulation: </strong>Every subproblem is defined by the (i,j) coordinates of the cell. Those are two parameters, so we need a 2D table sized m x n . Each cell in the table should hold the largest square size of the corresponding entry in the matrix.</p><p>We will fill the table from (i,j) = (n-1,m-1) and work our way backward according to the formula. It doesn’t matter if we iterate over rows or columns first.</p><p>To return the answer, we could either iterate over the entire board again or, even better, save the max size and return it after the iteration. This algorithm is O(m*n).</p><pre>class Solution:<br>    def maximalSquare(self, mat: List[List[str]]) -&gt; int:<br>        if not mat:<br>            return 0<br>        <br>        m = len(mat)<br>        n = len(mat[0])<br>        maxLength = 0<br>        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]<br><br>        for i in range(m-1, -1, -1):<br>            for j in  range(n-1, -1, -1):<br>                if mat[i][j] == &#39;1&#39;:<br>                    dp[i][j] = 1 + min(dp[i+1][j+1], dp[i+1][j], dp[i][j+1]) <br>                    maxLength = max(maxLength, dp[i][j])<br>        return maxLength**2</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5faba8dad554" width="1" height="1" alt=""><hr><p><a href="https://itnext.io/a-method-to-solve-leetcode-dynamic-programming-questions-5faba8dad554">An Academic Method to Solve LeetCode Dynamic Programming Questions</a> was originally published in <a href="https://itnext.io/">ITNEXT</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Finding Bugs in Code Programmatically Using Go]]></title>
            <link>https://medium.com/better-programming/finding-bugs-in-code-programmatically-using-go-c5599796e89e?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/c5599796e89e</guid>
            <category><![CDATA[linter]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[static-code-analysis]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Mon, 03 Oct 2022 13:11:01 GMT</pubDate>
            <atom:updated>2022-10-03T13:11:01.001Z</atom:updated>
            <content:encoded><![CDATA[<h4>Write a static code analyzer to find bugs in code</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KUVbQTqEaR18BE-2RCqJWA.jpeg" /><figcaption>Photo by <a href="https://www.pexels.com/@pixabay?utm_content=attributionCopyText&amp;utm_medium=referral&amp;utm_source=pexels">Pixabay</a> from <a href="https://www.pexels.com/photo/antique-book-hand-knowledge-207681/?utm_content=attributionCopyText&amp;utm_medium=referral&amp;utm_source=pexels">Pexels</a></figcaption></figure><p>This is a blog post based on a workshop I gave a year ago at GopherCon on static analysis in Go. The workshop covers much more than I could cover in this article, so you can check out the workshop <a href="https://github.com/amit-davidson/GopherCon2021IsraelStaticAnalysisWorkshop">here</a>.</p><h3>Motivation</h3><p>According to Wikipedia, Static code analysis is the analysis of computer programs performed without executing them. You might be already familiar with tools doing static analysis:</p><ul><li>A linter for detecting styling errors and fixing them.</li><li>Built-in IDE analyzers for detecting different issues such as infinite loops, unreachable code, and declaration redundancy.</li><li>The go analyzer <a href="https://github.com/dominikh/go-tools">staticcheck</a> and the open source platform <a href="https://www.sonarqube.org/">SonarQube</a>.</li></ul><p>Why you should care? Code analyzers are a staple when working in teams with many developers. They are used in the CI/CD process to enforce that no bad practices, bugs, and anti-patterns are pushed to the main repo.</p><p>The Go language provides the <a href="https://pkg.go.dev/golang.org/x/tools/go/analysis">go/analysis</a> package for creating static code analyzers. Before talking about how to write those tools, we need to introduce a bit of theory.</p><h3>AST</h3><p>An abstract syntax tree (AST) is a way of representing the syntax of a programming language as a hierarchical tree-like structure. Let’s take a look at the following program:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b0376b919fa7b565cc76c1354e4226d7/href">https://medium.com/media/b0376b919fa7b565cc76c1354e4226d7/href</a></iframe><p>This is the AST for the program.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/437/1*uNZLomA1WVXy-GGhpeTTfQ.png" /></figure><p>[]ast.Decl contains all the top-level declarations in the file — imports and the main function. Inside <a href="http://ast.funcdecl/">ast.FuncDecl</a>, which is the main function declaration, we have a <a href="https://golang.org/pkg/go/ast/#BlockStmt">ast.blockStmt</a>. It is a list of the function statements- the actual code of the main function. We can keep going down the tree, but you can easily match the tree node to the actual code. (I removed some nodes from the tree to make it concise).</p><p>Go provides the <a href="https://pkg.go.dev/go/ast">go/ast</a> package. The AST package contains the types used to represent syntax trees in Go, as in the tree above. Let’s take a look at <a href="https://pkg.go.dev/go/ast#AssignStmt">ast.AssignStmt</a>. The following code is from the <a href="https://pkg.go.dev/go/ast">go/ast</a> package:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/83b07aebabf620d56d6ac84c5f212f80/href">https://medium.com/media/83b07aebabf620d56d6ac84c5f212f80/href</a></iframe><p>The expression a := 5 is an assignment, so it would be represented in AST as an <a href="https://pkg.go.dev/go/ast#AssignStmt">ast.AssignStmt</a> as follows:</p><ul><li>Lhs is [a]</li><li>TokPos [2] (the position of the “:” character)</li><li>Tok [:=]</li><li>Rhs is [5]</li></ul><p>The list of all the types in the package is <a href="https://pkg.go.dev/go/ast#pkg-index">long</a>, but it is compliant with what you would actually expect. You can also view the AST tree of a code using this <a href="http://goast.yuroyoro.net/">site</a>.</p><h3>Writing the analyzer</h3><p>In this part, we will write a static analyzer that detects if function arguments are being overwritten. This is considered a code smell, as it makes it harder to know what arguments were passed to a function during debugging. You can check the full code of the analyzer <a href="https://github.com/amit-davidson/ArgOverwritten">here</a>.</p><p>First, let’s look at a typical structure of an analyzer. We create a directory named passes for each pass. Each pass is an inspection of our code. Every one of them lives in its own package, including its logic and tests. Then we create a main file that executes the passes the module has.</p><pre>│── README.md<br>│── cmd<br>│   └── analyzerName<br>│       └── main.go<br>│── go.mod<br>│── go.sum<br>└── passes<br>    └── passName<br>        │── analyzer.go<br>        │── analyzer_test.go<br>        └── testdata</pre><p>The <a href="https://pkg.go.dev/golang.org/x/tools/go/analysis">go/analysis</a> package defines an API for modular static analysis tools. To begin with, all passes should create an instance of <a href="https://pkg.go.dev/golang.org/x/tools/go/analysis#hdr-Analyzer">analysis.Analyzer</a>. It describes an analysis function: its name, documentation, flags, relationship to other analyzers, and of course, its logic.</p><p>We will start by adding an analyzer to <a href="https://github.com/amit-davidson/ArgOverwritten/blob/master/passes/ArgOverwritten/analyzer.go">analyzer.go</a>. We will also add its name, and docs.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2aee80fd8bb5c38e348cb6533b539070/href">https://medium.com/media/2aee80fd8bb5c38e348cb6533b539070/href</a></iframe><p>Below is the run function inside the <a href="https://github.com/amit-davidson/ArgOverwritten/blob/master/passes/ArgOverwritten/analyzer.go">analyzer.go</a> file. It contains the actual logic of the analyzer. It receives an argument of type *<a href="https://pkg.go.dev/golang.org/x/tools/go/analysis#hdr-Pass">analysis.Pass</a>. *<a href="https://pkg.go.dev/golang.org/x/tools/go/analysis#hdr-Pass">analysis.Pass</a> provides information and operations for reporting diagnostics to the analyzer&#39;s Run function about the analyzed package.</p><p>Let’s look at lines 51–53 in the code below. We iterate over all the files and run the <a href="https://pkg.go.dev/go/ast#Inspect">ast.Inspect</a> function on each file. This function traverses the AST tree of a given file in depth-first order. The function is also given the visitor function which receives an AST node, and there is where the logic happens.</p><p>In lines 3–18, we validate the given node matches our conditions:</p><ul><li>Lines 3–15 make sure the node type is a function — regular function or a lambda function. Also, in lines 13–15, we exclude functions without a body, such as assembly routines.</li><li>In lines 16–18, functions without parameters are excluded.</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4765fee8002668cfeb824a88e4e6f619/href">https://medium.com/media/4765fee8002668cfeb824a88e4e6f619/href</a></iframe><p>We iterate over each argument on lines 20-25 and construct a set from them. Lines 27–47 are where the magic happens.</p><p>We traverse the tree starting from the body of the function as the root node. Then the function body is searched for statements where variables are modified- AssignStmt (a = 5 for exmaple) and IncDecStmt (i++ for example).</p><p>Then we check the identifier participating in the statement, and if it’s one of the arguments in the set (arguments), then it’s considered an error, and we call the report function. This is an auxiliary function I wrote, and you can see its code below. All it does is wrap the call to pass.Report which actually notifies the user about an error.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7e603fd02a96f426d81979f668ecaafd/href">https://medium.com/media/7e603fd02a96f426d81979f668ecaafd/href</a></iframe><p>Finally, we will add a new main file and a main function that uses the analyzer we just wrote. To run an analyzer you have to use single/multi checker for single/multiple passes.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6e24e54ba24022929128a2f0ffe5d10f/href">https://medium.com/media/6e24e54ba24022929128a2f0ffe5d10f/href</a></iframe><h3>Running our analyzer</h3><p>Now that our analyzer is ready, we want to run it on an actual file. We can run it using the following commands:</p><pre>go install path/to/analyzer<br>go vet -vettool=$(which analyzername) path/to/files</pre><p>The first command installs the analyzer as a binary, and the second run it using go vet. This way, you can easily integrate it into your IDE or CI/CD environment.</p><p>We can also test our code using the <a href="https://pkg.go.dev/golang.org/x/tools/go/analysis/analysistest">analysistest</a> package. Using analysistest.Run, it is possible to run an analyzer on a package named testdata with test files and check that it reported all the expected diagnostics. Expectations are expressed using &quot;// want ...&quot; comments in the input code, such as the following:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/532b2522a14cd50f1d32efbf97e6fc61/href">https://medium.com/media/532b2522a14cd50f1d32efbf97e6fc61/href</a></iframe><p>Finally, we have to call <a href="https://pkg.go.dev/golang.org/x/tools/go/analysis/analysistest#Run">analysistest.Run</a> from a test file as below.</p><pre>analysistest.Run(t, analysistest.TestData(), Analyzer)</pre><p>The first argument is *testing.T , the second is a path to the test files, easily supplied to us by <a href="https://pkg.go.dev/golang.org/x/tools/go/analysis/analysistest#pkg-variables">analysistest.TestData()</a> , and the third is the actual analyzer itself.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c5599796e89e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/better-programming/finding-bugs-in-code-programmatically-using-go-c5599796e89e">Finding Bugs in Code Programmatically Using Go</a> was originally published in <a href="https://betterprogramming.pub/">Better Programming</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Build a NoSQL Database From The Scratch in 1000 Lines of Code]]></title>
            <link>https://medium.com/better-programming/build-a-nosql-database-from-the-scratch-in-1000-lines-of-code-8ed1c15ed924?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/8ed1c15ed924</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[go]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Wed, 21 Sep 2022 13:14:52 GMT</pubDate>
            <atom:updated>2022-09-21T19:49:11.177Z</atom:updated>
            <content:encoded><![CDATA[<h3>Build a NoSQL Database From Scratch in 1000 Lines of Code</h3><h4>Introducing LibraDB, a working database I created using Go</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5GEu7ALdCR8yy-DBK11KHg.jpeg" /><figcaption>Photo by Pixabay</figcaption></figure><h3>Chapter 1</h3><p>I’m a fan of personal projects. Throughout the years, I have had the pleasure of writing multiple database-related blogs/GitHub projects. Now, I’ve decided I want one project to rule them all!</p><p>I’ve implemented my database in Go and decided to share my knowledge by writing a blog post describing all the steps. This post is quite long, so I originally it was meant to be a 7 parts series. Eventually, I decided to keep it into one long blog post that is split into 7 original parts. This way, you stop and easily come back to each chapter.</p><p>The database is intentionally simple and minimal, so the most important features will fit in but still make the code short.</p><p>The code is in Go, but it’s not complicated, and programmers unfamiliar with it can understand it. If you do know Go, I encourage you to work along!</p><p><a href="https://github.com/amit-davidson/LibraDB">The entire codebase is on GitHub</a>, and there are also around 50 tests to run when you’re done. <a href="https://github.com/amit-davidson/Building-a-NoSQL-database-from-zero">In a second repo</a>, the code is split into the 7 logical parts, each part in a different folder.</p><p>We will create a simple NoSQL database in Go. I’ll present the concepts of databases and how to use them to create a NoSQL key/value database from scratch in Go. We will answer questions such as:</p><ul><li>What is NoSQL?</li><li>How to store data on disk?</li><li>The difference between disk-based and in-memory databases</li><li>How are indexes made?</li><li>What is ACID, and how do transactions work?</li><li>How are databases designed for optimal performance?</li></ul><p>The first part will start with an overview of the concepts we will use in our database and then implement a basic mechanism for writing to the disk.</p><h4>SQL vs NoSQL</h4><p>Databases fall into different categories. Those that are relevant to us are Relational databases (SQL), key-value store, and document store (Those are considered NoSQL). The most prominent difference is the data model used by the database.</p><p>Relational databases organize data into tables (or “relations”) of columns and rows, with a unique key identifying each row. The rows represent instances of an entity (such as a “shop” for example), and the columns represent values attributed to that instance (such as “income” or “expanses”).</p><p>In relational databases, business logic may spread across the database. In other words, parts of a single object may appear in different tables across the database. We may have different tables for income and expenses, so to retrieve the entire shop entity from the database, we would have to query both tables.</p><p>Key-value and document stores are different. All information of a single entity is saved collectively in collections/buckets. Taking the example from earlier, a shop entity contains both income and expenses in a single instance and resides inside the shops collection.</p><p>Document stores are a <strong>subclass</strong> of key-value stores. In a key-value store, the data is considered inherently opaque to the database, whereas a document-oriented system relies on the document’s internal structure.<br>For example, in a document store, it’s possible to query all shops by an internal field such as incomes, whereas key-value could fetch shops only by their id.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gsFP25iw5K-J5oUcuCxB2A.png" /></figure><p>Those are the basic differences, though, in practice, there are more database types and more reasons to prefer one over another.</p><p>Our database will be a <strong>key-value</strong> store (<strong>not a document store</strong>) as its implementation is the easiest and most straightforward.</p><h4>Disk-Based Storage</h4><p>Databases organize their data (collections, documents …) in <em>database pages</em>. Pages are the smallest unit of data exchanged by the database and the disk. It’s convenient to have a unit of work of fixed size. Also, it makes sense to put related data in proximity so it can be fetched all at once.</p><p><em>Database pages </em>are stored contiguously on the disk to minimize disk seeks. Continuing our earlier example, consider a collection of 8 shops, where a single page is occupied by 2 shops. On the disk, it’ll look like the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*G2r18bhMFmPmIVYShG5N_g.png" /></figure><p><a href="https://dev.mysql.com/doc/refman/5.6/en/innodb-file-space.html">MySQL</a> has a default page size of 16Kb, <a href="https://www.postgresql.org/docs/current/storage-page-layout.html">Postgres</a> page size is 8Kb, and <a href="https://db.apache.org/derby/docs/10.0/manuals/tuning/perf24.html#Tune+the+size+of+database+pages">Apache Derby</a> has a page size of 4Kb.</p><p>Bigger page sizes lead to better performance, but they risk having <em>torn pages</em>. A scenario where the system crashes in the middle of writing multiple database pages of a single write transaction.</p><p>Those factors are considered when choosing the page size in a real-life database. Those considerations are not relevant to our database, so we will arbitrarily choose the size of our <em>database pages </em>to be 4KB.</p><h4>Underlying Data Structure</h4><p>As explained, databases store their internal data across many pages, which are stored on the disk. Databases employ data structures to manage the quantity of pages.</p><p>Databases use different data structures to organize pages on the disk, mostly <a href="https://en.wikipedia.org/wiki/B-tree">B</a>/<a href="https://en.wikipedia.org/wiki/B%2B_tree">B+</a> Trees and <a href="https://en.wikipedia.org/wiki/Hash_table">hash buckets</a>. Each data structure has its own benefits and merits: read/write performance, support for more complex queries such as sorting or range scans, ease of implementation, and many more.</p><p>We will use B-tree since it allows for easy implementation, but its principles are close to what is used in real-world databases.</p><h4>Our Database</h4><p>Our database will be a key-value store. Its underlying data structure is a B-Tree, and the size of each page is 4KB. It’ll have the following architecture:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/201/1*OR_C71FsFmL_hMX99_zLYw.png" /></figure><p><strong>Database </strong>manages our program and is responsible for orchestrating transactions — those are sequences of read and write operations. It also faces the programmers using the database, and serves their requests.</p><p><strong>Data Access Layer (DAL) </strong>handles all disk operations and how data is organized on the disk. It’s responsible for managing the underlying data structure, writing the database pages to the disk, and reclaiming free pages to avoid fragmentation.</p><h4>Start Coding</h4><p>We will build our database from the bottom-up, starting from the <strong>Data Access Layer (DAL) </strong>component<strong>.</strong> We’ll begin coding by creating a file for it. We’ll have a struct, a constructor, and a close method.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5aae5a73d427ae6de3614dd90c16c2eb/href">https://medium.com/media/5aae5a73d427ae6de3614dd90c16c2eb/href</a></iframe><h4>Database Pages</h4><p>Reading and writing database pages will be managed by the DAL. We’ll add a struct for the page type inside dal.go. It&#39;ll contain a number that serves as a unique ID, but it’s serves a bigger role. That number is used to access the page with pointer arithmetic like (PageSize*pageNum). We&#39;ll also add PageSize attribute to dal .</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cf841bad40f13f2fa804e49eaeb4fe44/href">https://medium.com/media/cf841bad40f13f2fa804e49eaeb4fe44/href</a></iframe><p>Finally, we’ll add a constructor and read and write operations for it. Notice how, on lines 12 and 25, the correct offset in the file is calculated given the page size and the page number.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9d916e71fe2d24f1dd8e7d4c35e78765/href">https://medium.com/media/9d916e71fe2d24f1dd8e7d4c35e78765/href</a></iframe><h4>Freelist</h4><p>Managing pages is a complex task. We need to know which pages are free and which are occupied. Pages can also be freed if they become empty, so we need to reclaim them for future use to avoid <em>Fragmentation</em>.</p><p>All this logic is managed by the freelist. This component is part of the DAL. It has a counter named maxPage holding the highest page number allocated so far, and an attribute called releasedPages for tracking released pages.</p><p>When allocating a new page, releasedPages is assessed first for a free page. If the list is empty, the counter is incremented, and a new page is given, increasing the file size.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M83vZHQDbXfpHxCsn237kw.png" /><figcaption>Occupied pages are in grey. The free pages are in white.</figcaption></figure><p>We will start by creating the file freelist.go, defining the type for freelist , and adding a constructor newFreeList. Then, we need to add getNextPage and releasePage . Our database uses the first page for storing metadata (which will be explained in the next chapter), so we can only allocate new pages with numbers greater than 0.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e77b364283e830121d7bc6e5d6ace205/href">https://medium.com/media/e77b364283e830121d7bc6e5d6ace205/href</a></iframe><p>Finally, we will embed the freelist inside our dal structure and create an instance when opening the database.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/19d8660c1d26c6223f4e05f9b9aa280f/href">https://medium.com/media/19d8660c1d26c6223f4e05f9b9aa280f/href</a></iframe><h4>Chapter 1 Conclusion</h4><p>So far, our database supports reading and writing pages. To test our work, we can create a main function, write a page and look at how data is stored.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4ed7a044018294af60f081d328c3e158/href">https://medium.com/media/4ed7a044018294af60f081d328c3e158/href</a></iframe><p>The command hexdump , together with the -C flag is used for displaying the contents of a binary file.</p><p>The first 4096 bytes (1000 in hex as seen on the left) are reserved for the metadata, and our data is right after it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZOWSgiwyFoR7W8e2gLzqZw.png" /></figure><p>Our database is functioning as long as the program is running. If the program is killed, we can’t know which pages are empty and which contain actual data. To start, it means the freelist needs to be persisted to the disk. This will be our topic for the next chapter.</p><p>You can check <a href="https://github.com/amit-davidson/Building-a-NoSQL-database-from-zero/tree/master/Part%201">here</a> a complete version of this part’s code.</p><h3><strong>Chapter 2</strong></h3><p>We continue building our database. In the last chapter, we looked at the general architecture of our database.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/201/1*OR_C71FsFmL_hMX99_zLYw.png" /></figure><p>Then we implemented the Data Access Layer that handles disk operations. So far, it supports: opening and closing the database file, writing and reading data into disk pages, and also managing empty and occupied pages using the freelist .</p><p>In this chapter, we will implement persistence to disk. It’s essential to save the database state to the disk so it can operate correctly between restarts. The DAL will be responsible for it.</p><p>We will start by committing the state of the freelist to the disk.</p><h4>Start Coding</h4><p>To save the state of freelist we want to write it as a database page to the disk. It’s common in databases to have a page holding metadata about the database.</p><p>It can be page numbers of essential pages- freelist in our case. It can also hold the magic number- a constant numerical or text value used to identify the file format (we will meet it in the last chapter). In our case, it’ll be both.</p><p>To track the freelist page number, we will add a new page called meta . It’s a special page since it’s fixed and located on number 0. This way, upon a restart, we can read the meta page from page number 0 and follow it to load the freelist content.</p><h4>Meta Page Persistence</h4><p>A typical pattern in our database is defining serialize and deserialize methods for converting an entity into raw data that fits a single page. And wrapping those with reading and writing methods that return the entity itself.</p><p>We will create a new file named meta.go , define a new type meta and a constructor.</p><p>We need to serialize meta to []byte so we can write it to the disk. Unfortunately, Go does not support an easy conversion of structs to binary the way C does without using the Unsafe package (which we won’t use for obvious reasons), so we’ll have to implement it ourselves.</p><p>In each method, we’ll have a position variable (pos) for tracking the position in the buffer. It’s similar to the cursor in files.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9a407099e4cb6cee767208b4eb437293/href">https://medium.com/media/9a407099e4cb6cee767208b4eb437293/href</a></iframe><p>We will also create a new file const.go for holding the sizes and declare a new constant pageNumSize. It contains the size of a page number (in bytes).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/caa5ad88920fbc85d6e51f255e602eeb/href">https://medium.com/media/caa5ad88920fbc85d6e51f255e602eeb/href</a></iframe><p>The const.go file answers the <strong>how</strong> many bytes to store for each variable, and the serialize and deserialize take care of <strong>where</strong> to keep it inside the page.</p><p>Finally, we’ll add the methods writeMeta and readMeta using the previous meta serialize/deserialize and read/write page methods.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/260b8e647d45a4636c10537c92bd41f9/href">https://medium.com/media/260b8e647d45a4636c10537c92bd41f9/href</a></iframe><h4>Freelist Persistence</h4><p>We have defined the meta page so we know <strong>where to </strong>find the freelist data. Now, we need to add methods for reading/writing the freelist itself. As before, we’ll add methods for serializing and deserializing.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d2d9a81fd1243b7a6a7dfa43a79fe729/href">https://medium.com/media/d2d9a81fd1243b7a6a7dfa43a79fe729/href</a></iframe><p>Next, we’ll embed the meta inside the dal struct.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3e2a7e9a6455343a16bc903f59b520b2/href">https://medium.com/media/3e2a7e9a6455343a16bc903f59b520b2/href</a></iframe><p>Add methods for reading and writing a freelist page using the page number located inside the meta struct.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bdefb3bdfec70578e0f3da328692fcf2/href">https://medium.com/media/bdefb3bdfec70578e0f3da328692fcf2/href</a></iframe><p>And finally, update the dal constructor to check for the database’s existence. If it doesn’t, a new meta file is created, and the freelist and meta pages are initialized. If it does, read the meta page to find the freelist page number and deserialize it.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f5136207791881ee1b16d5ef6c5fd5d0/href">https://medium.com/media/f5136207791881ee1b16d5ef6c5fd5d0/href</a></iframe><h4>Chapter 2 Conclusion</h4><p>Ok! We have persistence. We can play around by creating a new database, closing it, and then opening it again.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6403dfb16730041ed763b5fd45330293/href">https://medium.com/media/6403dfb16730041ed763b5fd45330293/href</a></iframe><p>Notice the meta page on page 0 (starting at line 1) containing the number 1 of the freelist page.</p><p>Right below (third line) is the freelist . We have 4, 1, 4. The first 4 indicate the maximum allocated page number. 1 shows the length of the released pages list, and the last 4 account for the only released page.</p><p>And finally, we have our data, and as you can see in the right column, it behaves correctly after the DB restarts.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vW1wkQD9Z3PR-mpQz0q0eQ.png" /></figure><p>In the next episode, we’ll start exploring B-Trees which are the main star of the database. It’ll take us a few episodes to cover it completely. We’ll talk about how they help us in organizing the data and how to store them on disk.</p><p>You can check <a href="https://github.com/amit-davidson/Building-a-NoSQL-database-from-zero/tree/master/Part%202">here</a> a complete version of this part’s code.</p><h3>Chapter 3</h3><p>We finished persisting our database on the disk in the last two chapters. It means our database can restore its previous state between restarts. It also supports reading and writing pages to the disk, but we have to take care of the bookkeeping of the data. In other words, when fetching an item from the database, we must remember where it was inserted.</p><p>Today, we will talk about B-Trees, the database’s main star. We will see how they help us organize the data, so the user doesn’t have to track where each object is located on the disk.</p><h4>Binary Search Tree</h4><p>A binary search tree (also called BST) is a data structure used for storing data in an ordered way. Each node in the tree is identified by a key, a value associated with this key, and two pointers (hence the name binary) for the child nodes. The invariant states that the left child node must be less than its direct parent, and the right child node must be greater than its immediate parent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/0*2wv3HvfmFPFXtQIu.png" /><figcaption>Binary Search Tree</figcaption></figure><p>This way, we can easily find elements by looking at each node’s value and descent accordingly. If the searched value is smaller than the current value, descend to the left child; if it’s greater, descend to the right.</p><p>A binary search tree allows for fast lookup, addition, and removal of data items since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree.</p><h4>Motivation</h4><p>Why do we even need a tree in the first place? A straightforward approach would be to create a text file and write data sequentially. Writing is fast, as new data is appended to the end of the file. On the other hand, reading a specific item requires searching the entire file. If our file gets big, reading will take a long time.</p><p>Obviously, it’s not suited for many real-life applications. Compared to the previous approach, BST offers slower writing in favor of better reading. This balanced approach is ideal for general-use databases.</p><p>Another consideration is disk access. It is costly, so it has to be kept to a minimum when designing a data structure that resides on the disk.</p><p>A binary tree node has 2 children, so having 2⁵=32 items, for example, will result in a tree with 5 levels. Searching for an item in the tree will require descending 5 levels in the worst case and, in turn, 5 disk accesses for each level. 5 is not much, but can we do better?</p><h4>B-Tree</h4><p>B-Tree is a generalization of a binary search tree, allowing for nodes with more than two children. Each node has between <em>k </em>to <em>2k </em>key-value pairs and <em>k+1</em> to 2<em>k+1</em> child pointers, except the root node with as few as <em>2</em> children.</p><p>By having more children in each node, the tree’s height gets smaller, thus requiring fewer disk accesses.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PjlR1redNFBuaVfJA6zBKQ.png" /><figcaption>K-V indicates a key-value pair. P indicates a child pointer</figcaption></figure><h4>Coding</h4><p>We will start by creating a new file node.go and defining new types for Node for a B-Tree node and Item representing a key-value pair.</p><p>We will also add isLeaf and a constructor for Node and Item.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/77f20f7a2395ac5a42eda8f7165a63c6/href">https://medium.com/media/77f20f7a2395ac5a42eda8f7165a63c6/href</a></iframe><h4>Node Page Structure</h4><p>We want to store Node contents on the disk. A trivial approach would be a concatenation of “key-value-child pointer” triplets, but it has a significant downside.</p><p>Items contain keys and values of different sizes. It means iterating over key-value pairs becomes a non-trivial task since we can’t know how many bytes the cursor should advance each iteration.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*00oOqlIKlV8Pq7h1pfyE2Q.png" /><figcaption>pages are denoted by <strong>p, </strong>keys by <strong>k,</strong> and values by v</figcaption></figure><p>To solve that problem, we will use a technique called <em>slotted pages</em>. The page is divided into two memory regions. At end of the page lie the keys and values, whereas at the beginning are <strong>fixed size</strong> offsets to the records.</p><p>We will also add a header containing the number of records in the page and a flag indicating if the page is a leaf (As leaves don’t have child pointers).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*yI8_0O5-0zquW0NFEYnNHA.png" /></figure><p>This design allows making changes to the page with minimal effort. The logical order is kept by sorting cell offsets, so the data doesn’t have to be relocated.</p><p>Each node is serialized to a single page, but It’s important to understand the distinction between the two.</p><p>Node contains only key-value pairs, and it’s used at a higher level. Page on the other hand, works on the storage level and holds any type of data, as long as it’s 4KB in size. It can contain the key-value pairs organized in a <em>slotted page </em>structure, but also freelist and meta which are laid in a less strict form.</p><h4>Nodes Persistence</h4><p>As we’ve done in previous chapters, we will add the serialization and deserialization of the database node. Those methods convert data from/to a slotted page format.</p><p>The implementation is lengthy and technical, and there’s nothing new to the details above. It’s better to focus general design described above than the implementation itself (Although I encourage you to read the code).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d9c3e4fcc62624d3d3e2ba1931e0d6f/href">https://medium.com/media/6d9c3e4fcc62624d3d3e2ba1931e0d6f/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/204d863dffc2473b4c769fed12de5ad5/href">https://medium.com/media/204d863dffc2473b4c769fed12de5ad5/href</a></iframe><p>We will also add getNode , writeNode and deleteNode for returning a node.<br>The first two methods return the node struct itself so they are the same as what we did with freelist and meta .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/389/1*i3kwm31_-xmGnSPXEdyM_w.png" /></figure><p>deleteNode signals to the freelist that a node can be deleted, so its page id can be marked as released.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9c9c184d5a26592743983bc30ab4c738/href">https://medium.com/media/9c9c184d5a26592743983bc30ab4c738/href</a></iframe><h4>Search, Insert, and Delete</h4><p>Before implementing the algorithms for search, insert and delete, it’s safe to assume we will make many calls to receive and write nodes. <br>We will wrap the calls to the dal with a layer of our own. In future parts, this will come in handy.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2856b155f6bbdb196f2b4a7ed1b48a56/href">https://medium.com/media/2856b155f6bbdb196f2b4a7ed1b48a56/href</a></iframe><h4>Search</h4><p>Searching a B-Tree is done using a binary search. The algorithm starts with the root node and traverses all the keys until it finds the first key greater than the searched value. Then, we descend toward the relevant subtree using the corresponding child pointer and repeat the process until the value is found.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B--xjy9noLDOpIYOrcCevQ.png" /></figure><p>In the example, 20 is supplied. In the first level, no keys match 20 exactly, so the algorithm descends into the correct range- all the numbers bigger than 13. The process is repeated on the rightmost node in the second level</p><p>The function findKeyInNode searches for a key inside a node, as in the figure above. It compares searched key with the keys in each level. If a match is found, then the function returns. If the key doesn’t exist, then the correct range is returned.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9093e878a11aa2abded90e2c55a8fb29/href">https://medium.com/media/9093e878a11aa2abded90e2c55a8fb29/href</a></iframe><p>Now we want to traverse the entire tree and use the previous function when searching each node. We will perform a search similar to a binary search. The only difference is that searching is performed with many children and not two, as described in the image above.</p><p>The findKey function is a wrapper around findKeyHelper where the heavy lifting is performed.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2f4c6f02a7babcbb590fe5ce71002bea/href">https://medium.com/media/2f4c6f02a7babcbb590fe5ce71002bea/href</a></iframe><p>As explained, searching is done recursively from a given node, usually the root. Every node can be reached from its parent, but since the root has no parents, we reach it by saving its page number inside the meta page.</p><p>The root attribute was added to the meta struct, and serialize and deserialize were to handle this field as well.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/32cc838b2990755ae8c3808e468231d4/href">https://medium.com/media/32cc838b2990755ae8c3808e468231d4/href</a></iframe><h4>Chapter 3 Conclusion</h4><p>Let’s test our search method. Our DB performs a search in a B-Tree, so it expects the database pages to be laid in a B-tree format.</p><p>We don’t have a way to create one yet, so I’ve added a mock file named mainTest that is already built this way. This file contains a key-value pair. The key is “Key1” and the value “Value1”.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/033ac225c216a9dafde59adb0807a334/href">https://medium.com/media/033ac225c216a9dafde59adb0807a334/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/672/1*_jRI_16VaYBaWba1rkPl1Q.png" /></figure><p>In the next two chapters, we will implement writing and deleting from the database. You can find the code of this part <a href="https://github.com/amit-davidson/Building-a-NoSQL-database-from-zero/tree/master/Part%203">here</a>.</p><h3>Chapter 4</h3><p>In the last chapter, we talked about B-Trees. They are a binary search tree generalization, allowing for nodes with more than two children. Tree height was minimized, thus reducing disk access.</p><p>We also talked about slotted pages. A layout for organizing key-value pairs of different sizes by positioning fixed-sized offsets at the beginning and the actual data itself at the end.</p><p>Finally, we started implementing basic operations on B-Trees: Search, Insertion, Delete. In the previous chapter, we implemented the search operation. We will do the insertion in this one.</p><h4>Problem</h4><p>Inserting new items might cause a node to have too many items. For example, when all the new pairs get inserted into the same node.</p><p>It makes operations slower as we iterate over more items every time the node has to be accessed. Apart from that, it leads to a more severe problem. Nodes are translated to fixed-size <em>database pages, </em>so there’s a limitation on the amount of key-value pairs in each node based on the total size of the key-value pairs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*m1G9BhfAccDk2sqxtanyLg.png" /></figure><p>Deletion suffers a similar problem. Deleting key-value pairs from the same node can shrink a node, so it contains very few key-value pairs. At this point, it’s better to reallocate those pairs into a different node someway.</p><p>To know if a node has reached maximum or under-occupancy, we must define it first. We will add an upper and lower threshold, a percentage of the page size.</p><p>In the code, we introduce Options, that will be initialized by the user and used inside our DB init function.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/704c56710bea985495c860c41cba4148/href">https://medium.com/media/704c56710bea985495c860c41cba4148/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/247264dd6bbc0a46ea9c2df6992c62b0/href">https://medium.com/media/247264dd6bbc0a46ea9c2df6992c62b0/href</a></iframe><p>We will also add new methods to dal and node for calculating a node size in bytes and comparing it to the thresholds. elementSize calculates the size of a single key-value-child triplet at a given index. nodeSize sums the node header size and the sizes of all the keys, values, and child nodes.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7cabb1ce652d2cc295f3a727d270d7ac/href">https://medium.com/media/7cabb1ce652d2cc295f3a727d270d7ac/href</a></iframe><h4>Solution</h4><p>When a node in the tree suffers from too many key-value pairs, the solution is to split it into two nodes.</p><p>Splitting is done by allocating a new node, transferring half of the key-value pairs there, and adding its first key and a pointer to that node to the parent node. If it’s a non-leaf node, then all the child pointers after the splitting point will also be moved.</p><p>The first key and a corresponding pointer are moved to the parent, thus increasing its occupancy. The process might result in overflow, so rebalancing must be repeated recursively up the tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/180/0*qKU4YlBX_ch89BNq.png" /><figcaption>Splitting is done when inserting 4 and 7. Image taken from Wikipedia</figcaption></figure><h4>Insertion</h4><p>The algorithm for insertion of an item goes as follows:</p><ol><li>Search the tree to find the leaf node where the new element should be inserted and add it.</li><li>If the node is over maximum occupancy, rebalance the tree as described above:<br>a. Find the split index<br>b. Values less than the separation value are left in the existing node and values greater than the separation value are put into a newly created right node.<br>c. The separation value is inserted in the node’s parent.</li><li>Repeat step 2, starting from the insertion node to the root.</li></ol><h4>Auxiliary methods</h4><p>We will start with step 1 of the algorithm. The method addItem adds a key-value pair at a given index and then shifts all the pairs and children. This trivial method could have been easily shipped with the standard library.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c6100e1a59f073df6b85380262e648a8/href">https://medium.com/media/c6100e1a59f073df6b85380262e648a8/href</a></iframe><p>For step 2, we will add four methods to determine if a node reached maximum occupancy. (or minimum occupancy which is needed for the delete)</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/22ab11675de324607844e1341cc9ecbc/href">https://medium.com/media/22ab11675de324607844e1341cc9ecbc/href</a></iframe><p>We will add corresponding methods to node for decoupling, which will aid us later.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3d822f012576c484e84d34f623664ff4/href">https://medium.com/media/3d822f012576c484e84d34f623664ff4/href</a></iframe><p>Now that we know if a rebalance has to occur, we will write the rebalancing itself. Focusing on 2.a, getSplitIndex calculates the index where the node should be split based on the element size and the minimum node size. It sums the sizes of key-value pairs in bytes. Once enough is accumulated, the index is returned.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/16433d1185efa715bde7eab6d53f58be/href">https://medium.com/media/16433d1185efa715bde7eab6d53f58be/href</a></iframe><p>Finally, we are going to add split to handle steps 2.b and 2.c .It is called on a node and receives one of its child nodes and its index in the childNodes list.</p><p>As explained earlier, the split index is determined first. The pairs to the left of the split index are untouched, whereas the pairs to the right are moved to a new node. If child pointers exist, the second half is moved as well.</p><p>The pair in the split index is moved to the parent, and a pointer to the newly created node is added at the correct position in the parent.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a0cb4c10f2929f70448e7165f73ae556/href">https://medium.com/media/a0cb4c10f2929f70448e7165f73ae556/href</a></iframe><h4>Put it all together</h4><p>Before we combine the methods above to an insert function, we will introduce the concept of a <em>collection</em>. A <em>collection</em> is a grouping of key-value pairs. A <em>collection</em> is the equivalent of an RDBMS table. Key-value pairs in a <em>collection</em> have a similar purpose.</p><p>We will return to the concept of collections in later articles. For now, we will add a struct called Collection and the Find and Put methods.</p><p>A collection is B-Tree on its own. So each collection has a name and a root page marking the tree root node.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d975e2341c47ebecc831e846b9b4e51f/href">https://medium.com/media/d975e2341c47ebecc831e846b9b4e51f/href</a></iframe><p>The Find method loads the collection root node and performs findKey on that node to locate the key. If a key wasn’t found, nil is returned.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/26cede1a83b0c478af872d4f9d52d3d3/href">https://medium.com/media/26cede1a83b0c478af872d4f9d52d3d3/href</a></iframe><p>The Put sums all the work we’ve done in this chapter. It receives a key-value pair from the user and inserts it into the collection’s B-Tree.</p><p>On lines 9–23, the method checks if a root node was already initialized or its first insertion, so a new root has to be created.</p><p>On lines 26–36, we search the tree where insertion should occur. findKey returns the node and the index where insertion should happen. It also returns nodes (as indexes - each node can be retrieved from its parent childNodes array) in the path leading to the modified node if we need to rebalance the tree.</p><p>On lines 31–41, we perform the actual insertion. We first check if the key already exists. If so, we only override it with the new value. If it doesn’t, we insert it. Due to how B-Tree works, new items can be added only to leaf nodes. It means we don’t need to care for children.</p><p>Finally, we rebalance on lines 49–56 and 59–71 if needed. The first block rebalances up the insertion path, excluding the root. The second block rebalances the root and updates the collection’s root pointer.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3c5c7f8a087e178accd34f63c603c15e/href">https://medium.com/media/3c5c7f8a087e178accd34f63c603c15e/href</a></iframe><h4>Chapter 4 Conclusion</h4><p>This part was focused on insertion into the database. Now we can insert and find items in the database as the user would have done.</p><p>In the code below, we’re creating a new database with MinFillPercent and MaxFillPercent that will cause a node to split when a node has six items or more. We create a new collection assigning the DB root page as the collection root page. Finally, we simulate an actual user operation of adding new items to a collection and searching for them.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/12bb75b45a531ef46b09ddae2b8f3987/href">https://medium.com/media/12bb75b45a531ef46b09ddae2b8f3987/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/528/1*ZvW2AWa0Iv6IoR-AmrtlAA.png" /></figure><p>Running hexdump on our file, we can observe a split has occurred. We have a root node containing 4. Then we have two children nodes, one with the pairs 1–3 and another node with keys 5–6.</p><p>Also, since nodes are designed as slotted pages, observe how the upper and lower addresses are written on each page, and the space in between remains empty.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nZeZZSgoeWXR4mD-c8aD2w.png" /></figure><p>In the next part, we will focus on deleting. It’ll be less intensive than this part as many of the functions we’ve added in this part will be used later.</p><p>You can check the code for this part <a href="https://github.com/amit-davidson/Building-a-NoSQL-database-from-zero/tree/master/Part%204">here</a>.</p><h3>Chapter 5</h3><p>We discussed B-Trees and implemented Find and Insert methods in the last two parts. In this part, we will implement the Delete operation and finish discussing B-Trees.</p><h4>Deletion</h4><p>The algorithm for deleting an item goes as follows:</p><ol><li>Locate the item for deletion.</li><li>Delete the item:<br>a If the value is in a leaf node, simply delete it from the node.<br>b Otherwise, (the value is in an internal node), choose a new separator — the largest element in the left subtree, remove it from the leaf node it is in, and replace the element to be deleted with the new separator</li><li>Rebalance the tree, starting from the leaf node or the node the separator was chosen from according to the case above.</li></ol><h4>Deletion Implementation</h4><p>We will focus on point 2.</p><p>We have two scenarios we need to handle. The first (2.a) is to delete a node from a leaf node. This case is trivial since we only need to remove it from the node.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/771b96b4f0d6f00a0d1711e1712bbce6/href">https://medium.com/media/771b96b4f0d6f00a0d1711e1712bbce6/href</a></iframe><p>If, on the other hand, we encounter an internal node (2.b), we need to locate its predecessor and make it the new separator. On line 15, we choose the left subtree and descend in lines 20–27 to the rightmost child, giving us the node with the biggest items in the left subtree.</p><p>On lines 30–32, we replace the item to be deleted with its predecessor- the rightmost pair in the left subtree and remove it from the leaf node it was in.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4b74b534b86835e90af8bfb52416aeee/href">https://medium.com/media/4b74b534b86835e90af8bfb52416aeee/href</a></iframe><h4>Rebalance</h4><p>We will focus on point 3.</p><p>When entering a new item to a node, it might lead to an overflow in one of the nodes causing the tree to get out of balance. Deletion can cause underflow, so we would have to rebalance the tree right after.</p><p>Unlike insertion, where rebalancing is done only by splitting a node, rebalancing after a delete operation can be either merging or rotating nodes.</p><p>Rotation can be done to the right or the left, depending on which node has an item to spare. A right rotation, for example, is done by copying the separator key from the parent to the start of the underflow node and replacing the separator key with the last element of its left sibling. When rotating a non-leaf node, the last child pointer of the left sibling is moved to the start of the unbalanced one. A similar approach is made when performing a left rotation.</p><p>In the example below, 15 is deleted causing the right child to have too few items. This results in a right rotation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*U44xKwRNxHWt2npMz7hU7A.png" /><figcaption>Right rotation</figcaption></figure><p>If no sibling can spare an element, the deficient node must be merged with a sibling. The merge causes the parent to lose a separator element, so the parent may become deficient and need rebalancing. Rebalancing may continue all the way to the root.</p><p>In this case, 15 is deleted. A right rotation can’t be performed as will it leave the left child in a deficit. Therefore, the solution is to merge the nodes to a single node.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vOllP1YxYUhBU4Ijq_MPGg.png" /><figcaption>Merge</figcaption></figure><p>Similarly to the previous chapter, we will start adding some auxiliary functions and combine them into a single function under the collection struct.</p><p>Our first two functions are right and left rotation. The functions are almost identical so let’s examine rotation to the right.</p><p>Rotation is done as explained in the comments. Given node A, we remove its last item. We replace it with the item in the correct index in the parent node and take the item originally in the parent, putting it in the B node.</p><p>The correct index is the index of the item between those two nodes in the parent. If any child pointers exist, they are moved as well.</p><p>The code for both rotations is similar. The differences are the affected nodes and the key-value pairs being moved.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5b20f57e82d6c9d5e99d4675a29e6261/href">https://medium.com/media/5b20f57e82d6c9d5e99d4675a29e6261/href</a></iframe><p>Next, is merge. The merge function receives a node and its index. Then, it merges that node with its left sibling, transferring its key-value pairs and child pointers. After the function finishes, it deletes the node.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f206dc0dab3c253d7244ec143882a5f5/href">https://medium.com/media/f206dc0dab3c253d7244ec143882a5f5/href</a></iframe><p>Finally, we will write reblanceRemove that determines what algorithm should be applied when the tree gets out of balance.</p><p>In each rotation (lines 9–19 and 22–32), we ensure the unbalanced node is not on the edge, so it has a left/right sibling. We also ensure that the sibling can spare an element, meaning its sibling won’t be underflow after the operation. If both conditions are true, rotation is chosen.</p><p>If both conditions don’t hold, then we perform a merge (lines 36–45). The merge function merges a node with its left sibling. If we are on the leftmost sibling, use one node to the right, hence the if condition on line 36.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0b4a37309dfc6094eb7f179a274e92a7/href">https://medium.com/media/0b4a37309dfc6094eb7f179a274e92a7/href</a></iframe><h4>Putt it all together</h4><p>We will add a new method Remove to collection. On lines 8–11, the root node is loaded, then on 13–16, we perform step 1 in our algorithm of locating the item to delete. If it doesn&#39;t exist, we return in lines 18–20.</p><p>On lines 22–30, we delete the item according to step 2 in the algorithm. We extend our ancestor list to track any nodes that might be affected by the removal of the leaf node.</p><p>Finally, on lines 32–47, we follow the nodes in the ancestorsIndexes list that were potentially affected and rebalance them if needed.</p><p>Finally, on lines 51–53, if the root node is empty (if, for example, it had one item originally and it was deleted), then we ignore it and assign its child as the new root.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a357d054439c05af5b383c056ca59e12/href">https://medium.com/media/a357d054439c05af5b383c056ca59e12/href</a></iframe><h4>Conclusion</h4><p>In the code below, we extend our program from the previous chapter with the remove operation in line 29.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/635c30d24fa4158bf6de44807007df40/href">https://medium.com/media/635c30d24fa4158bf6de44807007df40/href</a></iframe><p>Running it, we get nil after the removal as expected.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*I5c0utv7olCEkJgLESMC9A.png" /></figure><p>Remember from the previous part that a split occurred after 6 was inserted. You can view its state on the left side of the image below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b-0l_NkTwAABMo9mkUwQzQ.png" /><figcaption>Deleting key 1 resulting in a merge</figcaption></figure><p>After the removal operation, the tree will be out of balance. The right sibling has only two items which aren’t enough to perform a left rotation. Therefore, the merge balancing tactic is chosen. The tree after the merge operation is on the right.</p><p>Running hexdump, we get on page 3 (starting at 00002000) precisely as expected. All the pairs are on the same node.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BU4Yq9gxu9kAy1k-KOjYIg.png" /></figure><p>It’s important to note that the process doesn’t end there. Remember that in the merge process, a node is deleted. That node is marked as free by the freelist . When the updated freelist is committed, it is written to page 5, where 5 and 6 resided after the Insert operation (Look at the state of the file at the end of the previous part).</p><p>Committing the freelist is awkward but necessary, along with other operations that should be carried out after a series of read/write operations.</p><p>In the next chapter, we will introduce the notion of a <em>database transaction. </em>A unit of work consists of a sequence of operations performed on the database. They’ll handle the work that needs to be carried out before a series of operations starts and ends, and many more.</p><h3>Chapter 6</h3><p>In the last three parts, we talked about B-Trees. We implemented B-Tree methods such as Find, Insert and Delete. Those methods were close to the disk level, as they defined what layout pages should be saved on the disk.</p><h4>Transactions</h4><p>Today, we introduce the concept of transactions. Transactions are a higher-level concept. A transaction is a work unit consisting of a sequence of operations performed on the database.</p><p>For example, transferring money from account A to B consists of:</p><ol><li>Reading the balance of account A.</li><li>Deduct 50 dollars from that amount and write it back to account A.</li><li>Read the balance of account B.</li><li>Add 50 dollars to that amount and it back to account B.</li></ol><p>All these operations together are a single transaction.</p><h4>ACID</h4><p>ACID stands for atomicity, consistency, isolation, and durability. It’s a set of properties of a database that guarantees transactions are processed reliably.</p><ul><li><strong>Atomicity</strong> means that either all of the transaction succeeds or none of it does. It ensures the database isn’t left in an undefined state.<br>Our database is not atomic since if a transaction fails the middle way (if the database crashes), part of the transaction is committed, and part does not. <br>I built the database so that it can be easily extended to support it, but it also involves more code and is out of the scope of our database.</li><li><strong>Consistency</strong> ensures that data written to the database must be valid according to all defined rules after the transaction completes. For example, the balance of an account in a bank must be positive.</li><li><strong>Isolation</strong> is a scale of how transactions occur in isolation from one another. In other words, to what level do transactions affect others. I’ll give more attention to this point in the next section.</li><li><strong>Durability</strong> means that once a transaction has been committed, data will be kept even in the case of a system failure.<br>Our database is durable since the database is persisted on the disk. Data remains on the disk after a crash, unlike in In-Memory (RAM) databases.</li></ul><h3>Isolation</h3><p>First, we’ll describe three anomalies that might happen when multiple transactions are running <strong>concurrently</strong>.</p><h4><strong>Dirty reads</strong></h4><p>A <em>dirty read</em> occurs when a transaction is allowed to read data from a row that has been modified by another running transaction and is not yet committed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/531/1*KujjYTFtRUx5UJn6op8muQ.png" /></figure><h4>Non-repeatable reads</h4><p>A <em>non-repeatable read</em> occurs when, during the course of a transaction, a row is retrieved twice, and the values within the row differ between reads.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/450/1*yhAfZrjJiovqRv2AppoHtA.png" /></figure><h4>Phantom reads</h4><p>A <em>phantom read</em> occurs when, in the course of a transaction, new rows are added or removed by another transaction to the records being read.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/619/1*tKBTtr7LbS2yIjz--lhrnQ.png" /></figure><p><em>Dirty reads</em><strong> </strong>read <strong>uncommitted </strong>data from another transaction.<br><em>Non-repeatable reads</em><strong> </strong>read <strong>committed</strong> data from an <strong>update</strong> query of another transaction. <br><em>Phantom reads </em>read <strong>committed</strong> data from an <strong>insert</strong> or a <strong>delete</strong> query of another transaction.<br><em>Phantom reads</em> are a more complex variation of <em>Non-repeatable reads</em>. <em>Phantom reads</em> involve range scans, so the problem is not in a single document as in <em>Non-repeatable reads </em>but in multiple documents.</p><h4>Isolation Levels</h4><p>The SQL standard defines four isolation levels based on the phenomena as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RCQeQG1uBEh1jA7ZY6KrQg.png" /><figcaption>Taken from Wikipedia</figcaption></figure><p>In our database, we will have a <em>Serializable</em> isolation level. Each transaction executes to completion before the next transaction begins.</p><p>We will achieve it by acquiring a RW lock before a transaction starts and releasing it when it ends. A RW lock can be held by an arbitrary number of readers or a single writer.</p><p>It means that our database can support a single writer or multiple readers at any given time, but not both.</p><h3>Start Coding</h3><h4>DB</h4><p>We will create a new file called db.go . We will add a new struct called DB and the methods Open and Close . DB contains dal and a RW lock. It manages access to the disk and ensures concurrent transactions don’t cause any anomalies, as described above.</p><p>DB is user-facing, so we will use public methods wrapping the dal layer.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/464e130c7548692177be3c29e12bd4eb/href">https://medium.com/media/464e130c7548692177be3c29e12bd4eb/href</a></iframe><p>We will also add two methods ReadTx and WriteTx for opening transactions and acquiring the lock.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9bfece31c07eadee4e8ff2bb5cec60f2/href">https://medium.com/media/9bfece31c07eadee4e8ff2bb5cec60f2/href</a></iframe><h4>Transactions</h4><p>We will add a new file called tx.go . We will add a new tx struct and constructor.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e07f4dd7dd9f681b850c0965721a0210/href">https://medium.com/media/e07f4dd7dd9f681b850c0965721a0210/href</a></iframe><p>The write flag indicates if the transaction is read-only or not. We will add a new error to const.go when a read-only transaction tries to make a change.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/43fdf44bf76da43d1d9b33ac3709941e/href">https://medium.com/media/43fdf44bf76da43d1d9b33ac3709941e/href</a></iframe><p>Then use it in the Put and Remove methods from earlier episodes.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/662a863a7befe6b748ab9d5d9928c1eb/href">https://medium.com/media/662a863a7befe6b748ab9d5d9928c1eb/href</a></iframe><p>Once a transaction starts, it either commits, and all modified data is saved, or it is rolled back, and all changes are ignored. Committing the changes is easy, as we have already done in previous parts, but rollback is more complicated.</p><p>Instead of reverting the changes when performing a rollback, an easier approach would be to store the modified nodes temporarily on RAM and propagate them to disk all at once. Then to perform a rollback, we have to do nothing since the data wasn’t committed.</p><p>For that, dirtyNodes holds modified nodes, waiting to be committed. pagesToDelete holds pages waiting to be deleted. And allocatedPageNums holds any new pageNums that we allocated by the freelist during the transaction.</p><p>If a transaction is read, performing a rollback is simple as only the mutex has to be released. If it’s a write transaction, we have to release pages given by the freelist , mark the slices as nil and release the mutex.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fd79457b11643212b04eec0c50ba493b/href">https://medium.com/media/fd79457b11643212b04eec0c50ba493b/href</a></iframe><p>Performing a Commit is also straightforward. In a read transaction, only the mutex has to be released. In a write, modified nodes are saved, deleted nodes are removed, and any acquired pages are marked. Finally, the mutex is released.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9cb0f1173964354498f81205dbccc221/href">https://medium.com/media/9cb0f1173964354498f81205dbccc221/href</a></iframe><p>Now we want to redirect the read/write/delete operations we added in previous episodes to dirtyNodes and pagesToDelete instead of the disk. It means that we will have to go over the code and replace accesses to dal to tx instead.</p><p>For example, do the following change:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7f70742faea7de2dd234a8c808000657/href">https://medium.com/media/7f70742faea7de2dd234a8c808000657/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a96ad3a4ec416d5e24d818dd28c5fa30/href">https://medium.com/media/a96ad3a4ec416d5e24d818dd28c5fa30/href</a></iframe><p>Or the following inside the collection file:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/22b04a15f9819cb5e30d68de735cde68/href">https://medium.com/media/22b04a15f9819cb5e30d68de735cde68/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/44fb78d0a0ae621fd14e4e371f2501ea/href">https://medium.com/media/44fb78d0a0ae621fd14e4e371f2501ea/href</a></iframe><p>This process is lengthy, but you can check all the changes on <a href="https://github.com/amit-davidson/Building-a-NoSQL-database-from-zero/tree/master/Part%206">Github</a>.</p><p>It’s important to notice that once we write a node, it’s not actually written to the disk but to a temporary buffer. If the system fails midway, we won’t be able to continue the transaction from the crash point.</p><p>To solve this problem, it’s possible to track the changes using <em>WAL</em>. It stands for <em>write-ahead logging</em> and is used for providing atomicity and durability. It’s usually implemented as an append-only log file recording changes to the database.</p><p>Then, every time the write node method is called (or delete), we could record the change in a separate log file (and not in the B-Tree!). If the system crashes, we could restore the database from the last call.</p><p>This is also out of the scope of our database, but our database is built so it can be easily extended with this improvement.</p><h4>Chapter 6 Conclusion</h4><p>In this part, we won’t showcase our new capabilities, but in the next part, we will have a working database from the bottom-up. We will add new methods for working with collections that will conclude all the critical features of our database.</p><h3>Chapter 7</h3><p>In this part, we will complete the database. We will take a deeper look at collections that we already saw before. This part is going to be our last episode as well.</p><h4>Collections</h4><p>We have already introduced the concept of collections. They store key-value pairs with a similar purpose and are the equivalent of an RDBMS table.</p><p>We discussed adding/removing/searching inside a <strong>given</strong> collection, but we haven’t discussed how to <strong>create</strong> them.</p><p>The idea is to have a master collection that holds other collections (<em>Root Collection</em>). It will contain key-value pairs, where the <strong>key</strong> is the collection name.</p><p>In a B-tree, every node is a root of a sub B-Tree so that every collection will be B-tree by itself and a sub B-tree of the entire B-Tree. The <strong>value</strong> will point to a page number that is the root of the collection sub-tree.</p><p>Remember that the meta page holds the page number of the B-tree root. The root field will point to the root page of the <em>Root Collection</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2DJlkPpcLGVgSGWOKe5DGQ.png" /></figure><p>A real-life flow of searching a key-value pair in the database is as follows:</p><ol><li>Start by retrieving the desired bucket to perform the search in. The database will search the <em>Root Collection</em> for the given collection.</li><li>Fetch the collection sub-tree root page</li><li>Find the desired element inside the collection sub-tree, starting at the root page.</li></ol><p>Both steps 1 and 3 utilize the Find method we have implemented in part 4. The difference is the searched collection. The image below shows the process where each arrow corresponds to a step in the process.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rebSSZYOpjGhx_NgglVxXw.png" /></figure><h4>Start Coding</h4><p>We will start by implementing a method for retrieving the root collection. The critical part is assigning its root page the same as the entire DB’s root page.</p><p>Then we will add GetCollection as discussed above. Searching the root collection for the collection name, deserializing the content, and returning.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ea136255b4e196f8cf1a3c4200280126/href">https://medium.com/media/ea136255b4e196f8cf1a3c4200280126/href</a></iframe><p>Creating and deleting a collection are similar. Apply Put /Remove on the <em>Root Collection</em>. Also, make sure the calling transaction is a write transaction.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1bcf2af281216d07349831c7467f96d6/href">https://medium.com/media/1bcf2af281216d07349831c7467f96d6/href</a></iframe><h4>Magic Numbers</h4><p>We will add a final nice-to-have feature. A magic number is a constant numerical or text value used to identify a file format. Programs store in the first bytes an identifier such as CA FE BA BE (Java class files, for example). When the program loads, it compares the first bytes with the expected signature and ensures they are equal.</p><p>We will define our magic number to be D00DB00D (But it can be whatever you choose). We will include the magic number when writing the meta page to the disk. When loading it from the disk when the database starts, we will compare the file contents with the expected signature.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1da4fd765485cd27c8207c9af6005920/href">https://medium.com/media/1da4fd765485cd27c8207c9af6005920/href</a></iframe><h4>Chapter 7 Conclusion</h4><p>This was a long journey, but our database is completed now. You should pat on your back if you followed me to this point.</p><p>To test our database, you can either use one of the tests inside the completed on <a href="https://github.com/amit-davidson/LibraDB">Github</a> or write your scenario. Any mix of read/write operations concurrently or non-concurrently will work.</p><h3>Summary and Final Words</h3><p><strong>In chapter 1</strong>, we introduced broad terms such as SQL vs. NoSQL, data structures, and disk-based storage. We talked about our database, specifically the <em>dal</em> layer and its components, such as <em>freelist </em>and <em>database pages.</em></p><p><strong>Chapter 2</strong> was all about persistence to the disk. We introduced a special page located on the file’s first page called <em>meta. </em>It holds all the information our database needs to start correctly. We also added methods for writing to the disk, such as: serialize /deserialize and read/write of <em>meta</em> and <em>freelist</em> pages. Those methods reappear every time a new entity is added to the database.</p><p><strong>Chapter 3, 4, and 5</strong> were about B-Trees. <strong>In chapter 3</strong>, we introduced binary search trees and talked about the rationale of B-Trees in databases. We decided to use <em>slotted pages. </em>A technique for organizing data on the disk by storing the data at the end of each page and fixed-size pointers to the data at the beginning.</p><p>Then, we started coding the B-Tree and finished that part with a search operation.</p><p><strong>In chapter 4</strong>, we coded insertion to the database using B-Tree. We first saw the importance of keeping the B-Tree balanced and added methods for determining if the tree was out of balance- if it had too many/few elements in a node. Then we coded the split method to handle rebalancing and the insertion method itself. We also saw the collection entity for the first time.</p><p><strong>In chapter 5</strong>, we finished coding the B-Tree by implementing the deletion and the appropriate balancing methods- left/right rotation and merge.</p><p><strong>Chapter 6</strong> differed from the previous parts since we weren’t handling disk operations. We brought up the topic of transactions- a work unit consisting of a sequence of operations performed on the database.</p><p>We talked about ACID- a set of properties for processing transactions reliably. We also looked closely at the isolation properly and used locks to ensure concurrent transactions don’t interfere with each other.</p><p><strong>Finally, in chapter 7</strong>, we added the collections mechanism, the last piece remaining for the databases to function, and magic numbers that seal it completely.</p><p>Below you can see the general architecture of our database.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NziZHy0960OJdRFdQLoyfA.png" /></figure><p>It was a year since I started writing the database till the articles were completed. I hope you enjoyed reading my posts half as much as I enjoyed writing them for you. Be sure to check the completed database called LibraDB on <a href="https://github.com/amit-davidson/LibraDB">GitHub</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8ed1c15ed924" width="1" height="1" alt=""><hr><p><a href="https://medium.com/better-programming/build-a-nosql-database-from-the-scratch-in-1000-lines-of-code-8ed1c15ed924">Build a NoSQL Database From The Scratch in 1000 Lines of Code</a> was originally published in <a href="https://betterprogramming.pub/">Better Programming</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Databases Behind the Scenes: How BoltDB Saves Data To the Disk]]></title>
            <link>https://itnext.io/databases-behind-the-scenes-how-boltdb-saves-data-to-the-disk-de8f1e3feda6?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/de8f1e3feda6</guid>
            <category><![CDATA[dbms]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[performance]]></category>
            <category><![CDATA[boltdb]]></category>
            <category><![CDATA[data]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Mon, 04 Oct 2021 15:21:31 GMT</pubDate>
            <atom:updated>2021-10-08T07:15:27.547Z</atom:updated>
            <content:encoded><![CDATA[<h4>Understanding how databases write data to the disk by reading their source code</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*YFseH0D9AjJNQWYD" /><figcaption>Photo by <a href="https://unsplash.com/@markuswinkler?utm_source=medium&amp;utm_medium=referral">Markus Winkler</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Most software engineers don’t know databases. For many, the only thing they know about a database is if it supports SQL or NoSQL.</p><p>Today, we will talk about databases concepts. We will see what happens from the moment a <em>write </em>starts until it is committed to the disk.</p><p>We will do it by looking at BoltDB. A lightweight database written in Go for storing data on disk. The code is simple and has less than 5000 lines of code, so it’s a good place for starting to read about databases.</p><p>Even though Bolt is written in Go, the post will be language agnostic.</p><h3>BoltDB overview</h3><p>BoltDB is a NoSQL key/value storage engine based on B+ tree. There are only a few types in BoltDB: DB, Bucket, Tx, and Cursor.</p><p>DB is a wrapper for the database. Bucket is a collection of key/value pairs. Bucket operations are handled inside transactions Tx. Read-only or read-write transactions depending on the process. Cursor is used to iterate over keys in the tree in sequential order.</p><p>BoltDB doesn’t have a query language like in a fully fledged database. Instead, all operations are carried through the Read, Put and Delete functions inside the transaction itself.</p><h3>Data organization</h3><h4>Memory representation</h4><p>To locate a record, database systems use <em>indexes. </em>The <em>indexes</em> are built on top of different data structures, each giving its benefits. Most popular are LSM trees and B-Trees and their variants.</p><p>The underlying data structure for Bolt is a B+ tree. It means Bolt is suited for read-heavy applications. All the nodes contain key/value pairs called inodes. On branch nodes, the value is a pointer to the child on disk, and on leaves, it’s the actual value.</p><p>BoltDB B+ tree is different from a conventional one. Child nodes don’t hold a pointer to the sibling node, making range scans slower in favor of less space.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zovzND-fuOK_5vuzvaKECA.png" /><figcaption>BoltDB B+ Tree</figcaption></figure><p>Rebalancing is also adapted for “real world” implications. It consists only of merging and splitting without rotating. Also, it is delayed until the transaction commits to avoid undoing changes when the transaction is rolled back.</p><h4>Disk representation</h4><p>When writing to disk, databases have to develop a format for how to lay data on disk. Page is the smallest amount of data that can be written or read using the OS. It is usually 4KiB in size and is laid contiguously on the disk. Databases aim to have their data aligned with the pages to minimize requests to the disk and improve performance.</p><p>In Bolt, each tree node corresponds to one or more disk pages. Each page contains the headers: id, flags, count, and overflow.</p><ul><li>flags is the type of the page: branch, leaf, meta or freelist</li><li>count is the number of key-value pairs</li><li>overflow is the number of overflow pages in case the node is big</li></ul><p>And a generic ptr field pointing to page type specific data. The layout of the page on disk is as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sgHJYnHEtuDUeNdSmn2ZuQ.png" /><figcaption>Page Layout</figcaption></figure><h4>Branch page</h4><p>Branch pages are divided into two segments: keys and pointers to keys. Pointers have a fixed size, but keys can vary. To find a key, we can easily locate the pointer and read <em>ksize</em> bytes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZTrow6iAtUwqjjeunHdWuw.png" /><figcaption>Branch Node Layout</figcaption></figure><h4>Leaf page</h4><p>Leaf pages are similar to branch pages. The most notable difference is pgid is replaced with vsize and the value is added to the keys segment.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wOirnYiydgcH4mGa-S9zUg.png" /><figcaption>Leaf Node Layout</figcaption></figure><p>When a node is loaded, it has to be deserialized first. BoltDB doesn’t complicate things and uses binary encoding. When deserializing, the flags field is used to load the appropriate page type into ptr .</p><p>When a node is saved back, it has to be converted from the node representation into a page. So the data is serialized into the page format.</p><h3>Transactions</h3><p>ACID stands for atomicity, consistency, isolation, durability. It’s a set of properties of a database that guarantees transactions are processed reliably.</p><ul><li>Atomicity means that either all of the transaction succeeds or none of it does. This ensures the database isn’t left in an undefined state.</li><li>Consistency ensures any data written to the database must be valid according to all defined rules after the transaction completes.</li><li>Isolation guarantees that all transactions will occur in isolation. No transaction will be affected by other transactions. So a transaction cannot read data from any other transaction that has not yet been completed.</li><li>Durability means that once a transaction has been committed, data will be kept even in the case of a system failure.</li></ul><p>BoltDB transactions are ACID compliant. It uses copy-on-write, so BoltDB copies all the nodes in the path leading to it when a node is modified. Then to apply the changes, all that has to be done is to replace the root of the new branch.</p><p>This way, transactions are isolated. Multiple readers can be served using the original version while the copied version is modified. Also, the transaction is atomic since its state can change from no execution to complete execution using a pointer switch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7IDaQbTQkl9TpuPQ7e7qVA.png" /><figcaption>Copy On Write</figcaption></figure><p>Metadata is tracked in pages with the flag meta that was mentioned earlier. The meta page holds a reference to the page id of the root bucket. So BoltDB replaces the root pointer by rewriting the meta page.</p><h3>Page Management</h3><p>The OS maintains a page cache to improve the performance of reads. With a regular file read, the call passes through the cache, but pages may have been evicted from the cache ages ago.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1IIL8__92AN_Qdl56CsNUQ.png" /><figcaption>Page Cache</figcaption></figure><p>Many databases implement their cache instead. BoltDB doesn&#39;t implement its own cache and uses mmap . With mmap pages are saved separately in memory until done, so pages are never evicted. More RAM is required in favor of faster reads.</p><p>The entire database is a single file. With mmap, a fixed size to map has to be specified. The file may grow indefinitely, so mmap has to be called accordingly.</p><p>mmap is a syscall and expensive, so BoltDB avoids calling it after each write. Instead, it maps more than it needs, so fewer calls have to be made. From 32KB to 1GB, the increments are in powers of 2. After 1GB, the file grows in steps of 1GB.</p><p>The free pages of the leftover space are managed by freelist. When a transaction is committed, it requests free pages from freelist to write the modified nodes. Once a transaction completes or is rolled back, the pages can be reclaimed. If there are no free pages, mmap is called with a bigger size.</p><h3>Putting it all together</h3><p>Finally, we can put everything together to understand how database transactions work in BoltDB.</p><ol><li>To make a change to the database, a read-write transaction is opened.</li><li>For example, Put is called and Cursor is moved to the correct node and position in the tree.</li><li>To modify a node, it has to be copied first. The relevant pages are loaded and deserialized according to the page type. All changes are performed on the tree until the transaction commits.</li><li>Once <em>Commit</em> is called, the tree is rebalanced with merge or split.</li><li>freelist allocates new pages. If there aren’t enough pages, the file is remapped using mmap.</li><li>The modified nodes are serialized into the pages. The pages are written to the disk.</li><li>The root is replaced by rewriting the meta page, pointing to the new one.</li></ol><h3>Conclusion</h3><p>I hope now you have a better understanding of how databases work. The biggest takeaway is realizing that even though modern databases are complex, studying them isn’t that difficult.</p><p>If you find databases interesting, I recommend reading my <a href="https://itnext.io/all-about-b-trees-and-databases-8c0697856189">blog post about B-Trees and databases</a>. I also recommend reading yourself through the <a href="https://github.com/boltdb/bolt">source code of BoltDB</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=de8f1e3feda6" width="1" height="1" alt=""><hr><p><a href="https://itnext.io/databases-behind-the-scenes-how-boltdb-saves-data-to-the-disk-de8f1e3feda6">Databases Behind the Scenes: How BoltDB Saves Data To the Disk</a> was originally published in <a href="https://itnext.io/">ITNEXT</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 B Trees and Database]]></title>
            <link>https://itnext.io/all-about-b-trees-and-databases-8c0697856189?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/8c0697856189</guid>
            <category><![CDATA[b-tree]]></category>
            <category><![CDATA[database]]></category>
            <category><![CDATA[performance]]></category>
            <category><![CDATA[data]]></category>
            <category><![CDATA[data-intensive-system]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Fri, 17 Sep 2021 07:16:26 GMT</pubDate>
            <atom:updated>2021-09-21T07:32:26.979Z</atom:updated>
            <content:encoded><![CDATA[<h4>How B-Trees power your database in handling data-intensive workloads.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*f_PKRubW6rQGb9LF" /></figure><p>Recently, I’ve been reading <a href="https://www.goodreads.com/book/show/44647144-database-internals"><em>Database Internals</em></a> (Alex Petrov, 2019). An excellent book covering the implementation of database <em>storage engines</em> — the component of databases that stores and retrieves data from the disk in an efficient and reliable way. A significant part of this book discusses the implementation and optimization of various B-Tree data structures.</p><p>B-Trees are the most prominent data structures employed by databases. Most notable examples are Postgres, Mysql, and Oracle Database. Before diving into B-Trees, we should focus first on binary search trees.</p><h3>Binary Tree</h3><p>A binary tree is a data structure used for storing data in an ordered way. Each node in the tree is identified by a key, a value associated with this key, and two pointers (hence the name binary) for the child nodes. The rule is that the left child node must be less than its direct parent, and the right child node must be greater than its direct parent.</p><figure><img alt="Binary tree" src="https://cdn-images-1.medium.com/max/454/1*8i77nF2bOdnGDT9LwcZ3Eg.png" /></figure><p>This way, we can easily find elements by looking at each node’s value and descent accordingly. If the searched value is smaller than the current value, descend to the left child; if it’s greater, descend to the right.</p><h3>Rebalancing</h3><p>When inserting a new element, we need to find the right position and insert a new node there. This might lead the tree to get out of balance. In the worst case, it might look like the case on the right, resembling a linked list instead of a tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sU_hsOdtsrtbQHIOo-scAg.png" /><figcaption>Binary tree ideal and worst cases</figcaption></figure><p>In an ideal case, following the right or left node reduces the search complexity in half on average by avoiding checking the unchosen path. When having an unbalanced tree, more nodes have to be traversed, which significantly slows down searches.</p><p>Mathematically speaking, when looking for an element, it has a complexity of O(log₂ N) on the tree form, and O(N) on the linked list form. The shallower the tree is, the faster searches will be.</p><p>Instead of adding new elements to one of the tree branches and making it longer while the other remains empty, the tree will be rebalanced. As shown below, it’s done by rotating nodes around, to the right or the left. The rule of having smaller items on the left and greater on the right is preserved, but the height gets smaller, making searches faster.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/847/1*lRgLxzLlKzTOqJf8uDQX2Q.png" /><figcaption>Tree rotation</figcaption></figure><h3>On-Disk Limitations</h3><p>The storage engine must commit the tree to disk to make database systems durable for crashes and power outages.</p><p>Data is stored on the disk in page frames. The data is laid contiguously on the disk and is usually 4KiB in size (defined by the underlying CPU architecture). That is the smallest amount of data that can be written or read programmatically.</p><p>Balanced search trees aren’t suitable for maintaining on disk:</p><ul><li>One reason is locality. Elements are entered in random order, so there’s no guarantee that nodes reside close to one another and may spread across different pages, causing excessive disk accesses.</li><li>The second reason is tree height. Since binary tree nodes only have 2 children, the height of the tree increases relatively fast. For each level, we have to compare and descend to the node below, and in turn, additional disk access.</li></ul><p>Disk accesses are costly, so when designing a data structure that resides on the disk, they have to be kept to a minimum.</p><h3>B-Tree</h3><p>B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, but it generalizes the binary search tree, allowing for nodes with more than two children.</p><p>More formally, each node has between <em>k </em>to <em>2k </em>key-value pairs and <em>k+1</em> to 2<em>k+1</em> child pointers except the root node with as few as <em>2</em> children even when <em>k</em> is a high number.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KUs-6D8xFh7_PxvCgZd3rg.png" /><figcaption>B Tree</figcaption></figure><p>B-Trees are suited for storage systems by solving the 2 problems from earlier.</p><ul><li>Each node is the size of a disk page. The total size of the keys, values and pointers matches 4KiB. The locality is increased as keys and values reside next to each other on the same disk page, so fewer disk accesses are required.</li><li>The tree&#39;s height gets smaller by having more children in each node (also called higher fanout).</li></ul><h3>Searching, Inserting, and Deleting</h3><h4>Searching</h4><p>Searching a B-Tree is done using a binary search. The algorithm starts with the root node and traverses all the keys until it finds the first key greater than the searched value. Then, we descend toward the relevant subtree using the corresponding child pointer and repeat the process until the value is found.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*AkLNXyS7VlIPe6OO.png" /><figcaption>B Tree node</figcaption></figure><p>Range scans are also possible by finding the starting key of the scan and following sibling pointers until the last node is found. This is not optimal as values are spread across many nodes. A better approach is using a B+ tree, a modification of B-Tree.</p><h4>Insertion</h4><p>Insertion is done by performing a search and inserting the value at the correct index. Insertion might cause the tree to get out of balance if a node has too many values (<em>n</em>&gt;<em>2k</em>).</p><p>In that case, the tree will be balanced using node split. Splitting is done by allocating a new node, transferring half of the key-value pairs there, and adding its first key and a pointer to that node to the parent node. If it’s a non-leaf node, then all the child pointers after the splitting point will be moved as well.</p><p>The first key and a corresponding pointer are moved to the parent, thus increasing its occupancy. This might result in overflow again, so rebalancing has to be repeated recursively all the way up the tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*98vwm5DH80XqM3nyYL9ROA.png" /><figcaption>B tree split</figcaption></figure><h4>Deleting</h4><p>When deleting, the target node and the deletion index are located. After removing, a node can get out of balance by having too few values (<em>n</em>&lt;<em>k</em>). It can be solved either by merging nodes or by rotating.</p><p>Rotation can be done to the right or the left, depending on which node has an item to spare. A right rotation, for example, is done by copying the separator key from the parent to the start of the underflow node and replacing the separator key with the last element of its left sibling. When rotating a non-leaf node, the last child pointer of the left sibling is moved to the start of the unbalanced one. A similar approach is made when performing a left rotation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LTygG8hA8eAWHLQK4pgZUQ.png" /><figcaption>B tree rotation</figcaption></figure><p>If no sibling can spare an element (has <em>k</em> elements), the deficient node must be merged with a sibling. The merge causes the parent to lose a separator element, so the parent may become deficient and need rebalancing. Rebalancing may continue all the way to the root.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gf3eRF6MlbEpHSPbG_mw6g.png" /><figcaption>B tree merge</figcaption></figure><h3>Summary</h3><p>This post covered how data structures should accommodate on-disk storage. We started with an explanation about binary trees and how they fall short of being suitable for disk due to having few children and low locality. On the other hand, B-tree solves it by having more items in each node, making keys and values nearby on disk, and the tree shallower.</p><p>Then we covered how to implement find, insert and delete operations and rebalance them when they get out of balance using split, merge, and rebalancing, so the tree depth is kept to a minimum.</p><p>Big credit to Alex Petrov and his book <strong>Database Internals</strong>. The images and most of my knowledge about B Trees are from his book.</p><p>This post was inspired by my in-memory B Tree implementation written in Go. You can check it out <a href="https://github.com/amit-davidson/btree">GitHub</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8c0697856189" width="1" height="1" alt=""><hr><p><a href="https://itnext.io/all-about-b-trees-and-databases-8c0697856189">All About B Trees and Database</a> was originally published in <a href="https://itnext.io/">ITNEXT</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Write a static code analysis tool for detecting race conditions]]></title>
            <link>https://medium.com/@amitdavidson234/write-a-static-code-analysis-tool-for-detecting-race-conditions-e05a49692ab1?source=rss-9269be8f37e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/e05a49692ab1</guid>
            <category><![CDATA[golang]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[static-code-analysis]]></category>
            <category><![CDATA[race-condition]]></category>
            <category><![CDATA[vector-clocks]]></category>
            <dc:creator><![CDATA[Amit Davidson]]></dc:creator>
            <pubDate>Sun, 15 Aug 2021 07:37:02 GMT</pubDate>
            <atom:updated>2021-08-15T07:37:02.596Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/proxy/0*KlKorLzZxaCLa1Rp.jpg" /></figure><p>This blog post walks you through how to implement a static code analysis tool for detecting race conditions. While it is written in Go, for code written in Go, the concepts presented can be applied to any language.</p><p>The tutorial is based on a tool called Chronos that does static code analysis to find race conditions. You can find the code <a href="https://github.com/amit-davidson/Chronos">here</a>.</p><h3>What are race conditions?</h3><h4>Data race</h4><p>First, let’s look at a class of race conditions known as &quot;data race&quot;. It refers to a situation where a memory operation in one thread attempts to access a memory location while a memory operation in another thread is writing to that memory location.</p><pre>func race() {<br>    wait := make(chan struct{})<br>    x:= 0 <br>    go func() {<br>        x++ // read, increment, write <br>        close(wait)<br>    }()</pre><pre>    x++ // conflicting access <br>    &lt;-wait<br>    fmt.Println(n) // Output: &lt;undefined&gt;<br>}</pre><p>In the following example, the two goroutines try to increment the variable “x”. Incrementing isn’t one operation but made from three sub-operations: reading, incrementing, writing the new value. The variable is accessed at the same time, causing the result to be either 1 or 2- an unpredictable behavior.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*qLrVTDnyM_fx33UupVoOxw.png" /></figure><p>We would have to use a mutex to guarantee that the variables are accessed at separate times to solve it.</p><pre>func norace() {<br>    wait := make(chan struct{})<br>    x:= 0 <br>    mutex := &amp;sync.Mutex{}<br>    go func() {<br>        mutex.Lock()<br>        x++<br>        mutex.Unlock()<br>        close(wait)<br>    }()</pre><pre>    mutex.Lock()<br>    x++<br>    mutex.Unlock()<br>    &lt;-wait<br>    fmt.Println(n)<br>}</pre><h4>Race condition</h4><p>The second type is when the program behavior is dependent on the sequence or timing of the program’s processes or threads.</p><pre>func race() {<br>    x := 0<br>    go func() {<br>        x = 1<br>    }()<br>    if x == 1 {<br>        fmt.Println(&quot;Success&quot;)<br> }<br>}</pre><p>In this example, the problem is <strong>order</strong>. The expectation is for the goroutine to finish before the condition is evaluated as it starts before, but in reality, it might complete after so the assignment won’t happen in time. A mutex won’t solve it as it only handles mutual exclusion. The solution is to use a syncing mechanism such as an unbuffered channel, waitgroup, etc.</p><pre>func norace() {<br>    c := make(chan bool)<br>    x := 0<br>    go func()<br>        x = 1<br>        c &lt;- true<br>    }()<br>    &lt;-c<br>    if x == 1 {<br>        fmt.Println(&quot;Success&quot;)<br>    }<br>}</pre><h3>Detecting race conditions</h3><p>Now that we know how to find race conditions and solve them, we need an algorithm to do it programmatically.</p><p>In Chronos, we use “guarded access” to record each memory access. Guarded accesses are collected and compared. write-write or read-write accesses from different goroutines that are not guarded by mutexes or other syncing mechanisms are flagged as race conditions.</p><p>Guarded access contains data about the access that is flow-agnostic- it’s related to the memory access itself and is the same between flows:</p><ol><li><strong>Access kind</strong>- Write/Read and Write/Write memory accesses are considered race conditions so we can tell if two memory accesses are conflicting or not.</li><li><strong>Code position</strong> (from the beginning of the program)- Position serves as an id for memory access.</li><li><strong>value modified</strong>- Used to tell when the same value is being accessed when comparing memory accesses.</li></ol><p>and the data related to the flow (goroutine):</p><ol><li><strong>Goroutine id- </strong>Goroutine id serves as an id for the flow.</li><li><strong>Stacktrace</strong>- Used when printing the results the explain the flows easily.</li><li><strong>mutexes</strong> acquired/released (lockset)</li><li><strong>vector clock</strong>- will be explained later</li></ol><p>If we take the memory access “x:=0” for example, the guarded access is:</p><pre>func guardedaccess() {<br>    x := 0<br>    go func() {<br>        x = 1<br>    }()<br>}</pre><ul><li>write</li><li>position- 60</li><li>value modified- x</li><li>goroutine id- 2</li><li>stack trace- guardedaccess-&gt;func1-&gt;”x=1&quot;</li><li>mutexes- none</li><li>vector clock- irrelevant</li></ul><h4>Detecting mutexes</h4><p>Same as memory accesses, we track mutex locks and unlocks in a data structure called <strong>lockset</strong>. Each goroutine holds its own lockset, and it contains the locks that have been acquired or released so far.</p><pre>func locks() {<br>    m := sync.Mutex{} // lockset: {locks:{}, unlocks:{}}<br>    m.Lock()          // lockset: {locks:{m}, unlocks:{}}<br>    m.Unlock()        // lockset: {locks:{}, unlocks:{m}}<br>    a := 5            // lockset: {locks:{}, unlocks:{m}}</pre><p>If the code contains branches, a join operation is made between the branches when a mutex is acquired inside it. In other words, for the mutex to be considered as locked, all branches must acquire it. On the other hand, when a release is made in one of the branches, a union is performed on the branches, so one release is sufficient for it be considered unlocked.</p><p>This algorithm is sound but not precise- it will flag more race conditions for the loss of accuracy. It suffices for one branch to release a lock but all branches must acquire a lock for it to be consider locked. It means that locks will be unlocked more often so less guarded accesses are “defended” by mutexes hence more race conditions being flagged.</p><pre>func mutexes() {<br>    m := sync.Mutex{}   // lockset: {locks:{}, unlocks:{}}<br>    if rand.Int() &gt; 0 { // lockset: {locks:{}, unlocks:{}}<br>        m.Lock()        // lockset: {locks:{m}, unlocks:{}}<br>    } else {<br>        fmt.Println(&quot;Lock wasn&#39;t acquired&quot;)<br>    }<br>    if rand.Int() &gt; 0 { // lockset: {locks:{}, unlocks:{}}<br>        m.Unlock()      // lockset: {locks:{}, unlocks:{m}}<br>    } else {<br>        fmt.Println(&quot;Lock was released&quot;)<br>    }<br>    if rand.Int() &gt; 0 { // lockset: {locks:{}, unlocks:{m}}<br>        m.Lock()        // lockset: {locks:{m}, unlocks:{}}<br>    } else {<br>        m.Lock()        // lockset: {locks:{m}, unlocks:{}}<br>    }<br>                        // lockset: {locks:{m}, unlocks:{}}<br>}</pre><p>In the first condition, the lock was acquired only inside the branch, but it’s not relevant anymore since it wasn’t acquired in all branches. As opposed, when doing union across the branches of the second condition, we still have the unlock since an unlock in at least one branch is sufficient. Finally, in the last condition, the lock is acquired in all branches, so the lock operation counts, and the mutex isn’t flagged as released anymore.</p><h4>Vector clocks</h4><p>We need to look at vector clocks to understand how to trace channels, waitgroups, and the rest of the order syncing mechanisms.</p><p><a href="https://en.wikipedia.org/wiki/Vector_clock">A vector clock</a> is a data structure used for determining the partial ordering of events in a distributed system. In other words, it helps to track the order of events between different goroutines and create a happen before/after relationship between each other.</p><p>Each goroutine has its own vector clock. The vector clock has the ids of the other goroutines and maps between them to the number of events (memory accesses) taken in each goroutine.</p><ol><li>Initially, all clocks are zero.</li><li>Each time a goroutine has memory access, it increments its own logical clock in the vector by one.</li><li>Each time a goroutine communicates with another one, it increments its own logical clock in the vector by one and sends its own clock as well.</li><li>When the other goroutine receives it, it increments its own logical clock in the vector by one and updates each element in its vector by taking the maximum value in its own vector clock and the value in the received vector.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mEbp0WNyhr8BswmMdc0Wjw.png" /></figure><p>In the above example, we have the proccesses p1,p2 and p3. Each process has it’s own empty clock. Every time an event happpens, a proccess increments it’s own clock in the vector. When we sync, as in p1-&gt;p2, p1 increments it’s own clock and send it to p2. p2 increments it’s clock and take the maximum number for each clock in the vector.</p><h4>Putting it in the code</h4><pre>func norace() {<br>                               // VC1: {1:0}<br>    c := make(chan bool)       // VC1: {1:1}<br>    x := 0                     // VC1: {1:2}<br>    go func() // Clock synced! // VC1: {1:3, 2:0} VC2: {1:3, 2:0}<br>        x = 1                  // VC1: {1:3, 2:0} VC2: {1:3, 2:1}<br>        c &lt;- true              // VC1: {1:3, 2:0} VC2: {1:3, 2:2}<br>    }()<br>    &lt;-c       // Clock synced! // VC1: {1:3, 2:2} VC2: {1:3, 2:2}<br>    if x == 1 {                // VC1: {1:4, 2:2} VC2: {1:3, 2:2}<br>        fmt.Println(&quot;Success&quot;)<br>    }<br>}</pre><p>The clocks were synced twice. When we created a new goroutine and the other when the message was sent to the unbuffered channel. To avoid complications, in Chronos, clocks are synced only when a new goroutine is created.</p><p>Once we have the vector clocks, we can create the relationship between the memory accesses- they happened one after another or are in parallel, hence a race condition. To do that, we can consider the following clocks VCᵢ {c1ᵢ,c2ᵢ} and VCⱼ{c1ⱼ,c2ⱼ} where VCᵢ and VCⱼ are the clocks and inside are vector components for each clock. Event e₁ has the clock VCᵢ and event e₂ has the clock VCⱼ.</p><ul><li>e₁ is before e₂ (e₁&lt;e₂) if c1ᵢ&lt;c1ⱼ and c2ᵢ≤c2ⱼ e₁ : {5,2} e₂:{4,2}</li><li>e₁ is after e₂ (e₁&gt;e₂) if c1ᵢ&gt;c1ⱼ and c2ᵢ≥c2ⱼ e₁ : {7,2} e₂:{4,1}</li><li>If none, they are concurrent (e₁||e₂) to each other e₁ : {3,2} e₂:{4,1}</li></ul><p>In the example above, the write of “x=1” precedes the read “x==1” in the condition, because for “VCᵢ: {1:4, 2:2} VCⱼ: {1:3, 2:2}” 4&gt;3 and 2≥2.</p><p>On the other hand, if we didn’t send a message through the channel, the clocks weren’t synced, and we can conclude the read and writes are parallel to each other. “VCᵢ: {1:3, 2:0} VCⱼ: {1:2, 2:1}” 3&gt;2 but 0≥1 isn’t true.</p><pre>func norace() {<br>                         // VC1: {1:0}<br>    x := 0               // VC1: {1:1}<br>    go func()            // VC1: {1:2, 2:0} VC2: {1:2, 2:0}<br>        x = 1            // VC1: {1:2, 2:0} VC2: {1:2, 2:1}<br>    }()<br>    if x == 1 {          // VC1: {1:3, 2:0} VC2: {1:2, 2:1}<br>        fmt.Println(&quot;Success&quot;)<br>    }<br>}</pre><h4>Summary</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fqzs2C7TxXGXrIg5TjSJqw.png" /></figure><h3>Performing static analysis</h3><p>We know how to detect race conditions once we have the information about the guarded accesses, the mutexes, and the syncing mechanism. But the question is how to infer it from the code. In this part, we will talk about how to perform static analysis.</p><h4>SSA</h4><p><a href="https://en.wikipedia.org/wiki/Static_single_assignment_form">SSA</a> stands for static single assignment. It’s a representation of the code compilers use when doing optimization by requiring each variable only to be assigned once.</p><pre>y = 1        y1=1<br>y = 2 -----&gt; y2=2<br>x = y        x1=y2</pre><p>“y” is declared twice and is assigned each time to ensure the assignment only happens once.</p><p>In Go, the package <a href="http://golang.org/x/tools/go/ssa">tools/ssa</a> can generate SSA code, allowing us to use the generated code from within our code!</p><h4>Basic block</h4><p>In the package, functions are represented using the following struct:</p><pre>type Function struct {<br>    Signature *types.Signature<br>    Pkg       *Package          // enclosing package<br>    Prog      *Program          // enclosing program<br>    Params    []*Parameter      // function parameters<br>    Blocks    []*<a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#BasicBlock">BasicBlock</a>     // basic blocks of the function<br>...<br>}</pre><p>Signature, Pkg, Prog, and Params are self explanatory, but what are Blocks (Basic blocks)? In SSA, functions are divided into basic blocks where each block is multiple lines of code without branches. This makes it highly amenable to analysis.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rC8d0BTwdtHPkHs32VL4oA.png" /></figure><pre>type BasicBlock struct {<br>    Index   int                // index of this block within<br>                               // Parent().Blocks<br>    Instrs       []<a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#Instruction">Instruction</a> // instructions in order<br>    Preds, Succs []*<a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#BasicBlock">BasicBlock</a> // predecessors and successors<br>}</pre><p>Using “Preds” (predecessor) and “Succs” (successor), the blocks create the control flow graph (CFG) of the function. A graph that represents all the paths that might be traversed during execution. This way, we can mimic the execution of how the code might run.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G00j1auvO77yGobia56rvQ.png" /></figure><h4>Instructions</h4><p>A block has a set of instructions. “Instruction“ is an interface for representing all possible instructions in Go such as “ssa.BinOp”, “ssa.TypeAssert”, “ssa.Go”, and so on.</p><pre>type Instruction interface {<br>    String() string<br>    Parent() *<a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#Function">Function</a><br>    Block() *<a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#BasicBlock">BasicBlock</a><br>    Operands(rands []*Value) []*<a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#Value">Value</a><br>    Pos() <a href="https://pkg.go.dev/go/token#Pos">token.Pos</a><br>}</pre><p>Operands and Pos are the most important. Operands() returns the values used in the instruction, and Pos() returns the position in the code.<br>Now, it’s possible to fill the position and the value when creating a guarded access for the memory access. Also, according to the instruction, we can deduce if it’s a read or a write.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HMtri32Da8cJqRALQV_93Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cYVAesFhSgn5biOP7IQ5LQ.png" /></figure><h4>Putting it all together</h4><p>Let’s consider the following code. We don’t have any branches in our code, so there’s only a single basic block. We iterate over the instructions of the basic block until we find the ones that are interesting to us.</p><pre>func norace() {<br>    wait := make(chan struct{})<br>    x:= 0 <br>    mutex := &amp;sync.Mutex{}<br>    go func() {<br>        mutex.Lock()<br>        x = 5<br>        mutex.Unlock()<br>        close(wait)<br>    }()</pre><pre>    mutex.Lock()<br>    x++<br>    mutex.Unlock()<br>    x=4<br>    &lt;-wait<br>    fmt.Println(n)<br>}</pre><p>For “x=5” it’s the “Store” instruction.</p><pre>type Store struct {<br>	Addr <a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#Value">Value</a><br>	Val  <a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#Value">Value</a><br>	// contains filtered or unexported fields<br>}</pre><p>To create the guarded access, the operation is “write”, the position is 132, and the value accessed is “Addr”- x.</p><p>For the mutex, we can look for “ssa.Function” instruction as we have already seen before and check if the call is made to “(*sync.Mutex).Lock” or “(*sync.Mutex).Unlock”. Then we can add it to the lockset and attach it to the guarded access.</p><p>Finally, for the vector clock, we can look for the “ssa.Go” instruction. Then we sync the clocks by adding a new entry for the vector clock of the main goroutine for the new goroutine and copy the vector clock to the new one. The clock is incremented every time memory access is performed inside the goroutine and added to the guarded access when it’s created.</p><pre>type Go struct {<br>	Call <a href="https://pkg.go.dev/golang.org/x/tools/go/ssa#CallCommon">CallCommon</a><br>	// contains filtered or unexported fields<br>}</pre><p>Only the value, the vector clock, the lockset and read/write are relevant when comparing guarded accesses. We can do the same for all the memory accesses to “x”.</p><ul><li>x := 0 — write, vc: {1:2}, ls: {}</li><li>x = 5 — write, vc:{1:3, 2:1}, ls: {locks:[mutex], unlocks:[]}</li><li>x ++ — write, vc:{1:4, 2:0}, ls: {locks:[mutex], unlocks:[]}</li><li>x =4 — write, vc:{1:5, 2:0}, ls: {locks:[], unlocks:[mutex]}</li></ul><p>Then we compare guarded accesses from different goroutines:</p><ul><li>x = 5 and x:=0 don’t conflict as {1:3, 2:1} &gt; {1:2}</li><li>x=5 and x++- don’t conflict as they are both guarded by the same lock</li><li>x=5 and x=4- x=4 isn’t guarded by any locks and the vector clocks are {1:3, 2:1} || {1:5, 2:0} so that’s a race condition.</li></ul><h4>Conclusion</h4><p>This post covered the implementation points in an abstract way. It also didn’t cover how to traverse the control flow graph if there are branches or handle race conditions of variables from different functions. I decided not to go into those topics as they are complex. I hope you will have a look at <a href="https://github.com/amit-davidson/Chronos">the source code</a> if you are interested.</p><p>If you have any questions or feedback or found out mistakes, it would be great if you could contact me <a href="https://github.com/amit-davidson">in any way you like</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e05a49692ab1" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>