分散システムにおけるイベントの前後関係と論理時計・ベクトル時計について
分散システムでは時刻同期はとらずに順序同期だけをとっている、という話はよく聞きます。順序同期とはいったいどのような仕組みなのでしょうか
前提
- 各ノード間の処理の順序を適正に処理したい。
- 個々のサーバーが原子時計などの十分に正確な時計を持っていることを前提としない
- 時刻の責任を持つノード(FTPや電波時計)のある仕組みは順序同期のためには使えない(ミリ秒単位の誤差が発生するため)
前後関係とは
プロセスローカルでの順序と送受信イベントからの推移測で導かれる順序のことを前後関係といいます。 前後関係には以下のルールがあります。
(ルールH1)同一プロセス上でおこなわれたイベントeとe'に対して、eがe'の後に行われていればe→e'が成り立つ
(ルールH2)eがメッセージmの送信イベント、e'がmの受信イベントであればe→e'が成立する
(ルールH3)e→e'、e'→e''ならば、e→e''
これらのルールから察する通り、すべてのイベント間の前後関係を定義できるわけではありません。 特に、本記事で紹介するアルゴリズムでは通信が行われていないノード間ではそれぞれのイベントがどちらが先に起こったか類推することはできません。
なおここで定義した前後関係は以下の特性があるため、半順序(Partial order)になります。
- 満たしている:推移律(定義より自明)、反射率(自分自身と同値な関係)、反対象律(相違な2要素の同値な関係がない)
- 満たしていない:完全律(比較できない相違な2要素がある)
比較できない関係を「平行である」といいます。例えば下記の例だと
- b1→b2(ルールH1)
- a1→b1(ルールH2)
- c1→b2(ルールH2)
- a1→b2(ルールH3)
という前後関係を導出することができますが、 a1とc1に関しては前後関係の比較ができません。
論理時計
前後関係を実現する実装として「論理時計」というものがあります。 前後関係を定義したルール通通りそのまま実装すると、順序関係の保存と推移の計算などでパフォーマンス上あまり効率的ではありません。ローカルなイベント発生時のカウンタインクリメントと送受信イベント時のカウンターの比較・マージによって効率よくルールH1,H2,H3を満たす実装が論理時計です。
論理時計は以下のルールに沿って動作します
(ルールC1) 各プロセスは初期状態において、時計の時刻t=0である
(ルールC2) 受信以外のイベントeを行うときに、時計の時刻を1増やす
(ルールC3) メッセージ送信イベントeを行うときには、送信イベントeの発生時刻t(e)をメッセージに付加して送る
(ルールC4) メッセージ受信イベントeを行うときには、受信したメッセージに付加された時刻をt'とすると、t←max(t,t')+1として、この値をイベントeの発生時刻t(e)とする
論理時計を使うことで以下のことがわかります。
イベントeとe'でe→e'ならt(e)<t(e')
逆は成り立ちません。t(e)<t(e')ならe→e'ということは言えません。
たとえば下記の図だとt(a1)<t(c2)ですが、a1→c2ではありません。
ベクトル時計
論理時計より強力なベクトルクロックでt(e)<t(e')ならe→e'を成り立たせることができます。
プロセス数n,iэ{1,2,...n}の時ベクトル時計では各プロセスPiがベクトル時計Vi=(v1,v2,...vn)を持ちます。
ベクトル時計は以下のルールV1~V4で実現できます
(V1)各プロセスは初期状態において、ベクトル時計の時刻V=(0,0,...,0)である。
(V2) プロセスPiは受信以外のイベントeを行うときに、ベクトル時計の時刻V=(v1,v2,...,vn)にたいして、vi←vi + 1を行ったV'にベクトル時計の値をへんこうし、この値V'をイベントeの発生時刻V(e)とする
(V3) メッセージ送信イベントeを行うときには、送信イベントeの発生時刻V(e)をメッセージに付加して送る
(V4) プロセスPiがメッセージ受信イベントeを行うときには、受信したメッセージにふかされた時刻をV'=(v1',v2',...,vn')とすると、vj←max(vj,vj')(1<=j<=n)を実行し、さらにvi ← vi + 1を行った値にベクトル時計のアタを変更し、この時刻をイベントeの発生時刻V(e)とする
以下はこのベクトル時計Vを使う例です。ベクトル時計を青字で、論理時計を赤時で引き続き示しています。
- V(b2)=(1,2,2)とV(c2)=(0,0,2)ではV(c2)<V(b2)の大小関係があるのでc2→b2の前後関係があることがわかります。
- V(a1)=(1,0,0)とV(c2)=(0,0,2)には大小関係がありませんので、a1とc2が並行であることがわかります。
この記事は「分散システム(情報工学レクチャーシリーズ)」の第2章 時刻と時計の個人的まとめです。
- 作者: 真鍋義文
- 出版社/メーカー: 森北出版
- 発売日: 2013/09/14
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
Linuxのパフォーマンス計測ツールの違いとか
詳解システムパフォーマンス4章で学んだことや、直近で利用したツール等のざっくりしたまとめ。引用はすべて詳解システムパフォーマンスの４章のもの。
カウンタタイプ
カーネルは、イベントの回数を数えたカウンタ( counter )と呼ばれるさまざまな統計を管理し ている。
カウンタはデフォルトで有効になっており、カーネルによって継続的にメンテナンスされている ので、 「タダ」で使えると考えてよい。カウンタを使うときの唯一の追加コストは、ユーザーラン ドからの値の読み出しである(無視できる)。
カーネルはIOやCPU利用の実績を/sysや/proc配下のファイルに書き込んでいる。これは標準でデフォルトになっているため、読み出しコストのみで参照することができる。多くのXstat系のツールはこの形式になっている。
カウンタタイプのツールとしては
- vmstat
- iostat
- sar
などがある。個人的にはdstatというstat族のキメラ的なツールがあるでそちらを利用している。
トレーサタイプ
イベントごとのデータを集めてくるツールのこと。システムコール、ネットワークパケット、ディスクIOなどのイベント発生時の情報を収集します。頻度の高いイベントを対象にすると観測自体に負荷が高いため、それを考慮に入れること。またパフォーマンスの都合上、デフォルトで無効にされているものもあるため、利用した後は無効にするなどしてもとに戻すこと。
トレーシングはデータをキャプチャするために CPU にオーバーヘッドをかけ、保存のためにかなりの量のストレージを必要とすることがあるため、一般にデフォルトでは有効にされていない。
- ftrace カーネルトレーサ。呼び出しているカーネルのコードのスタックや引数などをトレースできる。
- gdb デバッガ。ソースコードや機械語の特定の行でのトレースを行う
- strace プロセスのシステムコール・シグナルをトレースする
プロファイラ
ある実行バイナリに異常な時間がかかっているというときはコンパイルでデバッグオプションでビルドした後、gprofで処理に時間がかかっている関数を調べることができる。
参考:gprofの使い方 https://minus9d.hatenablog.com/entry/20140112/1389502918
他:timeコマンドのvオプション
timeコマンドだけでもioの回数やswappingの発生、rssなどがわかる。
参考:https://kuenishi.hatenadiary.jp/entry/2016/11/02/131046
上記の重厚な？ツール群を試す前に/usr/bin/time -vを使ってみるのもいいかもしれない。
詳解システムパフォーマンスおすすめです。
青汁を一週間飲み続けました
近所の世間話がきっかけで青汁やさんの回数券を買ってほぼ毎日飲むという謎ムーブをかましました。
今週は毎日青汁飲もうと思います。🤗 pic.twitter.com/sml0PHMz6R
— yuYabu☕️ (@yuyabu2) 2019年2月10日
今週は100mlの回数券を買って平常時は100ml、たまに2枚使って200mlを飲むという感じでほぼ毎日飲めました*1。
効果はあったのか
今現在身体的に特に効果は出ていません。若干乾燥が改善したくらい*2。
私は成人男性にしては野菜を食べている方だと思うので、おそらく野菜不足を解消することによって発動する効果は現れないと思います。しかしケールの絞り汁を日常的に摂取した経験はないためケール固有の効果は出るかもしれません。
個人的な生活習慣の問題はコンビニ飯やジャンクフードが多いことと運動不足なので、そちらの改善を計画的に行わないと青汁を飲む意味がないような気がします。
気づいたこと
トッピングせずに青汁を飲む人はどうも少数派のようです。 飲んでいる青汁はいままで飲んだことのないようなハードコアな味がします。 他のお客さんもだいたいゴマ、はちみつ、リンゴ酢などを入れて飲みやすくしている人が多い印象です。私も初日は鼻をつまんで無理やり流し込むというスタイルで飲んでいましたが、いまは慣れたので普通に飲めています。
今後
回数券の量を100mlから200mlに増やして日常的に200ml飲むように変えて様子を見ようと思います。あと、豆腐屋さんが作っている豆乳もいいらしいのでそちらも試すかもしれません。
virtualbox でホスト(mac)とゲスト(ubuntu)のclipbordの共有がうまくいかない(解決)
色々生産性が悪いので調査した。
バージョン
- 仮想化ソフト:Virtualbox 5.2.22
- ゲスト:ubuntu 18.04
- ホスト:macOS Mojave 10.14.1
巷ではVirtualboxの設定>一般>高度の「クリップボードの共有」を「双方向」にすることで解決するという記事が多いが、 それだけでは解決しなかった。追加でVM側にVBoxClientを導入することで解決した。
yy@yy-VirtualBox:~$ sudo apt-get install virtualbox-guest-x11 yy@yy-VirtualBox:~$ sudo VBoxClient --clipboard
早速ターミナルで試してみた所、Ctrl + vが使えなくて調べた結果。。。
ターミナルではCtrl + Shift + Vが貼り付けらしい。
https://askubuntu.com/questions/202459/keyboard-shortcut-for-pasting-on-the-gnome-terminal
「チョコレートの世界史」を読んだ
バレンタインデー記念エントリー。ちょうど時期が良いので昔読んだ本の感想を投下。
チョコレートの世界史―近代ヨーロッパが磨き上げた褐色の宝石 (中公新書)
- 作者: 武田尚子
- 出版社/メーカー: 中央公論新社
- 発売日: 2010/12/01
- メディア: 単行本
- 購入: 1人 クリック: 28回
- この商品を含むブログ (26件) を見る
感想
若干ネタバレになりますが、本書は某大学のロウントリー社(オリジナルのキットカットを製造した会社)の資料コーナーを著者が訪れたことが原点にあるらしいので若干ロウントリー社贔屓な歴史書になっている。
チョコレートは以外と歴史が浅く、特に今の固形のものが食されるようになってからまだ200年も建っていない。本書には中南米がスペインに侵略されてからカカオを加工する技術がヨーロッパ諸国で発展してキットカットが出来上がる歴史が書かれている。
個人的にはチョコレートの成分とかが詳しく書かれているところが分かりやすかった。カカオポッド、カカオパウダー、カカオバター、カカオマス、カカオニブの違いは全くわからなかったけど、本書で理解した。
ノート
チョコレートの品種は結構コーヒーに似てる
カカオ豆には、ポリフェノールの含有量が異なる三種類の系統がある。クリオロ種、フォラステロ種、トリニタリオ種という。
クリオロ種でビター系のチョコレートを作ると、抜群の味になる。クリオロ種は生の豆を食べても美味に感じるという。しかし、病気に弱いため、栽培が難しい。稀少品種で、現在世界で生産されているカカオ豆の一％程度の生産量にすぎない。フォラステロ種は、ポリフェノールを多く含む。栽培が容易な強い品種で、世界の生産量の約八五～九○％を占める。味にパンチはあるが、苦味が強い。そのままでは、ビター系のチョコレートには向かない。
コーヒーも似た感じでアラビカ種とロブスタ種があり、
- 美味しいけど病気に弱く量が取れないアラビカ
- 味は劣るけど病気に強くで量が取れるロブスタ
という風になっている。この種構成に関して、コーヒーと比べた時のチョコレートの特筆点は美味しい方(クリオロ)が極端に出回っていない、という点だと思う。
コーヒーはアラビカ種の方が消費量が多い*1。私個人の経験でもロブスタ100%のコーヒーは飲んだ覚えがない。逆にチョコレートに関してはこの本を読むまでクリオロ種のものは食べたことがなかった。
お店で買えるクリオロ種チョコレート
市販されているものの中で安いクリオロ種のものはカルディに売ってあったペルー産の板チョコがあった。こちらはカカオ分の高いブラックチョコレートだが、評判通りブラックチョコレートでも美味しく、他のものによくある強い苦味がなく美味しく食べられた。値段も安かったのでおすすめ。ちょっと前流行ったbean to barのチョコレートは高すぎる(板チョコ1枚くらいの量で数千円)ので個人的に日用するのは無理。
チョコレートの製造方法とかややこしい成分とか
- カカオポッドからカカオ豆を取り出す
- カカオ豆を砕きカカオニブ(胚乳)を取り出す
- カカオニブをローストする
- カカオニブをすりつぶしてカカオマス(ドロドロ状のものを作る)
ここまでがチョコレートとココアパウダー製造の共通部分。ここからが工程が違っている。
ココアパウダー
チョコレート
一応チョコレートの作り方はここに色々応用があり、例えばホワイトチョコレートを作る際はカカオマスは使わずココアバターのみを使う。ここアバターの代わりに融点の高い油を使えば高音でも溶けにくいチョコレートになる。戦中は東南アジアや潜水艦内(熱がこもると40度を超える)内でも日本兵の食用に作っていた。ちなみにスーパーでみる殆どの普及品チョコレートはにはココアバターだけでなく植物性油脂も使われている。
商品分類(名称の分け方)
チョコレート分が多い順に
チョコレート>ミルクチョコレート>準チョコレート>準ミルクチョコレート
カカオ分35%以上かつココアバター18%以上がチョコレートを名乗れる
年表
- (~1521年まで)オルメカ文明/マヤ文明がクリオロ種をメインにカカオ崇拝(通貨としても利用)
- (1521年)滅亡したアステカ王国らへんを植民地にしたスペインがカカオを広め始める
- スペイン人がココアに砂糖を入れ出すようになってくる
- メキシコでカカオの消費量増加に伴いエルサルバドル、エクアドル、ベネズエラがフォラステロ種の産地として台頭
- 味の悪いフォラステロ種の増加によりカカオの価格が下落し、市民に普及
- (1660年頃)フランス人がカリブ海諸島(マルチニーク島)にカカオを持ち込んで栽培を始める。
- (1757年)トリニダード島(スペイン領後のイギリス領)でクリオロ種が病気のため壊滅。生き残ったクリオロとフォラステロ種を交配してトリニタリオ種が作られる。
- (1828年)ヴァン・ホーテン(オランダ)がココアパウダーを作る発明から特許を取得(カカオマスからここアバターを搾り取る技術)
- (1879年)アフリカ本土(ガーナ)にフォラステロ種が移植される
- (1847年)ブリストルでジョーゼフ・フライがカカオマスにここアバターを混ぜて固形チョコレートを初めて作る。
- (1849年)ココアパウダーに色々混ぜて売るのが流行る。その流れで粉末ミルクを混ぜたミルクココアが発明される
- (1876年)アンリ・ネスレ(スイス)がコンデンスミルクをチョコレートに混ぜてミルクチョコレートを発明する
- (1878年) 日本で初めてチョコレートが売られる@米津風月堂
- (1918年)日本で初めてチョコレートが製造される@田町by森永製菓
- (1935年)ロウントリー社キットカット販売開始。当初の商品名はチョコレート・クリスプ
- (1941年)原材料不足・価格統制などにより商品名をチョコレートクリスプからキットカットに変え、戦時中は青いラベルで売り始める
- (1958)ブリュッセル万博を機に家族経営小規模生産だったベルギーチョコレート(ノイハウス、ゴディバ等)が世界的に注目を浴びる
- (1988)ネスレがロウントリー社を買収。以後アメリカ以外ではネスレ社がキットカットを販売。アメリカではハーシー社が販売権保有。
戦時中の日本のチョコレート事情
- 1940年12月でカカオ豆の輸入ストップ
- 戦中は森永製菓が50人社員をインドネシアに派遣し、現地のカカオでチョコレートを作っていた
- 代用チョコレート
- 進駐軍が消費していたチョコレートはハーシー社*2のチョコレートといい、闇市に出回っているものや「ギブミーチョコレート」でもらえるやつはこれらしい。
余談:バレンタインデーに関する記載が一切ない
本書を「バレンタイン」で検索をかけても前書きで1単語だけ登場するだけで詳しい解説とかは一切なかった。 広告とかマーケティングの章は一応あるけど、チョコ業界的にバレンタインデーが成功したのは日本だけなのでしょうか。
「RDBMS解剖学 よくわかるリレーショナルデータベースの仕組み」を読んだ
結構古い本です。中古で書いましたが、多分新品はあまり出回っていないと思います。
この本を読んだ動機
- CC本(Bernstein本)やweikum本をいきなり読むのはきついので、RDBMS(自体の)入門書が読みたい
- DBのコンポーネントを特定製品に依存しない形式で理解したい
- 特定の製品に依存していないMVCCの日本語解説を読みたい
などを理由にこの本を読みました。
Concurrency Control and Recovery in Database Systems
- 作者: Philip A. Bernstein,Vassos Hadzilacos,Nathan Goodman
- 出版社/メーカー: Addison-Wesley
- 発売日: 1987/02/01
- メディア: ハードカバー
- この商品を含むブログを見る
- 作者: Gerhard Weikum,Gottfried Vossen
- 出版社/メーカー: Morgan Kaufmann
- 発売日: 2001/05/30
- メディア: Kindle版
- この商品を含むブログを見る
ノート
- SQLを解釈実行するパーツ
- データベースの構造を司るパーツ
- カタログ管理
- インデックス管理
- バッファ管理
- ストレージ管理
- 複数のアプリケーションからの要求や可溶性を司るパーツ
雑感
- プランには論理プランと物理プランの2種類がある
論理プラン
データベースの処理手順を「関係代数」の言葉で(厳密にはこれだけではないが)書き下したのが「論理プラン」である(p36)
物理プラン
論理プランをコンピュータ上の実行手順に書き換えたものを物理プランという(p36)
- 論理プランではSQLで書かれた内容を関係代数の操作に書き直す(和、差、共通、選択、射影、直積、結合)
物理プランでは結合アルゴリズム(nested loop/sort merge/hash join)を選んだりスキャン方式(index/table scan)を選ぶ
WAL(Write a head log)のメリットがわかりやすく書かれている。
Create tableで宣言したテーブル情報は一般に「カタログ情報」というらしい。これは知らなかった。
- 本書ではMVCCはMVTO (Multi Version Timestamp Ordering)のプロトコルを例に説明されている
微妙な点
- 記述が若干古い
- HDDが100GBの時代。
- もちろんSSDやOn memory DBなんてない
- JOIN構文がまだ存在していない
- FROM句にテーブルをカンマ区切りで列挙してWhere句に結合条件を書くスタイル
と、こんな感じです。RDBMSの内部に切り込んでかつ特定製品に依存しないような類書はあまり無いように思います。データベーススペシャリストの獲得を目指す方が副読本として読むのがいいのではないでしょうか。
RDBMS解剖学 よくわかるリレーショナルデータベースの仕組み (DB Magazine Selection)
- 作者: 鈴木幸市,藤塚勤也
- 出版社/メーカー: 翔泳社
- 発売日: 2005/02/22
- メディア: 単行本（ソフトカバー）
- 購入: 11人 クリック: 88回
- この商品を含むブログ (26件) を見る
