DEV Community: Quame Jnr

Binary Search Trees: Why They’re Great in Memory but Terrible on Disk

Quame Jnr — Thu, 05 Feb 2026 22:05:13 +0000

Binary search trees (BST) are in-memory sorted data for efficient lookups. They have 2 children nodes, ergo the name binary. For each node, all values of nodes to the left should be less than the node and all values of nodes to the right should be greater than the node.

This is good because it allows you to do O(log N) search since the tree has O(log N) height. For a tree like ours above with 4 elements, in the worst case you traverse O(log 4) = 2 to find your target since the height is 2. However, BSTs can also be at the mercy of the insertion order, thus we need to constantly rebalance the tree.

Tree Balancing

If we insert numbers [1, 2, 3] then without rebalancing, insertions will determine the tree structure leading us to Fig A. This means O(N) searches, thus defeating the purpose of BST. A BST is seen as unbalanced if the difference between the heights of the two subtrees is greater than 1. We can rebalance by doing a rotation pivot to get Fig B.

Why does it Suck as Disk-Based Storage?

1. Random Insertion Order

Each new node is allocated any free disk space and the pointer from its parent This means a node can be far away from its parent node, thus no benefits of locality.

So here's the thing: when the OS is loading data into memory, it doesn't just load the target data, it loads in certain sizes, let's say 16KB. This contiguous segment of memory will contain your target data but also neighboring data. Ergo, if the next data the CPU has to operate on is closer to your target data, it might already be loaded in memory. Since BST puts nodes in any free space, it means you don't benefit from this as your child node might be in another segment of the disk.

2. Fanout of 2

BST having binary nodes means a higher number of elements leads to higher height, and higher height means a higher number of traversals during search. So given 1 million elements, you will have a height of ~20, which means 20 traversals. Coupled with the data being in random disk locations means you have to do a disk seek for each node, read the data to find the pointer to the child node if it's not your target element, and then do another disk seek, another page transfer to read the data, over and over again.

Also, keep in mind that the tree may rebalance during insertions, thus you can't cache pathways to a node as they may change.

Conclusion

BSTs are elegant for in-memory operations; O(log N) searches with simple pointer-chasing works great when everything's in RAM. But the moment you move to disk, those same properties become liabilities. Random allocation kills locality, binary fanout means excessive tree height, and every pointer dereference potentially triggers a disk seek.

This is why disk-based databases don't use binary search trees. Instead, they use B-trees and B+ trees with high fanout (hundreds of children per node instead of 2) and nodes sized to match disk pages. A B-tree with the same 1 million elements? Height of ~3 instead of ~20. That's the difference between 3 disk reads and 20.

Sometimes data structures that work brilliantly in one context can be completely wrong for another.

Database Management System (DBMS) Architecture Explained

Quame Jnr — Mon, 26 Jan 2026 09:56:55 +0000

Most modern database management systems follow a client–server architecture. The database acts as the server, responsible for storing, processing, and protecting data, while applications act as clients that send requests, usually SQL queries, over the network.

At a high level, a DBMS can be broken into four major components:

Query Processor
Query Optimizer
Execution Engine
Storage Engine

Query Processor

The query processor is responsible for understanding and validating incoming SQL queries before any data is touched.

Query Parser

When a client sends a SQL query, it is first passed from the transport layer to the query parser. The parser’s job is to ensure that the query is valid and meaningful.

This happens in several stages:

Lexical analysis: The raw SQL string is broken into tokens such as keywords, identifiers, operators, and literals.
Syntax checking: The parser verifies that the tokens follow the grammar rules of SQL.
Semantic analysis: The database checks that referenced tables, columns, functions, and operations actually exist and make sense.
Access control checks: The system ensures the user has the required permissions on the referenced objects.

If all checks pass, the parser produces an abstract syntax tree (AST). This is then transformed into a logical query plan, which represents the query in relational terms and is passed to the query optimizer.

Query Optimizer

The query optimizer’s goal is to find the most efficient way to execute the query.

Given a logical query plan, the optimizer generates multiple physical execution plans. These plans may differ in join order, join algorithms, index usage, or access paths. Each plan is assigned a cost, and the plan with the lowest estimated cost is chosen.

Cost is an estimate of how expensive a query plan is to run. Lower cost usually means faster execution.

How Cost Estimation Works

The optimizer relies heavily on database statistics, such as:

Number of rows in a table
Number of distinct values per column
Data distribution and histograms
Index availability
Percentage of NULL values

Using these statistics, the optimizer estimates:

I/O cost (disk reads and writes, typically the most expensive)
CPU cost (hashing, comparisons, sorting)
Memory usage

For very large tables, collecting exact statistics can be expensive. To manage this, many databases sample random data pages and extrapolate statistics from the sample. This balances accuracy with performance.

Execution Engine

The execution engine is responsible for actually running the chosen execution plan.

It walks the execution plan tree and executes each operator, such as:

Table scans or index scans
Filters and projections
Joins
Sorting and aggregation
Set operations

During execution, the engine:

Requests data pages from the storage engine
Manages memory for operations like sorting and hashing
Handles set operations and aggregations
Formats the final result set and returns the result back to the client.

Storage Engine

The storage engine handles how data is physically stored, retrieved, and protected on disk. It has several components:

Buffer Manager: Caches frequently accessed data pages in memory to reduce disk I/O.
Access Methods: Define how data is organized and accessed on disk, supporting structures such as sequential files, B-Trees, and LSM Trees.
Transaction Manager: Enforces ACID properties, ensuring that transactions are atomic, consistent, isolated, and durable.
Lock Manager: Coordinates concurrent access to data. In many modern systems, this is implemented using MVCC (Multi-Version Concurrency Control) rather than traditional locking.
Recovery Manager: Manages write-ahead logging (WAL) and ensures the database can recover to a consistent state after crashes or failures.

A page is the fundamental unit of storage in a database. Each page contains multiple rows, with the exact number depending on page size and row layout.

Conclusion

A DBMS is more than just a place to store data. From parsing SQL into a syntax tree, turning it into a logical plan, optimizing for best execution paths, managing memory, ensuring consistency and recovery from crashes, each layer has a critical role.

Undertanding this architecture will help you write better queries and give you insights into performance, debugging and designing systems at scale.

Why Columnar Storage Makes Analytics Faster

Quame Jnr — Mon, 19 Jan 2026 11:46:50 +0000

Traditional databases store data row by row, which works well for many applications. But for analytics, most queries only touch one or two columns. Storing data by column is often much more efficient because each column is stored contiguously in memory, making it faster to load and process.

// Row storage
Row 0: [1, "Alice", "Engineering", 95000]
Row 1: [2, "Bob", "Sales", 87000]
Row 2: [3, "Carol", "Engineering", 102000]

// Columnar storage
ids:         [1, 2, 3]
names:       ["Alice", "Bob", "Carol"]
departments: ["Engineering", "Sales", "Engineering"]
salaries:    [95000, 87000, 102000]

A query like the one below becomes much faster since only the relevant columns are loaded and processed:

SELECT AVG(salary) FROM employees WHERE department = 'Engineering'

Why Queries Are Faster with Columns

Memory & cache efficiency
- Each column is stored contiguously, so loading a single column is fast.
- Smaller memory footprint means only the data you need is loaded. This also fits better in CPU caches.
Compression & storage
- Columns contain the same data type, often with repeated values, making them ideal for compression. For example, a column storing categories, gender or nationality will have low cardinality
- Algorithms like run-length encoding (RLE) or dictionary encoding handle this repetitive data extremely efficiently.
Vectorized processing (SIMD)
- CPUs can apply the same operation to multiple values in a column at once, speeding up aggregation and analytics.

This is one reason OLAP systems handle large-scale analytics much more efficiently than OLTP systems.

Understanding Prometheus Storage: From Scrape to Disk

Quame Jnr — Sun, 23 Nov 2025 18:32:05 +0000

Prometheus is a time series monitoring system built for metrics and alerting. For people curious about how Prometheus works under the hood, this post will guide you through how Prometheus scrapes data, accumulates it in memory, and eventually persists it to disk.

The Data Flow: From Metrics to Disk

┌──────────┐
│ Scrape   │  (Pull metrics from targets)
└────┬─────┘
     │
     ↓
┌──────────┐
│  Parse   │  (Parse response, create series)
└────┬─────┘
     │
     ↓
┌──────────────┐
│   Batch      │  (Temporary, request-scoped buffer)
└────┬─────────┘
     │
     ├──→ [WAL] (Write to durability log)
     │
     ↓
┌─────────────────────┐
│ Head (In-Memory)    │  (Mutable chunks, queryable)
│ 2-hour window       │
└────┬────────────────┘
     │ (after 2 hours)
     ↓
┌──────────────────────┐
│  Block (On Disk)     │  (Immutable, compressed)
│ - metadata           │
│ - index              │
│ - chunks (512MB)     │
└──────────────────────┘

Note: This entire cycle (scrape → parse → batch → WAL → Head) repeats every 15 seconds by default (configurable via the scrape_interval setting). This means the Head continuously accumulates samples, with 240 scrapes per hour appending to series chunks.

Scraping & Parsing

Prometheus queries the /metrics endpoint of target systems, receiving responses in a text-based format. Here's an example:

http_requests_total{job="api", instance="server1"} 100
http_requests_total{job="api", instance="server2"} 200
http_requests_total{job="web", instance="server1"} 50

Prometheus parses this response line by line. Each unique combination of metric name + label key-value pairs becomes a series. In this example, we have one metric (http_requests_total) but three different series because the labels differ.

This series-based organization allows Prometheus to track and query metrics independently by their labels. Now that we have series, they're temporarily collected into a batch before being processed further.

The Batch

The batch is a temporary buffer that holds all the samples from a single scrape cycle. Once the scrape completes, Commit() is called on the batch, triggering two operations: first, the data is written to a Write-Ahead Log (WAL) for durability, then it's appended to the in-memory Head for querying.

Batching is more efficient than writing samples individually, all samples are written together in one operation, reducing I/O overhead. It's also atomic: either all samples from a batch succeed or none do, ensuring consistency.

The Write-Ahead Log (WAL)

Before any data is stored in memory or on disk, Prometheus writes it to a Write-Ahead Log (WAL) file. Think of the WAL as a journal: it records encoded data structures (called records) sequentially on disk. These records include:

Series records (metric names and labels)
Sample records (sample values and timestamps)
Metadata records (metric metadata and exemplars)

Why is the WAL critical?

If Prometheus crashes (power outage, Out of Memory (OOM), restart), unsaved data in memory is lost. The WAL acts as a safety net. When Prometheus restarts, it replays these records from the WAL to recover all uncommitted samples and rebuild the in-memory state. This ensures durability: no data loss.

The WAL typically uses segments of ~128MB each (configurable). These files are stored on disk and can be replayed if needed. After records are written to the WAL successfully, it's safe to update the in-memory Head, knowing that even if the system crashes next second, that data can be recovered.

The Head (In-Memory)

The Head is Prometheus's in-memory mutable storage. It contains multiple series, and each series tracks its own list of chunks: compressed, time-ordered collections of samples. New samples are constantly appended to existing series, growing the chunks until they fill up, at which point new chunks are created.

The Head keeps data in memory for a configurable time window (default: 2 hours). This design has tradeoffs:

Benefit: In-memory storage enables fast writes and queries. Answering questions like "What was the CPU usage 5 minutes ago?" is immediate since data is already in RAM.
Cost: More unique series means more memory usage. This is why Prometheus can suffer from high memory consumption with high-cardinality metrics (thousands or millions of unique series due to many label combinations).

Why does cardinality matter? Each series stores its labels (metric name + key-value pairs), a unique ID, and its list of chunks. When you have many unique series, each one consumes memory for storing label strings and chunk metadata. For example, a single metric with 1,000 unique label combinations = 1,000 separate series, each with its own label data and chunk pointers. This is why high-cardinality metrics can quickly exhaust memory.

After 2 hours of data accumulation, the Head is sealed and flushed to disk as an immutable block. This move from memory to disk is critical for long-term storage and frees up memory for new incoming data.

Blocks (On Disk)

A block is a directory containing all the time-series data from a 2-hour window in a compressed, queryable format. Once sealed, blocks are immutable and stored on disk for long-term retention.

Block Structure:

metadata file: Contains metadata about the block (time range, number of series, etc.)
index file: Maps metric names and labels to their corresponding series, enabling fast lookups during queries.
chunks directory: Contains the actual time-series data. While each chunk belongs to a single series, multiple chunks from different series are packed together into segment files (512MB each by default) for efficient storage and retrieval.

Why are blocks immutable?

Immutability is key to Prometheus's design. Once a block is written to disk, it never changes. This enables compaction: the process of merging multiple blocks together. For example, you might merge 30 blocks from 30 days into fewer, larger blocks, reducing disk usage and improving query performance. Immutability ensures compaction is safe: no concurrent writes can conflict with the merge operation.

This immutable-block architecture is one reason Prometheus is so efficient: old data is read-only, allowing aggressive optimization without worrying about concurrent modifications.

Conclusion

Now you understand the journey of data in Prometheus. Every 15 seconds, metrics are scraped, parsed into series, collected into a batch, written to the WAL for durability, appended to the in-memory Head for fast queries, and then sealed to disk as immutable blocks after 2 hours.

This architecture is elegant: it balances speed, durability, and long-term storage. The in-memory Head enables sub-millisecond query responses for recent data. The WAL ensures no data loss on crashes. Immutable blocks on disk enable efficient compaction and long-term retention without sacrificing query performance.

The tradeoff? Memory usage scales with cardinality. Understanding this design helps you make better decisions when monitoring with Prometheus, whether it's designing your metric labels, configuring retention, or troubleshooting performance.

Prometheus: The Essential Guide to Monitoring Systems

Quame Jnr — Thu, 06 Nov 2025 08:22:39 +0000

What is Prometheus?

Prometheus is an open-source systems monitoring and alerting toolkit originally built at SoundCloud. It collects metrics as time series data, numerical measurements stored with timestamps and optional key-value pairs called labels. Since joining the Cloud Native Computing Foundation in 2016, it has become a standalone project with an active community.

History and Relevance Compared to Older Tools

When monitoring tools like Nagios (1999), Zabbix (2004), and Graphite emerged, they were designed for stable, on-premises environments with fixed servers. As cloud computing and microservices grew popular with containers and services scaling dynamically these tools faced challenges.

Their limitations included push-based architectures, where agents sent data to a central system, leading to configuration issues in changing setups and missed data from short-lived jobs. They lacked multi-dimensional labels for flexible data analysis, and querying was limited. Storage was often absent or added separately.

Prometheus addressed these by using a pull model to retrieve metrics, enabling auto-discovery. Its labels and PromQL query language allowed rich data exploration, while self-contained storage ensured reliability. Joining the CNCF in 2016, it became key for Kubernetes and modern infrastructures, offering better adaptability.

Why Use Prometheus?

Prometheus helps monitor system and application performance, such as CPU usage, RAM usage, network traffic, and request counts. It alerts you to issues like sudden RAM or CPU surges, memory leaks, or high error rates. This is especially useful for dynamic, service-oriented architectures where traditional monitoring falls short.

It excels in:

Machine-centric monitoring: Tracking hardware metrics like CPU, memory, and disk usage.
Application monitoring: Measuring request latency, error rates, and throughput.
Microservices architectures: Handling dynamic environments with multi-dimensional data (e.g., labeling by service, version).
Alerting: Triggering notifications for thresholds (e.g., "RAM usage > 90%").
Reliability during outages: Standalone design allows diagnosis when other systems fail.

However, it's not ideal for 100% accurate billing data, as it prioritizes reliability over completeness in failure scenarios.

How Does It Work?

Prometheus performs three main functions:

Retrieves data: Uses a pull model over HTTP to scrape metrics from endpoints (typically /metrics).
Stores data: Saves metrics in a time series database with timestamps and labels.
Queries data: Provides an HTTP API for querying via PromQL, a flexible query language.

To expose metrics, applications use client libraries or exporters like the Node Exporter for system data. For short-lived jobs, a push gateway allows pushing metrics that Prometheus then scrapes. The Alertmanager handles alerts by routing them to channels like Slack or email.

Metric Types in Prometheus

Prometheus uses four metric types:

Counter: How many times something happened (e.g., number of requests).
Gauge: The current value of something that can go up or down (e.g., CPU or memory usage).
Histogram: How long or big something is (e.g., request latency).
Summary: Pre-computed percentiles for distributions.

Architecture

Prometheus scrapes metrics from instrumented jobs directly or via the push gateway. It stores samples locally and runs rules for aggregation or alerting. Visualization tools like Grafana query the data via the API.

At its core, Prometheus handles three key functions: retrieving metrics (scraping), saving metrics (storing in TSDB), and querying metrics (via HTTP API).


┌─────────────────┐          ┌──────────────────────────────┐          ┌─────────────┐
│                 │          │     PROMETHEUS SERVER        │          │             │
│  Instrumented   │─ Pull ──▶│                              │◀─ Query ─│   Grafana   │
│      Jobs       │          │  ┌────────────────────────┐  │          │             │
│   (/metrics)    │          │  │   1. Retrieval         │  │          └─────────────┘
└─────────────────┘          │  │      (Scrape)          │  │
                             │  └──────────┬─────────────┘  │
┌─────────────────┐          │             │                │          ┌─────────────┐
│                 │          │             ▼                │          │             │
│  Push Gateway   │─ Pull ──▶│  ┌────────────────────────┐  │─ Alert  ─│ Alertmanager│
│  (short-lived)  │          │  │   2. Storage (TSDB)    │  │          │             │
└─────────────────┘          │  └──────────┬─────────────┘  │          └──────┬──────┘
        ▲                    │             │                │                 │
        │ Push               │             ▼                │                 │
┌─────────────────┐          │  ┌────────────────────────┐  │                 ▼
│  Short-lived    │          │  │   3. Query (HTTP API)  │  │          ┌─────────────┐
│     Jobs        │          │  │      PromQL            │  │          │ Slack/Email │
└─────────────────┘          │  └────────────────────────┘  │          └─────────────┘
                             │                              │
┌─────────────────┐          │  ┌────────────────────────┐  │
│                 │          │  │   Rules Engine         │  │
│    Exporters    │─ Pull ──▶│  │   (Aggregation +       │  │
│  (Node, etc.)   │          │  │    Alerting)           │  │
└─────────────────┘          │  └────────────────────────┘  │
                             └──────────────────────────────┘

Components

The Prometheus ecosystem includes:

Prometheus server: The core engine that scrapes, stores, and queries metrics using a time series database.
Client libraries: SDKs for languages like Go, Python, or Java to instrument application code and expose custom metrics.
Push gateway: An intermediary for short-lived jobs (e.g., batch scripts) to push metrics, which Prometheus then scrapes.
Exporters: Specialized tools that collect metrics from external systems (e.g., Node Exporter for OS stats, HAProxy for load balancers) and expose them in Prometheus format.
Alertmanager: Handles alert routing, deduplication, and notifications to channels like Slack or email.
Support tools: Utilities for tasks like configuration validation, data migration, or federation with other Prometheus instances.

Conclusion

Prometheus is a powerful, flexible tool for modern monitoring, especially in dynamic environments like microservices and Kubernetes. It addresses many limitations of older tools through its pull model, labels, and query language.

Virtual Machines: How One Computer Becomes Many

Quame Jnr — Mon, 08 Sep 2025 15:20:24 +0000

Introduction

Virtual machines (VM) virtualize the hardware of a physical computer (like CPU, RAM, storage) to allow multiple isolated operating systems (OS) on the physical computer.

Brief History

Before the age of personal computing, computers used to be these large mainframes that were being used in big organizations and schools like MIT. These mainframes had relatively a lot of resources at that time and thus to use resources efficiently and reduce idle time, Compatible Time Sharing System (CTSS) was introduced

In the early 1960s, researchers on MIT's Project MAC introduced CTSS. CTSS allowed multiple users to use the same computer at the same time giving them the illusion that they are the only ones who had access to the computer at the time. It provided some form of isolation protecting your personal files but you still used the same applications and OS on the machine.
In the 1960s, IBM introduced the CP-40, an experimental time sharing project that laid the groundwork for VMs. It took CTSS a step further by using virtualization to give users the illusion that they had their own dedicated machine. Users could run multiple isolated computing sessions on the machine giving them greater control, flexibility and isolation.
Building on the CP-40 experiment, IBM released VM/370 in August 1972, which became the first commercial virtual machine system. This marked the true beginning of virtualization as we know it today.

This early virtualization concept from VM/370 evolved over decades, eventually becoming the foundation for today's hypervisor technology.

How does it work

Virtual machines use what we call a hypervisor to create virtualized hardware that allows operating systems to run in isolation over a physical computer's hardware. This allows different operating systems to run on top of the computer hardware unaware it is not directly on the physical machine. The process involves 3 components.

Components

The host machine: This is the physical computer that provides the hardware resources.
The guest machine: This is the virtual machine that will be running on top of the host machine.
Hypervisor: This sits between the host and guest machine and acts as a translator. It acts as a translator managing host's resources to the guest VMs.

Process

Assuming the guest operating system wants to write to a file in the virtual hard disk, it will issue a syscall to perform the action just as it would on a physical machine.

Intercepting requests: The hypervisor will intercept the request coming from the guest machine.
Translating requests: The hypervisor will translate the request to the host machine. In this case, it ensures the file the guest machine is trying to write into maps to the specific folder on the physical drive. This is because virtual machines, its configs and applications all exist in a specific folder on your drive. It also translates the commands into instructions the host computer can understand.
Resource allocation: The hypervisor will manage and allocate resources to the guest VM from the host's pool and ensure each VM is isolated.
Returning Results: Once the physical machine is done performing the action, the hypervisor translates back to the format the guest OS can understand.

Types of Hypervisors

Hypervisors are of two different types based on where they sit on the stack.

Type 1: In type 1, the hypervisor runs directly on the bare metal hardware without a traditional host OS underneath it. This makes it fast and efficient. This is mostly used in enterprise data centers and cloud environments. Eg. VMware ESXi.
Type 2: Type 2 hypervisors are installed as an application on the host machine's OS. This adds an extra layer as the hypervisor has to translate requests through the host OS instead of directly to the hardware. This is simple to install and mostly used by developers for testing in a different OS and playing around safely in a different OS. Eg. VirtualBox

Why should you care?

VMs are incredibly useful, they provide isolation, flexibility and portability and these are some of the reasons I think you should care;

Sandboxing

VMs create the ultimate sandbox if you're a developer or curious. You can use it to;

test untrusted software
mess around with system configs
test your program on multiple operating systems

Running Multiple Operating Systems

if you are Mac user, curious about linux, you can install it on a VM without having to partition your disks
you can try out platform specific applications without having to switch your host OS.

Conclusion

Virtual machines are ubiquitous albeit abstracted. When you create an instance on AWS, you are creating a virtual machine on one of Amazon's big machines and you are not alone. Virtual machines give you the illusion that you have a dedicated machine. This VM technology has also paved the way for containers, another virtualization approach that's become essential in modern software deployment.

Why 0.1 + 0.2 != 0.3: Understanding Floating Point Arithmetic in Computers

Quame Jnr — Mon, 09 Sep 2024 11:56:05 +0000

Introduction
Normalization and Representation
- Explicit Normalization
- Implicit Normalization
Converting Floating Point Decimal to Binary
Conclusion

Introduction

If you have worked with floating-point numbers in computers, you'll notice they sometimes exhibit certain weird behavior. For example, if you type 0.1 + 0.2 in the Python console, you're going to get 0.30000000000000004 instead of 0.3. This behavior is mainly due to how computers store floating-point numbers.

Normalization and Representation

For us, 0.1 is just 0.1, but that is in decimal, and computers know nothing about decimals. All they know is binary. Computers store floating-point numbers by first converting them from floating-point decimal into binary, which we'll take a look at shortly. Then they do what we call normalization.

The idea behind normalization is to create some form of standard. This is because floating-point numbers can be represented in different ways. Take, for example, 0.123. We can represent this as $1.23 \times 10^{-1}$ or $12.3 \times 10^{-2}$ . These are all valid ways of representing floating-point numbers. To make it standardized, we first came up with what is now known as explicit normalization.

Explicit Normalization

With explicit normalization, we move the radix point of a floating-point binary number to the left-hand side of its most significant 1. For example, given the binary number 10.100, we'll move the radix point to the left-hand side of the most significant 1, giving 0.10100. Since we moved the radix point 2 times to the left, we will multiply by $2^2$ , thus $10.100 \times 2^2$

This is binary, thus we're multiplying by 2 and not 10

This allows us to save only the fractional part, 10100, which is also known as the mantissa, and the exponent, 2. The values are laid out in memory in the form:

________________________
|sign|exponent|mantissa|
------------------------
sign: represents the sign of the floating-point number, with 0 being positive and 1 being negative
exponent: represents the exponent of 2 after normalization
mantissa: represents the fractional value after the radix point

For simplicity's sake, let's assume we have an 8-bit computer, so we're going to store our floating-point number in 8 bits. We use 1 bit to represent our sign, 4 bits to represent our exponent, and 3 bits to represent our mantissa.

The sign is 0 since the value is positive, and the mantissa will be 10100. The exponent will be a bit tricky as we can't just convert 2 into binary and save it. This is because the exponent can be a negative number, thus we need to add a bias. We get the bias using $2^{k-1} - 1$ where k is the number of bits representing the exponent, which for our 8-bit computer is 4. Thus, $2^{4-1} - 1 = 7$ , so our exponent will be $2 + 7 = 9$ , whose binary is 1001. A representation of 0.10100 in an 8-bit computer will be:

____________
|0|1001|101|
------------

We only store 101 instead of 10100 because we only have 3 bits to save our number.

We can then convert this back with the formula:

-1^s \times 0.M \times 2^e

$1^s$ allows us to get the right sign of the value. s is the sign, and thus if s is 0, then the expression will evaluate to $1^0 = 1$ , but if s is 1, then the expression will evaluate to $1^1 = -1$
0.M evaluates to 0.101 as M represents the mantissa.
$2^e$ evaluates to the exponent, but before saving the exponent, we added a bias, thus we need to subtract the bias: $\text{exponent} - \text{bias} = 9 - 7 = 2$ . Thus, the formula becomes

$-1^s \times 0.M \times 2^e = 1 \times 0.101 \times 2^2 = 0.101 \times 2^2 = 10.1$

Implicit Normalization

The problem with explicit normalization is the same problem that leads to the sum of 0.1 and 0.2 not being exactly 0.3. The problem is precision. With floating-point numbers, the more bits we can store, the more precise our floating-point representation. With our 8-bit computer described earlier, we had 3 bits representing the mantissa. This means if we had more than 3 bits, as we did, we could still only save 3 bits, thus losing the remaining bits. However, if instead of moving the radix point to the left-hand side of the most significant 1 bit, we move it to the right-hand side of it, we can save an extra fractional bit.

10.100 will become $1.0100 \times 2^1$ and will be represented as:

____________
|0|1000|010|
------------

We can then, during conversion, change the expression 0.M to 1.M.

-1^s \times 1.M \times 2^e = 1 \times 0.1010 \times 2^2 = 0.1010 \times 2^2 = 10.10

The last bit is 0 so it’s irrelevant in this case but would be important if it was 1.

Thus, implicit normalization allows us to imply there is a 1 and saves an extra bit. One bit may not seem like a lot, but it's the difference between ASCII and UTF-8, it's the difference between 127 and 256, so yeah, for computers, it's a lot.

Converting Floating Point Decimal to Binary

Now that we have some basic understanding of how computers store floating-point numbers, let's try to understand why 0.1 + 0.2 is not particularly equal to 0.3. First, let's convert 0.1 and 0.2 to binary. To convert floating-point numbers to binary, we first convert the value before the radix point to binary and then multiply the fractional part by 2, keeping the value of the integer before the radix point until the value becomes 1. Yeah, that may not have been the best explanation, so let's see an example.

Let's say we want to convert 2.25 to binary:

Convert the integer before the radix point, which is 2, to binary: 10.
Convert the fractional part by multiplying it by 2 and keep whatever integer is before the radix point until we get 1:

0.25 × 2 = 0.5 → 0
0.5 × 2 = 1.0 → 1

Then put the integer values you got from top down behind the radix point. The floating-point 2.25 will be 10.01.

Now let's convert 0.1:

The integer before the radix point is 0, which is the same in binary
Convert the remaining fraction:

0.1 × 2 = 0.2 → 0
0.2 × 2 = 0.4 → 0
0.4 × 2 = 0.8 → 0
0.8 × 2 = 1.6 → 1
0.6 × 2 = 1.2 → 1
0.2 × 2 = 0.4 → 0
0.4 × 2 = 0.8 → 0
0.8 × 2 = 1.6 → 1
0.6 × 2 = 1.2 → 1
...

We can see this goes on and on. This is a recurring binary number, thus 0.1 in binary is 0.0001100110011....

We can also do the same for 0.2:

0.2 × 2 = 0.4 → 0
0.4 × 2 = 0.8 → 0
0.8 × 2 = 1.6 → 1
0.6 × 2 = 1.2 → 1
0.2 × 2 = 0.4 → 0
0.4 × 2 = 0.8 → 0
0.8 × 2 = 1.6 → 1
0.6 × 2 = 1.2 → 1
...

Thus, 0.2 in binary is 0.001100110011....

Now before adding these two numbers, we're first going to store them in our 8-bit computer:

Normalize using implicit normalization: $0.1 = 0.000110011... = 1.100110011... × 2^{-4}$ $0.2 = 0.00110011... = 1.100110011... × 2^{-3}$
Add bias to our exponents:
- for 0.1: -4 + 7 = 3
- for 0.2: -3 + 7 = 4
Store in our 8-bit computer. We only have 3 bits for the fractional part, so we can only store 3 values after the radix point, meaning we lose all the remaining bits:

For 0.1
____________
|0|0011|100|
------------

For 0.2
____________
|0|0100|100|
------------

Convert them back to their floating-point representations using our formula earlier $-1^s \times 1.M \times 2^e$ :
- 0.1: $1.100 \times 2^{-4} = 0.0001100$
- 0.2: $1.100 \times 2^{-3} = 0.001100$
Add them:

  0.0001100
+ 0.001100
-----------
  0.0100100

Convert back to decimal. Values before the radix point will be converted as normal, while values after the radix point will have exponents with decreasing values of negative numbers, i.e., $2^{-1}, 2^{-2}$ , etc.: $0.0100100 → (0 × 2^0) + (0 × 2^{-1}) + (1 × 2^{-2}) + (0 × 2^{-3}) + (0 × 2^{-4}) + (1 × 2^{-5}) + 0 = 0 + 0 + 0.25 + 0 + 0 + 0.03125 = 0.28125$
In our 8-bit computer,0.1 + 0.2 = 0.28125

Conclusion

We started this article trying to understand why 0.1 + 0.2 sometimes does not give us 0.3. Using our 8-bit computer for illustration purposes, we've been able to come to that conclusion. This weird behavior, we came to understand, was a result of how computers normalize and represent floating-point numbers, which leads to loss of bits, ergo leading to loss of precision.

Luckily for us, we have 32-bit and 64-bit computers now. The Institute of Electrical and Electronics Engineers (IEEE) has standards for how these representations should be done. Thus, 32-bit systems allow 8 bits for the exponent and 23 bits for the mantissa, while 64-bit systems use 11 bits for the exponent and 52 bits for the mantissa. They both still use 1 bit for the sign. This means 64-bit systems have more bits to store the fractional parts, hence more precision. This is why 64-bit systems are known as double-precision and 32-bit systems are known as single-precision. The more bits we're able to store, the closer our approximation to the actual value.

Go Test Coverage: Visualizing Profiles

Quame Jnr — Mon, 22 Jul 2024 13:54:27 +0000

Table of Content

Introduction
Go Tests
Go Tests Coverage
Conclusion

Introduction

Go has incredible tooling out of the box. It has tools for testing, benchmarking, profiling etc. I want to discuss an interesting one that impressed me: go test coverage and the different visualization options.

Go Tests

To help us understand these concepts, we will be writing some functions to do basic calculations.

Let's first write a function that adds two numbers

func Add(num1 int, num2 int) int {
    return num1 + num2
}

Let's write some tests for it

import "testing"

func TestAddition(t *testing.T) {
    got := Add(1, 3)
    want := 4
    if got != want {
        t.Errorf("wanted %d got %d", want, got)
    }
}

Let's run our tests to see if everything is ok

go test ./...

ok      github.com/quamejnr/go-cover    0.687s

Everything looks good.
We can also see how much of our code written is covered by tests and this is where the excitement begins.

Go Tests Coverage

To see the test coverage, we can add a -cover flag to our go test command.

go test ./... -cover

ok      github.com/quamejnr/go-cover    (cached)        coverage: 100.0% of statements

Currently we are 100% covered as we have written tests for all our code.
Now let's add a division function and see what happens.

func Div(num int, denom int) int {
  if denom == 0 {
    panic("invalid division error")
  }
    return num / denom
}

We can rerun our test coverage command and see our response.

go test ./... -cover

ok      github.com/quamejnr/go-cover    (cached)        coverage: 50.0% of statements

Now we've covered only 50% of our coverage as we are yet to write tests for our division function.
For a simple case like this, it's obvious what we need to test but in a larger codebase it's not so apparent and this is where coverage can be very powerful.
Go gives us tools to visualize where exactly in our code have not been tested.
We can do this by passing in some flags to our go test command: go test -coverprofile=c.out. coverprofile generates a coverage profile with the value being the name of the output file, in this case c.out.
Once you have the profile c.out, you can examine it to know more about your code coverage using the go's tool command.
We can check it out on our terminal using the command

go tool cover -func=c.out

github.com/quamejnr/go-cover/main.go:3: Add             100.0%
github.com/quamejnr/go-cover/main.go:7: Div             0.0%
total:                                  (statements)    50.0%

This shows our Div function is yet to have any test coverage so let's add test coverage to our Div function.

func TestDivison(t *testing.T) {
    t.Run("Test division", func(t *testing.T) {
        got := Div(4, 2)
        want := 2
        if got != want {
            t.Errorf("wanted %d got %d", want, got)
        }
    })
}

Now we should have covered everything. Let's run our coverage again and see

go test ./... -cover

ok      github.com/quamejnr/go-cover    0.213s  coverage: 75.0% of statements

It says we have covered only 75% of our test coverage.
And if we generate our cover profile again and inspect it.

go test ./... -coverprofile=c.out
go tool cover -func=c.out

github.com/quamejnr/go-cover/main.go:3: Add             100.0%
github.com/quamejnr/go-cover/main.go:7: Div             66.7%
total:                                  (statements)    75.0%

We can see we have covered only 66.7% of our Div code but this doesn't give us much info on what we're missing out.
This is where another useful visualization tool of the coverprofile comes in.
Go gives us the ability to look at our code in our browser to see which parts are yet to be tested. All we need to do is change our -func flag to -html flag.

go tool cover -html=c.out

This screenshot shows us that we're yet to test our path when denom is 0.
Let's update our TestDivison function to handle that.

func TestDivison(t *testing.T) {
    t.Run("Test division", func(t *testing.T) {
        got := Div(4, 2)
        want := 2
        if got != want {
            t.Errorf("wanted %d got %d", want, got)
        }
    })
    t.Run("Test division with 0", func(t *testing.T) {
        defer func() {
          if r := recover(); r == nil {
            t.Errorf("zero divsion did not panic")
          }
        }()
        Div(4, 0)
        })
}

Now if we run our go test coverage command, we should have 100% coverage.

go test ./... -cover

ok      github.com/quamejnr/go-cover    0.649s  coverage: 100.0% of statements

Conclusion

In this article, we examined how we can use go's coverage tools to help us with our testing coverage
We learnt how to;

create coverage profiles
examine them in our terminal
visualize them in our browsers. All code can be found here https://github.com/quamejnr/go-cover

References

Go Class: 39 Code Coverage by Matt Holiday

Understanding XOR-based-value Swapping

Quame Jnr — Sat, 04 May 2024 09:05:49 +0000

Objectives
Introduction
Understanding XOR
Proof of the 3 XOR operations
Conclusion

Objectives

Understanding XOR operations
Understanding why the 3 special XOR operations swap two numbers in place

Introduction

Given two numbers x=5 and y=10, we can switch these two numbers in place by using a temporary variable as the C code below;

#include <stdio.h>

int main(void) {
    int x = 5;
    int y = 10;
    printf("Before reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);

    printf("-----------------------\n");

    // Assign y to a temporay variable
    int temp = y;
    y = x;
    x = temp;

    printf("After reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);

}

There is also another way to do this by using Exclusive OR (XOR). This does not need a temporary variable and will switch the values in place.
It involves 3 XOR operations.

#include <stdio.h>

int main(void) {
    int x = 5;
    int y = 10;

    printf("Before reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);

    printf("-----------------------\n");

    // XOR is represented by ^
    // The 3 XOR operations
    y = x ^ y;
    x = x ^ y;
    y = x ^ y;

    printf("After reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);
}

The above code changes the two variables without using a temporary variable. When you do those 3 XOR operations, the variables will switch places but why?
To understand that, let's first understand what Exclusive OR (XOR) is.

Understanding XOR

XOR is a logical operator that returns True only if one of its inputs is True. For example: Given two inputs if both input A and input B are True then the XOR of both will be False.
If both are False then the XOR will also be False. XOR will only be True if one of them is True and the other is False.
To use 0s and 1s to represent our inputs, we can say True is 1 and False is 0. Thus, an XOR operation between the two inputs will give us the table below;

Input A	Input B	Output
0	0	0
0	1	1
1	0	1
1	1	0

XOR between binary numbers

This means if we XOR two binary numbers, A(1011) and B(0110), we are going to get 1101.

   A:    1 0 1 1
   B:    0 1 1 0
----------------
Result:  1 1 0 1

If we also XOR two binary numbers, A(1011) and B(1011), we are going to get 0000

   A:    1 0 1 1
   B:    1 0 1 1
----------------
Result:  0 0 0 0

We can see both binary numbers are the same and we know XOR outputs 0 if both inputs are the same, ergo A ^ A = 0.
We can also also establish that XOR between A and B where A=0 will output B.

   A:    0 0 0 0
   B:    0 1 1 0
----------------
Result:  0 1 1 0

This means 0 ^ B = B.

Given:

A ^ A = 0 and 
0 ^ B = B
We can say;
(A ^ A) ^ B = B
This is associative and can also be written as;
A ^ A ^ B = B

Proof of the 3 XOR operations

Let's go back to our 3 operations that change x and y in place;

y = x ^ y
x = x ^ y
y = x ^ y

Let's use the various rules we've established so far to see if we can prove that after these 3 operations x=y and y=x.
We have the first 2 operations;

y = x ^ y and 
x = x ^ y

We can replace y in the 2nd operation with its value in the first: x ^ y, ergo our second operation can be expanded to;

x = x ^ y
x = x ^ (x ^ y) 
x = x ^ x ^ y

We have already established that A ^ A ^ B = B thus,

x = x ^ x ^ y = y
x = y

So x is now y on the 2nd operation.

We can now represent our 3 operations as;

y = x ^ y
x = y
y = x ^ y

We can then proceed to expand our 3rd operation by replacing x whose current value is now y and y whose current value is x ^ y;

y = x ^ y
Replacing x with y and y with x ^ y;
y = y ^ (x ^ y) 
y = y ^ x ^ y 
y = y ^ y ^ x
y = x

After the 3 operations, we have x = y and y = x.

Conclusion

We've been able to prove why 3 special XOR operations lead to the swapping of two values without using a temporary variable.
Although this algorithm does not offer any significant improvement over swapping two values using a temporary variable, understanding it gives us a better understanding of bit operations and their properties.

Mocking Return Values in Python

Quame Jnr — Tue, 19 Dec 2023 17:52:13 +0000

Unit tests are easier to write when given a set of inputs you know you're always going to get an expected response. It becomes a bit difficult when the same set of inputs can lead to varying responses.
When you work on programs where sometimes you have to make a request to an external API or making requests to other services in your microservices, you can't be sure you're going to get 200 status code on each request.
You'll mostly put in measures to handle when your requests fail but how do you write unit tests to ensure your system works as expected.

Writing Program

Let's build a program that a pings a url and returns True if the status code is 200 and False when it is not.

Create a file called client.py
Write the following code

# client.py

# Make sure you have requests installed.
# If not, you can install with `pip3 install requests` 
# or `pip install requests`.
import requests

def ping(url):
    res = requests.get(url)
    retun res.status_code == 200

print(ping("https://google.com"))

Run python3 client.py in your terminal in the directory where client.py resides. The below should be your response;

❯ python3 client.py
True

Writing Tests

Our program works as expected. It's time to write tests to ensure that we return True when our request is 200 and False when the status code is not 200.

Create a file called test_client.py in the same directory as client.py
Write the following code;

# test_client.py
import unittest
from client import ping

class TestClient(unittest.TestCase):
    def setUp(self):
        self.url = "https://google.com"

    def test_ping_returns_200(self):
        result = ping(self.url)
        self.assertTrue(result)

if __name__ == "__main__":
    unittest.main()

Run python3 test_client.py. You should get a response like below;

❯ python3 test_client.py
.
---------------------------------------------------------
Ran 1 test in 1.113s

OK

All our tests are passing but now let's test for the case when the status code is not 200. Let's add another test to our test

# test_client.py
import unittest
from client import ping

class TestClient(unittest.TestCase):
    def setUp(self):
        self.url = "https://google.com"

    def test_ping_returns_200(self):
        result = ping(self.url)
        self.assertTrue(result)

    # New
     def test_ping_returns_500(self):
        result = ping(self.url)
        self.assertFalse(result)


if __name__ == "__main__":
    unittest.main()

When we rerun python3 test_client.py, our new test fails.


❯ python3 test_client.py
.F
==========================================================
FAIL: test_ping_returns_500 (__main__.TestClient.test_ping_returns_500)
----------------------------------------------------------
Traceback (most recent call last):
  File "/Users/mock/test_client.py", line 46, in test_ping_returns_500
    self.assertFalse(result)
AssertionError: True is not false

-----------------------------------------------------------
Ran 2 tests in 2.076s

FAILED (failures=1)

This is because for now our request returns 200, so we are unable to test for when our ping fails.
To be able to do this we are going to mock our requests and responses. This gives us the ability to determine what response we should get.
This way we can manipulate our requests to return 500 response status code instead of the actual status code.

Mocking requests and responses

First we're going to import the patch decorator and MagicMock object from unittest.mock.
The patch decorator allows us to edit our requests, it takes a target which will be the requests we want to change, which in this case is the one in client.py.
The MagicMock object allows us to create the response we want so we can pass it to requests.
We have add an additional parameter which can be named anyway we want. I'll name it mock_requests. This is the object we can attach our response to.
Let's add these changes to our test_client.py;

# test_client.py
import unittest
from unittest.mock import patch, MagicMock
from client import ping

class TestClient(unittest.TestCase):
    def setUp(self):
        self.url = "https://google.com"

    def test_ping_returns_200(self):
        result = ping(self.url)
        self.assertTrue(result)


    @patch("client.requests")   # New
    def test_ping_returns_500(self, mock_requests):    # New

        # New
        mock_response = MagicMock()
        mock_response.status_code = 500
        mock_requests.get.return_value = mock_response

        result = ping(self.url)
        self.assertFalse(result)


if __name__ == "__main__":
    unittest.main()

Let's dive into what we've done so far.

By adding the decorator @patch("client.requests"), we're saying we want to modify the requests function that we imported in client.py. It can be any function, we could have targeted ping itself. You can try that on your own after this. The patch decorator modifies our test method and passes in a second argument to our test_ping_returns_500 method. Thus, we add mock_requests as a parameter to our method. This mock_requests is a mock variant of requests.
We instantiate our MagicMock object and assign to mock_response. Our MagicMock object allows us to take the form of any class we want and in this case a Response object.
We add a status_code attribute to our mock_response and assign it the value of 500.
We proceed to assign our mock_response to mock_requests.get.return_value. We have now modified our requests in that, we're saying, when the requests in client.py calls it's get function, we want the value returned to be that of our mock_response. Thus when requests.get() is called, the value returned is going to be the mock_response.

If we run our test again, we see everything passes now.


❯ python3 test_client.py
..
----------------------------------------------------------------------
Ran 2 tests in 1.609s

OK

We can proceed to do the same for test_ping_returns_200 method but make the status_code 200 so we can add a fake url instead of making requests to https://google.com.

# test_client.py
import unittest
from unittest.mock import patch, MagicMock
from client import ping

class TestClient(unittest.TestCase):
    def setUp(self):
        self.url = "https://api.service.com"    # New

    @patch("client.requests")   # New
    def test_ping_returns_200(self, mock_requests):    # New

        # New
        mock_response = MagicMock()
        mock_response.status_code = 200
        mock_requests.get.return_value = mock_response


        result = ping(self.url)
        self.assertTrue(result)


    @patch("client.requests")
    def test_ping_returns_500(self, mock_requests):

        mock_response = MagicMock()
        mock_response.status_code = 500
        mock_requests.get.return_value = mock_response

        result = ping(self.url)
        self.assertFalse(result)


if __name__ == "__main__":
    unittest.main()

We can run our tests again to ensure everything works well.


❯ python3 test_client.py
..
----------------------------------------------------------------------
Ran 2 tests in 1.609s

OK

Mocking response body

We can also add response body to our mock_response. Assuming, the 3rd party API we're pinging returns a json response with an attribute {"status": "ok"}.

Let's modify our function in client.py to return the json response too when the status_code is 200 and None when it is not.

# client.py

import requests

def ping(url):
    res = requests.get(url)
    # New
    if res.status_code == 200:
        return (True, res.json())
    return (False, None)

We modify our test_client.py to this;

# test_client.py
import unittest
from unittest.mock import patch, MagicMock
from client import ping

class TestClient(unittest.TestCase):
    def setUp(self):
        self.url = "https://api.service.com"

    @patch("client.requests")
    def test_ping_returns_200(self, mock_requests):

        mock_response = MagicMock()
        mock_response.status_code = 200
        mock_response.json.return_value = {"status": "ok"}  # New
        mock_requests.get.return_value = mock_response


        status, body = ping(self.url)  # New
        self.assertTrue(status)
        self.assertEqual(body["status"], "ok")


    @patch("client.requests")
    def test_ping_returns_500(self, mock_requests):

        mock_response = MagicMock()
        mock_response.status_code = 500
        mock_requests.get.return_value = mock_response

        status, body = ping(self.url)  # New
        self.assertFalse(status)


if __name__ == "__main__":
    unittest.main()

Adding mock_response.json.return_value, we're saying when we call the json function on our mock_response we should get {"status": "ok"}.
Thus, {"status": "ok"} is the value we get when we call res.json() in client.py.

Conclusion

Mocking requests make testing easier especially when you have to deal with 3rd party APIs and even other services in your microservices.
Let's say, you have an API that first makes a request to your auth service to confirm if a user has certain permissions before allowing them access to certain resources.
You can mock the response you have to test that only users with the needed permissions are allowed to access the resource.

Code for this tutorial can be found here https://github.com/quamejnr/python-mock-requests

Introduction to Caches

Quame Jnr — Thu, 07 Dec 2023 09:46:56 +0000

Objectives

Understand what caching is?
Understand how caching is done?
Understand the difference between cache hit and cache miss?
What data inconsistency is and how we can minimize it in our cache services?

What is caching?

I'm going to ask you to do a couple of computations and I'll want you to bear with me. You can use a calculator if you want.

What is 30 x 25? Got the answer?
Ok What is 2 x 3?
Great, what is 30 x 25 again?

If you observed, the first time you answered what 30 x 25 was, it took you a while to compute the answer which is 750 by the way but the second time I asked the question, you most likely didn't have to recompute the answer, you just remembered the answer because you had just made the computation not long ago. This is what caching is about. A cache service stores part of your data(mostly recently accessed data) so it can serve data faster. Caches happen from the low level of computer architecture with pages, L-series caches and RAM to the application layer using tools like memcached and redis. This article will focus more on the application level.

How is caching done?

Sometimes, the requests coming to your system will need a lot of computing process before a response. Sometimes, you have high number of requests coming in your services which will put your database under heavy pressure leading to high latency. Caches allow you to serve data faster by not having to hit your datastore on each request. It improves your read performance thus increasing your overall throughput. Adding a caching
layer to your system means anytime a read request comes in;

Your system checks your cache service and if the data exists in the cache service, the request is served.
If the data is not in the cache service, the request is sent to your database to get the data so it's served. The data is also written to your cache service.

The more the data being requested are found in the cache the faster you can serve responses and this is known as cache hit. Cache hit is the rate at which data being requested are found in your cache. The opposite is cache miss, which defines the rate at which data being requested are not found in the cache. The goal is to increase your cache hit as the higher your cache hit the faster you serve your responses. When your caches don't have a lot of data in them, they are said to be cold and when they do have a lot of data in them they are said to be warm.

This was the cause of the Slack's incident on 0-22-22. They had an issue that led to their cache layers being flushed thus becoming cold leading to high cache misses that overloaded their databases. Databases couldn't keep up with all the requests and kept timing out which also hampered their cache service from filling up with data thus leading to higher requests on database. They had to throttle their system so they can fail some requests and be able to serve some requests to gradually build their cache system to a level of normalcy.

Data Inconsistency

Caches as good as they are are also tricky to deal with. One of the biggest issues is data inconsistency. Data inconsistency is as a result of data in your database being different from data in your cache. This can be as a result of
updates on data not yet synchronised to your cache service. There are different ways to resolve this and they all have their pros and cons.

Write through. Data will first be written to your cache and then written to your datastore synchronously. This is expensive as two writes have to be done simultaneously, one to the database and one to the cache.
Write behind. Data will first be written to your cache and later be written to your database asynchronously.

They both shine in different situations. Let's say, you are building a caching layer that serve the likes feature on your products in your e-commerce store. If someone likes a product, it's not integral to show them the right number of
likes at the moment, the consequences are inconsequential thus you can update the cache and update your database later. However, let's say you caching the quantity of the products. It's very important to show the latest updated
quantity, otherwise you'll end up with more orders than products. You want to use a write through approach in such cases even though it's computationally expensive.

Data invalidation. We can also update data on the cache when the data has been updated or we can invalidate the data and create a new data that the requests will be pointed to.
Time to Live (TTL). We can also set a TTL, in which we give data a limited amount of time like 60 seconds, after which the data becomes obsolete. You want to set your TTL to a range +/- 10s of your chosen time. So for 60s, that will be range 50s-70s. This ensures all your cache data don't go cold at the same time thus overloading your database with requests.

Why don't we use cache everywhere?

If caches are so good then why don't we use them all the time?

Because caches contain temporary data, the data are saved in your RAM thus when your system goes down or restarts, you lose your cache data. Due to continuous deployments, errors, autoscaling etc. containers restart and rebalance quite frequently. This means when you have your cache services baked in your applications, your cache will go cold frequently. This is why caches are recommended as standalone services (We will discuss this in another article).
Apart from the transient nature of RAM, they are also very expensive. You need databases to write your data to disks not only to save your data but also to save you cost.

Conclusion

In the current climate where everything is supposed to be blazingly fast. You want to increase your system response times using cache. However, you want to be
also aware of the extra complexity it introduces and how to mitigate its pitfalls.

References

Maintaining Cache Consistency

Optimizing API Endpoint (Real World Case Study)

Quame Jnr — Thu, 10 Aug 2023 16:03:17 +0000

Situation

I had to work on a task where we wanted to show payment information of orders to users which meant as the backend engineer, I had to add payment information to the data being sent to the client.
The payment data is on another service so had to make a request to that service so I can add it to the order information. The task itself was pretty easy, however prior to doing the task, I realised the endpoint was already taking about 3s to return a response. 3s may not seem like a lot but in the age of TikTok, It was too long. The endpoint was doing two things under the hood when the client makes a request.

Make a request to orders service for orders.
Make a request to product service product images to update order items with current product images.

I didn't think these processes warranted the response time especially when the response was paginated so investigated the implementation details.

Problem

Multiple Calls

When we make a request to get orders from our order service we make another request to the products service to get an updated image of the order items in each order. Each order item is a product and we needed to get images of those products from another service to include it in the order item when returning orders data to the client. Our proxy service which from here will be regarded as bff (backend for frontend) is the one making these calls. The implementation was in this manner;
In bff

We loop through orders
Then loop through the order items in each order
Get the product id of each order item, put them in a list then make a request to the product service for the current image of the order items.

All Code snippets have been modified to represent the logic of the implementation. This simplifies the code so the reader can easily understand without having to worry about other unnecessary details.

def get_images_for_orders(orders):
    for order in orders:
        product_ids = []
        order_items = order["order_items"]
        for order_item in order_items:
            product_id = order_item["product_id"]
            product_ids.append(product_id)

        response = make_request_for_product_images(product_ids)
        images = response["results"]
        result = add_images_to_orders(images, order_items)

    return result

A request was being made to the products service to get product images on each iteration of order thus leading a network for each order. This was done this way because the images were needed in certain order to be able to easily match each order item to image. So first product image in the list had to belong to the first order item.

In products service

Receive the request for images, get the product uuids
Loop through the product ids and query the database for product image on each iteration.

def get_product_images(product_ids):
    product_images = []
    for prod_id in product_ids:
        ## The first product image is being retrieved because a product can
        ## have multiple images
        product_image = ProductImage.objects.filter(product_id=prod_id).first()
        product_images.append(product_image)
    return product_images

Doing this meant, we make a db call on every single product id.
This meant if our request for orders returns 20 orders per page and each order had 2 order items. We are going to make 20 network calls in the bff and 40 database queries in the products service.

Solution

To increase the response time, there were two solutions I had to implement.

Make one network call in the bff.
Make one db call in the products service.

The first solution was implemented by putting all the product ids of order items into one list before making the network call.
The second solution was implemented by modifying the db call so we can get distinct product images.
Implementing the first two posed another challenge. We needed to find a way to match each image to its respective order item. That was resolved using a dictionary (hash table).

Refactoring

Make one network call In bff

def get_images_for_orders(orders):
    order_items_dict = {}
    for order in orders:
        order_items = orders["order_items"]
        order_items_dict.update(
            {order_item["product_id"]: order_item for order_item in order_items}
        )
    product_ids = list(order_items_dict.keys())

    response = make_request_for_product_images(product_ids)
    images = response["results"]
    result = add_images_to_orders(images, order_items_dict)

    return result

Putting order_items in a dictionary order_items_dict with product_id as key and the order_item as value, meant we don't have to worry about the order the product images come in, we can just match them to their product ids in order_items_dict thus resolving our challenge of matching the images to the order.
We can then get all the keys which will now be the list of the product_ids and use them for our request.

Make one database call In products service

def get_product_images(product_ids):
    product_images = (
            ProductImage.objects.filter(
                product_id__in=product_ids
            )
            .order_by("product_id")
            .distinct("product_id")
        )
    return product_images

This query ensures we only get one product image per product_id.

Results

These little changes reduced the response time of our calls from 3s to 1s. Also, these changes ensures only one network call and only one db call is made no matter the number of orders, thus changing our time complexity from O(n) to O(1). Last but not least, this endpoint is widely used by a number of teams in the company and getting orders went from being noticeably delayed to almost instant thus saving a lot of time.

DEV Community: Quame Jnr

Binary Search Trees: Why They’re Great in Memory but Terrible on Disk

Tree Balancing

Why does it Suck as Disk-Based Storage?

1. Random Insertion Order

2. Fanout of 2

Conclusion

Database Management System (DBMS) Architecture Explained

Query Processor

Query Parser

Query Optimizer

How Cost Estimation Works

Execution Engine

Storage Engine

Conclusion

Why Columnar Storage Makes Analytics Faster

Why Queries Are Faster with Columns

Understanding Prometheus Storage: From Scrape to Disk

The Data Flow: From Metrics to Disk

Scraping & Parsing

The Batch

The Write-Ahead Log (WAL)

The Head (In-Memory)

Blocks (On Disk)

Conclusion

Prometheus: The Essential Guide to Monitoring Systems

What is Prometheus?

History and Relevance Compared to Older Tools

Why Use Prometheus?

How Does It Work?

Metric Types in Prometheus

Architecture

Components

Conclusion

Virtual Machines: How One Computer Becomes Many

Introduction

Brief History

How does it work

Components

Process

Types of Hypervisors

Why should you care?

Sandboxing

Running Multiple Operating Systems

Conclusion

Why 0.1 + 0.2 != 0.3: Understanding Floating Point Arithmetic in Computers

Table of Contents

Introduction

Normalization and Representation

Explicit Normalization

Implicit Normalization

Converting Floating Point Decimal to Binary

Conclusion

Go Test Coverage: Visualizing Profiles

Table of Content

Introduction

Go Tests

Go Tests Coverage

Conclusion

References

Understanding XOR-based-value Swapping

Table of contents

Objectives

Introduction

Understanding XOR

XOR between binary numbers

Proof of the 3 XOR operations

Conclusion

Mocking Return Values in Python

Writing Program

Writing Tests

Mocking requests and responses

Mocking response body

Conclusion

Introduction to Caches

Objectives

What is caching?

How is caching done?

Data Inconsistency

Why don't we use cache everywhere?