Designing an Object Storage System: Blob Storage, Metadata Indexing, and Erasure Coding at Scale

Most engineers interact with object storage through a thin HTTP API: PUT a blob, GET it back by key, list by prefix. The simplicity of that surface area hides a set of hard distributed systems problems underneath. Understanding how S3, R2, and their open-source equivalents actually work gives you the mental model to make real capacity and architecture decisions, not just pick a tier from a pricing table.

This article covers the data and metadata planes separately because they have different scaling properties, consistency requirements, and failure modes. Then it gets into erasure coding (which is how you get 11 nines of durability without tripling your storage bill), metadata indexing for listing operations, and finally capacity planning with concrete numbers.

The Two-Plane Architecture

Object storage splits into two distinct planes that should never be conflated.

The data plane is responsible for storing and retrieving raw bytes. It does not know or care what a “bucket” is. It thinks in terms of physical placement: which storage nodes hold which chunks of which objects. The data plane prioritizes throughput and durability.

The metadata plane is responsible for the namespace: bucket names, object keys, ACLs, content-type headers, ETags, and the mapping from (bucket, key) to physical storage locations. The metadata plane prioritizes consistency and lookup latency. A GET request hits the metadata plane first to resolve the location, then fetches bytes from the data plane.

Client
  |
  v
[API Gateway / Load Balancer]
  |
  +---> [Metadata Service]  (RocksDB or similar, per-region)
  |         |
  |         v
  |     (location record: bucket + key -> shard IDs + node addresses)
  |
  +---> [Data Nodes]  (raw block storage, 36-72 drives per node)
            |
            v
        [Chunk/Shard Layer]  (erasure-coded stripes stored here)

These two planes fail independently. If your metadata service is degraded, reads and writes fail even if all data nodes are healthy. If several data nodes are down but below the erasure coding threshold, reads succeed normally. Designing them as separate deployment units with separate SLOs is what makes this work at scale.

Consistent Hashing for Blob Placement

When a PUT request arrives, the data plane needs to decide which storage nodes will hold the object’s shards. Naive modulo hashing (node = hash(key) % N) breaks whenever you add or remove nodes because nearly every key remaps. Consistent hashing solves this: only K/N keys move when you add a node (where K is total keys and N is total nodes).

The standard implementation uses a ring. Each physical node is assigned multiple positions on the ring (virtual nodes), typically 100-200 per physical node. This gives even distribution even when physical nodes have different capacities or when the fleet is small.

import { createHash } from "crypto";

interface StorageNode {
  id: string;
  address: string;
  weightFactor: number; // 1.0 = standard, 2.0 = twice the virtual nodes
}

class ConsistentHashRing {
  private ring: Map<number, StorageNode> = new Map();
  private sortedKeys: number[] = [];
  private readonly virtualNodesPerUnit = 150;

  addNode(node: StorageNode): void {
    const virtualCount = Math.floor(
      this.virtualNodesPerUnit * node.weightFactor
    );
    for (let i = 0; i < virtualCount; i++) {
      const virtualKey = this.hash(`${node.id}:${i}`);
      this.ring.set(virtualKey, node);
    }
    this.sortedKeys = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }

  removeNode(nodeId: string): void {
    for (const [key, node] of this.ring.entries()) {
      if (node.id === nodeId) {
        this.ring.delete(key);
      }
    }
    this.sortedKeys = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }

  getNodes(objectKey: string, count: number): StorageNode[] {
    if (this.ring.size === 0) return [];
    const hash = this.hash(objectKey);
    const startIdx = this.bisect(hash);
    const nodes: StorageNode[] = [];
    const seen = new Set<string>();

    for (let i = 0; i < this.sortedKeys.length && nodes.length < count; i++) {
      const idx = (startIdx + i) % this.sortedKeys.length;
      const node = this.ring.get(this.sortedKeys[idx])!;
      if (!seen.has(node.id)) {
        nodes.push(node);
        seen.add(node.id);
      }
    }
    return nodes;
  }

  private hash(key: string): number {
    const buf = createHash("md5").update(key).digest();
    return buf.readUInt32BE(0);
  }

  private bisect(target: number): number {
    let lo = 0;
    let hi = this.sortedKeys.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.sortedKeys[mid] < target) lo = mid + 1;
      else hi = mid;
    }
    return lo % this.sortedKeys.length;
  }
}

One non-obvious detail: you generally want to place shards on nodes in different failure domains (racks, availability zones, power circuits), not just different nodes. The getNodes call above returns nodes by ring position, but a production implementation filters candidates by failure domain before committing placement.

Erasure Coding: Durability Without Full Replication

Three-way replication gives you durability at the cost of 3x raw storage. For a petabyte-scale system, that overhead is the primary cost driver. Erasure coding (EC) changes the tradeoff.

The common production scheme is Reed-Solomon encoding with parameters (k, m): split the object into k data shards and compute m parity shards. The object is recoverable from any k of the k + m total shards. S3’s Standard tier uses a variant roughly equivalent to RS(6, 3), giving 9 total shards with tolerance for any 3 failures, at roughly 1.5x storage overhead versus 3x for full replication.

// Conceptual interface for an EC layer
// Real implementations use native bindings (e.g., ISA-L, BackBlaze's JavaReedSolomon)
interface ECScheme {
  dataShards: number;
  parityShards: number;
  totalShards: number;
  storageOverhead: number; // (k + m) / k
}

function buildScheme(k: number, m: number): ECScheme {
  return {
    dataShards: k,
    parityShards: m,
    totalShards: k + m,
    storageOverhead: (k + m) / k,
  };
}

// RS(6, 3): tolerate 3 node failures, 1.5x overhead
const standardTier = buildScheme(6, 3);

// RS(14, 4): tolerate 4 failures, 1.29x overhead (used for cold storage at scale)
const coldTier = buildScheme(14, 4);

interface ShardPlacement {
  shardIndex: number;
  nodeId: string;
  availabilityZone: string;
  byteRange: [number, number];
}

function planShardPlacement(
  objectKey: string,
  objectSizeBytes: number,
  scheme: ECScheme,
  ring: ConsistentHashRing,
  zonesRequired: number
): ShardPlacement[] {
  const nodes = ring.getNodes(objectKey, scheme.totalShards);
  const shardSize = Math.ceil(objectSizeBytes / scheme.dataShards);

  return nodes.map((node, idx) => ({
    shardIndex: idx,
    nodeId: node.id,
    availabilityZone: node.id.split("-")[0], // simplified
    byteRange: [idx * shardSize, Math.min((idx + 1) * shardSize, objectSizeBytes)],
  }));
}

The tradeoff you must internalize: erasure coding increases read latency because a GET requires fetching k shards and reconstructing the object, versus a replicated read that can fetch from any single replica. Systems that use EC for large objects (typically over 1 MB) often maintain full replicas for small objects below a size threshold, where the reconstruction overhead exceeds the storage savings.

A second non-obvious cost: EC raises the write latency floor. You cannot acknowledge a write until at least k shards are durably stored. With synchronous replication you have the same constraint, but EC adds the encoding computation time on the write path.

Metadata Indexing for Listing and Prefix Queries

Object storage APIs expose a flat namespace with prefix-based listing. The ListObjectsV2 behavior in S3 is worth understanding: there are no real directories, only key prefixes that act like directories. A request for prefix=photos/2024/ with delimiter=/ returns a flat list of keys in that logical “directory” plus common prefixes for sub-”directories.”

This is hard to implement efficiently. A naive B-tree index on (bucket_id, key) works for small buckets but degrades when a single bucket holds billions of objects. Production systems use a few strategies:

Range partitioning by key lexicographic order. Split the keyspace into shards at partition boundaries. Each shard owns a contiguous key range. Listing scans shards sequentially and merges. The challenge is hotspot avoidance: if most keys share a common prefix, one shard handles all writes.

Metadata compaction log. Each write appends a log entry. Background jobs compact logs into sorted key ranges. Reads merge the log tail with the compacted index. This is essentially LSM (log-structured merge) applied to object metadata, which is why RocksDB appears in many production metadata stores.

interface ObjectMetadata {
  bucketId: string;
  key: string;
  size: number;
  etag: string;
  contentType: string;
  lastModified: Date;
  storageClass: "STANDARD" | "INFREQUENT_ACCESS" | "GLACIER";
  shardLocations: ShardPlacement[];
  customHeaders: Record<string, string>;
}

interface ListQuery {
  bucketId: string;
  prefix?: string;
  delimiter?: string;
  startAfter?: string;
  maxKeys: number;
}

interface ListResult {
  objects: Pick<ObjectMetadata, "key" | "size" | "etag" | "lastModified">[];
  commonPrefixes: string[];
  nextContinuationToken?: string;
  isTruncated: boolean;
}

// Prefix query over a partition-aware metadata store
async function listObjects(
  query: ListQuery,
  metadataStore: MetadataStore
): Promise<ListResult> {
  const { bucketId, prefix = "", delimiter, startAfter, maxKeys } = query;

  // Range scan: start at (bucketId, prefix) and end at (bucketId, prefix + "\xff")
  const scanStart = startAfter ?? prefix;
  const scanEnd = prefix + "\xff";

  const rawEntries = await metadataStore.rangeScan(
    bucketId,
    scanStart,
    scanEnd,
    maxKeys + 1 // fetch one extra to determine isTruncated
  );

  const objects: ListResult["objects"] = [];
  const commonPrefixSet = new Set<string>();

  for (const entry of rawEntries.slice(0, maxKeys)) {
    if (delimiter) {
      const afterPrefix = entry.key.slice(prefix.length);
      const delimIdx = afterPrefix.indexOf(delimiter);
      if (delimIdx !== -1) {
        commonPrefixSet.add(prefix + afterPrefix.slice(0, delimIdx + 1));
        continue;
      }
    }
    objects.push({
      key: entry.key,
      size: entry.size,
      etag: entry.etag,
      lastModified: entry.lastModified,
    });
  }

  return {
    objects,
    commonPrefixes: Array.from(commonPrefixSet).sort(),
    isTruncated: rawEntries.length > maxKeys,
    nextContinuationToken:
      rawEntries.length > maxKeys
        ? Buffer.from(rawEntries[maxKeys].key).toString("base64")
        : undefined,
  };
}

The performance trap here is the LIST on buckets with uniform key prefixes, for example when keys are UUIDs. Every partition gets hit roughly equally, which is fine for throughput but terrible for listing in meaningful order. If you need ordered listing (e.g., paginating recent uploads by timestamp), embed the timestamp into the key prefix: 2026/04/02/T14:32:00Z-<uuid>. This concentrates recent writes on one partition but makes ordered listing a single sequential scan.

Consistency Model: Strong vs. Eventual

Object storage systems have moved toward strong read-after-write consistency (S3 announced this in 2020). The implementation cost is real: after a successful PUT, the metadata service must synchronously propagate the new entry to all readers before returning 200. This requires either a consensus protocol (Raft, Paxos) or a lease-based approach where the primary holds a lease on the bucket’s partition.

For listing, strong consistency is harder. A list operation scans multiple metadata partitions. Each partition can be strongly consistent internally, but a list across partitions is only as consistent as the moment each partition was read. An object PUT that hits partition A after partition B is scanned will not appear in that list result, even with strong consistency within each partition. This is a fundamental constraint, not an implementation shortcut.

The practical implication: do not use LIST operations as a work queue. If you PUT an object and then immediately LIST to check its existence, you may or may not see it depending on partition scan ordering. Use HEAD or GET directly.

Tradeoffs

Dimension	Full Replication (3x)	Erasure Coding RS(6,3)	RS(14,4) Cold
Storage overhead	3.0x	1.5x	1.29x
Fault tolerance	Any 2 node failures	Any 3 node failures	Any 4 node failures
Read amplification	1x (single replica)	6x (k shards)	14x (k shards)
Write latency floor	Low (first replica ack)	Medium (k shards ack)	Medium-high
Reconstruction CPU	None	Moderate (Reed-Solomon decode)	Higher (larger matrix)
Best use case	Small objects, hot access	Standard objects >1 MB	Archive, rarely read

Production Considerations

Capacity planning. The formula for raw storage is: usable_bytes * (k + m) / k + metadata_overhead_per_object * object_count. Metadata overhead in production systems runs 1-4 KB per object depending on custom headers and ACL entries. A bucket with 1 billion objects can have 1-4 TB of pure metadata storage requirements.

For throughput planning, a single 10 GbE node with 36 SATA drives can sustain roughly 1-2 GB/s of sequential write throughput. Peak ingest often arrives in bursts (batch jobs, backups), so you should plan for 3-5x your average ingest rate at the node level.

Object size distribution matters. Systems optimized for large objects perform poorly on large counts of tiny objects. If your workload has many sub-1 KB objects (e.g., event payloads, log entries), consider compacting them into larger blobs at write time and treating them as segments within a larger file. This is how distributed logging systems like Kafka’s log segments work under the hood.

Multipart upload for large objects. Anything over 100 MB should use multipart upload, which lets you parallelize uploads and resume failed transfers. Each part becomes an independent EC stripe. The manifest (which parts in which order) is a metadata object stored separately. On completion, the parts are linked without physically copying bytes. Failed incomplete multiparts accumulate storage quietly: implement a lifecycle rule to abort them after 24-48 hours.

Hotspot mitigation for metadata. If all clients access the same bucket with the same key prefix, the metadata partition for that prefix becomes a hotspot. Solutions include: key prefix randomization (prepend a short hash), partition splitting (most systems do this automatically but with lag), and client-side request spreading across prefix ranges.

Garbage collection. Deletes in object storage are typically soft-deletes: a tombstone is written to the metadata log, and the actual shard data is reclaimed by a background GC process. Between the delete and GC, storage usage does not decrease. At scale, GC lag of hours to days is normal. Your capacity planning should account for 10-20% headroom above your steady-state usage to absorb GC lag during write spikes.

Observability. The five metrics that matter for an object storage cluster:

• Shard availability ratio: available_shards / total_shards per erasure group. Alert at anything below k / (k + m) (the reconstruction threshold).
• Metadata partition latency: p99 scan latency per partition. Degradation here surfaces as slow LIST operations before it surfaces as GET failures.
• Rebalancing throughput: bytes/sec being moved when nodes are added or removed. Rebalancing competes with client traffic for disk I/O.
• GC debt: bytes pending reclamation. Rising GC debt at constant delete rate indicates a GC throughput problem.
• Write amplification factor: actual bytes written to disks divided by client-visible bytes written. Should stay near (k + m) / k for steady-state workloads.

Cost Modeling

For a system targeting 1 PB usable capacity using RS(6,3):

Raw storage needed:    1 PB * 1.5x overhead = 1.5 PB raw
Metadata storage:      500M objects * 2 KB/object = ~1 TB (negligible)
Node count (36x14TB):  1.5 PB / (36 * 14 TB * 0.85 usable factor) ≈ 4 nodes
Plus metadata nodes:   3-node Raft cluster for metadata service

At $0.023/GB-month (self-hosted power + hardware amortized):
  1.5 PB/month ≈ $35,000/month for storage hardware
  Operations cost (requests, egress) is separate

Compare: AWS S3 Standard at $0.023/GB = $23,000/month for 1 PB usable
  but you pay for raw storage equivalent of ~1.5 PB in practice due to internal overhead
  and you also pay $0.09/GB egress after the free tier

The break-even point for building versus buying varies by access pattern. High-egress workloads (video streaming, large dataset exports) are where self-hosted or R2-style egress-free pricing changes the economics significantly. A system serving 500 TB of egress per month pays roughly $45,000/month in S3 egress fees alone.

Closing

Object storage looks like a simple key-value store from the outside. The interesting engineering is in the separation of concerns: the metadata plane handles consistency and namespace, the data plane handles durability and throughput, and erasure coding is the mechanism that makes the storage overhead of the data plane acceptable at scale. Understanding where these planes interact, where they fail independently, and what each layer optimizes for is what lets you make non-arbitrary decisions about object sizes, key naming conventions, consistency guarantees, and capacity headroom.

The consistent hashing ring, the EC scheme parameters, and the metadata partitioning strategy are all tunable knobs with concrete tradeoff profiles. Pick them based on your actual workload shape, not the default configuration of whatever managed service you are evaluating.