Ask HN: How does S3 locate object data?
What's the average amount of data in a region now? Exabyte? Jumanjibyte? How do they locate a specific object in a literal sea of harddrives?
https://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.