6 ms·

I enjoyed this article but I think the answer to the headline is obvious: parallelism

by dgllghr 1y ago

ffsm8 1y ago
That's like saying "how to get to the moon is obvious: traveling"
- crazygringo 1y ago
  I dunno, the article's tl;dr is just parallelism. Data gets split into redundant copies, and is rebalanced in response to hot spots. Everything in this article is the obvious answer you'd expect.
  - deleted 1y ago
    [deleted]
  - toolslive 1y ago
    It's not really "redundant copies". It's erasure coding (ie, your data is the solution of an overdetermined system of equations).
    - christina97 1y ago
      That’s just fractional redundant copies.
      - Dylan16807 1y ago
        And "fractional redundant copies" is way less obvious.
        crazygringo 1y ago
        The fractional part isn't helping them serve data any faster. To the contrary, it actually reduces the speed from parallelism. E.g. a 5:9 scheme only achieves 1.8x throughput, whereas straight-up triple redundancy would achieve 3x. It just saves AWS money is all, by achieving greater redundancy with less disk usage.
  - fair_enough 1y ago
    You're right if you're only looking at peak sequential throughput. However, and this is the part that the author could have emphasized more, the impressive part is their strategy for dealing with disk access latency to improve random read throughput. They shard the data as you might expect of a RAID, 5, 6, etc array and the distributed parity solves the problem of failure tolerance as you would expect and also improves bandwidth via parallelism as you describe. The interesting part is their best strategy for sharding the data: plain-old-simple random. The decision of which disks and at which sectors to shard the data is done at random, and this creates the best change that at least one of the two copies of data can be accessed with much lower latency (~1ms instead of ~8ms). The most crude, simple approach turns out to give them the best mileage. There's something vaguely poetic about it, an aesthetic beauty reminiscent of Euler's Identity or the solution to the Basel Problem; a very simple statement with powerful implications.
- DoctorOW 1y ago
  Thank you for setting me up for this... It's not exactly rocket science.
  - ffsm8 1y ago
    Haha, good one! I still feel like you're underselling the article however. Is obviously ultimately parallelism, but parallelism is hard at scale - because things often don't scale - and incorrect parallelism can even make things slower. And it's not always obvious why something gets slower by parallelism. As a dumb example, if you have a fictional HDD with one disk and one head, you have two straightforward options to optimize performance: Make sure only one file is read at the same time (otherwise the disk will keep seeking back and forth) Make sure the file is persisted in a way that you're only accessing one sector, never entering the situation in which it would seek back and forth. Ofc, that can be dumped down to "parallelism", because this is inherently a question about how to parallelize... But it's also ignoring that that's what is being elaborated on: ways s3 used to enable parallelism
timeinput 1y ago
I generally don't think about storage I/O speed at that scale (I mean really who does?). I once used a RAID0 to store data to HDDs faster, but that was a long time ago. I would have naively guessed an interesting caching system, and to some degree tiers of storage for hot vs cold objects. It was obvious after I read the article that parallelism was a great choice, but I definitely hadn't considered the detailed scheme of S3, or the error correction it used. Parallelism is the one word summary, but the details made the article worth reading. I bet minio also has a similar scaling story: parallelism.
- 0x457 1y ago
  My homelab servers all have raidz out of 3 nvme drives for this reason: higher parallelism without loosing redundancy. > I would have naively guessed an interesting caching system, and to some degree tiers of storage for hot vs cold objects. Caching in this scenario usually done outside of S3 in something like Cloudfront
- MrDarcy 1y ago
  If you’re curious about this at home, try Ceph in Proxmox.
  - glitchcrab 1y ago
    Unless you have a large cluster with many tens of nodes/OSDs (and who does in a homelab?) then using Ceph is a bad idea (I've run large Ceph clusters at previous jobs).
    - shric 1y ago
      Why is it a bad idea?
      - jodrellblank 1y ago
        Ceph's design is to avoid a single bottleneck or single point of failure, with many nodes that can all ingest data in parallel (high bandwidth across the whole cluster) and be redundant/fault tolerant in the face of disk/host/rack/power/room/site failures. In exchange it trades away some of: low latency, efficient disk space use, simple design, some kinds of flexibility. If you have a "small" use case then you will have a much easier life with a SAN or a bunch of disks in a Linux server with LVM, and probably get better performance. How does it work with no single front end[1] and no centralised lookup table of data placement (because that could be a bottleneck)? All the storage nodes use the same deterministic algorithm for data placement known as CRUSH, guided by placement rules which the admin has written into the CRUSH map, things like: - these storage servers are grouped together by some label (e.g. same rack, same power feed, same data centre, same site). - I want N copies of data blocks, separated over different redundancy / failure boundaries like different racks or different sites. There's a monitoring daemon which shares the CRUSH map out to each node. They get some data coming in over the network, work through the CRUSH algorithm, and then send the data internally to the target node. The algorithm is probabalistic and not perfectly balanced so some nodes end up with more data than others, and because there's no central data placement table this design is "as full as the fullest disk" - one full disk anywhere in the cluster will put the entire cluster into read-only mode until you fix it. Ceph doesn't easily run well with random cheap different size disks for that reason, the smallest disk or host will be a crunch point. It runs best with raw storage below 2/3rds full. It also doesn't have a single head which can have a fast RAM cache like a RAID controller can have.[2] Nothing about this is designed for the small business or home use case, it's all designed to spread out over a lot of nodes[3]. It’s got a design where the units of storage are OSDs (Object Storage Devices) which correspond roughly to disks/partitions/LVM volumes, each one has a daemon controlling it. Those are pulled together as RADOS (Reliable Autonomic Distributed Object Store) where Ceph internally keeps data, and on top of that the admin can layer user-visible storage such as the CephFS filesystem, Amazon S3 compatible object storage, or a layer that presents as a block device which can be formatted with XFS/etc. It makes a distributed system that can ingest a lot of data in parallel streams using every node’s network bandwidth, but quite a lot of internal shuffling of data around between nodes and layers adding latency, and there are monitor daemons and management daemons overseeing the whole cluster to keep track of failed storage units and make the CRUSH map available to all nodes, and those ought to be duplicated and redundant as well. It's a bit of a "build it yourself storage cluster kit" which is pretty nicely designed and flexible but complex and layered and non-trivial. There are some talks on YouTube by people who managed and upgraded it at CERN as targets of particle accelerators data which are quite interesting. I can only recommend searching for "Ceph at Cern" and there are many hours of talks, I can't remember which ones I've seen. Titles like: "Ceph at CERN: A Year in the Life of a Petabyte-Scale Block Storage Service", "Ceph and the CERN HPC Infrastructure", "Ceph Days NYC 2023: Ceph at CERN: A Ten-Year Retrospective", "Ceph Operations at CERN: Where Do We Go From Here?". [1] If you are not writing your own software that speaks to Ceph's internal object storage APIs, then you are fronting its with something like a Linux machine running an XFS filesystem or the S3-compatible gateway, and that machine becomes your single point of failure and bottleneck. Then you front one Ceph cluster with many separate Linux machines as targets, and have your users point their software to different front ends, and in that case why use Ceph at all? You may as well have had many Linux machines with their own separate internal storage and rsync, and no Ceph. Or two SANs with data replication between them. Do you need (or want) what Ceph does, specifically? [2] I have only worked on HDD based clusters, with some SSDs for storing metadata to speed up performance. These clusters were not well specced and the metadata overflowed onto the HDDs which didn't help anything. [3] There are ways to adjust the balance of data on each node to work with different size or nearly full disks, but if you get to read-only mode you end up waiting for it to internally rebalance while everything is down. This isn't so different to other storage like SANs, it's just that if you are going for Ceph you probably have a big cluster with a lot of things using it so a lot of things offline. You still have to consider running multiple Ceph clusters to limit blast radius of failures, if you are thinking "I don't want to bother with multiple storage targets I want one Ceph" you still need to plan that maybe you don't just want one Ceph.
gregates 1y ago
I think the article's title question is a bit misleading because it focuses on peak throughput for S3 as a whole. The interesting question is "How can the throughput for a GET exceed the throughput of an HDD?" If you just replicated, you could still get big throughput for S3 as a whole by doing many reads that target different HDDs. But you'd still be limited to max HDD throughput * number of GETs. S3 is not so limited, and that's interesting and non-obvious!
UltraSane 1y ago
Millions of hard drives cumulatively has enormous IO bandwidth.
3abiton 1y ago
I can only imagine the counts of those hdds

I enjoyed this article but I think the answer to the headline is obvious: parallelism

ffsm8 1y ago

That's like saying "how to get to the moon is obvious: traveling"

crazygringo 1y ago
I dunno, the article's tl;dr is just parallelism. Data gets split into redundant copies, and is rebalanced in response to hot spots. Everything in this article is the obvious answer you'd expect.
- deleted 1y ago
  [deleted]
- toolslive 1y ago
  It's not really "redundant copies". It's erasure coding (ie, your data is the solution of an overdetermined system of equations).
  - christina97 1y ago
    That’s just fractional redundant copies.
    - Dylan16807 1y ago
      And "fractional redundant copies" is way less obvious.
      - crazygringo 1y ago
        The fractional part isn't helping them serve data any faster. To the contrary, it actually reduces the speed from parallelism. E.g. a 5:9 scheme only achieves 1.8x throughput, whereas straight-up triple redundancy would achieve 3x. It just saves AWS money is all, by achieving greater redundancy with less disk usage.
- fair_enough 1y ago
  You're right if you're only looking at peak sequential throughput. However, and this is the part that the author could have emphasized more, the impressive part is their strategy for dealing with disk access latency to improve random read throughput. They shard the data as you might expect of a RAID, 5, 6, etc array and the distributed parity solves the problem of failure tolerance as you would expect and also improves bandwidth via parallelism as you describe. The interesting part is their best strategy for sharding the data: plain-old-simple random. The decision of which disks and at which sectors to shard the data is done at random, and this creates the best change that at least one of the two copies of data can be accessed with much lower latency (~1ms instead of ~8ms). The most crude, simple approach turns out to give them the best mileage. There's something vaguely poetic about it, an aesthetic beauty reminiscent of Euler's Identity or the solution to the Basel Problem; a very simple statement with powerful implications.
DoctorOW 1y ago
Thank you for setting me up for this... It's not exactly rocket science.
- ffsm8 1y ago
  Haha, good one! I still feel like you're underselling the article however. Is obviously ultimately parallelism, but parallelism is hard at scale - because things often don't scale - and incorrect parallelism can even make things slower. And it's not always obvious why something gets slower by parallelism. As a dumb example, if you have a fictional HDD with one disk and one head, you have two straightforward options to optimize performance: Make sure only one file is read at the same time (otherwise the disk will keep seeking back and forth) Make sure the file is persisted in a way that you're only accessing one sector, never entering the situation in which it would seek back and forth. Ofc, that can be dumped down to "parallelism", because this is inherently a question about how to parallelize... But it's also ignoring that that's what is being elaborated on: ways s3 used to enable parallelism

timeinput 1y ago

I generally don't think about storage I/O speed at that scale (I mean really who does?). I once used a RAID0 to store data to HDDs faster, but that was a long time ago. I would have naively guessed an interesting caching system, and to some degree tiers of storage for hot vs cold objects. It was obvious after I read the article that parallelism was a great choice, but I definitely hadn't considered the detailed scheme of S3, or the error correction it used. Parallelism is the one word summary, but the details made the article worth reading. I bet minio also has a similar scaling story: parallelism.

0x457 1y ago
My homelab servers all have raidz out of 3 nvme drives for this reason: higher parallelism without loosing redundancy. > I would have naively guessed an interesting caching system, and to some degree tiers of storage for hot vs cold objects. Caching in this scenario usually done outside of S3 in something like Cloudfront
MrDarcy 1y ago
If you’re curious about this at home, try Ceph in Proxmox.
- glitchcrab 1y ago
  Unless you have a large cluster with many tens of nodes/OSDs (and who does in a homelab?) then using Ceph is a bad idea (I've run large Ceph clusters at previous jobs).
  - shric 1y ago
    Why is it a bad idea?
    - jodrellblank 1y ago
      Ceph's design is to avoid a single bottleneck or single point of failure, with many nodes that can all ingest data in parallel (high bandwidth across the whole cluster) and be redundant/fault tolerant in the face of disk/host/rack/power/room/site failures. In exchange it trades away some of: low latency, efficient disk space use, simple design, some kinds of flexibility. If you have a "small" use case then you will have a much easier life with a SAN or a bunch of disks in a Linux server with LVM, and probably get better performance. How does it work with no single front end[1] and no centralised lookup table of data placement (because that could be a bottleneck)? All the storage nodes use the same deterministic algorithm for data placement known as CRUSH, guided by placement rules which the admin has written into the CRUSH map, things like: - these storage servers are grouped together by some label (e.g. same rack, same power feed, same data centre, same site). - I want N copies of data blocks, separated over different redundancy / failure boundaries like different racks or different sites. There's a monitoring daemon which shares the CRUSH map out to each node. They get some data coming in over the network, work through the CRUSH algorithm, and then send the data internally to the target node. The algorithm is probabalistic and not perfectly balanced so some nodes end up with more data than others, and because there's no central data placement table this design is "as full as the fullest disk" - one full disk anywhere in the cluster will put the entire cluster into read-only mode until you fix it. Ceph doesn't easily run well with random cheap different size disks for that reason, the smallest disk or host will be a crunch point. It runs best with raw storage below 2/3rds full. It also doesn't have a single head which can have a fast RAM cache like a RAID controller can have.[2] Nothing about this is designed for the small business or home use case, it's all designed to spread out over a lot of nodes[3]. It’s got a design where the units of storage are OSDs (Object Storage Devices) which correspond roughly to disks/partitions/LVM volumes, each one has a daemon controlling it. Those are pulled together as RADOS (Reliable Autonomic Distributed Object Store) where Ceph internally keeps data, and on top of that the admin can layer user-visible storage such as the CephFS filesystem, Amazon S3 compatible object storage, or a layer that presents as a block device which can be formatted with XFS/etc. It makes a distributed system that can ingest a lot of data in parallel streams using every node’s network bandwidth, but quite a lot of internal shuffling of data around between nodes and layers adding latency, and there are monitor daemons and management daemons overseeing the whole cluster to keep track of failed storage units and make the CRUSH map available to all nodes, and those ought to be duplicated and redundant as well. It's a bit of a "build it yourself storage cluster kit" which is pretty nicely designed and flexible but complex and layered and non-trivial. There are some talks on YouTube by people who managed and upgraded it at CERN as targets of particle accelerators data which are quite interesting. I can only recommend searching for "Ceph at Cern" and there are many hours of talks, I can't remember which ones I've seen. Titles like: "Ceph at CERN: A Year in the Life of a Petabyte-Scale Block Storage Service", "Ceph and the CERN HPC Infrastructure", "Ceph Days NYC 2023: Ceph at CERN: A Ten-Year Retrospective", "Ceph Operations at CERN: Where Do We Go From Here?". [1] If you are not writing your own software that speaks to Ceph's internal object storage APIs, then you are fronting its with something like a Linux machine running an XFS filesystem or the S3-compatible gateway, and that machine becomes your single point of failure and bottleneck. Then you front one Ceph cluster with many separate Linux machines as targets, and have your users point their software to different front ends, and in that case why use Ceph at all? You may as well have had many Linux machines with their own separate internal storage and rsync, and no Ceph. Or two SANs with data replication between them. Do you need (or want) what Ceph does, specifically? [2] I have only worked on HDD based clusters, with some SSDs for storing metadata to speed up performance. These clusters were not well specced and the metadata overflowed onto the HDDs which didn't help anything. [3] There are ways to adjust the balance of data on each node to work with different size or nearly full disks, but if you get to read-only mode you end up waiting for it to internally rebalance while everything is down. This isn't so different to other storage like SANs, it's just that if you are going for Ceph you probably have a big cluster with a lot of things using it so a lot of things offline. You still have to consider running multiple Ceph clusters to limit blast radius of failures, if you are thinking "I don't want to bother with multiple storage targets I want one Ceph" you still need to plan that maybe you don't just want one Ceph.

gregates 1y ago

I think the article's title question is a bit misleading because it focuses on peak throughput for S3 as a whole. The interesting question is "How can the throughput for a GET exceed the throughput of an HDD?" If you just replicated, you could still get big throughput for S3 as a whole by doing many reads that target different HDDs. But you'd still be limited to max HDD throughput * number of GETs. S3 is not so limited, and that's interesting and non-obvious!

UltraSane 1y ago

Millions of hard drives cumulatively has enormous IO bandwidth.

3abiton 1y ago

I can only imagine the counts of those hdds