Software Transactional Memory の雰囲気メモ

wikipedia の ( Software Transactional Memoryのページ ) を眺めたまとめのメモと、toy 実装をしてみた話。

stm の rust 実装見ながら書いてたんだけど、そのまま rust で書くのもあれなのでなんとなく go で書いてみた。ちなみに int にしか対応していない完全なトイ実装。

STM

並列プログラミングをする際に、共有メモリへのアクセスを制御するための機構のことで、ロックを使用した排他制御機構の代替として使用できる。例えば、ロックを使用してスレッドセーフなプログラムを実現するには以下のようになる。

v := 1
m := new(sync.Mutex)

go func() {
    m.Lock()
    v += 1
    m.Unlock()
}()

go func() {
    m.Lock()
    v += 1
    m.Unlock()
}()


...

これを STM で実現すると以下のようになる(自分で実装した STM だけど大体ほかの実装もこんなシンタックスになってるはず)。

tvar := istm.NewTVar(1)

go func() {
    tv, _ := istm.Atomically(func(t *istm.Transaction) (int, error) {
        v := tvar.Read(t)
        tvar.Write(t, v+1)
        return v, nil
    })

    fmt.Printf("t1: %v\n", tv)
}()

go func() {
    tv, _ := istm.Atomically(func(t *istm.Transaction) (int, error) {
        v := tvar.Read(t)
        tvar.Write(t, v+1)
        return v, nil
    })

    fmt.Printf("t2: %v\n", tv)
}()

...

Atomically のブロック内は必ずアトミックであることが保証されているので、STM の方ではロックを(シンタックス上は)使用せずにスレッドセーフなプログラムを書くことができる。ロックを使用する問題点として、デッドロックやライブロックが発生するコードが書けてしまうこと、ロックし忘れてレースコンディションが発生する恐れがあること、優先順位の逆転が発生することなどがある。 STM はロックに比べて高いレベルの抽象化を提供しているので、そのあたり問題をいい感じに回避している。また、STM の利点としてスケールしやすいという点もある。ロックを用いた場合、大雑把にロックを取るとそこがボトルネックとなりスケールしないプログラムになってしまう(逆に細粒度にロックを取ろうとするとバグを生み出しやすいという問題もある)。しかし、STM は変更をコミットする瞬間だけロックを取ることで大きなロックを取る必要がなくなりスケールするプログラムを意識しなくても書くことができる。問題点もあって、コミットにする際に一貫性が取れていないとすべての処理をアボートして、再度処理を初めからすべて実行し直すためオーバヘッドが大きいというのがある。

実装

github.com

DB で言うところの楽観的ロックみたいな実装をしている。アトミックなブロック中 (istm.Atomicallyに渡されたクロージャ) での変更はトランザクションでログとして持っておき、ブロックが終了するときにまとめて変更をコミットする(このへん)。コミット処理の際に一貫性を検査し、他のトランザクションと衝突していたら自分側の変更をすべて破棄する。これを成功するまで何度も再実行する。

memo-mode

Software Transactional Memory の雰囲気メモ

STM

実装

参考