Object Store: System Design

An object store keeps files of any size, from a thumbnail of a few kilobytes to a video of many gigabytes, and returns them on request by name. Photographs, backups, logs, the trained weights of machine learning models and the videos of chapter 17 all end up in a system of this kind, and a large one holds hundreds of petabytes on tens of thousands of disks.

At that scale the governing fact is that hardware fails continuously. A disk drive has perhaps a 2% chance of failing in any given year, so that among 20000 disks about 1 fails every day, as a matter of routine. Disks also fail in a quieter and more dangerous manner, by returning data that differs from what was written without reporting any error. A system that is to keep data for decades on such components cannot treat failure as an exceptional event to be handled when it occurs. It has to be built so that the loss of any disk, or any machine, or any rack of machines, at any moment, destroys nothing, and so that the damage is repaired automatically before a second failure can compound the first. This chapter is chiefly about how that is arranged, and about the related question of how to keep track of where everything is.

What an object store is

It is easiest to say what an object store is by contrast with the file system that every reader has used. A file system offers a tree of directories, files that can be opened and modified at any position, appended to, renamed and locked, and it is expected to make all of these operations consistent with one another. These features are costly to provide across many machines, and most large collections of data do not need them.

An object store offers much less and can therefore scale much further. An object is a sequence of bytes with a name, held in a container called a bucket. The name is a plain string. It may contain slashes, as in 2026/10/holiday.mp4, and tools display such names as if they were folders, yet the store itself knows of no directories and treats the name as a single key. An object is written whole and read whole or in ranges, and it is never modified in place: to change an object, one uploads a replacement under the same name. There is no appending, no partial overwriting and no renaming other than by copying.

The restriction to whole, immutable objects is what makes the rest of the design tractable. Data that never changes after it is written can be copied freely to several places without any risk of the copies diverging, can be verified against a checksum computed once, and can be cached anywhere.

Names in one place, bytes in another

An object store has 2 quite different things to remember about every object: what it is called and where its bytes are, which together are its metadata, and the bytes themselves. The 2 kinds of information have such different characteristics that they are kept in separate systems.

Metadata is small, a few hundred bytes per object, and is needed for every operation. It is updated when objects are created and deleted, it must be listed in the order of names, and it has to be strongly consistent, since an application that has just uploaded an object and been told so must find it when it asks. These are the requirements of a database, and the metadata is kept in a replicated, sharded key-value store of the kind built in chapters 1 to 6, keyed by bucket and object name.

The bytes are large, are written once and never altered, and are read sequentially. They need no ordering, no transactions and no queries. What they require is a great deal of cheap disk space and protection against the loss of disks. They are kept on storage nodes, which are machines with many disks and very simple software that stores and returns pieces of data by identifier.

This separation has a practical consequence for every request. A download first asks the metadata store where the pieces of the object are, and then fetches the pieces from storage nodes. An upload proceeds in the opposite order, writing the pieces to storage nodes first and recording the object in the metadata store last. The order of an upload is deliberate. The metadata entry is the single point at which an object comes into existence, and it is created only when all the bytes are safely stored, so that an upload interrupted in the middle leaves behind some unreferenced pieces, to be cleaned up later, and never an object that claims to exist and cannot be read.

Chunks

Objects range in size over 9 orders of magnitude, and it is impractical to handle a 5 TB object as 1 unit: it would not fit on a single disk together with others, could not be read in parallel, and would have to be copied in its entirety to repair the loss of any part. Objects are therefore cut into chunks of a fixed maximum size, a few megabytes, and each chunk is stored and protected independently. The metadata of an object lists its chunks in order.

A chunk needs an identifier under which storage nodes can keep it, and a particularly useful choice is to name each chunk by a hash of its contents. Naming data by its own hash is called content addressing, and it has 2 valuable consequences. The first is that integrity can be checked by anyone at any time: whoever holds a chunk can recompute the hash and compare it with the name, and a mismatch proves that the bytes have been altered. The second is that identical chunks receive identical names and so are stored only once, however many objects contain them, which is called deduplication.

The simulation for this chapter uploads a file of 10 MB, which is cut into 3 chunks of at most 4 MB, each stored on 3 of 6 nodes. It then uploads the same bytes again under another name, and the second upload writes no chunks at all, the 3 it needs being already present. The store holds 2 objects and the bytes of 1.

Content addressing demands a hash function for which it is not feasible to find 2 different inputs with the same output, since 2 different chunks with the same name would be treated as the same chunk and 1 of them would be lost. The simulation uses a short checksum for brevity, and a real store uses a cryptographic hash of 256 bits.

Surviving the loss of disks

Every chunk must survive the failure of the disks that hold it, and there are 2 ways of arranging this.

Copies

The simple way is replication: each chunk is stored in full on 3 different storage nodes. Any 1 of the copies suffices to read the chunk, so that the chunk survives the loss of any 2 nodes. Reading is fast, since any copy will serve, and repairing a lost copy consists of reading 1 of the survivors and writing it elsewhere. The cost is space. Every terabyte of objects occupies 3 terabytes of disk, and at 100 petabytes this overhead is 200 petabytes of disks that hold nothing but duplicates.

Parity

The economical way stores extra information from which lost pieces can be recomputed, in place of whole copies. The principle can be shown with ordinary addition.

In this small example, 4 disks protect 3 disks’ worth of data against the loss of any 1 disk. To protect the same data against 1 loss by replication would require 2 full copies and therefore 6 disks.

Practical systems extend the idea to tolerate several losses. A chunk is divided into k data pieces, and m additional parity pieces are computed from them, each by a different combination, in such a way that any k of the k + m pieces are sufficient to reconstruct the original. The technique is called erasure coding. Its arithmetic is carried out in a number system devised so that the necessary equations can always be solved, which is more elaborate than addition and rests on the same idea. A common choice is 10 data pieces and 4 parity pieces, stored on 14 different nodes.

The comparison is striking. The coded chunk occupies 1.4 times its own size where replication occupies 3 times, and it survives the loss of any 4 pieces where replication survives the loss of 2. At 100 petabytes of objects, the difference is 160 petabytes of disks.

Erasure coding exacts its price elsewhere. Computing parity takes processor time on every write. Reading normally touches only the data pieces, and when 1 of them is unavailable the reader must fetch 10 other pieces and compute the missing one, which makes reads of damaged chunks slow. Repair is costlier in the same way: to rebuild a single lost piece, 10 pieces must be read over the network, where replication reads 1. And the scheme is unsuitable for small objects, for which the fixed work of dealing with 14 nodes outweighs the saving in space.

Large stores accordingly use both. Small objects and recently written, frequently read data are replicated, for speed. Large objects, and data that has grown cold, are erasure coded, for economy, and a background process converts data from the first form to the second as it ages.

Where the copies go

The number of copies is only half of durability. Their placement is the other half. 3 copies on 3 disks of the same machine are all lost when that machine’s power supply fails, and 3 copies on 3 machines in the same rack are all unreachable when the rack’s network switch fails. Failures of this kind, in which many components go down together for a common reason, are called correlated, and they are far more common than a calculation that treats disks as independent would suggest.

A group of components that may fail together is called a failure domain, and the rule for placement is that the copies or pieces of a chunk are spread over as many failure domains as possible: on different machines, in different racks, and for the most valuable data in different buildings. The system must know the physical arrangement of its machines in order to apply this rule, and the rule has to be reapplied whenever data is moved for repair or rebalancing.

Silent damage

The failures discussed so far announce themselves. A dead disk returns errors, and a dead machine does not respond. A more insidious failure is the disk that works and returns the wrong bytes. Magnetic media decay, firmware has defects, and a write is occasionally directed to the wrong place. The rate of such events is low for any 1 disk and, across tens of thousands of disks and many years, they are a certainty. Because the disk reports success, nothing prompts anybody to look, and the damage lies undiscovered until the data is next read, which for an archive may be years later.

The defence has 2 parts. Every chunk is stored together with a checksum of its contents, and every read verifies the bytes against the checksum before returning them, so that damaged data is never served to a client. This alone is insufficient, since it finds damage only in data that happens to be read. The second part is therefore a background process, the scrubber, which reads every chunk on every disk in rotation, verifies it, and arranges for the repair of any that fails.

The simulation damages a single byte in 1 copy of 1 chunk and then reads the object. The read detects the mismatch, takes the chunk from another node, returns the correct 10485760 bytes, and repairs the damaged copy in passing.

The importance of scrubbing lies in the timing. A chunk with 3 copies survives the corruption of 1 or 2 of them provided the damage is found and repaired while a good copy still exists. If nothing looks for years, the damage accumulates unobserved, and the day arrives on which the last good copy of some chunk is found to be bad as well. Redundancy protects data only for as long as lost redundancy is promptly restored.

Repair

When a disk or node fails, every chunk that had a copy there is left with 1 copy fewer than it should have. A repair process detects this, from the absence of the node’s heartbeats or from the scrubber’s reports, and creates new copies on other nodes from those that remain.

The durability of the whole store depends more on the speed of repair than on any other single factor. A chunk with 3 copies is lost only if all 3 fail, and what matters is the length of the interval during which it is exposed. If a failed copy is replaced within an hour, the chunk is lost only if 2 further specific disks fail within that hour, which is extraordinarily improbable. If replacement takes a week, the window is 168 times longer and the probability of loss correspondingly greater. The remarkable durability figures quoted for large object stores are obtained less by keeping many copies than by repairing quickly.

Repair nevertheless has to be restrained in 2 respects. A node that has merely been restarted for maintenance will return in a few minutes with its data intact, and to begin copying terabytes the instant it disappears would be wasted effort, so repair waits for a short period before acting. And when an entire rack fails, the repair of all its chunks at once could saturate the network and disturb the service to clients, so repair is rate limited and proceeds in order of urgency, attending first to the chunks that have the fewest surviving copies.

Very large objects

An object of 50 GB cannot sensibly be uploaded in a single HTTP request, since any interruption in several hours of transfer would oblige the client to begin again. Object stores therefore offer multipart upload. The client announces that it intends to upload a large object and receives an identifier for the upload. It then sends the object in numbered parts of some tens of megabytes each, in any order and several in parallel, and a part that fails is sent again by itself. When every part has arrived, the client sends a final request listing them, and the store assembles the object by writing a metadata entry that refers to the chunks of all the parts in sequence.

Until that final request, the object does not exist as far as readers are concerned, which preserves the rule that an object appears whole or not at all. Uploads that are begun and never completed leave their parts behind, and a store needs a policy for discarding them after a time, since they would otherwise accumulate invisibly and be charged for.

Downloads have a corresponding facility in the range request, by which a client asks for a stated range of bytes within an object. The store determines from the metadata which chunks cover the range and fetches only those. A video player uses this to jump to the middle of a film without downloading what precedes it, and an interrupted download can be resumed from the point it had reached.

Deleting, and collecting unused chunks

Deleting an object removes its metadata entry, upon which the object ceases to exist for clients at once. Its chunks cannot be deleted at the same moment, for 2 reasons. With deduplication, a chunk may also belong to other objects. And the deletion of chunks on many nodes is slow work that should not hold up the client’s request.

Chunks that are no longer referred to by any object are therefore removed afterwards, by a background process of garbage collection. It determines which chunks are in use, by examining the metadata, and deletes those on the storage nodes that are not. This process contains a race that has cost real systems real data.

The collector’s knowledge of what is unused is necessarily a little out of date, and an upload that arrives in the meantime may rely on a chunk that the collector has already condemned. The standard protection is a period of grace. A chunk is deleted only when it has been unreferenced continuously for a substantial time, a day for example, and an upload that reuses an existing chunk records the fact in a way that restarts the period. The store thus retains some garbage for a day longer than strictly necessary, which is a trivial price for the assurance that nothing in use is ever removed.

Many stores also offer versioning, under which replacing or deleting an object retains the previous version, the latest version being what a plain request returns. This protects against deletion by mistake and against software that overwrites good data with bad, and it is among the few defences against an operator’s or a program’s own errors, which replication does nothing to prevent, since a mistaken deletion is replicated as faithfully as anything else.

Use cases

Applications upload, download and list objects. Operators replace failed hardware, which in a store of this size is a daily task.

Functional requirements

Non-functional requirements

The store combines 2 consistency models. Metadata is strongly consistent: once an upload has been confirmed, every subsequent request for that name finds the new object, and a listing of the bucket includes it. This property, known as read-after-write consistency, is what applications expect, and its absence from some early object stores was a persistent source of defects in the software built on them. The chunks need no consistency model in the usual sense, because they are immutable. A chunk either exists under its name with the correct contents, or it does not exist, and no reader can ever observe an out-of-date version of one.

Core entities

Capacity estimate

Arithmetic ahead. 100 PB in 3 copies is 300 PB, about 21000 disks of 16 TB, with 25 billion chunks to keep track of.

Skip to the high-level design

Show the calculation

Quantity	Calculation	Result
Raw storage	100 PB × 3 copies	300 PB
Disks of 16 TB, 90% full	300 PB ÷ 14.4 TB	20834
Chunks of 4 MB	100 PB ÷ 4 MB	25 billion
Metadata	1 billion objects × 1 KB	1 TB

The API

The API is that of HTTP applied directly to objects. PUT stores an object under a name, GET retrieves it, and DELETE removes it.

Upload an object

PUT /v1/buckets/holiday/video.mp4 HTTP/1.1
Host: objects.example
Content-Type: video/mp4
Content-Length: 10485760

(10485760 bytes)

HTTP/1.1 201 Created
ETag: "crc32:9a3f11c2-3"

Clients can compare the ETag, which names the content, with their own checksum.

Download part of an object

GET /v1/buckets/holiday/video.mp4 HTTP/1.1
Host: objects.example
Range: bytes=0-1048575

HTTP/1.1 206 Partial Content
Content-Range: bytes 0-1048575/10485760
Content-Length: 1048576

(1048576 bytes)

With a range, a video player fetches only the part it is about to show.

Applications frequently wish to let a user’s browser upload or download an object directly, without the bytes passing through the application’s own servers. For this the application generates a presigned URL: an ordinary address for the object that carries an expiry time and a signature computed with the application’s secret key. Anyone holding the address may perform the 1 operation it describes until it expires, and the store verifies the signature without needing to consult the application.

High-level design

One request, step by step

The steps follow the arrows of figure 16.7.

1. An application sends PUT /v1/buckets/holiday/video.mp4 with the file as the body.
2. The API server reads the body 4 MB at a time. It computes each chunk’s checksum and stores the chunk on 3 storage nodes.
3. When every chunk is stored, the API server writes 1 record to the metadata store: the object’s name and its list of chunk names.
4. In the background, the repair worker checks that every chunk still has 3 good copies, and makes a new copy where 1 is missing.

The design, deployed

The front end is a large stateless tier of API servers behind load balancers. Below it the 2 kinds of storage are plainly separate: 60 machines of the metadata store, which is 20 shards of 3 replicas each, and 600 storage nodes with some 36 disks apiece, which hold the bytes. The bottom tier is peculiar to storage systems. It serves no request, and it runs all the time: a scrubber on every node reading its disks in rotation, a pool of repair workers, and the garbage collector. A store of this size loses a disk on most days, and this tier is what turns that from an event into routine.

How real systems do it

The published designs of large stores show a clear progression, and this chapter compresses several generations into 1.

The Google File System of 2003 established the pattern of a metadata service and many chunk servers, with chunks of 64 MB kept in 3 copies. Facebook’s Haystack, in 2010, addressed a problem that this chapter passes over: a store of billions of small photographs spends most of its disk operations on locating files and very few on reading them, and Haystack packed many photographs into each large file with an index held in memory, so that a read needs a single disk operation. Any store of small objects has to do something of the kind, and a design that kept every object as a separate file would not survive.

For data that is seldom read, Facebook then built f4, which replaces copies by erasure coding with exactly the scheme of this chapter, 10 data blocks and 4 parity blocks, at 1.4 times the size of the data within a data centre. The paper gives the effective overhead of Haystack as 3.6, since it kept 3 copies on disks that were themselves in redundant arrays, and that of f4 as 2.1 once a further coding across data centres is included. Microsoft’s storage system uses a variant, local reconstruction codes, which adds parity blocks that each cover half of the data blocks, so that the common case of a single lost block is repaired by reading 6 blocks where the plain scheme reads 10 or more.

On placement, a paper from Stanford made precise the danger of correlated failures. When replicas are placed on nodes chosen at random, almost any simultaneous loss of 3 nodes in a large cluster destroys some chunk, because nearly every combination of 3 nodes holds the replicas of something. Restricting placement to a limited number of fixed groups of nodes makes a simultaneous loss far less likely to hit all copies of anything, at the cost of losing more when it does.

The deduplication of identical chunks described in this chapter is characteristic of backup and file synchronisation systems, and public object stores generally do not practise it across customers, in part because it lets 1 customer discover whether another holds a given file. And the consistency that this chapter requires of metadata was for many years not provided by the largest public store, Amazon’s S3, which offered it only from the end of 2020.

Mistakes to avoid

Failures

Trade-offs

The simulation

References

• S. Ghemawat, H. Gobioff and S. Leung, “The Google File System”, SOSP 2003.
• D. Beaver and others, “Finding a Needle in Haystack: Facebook’s Photo Storage”, OSDI 2010.
• S. Muralidhar and others, “f4: Facebook’s Warm BLOB Storage System”, OSDI 2014.
• C. Huang and others, “Erasure Coding in Windows Azure Storage”, USENIX ATC 2012.
• A. Cidon and others, “Copysets: Reducing the Frequency of Data Loss in Cloud Storage”, USENIX ATC 2013.
• B. Calder and others, “Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency”, SOSP 2011.
• Amazon Web Services, “Amazon S3 Update: Strong Read-After-Write Consistency”, 2020.

Terms introduced in this chapter