3 ms·

I've been working on a JS database to support optimistic concurrency control. I did some research and arrived on 2 seemingly related concepts but from independe

I've been working on a JS database to support optimistic concurrency control. I did some research and arrived on 2 seemingly related concepts but from independent research lines. Software transactional memory in functional programming/Haskell land versus snapshot isolation in database research. After reading them both, I asked this unanswered question on SO: https://stackoverflow.com/q/72084071/582917 https://stackoverflow.com/q/72084071/582917. My theory is that STM is the same as SI, but most SI database implementations don't just do value comparisons, but actually check a logical timestamp. This is probably done for performance reasons as databases handle larger pieces of data than functions would when using STM. Along the way I also discovered SSI serializable snapshot isolation but it isn't yet available in rocksdb but cockroachdb apparently has a fork of rocksdb with it but I couldn't find it. Anyway the db library which wraps around rocksdb is available to be used embedded in any nodejs program at https://github.com/MatrixAI/js-db https://github.com/MatrixAI/js-db.

anonymousDan 4y ago
These are apples and oranges. Snapshot isolation is a consistency guarantee, STM is a concurrency control mechanism. STM can be used to provide snapshot isolation (or stronger guarantees such as linearizability).
- jsmith45 4y ago
  you are correct that snapshot isolation is a consistency guarantee. But I'm guessing the grand parent was really talking about MVCC-style database implementations, which are conceptually similar to some of the STM approaches. MVCC implementations are indeed fundamentally about concurrency, but they also tend to make snapshot isolation easy to implement. (Far easier than implementing snapshot isolation with classic pessimistic locking!)
  - CMCDragonkai 4y ago
    Yes I'm talking about snapshot isolation when implemented as a concurrency control system in databases. But I don't think they used STM approaches to do it. So STM works nicely inside languages like Haskell, but when you work with a library database you can gain similar behaviour by using a key value database that has SI.
thesz 4y ago
I think you are right about STM being roughly equivalent to snapshot isolation. What STM offers is an easy way to invent "containers for snapshotted values" aka TVars. Using them carefully may result in better scaling: https://hackage.haskell.org/package/stm-containers https://hackage.haskell.org/package/stm-containers
samsquire 4y ago
Could you explain what you are doing? JavaScript is single threaded so I cannot see how you can implement actual concurrency control. I implemented multiversion concurrency control in Java but I am yet to include the algorithm from the whitepaper Serializable Snapshot Isolation. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro...
- CMCDragonkai 4y ago
  JavaScript isn't single threaded anymore. There's workers and even at the C++ extension native add-ons are exposed to libuv threading. But even in single threaded JS, asynchronous handlers can result in concurrent race conditions. That's why concurrency control is necessary. I also maintain https://github.com/MatrixAI/js-async-locks https://github.com/MatrixAI/js-async-locks repo to help control all sorts of concurrent effects.
  - samsquire 4y ago
    Even from a nodejs extension and libuv perspective, Javascript has one event loop. You can create your own libuv event loops and run them on a separate pthread. If you create a pthread in your own C++ extension then you're not really talking of Javascript. Workers are not threads but they run in their own thread. Unfortunately you don't have shared memory. So you kind of have snapshot isolation by immutability. They can only communicate with postMessage. They're not threads, they do not share address space. So Javascript is single threaded. If you're getting race conditions with your multiversion concurrency control implementation, then you might need to look at how you isolate versions from one another. Write a unit test that adds numbers from 1 to 100 from 100s of concurrent transactions, you should end with 100 every time if you have no race conditions. Without parallelism, you could introduce a bulk command API and wrap all your writes and reads in a single function. The single threaded nature of Javascript will prevent race conditions if you do this - only one function can run at a time.
    - mping 4y ago
      Isn't there a SharedArrayBuffer thingy in workers now?

anonymousDan 4y ago

These are apples and oranges. Snapshot isolation is a consistency guarantee, STM is a concurrency control mechanism. STM can be used to provide snapshot isolation (or stronger guarantees such as linearizability).

jsmith45 4y ago
you are correct that snapshot isolation is a consistency guarantee. But I'm guessing the grand parent was really talking about MVCC-style database implementations, which are conceptually similar to some of the STM approaches. MVCC implementations are indeed fundamentally about concurrency, but they also tend to make snapshot isolation easy to implement. (Far easier than implementing snapshot isolation with classic pessimistic locking!)
- CMCDragonkai 4y ago
  Yes I'm talking about snapshot isolation when implemented as a concurrency control system in databases. But I don't think they used STM approaches to do it. So STM works nicely inside languages like Haskell, but when you work with a library database you can gain similar behaviour by using a key value database that has SI.

thesz 4y ago

I think you are right about STM being roughly equivalent to snapshot isolation. What STM offers is an easy way to invent "containers for snapshotted values" aka TVars. Using them carefully may result in better scaling: https://hackage.haskell.org/package/stm-containers https://hackage.haskell.org/package/stm-containers

samsquire 4y ago

Could you explain what you are doing? JavaScript is single threaded so I cannot see how you can implement actual concurrency control. I implemented multiversion concurrency control in Java but I am yet to include the algorithm from the whitepaper Serializable Snapshot Isolation. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro...

CMCDragonkai 4y ago
JavaScript isn't single threaded anymore. There's workers and even at the C++ extension native add-ons are exposed to libuv threading. But even in single threaded JS, asynchronous handlers can result in concurrent race conditions. That's why concurrency control is necessary. I also maintain https://github.com/MatrixAI/js-async-locks https://github.com/MatrixAI/js-async-locks repo to help control all sorts of concurrent effects.
- samsquire 4y ago
  Even from a nodejs extension and libuv perspective, Javascript has one event loop. You can create your own libuv event loops and run them on a separate pthread. If you create a pthread in your own C++ extension then you're not really talking of Javascript. Workers are not threads but they run in their own thread. Unfortunately you don't have shared memory. So you kind of have snapshot isolation by immutability. They can only communicate with postMessage. They're not threads, they do not share address space. So Javascript is single threaded. If you're getting race conditions with your multiversion concurrency control implementation, then you might need to look at how you isolate versions from one another. Write a unit test that adds numbers from 1 to 100 from 100s of concurrent transactions, you should end with 100 every time if you have no race conditions. Without parallelism, you could introduce a bulk command API and wrap all your writes and reads in a single function. The single threaded nature of Javascript will prevent race conditions if you do this - only one function can run at a time.
  - mping 4y ago
    Isn't there a SharedArrayBuffer thingy in workers now?