真夜中のconsistency談義
-
- いいね！0
Nobuyuki Kubota
@nobu_k
やっぱりsequential consistencyの定義は毎回頭がこんがらがる。でも今まで読んだ中で割とわかりやすい部類な気がする。
2011-07-24 23:23:05
Nobuyuki Kubota
@nobu_k
@kumagi_bot 俺が知りたいｗ なんか複数のクライアント(マルチプロセッサ環境だとCPU)がいる状況で、特定のクライアントからみて、実際の実行順序がクライアントが実行した通りの順序(実行結果を含む)にリオーダリングできれば良いという話が＞某本 (140文字短いｗ
2011-07-24 23:56:56
Nobuyuki Kubota
@nobu_k
本の分野によっていろいろ話が変わるということで、他の分野だとこういう意味になりますっていう例はいくつか載ってる。制限が緩くなるほど理解するのが難しくなるｗ
2011-07-24 23:59:20
kumagi
@kumagi_bot
@nobu_k 例えばデータベースの分野だと範囲検索があるので、ファントムリードは発生し得ると思いますが、普通のメモリ上でやる分には関係のない話ですよね。
2011-07-25 00:10:01
Nobuyuki Kubota
@nobu_k
Linearizabilityとserializabilityの違いも良くわからなくなって調べたけど良くわからなかった。しかしこれは寝て起きると分かってたことになってる系のわからなさだと思うので寝る。
2011-07-24 23:45:46
kumagi
@kumagi_bot
write skeyが発生するANSI serializable consistencyと、発生しないmathematically serializable consistencyとで、どう違うのか。write skewが困る状況とは何か。
2011-07-24 23:48:48
kumagi
@kumagi_bot
何らかのデータを書き込む瞬間に、書きこむデータはもちろんのこと、書きこむ要因となった全ての判断材料が書き込みの瞬間まで同じであれば、serializable consistencyだと思ってたんだけど、それだと何らかの暗黙の依存関係を無視してしまう、という弁が立たないと…。
2011-07-24 23:51:16
Nobuyuki Kubota
@nobu_k
Transactional Information Systemsにはもう少し細かい話が載ってた気もする。あれもまた読み直したいなぁ。そろそろちゃんと読める気がする。
2011-07-25 00:00:44
kumagi
@kumagi_bot
@nobu_k すいませんまずsequential consistencyとserializable consistencyの違いからしてわかっていませんでした。結果的に実際の実行順序で直列に行われた場合に出来れば良い、というのはつまり数字を振れるという事ですよね。
2011-07-25 00:07:49
Nobuyuki Kubota
@nobu_k
@kumagi_bot 数字を振れるということだと思います！ メモリの特定の位置をアトミックに書き換えられるなら関係ない話に見えましたが、キャッシュとかが絡んでくるとどうなんだろう。。。後はなんかマルチプロセッサ環境だとseq_cstが一番強いという記述があったり。
2011-07-25 00:16:00
Nobuyuki Kubota
@nobu_k
マルチプロセッサでlinearizableにしようと思うと、すべてのプロセッサから常に同じ状態が見えるように制御しないといけないということなのかな？そしてレプリケーション本にはserializableに関する記述が無いので良くわからなくなってきたなう。
2011-07-25 00:18:18
kumagi
@kumagi_bot
@nobu_k えーと、その話は若干レイヤーを混同していると思います。例えば「1.配列の中身の数値を全部合計して」「2.その値をその配列の末尾に加える」という処理の場合、末尾への追加をseq_cstでアトミックに行なっても、0〜10までの足し算の結果を配列の100番目に加えたり…
2011-07-25 00:25:18
kumagi
@kumagi_bot
@nobu_k この場合seq_cstでアトミックに行なおうとセマンティクスレベルでのsequential consistencyを満たせないです。結果に対し後付でどのような数字の振り方を考えても、他のトランザクションに割り込まれない限り説明が付かないような状態になるのです。
2011-07-25 00:28:14
Nobuyuki Kubota
@nobu_k
そうそう、トランザクションの話だと、個々のトランザクションを1個のブロックと見なして完全に分離して実行した場合と同じ状態に持って行けるかとかそう言う話がメインだった。今読んでるのはトランザクションと言うより操作単位での話か。むむ。
2011-07-25 00:24:28
kumagi
@kumagi_bot
@nobu_k マルチプロセッサが提供する一貫性はこういう緩さがあって、その緩さの上でより強い一貫性を満たそうと思った場合にはどこにどういう配慮を加えてやればいいか、を考える議論だと思います。メモリモデルゆるっゆるなalpha上で同じ状態が見えるようにするためにどうするか、とか。
2011-07-25 00:31:05
Nobuyuki Kubota
@nobu_k
@kumagi_bot あー、複数のオペレーションにまたがるようなトランザクション的な話では無いですー。単純に個々のCPUがそれぞれ別のキャッシュを持っている状態で特定のメモリアドレスに書き込むと、全体に書き込んだ内容を反映しないといけないと思うんですが、という話でした。
2011-07-25 00:29:37
kumagi
@kumagi_bot
@nobu_k なるほど。そうですね、特定のメモリアドレスに書き込んだら適切なタイミングで全体から見えるようにしないと不味いです。で、常にその条件を満たし続けようとすると絶対にパフォーマンスが出なくなるので、同様の一貫性を保ちつつどこまでその条件を満たすタイミングをサボろうか、と
2011-07-25 00:33:51
Nobuyuki Kubota
@nobu_k
@kumagi_bot linearizableを実現しようとすると、実行時のコストが凄いことになってしまうので採用してないという話ですよね。実際はもう少し緩い制約でも問題なく扱えて速度も速くなる。そんで一般的なプロセッサだとseq_cstが一番強い制約である場合が多いと。
2011-07-25 00:33:56
kumagi
@kumagi_bot
@nobu_k 一般的なプロセッサでのseq_cstの明示はたとえばx86だったらmfenceを使って指定する(確か)わけですが、その画鋲を用いてどこをピン止めすれば意味を壊さずパフォーマンスを得られるかを考える物で、alphaのようなCPUになったらピンの種類も増えて大変な事に
2011-07-25 00:41:19
kumagi
@kumagi_bot
@nobu_k 一般的なプロセッサでのseq_cstの明示はたとえばx86だったらmfenceを使って指定する(確か)わけですが、その画鋲を用いてどこをピン止めすれば意味を壊さずパフォーマンスを得られるかを考える物で、alphaのようなCPUになったらピンの種類も増えて大変な事に
2011-07-25 00:41:19