Google Spannerまとめ

Bigtable、Megastoreに続くGoogleの最新世代のデータストアSpannerについての皆さんの考察をまとめました。
14
ICHIRO SATOH @ichiro_satoh

続き。分散システムも、Strict/Sequential/Casual/Weak ConsistencyとLinearizabilityについて、それぞれの実装方法が、パッと頭に浮かぶようになったら一人前なのでしょうが、これは体型的に勉強しないと難しい。

2012-06-07 09:33:45
Kazunori Sato @kazunori_279

@ichiro_satoh 並行プログラミングというよりマルチプロセッサ設計の文脈で使われる意味に近い。。ということでしょうか?

2012-06-07 09:40:50
Kazunori Sato @kazunori_279

@ichiro_satoh linearlizabilityのところがすっきりしないですが、全体としては「GPS+原子時計でグローバルに全順序のタイムスタンプ用意してTXのコミット順を並べたりsnapshot readを実現する」って理解しました。。どうでしょう?

2012-06-07 09:42:24
ICHIRO SATOH @ichiro_satoh

もともと並行プログラミングが初出で、マルチプロセッサもそれに近いはず。ちなみにデータ複製の分野ではグロバール時刻による順序づけも要件になります。RT @kazunori_279 並行プログラミングというよりマルチプロセッサ設計の文脈で使われる意味に近い。。ということでしょうか?

2012-06-07 09:44:40
ICHIRO SATOH @ichiro_satoh

はい、だいたいいいと思います。ただSnapshot Readのところはちょっとわからない。でも中の人にきかれるとは。RT @kazunori_279 linearlizabilityのところがすっきりしないですが、全体としては「GPS+原子時計でグローバルに全順序のタイム…

2012-06-07 09:47:28
ICHIRO SATOH @ichiro_satoh

続き。分散アルゴリズム研究では高精度の時計がないことを前提に複雑なら手順を数多く提案してきましたが、GPSによる時刻合わせを前提にしたら、その多くは無駄になるということ。

2012-06-07 09:49:34
ICHIRO SATOH @ichiro_satoh

続き。GPSの時刻合わせは予想候補の一つだったのですが、Snapshop Readは意外。実はSpannerはLock回避のため、Leaseを使うと予想していました。故障は少ないということなのでしょうね。

2012-06-07 09:52:22
ICHIRO SATOH @ichiro_satoh

続き。セシウムクロックよりは3桁ぐらい精度が落ちますが、1cmキューブぐらいの小型原子時計が試作されており、将来的にはすべてのコンピュータに原子時計が内蔵される状況もゼロではないありません。

2012-06-07 09:54:21
Kazunori Sato @kazunori_279

ふぅ。。- Spannerお勉強メモ - スティルハウスの書庫 http://t.co/xBWdznOu

2012-06-07 10:25:39
ICHIRO SATOH @ichiro_satoh

分散システム系のLinearizabilityについては、G.Coulouris他のDistributed Systemsの説明が一番まとまっている(続きあり)

2012-06-07 11:11:27
ICHIRO SATOH @ichiro_satoh

続き。逆にTanenbaumの教科書Distributed Systemsは改訂版ではLinearizabilityの説明が省略。実は分散システムの授業のスライドが旧版にあわせていたので、気が付いたのですが、意外感はありましたね。

2012-06-07 11:14:51
Kazunori Sato @kazunori_279

@ichiro_satoh ですね。探したのですがなかった。。

2012-06-07 11:26:50
Masayoshi Hagiwara @masayh

素朴な疑問だけどGPSクロックって衛星の冗長構成に依存しているという点では、ZooKeeperやPaxosのアクセプターと同様に、そこの障害が重要となるということ。将来のテロの目標になりそう。

2012-06-07 11:35:40
Kazunori Sato @kazunori_279

原子時計でバックアップしてるとはいえ、すべてをGPSのタイムスタンプに依存した作りにするとGPSがSPoFになるような。。

2012-06-07 11:35:56
Masayoshi Hagiwara @masayh

いや、GPSはSPOFにはならないと思います、システムとしては。ただし、Azureでの閏年の問題のようにクラウドでは時刻はSPOFです。なぜなら、空間分割するというreplicationが使えないからです。

2012-06-07 11:42:29
Masayoshi Hagiwara @masayh

あと、serializablilityとserializableは全然意味が違います。前者はコンカレンシー制御が正しいかどうかを検証するためのルールで、後者はisolationレベルの1つの強い選択肢。

2012-06-07 11:44:10
Kazunori Sato @kazunori_279

@masayh 時刻のシステムそのものに何らかの想定外の事象が発生すると、全体が一斉にダウンする。。という意味でしょうか?

2012-06-07 11:44:22
Masayoshi Hagiwara @masayh

あと、serializabilityとserializableは全然意味が違います。前者はコンカレンシー制御が正しいかどうかを検証するためのルールで、後者はisolationレベルの1つの強い選択肢。

2012-06-07 11:44:52
Masayoshi Hagiwara @masayh

はい、時刻は1次元なので、共有するしかないのです。@kazunori_279 時刻のシステムそのものに何らかの想定外の事象が発生すると、全体が一斉にダウンする。。という意味でしょうか?

2012-06-07 11:45:32
Masayoshi Hagiwara @masayh

タイムスタンプとい形で過去の時刻をコピーすることはできても、リアルタイムに進行する、クロックそのもののコピーはできないということです。これは情報伝達は光速を超えられないことからで、クラウドでの超えられないSPOFです。

2012-06-07 11:47:44
Masayoshi Hagiwara @masayh

atomicity、asynchronous、linearizabilityいずれも分散システムとその他の分野では意味が違います。2重の意味を持っているので注意。

2012-06-07 12:05:28
Masayoshi Hagiwara @masayh

CAP定理のconsistencyに誤解が生じるのもこの用語の意味の違いから。あ、availabilityも微妙に違うし、dependableという用語も意味が広くて....

2012-06-07 12:07:14
Masayoshi Hagiwara @masayh

consistency、durabilityも違いがある。なんなんだろうな、この用語の使い分けは。

2012-06-07 12:07:50
Masayoshi Hagiwara @masayh

replicationもDBと分散システムでは違う。ああ。。すごい

2012-06-07 12:09:14