How do compare-and-swap atomics fare on persistent memory?

[Niall Douglas]

My apologies in advance that this question isn't about the pmem libraries, but rather about the nature of persistent memory.

I'm the main person working on adding persistent memory support to the C++ language standard. One of the algorithms which I need to write next is an optionally concurrent B+ tree implementation which works out of a single self-expanding mapped file, specifically a https://ned14.github.io/afio/classafio__v2__xxx_1_1mapped__file__handle.html which will be the proposed main workhorse object for mapped filesystem memory.

I have no access to actual persistent memory, so I've been writing my algorithms to date using standard atomics which I would assume will work as expected on persistent memory by fencing via atomics when writes are sent to the device in relation to other writes, and thus ensuring a sequential consistency of writes, and thus recovery after a sudden power loss.

However what kind of performance damage is there with using std::atomic on persistent memory? For example, Intel CPUs have implicit acquire release semantics in all their loads and stores. I would hope that persistent memory observes those (please definitely do say if it doesn't!). But what about LOCK CMPXCHG which is a read-modify-write operation? Is this a similar speed to RAM? Is it vastly slower? If so, by what order of magnitude? How well does persistent memory cope with cache line contention i.e. multiple threads all fighting over the same CMPXCHG?

I appreciate that the answer to all the above will vary according to the persistent memory technology. So, Optane probably does CMPXCHG much better than NAND for example. Nevertheless, some rough ballpark figures for the relative differences over RAM for various technologies would be extremely useful to me for implementing the optionally concurrent B+ tree implementation which needs to handle sudden power loss correctly.

My thanks in advance.

Niall

[Piotr Balcer]

Hi Niall,

W dniu środa, 21 lutego 2018 22:55:39 UTC+1 użytkownik Niall Douglas napisał:

My apologies in advance that this question isn't about the pmem libraries, but rather about the nature of persistent memory.

That's no problem at all. While we do have overwhelming number of mails about our libraries, this forum is about persistent memory in general.
 

I'm the main person working on adding persistent memory support to the C++ language standard. One of the algorithms which I need to write next is an optionally concurrent B+ tree implementation which works out of a single self-expanding mapped file, specifically a https://ned14.github.io/afio/classafio__v2__xxx_1_1mapped__file__handle.html which will be the proposed main workhorse object for mapped filesystem memory.

Implementing concurrent data structures on persistent memory is unfortunately even harder than on regular memory. Here's an interesting paper that discusses a persistent B+ Tree from recent FAST conference:
https://www.usenix.org/system/files/conference/fast18/fast18-hwang.pdf
 

I have no access to actual persistent memory, so I've been writing my algorithms to date using standard atomics which I would assume will work as expected on persistent memory by fencing via atomics when writes are sent to the device in relation to other writes, and thus ensuring a sequential consistency of writes, and thus recovery after a sudden power loss.

You cannot rely on atomics alone to ensure failure atomicity. All stores still need to be followed by a cache flush instruction and a fence to ensure ordering. So if you use a CMPXCHG in one thread and flush, a different thread might read the modified value before it reached the persistent domain - this might cause inconsistencies when one thread makes a persistent change based on transient modifications somewhere else.

However what kind of performance damage is there with using std::atomic on persistent memory? For example, Intel CPUs have implicit acquire release semantics in all their loads and stores. I would hope that persistent memory observes those (please definitely do say if it doesn't!).

It doesn't, it's all in the cache.
 

But what about LOCK CMPXCHG which is a read-modify-write operation? Is this a similar speed to RAM? Is it vastly slower? If so, by what order of magnitude? How well does persistent memory cope with cache line contention i.e. multiple threads all fighting over the same CMPXCHG?

I appreciate that the answer to all the above will vary according to the persistent memory technology. So, Optane probably does CMPXCHG much better than NAND for example. Nevertheless, some rough ballpark figures for the relative differences over RAM for various technologies would be extremely useful to me for implementing the optionally concurrent B+ tree implementation which needs to handle sudden power loss correctly.

Not sure how relevant this still is, but the main cost is going to be the cache miss caused by cache flushes. The cost of the cache miss is hardware dependent, but you will want to avoid it if possible.
 

My thanks in advance.

Niall

My pleasure,
Piotr

[Sergei Vinogradov]

Hi Niall,

Piotr already provided detailed response for your question. But I would like to add my thoughts about thread-safe programming for persistent memory.

First of all, CPU works with persistent memory almost the same like with volatile DRAM. I mean data goes through registers, caches, memory controller WPQ and only after that goes to memory (persistent or volatile). So the only difference, as you can see, is a type of memory. Persistent memory survive its state across power loss.

According to above, compare-and-exchange operation works the same (like in volatile case) in case of persistent memory. That means that results of CMPXCHG operation visible in cache but not immediately goes to persistent memory. It will goes to persistent memory due to eviction or explicit cache flush. That's why it is important to distinguish visibility domain and persistent domain. Atomic operations applies to visibility domain. But you need explicit cache flush to move it to persistent domain. As you understand it is not an atomic operation anymore (there are two operations: CMPXCHG + CLFLUSH/CLFLUSHOPT/CLWB). As a result, in case of multi-threaded application there might be a situation when one thread sees result of atomic operation executed by another thread and this results in visibility domain, but not persisted yet. So, it might cause data inconsistency in persistent memory.

Designing multi-threaded application for persistent memory is challenging and you should consider how thread-safe algorithm that applied for visibility domain aligns with persistent domain.

четверг, 22 февраля 2018 г., 0:55:39 UTC+3 пользователь Niall Douglas написал:

[Niall Douglas]

Implementing concurrent data structures on persistent memory is unfortunately even harder than on regular memory. Here's an interesting paper that discusses a persistent B+ Tree from recent FAST conference:
https://www.usenix.org/system/files/conference/fast18/fast18-hwang.pdf

That is indeed an interesting paper.

If kernels were more consistent across various systems, the same algorithm could be written using memory maps of traditional spinning rust. The problem is that msync() is a no-op some, or all, or none of the time depending. So you'd have to implement the write ordering using a write() of a single byte to a node using a special fd opened with O_DIRECT to force out the page after it's been modified. Or just use fsync(). I dunno, if the nodes were 4Kb each, it might just be reasonably fast. On DAX mapped storage, you'd then shrink the node to 256 bytes or so, so the same algorithm could be applied in both cases.

I'll ponder it. Thanks for the link, it was very useful to organise my thoughts.

 

However what kind of performance damage is there with using std::atomic on persistent memory? For example, Intel CPUs have implicit acquire release semantics in all their loads and stores. I would hope that persistent memory observes those (please definitely do say if it doesn't!).

It doesn't, it's all in the cache.

Ah okay. So our existing algorithms for working directly with the kernel page cache thus continue to apply. The only difference is that the very bottom most DMA from kernel page cache to device when the page is being undirtied is no longer performed.

I've got then to ask the stupid question: what gain is there to the C++ userbase to treat pmem any differently to the kernel page cache? If we design our STL2 algorithms to work excellently with mapped file memory i.e. doing things in units of the system page size, use of non-temporal loads and stores when we know that the output will immediately go to storage, use of barriers to fence reordering of reads and writes etc., then surely all that simply works faster and better on pmem with no extra effort on our part?

In other words, what's the value add to the average C++ developer to have specific awareness of pmem built into the C++ standard library's algorithms and containers? i.e. what great pmem-only optimisations can we do behind the scenes with no extra work placed onto the C++ end user?

Niall

[Niall Douglas]

Ah okay. So our existing algorithms for working directly with the kernel page cache thus continue to apply. The only difference is that the very bottom most DMA from kernel page cache to device when the page is being undirtied is no longer performed.

I've got then to ask the stupid question: what gain is there to the C++ userbase to treat pmem any differently to the kernel page cache? If we design our STL2 algorithms to work excellently with mapped file memory i.e. doing things in units of the system page size, use of non-temporal loads and stores when we know that the output will immediately go to storage, use of barriers to fence reordering of reads and writes etc., then surely all that simply works faster and better on pmem with no extra effort on our part?

In other words, what's the value add to the average C++ developer to have specific awareness of pmem built into the C++ standard library's algorithms and containers? i.e. what great pmem-only optimisations can we do behind the scenes with no extra work placed onto the C++ end user?

Let me put this a different way.

Shortly I'm going to have to make the case, to those with the money and power, arguments in favour of establishing of a WG21 Study Group on "Persistent Algorithms and Containers". This study group would turn papers like https://www.usenix.org/system/files/conference/fast18/fast18-hwang.pdf into reference C++ implementations of std::persist::bp_tree<K, T> or whatever for proposed inclusion into the C++ standard.

Right now I would find it difficult to argue in favour of that study group going more than a little out of its way in supporting persistent memory. Those arguing against will say: (i) persistent memory is too rare/expensive/specialist to support now (ii) persistent memory does not offer sufficient advantages in the general purpose use case over kernel paged memory to warrant special treatment (iii) persistent memory should be placed under the (much later) future RDMA standardisation framework, and not given any special treatment right now.

I'd like to know if the persistent memory community feels that this is reasonable opinion and approach to take. If not, please provide arguments with evidence in favour of a different approach, otherwise I'll proceed with pushing pmem into the future RDMA proposal and only giving minimum support in the proposed study group.

Do bear in mind that none of this is expected to enter the standard until C++ 23 at the earliest, and more likely C++ 26. Decisions made in the next year or so will be very hard to undo later due to how ISO standardisation works.

Niall

[Piotr Balcer]

Sorry for the delay, I didn't have time to answer over the weekend.

Algorithms that perform well on block based storage will perform well on persistent memory. LSM is one example of that.
But... the opposite is not true. Continuing the example, LSM implementations such as LevelDB/RocksDB pack a lot of complexity to make sure they fully utilize the device they are running on. Most importantly, they rely on worker threads to flush data to storage.
You cannot even begin to saturate an HDD/SSD with an algorithm that does not have some kind of asynchronous flushing. What this means is that when an algorithm wants to have a semantic where an insert() to a container blocks until the new element is actually stored on medium (or plainly ACID semantics), it wouldn't perform anywhere near satisfactory levels. Additionally, for traditional storage you will want to avoid msync() after writes smaller than a full page (keep in mind that a page can be 2 megabyte or even 1 gigabyte).

Circling back to LSM, it solves the problems of storage devices that achieve high performance on high queue depth levels, and it will also perform well on persistent memory, but, for PMEM, we can use a much simpler algorithm to achieve the same performance, superior ACID semantics, and all of that at a much much lower CPU costs.

We also cannot omit the fact that pmem would allow container elements modification at a much lower granularity, so users can have pointers, modify single 8 byte values etc. Obviously if you need to flush, it's best to write a full cacheline, but it's better than a page. Such elements also can be smaller than a page without severe performance penalty.

Piotr

[Niall Douglas]

On Monday, February 26, 2018 at 8:44:55 AM UTC, Piotr Balcer wrote:

Sorry for the delay, I didn't have time to answer over the weekend.

No problem. It's a busy time for us too, there is a WG21 meeting week after next. I'm also currently arranging for the June meeting where all this stuff will get launched.

 

Algorithms that perform well on block based storage will perform well on persistent memory. LSM is one example of that.
But... the opposite is not true. Continuing the example, LSM implementations such as LevelDB/RocksDB pack a lot of complexity to make sure they fully utilize the device they are running on. Most importantly, they rely on worker threads to flush data to storage.
You cannot even begin to saturate an HDD/SSD with an algorithm that does not have some kind of asynchronous flushing.

In the whole system case, you are correct. However, an application with a single thread doing nothing but O_SYNC i/o can saturate even a fast SSD if the block they write at a time is large enough. Under the bonnet, the kernel turns that into multiple, parallel individual i/o's, and thus saturates the device. For example, I've seen great results with O_SYNC i/o  on ZFS with a fast log device, it'll belt the data onto the fast log device so the write appears fast, and then in the background merge that into the disk array. It's the only filing system I know of which does a decent job of pretending that it's faster than spinning rust if fed enough cache devices.

 

What this means is that when an algorithm wants to have a semantic where an insert() to a container blocks until the new element is actually stored on medium (or plainly ACID semantics), it wouldn't perform anywhere near satisfactory levels. Additionally, for traditional storage you will want to avoid msync() after writes smaller than a full page (keep in mind that a page can be 2 megabyte or even 1 gigabyte).

Circling back to LSM, it solves the problems of storage devices that achieve high performance on high queue depth levels, and it will also perform well on persistent memory, but, for PMEM, we can use a much simpler algorithm to achieve the same performance, superior ACID semantics, and all of that at a much much lower CPU costs.

Ah okay. You're thinking about this in terms of application design. We won't be standardising anything like as complex as LSM. In fact, we won't even be mentioning threads in anything we standardise. We're coming at this from a far lower level. So, for example, a templated B+ tree implementation whose on-disk representation is the same as in-memory, and thus it can be memory mapped. Or even a good old fashioned sparse array, so a one trillion item int array whose storage is allocated on first page fault. We say nothing about flushing or persistence, if the end user wants to persist some region, they call barrier(collection of ranges of memory) with a choice of (i) return immediately but do not reorder writes around the barrier (ii) block until preceding writes reach storage (iii) block until preceding writes and the metadata to retrieve them later reach storage (iv) the preceding two, but execute other code while they are happening in the background, and resume execution once they complete.

Implied in the above is the new Coroutines language support in C++ 20 onward. It lets us avoid needing to mention threads explicitly.

As a special nod to NVRAM/RDMA, we do provide a lightweight, 100% inlined overload of barrier() which injects the CLWB <range>; SFENCE directly into end user code, thus avoiding the indirect function call of going via the virtual functioned normal barrier(). I may yet rename that function into a free function actually, I don't think it stands out enough name-wise, and it's useful in many ways.

We also cannot omit the fact that pmem would allow container elements modification at a much lower granularity, so users can have pointers, modify single 8 byte values etc. Obviously if you need to flush, it's best to write a full cacheline, but it's better than a page. Such elements also can be smaller than a page without severe performance penalty.

I think we all conceptually get this, but it's very far from our personal development experiences to think that power loss safe persistence is something you can get almost for free without O_SYNC and being careful to always write kilobytes at a time. I know I still struggle with this. I find it hard to imagine what simplified code end users might write twenty years from now.

Niall

[Piotr Balcer]

W dniu poniedziałek, 26 lutego 2018 10:37:32 UTC+1 użytkownik Niall Douglas napisał:

On Monday, February 26, 2018 at 8:44:55 AM UTC, Piotr Balcer wrote:

Sorry for the delay, I didn't have time to answer over the weekend.

No problem. It's a busy time for us too, there is a WG21 meeting week after next. I'm also currently arranging for the June meeting where all this stuff will get launched.

 

Algorithms that perform well on block based storage will perform well on persistent memory. LSM is one example of that.
But... the opposite is not true. Continuing the example, LSM implementations such as LevelDB/RocksDB pack a lot of complexity to make sure they fully utilize the device they are running on. Most importantly, they rely on worker threads to flush data to storage.
You cannot even begin to saturate an HDD/SSD with an algorithm that does not have some kind of asynchronous flushing.

In the whole system case, you are correct. However, an application with a single thread doing nothing but O_SYNC i/o can saturate even a fast SSD if the block they write at a time is large enough. Under the bonnet, the kernel turns that into multiple, parallel individual i/o's, and thus saturates the device. For example, I've seen great results with O_SYNC i/o  on ZFS with a fast log device, it'll belt the data onto the fast log device so the write appears fast, and then in the background merge that into the disk array. It's the only filing system I know of which does a decent job of pretending that it's faster than spinning rust if fed enough cache devices.

Yup, and just think about the complexities and the time/memory costs involved in doing what you just described, Andy might know something about it ;) Even with all those things you still need have enough data for a write() to be worthwhile.
 

 

What this means is that when an algorithm wants to have a semantic where an insert() to a container blocks until the new element is actually stored on medium (or plainly ACID semantics), it wouldn't perform anywhere near satisfactory levels. Additionally, for traditional storage you will want to avoid msync() after writes smaller than a full page (keep in mind that a page can be 2 megabyte or even 1 gigabyte).

Circling back to LSM, it solves the problems of storage devices that achieve high performance on high queue depth levels, and it will also perform well on persistent memory, but, for PMEM, we can use a much simpler algorithm to achieve the same performance, superior ACID semantics, and all of that at a much much lower CPU costs.

Ah okay. You're thinking about this in terms of application design. We won't be standardising anything like as complex as LSM. In fact, we won't even be mentioning threads in anything we standardise. We're coming at this from a far lower level. So, for example, a templated B+ tree implementation whose on-disk representation is the same as in-memory, and thus it can be memory mapped. Or even a good old fashioned sparse array, so a one trillion item int array whose storage is allocated on first page fault. We say nothing about flushing or persistence, if the end user wants to persist some region, they call barrier(collection of ranges of memory) with a choice of (i) return immediately but do not reorder writes around the barrier (ii) block until preceding writes reach storage (iii) block until preceding writes and the metadata to retrieve them later reach storage (iv) the preceding two, but execute other code while they are happening in the background, and resume execution once they complete.

Implied in the above is the new Coroutines language support in C++ 20 onward. It lets us avoid needing to mention threads explicitly.

No one expects an LSM, but building blocks for it. What I'm trying to say that an optimal B+ Tree algorithm for a memory mapped, but block based, I/O will significantly differ from an optimal persistent memory algorithm.
Let's take the simplest possible example you mentioned, a sparse array. On traditional storage having one with 8 byte integers and synchronously writing to it would be impractial, and the user would have to get creative and aggregate at least full pages before a write, whereas on pmem you can just write the 8 bytes. That's the key observation - the performance different is so significant it should drive a fundamental shift of how we solve the problems of storage. And if your platform has a capability to flush CPU caches on power failure you can even use atomics - and suddenly you can use the same old lock free algorithms to guarantee both isolation and fail safety.
 

As a special nod to NVRAM/RDMA, we do provide a lightweight, 100% inlined overload of barrier() which injects the CLWB <range>; SFENCE directly into end user code, thus avoiding the indirect function call of going via the virtual functioned normal barrier(). I may yet rename that function into a free function actually, I don't think it stands out enough name-wise, and it's useful in many ways.

We also cannot omit the fact that pmem would allow container elements modification at a much lower granularity, so users can have pointers, modify single 8 byte values etc. Obviously if you need to flush, it's best to write a full cacheline, but it's better than a page. Such elements also can be smaller than a page without severe performance penalty.

I think we all conceptually get this, but it's very far from our personal development experiences to think that power loss safe persistence is something you can get almost for free without O_SYNC and being careful to always write kilobytes at a time. I know I still struggle with this. I find it hard to imagine what simplified code end users might write twenty years from now.

Exactly. It's so different it requires us to rethink our basic assumptions and the lessons about storage we've learned over the years, which is why we need a departure from the status quo w.r.t. storage algorithms.

[Lucas Lersch]

Interesting discussion, and if I may jump in to ask something related:

Let's take the simplest possible example you mentioned, a sparse array. On traditional storage having one with 8 byte integers and synchronously writing to it would be impractial, and the user would have to get creative and aggregate at least full pages before a write, whereas on pmem you can just write the 8 bytes. That's the key observation - the performance different is so significant it should drive a fundamental shift of how we solve the problems of storage

Most storage devices have a sector size of 512 Bytes (also used as an atomic unit of persistency). NVRAM is expected to have it at a cache-granularity (64 Bytes usually), meaning that even writing a single 8 Byte integer would require the whole 64 Bytes to be flushed from cache to the device. If eventually the transfer unit from/to NVRAM increases (128/256/512 Bytes), that becomes very similar to current disk I/O (but with a much better latency). However, there is still the problem of having only 8 Byte atomic-writes persistent guarantees, but hopefully that will be improved in the future by either flushing the whole cache in case of a power failure (as mentioned) or enabling a cache-line as unit of atomic writes.

Finally, block devices allow the user to hide the I/O latency by batching operations and performing as many sequential reads/writes as possible while paying only a single I/O latency cost (one of the advantages of LSMs). Would it still be possible with NVRAM devices or there will be an latency cost for every cache-line written to the device (reads should be fine because of prefetching)?

Best regards,

Lucas

--
You received this message because you are subscribed to the Google Groups "pmem" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pmem+unsubscribe@googlegroups.com.
To post to this group, send email to pm...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/9036823a-bb41-4b65-83a8-11b241a4073b%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Lucas Lersch

[Piotr Balcer]

Hi Lucas,

W dniu poniedziałek, 26 lutego 2018 13:39:17 UTC+1 użytkownik Lucas Lersch napisał:

Interesting discussion, and if I may jump in to ask something related:

Let's take the simplest possible example you mentioned, a sparse array. On traditional storage having one with 8 byte integers and synchronously writing to it would be impractial, and the user would have to get creative and aggregate at least full pages before a write, whereas on pmem you can just write the 8 bytes. That's the key observation - the performance different is so significant it should drive a fundamental shift of how we solve the problems of storage

Most storage devices have a sector size of 512 Bytes (also used as an atomic unit of persistency). NVRAM is expected to have it at a cache-granularity (64 Bytes usually), meaning that even writing a single 8 Byte integer would require the whole 64 Bytes to be flushed from cache to the device. If eventually the transfer unit from/to NVRAM increases (128/256/512 Bytes), that becomes very similar to current disk I/O (but with a much better latency). However, there is still the problem of having only 8 Byte atomic-writes persistent guarantees, but hopefully that will be improved in the future by either flushing the whole cache in case of a power failure (as mentioned) or enabling a cache-line as unit of atomic writes.

That's a very accurate observation, this is indeed a similar situation to block I/O.
The transfer unit you mentioned is obviously hardware dependent and defined in ACPI, see this kernel patch for relevant info:
https://patchwork.kernel.org/patch/9932903/
 

Finally, block devices allow the user to hide the I/O latency by batching operations and performing as many sequential reads/writes as possible while paying only a single I/O latency cost (one of the advantages of LSMs). Would it still be possible with NVRAM devices or there will be an latency cost for every cache-line written to the device (reads should be fine because of prefetching)?

This works like for regular DRAM, so if you write more one or more cache lines you benefit from write combining and you will achieve higher throughput. The same way, if you use non temporal stores to bypass the cache you won't have to manually flush the CPU caches to reach persistence and the copying will be faster.

Also, notice that if you write full aligned cache lines using non-temporal instructions you can entirely avoid the cache miss on fetching of old cache line content on write.

(If you are receiving this for the second time, sorry, I've added a link to an ubuntu bug tracker instead of the original kernel patch.)
 

[Marcin Ślusarz]

2018-02-26 15:00 GMT+01:00 Piotr Balcer <ppbb...@gmail.com>:
> This works like for regular DRAM, so if you write more one or more cache
> lines you benefit from write combining and you will achieve higher
> throughput. The same way, if you use non temporal stores to bypass the cache
> you won't have to manually flush the CPU caches to reach persistence and the
> copying will be faster.

FTR, transparent write combining works only for non temporal stores. It changes
the moment modifications are visible to other threads, so it can't be enabled
by default.

Marcin

[Lucas Lersch]

Thanks for the answers Piotr and Marcin.

Taking the mentioned reasons into consideration for the current state of NVRAM, non-temporal stores seem to make a good case for log-structured data structures (in contrast to update-in-place), as every write to NVRAM will not imply a cache-miss or require manual flushing, as well as it would also enable transparent write combining. Optimizing the writes in a device with asymmetric latencies (writes being slower than reads) could bring some nice benefits. Correct me if I'm wrong.

Best regards,

Lucas

--
You received this message because you are subscribed to the Google Groups "pmem" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pmem+unsubscribe@googlegroups.com.
To post to this group, send email to pm...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/CA%2BGA0_ti9OMYhQfjb0_TGuDCfy8iX-sossCpzgN%2BjF%3DyCEYQJA%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Lucas Lersch

[Piotr Balcer]

Yes, but keep in mind that the degree of this asymmetry is platform dependent. You could theoretically have NVDIMM-N (DRAM + Flash) on a platform with CPU cache flush on failure.
But... some might argue that a log-structured approach is also valid for DRAM [1] ! ;) And as you rightly notice, there are also unquestionable benefits there for NVM [2], chief among them the ability to reduce the number of barriers needed to maintain correctness.

[1] - https://www.usenix.org/system/files/conference/fast14/fast14-paper_rumble.pdf
[2] - https://www.usenix.org/system/files/conference/atc17/atc17-hu.pdf

W dniu poniedziałek, 26 lutego 2018 17:11:35 UTC+1 użytkownik Lucas Lersch napisał:

Thanks for the answers Piotr and Marcin.

Taking the mentioned reasons into consideration for the current state of NVRAM, non-temporal stores seem to make a good case for log-structured data structures (in contrast to update-in-place), as every write to NVRAM will not imply a cache-miss or require manual flushing, as well as it would also enable transparent write combining. Optimizing the writes in a device with asymmetric latencies (writes being slower than reads) could bring some nice benefits. Correct me if I'm wrong.

Best regards,

Lucas

On Mon, Feb 26, 2018 at 3:17 PM, Marcin Ślusarz <marcin....@gmail.com> wrote:

2018-02-26 15:00 GMT+01:00 Piotr Balcer <ppbb...@gmail.com>:
> This works like for regular DRAM, so if you write more one or more cache
> lines you benefit from write combining and you will achieve higher
> throughput. The same way, if you use non temporal stores to bypass the cache
> you won't have to manually flush the CPU caches to reach persistence and the
> copying will be faster.
FTR, transparent write combining works only for non temporal stores. It changes
the moment modifications are visible to other threads, so it can't be enabled
by default.

Marcin

--
You received this message because you are subscribed to the Google Groups "pmem" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pmem+uns...@googlegroups.com.

To post to this group, send email to pm...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/CA%2BGA0_ti9OMYhQfjb0_TGuDCfy8iX-sossCpzgN%2BjF%3DyCEYQJA%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Lucas Lersch

[Niall Douglas]

No one expects an LSM, but building blocks for it. What I'm trying to say that an optimal B+ Tree algorithm for a memory mapped, but block based, I/O will significantly differ from an optimal persistent memory algorithm.
Let's take the simplest possible example you mentioned, a sparse array. On traditional storage having one with 8 byte integers and synchronously writing to it would be impractial, and the user would have to get creative and aggregate at least full pages before a write, whereas on pmem you can just write the 8 bytes. That's the key observation - the performance different is so significant it should drive a fundamental shift of how we solve the problems of storage. And if your platform has a capability to flush CPU caches on power failure you can even use atomics - and suddenly you can use the same old lock free algorithms to guarantee both isolation and fail safety.

The OS implements a lot of that stuff for you already though. For example, almost every kernel will enforce a maximum age for a dirty page before it gets persisted. Knowing this, if one always stores new data into atomic appended pages, and uses hole punching to deallocate spent pages, one can implement "late durability" i.e. time ordered. For some applications and filing systems this can really fly, however the implicit copy-on-write can be punishing for other applications. And some filing systems e.g. ZFS are truly horrid when more than one thread is atomic appending less than the stripe size concurrently - as in, three or four atomic appends per second. That bad.

Exactly. It's so different it requires us to rethink our basic assumptions and the lessons about storage we've learned over the years, which is why we need a departure from the status quo w.r.t. storage algorithms.

The WG21 leadership have been made aware of my funding request. We'll see how things land.

We've actually got a more fundamental problem which through AFIO solving has got WG21 all excited. AFIO needed a fixed latency mechanism of handling failure which is not a C++ exception throw, so I came up with https://ned14.github.io/outcome/ which has been accepted to enter the Boost C++ Libraries. Now WG21 wants to fix non-deterministic C++ exception throws once and for all. So I've sorta opened a can of worms which will proceed in parallel to the persistence effort. They are, however, tightly intertwined because I need predictably sub-100ns failure handling.

Niall

[Niall Douglas]

Most storage devices have a sector size of 512 Bytes (also used as an atomic unit of persistency).

That's a highly problematic assumption.

Empirical testing by me with AFIO on a wide variety of operating systems and devices shows that many devices use a 4Kb atomic unit internally, some even 8Kb. Modifying anything less than that causes the device to internally do a RMW cycle, which is inefficient.

Of the three major kernels, NT, Linux and FreeBSD, the most recent versions of each finally properly implement POSIX read/write concurrency and atomicity guarantees if O_DIRECT is on, and in some cases if it is off. I had to submit some bug reports on that a few years ago in fact, NT had become broken. In fairness Microsoft fixed it real quick and recent Windows 10 kernels are highly conforming to POSIX semantics now.

 

NVRAM is expected to have it at a cache-granularity (64 Bytes usually), meaning that even writing a single 8 Byte integer would require the whole 64 Bytes to be flushed from cache to the device. If eventually the transfer unit from/to NVRAM increases (128/256/512 Bytes), that becomes very similar to current disk I/O (but with a much better latency). However, there is still the problem of having only 8 Byte atomic-writes persistent guarantees, but hopefully that will be improved in the future by either flushing the whole cache in case of a power failure (as mentioned) or enabling a cache-line as unit of atomic writes.

Finally, block devices allow the user to hide the I/O latency by batching operations and performing as many sequential reads/writes as possible while paying only a single I/O latency cost (one of the advantages of LSMs). Would it still be possible with NVRAM devices or there will be an latency cost for every cache-line written to the device (reads should be fine because of prefetching)?

From what I now understand, the only semantic difference between kernel page caching and the CPU line caching is that the former is implemented in software. Each caching layer simply increases the block size, otherwise they are remarkably similar in terms of operation and tradeoffs. As you mention though, the kernel will place a maximum age before writing out a dirty page, whereas I am not aware that the CPU will write dirty lines based on age.

Niall

[Lucas Lersch]

Empirical testing by me with AFIO on a wide variety of operating systems and devices shows that many devices use a 4Kb atomic unit internally, some even 8Kb. Modifying anything less than that causes the device to internally do a RMW cycle, which is inefficient.

Of the three major kernels, NT, Linux and FreeBSD, the most recent versions of each finally properly implement POSIX read/write concurrency and atomicity guarantees if O_DIRECT is on, and in some cases if it is off. I had to submit some bug reports on that a few years ago in fact, NT had become broken. In fairness Microsoft fixed it real quick and recent Windows 10 kernels are highly conforming to POSIX semantics now.

I would be interested if you could point to any report or document that elaborate on this :)

From what I now understand, the only semantic difference between kernel page caching and the CPU line caching is that the former is implemented in software

Correct, but that is a big difference. The kernel has full control of when to write pages from the page cache to the device. This control is critical for applications that must provide a high degree of consistency (databases). With the CPU caches, this control is just not possible for now, we cannot "pin" a cache-line to the cache. 

I am not aware that the CPU will write dirty lines based on age.

I think the eviction policies varies for different architectures and I am not aware of any clear documentation about it. For simplicity I like to think of it as a LRU per associativity-set. That also imposes a restriction as we cannot experiment with different policies tailored for different workloads/trade-offs (as could be possible with software caching).

Best regards,

Lucas

--

You received this message because you are subscribed to the Google Groups "pmem" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pmem+unsubscribe@googlegroups.com.
To post to this group, send email to pm...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/7997dd0f-6299-4fb5-8d78-36a796c7e1bc%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Lucas Lersch

[Niall Douglas]

On Tuesday, February 27, 2018 at 9:50:40 AM UTC, Lucas Lersch wrote:

Empirical testing by me with AFIO on a wide variety of operating systems and devices shows that many devices use a 4Kb atomic unit internally, some even 8Kb. Modifying anything less than that causes the device to internally do a RMW cycle, which is inefficient.

Of the three major kernels, NT, Linux and FreeBSD, the most recent versions of each finally properly implement POSIX read/write concurrency and atomicity guarantees if O_DIRECT is on, and in some cases if it is off. I had to submit some bug reports on that a few years ago in fact, NT had become broken. In fairness Microsoft fixed it real quick and recent Windows 10 kernels are highly conforming to POSIX semantics now.

I would be interested if you could point to any report or document that elaborate on this :)

Best I can do is the public database of empirical results at https://github.com/ned14/afio/blob/master/programs/fs-probe/fs_probe_results.yaml. I have lots more for which I did not receive permission to redistribute.

Perhaps your surprise stems from my choices of storage device? Almost all of them are consumer devices, most of them cheap. All my spinning rust drives have 4Kb native sectors for example. My cheap as chips SSDs are particularly prone to throwing whatever flash is cheapest in there, if that works in 8Kb internal sectors and causes a RMW for every 4Kb written, then so be it as far as they're concerned. They don't care about longevity like enterprise SSDs.

From what I now understand, the only semantic difference between kernel page caching and the CPU line caching is that the former is implemented in software

Correct, but that is a big difference. The kernel has full control of when to write pages from the page cache to the device.

... to the device's caches, yes. It can ask the device to flush its caches, but it may be ignored. In fact, for several consumer SSDs, it is ignored. Recent MacBook Pro SSDs completely ignore flushing requests.

 

This control is critical for applications that must provide a high degree of consistency (databases). With the CPU caches, this control is just not possible for now, we cannot "pin" a cache-line to the cache. 

We can however "fsync" a cache line, even going right back to old CPUs. I agree it's unhelpful that we cannot pin cache lines for a given process id. If we could, SPECTRE would go away.

 

I am not aware that the CPU will write dirty lines based on age.

I think the eviction policies varies for different architectures and I am not aware of any clear documentation about it. For simplicity I like to think of it as a LRU per associativity-set. That also imposes a restriction as we cannot experiment with different policies tailored for different workloads/trade-offs (as could be possible with software caching).

Indeed the C++ standard must work on a very wide variety of architectures. Thankfully, unlike the C standard, we only support 8-bit CPUs!

Niall

[technovelist]

C++ only supports 8-bit CPUs? I hope you mean 8-bit-byte CPUs!