Comment by CMCDragonkai | Hacker News Reader

Comment by CMCDragonkai | Hacker News Reader

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. 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.

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).

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!)

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.

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-contro...

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 repo to help control all sorts of concurrent effects.

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.

Isn't there a SharedArrayBuffer thingy in workers now?

Yes shared memory exists for webworkers. Furthermore JS land has different kinds of threading implementations, see threadsjs.

But I'm not talking about concurrency control between threads, but between asynchronous operations.

In our experience race conditions happen in JS regardless of its single threaded nature. It happens because of concurrent asynchronous operations that work on shared state that exists not necessarily in-memory but also in embedded databases. So most definitely concurrency control must be applied whenever there is any kind of shared state. The single threadedness doesn't matter if there are concurrent asynchronous operations.

YMMV but when I was writing the rocksdb native binding into nodejs, I saw that any asynchronous operations setup in the C++ would be dispatched to separate threads. Didn't explore further though. It was built into the NAPI bindings.

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

Reply on news.ycombinator.com