The Flat Keyspace: What an Object Store Does and Does Not Provide

A name, a byte string, and a map of metadata

An object store answers four questions. Given a key, it can return the bytes stored under that key, replace those bytes, remove them, or enumerate the keys that share a prefix. Everything else in the interface is built from these four operations, and the properties that follow are consequences of them rather than independent features.

The value side is deliberately opaque. The service stores the bytes and returns them; it does not parse them, index them, or expose their internal structure. A file in a local filesystem has an inode with block pointers, a size, timestamps, permissions, and the possibility of sparse holes; an object has a key, a length, an entity tag, a last-modified time, a content type, and an arbitrary user metadata map. The metadata map is small, a few kilobytes at most on the major services, and it is written and replaced along with the object, never mutated in place. Changing a content type means rewriting the object’s metadata record, which on most services is expressed as a server-side copy that names the same bytes and a new metadata set.

Keys are strings, not paths. They are sequences of Unicode characters, conventionally capped at 1024 bytes of UTF-8, and the service assigns no meaning to any character inside them. A key containing / looks like a path only because clients and listing operations agree to treat that character specially; the store itself has one flat ordered map. Two keys can differ only by a trailing slash, and both can exist simultaneously. A key that ends in / is a zero-byte object indistinguishable from any other zero-byte object, which is why “folder placeholder” objects are a convention rather than a data type.

The write operation is a whole-object replacement. A PUT either creates the key or overwrites the bytes previously stored there, and the replacement is atomic with respect to readers: a concurrent GET observes the complete old object or the complete new one. There is no partial write visible to a reader, no append, no truncate, and no way to modify a byte range in place. That single decision removes an entire class of torn-read bugs and removes an equally large class of useful operations.

Prefixes and delimiters simulate a tree that is not there

Because the keyspace is one sorted sequence, hierarchy has to be reconstructed at read time. A list request carries three parameters: a prefix that every returned key must start with, a delimiter character, and a continuation token. The service walks its ordered index from the prefix, and for each key it looks at the substring following the prefix up to the first occurrence of the delimiter. If the delimiter is absent from that remainder, the key is returned as an object. If it is present, the truncated string up to and including the delimiter is collected into a set of common prefixes, and the scan skips ahead past that group.

The skip is the important part. Listing with a delimiter is not a tree traversal; it is a range scan over a sorted index with a seek after each group. The work performed is proportional to the number of distinct groups encountered, not to the number of objects beneath them, which is why a listing of a prefix holding ten million keys can return promptly when the delimiter is / and the first path segment has few distinct values. It is also why a listing without a delimiter over the same prefix must materialise the keys in pages: the major services cap a single response at 1000 keys and hand back a continuation token that encodes where the scan stopped.

The ordering is byte order, not locale order. In UTF-8, uppercase letters sort before lowercase ones, so Archive/ precedes archive/, and a key a sorts before a/b because the shorter string is a prefix of the longer one. Keys that are prefixes of other keys therefore appear in the same region of the scan as their descendants, and a key named logs/ will be returned alongside the common prefix logs/ derived from logs/2026/... in a way that surprises code expecting one or the other.

A small script makes the grouping rule explicit:

def group(keys, prefix, delimiter="/"):
    """Reproduce what a delimited list returns over a sorted key sequence."""
    objects, common = [], set()
    for key in keys:
        if not key.startswith(prefix):
            continue
        rest = key[len(prefix):]
        cut = rest.find(delimiter)
        if cut == -1:
            objects.append(key)
        else:
            common.add(prefix + rest[:cut + len(delimiter)])
    return objects, sorted(common)

keys = ["logs/", "logs/2026/readme", "logs/2027/a.gz", "logs/2027/b.gz"]
print(group(keys, "logs/"))
# (['logs/'], ['logs/2026/', 'logs/2027/'])

The result holds one object and two common prefixes, and it says nothing about the two files under logs/2027/: they are collapsed into the prefix and only become visible when the listing is repeated with logs/2027/ as the prefix. Note also that logs/ is returned as an object while logs/2026/ is returned as a prefix even though neither exists as anything other than a naming convention. Nothing in the store distinguishes them.

Rename is a copy plus a delete, and it is not atomic

Changing an object’s key requires writing the bytes under the new key and deleting the old one. Two requests, no transaction spanning them, and a window during which both copies exist or, if the delete is issued first, neither. The cost is proportional to the object’s size in the general case: a server-side copy may avoid moving bytes across the network, but it still reads and writes storage and, on some services and class combinations, incurs retrieval charges. A filesystem rename is a directory-entry update of constant cost; an object rename of a 100 GB object is a 100 GB operation.

The same arithmetic scales to directory-shaped prefixes. Renaming a prefix holding ten thousand keys means ten thousand copies and ten thousand deletes, each individually atomic, collectively offering no guarantee. A reader listing during the process sees a mixture of old and new names, and an interrupted run leaves a partial migration that must be reconciled by comparing listings.

This is the constraint that most often decides an architecture. The familiar pattern of writing to a temporary name and renaming into place, which gives atomic publication through a directory entry, has no counterpart. What replaces it is indirection through a small object whose replacement is atomic: a manifest, a pointer file, or an index that names the current generation of data. The commit is then a single-key write, and the problem moves to ensuring that two writers cannot both publish. That problem is treated in conditional writes and prefix-based coordination and in atomic commit over object stores, and it is strictly harder than the rename it replaces.

There is a second, subtler consequence. Because overwrite discards the previous bytes, any operation that needs to retain history must either enable versioning at the bucket level or write a new key per generation. Versioning is not a filesystem-like journal; it keeps every version as a separately addressable object and marks deletion with a placeholder rather than recording an intent to remove bytes.

The limits that show up in the API surface

The service publishes hard bounds that reveal the shape of the implementation. A single PUT is capped at 5 GiB and a whole object at 5 TiB, so anything larger than the former must be assembled from parts through a multipart upload. Multipart upload allows at most 10,000 parts, each between 5 MiB and 5 GiB except the last, which means the practical minimum part size for a maximum-size object is fixed by division rather than by choice. Those numbers exist because the store commits an object by writing an index entry that references a list of immutable extents, and a single request cannot produce an unbounded number of extents.

The entity tag is a quoted string whose value depends on how the object was written. For a single-request upload it is commonly the MD5 digest of the bytes, which makes it usable as an integrity check. For a multipart object it is a digest computed over the digests of the parts, with a suffix giving the part count, so it is not the MD5 of the assembled object and cannot be compared against a locally computed MD5. Code that treats the entity tag as a universal checksum works until the first object larger than the single-request limit, then fails silently. Per-part checksums exist for exactly this reason and are covered in multipart upload part sizing.

Reads are whole-object or ranged. A ranged read returns a byte interval and is the only way to touch part of an object without transferring all of it, which makes it the basis for random access over immutable blobs; the mechanics, including the partial-content response and its interaction with caching, belong to byte-range reads and parallel fetch. Writes have no such option. The asymmetry is deliberate: an immutable extent can be replicated and checksummed once, whereas an in-place overwrite requires coordination across every replica holding that extent.

Finally, the store offers no cross-object atomicity and no locking primitive beyond per-key conditional requests. A group of objects that must change together has to be made to change through one object. That is not a limitation the services are likely to lift, since the coordination cost would be paid by every workload whether or not it needed the guarantee. Durability and the visibility rules for reads and listings are the subject of durability and read-after-write consistency, which is where the flat keyspace meets the network.