S3 organizes objects into buckets. Buckets have unique names, and objects have unique keys. To find a specific object by key or partial key (prefix) several data structures would work. I believe under the hood S3 uses skip lists to quickly access, insert, delete objects. If you have the full key of something — like a bucket name — hashing would also work.
Obviously simplified because S3 has security, replication, versioning, and supports indexes and searching within objects, but the basic data structures and algorithms are well known and not all that complicated in principle.
and these data structures are themselves able to span hundreds/thousands of disks? eg. what happens when a customer's bucket/object are too many such that the skip list "indexing" them cannot fit in a single harddrive?
This kind of logical media mapped to physical media goes back to magnetic tape, predating disks and solid state storage.
Database systems solve this same problem. A database table may include millions of rows and indexes, too big to fit into RAM all at once. The index trees, for example, get loaded in pages. There’s no need to have the entire index in memory, only the relevant parts of it.
3 comments
[ 4.6 ms ] story [ 47.9 ms ] threadhttps://docs.aws.amazon.com/AmazonS3/latest/userguide/Welcom...
S3 organizes objects into buckets. Buckets have unique names, and objects have unique keys. To find a specific object by key or partial key (prefix) several data structures would work. I believe under the hood S3 uses skip lists to quickly access, insert, delete objects. If you have the full key of something — like a bucket name — hashing would also work.
Obviously simplified because S3 has security, replication, versioning, and supports indexes and searching within objects, but the basic data structures and algorithms are well known and not all that complicated in principle.
https://en.wikipedia.org/wiki/Logical_disk
This kind of logical media mapped to physical media goes back to magnetic tape, predating disks and solid state storage.
Database systems solve this same problem. A database table may include millions of rows and indexes, too big to fit into RAM all at once. The index trees, for example, get loaded in pages. There’s no need to have the entire index in memory, only the relevant parts of it.