Algorithm – A series of instructions that perform a task.

Big-O Notation

Used to describe time and space complexities of algorithms:

  • O(1) — O of 1 time aka constant time
  • O(n) — Linear time
  • O(log(n)) — Logarithmic time
  • O(n^2) — Exponential timeLeast efficient
  • O(n!) — Factorial time


Credit: ByteByteGo blog

Simple Hashing

A mechanism to distribute data evenly across servers.


  1. For each object, hash its key with a hashing function (like MD5):
    serverIndex = hash(object_key) % N where N is the size of the server pool

    A diagram depicting the above formula

  2. Perform modulo operation on the hash against the number of servers:
    hash(object_key) % numberOfServers

    This determines which server the object belongs to. As long as the number of servers stays the same, an object key will always map to the same server.

    Assuming a cluster of 4 servers:

    A diagram depicting the above function with 4 servers

    If Server 1 goes offline:

    • The modulo operation changes from 4 to 3.
    • Most of the keys (but not all) get distributed.
    • A storm of misses and objects moving ensues.

    The solution to this problem is consistent hashing.

Consistent Hashing

Hashing the object keys but also the server hostnames (or IP addresses) with the same hashing function to the same range of values:

A diagram depicting how both objects and servers use the same hashing function

Hash space: the range of x0 to xN:

A diagram depicting hash space from range x0 to xN

Hash ring: created by connecting the end of the hash range:

A diagram depicting the hash ring

Consistent hashing is used by:

  • Apache Cassandra and Amazon DynamoDB for data partitioning
  • CDNs to distribute web content evenly
  • Load balances to distribute persistent connections evenly


  1. Hash the server by its hostname or IP and place it on the hash ring.
  2. Hash the object key using the same hash function from step #1 and place it into the hash ring. The hash is used directly to map the object keys onto the ring:

    A diagram depicting the above two steps

    • To locate a server for a particular object, go clockwise from the location of the object key on the ring until a server is found.
    • If another server is added, only a fraction of the keys need to be redistributed:

      A diagram depicting how k0 is redistributed from s0 to s4

    • If server 1 is removed, only k1 needs to be remapped (to s2); the rest of the keys are unaffected:

      A diagram depicting how k1 is remapped to s2 if s1 is deleted

Size of Segments

If server 1 is removed, the segment for server 2 is now twice the size as the ones for server 0 and server 3:

A diagram depicting s2’s segment twice as large as s3

This is solved via virtual nodes. Each server appears multiple times on the ring. Each location is a virtual node representing a server:

A diagram depicting two virtual nodes each for s0 and s1

Each server handles multiple segments on the ring (one for each of its virtual nodes):

A diagram depicting how each server handles multiple segments on the ring via virtual nodes

As the number of virtual nodes increases, the distribution of objects becomes more balanced. But more virtual nodes means taking more space for the metadata of those nodes. This is a tradeoff.

Linked Lists

Elements are ordered one after another. They are not stored in contiguous locations. They are linked using pointers.

Linked Lists do not have indices. Each element is a node, which contains data and a reference to the next node. Size of a linked list is dynamic.

ele0 ele1 ele2 ele3
5 –> 8 –> 10 –> 13 –> null
head is 5
tail is null

setting 10 to null results in:
5 –> 8 –> null

Load Balancing Algorithms

Credit: ByteByteGo blog

diagrams of various load balancing algorithms

Static load-balancing algorithms

  • Round Robin — standard round robin
  • Sticky Round Robin — if initial request goes to Service A, remaining requests from that user will “stick” to Service A.
  • Weighted Round Robin — weight is specified for each service; the higher the weight, the more request that service handles.
  • Hash — a hash function is applied on the incoming requests’ IP or URL; requests are routed to relevant service instances.

Dynamic load-balancing algorithms

  • Least connections
  • Least lag (fastest response time)


  • A queue contains elements in the order they were added.
  • Queues are FIFO: Elements are inserted at the end (enqueue) and removed from the beginning (dequeue).
  • Queues do not have indices.

Blocking Queue

Credit: ByteByteGo blog
A blocking queue algorithm uses locks. Thread A acquires the lock first, and Thread B might wait for arbitrary lengthy periods if Thread A gets suspended while holding the lock. This algorithm may cause Thread B to starve.

diagram of a blocking queue

Non-blocking Queue

The non-blocking algorithm allows Thread A to access the queue, but Thread A must complete a task in a certain number of steps. Other threads like Thread B may still starve due to the rejections.

This is the main difference between blocking and non-blocking algorithms: The blocking algorithm blocks Thread B until the lock is released. A non-blocking algorithm notifies Thread B that access is rejected.

diagram of a non-blocking queue

Non-blocking Queue Implementation

Compare and Swap (CAS) can be used to implement a non-blocking queue:

diagram of a non-blocking queue implemented with compare-and-swap


A collection of nodes where each node can be linked to more nodes. Nodes are collected by links. Useful for nonlinear data.