線形合同法(Linear congruential method)のスペクトル検定による可視化
ここでのA(乗数) C(増分) M(法)は定数で、AとCはMより小さい数を選ぶ。
このA C Mの選び方によって周期性は変わる。
どういう選び方すればをいいかは下記本を参照ください。
線形合同法で生成された数列がどれくらい乱雑かを判定する方法の一つにスペクトル検定がある。
今回は三次元でこれをグラフにしてみた。
Rubyのrandはメルセンヌ・ツイスタなので、それと線形合同法で生成した乱数の分布を比べてみる。
適当なスクリプトを書いて可視化した結果が下記の図となる。
可視化にはGR.rbを利用している。
- メルセンヌ・ツイスタ
- 線形合同法(A(乗数)を137、C(増分)を187、M(法)を256にしているので規則性がわざと出やすくしている)
こう見ても今回のパラメータの線形合同法の結果は乱雑さがない感じがする。
参考資料
http://www.math.sci.hiroshima-u.ac.jp/m-mat/TEACH/ichimura-sho-koen.pdf
バイナリファイルを見る方法
白く塗りつぶしたpngファイルの例でやってみる。
% convert -size 128x128 xc:white white.png
vimを使う場合
vim -b white.png
でバイナリモードでvimで開いた後に下記コマンドでバイナリダンプします。
:%!xxd
00000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452 .PNG........IHDR 00000010: 0000 0080 0000 0080 0100 0000 00eb 455c ..............E\ 00000020: 6600 0000 0467 414d 4100 00b1 8f0b fc61 f....gAMA......a 00000030: 0500 0000 2063 4852 4d00 007a 2600 0080 .... cHRM..z&... 00000040: 8400 00fa 0000 0080 e800 0075 3000 00ea ...........u0... 00000050: 6000 003a 9800 0017 709c ba51 3c00 0000 `..:....p..Q<... 00000060: 0262 4b47 4400 01dd 8a13 a400 0000 0774 .bKGD..........t 00000070: 494d 4507 e602 170e 1622 78a1 b740 0000 IME......"x..@.. 00000080: 001f 4944 4154 48c7 63f8 8f06 1846 0546 ..IDATH.c....F.F 00000090: 0546 0546 0546 0546 0546 0546 0568 2b00 .F.F.F.F.F.F.h+. 000000a0: 0004 a0f8 6a22 6527 5400 0000 2574 4558 ....j"e'T...%tEX 000000b0: 7464 6174 653a 6372 6561 7465 0032 3032 tdate:create.202 000000c0: 322d 3032 2d32 3354 3134 3a32 323a 3334 2-02-23T14:22:34 000000d0: 2b30 303a 3030 d063 4c5a 0000 0025 7445 +00:00.cLZ...%tE 000000e0: 5874 6461 7465 3a6d 6f64 6966 7900 3230 Xtdate:modify.20 000000f0: 3232 2d30 322d 3233 5431 343a 3232 3a33 22-02-23T14:22:3 00000100: 342b 3030 3a30 30a1 3ef4 e600 0000 0049 4+00:00.>......I 00000110: 454e 44ae 4260 82 END.B`.
ちなみにバイナリモードでファイルを開かないとバイナリ表示がおかしくなるので注意 下記はバイナリモードで開かなかった場合のバイナリダンプ
00000000: 3f50 4e47 0d0a 1a0a 0000 000d 4948 4452 ?PNG........IHDR 00000010: 0000 003f 0000 003f 0100 0000 003f 455c ...?...?.....?E\ 00000020: 6600 0000 0467 414d 4100 003f 3f0b 3f61 f....gAMA..??.?a 00000030: 0500 0000 2063 4852 4d00 007a 2600 003f .... cHRM..z&..? 00000040: 3f00 003f 0000 003f 3f00 0075 3000 003f ?..?...??..u0..? 00000050: 6000 003a 3f00 0017 703f 3f51 3c00 0000 `..:?...p??Q<... 00000060: 0262 4b47 4400 01dd 8a13 3f00 0000 0774 .bKGD.....?....t 00000070: 494d 4507 3f02 170e 1622 783f 3f40 0000 IME.?...."x??@.. 00000080: 001f 4944 4154 483f 633f 3f06 1846 0546 ..IDATH?c??..F.F 00000090: 0546 0546 0546 0546 0546 0546 0568 2b00 .F.F.F.F.F.F.h+. 000000a0: 0004 3f3f 6a22 6527 5400 0000 2574 4558 ..??j"e'T...%tEX 000000b0: 7464 6174 653a 6372 6561 7465 0032 3032 tdate:create.202 000000c0: 322d 3032 2d32 3354 3134 3a32 323a 3334 2-02-23T14:22:34 000000d0: 2b30 303a 3030 3f63 4c5a 0000 0025 7445 +00:00?cLZ...%tE 000000e0: 5874 6461 7465 3a6d 6f64 6966 7900 3230 Xtdate:modify.20 000000f0: 3232 2d30 322d 3233 5431 343a 3232 3a33 22-02-23T14:22:3 00000100: 342b 3030 3a30 303f 3e3f 3f00 0000 0049 4+00:00?>??....I 00000110: 454e 443f 4260 3f0a END?B`?.
hexdumpコマンドを使う場合
受け取ったデータを8進数や16進数でダンプする。(デフォルト16進数)
hexdumpはオプションなしでは、2バイト単位で処理し、リトルエンディアン(最下位のバイトから順番に表示)で表示します。
-C
オプションをつけることで1バイトずつ処理をする。
なので、基本 -C
オプションを付けて使う。
% hexdump -C white.png 00000000 89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 |.PNG........IHDR| 00000010 00 00 00 80 00 00 00 80 01 00 00 00 00 eb 45 5c |..............E\| 00000020 66 00 00 00 04 67 41 4d 41 00 00 b1 8f 0b fc 61 |f....gAMA......a| 00000030 05 00 00 00 20 63 48 52 4d 00 00 7a 26 00 00 80 |.... cHRM..z&...| 00000040 84 00 00 fa 00 00 00 80 e8 00 00 75 30 00 00 ea |...........u0...| 00000050 60 00 00 3a 98 00 00 17 70 9c ba 51 3c 00 00 00 |`..:....p..Q<...| 00000060 02 62 4b 47 44 00 01 dd 8a 13 a4 00 00 00 07 74 |.bKGD..........t| 00000070 49 4d 45 07 e6 02 17 0e 16 22 78 a1 b7 40 00 00 |IME......"x..@..| 00000080 00 1f 49 44 41 54 48 c7 63 f8 8f 06 18 46 05 46 |..IDATH.c....F.F| 00000090 05 46 05 46 05 46 05 46 05 46 05 46 05 68 2b 00 |.F.F.F.F.F.F.h+.| 000000a0 00 04 a0 f8 6a 22 65 27 54 00 00 00 25 74 45 58 |....j"e'T...%tEX| 000000b0 74 64 61 74 65 3a 63 72 65 61 74 65 00 32 30 32 |tdate:create.202| 000000c0 32 2d 30 32 2d 32 33 54 31 34 3a 32 32 3a 33 34 |2-02-23T14:22:34| 000000d0 2b 30 30 3a 30 30 d0 63 4c 5a 00 00 00 25 74 45 |+00:00.cLZ...%tE| 000000e0 58 74 64 61 74 65 3a 6d 6f 64 69 66 79 00 32 30 |Xtdate:modify.20| 000000f0 32 32 2d 30 32 2d 32 33 54 31 34 3a 32 32 3a 33 |22-02-23T14:22:3| 00000100 34 2b 30 30 3a 30 30 a1 3e f4 e6 00 00 00 00 49 |4+00:00.>......I| 00000110 45 4e 44 ae 42 60 82 |END.B`.| 00000117
xxdコマンドを使う場合
ファイルを16進数でダンプする。 復元もできるのがポイント。
% xxd white.png 00000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452 .PNG........IHDR 00000010: 0000 0080 0000 0080 0100 0000 00eb 455c ..............E\ 00000020: 6600 0000 0467 414d 4100 00b1 8f0b fc61 f....gAMA......a 00000030: 0500 0000 2063 4852 4d00 007a 2600 0080 .... cHRM..z&... 00000040: 8400 00fa 0000 0080 e800 0075 3000 00ea ...........u0... 00000050: 6000 003a 9800 0017 709c ba51 3c00 0000 `..:....p..Q<... 00000060: 0262 4b47 4400 01dd 8a13 a400 0000 0774 .bKGD..........t 00000070: 494d 4507 e602 170e 1622 78a1 b740 0000 IME......"x..@.. 00000080: 001f 4944 4154 48c7 63f8 8f06 1846 0546 ..IDATH.c....F.F 00000090: 0546 0546 0546 0546 0546 0546 0568 2b00 .F.F.F.F.F.F.h+. 000000a0: 0004 a0f8 6a22 6527 5400 0000 2574 4558 ....j"e'T...%tEX 000000b0: 7464 6174 653a 6372 6561 7465 0032 3032 tdate:create.202 000000c0: 322d 3032 2d32 3354 3134 3a32 323a 3334 2-02-23T14:22:34 000000d0: 2b30 303a 3030 d063 4c5a 0000 0025 7445 +00:00.cLZ...%tE 000000e0: 5874 6461 7465 3a6d 6f64 6966 7900 3230 Xtdate:modify.20 000000f0: 3232 2d30 322d 3233 5431 343a 3232 3a33 22-02-23T14:22:3 00000100: 342b 3030 3a30 30a1 3ef4 e600 0000 0049 4+00:00.>......I 00000110: 454e 44ae 4260 82 END.B`.
xxd -r でdumpしたファイルから復元して新しいデータとして保存する
lsofの使い方まとめてみた
lsof
コマンドはプロセスがオープンしているファイルの一覧を表示します。
manには下記のように記載されている。
lsof - list open files
ファイルはディスク上のファイルだけでなく、ネットワークソケット、デバイスなども含まれるため、オープンしているファイルを調べることで、ネットワークのリッスンしているポート(待受ポート)などもわかりネットワーク周りの調査でもよく使うコマンド。
表示項目
項目 | 説明 |
---|---|
COMMAND | プロセス名(+c num で必要な文字数取れる) |
PID | プロセスID |
USER | 実行ユーザー |
FD | ファイルディスクリプター(それに続く英字1文字は r read access、w write access、u read and write access を指す) |
TYPE | ファイルの種別、例) IPv4 は IPv4 socket、LINK は symbolic link fileとか |
DEVICE | デバイス番号 |
SIZE/OFF | ファイルサイズまたはオフセット、0t または 0x で始まる場合はオフセット |
NODE | ファイルのノード番号 だったりインターネットプロトコルだったりする |
NAME | ファイル名だったりマウントポイント名だったり リモートアドレス( <net>:[<node>:]<port> とそれに続いて接続状態も表示される場合もある ) だったりする |
オプション
オプション | 説明 |
---|---|
-n |
名前解決をせずにIPアドレスを表示する。名前解決をしないので高速に表示されます |
-P |
ポート番号をポート名に変換しない。 例) 443 ポートを https に変換しない |
+c |
プロセス名の表示数(15まで、0を指定すると最大になる) |
-i |
ネットワークファイルのみを対象とする。色々書き方があり、-iTCP だとTCPのみ、-i:ポート番号 で利用しているポートで絞り込める 形式は→ [46][protocol][@hostname|hostaddr][:service|port] |
-U |
Unix domain socketの一覧を取得する |
よく使うコマンド
UDP一覧
lsof -n -P +c 0 -iUDP
複数の特定ポート
lsof -n -P +c 0 -i:8080,3000
create-clusterコマンドを使ってローカルでredis clusterを簡単に作成する方法
redis の中に 含まれている create-cluster
コマンドを使うと、Redis Clusterを簡単にローカルで立てることができたのでそのメモ。
手順
redisをcloneしてくる
git clone git@github.com:redis/redis.git cd redis
redisをビルドする
make
自分の環境ではmacOSでビルドは通っている。
create-clusterコマンドがあるdirectoryまで移動
cd utils/create-cluster
必要であれば config.sh
を置いて環境変数を設定する
config.sh
というファイルがあるとcreate-cluster
は自動的にそれを読み込んでくれる。
設定可能な環境変数は下記を参照
BIN_PATHを設定すれば、任意のredis-cliコマンドの場所を指定できる。
redis clusterに必要なnodeを立てる
create-cluster start
を実行してnodeを作る
% ./create-cluster start Starting 30001 Starting 30002 Starting 30003 Starting 30004 Starting 30005 Starting 30006
作成したnodeをclusterにする
% ./create-cluster create >>> Performing hash slots allocation on 6 nodes... Master[0] -> Slots 0 - 5460 Master[1] -> Slots 5461 - 10922 Master[2] -> Slots 10923 - 16383 Adding replica 127.0.0.1:30005 to 127.0.0.1:30001 Adding replica 127.0.0.1:30006 to 127.0.0.1:30002 Adding replica 127.0.0.1:30004 to 127.0.0.1:30003 >>> Trying to optimize slaves allocation for anti-affinity [WARNING] Some slaves are in the same host as their master M: df85f1ae9a3ac6728d80db7e7545c036eefff225 127.0.0.1:30001 slots:[0-5460] (5461 slots) master M: c195571fa6c08fef6319591e71148817934f87b4 127.0.0.1:30002 slots:[5461-10922] (5462 slots) master M: 34a8974de69408ec6956834363392f3735cf6f96 127.0.0.1:30003 slots:[10923-16383] (5461 slots) master S: ca3c5200b2b57ea7242955024418df051a16609a 127.0.0.1:30004 replicates df85f1ae9a3ac6728d80db7e7545c036eefff225 S: 15aebd8d8d14bd3df30ee5ee3c72d02b75101d12 127.0.0.1:30005 replicates c195571fa6c08fef6319591e71148817934f87b4 S: 69f8274ef598072797ada3e2b7d458a50ebd4f62 127.0.0.1:30006 replicates 34a8974de69408ec6956834363392f3735cf6f96 Can I set the above configuration? (type 'yes' to accept): yes >>> Nodes configuration updated >>> Assign a different config epoch to each node >>> Sending CLUSTER MEET messages to join the cluster Waiting for the cluster to join >>> Performing Cluster Check (using node 127.0.0.1:30001) M: df85f1ae9a3ac6728d80db7e7545c036eefff225 127.0.0.1:30001 slots:[0-5460] (5461 slots) master 1 additional replica(s) S: 15aebd8d8d14bd3df30ee5ee3c72d02b75101d12 127.0.0.1:30005 slots: (0 slots) slave replicates c195571fa6c08fef6319591e71148817934f87b4 M: c195571fa6c08fef6319591e71148817934f87b4 127.0.0.1:30002 slots:[5461-10922] (5462 slots) master 1 additional replica(s) S: 69f8274ef598072797ada3e2b7d458a50ebd4f62 127.0.0.1:30006 slots: (0 slots) slave replicates 34a8974de69408ec6956834363392f3735cf6f96 S: ca3c5200b2b57ea7242955024418df051a16609a 127.0.0.1:30004 slots: (0 slots) slave replicates df85f1ae9a3ac6728d80db7e7545c036eefff225 M: 34a8974de69408ec6956834363392f3735cf6f96 127.0.0.1:30003 slots:[10923-16383] (5461 slots) master 1 additional replica(s) [OK] All nodes agree about slots configuration. >>> Check for open slots... >>> Check slots coverage... [OK] All 16384 slots covered.
[OK] All 16384 slots covered.
がでれば、clusterの作成が完了となる。
その他
ログの確認
% ./create-cluster tailall
クラスタを止める
% ./create-cluster stop
物理クロック 論理クロック
物理クロック
ほぼすべてのコンピューターには、内蔵されている水晶発振器によって時刻を計算しています。
水晶は安定した周波数の電気信号を発振するため、振動子として広く使われています。
パソコンの電源が切れたり、充電が切れたりしても、マザーボードに内蔵されているCMOSバッテリーにより水晶は時刻を計算し続けれます。
この水晶発振器は個体ごとに誤差があるため、異なるコンピューターでは全て同じ周波数で動作はしません。
(月で±15秒とか)
時刻同期
上記の通り、複数台のコンピューターがあると、徐々に時間はずれていき、読み出したときに異なる時刻を示すようになります。
これはclock skewと呼ばれます。
手動で時刻を合わせても発振器の誤差の影響などですぐに時刻がずれてしまうので、手動ではなく自動的にコンピュータの時刻同期ができれば、これらの問題を解決することができます。
これを実現するために用いられるのが時刻を同期させるプロトコルがNTPです。
NTP
NTP は、正確な運針をもつ NTP サーバに一致させ、その後時刻を一定の誤差範囲内で維持する仕組みになっています。
つまり、NTP サーバの時刻変更に対して、NTP クライアントの時刻がこれに同期するというものではありません。
NTP プロトコルは、下記 3つで構成されています。
- リファレンスクロック(stratum 0) : 原子時計やGPS、電波時計などを使った精度の高い外部時計をもったサーバー
- NTP サーバ(stratum 1〜) : 信頼できる上位サーバから提供される時刻を利用して自分の時刻を保持し、他のマシンあるいは下位のサーバに時刻を提供する
- NTP クライアント : NTP サーバから時刻を提供される
NTPはネットワークを介して時刻同期を行います。
単純に相手のサーバが通知してきた時刻を信頼するだけでは、 ネットワークの遅延により時刻のずれが発生してしまいます。
そのため、NTPではサーバ・クライアント間の通信において、 NTPメッセージを送信した時刻、受信した時刻を、 サーバ・クライアントそれぞれがメッセージの中に含めており、これらを使ってネットワークでの遅延時間を推測し、ずれの少ない時刻同期を図っています。
下記シーケンスを元に考えてみます。
クライアントとサーバーは時刻はずれているとします。
パケットの往復時間(ラウンドトリップ)Δは下記になります。
Δ = (Tc2- Tc1) - (Ts2 - Ts1)
また、時刻差(タイムオフセット) θ はNTPサーバーの時刻と往復時間の半分(パケットの片道は往復の1/2として固定している) と NTPクライアントの時刻の差となります。
θ = (Ts2 + Δ / 2) - Tc2 = Ts2 + ((Tc2- Tc1) - (Ts2 - Ts1)/2) - Tc2 = (Ts2 + Ts1) / 2 - (Tc2 + Tc2) / 2
θ に基づいてNTPクライアントの時刻を調整します。
参照
その他の時刻同期の仕組み
NTP以外にも時刻同期をする仕組みはあります。
その一つにBerkeleyアルゴリズムを用いるものがあります。
NTPはクライアントが定期的にNTPサーバー(タイムサーバー)に通信して時刻を同期しているのに対して、Berkeleyアルゴリズムではタイムサーバーが全てのマシンに対して定期的にポーリングし、応答に基づいてメッセージの往復時間を計算し、現在の時間を平均化し、ローカルクロックを調整する必要があることをクライアントに通知します。
論理クロック
クロックスキューの問題などで、物理クロックの完全な同期は現実的には難しいです。
しかし、例えばシステム中のイベントのタイムラインにおいて、イベントの相対順序を決めるためには時刻の絶対値は必ずしも必要ありません。
イベントAがイベントBの前に起こることを知る必要がある場合、Ta=2、Tb=6でも、Ta=4、Tb=10であっても、Ta < Tbが満たされていれば問題ありません。
このようなシチュエーションにおいてはインクリメントされるカウンタに基づいてイベントの順序付けを行うほうが安全性が高いです。
物理クロックではなく、インクリメントされるカウンタに基づくものを論理クロックと呼びます。
Lamportの論理クロック
Lamportの論文( https://www.microsoft.com/en-us/research/uploads/prod/2016/12/Time-Clocks-and-the-Ordering-of-Events-in-a-Distributed-System.pdf ) では、 クロックの同期は必要だが、絶対値的なものである必要はないことを示しました。
2つのプロセスが相互作用しない場合(並行な場合)、クロックを同期させる必要はなく同期していないことは観測できないため、問題にはならない、さらに通常重要なのは、すべてのプロセスが正確な時間に合意することではなく、イベントが発生する 順序 に合意することであると述べています。
論理クロックの同期のために、happens-before
関係を定義しています。
happens-before
関係 →
は 以下の3つの条件を満たしている最小の関係としています。(happens-before
は日本語では事前発生と訳されます。データ指向アプリケーションデザイン p 199参照)
- aとbが同じプロセスのイベントで、bの前にaがくる(aがbよりも先に起こる)場合、a → bとなる。
- aがあるプロセスによるメッセージの送信であり、bが他の別のプロセスによる同じメッセージの受信であるならば、a → b (これはaがbに因果関係がある)
- a → b、b → cならば、a → c
また、a ↛ b かつ b ↛ a で、aとbのイベントが異なるイベントは concurrent(並行) と呼びます。
つまり、a bのどちらも先に行われていない、互いに相手を知らないのであれば、これらは並行していることになります。
全てのイベントに対して、全てのプロセスが合意する時間の値、論理クロックを定義します。
ここでは、論理クロックは下記のように定義します。
- 各プロセスPiのクロックCiは、プロセス Piにおける任意のイベント a に番号
Ci<a>
を割り当てる関数である - このシステム全体としてのクロックは、任意のイベント a に数値
C<a>
を割り当てる関数 C とする。- bがPjというプロセスのイベントであれば、
C<b> = Cj<b>
となる つまり、C はすべてのプロセスが合意する時間の数値を割り当てる
- bがPjというプロセスのイベントであれば、
その上で、この論理クロックがイベントの発生する順序に基づいて正しく振る舞うための条件は、 あるイベント aが他のイベント bよりも先に発生した場合、a は b よりも早い時間に発生すべき ということになります。
これは、
イベントaとbにおいて、 a → b であれば C<a> < C<b>
となります。
これは 、前述の happens-beforeの関係を考えると、
- C1
プロセスPiのイベントaとbにおいて、aがbの前に発生した場合、 Ci<a> < Ci<b>
- C2
プロセスPiのメッセージ 送信 a で プロセスPjでのメッセージの受信 b の場合 Ci<a> < Cj<b>
の2つの条件を満たすことになります。
これらの条件を満たす実装のルールは下記の通りです。
各プロセスPiは連続する2つのイベントの間にCiを増加させる。つまりa → b であれば bのイベントの前にCiを増加させる
2-a.イベントaは プロセスPiで mというメッセージ送信のイベントだとすると、メッセージ m にはタイムスタンプ Tm = Ci <a> が含まれている
2-b.Piとは別のプロセスPjがメッセージ mを受信すると、PjはCjの値を現在の値以上かつ、Tmの値より大きい値をセットする
イベントaがプロセスPiで Ci<a>
に発生すると、システム全体の論理クロック C<a>
= Ci<a>
に割り当てることで分散した環境での論理クロックが構築できます。
参照
www.distributed-systems.net CHAPTER6. COORDINATIONあたり
www.slideshare.net
- データ指向アプリケーションデザイン p377あたり
他にも参考にした文献
Tail Latencyについて
この論文では、大規模な分散システムでは、まれなパフォーマンスの低下であっても、全リクエストのかなりの部分に影響を与えるとあります。
つまり大規模な分散システムではテールレイテンシの影響が大きくなります。
テールレイテンシは大きなパーセンタイルのレスポンス値のことです。(大きいというのがp99なのかp99.9なのかは文脈次第です)
パーセンタイルの例としては、99 パーセンタイルのレスポンスタイムが 100 msとすると、平均して 100 リクエスト中の 99リクエストには 100 ms未満しかかからず、1 リクエストには 100 ms以上かかることを意味します。
例えば、各サーバが通常10msで応答し、99%のレイテンシーが1秒であるシステムを考えてみると、ユーザーのリクエストがそのようなサーバー1台だけで処理された場合、1/100の確率でユーザーのリクエストが遅く(1秒かかる)なります。
このサーバー群に対して、ユーザーのリクエストが100台のサーバーから並行してレスポンスを収集しなければならない場合、ユーザーのリクエストの63%が1秒以上かかることになります。
1台のサーバレベルで1秒以上の遅延が発生するのが1万件に1件のサービスであっても、そのようなサーバが2,000台あるサービスでは、5件に1件の割合(18%)で1秒以上の遅延が発生することになります。
これはテールレイテンシの増幅と呼ばれます。(データ指向アプリケーションデザインp 17のコラム参照)
Googleような大規模な分散システムではテールレイテンシが全体のパフォーマンスに大きく影響します。
マシンの共有リソースの競合( CPUとか )、バックグランド処理などいろいろな要因で高いテールレイテンシが発生します。
大規模システムにおいて、レイテンシの変動の要因をすべて排除することは現実的ではないですが、この論文では、突発的、一時的な遅延を隠蔽したり、回避するすることでテールレイテンシを改善する手法を紹介しています。
数十ミリ秒の時間スケールで動作するリクエスト内の即時応答での対応
多くのWebサービスでは、データアイテムの複数のレプリカを配置することで、スループットを向上させ、障害が発生しても可用性を維持しています。
この対応では、レプリカを使って、1つの高レベルのリクエスト内のレイテンシーの変動を抑えます。
Hedged Requests
遅延のばらつきを抑える簡単な方法は、 同じ リクエストを複数のレプリカに発行し、いずれかのレプリカが先に応答した結果を使用することです。
クライアントは、最初の結果を受け取ると、残りの未処理のリクエストをキャンセルします。
このようなリクエストは Hedged requests
と呼ばれています。
(この Hedged
は金融用語の意味での両掛けから引用していると思っています)
この技術をnaiveに実装すると、通常は許容できないほどの負荷が追加されますが、負荷の増加をわずかに抑えながら、ほとんどの遅延削減効果を得られる多くのバリエーションが存在します。
アプローチの1つに、最初のリクエストが、このクラスのリクエストに対する95パーセンタイルの予想待ち時間を超えて未処理になるまで、2番目のリクエストの送信を遅らせるというものがあります。
この方法では、追加の負荷を約5%に抑えつつ、レイテンシーテールを大幅に短縮することができます。
この技術が有効なのは、レイテンシーの原因が特定のリクエストに固有のものではなく、他のなんらかの形態の干渉によるものであることが多いためです。
論文内では、100台の異なるサーバに分散しているBigTableのテーブルに格納された 1000個のキーの値を読み取るGoogleベンチマークが紹介されていました。
10msの遅延後にヘッジ付きリクエストを送信すると、わずか2%のリクエスト数の増加で、1000個の値をすべて取得する際の 99.9%タイルの遅延が 1,800ms から 74msに短縮されたとありました。
Hedged requestsのオーバーヘッドは,プライマリリクエストよりも優先度の低いリクエストとしてタグ付けすることで,さらに低減することができます。
Tied Request
Hedged requests
には、複数のサーバが同じリクエストを不必要に実行してしまうという脆弱な側面があります。
この余分な作業はは上記で紹介したような方法で緩和はできますが、この方法ではメリットが得られるのはごく一部のリクエストに限られてしまいます。
適切なリソースの消費で Hedged requests
のより積極的な利用を可能にするには、リクエストをより速くキャンセルする必要があります。
一般的なレイテンシの変動要因は、リクエストが実行を開始する前のサーバでのキューイングの遅延です。
多くのサービスでは、リクエストが実際にスケジューリングされ、実行がはじまれば、その実行の完了時間のばらつきは大幅に減少します。
そこでGoogleでは、同時に複数のサーバにリクエストのコピーをエンキューし、サーバがこれらのコピーのステータスに関する更新情報を相互に通信できるようにしました。
サーバがサーバ間でステータスの更新を行うリクエストのことは Tied request
と呼ばれています。
Tied request
の最も単純な形式は、クライアントが2つの異なるサーバーにリクエストを送信し、それぞれのサーバーにもう一方のサーバーがタグ付けされます(結びつけられた tied)。
あるリクエストが実行を開始すると、そのリクエストは相手にキャンセルメッセージを送ります。 キャンセルメッセージに対応するリクエストは、もう一方のサーバーにまだキューが残っているときは、直ちに中止するか、大幅に優先順位を下げます。
Googleはこの手法をクラスタレベルの分散ファイルシステムに実装しており、中央値と末尾値の両方の遅延を減らすのに効果的であることを紹介しています。
その中では、サーバー間のキャンセルを行う Tied request
は、レイテンシーの中央値(50パーセンタイル)を16%削減し、レイテンシー分布の末尾に向かうにしたがって効果が増していき、99.9パーセンタイルのレイテンシーで40%近い削減を達成したとありました。
数十秒から数分の時間スケールで実行され、より長期的な現象の影響を隠すことを目的としたリクエストを跨いだ長期的な適応
多くのシステムでは、各パーティションのコストが等しくなるようにデータを分割しようとしますが、各マシンに単一のパーティションを静的に割り当てることは、下記から実際には十分ではありません。
- サーマルスロットリングや共有ワークロードの干渉などにより、ベースとなるマシンの性能は 時間軸上で均一でも一定でもありません。
- 分割したのアイテムの割り当てに外れ値があると、データによる負荷の不均衡が発生する可能性があります(特定のアイテムが注目され、そのパーティションの負荷が増加する、有名人対応みたいないこと)
マイクロパーテーション
不均衡に対処するために、Googleのシステムの多くは、サービス内のマシンの数よりも 多く のパーティションを生成し、これらのパーティションを特定のマシンに動的に割り当ててロードバランシングを行います。
ロードバランシングする側は、これらの小さなパーティションの1つをあるマシンから別のマシンに移すことに対しての責務があります。
選択的レプリケーション
マイクロパーティション方式の拡張機能として、負荷の不均衡を引き起こす可能性の高い特定のアイテムを検出、あるいは予測し、そのアイテムのレプリカを追加作成することができるようにします。
追加のレプリカを使用して、実際にマイクロパーティションを移動させることなく、これらのホットなマイクロパーティションの負荷を複数のマシンに分散させることができます。
遅延の原因の検定
中間サーバは、システム内の様々なマシンからの応答の遅延分布を観測し、特に遅いマシンを除外したり、検証を行うことでシステムのパフォーマンスが向上できる状況を検出することがあります。
遅延の原因は、無関係なネットワーク・トラフィックによる干渉や、そのマシン上の別のジョブのためのCPU動作の急増など一時的な現象であることが多く、システムの負荷が高いときに速度低下に気が付きやすいです。
システムの負荷が高いときであっても、システムはこれらの除外されたサーバーにシャドーリクエストを発行し続け、そのレイテンシーの統計を取り、問題が解決したときに再びサービスに組み込むことができるようにします。
大規模な情報検索(IR)システムでの対応
Good Enough (Not Best)
最良ではないわずかに不完全な("good-enough")結果で応答することで、エンド・ツー・エンドのレイテンシーが向上しユーザにとって最良のサービスとなる可能性があります。
カナリアリクエスト
ファンアウトが非常に大きいシステムで起こりうる一つの問題は、あるリクエストがテストされていないコードパスを実行してしまい、何千ものサーバで同時にクラッシュしたり、非常に長い遅延が発生したりすることです。
このような相関性のあるクラッシュシナリオを防ぐために、Googleの検索システムの一部では、カナリアリクエスト
と呼ばれる技術が採用されています。
これは、最初に何千ものリーフサーバにリクエストを送信するのではなく、ルートサーバがまず1つまたは2つのリーフサーバにリクエストを送信するというものです。
残りのサーバーは、ルートが適切な時間内にカナリアから成功した応答を得た場合にのみクエリが発行されるようになります。
カナリアリクエスト
の段階では,1台のサーバが応答するのを待たなければならないため,全体的な遅延はわずかであり,大規模なファンアウトリクエストに対してすべてのサーバが応答するのを待たなければならない場合に比べて,変動ははるかに小さくなります。
カナリアリクエスト
によってレイテンシーがわずかに増加するにもかかわらず、カナリアリクエスト
は安全性が高いため、Googleの大規模ファンアウト検索システムのすべてのリクエストに使用される傾向があります。
ほかでの応用
パフォーマンスの変動の対応についてはAuroraにも応用されていることが言及されています。
これらを踏まえて
テールレイテンシへの対応を見ていると、これらを担うコンポーネントはサービスメッシュだよなあと思っています。
Hedge requestなどはenvoyでも実装がありそうです。
マイクロパーティションのロードバランシング、カナリアなどもサービスメッシュが担う部分かと思います。
また、サーバーの切り離し、シャドーリクエストなどもサービスメッシュの範疇かなと思います。
参照
https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/44875.pdf
https://drkp.net/papers/latency-socc14.pdf
https://pdfs.semanticscholar.org/dede/f157ad3b5b4df21a6515b1b70ed8ad698422.pdf