4 ms·

I have encountered multiple claims that in-memory analytics databases are often constrained by memory bandwidth, and I myself held that misconception for longer

by nkurz 8y ago

I have encountered multiple claims that in-memory analytics databases are often constrained by memory bandwidth, and I myself held that misconception for longer than I want to admit. So if not memory-bandwidth, what is the constraining factor? Or specifically, what's the limiting factor that causes the observed benchmark speeds for LocustDB? My guess would be that a well designed in-memory database should be limited by memory-bandwidth, but that real-world memory-bandwidth shouldn't be thought of as a single number. Instead, it depends on the size and pattern of requests, the latency of different cache hierarchies, and (crucially but often forgotten) on the number of requests in flight. Is there a better terminology that distinguishes these two uses of memory-bandwidth?

blattimwind 8y ago
> there a better terminology that distinguishes these two uses of memory-bandwidth? theoretical peak bandwidth effective/observed bandwidth
- nkurz 8y ago
  That's not the distinction I'm looking for. I'm looking for a better term to describe the throughput the application would achieve if all non-memory constraints were removed. In the context of the article, the author is comparing the ratio of the "effective/observed bandwidth" and the "theoretical peak bandwidth", noting that the ratio is large, and concluding that he is not constrained by memory bandwidth. I don't know that this is a reasonable conclusion. I'm looking for a different denominator, which is also theoretical. Maybe call it the "theoretically achievable bandwidth", which takes into account all the details of the requests. If the "observed bandwidth" equals the "theoretically achievable bandwidth", your only path to improvement is to change your data layout or increase the parallelism of your requests. If the "observed bandwidth" is less than this theoretical, there should still be room for implementation optimizations. Falling short of the "theoretical peak bandwidth" (even by a lot) doesn't tell you which of these is the case.
  - squeed 8y ago
    Hmm. I'm not exactly sure if it's what you mean, but in the networking world, we use the term "Goodput" as a shorthand for "actual user-observed bandwidth".
cwinter 8y ago
The constraining factor in this case is CPU throughput. The CPU cannot execute instructions fast enough to keep up with the data being read in from memory. Of course you are right that this is not the whole picture, it is possible to be bottlenecked on neither memory bandwidth nor CPU throughput. With respect to memory, two additional considerations are read amplification and latency. Read amplification: Read amplification basically means that you are reading data but not actually using it. Suppose we have a table stored in row format with four columns C1, C2, C3, C4 which store 8 byte integers. Row format means that the values for the columns are interleaved, so the memory layout would look like this, where cn refers to some value for column Cn: 0x0000 c1 c2 c3 c4 c1 c2 c3 c4 0x0040 c1 c2 c3 c4 c1 c2 c3 c4 ... One property of conventional memory is that we can only read memory in blocks of 64bytes (the size of a cache line). So if we have a loop that sums of all of the values in C1, we will actually also load all of the values for columns C2, C3, C4. This means we have a read amplification of factor 4, and our usable bandwidth will be a quarter of the theoretical maximum. Latency: Suppose we also don't have any read amplification and make use of all values for each loaded cache line. Then after we finish processing a cache line, and load the next cache line, we might have to wait a long time (100s of cycles) before the new cache line actually arrives! So then we would actually be stalled because of memory latency during some parts of program execution. One of the big advantages of using columnar layout (which stores all values for a column sequentially) is that it all but eliminates read amplification. Similarly, by accessing data sequentially we make it possible for the CPU to predict what data will be accessed in the future, and have it loaded into the cache before we even request it. Of course there's a number of reasons why things might not work out quite so perfectly in practice, and those may why performance in this benchmark starts to degrade before the (usable) memory bandwidth reaches the theoretical maximum memory bandwidth. But as you can see it still possible to get very close, so it's safe to assume that queries which read much less data than the maximum bandwidth are constrained on CPU.
- taeric 8y ago
  Have we really progressed memory speeds to the point that reading memory is faster than execution speed on the processor? That just feels wrong. Your other points make sense. And those would surface as constraints in a similar fashion as a CPU throughput limitation would. I just expect those well before a CPU constraint. I confess I have not researched CPU speeds in quite a while. Nor RAM speeds. Just surprised to see that the CPU's throughput would ever really be the bottleneck.

by nkurz 8y ago

blattimwind 8y ago

> there a better terminology that distinguishes these two uses of memory-bandwidth? theoretical peak bandwidth effective/observed bandwidth

nkurz 8y ago
That's not the distinction I'm looking for. I'm looking for a better term to describe the throughput the application would achieve if all non-memory constraints were removed. In the context of the article, the author is comparing the ratio of the "effective/observed bandwidth" and the "theoretical peak bandwidth", noting that the ratio is large, and concluding that he is not constrained by memory bandwidth. I don't know that this is a reasonable conclusion. I'm looking for a different denominator, which is also theoretical. Maybe call it the "theoretically achievable bandwidth", which takes into account all the details of the requests. If the "observed bandwidth" equals the "theoretically achievable bandwidth", your only path to improvement is to change your data layout or increase the parallelism of your requests. If the "observed bandwidth" is less than this theoretical, there should still be room for implementation optimizations. Falling short of the "theoretical peak bandwidth" (even by a lot) doesn't tell you which of these is the case.
- squeed 8y ago
  Hmm. I'm not exactly sure if it's what you mean, but in the networking world, we use the term "Goodput" as a shorthand for "actual user-observed bandwidth".

cwinter 8y ago

The constraining factor in this case is CPU throughput. The CPU cannot execute instructions fast enough to keep up with the data being read in from memory. Of course you are right that this is not the whole picture, it is possible to be bottlenecked on neither memory bandwidth nor CPU throughput. With respect to memory, two additional considerations are read amplification and latency. Read amplification: Read amplification basically means that you are reading data but not actually using it. Suppose we have a table stored in row format with four columns C1, C2, C3, C4 which store 8 byte integers. Row format means that the values for the columns are interleaved, so the memory layout would look like this, where cn refers to some value for column Cn: 0x0000 c1 c2 c3 c4 c1 c2 c3 c4 0x0040 c1 c2 c3 c4 c1 c2 c3 c4 ... One property of conventional memory is that we can only read memory in blocks of 64bytes (the size of a cache line). So if we have a loop that sums of all of the values in C1, we will actually also load all of the values for columns C2, C3, C4. This means we have a read amplification of factor 4, and our usable bandwidth will be a quarter of the theoretical maximum. Latency: Suppose we also don't have any read amplification and make use of all values for each loaded cache line. Then after we finish processing a cache line, and load the next cache line, we might have to wait a long time (100s of cycles) before the new cache line actually arrives! So then we would actually be stalled because of memory latency during some parts of program execution. One of the big advantages of using columnar layout (which stores all values for a column sequentially) is that it all but eliminates read amplification. Similarly, by accessing data sequentially we make it possible for the CPU to predict what data will be accessed in the future, and have it loaded into the cache before we even request it. Of course there's a number of reasons why things might not work out quite so perfectly in practice, and those may why performance in this benchmark starts to degrade before the (usable) memory bandwidth reaches the theoretical maximum memory bandwidth. But as you can see it still possible to get very close, so it's safe to assume that queries which read much less data than the maximum bandwidth are constrained on CPU.

taeric 8y ago
Have we really progressed memory speeds to the point that reading memory is faster than execution speed on the processor? That just feels wrong. Your other points make sense. And those would surface as constraints in a similar fashion as a CPU throughput limitation would. I just expect those well before a CPU constraint. I confess I have not researched CPU speeds in quite a while. Nor RAM speeds. Just surprised to see that the CPU's throughput would ever really be the bottleneck.