CubicLouve

Spring_MTの技術ブログ

線形合同法(Linear congruential method)のスペクトル検定による可視化

線形合同法擬似乱数生成器の一つ

\displaystyle{
X_{n+1} = (A \times X_{n} + C)  \bmod M
}

ここでのA(乗数) C(増分) M(法)は定数で、AとCはMより小さい数を選ぶ。

このA C Mの選び方によって周期性は変わる。

どういう選び方すればをいいかは下記本を参照ください。

線形合同法で生成された数列がどれくらい乱雑かを判定する方法の一つにスペクトル検定がある。

今回は三次元でこれをグラフにしてみた。

Rubyのrandはメルセンヌ・ツイスタなので、それと線形合同法で生成した乱数の分布を比べてみる。

docs.ruby-lang.org

docs.ruby-lang.org

適当なスクリプトを書いて可視化した結果が下記の図となる。

可視化にはGR.rbを利用している。

github.com

  • 線形合同法(A(乗数)を137、C(増分)を187、M(法)を256にしているので規則性がわざと出やすくしている)

こう見ても今回のパラメータの線形合同法の結果は乱雑さがない感じがする。

参考資料

ja.wikipedia.org

http://www.math.sci.hiroshima-u.ac.jp/m-mat/TEACH/ichimura-sho-koen.pdf

tsujimotter.hatenablog.com

バイナリファイルを見る方法

白く塗りつぶした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の使い方まとめてみた

github.com

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 ファイルの種別、例) IPv4IPv4 socket、LINK は symbolic link fileとか
DEVICE バイス番号
SIZE/OFF ファイルサイズまたはオフセット、0t または 0xで始まる場合はオフセット
NODE ファイルのノード番号 だったりインターネットプロトコルだったりする
NAME ファイル名だったりマウントポイント名だったり
リモートアドレス(<net>:[<node>:]<port> とそれに続いて接続状態も表示される場合もある ) だったりする

オプション

lsof(8) - Linux manual page

オプション 説明
-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 は自動的にそれを読み込んでくれる。

設定可能な環境変数は下記を参照

github.com

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です。

www.spring8.or.jp

ja.wikipedia.org

xtech.nikkei.com

NTP

NTP は、正確な運針をもつ NTP サーバに一致させ、その後時刻を一定の誤差範囲内で維持する仕組みになっています。

つまり、NTP サーバの時刻変更に対して、NTP クライアントの時刻がこれに同期するというものではありません。

NTP プロトコルは、下記 3つで構成されています。

  • リファレンスクロック(stratum 0) : 原子時計GPS電波時計などを使った精度の高い外部時計をもったサーバー
  • NTP サーバ(stratum 1〜) : 信頼できる上位サーバから提供される時刻を利用して自分の時刻を保持し、他のマシンあるいは下位のサーバに時刻を提供する
  • NTP クライアント : NTP サーバから時刻を提供される

NTPはネットワークを介して時刻同期を行います。

単純に相手のサーバが通知してきた時刻を信頼するだけでは、 ネットワークの遅延により時刻のずれが発生してしまいます。

そのため、NTPではサーバ・クライアント間の通信において、 NTPメッセージを送信した時刻、受信した時刻を、 サーバ・クライアントそれぞれがメッセージの中に含めており、これらを使ってネットワークでの遅延時間を推測し、ずれの少ない時刻同期を図っています。

en.wikipedia.org

下記シーケンスを元に考えてみます。

f:id:Spring_MT:20210520162421p:plain

クライアントとサーバーは時刻はずれているとします。

パケットの往復時間(ラウンドトリップ)Δは下記になります。

Δ = (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クライアントの時刻を調整します。

参照

www.infraexpert.com

www.nic.ad.jp

ja.wikipedia.org

その他の時刻同期の仕組み

NTP以外にも時刻同期をする仕組みはあります。

その一つにBerkeleyアルゴリズムを用いるものがあります。

NTPはクライアントが定期的にNTPサーバー(タイムサーバー)に通信して時刻を同期しているのに対して、Berkeleyアルゴリズムではタイムサーバーが全てのマシンに対して定期的にポーリングし、応答に基づいてメッセージの往復時間を計算し、現在の時間を平均化し、ローカルクロックを調整する必要があることをクライアントに通知します。

ja.wikipedia.org

論理クロック

クロックスキューの問題などで、物理クロックの完全な同期は現実的には難しいです。

しかし、例えばシステム中のイベントのタイムラインにおいて、イベントの相対順序を決めるためには時刻の絶対値は必ずしも必要ありません。

イベント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参照)

  1. aとbが同じプロセスのイベントで、bの前にaがくる(aがbよりも先に起こる)場合、a → bとなる。
  2. aがあるプロセスによるメッセージの送信であり、bが他の別のプロセスによる同じメッセージの受信であるならば、a → b (これはaがbに因果関係がある)
  3. 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 はすべてのプロセスが合意する時間の数値を割り当てる

その上で、この論理クロックがイベントの発生する順序に基づいて正しく振る舞うための条件は、 あるイベント 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つの条件を満たすことになります。

これらの条件を満たす実装のルールは下記の通りです。

  1. 各プロセス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> に割り当てることで分散した環境での論理クロックが構築できます。

参照

medium.com

ieeexplore.ieee.org

www.distributed-systems.net CHAPTER6. COORDINATIONあたり

www.slideshare.net

  • データ指向アプリケーションデザイン p377あたり

他にも参考にした文献

www.spring8.or.jp

ja.wikipedia.org

xtech.nikkei.com

uchan.hateblo.jp

Tail Latencyについて

research.google

この論文では、大規模な分散システムでは、まれなパフォーマンスの低下であっても、全リクエストのかなりの部分に影響を与えるとあります。

つまり大規模な分散システムではテールレイテンシの影響が大きくなります。

テールレイテンシは大きなパーセンタイルのレスポンス値のことです。(大きいというのが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 と呼ばれています。

en.wikipedia.org

(この 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の大規模ファンアウト検索システムのすべてのリクエストに使用される傾向があります。

ほかでの応用

spring-mt.hatenablog.com

パフォーマンスの変動の対応についてはAuroraにも応用されていることが言及されています。

これらを踏まえて

テールレイテンシへの対応を見ていると、これらを担うコンポーネントはサービスメッシュだよなあと思っています。

Hedge requestなどはenvoyでも実装がありそうです。

www.envoyproxy.io

github.com

github.com

マイクロパーティションのロードバランシング、カナリアなどもサービスメッシュが担う部分かと思います。

また、サーバーの切り離し、シャドーリクエストなどもサービスメッシュの範疇かなと思います。

参照

agnozingdays.hatenablog.com

https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/44875.pdf

qiita.com

gihyo.jp

medium.com

https://drkp.net/papers/latency-socc14.pdf

https://pdfs.semanticscholar.org/dede/f157ad3b5b4df21a6515b1b70ed8ad698422.pdf