5 ms·

Software Transactional Memory (1997)

24 points by luu 4y ago

CMCDragonkai 4y ago
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?
arghnoname 4y ago
GCC supports code generation that will call into several different software transactional memory (STM) engines. It's not difficult to write your own engine that is called instead of a default version. What this basically does is generate multiple versions of functions that can be called both in and not in a transaction. Functions that may be called in a transaction have to be side-effect free (i.e., no system calls, recursively). The modified functions run code for each line of memory read or written so the STM engine can decide what to do with it (e.g., reads can be redirected to other locations, writes can be used to dirty memory or redirected to a scratch location). There are different trade-offs for efficiency, conflicts, etc. For instance, if each transaction begin just started with a global exclusive lock it would be correct, simple, and you'd never get conflicts, but just serializes everything. There are trade-offs. Languages with more rigid semantics and a propensity towards immutability would require less annotation. The GCC version generates these invocations for engine functions on most loads and stores. As you'd imagine, it's pretty expensive as is and basically is not used as a generic method of concurrency control for this reason.
- anonymousDan 4y ago
  Interesting, do you have a link to the documentation for this (or even a paper describing the design)? Does Clang/LLVM have something similar? I wonder would adding STM to Rust be more practical in terms of performance (or does the question even make sense given it already guarantees data race freedom)?
  - arghnoname 4y ago
    There's an Intel ABI specification that GCC closely follows. The gcc implementation is called libitm and their specification is just listed as a diff of intel's specification. Here is gcc's doc on libitm https://gcc.gnu.org/onlinedocs/libitm/ https://gcc.gnu.org/onlinedocs/libitm/ Here is intel's document (much more useful): https://gcc.gnu.org/wiki/TransactionalMemory?action=AttachFile&do=get&target=Intel-TM-ABI-1_1_20060506.pdf https://gcc.gnu.org/wiki/TransactionalMemory?action=AttachFi... I'm not sure what the support story is like on clang.
  - gpderetta 4y ago
hardwaresofton 4y ago
No modern language I know of beats Haskell’s support for STM: https://wiki.haskell.org/Software_transactional_memory https://wiki.haskell.org/Software_transactional_memory As I always say, Haskell is the Mercedes of programming languages.
- kortex 4y ago
  > Haskell is the Mercedes of programming languages. Comfortable, packed with features, pretty fast given its weight, kind of elitist yet approachable if you invest time in it? :p
  - hardwaresofton 4y ago
    ding ding ding! Also something about inventing/spurring mass adoption of airbags and ABS. Safe and fast.
- the-alchemist 4y ago
  I don't have much experience with Haskell, but Clojure also has STM out-of-the-box. I don't know if it's the approach described in paper, but it's quite fast. It's probably made faster by the fact that almost all data in Clojure is immutable. "The Clojure STM uses multiversion concurrency control with adaptive history queues for snapshot isolation, and provides a distinct commute operation." https://clojure.org/reference/refs https://clojure.org/reference/refs, for the curious and brave
  - dkersten 4y ago
    Interestingly, I’ve been using Clojure since 2009 and I’ve never once used STM (outside of playing around to learn how to use it). I’ve used agents on occasion, I’ve used atoms, I’ve used core.async a lot, but refs and STM, to me (ie YMMV) seem like one of those things that seemed like a useful great idea, that in practice just wasn’t really necessary. Maybe others have had a different experience, of course. This is just an observation about my own code and the libraries I use.

24 points by luu 4y ago

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?

arghnoname 4y ago

GCC supports code generation that will call into several different software transactional memory (STM) engines. It's not difficult to write your own engine that is called instead of a default version. What this basically does is generate multiple versions of functions that can be called both in and not in a transaction. Functions that may be called in a transaction have to be side-effect free (i.e., no system calls, recursively). The modified functions run code for each line of memory read or written so the STM engine can decide what to do with it (e.g., reads can be redirected to other locations, writes can be used to dirty memory or redirected to a scratch location). There are different trade-offs for efficiency, conflicts, etc. For instance, if each transaction begin just started with a global exclusive lock it would be correct, simple, and you'd never get conflicts, but just serializes everything. There are trade-offs. Languages with more rigid semantics and a propensity towards immutability would require less annotation. The GCC version generates these invocations for engine functions on most loads and stores. As you'd imagine, it's pretty expensive as is and basically is not used as a generic method of concurrency control for this reason.

anonymousDan 4y ago
Interesting, do you have a link to the documentation for this (or even a paper describing the design)? Does Clang/LLVM have something similar? I wonder would adding STM to Rust be more practical in terms of performance (or does the question even make sense given it already guarantees data race freedom)?
- arghnoname 4y ago
  There's an Intel ABI specification that GCC closely follows. The gcc implementation is called libitm and their specification is just listed as a diff of intel's specification. Here is gcc's doc on libitm https://gcc.gnu.org/onlinedocs/libitm/ https://gcc.gnu.org/onlinedocs/libitm/ Here is intel's document (much more useful): https://gcc.gnu.org/wiki/TransactionalMemory?action=AttachFile&do=get&target=Intel-TM-ABI-1_1_20060506.pdf https://gcc.gnu.org/wiki/TransactionalMemory?action=AttachFi... I'm not sure what the support story is like on clang.
- gpderetta 4y ago

hardwaresofton 4y ago

No modern language I know of beats Haskell’s support for STM: https://wiki.haskell.org/Software_transactional_memory https://wiki.haskell.org/Software_transactional_memory As I always say, Haskell is the Mercedes of programming languages.

kortex 4y ago
> Haskell is the Mercedes of programming languages. Comfortable, packed with features, pretty fast given its weight, kind of elitist yet approachable if you invest time in it? :p
- hardwaresofton 4y ago
  ding ding ding! Also something about inventing/spurring mass adoption of airbags and ABS. Safe and fast.
the-alchemist 4y ago
I don't have much experience with Haskell, but Clojure also has STM out-of-the-box. I don't know if it's the approach described in paper, but it's quite fast. It's probably made faster by the fact that almost all data in Clojure is immutable. "The Clojure STM uses multiversion concurrency control with adaptive history queues for snapshot isolation, and provides a distinct commute operation." https://clojure.org/reference/refs https://clojure.org/reference/refs, for the curious and brave
- dkersten 4y ago
  Interestingly, I’ve been using Clojure since 2009 and I’ve never once used STM (outside of playing around to learn how to use it). I’ve used agents on occasion, I’ve used atoms, I’ve used core.async a lot, but refs and STM, to me (ie YMMV) seem like one of those things that seemed like a useful great idea, that in practice just wasn’t really necessary. Maybe others have had a different experience, of course. This is just an observation about my own code and the libraries I use.