4 ms·

Multithreading sure is complicated. I'm currently playing with multithreading right now. I'm implementing snapshot isolation multiversion concurrency control.

Multithreading sure is complicated. I'm currently playing with multithreading right now. I'm implementing snapshot isolation multiversion concurrency control. In theory you can avoid locks (except for data structure locks) by creating a copy of the data you want to write and detect conflicts at read and commit time. Set the read timestamp of a piece of data to the transaction timestamp (timestamps are just monotonically increasing numbers) that reads it. If someone with a higher transaction timestamp comes along, they abort and restart because someone got in before them. At the moment I have something that mostly works but occasionally executes a duplicate. I'm trying to eradicate the last source of bugs but as with anything parallel, it's complicated due to the interleavings. My test case is to spin up 100 threads, with each thread trying to increment a number. The end numbers should be 101 and 102. If there was a data race, then the numbers will be lower. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro...

namibj 5y ago
Have you heard of TLA+? If not, I suggest checking it out. It's kinda made to handle investigating and preventing such rare race conditions.
- im_down_w_otp 5y ago
  That assumes that the problem is in their model, not their implementation.
  - vlovich123 5y ago
    In something like described, it sounds like the design part is where they’re at. If they were optimizing a working algorithm (eg selecting the best memory ordering for some operation), then I’d say they’re in the implementation phase. What’s not clear to me is if TLA+ can properly model the memory model. If I recall correctly, it doesn’t. You’re just testing your logic. That does still leave for some heavy lifting to be done.
    - namibj 5y ago
      AFAIK it can model the interleaving possibilities at hand, and helps to find somewhat short execution traces that violate some logic/assumptions.
senderista 5y ago
Very cool! I’ve spent the last few months implementing a production MVCC system that’s completely lock-free. It’s really quite simple, but there were initially bugs in all the concurrent algorithms I designed. I wish I had time to learn TLA+ and properly model-check the algorithms, but for now I have to gain confidence just from stress testing and thinking hard about interleavings. The main thing I’ve learned is not to over-optimize. Keeping the algorithms as simple as possible is the only way I can reason about them.
- samsquire 5y ago
  Does your commit function run in parallel too?

namibj 5y ago

Have you heard of TLA+? If not, I suggest checking it out. It's kinda made to handle investigating and preventing such rare race conditions.

im_down_w_otp 5y ago
That assumes that the problem is in their model, not their implementation.
- vlovich123 5y ago
  In something like described, it sounds like the design part is where they’re at. If they were optimizing a working algorithm (eg selecting the best memory ordering for some operation), then I’d say they’re in the implementation phase. What’s not clear to me is if TLA+ can properly model the memory model. If I recall correctly, it doesn’t. You’re just testing your logic. That does still leave for some heavy lifting to be done.
  - namibj 5y ago
    AFAIK it can model the interleaving possibilities at hand, and helps to find somewhat short execution traces that violate some logic/assumptions.

senderista 5y ago

Very cool! I’ve spent the last few months implementing a production MVCC system that’s completely lock-free. It’s really quite simple, but there were initially bugs in all the concurrent algorithms I designed. I wish I had time to learn TLA+ and properly model-check the algorithms, but for now I have to gain confidence just from stress testing and thinking hard about interleavings. The main thing I’ve learned is not to over-optimize. Keeping the algorithms as simple as possible is the only way I can reason about them.

samsquire 5y ago
Does your commit function run in parallel too?