If I were to make a concurrent map data structure whose operations are not linearizable and then put it on a library and give it to my users, any user of that library would come back to me and say that my library has a bug.
They may not be able to tell me exactly what it is, but they'll understand that there is a bug in it.
However, if I take the same concurrent map data structure, and put in an application and call that application a "Key-Value store" or a "Database" (DBMS) and give it to the typical database users, it seems they may certainly use it for a several decades without ever complaining that this "Database" is not linearizable (or serializable as the DB folks call it).
If this sounds far-fetched, then just go and read this post: http://jepsen.io/analyses/postgresql-12.3
It seems that the Postgresql users really didn't care that postgresql isn't serializable when told to be so and in fact, isn't even read committed by default, which should be the default. And a similar thing happened to MongDB last month, so it's not something specific to Postgresql.
I find this interesting because it's an extreme case of managing expectations: When you take a library of concurrent data structures, you expect a certain kind of consistency, namely, you expect linearizability (just go and read discussion on the Java concurrency mailing list if you don't believe me).
However, if you take a DBMS like Postgresql, you no longer expect linearizability to be the default behavior. In fact, you expect read committed as the default behavior, which turns out Postgresql doesn't even give read-committed and instead gives snapshot isolation.
A user of a library of concurrent data structures would call read committed a bug. She would also call snapshot isolation a bug, and pretty much everything that is not linearizable would be a bug to her.
The reason it would be a bug, is because it is very hard to reason about anything that is not linearizable. In the post by Jepsen you can even see that there is no exact definition of read committed, so I guess that's one of the reasons why nobody complained about it before.
I can easily imagine discussions of the type:
DBMS User: This behavior is weird!
DBMS Developer: No, it's not weird, it's "read committed", you just have to go and learn about what it means!
DBMS User: The definition of "read committed" is so fluffly that it can mean any weird thing... I can't even understand if the weird thing I'm observing is "read committed" or not.
DBMS Developer: See!?! I was right, this is "read committed"!
DBMS User: Ok, I'll keep using your DBMS because all the other DBMS work the same way.
I could have understood if it was a distributed database, because the cost of a serializable transaction over a distributed database is likely proportional to the latency of the furthest node in the database, while for read-committed it may be lower (who knows?). But the scenario that Jepsen describes isn't even about distributed databases. It's a bug found running on a single-node database. There's no "distributed-databases-are-hard" excuse here (which they are, it's true).
It makes me wonder how did the DBMS folks got their users so well trained that they don't complain about consistency bugs in the DBMS?!?
On one side, I'm super envious because I secretly wish I could be as dismissive to my users as the DBMS folks are to theirs, lol.
But seriously, how could this have happened for so long?!?
I see two possible reasons:
1st, the users don't really care about consistency. They're running businesses. As long as the DBMS is fast enough and has the features that they need, they'll continue to spew out cash for it. Correct consistency is not an issue for the 99% use-cases of databases, as long as the data doesn't get corrupted or lost, everything's fine.
2nd, it's always been like that. Everybody accepts it works like that, and if you want something better, you have to go for a niche DBMS (not that easy to find). Read-committed, snapshot isolation and other strange names as such, are just the "status quo" and nobody wants to change the status quo.
3rd, the DBMS folks hide behind the wall of complexity that is the DBMS. It's a common scenario in IT. They would say something like "Ooooohhhhh this DBMS is too complicated for mere mortals to question! It takes many years of work and millions of lines of code! Here be dragons! Oooohhhh".
If you think of other reasons behind this, I would like to hear about them in the comments section.
Anyways, with the advent of Persistent Memory (PM) and Software Transactional Memory for PM, this game is changing.
One example close to my heart is RedoDB.
RedoDB is a "key-value store" but it supports linearizable transactions over any C++ data type (needs to be type-annotated though). Not only that, but these transactions are wait-free.
That's right, you heard it well: RedoDB provides durable linearizable/serializable wait-free dynamic transactions.
No only does it do that, but is does it slightly faster than RocksDB.
The downside? Consumes vast amounts of memory, though it won't be any worse than most implementations of Multi-Version-Concurrency-Control. At least in RedoDB there is a bound on memory usage.
Anyways, our goal was to show that wait-free DBMS are feasible and can be made efficiently. We weren't aiming for a commercial product.
Ohh and did I say that this DB is about 3k lines of code, as opposed to the several hundred thousands LOC for other DBMS?
You can checkout the paper for RedoDB here: https://dl.acm.org/doi/abs/10.1145/3342195.3387515
and the source code here: https://github.com/pramalhe/RedoDB
Showing posts with label wait-free. Show all posts
Showing posts with label wait-free. Show all posts
Friday, June 12, 2020
Sunday, May 17, 2020
Dealing with bugs in Concurrency and Durability
Everyone knows that Concurrency is hard, in fact, it's NP-hard: the total number of interleavings typically grow exponentially with the number of lines of code (LOC) in a program. Determining if any of these interleavings causes incorrect behavior, becomes problematic for anything but very small programs.
This never prevented anyone from writing large multi-threaded programs, and the usual trick is to use locks. A code block surround by a lock does not have interleavings with other code blocks for the same lock, and the problem becomes "tractable" again.
Unfortunately, we can't use this trick for lock-free and wait-free code. Lock-free algorithms are typically done with atomic instructions that can interleave with each other.
Verifying correctness of these algorithms is a difficult problem.
There are static verification tools like SPIN, JSF, TLA+ and others, but such tools only work for a small number of threads (no more than 6 threads) and small-size programs (less than 100 LOC). As if this wasn't bad enough, these tools enforce the user to write the program in a particular language, apart from JSF, which is almost Java. The program will have to be re-written later in the target language that is meant for, and during this "translation" errors can be introduced.
Now, don't get me wrong, software has bugs. It's just part of life as a software developer to deal with them and try to minimize them.
Entire industry trends like Test Driven Development (TDD) and Test Automation revolve around the concept of testing to reduce the amount of bugs.
In other words, there's this idea that the more time you invest in tests, the more quality the final program will have. IMO this is true, but obviously it's not a linear effort: beyond a certain number of tests, the number of new bugs you'll detect will be small compared to the effort of maintaining those tests.
Concurrency bugs can, and should, also be approached in this manner, but this is far from sufficient.
Moreover, testing a concurrent program requires a different set of techniques and mindset than testing a sequential program: instead of exercising input-output responses, we should test program invariants; instead of mocking components, we should stress the code by increasing the number of threads or changing timings to exercise different interleavings and code paths.
This is where run-time verification can provide a good help. Tools like valgrind and Address Sanitizer become a need-to-have if you're writing C/C++ multi-threaded applications and there is a good deal of research being done on this field, so I'm sure that more capabilities and more efficient tools will show up in the future. However...
Suppose I have a new lock-free algorithm and I implement it. Then I bother to write some tests for it (which most researchers won't do) and then run it with address sanitizer and whatever other run-time tools I can get my hands on. None of my tests or run-time tools encounter any error. Now what? Is my algorithm ready for publication? How will the peer reviewers know that it is correct? How will I convince them of that?
And here lies the big problem in researching concurrent algorithms that people don't usually talk about: "How do I know if the lock-free algorithm in this paper is correct?"
As I said before, it's ok to have bugs in your code, all software has bugs, and software developers are used to this inevitability.
What is not ok is to have bugs in your algorithm. It's very hard to prove the correctness of a lock-free algorithm. Although it's usually simple to verify that a bug exists, once someone tells you the sequence of steps to reproduce that bug.
This can lead to surreal scenarios that typically look like this:
Me: Read the latest paper on a novel lock-free algorithm. Spend weeks thinking about it. Come up with a scenario where the algorithm doesn't work. Send an email to authors describing the scenario.
Authors: Spend a week thinking if the scenario is actually a bug and how to fix it, propose a slight variation of the algorithm.
Me: Spend another week thinking about it, come up with a difference scenario where there is a race condition.
Authors: Spend another week thinking about it and propose a modified algorithm.
Me: Spend another week thinking about this different algorithm. Get to the conclusion that the algorithm is no longer lock-free. Send a new email explaning why.
Authors: Spend another week thinking about it and propose yet another version of the algorithm.
Me: Spend another week thinking about it, only to reach the conclusion that this new algorithm is not even linearizable.
Authors: We weren't aiming for linearizability anyways...
Me: Lose all faith on the work done in the field of concurrent algorithms, and lose faith in mankind in general... at least for a couple of weeks, then I read another paper that looks interesting and the cycle restarts.
This can sound bad but it's a description of when things turn out good. Other times I send the email and the authors just ignore me, or they answer something that shows that they don't even understand there is a bug, or there is no bug and the whole things was a result of me missing some vital detail in the algorithm.
Ultimately, either I shame the authors by pointing out their mistakes or I shame myself for being too dumb to understand their paper. Never a good turnout and it's not a good way of "making friends". Unfortunately I can't help myself, I'm in it because I want to learn, and you learn the most when you're willing to make a fool of yourself ;)
This is not about incompetence, this is about the inherent difficulty in writing lock-free algorithms. The authors are not sure that their algorithms are correct, the reviewers are not sure that the algorithms are correct and the readers of the papers are not sure that the algorithms are correct. And don't get me started on the actual "implementations" of these algorithms.
It's a mess, and it creates a lot of distrust in the field, specially during peer revieweing.
Papers end up being accepted only if there is an expert reviewer that really knows about this stuff and decides to spend the several weeks of his personal time it takes to fully understand that algorithm and then comes back to the other reviewers and manages to convince them that this stuff is correct.
Most of the times, academic papers gets accepted just because they're not obviously wrong. But the problem is that may be simply because the algorithm is so complex that no one is willing to "dig into it". I've seen examples of papers accepted into major conferences, where the basic algorithm was wrong (and there is not obvious way of fixing it) and then the authors will continue convinced that approach is valid and correct and write follow up papers that build on that algorithm and those papers continue to be accepted in major conferences, when it's all crap.
Luckily, this is rare. Most of the bugs I've seen in lock-free algorithms are things that can be fixed without a major re-design of the algorithm.
There is also the effect that if the algorithm is too simple (there aren't many of those, but still) then the reviewers may think that the work doesn't have enough value. But if the algorithm is too complex, then they wouldn't be able to understand if it is correct or not.
This kind of creates the incentive for papers to have incremental algorithms based on prior published work, or to have several simple algorithms as opposed to a single complex one.
I've noticed that when it comes to durability (persistence), the problem is similar.
Durable algorithms are not NP-Hard, the failure can occur at a single point in the code, which means that the complexity is linearly proportional to the LOCs, as opposed to concurrency algorithms where the complexity grows exponentially with the LOCs in the algorithm.
However, the pattern of me reading papers on durable algorithms and then sending emails and then the authors fixing but not really fixing is pretty much the same.
It's still a hard problem, particularly now with Optane DC Persistent Memory that has a special set of rules for data to be correctly persisted.
On Persistent Memory it is very easy to forget a flush or a persistent fence. This means the implementation is incorrect, however, in practice it may have no issue, because the probability of having a crash exactly in the place where the fence is missing is very low.
On the other hand, if there are fences missing all over the place or if there is something being used that simply doesn't make sense, then no matter where the program crashes, the data will end up corrupted. So there are different shades of grey here.
Again here the problem repeats itself when it comes to getting a paper accepted at a conference: unless one of the reviewers really knows its stuff and is willing to invest the time it takes to deep dive on the algorithm presented on the paper, getting a "correct" durable algorithm accepted is just a game of luck. The best that can be done is to make a convincing proof or at least explain some invariants.
I believe that as time goes by, there will be better tools that will help writing and verifying correct durable algorithms. The thing is, by the time that happens (years from now), all or most of the interesting durable algorithms will be published by then, so it kind of defeats the purpose. Moreover, for the complicated stuff we can always use transactional durable techniques (undo-log, redo-log, copy-on-write, shadow-data) or a universal construction, like the one we presented at EuroSys2020 : link here.
For concurrency it's really black and white: you miss a fence, you're algorithm is wrong and you WILL see a bug happen eventually.
I don't see any real solution for concurrent algorithms coming anytime soon. And that's a shame because as long as things remain the way they are, it will be very hard for the good (correct) algorithms to be distinguished from the bad (incorrect) ones. It becomes a kind of "reputation game" where papers from people who have made correct algorithms in the past, will likely have correct algorithms later as well, but this is not really reliable seen as we're all humans we're bound to make mistakes at some point. For now, all we can do is test our implementations of these algorithms as extensively as possible so as to minimize the chances of bugs, but it will never be 100% certain.
This discussion may seem a bit boring: software will always have bugs, so what's the problem with having buggy algorithms?
My argument is that it's a big deal, actually, it's a very BIG deal!I've seen many papers that build on previous papers and then I go look at the previous work on which they're based, and those are incorrect. We need solid foundations on which to build, to be able to progress further and faster.
If we don't give the proper value to the correct algorithms and point out the incorrect ones, then we're creating the wrong incentive. Researchers will not bother to spend the time testing or validating their algorithms. This creates the climate of suspicion that we're in today.
Ultimately, designing lock-free algorithms will never be "easy", but designing lock-free and persistent data structures is easy when you use universal constructions or a lock-free software transactional memory. This means all these are problems are an issue only for the researchers of concurrent algorithms, but not really a problem for people that need a peristent or lock-free data structure.
This never prevented anyone from writing large multi-threaded programs, and the usual trick is to use locks. A code block surround by a lock does not have interleavings with other code blocks for the same lock, and the problem becomes "tractable" again.
Unfortunately, we can't use this trick for lock-free and wait-free code. Lock-free algorithms are typically done with atomic instructions that can interleave with each other.
Verifying correctness of these algorithms is a difficult problem.
There are static verification tools like SPIN, JSF, TLA+ and others, but such tools only work for a small number of threads (no more than 6 threads) and small-size programs (less than 100 LOC). As if this wasn't bad enough, these tools enforce the user to write the program in a particular language, apart from JSF, which is almost Java. The program will have to be re-written later in the target language that is meant for, and during this "translation" errors can be introduced.
Now, don't get me wrong, software has bugs. It's just part of life as a software developer to deal with them and try to minimize them.
Entire industry trends like Test Driven Development (TDD) and Test Automation revolve around the concept of testing to reduce the amount of bugs.
In other words, there's this idea that the more time you invest in tests, the more quality the final program will have. IMO this is true, but obviously it's not a linear effort: beyond a certain number of tests, the number of new bugs you'll detect will be small compared to the effort of maintaining those tests.
Concurrency bugs can, and should, also be approached in this manner, but this is far from sufficient.
Moreover, testing a concurrent program requires a different set of techniques and mindset than testing a sequential program: instead of exercising input-output responses, we should test program invariants; instead of mocking components, we should stress the code by increasing the number of threads or changing timings to exercise different interleavings and code paths.
This is where run-time verification can provide a good help. Tools like valgrind and Address Sanitizer become a need-to-have if you're writing C/C++ multi-threaded applications and there is a good deal of research being done on this field, so I'm sure that more capabilities and more efficient tools will show up in the future. However...
Suppose I have a new lock-free algorithm and I implement it. Then I bother to write some tests for it (which most researchers won't do) and then run it with address sanitizer and whatever other run-time tools I can get my hands on. None of my tests or run-time tools encounter any error. Now what? Is my algorithm ready for publication? How will the peer reviewers know that it is correct? How will I convince them of that?
And here lies the big problem in researching concurrent algorithms that people don't usually talk about: "How do I know if the lock-free algorithm in this paper is correct?"
As I said before, it's ok to have bugs in your code, all software has bugs, and software developers are used to this inevitability.
What is not ok is to have bugs in your algorithm. It's very hard to prove the correctness of a lock-free algorithm. Although it's usually simple to verify that a bug exists, once someone tells you the sequence of steps to reproduce that bug.
This can lead to surreal scenarios that typically look like this:
Me: Read the latest paper on a novel lock-free algorithm. Spend weeks thinking about it. Come up with a scenario where the algorithm doesn't work. Send an email to authors describing the scenario.
Authors: Spend a week thinking if the scenario is actually a bug and how to fix it, propose a slight variation of the algorithm.
Me: Spend another week thinking about it, come up with a difference scenario where there is a race condition.
Authors: Spend another week thinking about it and propose a modified algorithm.
Me: Spend another week thinking about this different algorithm. Get to the conclusion that the algorithm is no longer lock-free. Send a new email explaning why.
Authors: Spend another week thinking about it and propose yet another version of the algorithm.
Me: Spend another week thinking about it, only to reach the conclusion that this new algorithm is not even linearizable.
Authors: We weren't aiming for linearizability anyways...
Me: Lose all faith on the work done in the field of concurrent algorithms, and lose faith in mankind in general... at least for a couple of weeks, then I read another paper that looks interesting and the cycle restarts.
This can sound bad but it's a description of when things turn out good. Other times I send the email and the authors just ignore me, or they answer something that shows that they don't even understand there is a bug, or there is no bug and the whole things was a result of me missing some vital detail in the algorithm.
Ultimately, either I shame the authors by pointing out their mistakes or I shame myself for being too dumb to understand their paper. Never a good turnout and it's not a good way of "making friends". Unfortunately I can't help myself, I'm in it because I want to learn, and you learn the most when you're willing to make a fool of yourself ;)
This is not about incompetence, this is about the inherent difficulty in writing lock-free algorithms. The authors are not sure that their algorithms are correct, the reviewers are not sure that the algorithms are correct and the readers of the papers are not sure that the algorithms are correct. And don't get me started on the actual "implementations" of these algorithms.
It's a mess, and it creates a lot of distrust in the field, specially during peer revieweing.
Papers end up being accepted only if there is an expert reviewer that really knows about this stuff and decides to spend the several weeks of his personal time it takes to fully understand that algorithm and then comes back to the other reviewers and manages to convince them that this stuff is correct.
Most of the times, academic papers gets accepted just because they're not obviously wrong. But the problem is that may be simply because the algorithm is so complex that no one is willing to "dig into it". I've seen examples of papers accepted into major conferences, where the basic algorithm was wrong (and there is not obvious way of fixing it) and then the authors will continue convinced that approach is valid and correct and write follow up papers that build on that algorithm and those papers continue to be accepted in major conferences, when it's all crap.
Luckily, this is rare. Most of the bugs I've seen in lock-free algorithms are things that can be fixed without a major re-design of the algorithm.
There is also the effect that if the algorithm is too simple (there aren't many of those, but still) then the reviewers may think that the work doesn't have enough value. But if the algorithm is too complex, then they wouldn't be able to understand if it is correct or not.
This kind of creates the incentive for papers to have incremental algorithms based on prior published work, or to have several simple algorithms as opposed to a single complex one.
I've noticed that when it comes to durability (persistence), the problem is similar.
Durable algorithms are not NP-Hard, the failure can occur at a single point in the code, which means that the complexity is linearly proportional to the LOCs, as opposed to concurrency algorithms where the complexity grows exponentially with the LOCs in the algorithm.
However, the pattern of me reading papers on durable algorithms and then sending emails and then the authors fixing but not really fixing is pretty much the same.
It's still a hard problem, particularly now with Optane DC Persistent Memory that has a special set of rules for data to be correctly persisted.
On Persistent Memory it is very easy to forget a flush or a persistent fence. This means the implementation is incorrect, however, in practice it may have no issue, because the probability of having a crash exactly in the place where the fence is missing is very low.
On the other hand, if there are fences missing all over the place or if there is something being used that simply doesn't make sense, then no matter where the program crashes, the data will end up corrupted. So there are different shades of grey here.
Again here the problem repeats itself when it comes to getting a paper accepted at a conference: unless one of the reviewers really knows its stuff and is willing to invest the time it takes to deep dive on the algorithm presented on the paper, getting a "correct" durable algorithm accepted is just a game of luck. The best that can be done is to make a convincing proof or at least explain some invariants.
I believe that as time goes by, there will be better tools that will help writing and verifying correct durable algorithms. The thing is, by the time that happens (years from now), all or most of the interesting durable algorithms will be published by then, so it kind of defeats the purpose. Moreover, for the complicated stuff we can always use transactional durable techniques (undo-log, redo-log, copy-on-write, shadow-data) or a universal construction, like the one we presented at EuroSys2020 : link here.
For concurrency it's really black and white: you miss a fence, you're algorithm is wrong and you WILL see a bug happen eventually.
I don't see any real solution for concurrent algorithms coming anytime soon. And that's a shame because as long as things remain the way they are, it will be very hard for the good (correct) algorithms to be distinguished from the bad (incorrect) ones. It becomes a kind of "reputation game" where papers from people who have made correct algorithms in the past, will likely have correct algorithms later as well, but this is not really reliable seen as we're all humans we're bound to make mistakes at some point. For now, all we can do is test our implementations of these algorithms as extensively as possible so as to minimize the chances of bugs, but it will never be 100% certain.
This discussion may seem a bit boring: software will always have bugs, so what's the problem with having buggy algorithms?
My argument is that it's a big deal, actually, it's a very BIG deal!I've seen many papers that build on previous papers and then I go look at the previous work on which they're based, and those are incorrect. We need solid foundations on which to build, to be able to progress further and faster.
If we don't give the proper value to the correct algorithms and point out the incorrect ones, then we're creating the wrong incentive. Researchers will not bother to spend the time testing or validating their algorithms. This creates the climate of suspicion that we're in today.
Ultimately, designing lock-free algorithms will never be "easy", but designing lock-free and persistent data structures is easy when you use universal constructions or a lock-free software transactional memory. This means all these are problems are an issue only for the researchers of concurrent algorithms, but not really a problem for people that need a peristent or lock-free data structure.
Wednesday, November 6, 2019
CX - Wait-Free Universal Construction
After many years, we've decided to make public the source code for the CX Universal Construction and explain what it is. Source code can be obtained here: https://github.com/pramalhe/CX
and paper here: https://arxiv.org/abs/1911.01676
CX is the first wait-free Universal Construction that can actually be used in practice.
It can take lambdas for its operations, it has integrated (wait-free) memory reclamation, it was extensively tested and it doesn't leak.
CX allows you to take a sequential data structure or object (single-threaded code) and make a wait-free concurrent implementation of the same object by simply encapsulating the methods in calls to updateTx() or readTx(). The resulting data structures have linearizable operations.
Transforming a sequential data structure with CX is not trivial, but it is simple enough that a developer fresh out of college can do it. There are a few rules specific to wait-free UCs that need to be followed (no I/O, no exceptions, no side effects, deterministic code only) but these are easy enough to adhere to.
Unlike handmade wait-free and lock-free data structures, you can have any kind of type in your container (there are limitations on the return values though). All lock-free data structures I've seen so far were meant for integers only, or something equal or smaller than 64bits. Moreover, with CX it's easy to modify the data structure later and add more functionality.
Unlike STMs, CX does not need to have interposing and therefore, we can use CX to wrap data structures in libraries to which we don't have access to the source code. For example, you can use CX to wrap STL containers (we have!). Here is an example on how to make a wait-free std::set
https://github.com/pramalhe/CX/blob/master/examples/WFStdSet.hpp
or even easier, just create the instance and do the operations on the fly:
https://github.com/pramalhe/CX/blob/master/examples/example1.cpp
All you need is a copy constructor for the underlying data structure you want to protect. As long as your sequential data structure has a copy constructor (or something logically equivalent) and deterministic operations, you should be able to convert it to a wait-free data structure.
We've used CX to make the world's first wait-free balanced binary tree, with integrated wait-free memory reclamation, capable of supporting multiple types. How did we do that? Well, we wrapped a std::set in CX and BOOM, out comes the world's first wait-free balanced BST :)
Several years ago, when Andreia first came up with the idea that we could use a reader-writer lock to achieve wait-freedom, I though that was crazy, but cool. After joining up forces with Pascal and a lot of work, we were able to turn that into a universal construction, CX.
Sure, it has its limitations, but it opens new venues for research and is evidence of some contrarian concepts:
- wait-freedom can be generic and fast (at least for read-mostly workloads);
- wait-free memory reclamation can be lightweight;
- wait-freedom can be achieved with locks;
Now for the bad news: just because it's wait-free, doesn't mean it scales.
CX serializes all mutative operations which means it's flat at best if the workload consists of only mutations on the sequential object.
It also consumes larges amounts of memory and in the very unlikely worst case, may require 2x MAX_THREADS replicas of the sequential object. If the object is a data structure with 1000 nodes, then it doesn't make a dent, but if we're talking about a container with multiple millions of keys and tens of threads writing to it, then it's going to chew up with DRAM pretty fast.
This high memory usage means CX likely won't be your favorite concurrency approach when deploying in production.
The good news is that it scales really well for read-only operations. This means that as long as your workload is read-mostly, it will be able to scale.
Synchronization for read-only operations in CX is very low, typically a few acquire-loads and a single seq-cst fence instruction and beyond that it's just regular loads.
Yes, that's right, the user-code you place in the lambdas is being executed without having to do any load acquires or heavy synchronization fences, just like when you execute code inside a lock!
This is what makes CX be very fast for read-mostly workloads.
In fact, it's so fast that when we submitted the paper to conferences, a few reviewers complained that it was too good to be true and it couldn't possibly be correct. That's how fast it is ;)
Hand-made lock-free data structures can take months (or years) of work by expert researchers to complete, therefore it's normal be greeted with disbelief when we show them a technique capable of transforming generic sequential code into wait-free safe code. Something a young developer can do in minutes. If on top of that we say that it has wait-free memory reclamation and on top of it we show plots where it beats multiple handmade data structures in read-mostly scenarios, then they go ballistic and think it's all a bunch of BS.
It's understandable, we all have our biases. Mine is to think that it's a good idea to trade off large amounts of memory for a generic construct that scales in read-mostly workloads.What's yours?
Hey, nobody's perfect!
and paper here: https://arxiv.org/abs/1911.01676
CX is the first wait-free Universal Construction that can actually be used in practice.
It can take lambdas for its operations, it has integrated (wait-free) memory reclamation, it was extensively tested and it doesn't leak.
CX allows you to take a sequential data structure or object (single-threaded code) and make a wait-free concurrent implementation of the same object by simply encapsulating the methods in calls to updateTx() or readTx(). The resulting data structures have linearizable operations.
Transforming a sequential data structure with CX is not trivial, but it is simple enough that a developer fresh out of college can do it. There are a few rules specific to wait-free UCs that need to be followed (no I/O, no exceptions, no side effects, deterministic code only) but these are easy enough to adhere to.
Unlike handmade wait-free and lock-free data structures, you can have any kind of type in your container (there are limitations on the return values though). All lock-free data structures I've seen so far were meant for integers only, or something equal or smaller than 64bits. Moreover, with CX it's easy to modify the data structure later and add more functionality.
Unlike STMs, CX does not need to have interposing and therefore, we can use CX to wrap data structures in libraries to which we don't have access to the source code. For example, you can use CX to wrap STL containers (we have!). Here is an example on how to make a wait-free std::set
https://github.com/pramalhe/CX/blob/master/examples/WFStdSet.hpp
or even easier, just create the instance and do the operations on the fly:
https://github.com/pramalhe/CX/blob/master/examples/example1.cpp
All you need is a copy constructor for the underlying data structure you want to protect. As long as your sequential data structure has a copy constructor (or something logically equivalent) and deterministic operations, you should be able to convert it to a wait-free data structure.
We've used CX to make the world's first wait-free balanced binary tree, with integrated wait-free memory reclamation, capable of supporting multiple types. How did we do that? Well, we wrapped a std::set in CX and BOOM, out comes the world's first wait-free balanced BST :)
Several years ago, when Andreia first came up with the idea that we could use a reader-writer lock to achieve wait-freedom, I though that was crazy, but cool. After joining up forces with Pascal and a lot of work, we were able to turn that into a universal construction, CX.
Sure, it has its limitations, but it opens new venues for research and is evidence of some contrarian concepts:
- wait-freedom can be generic and fast (at least for read-mostly workloads);
- wait-free memory reclamation can be lightweight;
- wait-freedom can be achieved with locks;
Now for the bad news: just because it's wait-free, doesn't mean it scales.
CX serializes all mutative operations which means it's flat at best if the workload consists of only mutations on the sequential object.
It also consumes larges amounts of memory and in the very unlikely worst case, may require 2x MAX_THREADS replicas of the sequential object. If the object is a data structure with 1000 nodes, then it doesn't make a dent, but if we're talking about a container with multiple millions of keys and tens of threads writing to it, then it's going to chew up with DRAM pretty fast.
This high memory usage means CX likely won't be your favorite concurrency approach when deploying in production.
The good news is that it scales really well for read-only operations. This means that as long as your workload is read-mostly, it will be able to scale.
Synchronization for read-only operations in CX is very low, typically a few acquire-loads and a single seq-cst fence instruction and beyond that it's just regular loads.
Yes, that's right, the user-code you place in the lambdas is being executed without having to do any load acquires or heavy synchronization fences, just like when you execute code inside a lock!
This is what makes CX be very fast for read-mostly workloads.
In fact, it's so fast that when we submitted the paper to conferences, a few reviewers complained that it was too good to be true and it couldn't possibly be correct. That's how fast it is ;)
Hand-made lock-free data structures can take months (or years) of work by expert researchers to complete, therefore it's normal be greeted with disbelief when we show them a technique capable of transforming generic sequential code into wait-free safe code. Something a young developer can do in minutes. If on top of that we say that it has wait-free memory reclamation and on top of it we show plots where it beats multiple handmade data structures in read-mostly scenarios, then they go ballistic and think it's all a bunch of BS.
It's understandable, we all have our biases. Mine is to think that it's a good idea to trade off large amounts of memory for a generic construct that scales in read-mostly workloads.What's yours?
Hey, nobody's perfect!
Wednesday, July 10, 2019
Hydra Conference
The Hydra Conference will start in less than 12 hours and the program is super cool.
Maurice Herlihy will be there, Cliff Click, Michael Scott, Leslie Lamport and many many more. You can check the live feed at this link:
https://hydraconf.com/onlinefree/
Maurice Herlihy will be there, Cliff Click, Michael Scott, Leslie Lamport and many many more. You can check the live feed at this link:
https://hydraconf.com/onlinefree/
Saturday, May 18, 2019
OneFile and wait-free memory reclamation
Last week we talked about OneFile and how it is capable of doing wait-free allocation and de-allocation. This week we'll give a brief intro on how it is capable of doing wait-free memory reclamation.
This isn't the first wait-free memory reclamation scheme, I know of at least one more by Maged Michael based on LL/SC, but OneFile is the first one that is generic in the sense that it works for any data structure (although it requires DCAS). One thing's for sure, the optimistic technique we use in OneFile PTM is the first ever lock-free/wait-free memory reclamation technique shown for Persistent Memory (PM).
Let's start with the volatile memory first.
In a multi-threaded application, pointers to dynamically allocated objects (in the heap) are typically shared among multiple threads. In a lock-free data structure, because another thread may still de-reference a pointer to an object, we can not immediately delete/free the object when we no longer need it.
Instead, we need to use a memory reclamation technique like Pass The Buck, RCU, Hazard Pointers, or Hazard Eras.
In OneFile, user objects are allocated using tmNew() and de-allocated using tmDelete(). Internally, tmNew() calls 'new' and creates a new object that is tracked using Hazard Eras. When tmDelete() is called by the user, the object is placed in a retire list until it is safe to delete.
This technique is not new, Hazard Pointers and pretty much every pointer-based memory reclamation mechanism work like this. The innovation is that because OneFile is an STM, every access to a word of an object in the STM has to go through a load interposing method (we named pload()) and in this pload(), if we see that the sequence associated with the word we're trying to read has been modified and is more recent than the timestamp (curTx) of when we started the transaction, then it might be an inconsistent read, and we abort the transaction, never returning the (possibly incorrect) value at the memory address.
Explained another way, the pload() will never return a value that may be inconsistent (will throw/catch an exception and abort the current transaction) because that's part of how the STM works. A result of this, is that the memory reclamation scheme will never de-reference an incorrect pointer.
The really cool thing about this is that it was _not_ possible to make this option practical until the invention of Hazard Eras. Hazard Eras is the first atomics-only and lock-free memory reclamation scheme that uses epochs instead of pointers. Because of this, it means that a single era can protect all objects alive in a given time instant.
Doing something similar with a pointer-based scheme like Hazard Pointers would require having one published pointer per object traversed. First difficulty, we would have to know to which object a given address belongs to, a highly non-trivial problem in word-based STMs.
Second difficulty, and way more serious, each de-referenced pointer (node traversed in a data structure) needs to be protected first, which on Hazard Pointers means publishing that pointer and doing an mfence (on x86). It also means that each pointer has to have a unique publishing. Example: if we want to traverse a linked list with 1000 nodes, we need to publish 1000 distinct pointers, which other threads will have to scan before they de-allocate a single object. Clearly the memory usage cost of doing 1000 mfences would drown out any chance of making this a suitable approach, plus the fact that to delete an object we have to scan 1000 memory locations to check for a match.
_This_ is the reason why, until now, there has been no lock-free STM with lock-free memory reclamation!
Thanks to Hazard Eras, a single era protects all the objects that the transaction needs to touch, until the transaction commits or aborts.
In a certain sense, OneFile is in a show-case for the power of Hazard Eras.
But it doesn't stop there. Let's take a look at the algorithm for Persistent Memory (PM).
In the wait-free PM variant of OneFile we use the same Hazard Eras algorithm described above to track the std::function objects where the transactions are stored (the lock-free variant doesn't share transactions among threads), but the user allocated objects in PM are handled differently.
For the dynamic objects allocated by the user, we rely on an optimistic technique. Access to a de-allocated object in the mmap()ed region in PM does not trigger a segmentation fault (the object was within the mmaped region) and therefore doesn't have the constraints that using the system allocator has for the volatile heap.
However, it does have the issue that we can _never_ reset the sequence on a tmtype<T>. This sequence must be ever-increasing (takes about 100k years to wrap, so it should be fine), changing with every modification pertaining to a transaction.
The proof is in the paper https://github.com/pramalhe/OneFile/blob/master/OneFile-2019.pdf but it makes the memory reclamation scheme become almost trivial, in the sense that the implementation of the memory reclamation scheme is non-existent, or so it may seem when you look at the code.
Appearances are deceiving and although the no-resetting-sequence-of-a-tmtype being a constraint carefully handled throughout the code, the reason _why_ this is enough is super hard.
As Andreia always says, we make things that look so easy, that people sometimes mistake them for being trivial. Believe me, it's not, and it was not trivial to get there. Andreia, Nachshon, Pascal and I had to work hard to get there.
Until today, there has been no lock-free (much less wait-free) memory reclamation scheme presented for PM, and certainly none that is as generic or as fast as the one we use in OneFile PTM. The fact that we don't have to keep a retired/zombie list in PM is a major breakthrough because persisting such a list has a high cost in number of clwb/clflushopt/sfence. Our optimistic reclamation scheme doesn't have any zombie list: the destructor is immediately called during the transaction (and this is safe even if the transaction later aborts because those changes will themselves be reverted) and the object is immediately de-allocated, all from within the transaction. This guarantees there are no leaks and no allocator metadata corruption in the event of a failure.
Hope you enjoy OneFile.
That's the end of this series for now. I'll come back when we have more cool stuff to talk about.
This isn't the first wait-free memory reclamation scheme, I know of at least one more by Maged Michael based on LL/SC, but OneFile is the first one that is generic in the sense that it works for any data structure (although it requires DCAS). One thing's for sure, the optimistic technique we use in OneFile PTM is the first ever lock-free/wait-free memory reclamation technique shown for Persistent Memory (PM).
Let's start with the volatile memory first.
In a multi-threaded application, pointers to dynamically allocated objects (in the heap) are typically shared among multiple threads. In a lock-free data structure, because another thread may still de-reference a pointer to an object, we can not immediately delete/free the object when we no longer need it.
Instead, we need to use a memory reclamation technique like Pass The Buck, RCU, Hazard Pointers, or Hazard Eras.
In OneFile, user objects are allocated using tmNew() and de-allocated using tmDelete(). Internally, tmNew() calls 'new' and creates a new object that is tracked using Hazard Eras. When tmDelete() is called by the user, the object is placed in a retire list until it is safe to delete.
This technique is not new, Hazard Pointers and pretty much every pointer-based memory reclamation mechanism work like this. The innovation is that because OneFile is an STM, every access to a word of an object in the STM has to go through a load interposing method (we named pload()) and in this pload(), if we see that the sequence associated with the word we're trying to read has been modified and is more recent than the timestamp (curTx) of when we started the transaction, then it might be an inconsistent read, and we abort the transaction, never returning the (possibly incorrect) value at the memory address.
Explained another way, the pload() will never return a value that may be inconsistent (will throw/catch an exception and abort the current transaction) because that's part of how the STM works. A result of this, is that the memory reclamation scheme will never de-reference an incorrect pointer.
The really cool thing about this is that it was _not_ possible to make this option practical until the invention of Hazard Eras. Hazard Eras is the first atomics-only and lock-free memory reclamation scheme that uses epochs instead of pointers. Because of this, it means that a single era can protect all objects alive in a given time instant.
Doing something similar with a pointer-based scheme like Hazard Pointers would require having one published pointer per object traversed. First difficulty, we would have to know to which object a given address belongs to, a highly non-trivial problem in word-based STMs.
Second difficulty, and way more serious, each de-referenced pointer (node traversed in a data structure) needs to be protected first, which on Hazard Pointers means publishing that pointer and doing an mfence (on x86). It also means that each pointer has to have a unique publishing. Example: if we want to traverse a linked list with 1000 nodes, we need to publish 1000 distinct pointers, which other threads will have to scan before they de-allocate a single object. Clearly the memory usage cost of doing 1000 mfences would drown out any chance of making this a suitable approach, plus the fact that to delete an object we have to scan 1000 memory locations to check for a match.
_This_ is the reason why, until now, there has been no lock-free STM with lock-free memory reclamation!
Thanks to Hazard Eras, a single era protects all the objects that the transaction needs to touch, until the transaction commits or aborts.
In a certain sense, OneFile is in a show-case for the power of Hazard Eras.
But it doesn't stop there. Let's take a look at the algorithm for Persistent Memory (PM).
In the wait-free PM variant of OneFile we use the same Hazard Eras algorithm described above to track the std::function objects where the transactions are stored (the lock-free variant doesn't share transactions among threads), but the user allocated objects in PM are handled differently.
For the dynamic objects allocated by the user, we rely on an optimistic technique. Access to a de-allocated object in the mmap()ed region in PM does not trigger a segmentation fault (the object was within the mmaped region) and therefore doesn't have the constraints that using the system allocator has for the volatile heap.
However, it does have the issue that we can _never_ reset the sequence on a tmtype<T>. This sequence must be ever-increasing (takes about 100k years to wrap, so it should be fine), changing with every modification pertaining to a transaction.
The proof is in the paper https://github.com/pramalhe/OneFile/blob/master/OneFile-2019.pdf but it makes the memory reclamation scheme become almost trivial, in the sense that the implementation of the memory reclamation scheme is non-existent, or so it may seem when you look at the code.
Appearances are deceiving and although the no-resetting-sequence-of-a-tmtype being a constraint carefully handled throughout the code, the reason _why_ this is enough is super hard.
As Andreia always says, we make things that look so easy, that people sometimes mistake them for being trivial. Believe me, it's not, and it was not trivial to get there. Andreia, Nachshon, Pascal and I had to work hard to get there.
Until today, there has been no lock-free (much less wait-free) memory reclamation scheme presented for PM, and certainly none that is as generic or as fast as the one we use in OneFile PTM. The fact that we don't have to keep a retired/zombie list in PM is a major breakthrough because persisting such a list has a high cost in number of clwb/clflushopt/sfence. Our optimistic reclamation scheme doesn't have any zombie list: the destructor is immediately called during the transaction (and this is safe even if the transaction later aborts because those changes will themselves be reverted) and the object is immediately de-allocated, all from within the transaction. This guarantees there are no leaks and no allocator metadata corruption in the event of a failure.
Hope you enjoy OneFile.
That's the end of this series for now. I'll come back when we have more cool stuff to talk about.
Tuesday, May 14, 2019
OneFile is also a database engine
In this post we'll talk about OneFile, the world's first wait-free Software Transactional Memory that works on Persistent Memory, and why it's actually a (wait-free) database storage engine.
An STM (Software Transactional Memory) is a library which provides dynamic transactions over multiple objects with linearizable consistency. In effect, an STM provides Atomicity, Consistency and Isolation, but not Durability, i.e. and STM gives ACI transactions.
A Persistent Transactional Memory (PTM) is just like an STM except it also gives Durability, or as I like to call it "failure-resilience". PTMs are capable of providing fully ACID transactions, as long as they're used with byte-addressable Persistent Memory (PM).
Examples of Persistent Memory are the Optane Persistent Memory NV-DIMMS:
https://www.intel.com/content/www/us/en/architecture-and-technology/optane-dc-persistent-memory.html
or the battery backed NV-DIMMS by HP or Viking:
https://www.hpe.com/nl/en/servers/persistent-memory.html
https://www.vikingtechnology.com/products/nvdimm/
Not all PTMs provide ACID with serializable isolation.
In the concurrency literature there are two major distinctions for the consistency of durable transactions:
- durable linearizable: pretty much equivalent to what the databse community calls "serializable isolation" or full ACID transactions;
- buffered durable linearizable: means that transactions are linearizable however, in the event of a failure, a non-specified amount of transactions will be lost up to the current one. The system is guaranteed to be restored to a consistent state in the past, just not necessarily the last committed transaction.
https://urresearch.rochester.edu/institutionalPublicationPublicView.action?institutionalItemId=30821
All the other cases in between, which the database folks have names for such as "dirty reads", "non-repeatable reads", "phantom reads", we just call those "wrong" or "bugs" because that's how most users think of them.
Last year we made a PTM with (blocking) durable linearizable mutative transactions and wait-free read-only transactions called RomulusLR:
https://dl.acm.org/citation.cfm?id=3210392
This PTM has ACID transactions and it's pretty fast due to its combining technique, but it does serialize all mutative transactions. Other PTMs like Mnemosyne don't have this limitation, but they have other limitations.
A pretty well know PTM is libpmemobj in PMDK by the Intel guys, which understandably use it as a way to sell more Optane persistent memory ;)
libpmemobj only has durable transactions and leaves the concurrency part up to the user, either by using a global lock, or fine grained locking (good luck with that!).
https://pmem.io/
PMDK is an awesome piece of software because it has many tools that help enable the usage of persistent memory, not to mention all the effort that the Intel guys have put in in defining standards so that it all works with the PM products from different vendors.
We made a variant of OneFile for PM. In this variant the memory reclamation is done in a different way. We'll leave those details to its own blog post, but the cool thing about OneFile for PM is that it comes with its own memory allocator for persistent memory:
https://github.com/pramalhe/OneFile/blob/master/ptms/OneFilePTMWF.hpp
Even if you don't have persistent memory, you can use a region of your DRAM memory and mmap on it. This will give you durability for process failure but not for system failure. In other words, if the process that is doing a transaction gets killed, the information will be recovered correctly, but if the machine dies (gets unpluged or reboots) then the data is lost (unless you have a persistent memory module in your machine).
The allocator that comes with OneFile is very simple, doesn't do coalescence of blocks or anything like that. We call it EsLoco (Extremely Simple Allocator).
Other allocators can be used, as long as annotation is added to them by adding the template tmtype to each struct/class member of the allocator metadata.
Because the changes to allocator metadata are part of the transaction, there will not be any leaks in the event of a failure and all the operations are wait-free. This means that this allocator is capable of allocating and de-allocating blocks of data in a wait-free way.
In summary, by using OneFile, we've made the world's first wait-free allocator!
So ok, the bad news is that it serializes all operations, whether allocations or de-allocations. Don't expect any scalability from it, but on the other hand, it will be hard to find anything better in a multi-threaded environment when it comes to tail latency.
Another interesting aspect is the number of fences.
When doing a durable transaction in block storage (disk) the typical trick is to do two fsync() or two fdatasync(). The cost of the fsync() is significant because it's about the order of the latency of a round trip to the media device, i.e. the disk's latency.
In PM, the equivalent is to do two pfence (SFENCE instructions on x86). The cost of the pfence is also the cost of a round trip to the device, but this is sub-microsecond so it's not that costly.
Libpmemobj in PMDK uses an undo-log technique, which means it executes two SFENCE per modified range/object in a transaction. Even though the pfence are 1000x cheaper than calling fsync,() if we do too many of them it becomes a performance bottleneck. In OneFile we did our best to reduce the number of pfence to a minimum and reduced them to 2 per transaction, regardless of the number of objects modified during the transaction.
In effect, OneFile is the world's first wait-free database engine. When coupled with persistent memory, it is capable of providing transactions with serializable isolation.
A relevant question would be:
Like all other databases, it has to have a recovery mechanism for when a failure occurs... right?
Actually, no it doesn't.
OneFile is the first database engine with null-recovery. Null-recovery is a property of certain lock-free algorithms which was first introduced in a paper by Izraelevitz et al. in 2016
https://www.cs.rochester.edu/u/scott/papers/2016_DISC_persistence.pdf
Basically it says that some lock-free (and wait-free) algorithms have this property of simply continuing where they left off after a failure, meaning that they don't need a specific recovery procedure to recover after a crash.
This property is theoretically appealing but no database engine or PTM had so far been able to do it. With OneFile we've shown a practical implementation of it and we showed that database recovery can be done with the cost of applying the last incomplete transaction (it's actually possible to do even less).
The database research community has entire papers where they have complicated techniques to improve the time it takes to recover a database: https://research.fb.com/wp-content/uploads/2016/11/fast-database-restarts-at-facebook.pdf?
With OneFile + PM, we've reduced recovery time to the time of a single transaction!
... and did I mention that transactions in OneFile PTM are wait-free and have serializable isolation? :)
Next week we talk about wait-free memory reclamation
An STM (Software Transactional Memory) is a library which provides dynamic transactions over multiple objects with linearizable consistency. In effect, an STM provides Atomicity, Consistency and Isolation, but not Durability, i.e. and STM gives ACI transactions.
A Persistent Transactional Memory (PTM) is just like an STM except it also gives Durability, or as I like to call it "failure-resilience". PTMs are capable of providing fully ACID transactions, as long as they're used with byte-addressable Persistent Memory (PM).
Examples of Persistent Memory are the Optane Persistent Memory NV-DIMMS:
https://www.intel.com/content/www/us/en/architecture-and-technology/optane-dc-persistent-memory.html
or the battery backed NV-DIMMS by HP or Viking:
https://www.hpe.com/nl/en/servers/persistent-memory.html
https://www.vikingtechnology.com/products/nvdimm/
Not all PTMs provide ACID with serializable isolation.
In the concurrency literature there are two major distinctions for the consistency of durable transactions:
- durable linearizable: pretty much equivalent to what the databse community calls "serializable isolation" or full ACID transactions;
- buffered durable linearizable: means that transactions are linearizable however, in the event of a failure, a non-specified amount of transactions will be lost up to the current one. The system is guaranteed to be restored to a consistent state in the past, just not necessarily the last committed transaction.
https://urresearch.rochester.edu/institutionalPublicationPublicView.action?institutionalItemId=30821
All the other cases in between, which the database folks have names for such as "dirty reads", "non-repeatable reads", "phantom reads", we just call those "wrong" or "bugs" because that's how most users think of them.
Last year we made a PTM with (blocking) durable linearizable mutative transactions and wait-free read-only transactions called RomulusLR:
https://dl.acm.org/citation.cfm?id=3210392
This PTM has ACID transactions and it's pretty fast due to its combining technique, but it does serialize all mutative transactions. Other PTMs like Mnemosyne don't have this limitation, but they have other limitations.
A pretty well know PTM is libpmemobj in PMDK by the Intel guys, which understandably use it as a way to sell more Optane persistent memory ;)
libpmemobj only has durable transactions and leaves the concurrency part up to the user, either by using a global lock, or fine grained locking (good luck with that!).
https://pmem.io/
PMDK is an awesome piece of software because it has many tools that help enable the usage of persistent memory, not to mention all the effort that the Intel guys have put in in defining standards so that it all works with the PM products from different vendors.
We made a variant of OneFile for PM. In this variant the memory reclamation is done in a different way. We'll leave those details to its own blog post, but the cool thing about OneFile for PM is that it comes with its own memory allocator for persistent memory:
https://github.com/pramalhe/OneFile/blob/master/ptms/OneFilePTMWF.hpp
Even if you don't have persistent memory, you can use a region of your DRAM memory and mmap on it. This will give you durability for process failure but not for system failure. In other words, if the process that is doing a transaction gets killed, the information will be recovered correctly, but if the machine dies (gets unpluged or reboots) then the data is lost (unless you have a persistent memory module in your machine).
The allocator that comes with OneFile is very simple, doesn't do coalescence of blocks or anything like that. We call it EsLoco (Extremely Simple Allocator).
Other allocators can be used, as long as annotation is added to them by adding the template tmtype to each struct/class member of the allocator metadata.
Because the changes to allocator metadata are part of the transaction, there will not be any leaks in the event of a failure and all the operations are wait-free. This means that this allocator is capable of allocating and de-allocating blocks of data in a wait-free way.
In summary, by using OneFile, we've made the world's first wait-free allocator!
So ok, the bad news is that it serializes all operations, whether allocations or de-allocations. Don't expect any scalability from it, but on the other hand, it will be hard to find anything better in a multi-threaded environment when it comes to tail latency.
Another interesting aspect is the number of fences.
When doing a durable transaction in block storage (disk) the typical trick is to do two fsync() or two fdatasync(). The cost of the fsync() is significant because it's about the order of the latency of a round trip to the media device, i.e. the disk's latency.
In PM, the equivalent is to do two pfence (SFENCE instructions on x86). The cost of the pfence is also the cost of a round trip to the device, but this is sub-microsecond so it's not that costly.
Libpmemobj in PMDK uses an undo-log technique, which means it executes two SFENCE per modified range/object in a transaction. Even though the pfence are 1000x cheaper than calling fsync,() if we do too many of them it becomes a performance bottleneck. In OneFile we did our best to reduce the number of pfence to a minimum and reduced them to 2 per transaction, regardless of the number of objects modified during the transaction.
In effect, OneFile is the world's first wait-free database engine. When coupled with persistent memory, it is capable of providing transactions with serializable isolation.
A relevant question would be:
Like all other databases, it has to have a recovery mechanism for when a failure occurs... right?
Actually, no it doesn't.
OneFile is the first database engine with null-recovery. Null-recovery is a property of certain lock-free algorithms which was first introduced in a paper by Izraelevitz et al. in 2016
https://www.cs.rochester.edu/u/scott/papers/2016_DISC_persistence.pdf
Basically it says that some lock-free (and wait-free) algorithms have this property of simply continuing where they left off after a failure, meaning that they don't need a specific recovery procedure to recover after a crash.
This property is theoretically appealing but no database engine or PTM had so far been able to do it. With OneFile we've shown a practical implementation of it and we showed that database recovery can be done with the cost of applying the last incomplete transaction (it's actually possible to do even less).
The database research community has entire papers where they have complicated techniques to improve the time it takes to recover a database: https://research.fb.com/wp-content/uploads/2016/11/fast-database-restarts-at-facebook.pdf?
With OneFile + PM, we've reduced recovery time to the time of a single transaction!
... and did I mention that transactions in OneFile PTM are wait-free and have serializable isolation? :)
Next week we talk about wait-free memory reclamation
Sunday, May 5, 2019
OneFile and wait-free balanced trees
OneFile is the world's first wait-free STM and as such, it allows to create wait-free trees.
As it so happens, there is a hand-made wait-free tree in the literature but it is not a "balanced", which means that our sequential implementation of a red-black tree protected by OneFile is the first wait-free balanced tree ever made... and did I mention that it has wait-free memory reclamation? :)
Hand-made lock-free trees are not new. A fellow researcher, Trevor Brown, has been particularly prolific in this area and made several robust trees, with integrated memory reclamation and several with lock-free progress (just a small sample of his work on this topic):
https://arxiv.org/abs/1708.04838
https://www.cs.tau.ac.il/~mad/publications/atc2018-bst.pdf
Back in 2013, Aravind Natarajan, Lee Savoie and Neeraj Mittal presented a hande-made wait-free tree. Their tree does not have memory reclamation, which means that as you do a removal of a node from the tree, the node will will not be reclaimed/deleted, thus leaking. Eventually, your application will crash due to running out of memory. I remember I tried once with Andreia to add memory reclamation to their code but it was just too hard, even for epoch-based reclamation.
Moreover, the keys have to be 64 bit variables, from which a couple of bits are stolen to store some metadata. Perhaps there is a way to extend it to generic keys, but it's non-trivial.
This tree is not balanced. What this means is that if you do insertions of keys in sequential order (1,2,3,4,5...) the tree will not re-balance the nodes and what you end up with is just a "linked list" of nodes. Obviously, if you create a tree with 1 million keys, the latency for any operation will be around hours. Yes, hours per insertion or removal or lookup because that's how long it takes to do 1 million traversals of a linked list with 1 million nodes.
This tree is interesting more as a theoretical construct: it showed for the first time that wait-free trees are possible!
We took a sequential implementation of a Red-Black Tree (a balanced tree) and we added the annotation to work with OneFile. The result is a fully functional wait-free balanced tree. Also, it has wait-free memory reclamation for its nodes and the keys are generic (a template parameter).
This isn't the first wait-free balanced tree, that honor falls on CX, a universal construct that is capable of taking any sequential implementation of a data structure and making a wait-free data structure, without even needing annotation of any sort. It even works with std::set.
https://github.com/pramalhe/CX
One day I'll talk more about CX and what it can do, but for the moment let's just say that OneFile is better than CX when it comes to tail latency for writes.
Because OneFile is a generic technique to make concurrent data structures, it means that adding other operations to the underlying data structure is as easy/hard as adding those operations as sequential code. This means it's easy to add things like range queries, do joins/splits, range deletions, range updates, add key A if key B is present, and pretty much anything you can express in C++ code and place inside a lambda. All with linearizable consistency and wait-free progress.
The source code for this wait-free balanced tree can be obtained here:
https://github.com/pramalhe/OneFile/blob/master/datastructures/treemaps/OFWFRedBlackTree.hpp
All you'll need to run it is the header containing the OneFile STM and a C++ compiler.
https://github.com/pramalhe/OneFile/blob/master/stms/OneFileWF.hpp
OneFile is an STM and as such, allows for dynamic transactions. These transactions can cover multiple objects or multiple data structure instances. This means that we can have a wait-free linearizable operation which removes one key from a tree and inserts into another tree, or another data structure. In other words, these transactions are dynamic, have Atomicity, Isolation and Consistency (are linearizable).
... if only we could have Durability... but ohhh wait, there is this thing called "Persistent Memory" (PM) which can give byte-addressable durability.
We have made a variant of the OneFile that is meant for Persistent Memory and gives ACID wait-free transactions.
Next week we'll talk about Persistent Memory and how OneFile is actually the first ever wait-free database storage engine.
As it so happens, there is a hand-made wait-free tree in the literature but it is not a "balanced", which means that our sequential implementation of a red-black tree protected by OneFile is the first wait-free balanced tree ever made... and did I mention that it has wait-free memory reclamation? :)
Hand-made lock-free trees are not new. A fellow researcher, Trevor Brown, has been particularly prolific in this area and made several robust trees, with integrated memory reclamation and several with lock-free progress (just a small sample of his work on this topic):
https://arxiv.org/abs/1708.04838
https://www.cs.tau.ac.il/~mad/publications/atc2018-bst.pdf
Back in 2013, Aravind Natarajan, Lee Savoie and Neeraj Mittal presented a hande-made wait-free tree. Their tree does not have memory reclamation, which means that as you do a removal of a node from the tree, the node will will not be reclaimed/deleted, thus leaking. Eventually, your application will crash due to running out of memory. I remember I tried once with Andreia to add memory reclamation to their code but it was just too hard, even for epoch-based reclamation.
Moreover, the keys have to be 64 bit variables, from which a couple of bits are stolen to store some metadata. Perhaps there is a way to extend it to generic keys, but it's non-trivial.
This tree is not balanced. What this means is that if you do insertions of keys in sequential order (1,2,3,4,5...) the tree will not re-balance the nodes and what you end up with is just a "linked list" of nodes. Obviously, if you create a tree with 1 million keys, the latency for any operation will be around hours. Yes, hours per insertion or removal or lookup because that's how long it takes to do 1 million traversals of a linked list with 1 million nodes.
This tree is interesting more as a theoretical construct: it showed for the first time that wait-free trees are possible!
We took a sequential implementation of a Red-Black Tree (a balanced tree) and we added the annotation to work with OneFile. The result is a fully functional wait-free balanced tree. Also, it has wait-free memory reclamation for its nodes and the keys are generic (a template parameter).
This isn't the first wait-free balanced tree, that honor falls on CX, a universal construct that is capable of taking any sequential implementation of a data structure and making a wait-free data structure, without even needing annotation of any sort. It even works with std::set.
https://github.com/pramalhe/CX
One day I'll talk more about CX and what it can do, but for the moment let's just say that OneFile is better than CX when it comes to tail latency for writes.
Because OneFile is a generic technique to make concurrent data structures, it means that adding other operations to the underlying data structure is as easy/hard as adding those operations as sequential code. This means it's easy to add things like range queries, do joins/splits, range deletions, range updates, add key A if key B is present, and pretty much anything you can express in C++ code and place inside a lambda. All with linearizable consistency and wait-free progress.
The source code for this wait-free balanced tree can be obtained here:
https://github.com/pramalhe/OneFile/blob/master/datastructures/treemaps/OFWFRedBlackTree.hpp
All you'll need to run it is the header containing the OneFile STM and a C++ compiler.
https://github.com/pramalhe/OneFile/blob/master/stms/OneFileWF.hpp
OneFile is an STM and as such, allows for dynamic transactions. These transactions can cover multiple objects or multiple data structure instances. This means that we can have a wait-free linearizable operation which removes one key from a tree and inserts into another tree, or another data structure. In other words, these transactions are dynamic, have Atomicity, Isolation and Consistency (are linearizable).
... if only we could have Durability... but ohhh wait, there is this thing called "Persistent Memory" (PM) which can give byte-addressable durability.
We have made a variant of the OneFile that is meant for Persistent Memory and gives ACID wait-free transactions.
Next week we'll talk about Persistent Memory and how OneFile is actually the first ever wait-free database storage engine.
Wednesday, September 6, 2017
Dawn of the Universal Constructs
Historical Introduction
Some time ago I saw this nice presentation by Andrei Alexandrescu about Generic Locking.https://www.youtube.com/watch?v=ozOgzlxIsdg
He starts the talk by giving an introduction to how the "Concurrency Problem" has been attacked.
And what is the "Concurrency Problem" you might ask?
Well, remember this little issue about Moore's Law (on CPU clock speed) having stopped back in 2004 and that nowadays to get more performance you need to use multiple cores, which means using some form of concurrency? Yeah, that's the "Concurrency Problem"!
Sure, if you can write your application or algorithms in a map-reduce form, then you can parallelize it, but not all algorithms are inherently parallel to profit from this approach, and those are the ones we need to worry about.
As Andrei says in his presentation, in the beginning there were mutual exclusion locks, and those were pretty much the only way to deal with concurrency.
Then came reader-writer locks, lock-free and wait-free data structures, CSP, Actor Models, Software Transactional Memory, Hardware Transactional Memory and many others.
For a while, lock-free and wait-free data structures seemed to be the thing, but the fact that there wasn't a memory model to program them in, and that it was very hard to verify their correctness, and very hard to do efficient lock-free memory reclamation (wait-free is even harder), it caused people to try the other approaches. Nowadays, there is no clear winner, and maybe there never will be. Actor models have been gaining a lot of followers, with the whole Rx/Reactive movement based on it... I'm not sure they all realize that at the base of the actor model is the message-passing queue between the actors which is itself based on a lock-free queue.
Anyways, fast-forwarding to 2017, one of the upcoming CppCon talks which will definitly be worth watching, is the one by Paul McKennney, Maged Michael and Michael Wong:
https://cppcon2017.sched.com/event/Bgtm/the-landscape-of-parallel-programming-models-is-it-still-hard-or-just-ok-part-1-of-2?iframe=no&w=100%&sidebar=no&bg=no
As they mention in the abstract, there was a time when writing a simple loop seemed as perilous then as writing a lock-free data structure seems now.
I don't know what their talk will be about, but I do agree that most of the dangers in concurrent programming can be avoided by using better programming tools, and on that note, I would dare go so far as to say that we're entering "The Dawn of the Universal Constructs"!
What is a Universal Construct
Universal Constructs aren't a new thing. The first Wait-Free Universal Construct (WFUC) was invented by Maurice Herlihy back in 1993:http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p745-herlihy.pdf
WFUCs are a construction that encapsulate an object (or data structure) which was written for single-threaded usage, and provide a way to call its methods with wait-free progress.
It's kind of like wrapping all the methods in an object with a call to lock()/unlock() of a mutual exclusion lock, except that a lock is blocking while WFUC are, well, wait-free!
In summary, a Wait-Free Universal Construct lets you write your favorite data structure as if it was "single-threaded code" and then wraps its methods to provide wait-free progress.
If you saw Andrei's presentation at the beginning of the post, you'll know that he has a cool way (in C++) of automatically exporting the methods of an object/data-structure wrapped with a read-lock or a write-lock depending on whether the methods are mutative or read-only. The same kind of approach can be done with WFUCs, which means that they are truly generic.
How come I never heard of this before?
Well, you kind of have heard about this (if you read this blog).Left-Right for example, is a Universal Construct that provides wait-free progress for readers and blocking (starvation-free) progress for writers:
http://concurrencyfreaks.blogspot.nl/2013/12/left-right-concurrency-control.html
It's fast, it reclaims memory, it's "universal", but it's not completely wait-free, i.e. it's not wait-free for mutations.
There are truly WFUCs in the literature and we've even added (wait-free) memory reclamation to a few of them. The most famous being P-Sim by Panagiota Fatourou and Nikolaos Kallimanis:
http://thalis.cs.uoi.gr/tech_reports/publications/TR2011-01.pdf
But even the best of them still works on the COW principle, in the sense that it requires a full copy of the data structure for every mutation.
Yes, that's right, if we have a map with 1M keys/values, and we want to insert a new key (or remove an existing one), we have to make a full copy of the 1M nodes of the data structure.
Waaaaiiiit wwwhhhaaat? Did you just say that this thingy has to copy 1 million nodes every time I want to insert a new key/value in my hashmap?
Yes, I'm afraid that's how it works. It's not as bad as it looks if the data structure is small, but as soon as you start going to anything bigger than a few thousand nodes in the data structure, throughput is going to go down the drain. And cache locality is a big issue with COW.
What's on the horizon
I happen to have insider knowledge that it is possible to make a wait-free universal construct that is fast enough to be used in production, because it doesn't have to copy the entire data structure (except on very rare occasions). This new way of doing WFUCs is fast enough to be used in real-life applications, in fact, it's capable of beating hand-written lock-free and wait-free data structures.Yes, it's that good. We call it CX and the paper is almost ready.
... did I say it does wait-free memory reclamation as well? ;)
As soon as other researchers see what CX is capable of, I'm sure they will have their own ideas and improve upon it, thus bringing about a new age of production-capable WFUCs.
Going back to the Concurrency Problem, how does this change the way we program multi-threaded applications?
Based on my experience as a developer, software engineers rarely use an off-the-shelf data structure as is. We always add a little twist to it.I don't know whether this happens due to us having big egos and wanting to give our little personal touch to everything we do (I'm generalizing here), or if it's simply because we're tinkerers and we like to see what's under the hood and tweak it to our own desire. the truth is, if we could use it as is then there wouldn't be a need to write all the software people write, there would be just one search engine, just one banking software, just one customer management software, etc.
Whatever the reason may be, the consequence is, that we always make changes to the data structures, and the problem with that, is that lock-free and wait-free data structures will fall apart if they're touched. They have sequences of instructions that have to be done in a particular way, they have optimizations for relaxed memory orderings and subtle details, and memory reclamation, etc, etc. The temptation to touch and tinker a lock-free data structure is just too much, and we end up getting burned and then we say that "lock-free data structures suck", which is not true.
The algorithms behind these data structures are very subtle, and our human nature is to tinker with it, which is incompatible.
This is where Wait-Free Universal Constructs come in.
With an efficient WFUC, any software engineer without any knowledge of lock-free data structures (or atomics or the memory model) can just take a "single-threaded data structure", modify it to satisfy its needs (or ego) and then wrap it with WFUC and BOOOOM, out comes a fast and scalable implementation of its customized data structure, with wait-free progress.
Even more, another software engineer working on the code can later fix bugs or add new features to the data structure without breaking its correct functionality. Try doing that with a lock-free data structure, it's hard enough to get it right the first time, to add new functionality later is just too nuts.
As a software engineer, what more could I ask for?
No wonder that WFUCs are seen by researchers as the Holy Grail of concurrency, it's because they make it so easy to solve the Concurrency Problem in production.
Yes, I'm a fan boy of Universal Constructs, but the hype is called for and needed. This stuff doesn't solve all the concurrency problems, but it solves a a lot of them, enough to become a standard way of dealing with multi-threaded code, or at least for writing multi-threaded data structures.
Whatever happens, Universal Constructs are here to stay as one of the easiest tools to use when writing multi-threaded applications, and we all know that when it comes to multi-threaded programs, any help we can get is not enough ;)
Subscribe to:
Posts (Atom)