読者です 読者をやめる 読者になる 読者になる

テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

Raft: Processing read-only queries more efficientlyの解説

引き続きRaft. Rustは書いていない. Rustを書く時間はすべてオーバーウォッチに捧げてしまった.

github.com

の6.4を説明する. Raftでreadを行う時はどう考えればいいか.

Read-only client commands only query the replicated state machine; they do not change it. Thus, it is natural to ask whether these queries can bypass the Raft log, whose purpose is to replicate changes to the servers’ state machines in the same order. Bypassing the log offers an attractive performance advantage: read-only queries are common in many applications, and the synchronous disk writes needed to append entries to the log are time-consuming.

Raftでは, State Machine (以下SM)に適用した時にクライアントにackする. だから, read queryは直接SMを読めばいいんじゃないの?と思うかも知れないけど, それはほとんどの場合正しいけど完全ではない.

For example, a leader might be partitioned from the rest of the cluster, and the rest of the cluster might have elected a new leader and committed new entries to the Raft log. If the partitioned leader responded to a read-only query without consulting the other servers, it would return stale results, which are not linearizable.

仮にそのleaderがネットワーク分断されていたらどうか?実は他にleaderがいて, たくさん新しいログが追加されていて, もっと先までackしているかも知れない. だとすると, 自分がackしたところを基準にしてread requestに応答するのはstale readとなる可能性がある. (これはネットワーク分断にかぎらず, 自分がしばらくstallしていた場合にも起こりうるはず. 起きた瞬間にread requestを受け取った場合)

This approach is more efficient than committing read-only queries as new entries in the log, since it avoids synchronous disk writes.

This approach(以下で説明するefficientなもの)はnaiveなアプローチより効率が良いとしている. naiveなアプローチとは, read requestも更新系と同様にコマンドとしてログに格納して, 適用順序についての合意に乗せるというやり方. 効率が良い理由は, logへの同期ライトを省けるから (だから, これが微小であればこの主張は嘘になる. 例えば不揮発メモリやSSDを使えば?)

This approachの考え方:

  1. 自分のログのうちcommitしたところまではSMに適用してからackしよう (このindexをreadIndexと呼んでいる)
  2. readIndexが全ノードの中で最新であることを保証しよう
  3. 全ノードで最新のreadIndexを適用したSMは最新だからstaleにならない!!!

そのために5つの手続きをする必要がある:

  1. leaderになった瞬間にnoopコマンドをコミットする: こうすることでleaderのcommitIndexはそのtermにおける全ノード中最大であることを保証出来る (これはread requestの実装うんぬんに関わらずleader safety propertyの確保に必要だからどのみち省けない)
  2. 今のcommitIndexをreadIndexとして記録する (これはtempなのでメモリでおk)
  3. ハートビートを飛ばして, majorityからackを得る: これは自分が本当にleaderであることを確かめるために行う
  4. SMにreadIndexまで適用する
  5. read requestに対してSMからのresponseを返す

To improve efficiency further, the leader can amortize the cost of confirming its leadership: it can use a single round of heartbeats for any number of read-only queries that it has accumulated.

明らかに重いのは, ハートビートを飛ばすところだ. しかしこれは最適化として, 複数のread requestをまとめて, それに対して1回のハートビートを飛ばすことでamortize出来ると言っている. しかし, おれの考えではこの考え方は都合が良すぎると思う. そして, ハートビートがamortize出来ないならば, このアプローチのどこがefficientなのだ?という話になってくる. あと, read requestが溜まるのを一定時間待つという自然な実装を考えると, readのレイテンシに影響する.

Followers could also help offload the processing of read-only queries. This would improve the system’s read throughput, and it would also divert load away from the leader, allowing the leader to process more read-write requests. However, these reads would also run the risk of returning stale data without additional precautions. For example, a partitioned follower might not receive any new log entries from the leader for long periods of time, or even if a follower received a heartbeat from a leader, that leader might itself be deposed and not yet know it. To serve reads safely, the follower could issue a request to the leader that just asked for a current readIndex (the leader would execute steps 1–3 above); the follower could then execute steps 4 and 5 on its own state machine for any number of accumulated read-only queries.

Raftではleaderがすべてのリクエストに応答することになっているが, writeはともかくreadはfollower(非leader)がoffloadした方が効率良いよねという考え方は出来る. しかしこれはもちろんstale readに繋がる. ここでは, leaderに3までを実行させて, readIndexを得た上で4,5はfollowerが実行するという解法が書かれている.

LogCabin implements the above algorithm on leaders, and it amortizes the cost of the heartbeats across multiple read-only queries under high load. Followers in LogCabin do not currently serve read-only requests.

しかし彼がRaftのアプリケーションとして作ったLogCabinではfollowerからのreadは実装していないとのこと. (つまりアイデアのみ. もちろん, うまく行きそうではあるけど)

まとめ

readを実装する時はstale readに注意しよう. その上で性能要件なども考えて, 実装方式を決定しよう.

Overwatch: 回線状況が悪いやつはランクマをやるな

jp.automaton.am

昨日まさにこれが起きた. おれは今, フレンドと一緒にランクマをやっている. 社会人から中学生まで色々いるが, 集まりもよく, 向上心もまぁまぁあるため楽しくやれていると思う.

このチームで問題が起きたことは先日述べた. これは意図的なランクマ落ち.

akiradeveloper.hatenadiary.com

また問題が起きた. 同じメンバが今度は回線落ちしたのだ. そしてその問題はさらに悪くなる. 他のメンバが「回線が悪いのはしょうがないことだ」と言い出したのだ. おれはそうは思わなかった. その場合, PS4を無線接続していることが明らかな原因だったし, LAN接続すれば済むだけの問題だった. 「その程度を改善をすることはランクマをする上で義務だ」とも言った. しかしなぜかチームはおれの意見にはなびかなかった. 回線が悪いことはしょうがないことであって, 子供にはどうしようもないことだと言い出した.

おれはやっぱりそうは思わない. その意見には同意出来ない. リンクの記事で公式が述べているように, 回線状況が悪い場合にはランクマへの参加は控えるべきなのだ. 回線状況は免罪符には全くならない.

ランクマはレートを賭けている. もしレートを賭けたくないならばクイックマッチに行けばいいし, 実際にクイックマッチでもオーバーウォッチは十分に楽しめる. レートを賭けて勝ちにこだわった"ひりつく"勝負がしたいという人だけがランクマに参加すればよく, 回線不良を許容する発言などはもってのほかだ.

ランクマのレートというのがどれほど重要なものかというと, おれはお金と等価だと考えている. 具体的には, 1ポイントに対して100円払っても惜しくない人はおれを含めて結構いるだろうし(ゲームを楽しむために10万円くらい課金することは大人ならばふつうだ), 1000円でも払っていいと考えているお金持ちはふつうにいると思う. だから, 一回負けて何十ポイントか失うことは何千円か失うことと等しく, これはレートとしてはギャンブルと変わりない.

一方で競馬や麻雀などギャンブルは, 賭けなくても楽しむことは出来る. おれは今は馬券は買わないが, 競馬実況を見るだけでも面白いなとは感じるし, ネットの馬柱を見て予想をして当たったらそれはそれで面白いなとも思う. この面白さは, 何万円もの馬券を買った場合とはベクトルが全く異なるものだ.

オーバーウォッチは親切なことに, そういう純粋な楽しさを追求したい人にはクイックマッチを提供しているし, 回線が悪いとか, あるいは自分の好きなキャラクターをやりたいと思ってる人はもれなくクイックマッチしかやらないでほしい.

ランクマではチームが勝つことが最優先であり, 自分の楽しみは二の次だ. これは馬券でいうと, 馬券を当てること(あるいは儲けること)が最優先であって, 好きな馬好きな騎手を応援することは二の次ということと同じだ. おれはチームにとって火力が必要だと思うからソルジャーなどのDPSをピックしているし, エイムが良いから成果を出し続けている. でも実は一番好きなのはトレーサーで, クイックマッチではトレーサーを良く使う. ランクマでも本当はトレーサーを使いたいが, もっとも安定して活躍出来るソルジャーを好きでもないのに使っているのだ. ソルジャーが好きという人なんかいるわけないよな, 退屈なキャラクターだから.

Raft: Membership Changeのシンプルなアルゴリズム

Raftは理解と実装の容易性に重きを置いた合意アルゴリズムだ. 合意アルゴリズムは複数のサーバが何か1つの値について合意するために使われる. このアルゴリズムは2014年に発表された. PFIがSlideを作ってくれているからこれを読めば大体は分かる. しかしもっと詳しく知りたい人は論文を読むしかない. Raft自体の説明はここでは省く.

www.slideshare.net

上のスライドはIn search of an understandable consensus algorithmという学会論文に基いて調査されているけど, 博士論文の方にはさらに詳しく書かれている.

github.com

おれはRaftの調査のため今これを読んでいる. 読んでおれが理解するだけではもったいないから, みんなに知識を共有する.

Most membership change algorithms introduce additional mechanism to deal with such prob- lems. This is what we did for Raft initially, but we later discovered a simpler approach, which is to disallow membership changes that could result in disjoint majorities. Thus, Raft restricts the types of changes that are allowed: only one server can be added or removed from the cluster at a time.

Raftでクラスタの構成を変更(Membership Changeという)する時, 問題は2つのリーダーが選出されてしまうことを避けることだ. この解決のために, いかなるクラスタ構成 (C_old)から別のクラスタ構成(C_new)に変更しようとも, あらゆる合意(リーダー選出含む)が1つしかされないこと保証するために著者が最初に考えていたことは, C_oldとC_newの両方から合意をとらないといけない厳しい中間状態を経るというアイデアで, Joint Consensusと呼ばれている.

This joint consensus approach is more complex than the single-server changes precisely because it requires transitioning to and from an intermediate configuration. Joint configurations also require changes to how all voting and commitment decisions are made; instead of simply counting servers, the leader must check if the servers form a majority of the old cluster and also form a majority of the new cluster. Implementing this required finding and changing about six comparisons in our Raft implementation

しかしよくよく考えてみると, そんな柔軟なクラスタ変更は実際には要らない上に, 実装しようとすると様々な問題を生むことが分かった. そこで, もっとシンプルに1台ずつの追加・削除に限定してみたらどうなるか?と考えてみたら, 全く安全であることに気づいた. 任意の変更も, 1台ずつの変更の積み重ねとして表現することにする方が良いという結論に至った.

説明

f:id:akiradeveloper529:20170220130348p:plain

When adding a single server to a cluster or removing a single server from a cluster, any ma- jority of the old cluster overlaps with any majority of the new cluster; see Figure 4.3. This overlap prevents the cluster from splitting into two independent majorities; in terms of the safety argument of Section 3.6.3, it guarantees the existence of “the voter”. Thus, when adding or removing just a single server, it is safe to switch directly to the new configuration. Raft exploits this property to change cluster membership safely using little additional mechanism.

  1. 1つのサーバを追加・削除する場合には, C_oldとC_newのそれぞれ任意のmajorityは必ずoverlapする; 上の実際の4パターンの実例では正しい. スケールを2k上げたとしても結局同じことなので正しい
  2. このオーバーラップが1つのリーダーしか選出されないことを保証する; どちらかのクラスタがmajorityを得ようとする時には必ずその1台のvoteを得なければいけない. その1台は1つのTermに複数のvoteをしないからリーダーは1つのTermに1つしか選出されない

まとめ

Joint Consensusはやめよう. 1台ずつの追加・削除に分解しよう.

RaftのMembership Changeは博士論文を読めとのこと

Raftは簡単だ. Yeah. Raftは素晴らしい. YEAH! しかしMembership Change… WHAT!?

おれは, In Search of an Understandable Consensus Algorithm (Extended Version) (https://raft.github.io/raft.pdf) を読んだ. Membership Changeの章で分からないことがあったので, とりあえずメールしてみたらわりと速攻で返ってきた. ありがとうディエイゴー

Dr. Diego Ongaro,

I am Akira Hayakawa. I am working as a software engineer.

I am implementing Raft algorithm based on your paper and I have one question:

Does joint consensus algorithm described in your paper works in case the C_old and C_new don’t have any intersection?

I think the answer is no because there is a case that no leader can be elected under C_old,new. This case is artificially made in such scenario:

  1. Client sends request to update membership from [0,1,2] to [3,4,5]
  2. Leader distributes and [0,1,2,3,4,5] and it’s committed.
  3. Leader crashes
  4. The cluster needs to elect new leader from C_old,new the membership that all the follower recognize.

I am not pointing any theoretical defect in the algorithm but just from my curiosity.

Thanks,

Akira

質問は, Membership ChangeでC_old, C_newに仮に共通集合がなかった場合はリーダーが選出出来なくなって破綻するケースがありませんか?ということ.

Hi Akira,

The short answer is yes, C_old and C_new do not need any servers in common. There’s a simpler algorithm and better explanation in my dissertation ( https://github.com/ongardie/dissertation/), but make sure you check the errata too. If you want to discuss further, please use the raft-dev Google group, where others are likely to chime in before me.

Best, Diego

答えは,

  • 破綻はしない (short answer)
  • simpler algorithm and better explanation in my dissertation
  • より議論したい場合はraft-devへ

とのことだった. 博士論文を見てみると遥かに詳しく書いてある. Simpler algorithmについて分かったらシェアします.

追記

破綻しないというのは分かった. 頭が悪くて混乱していた.

破綻するケースはないというのは, 単に[3,4,5]は[0,1,2]の中のcandidateにvoteすることが出来るから. membershipはどいつらからmajorityを確保するか発信側が決めることであって, それにvoteするかどうかはmembershipは関係なく, consistency checkのみが関わる. だから例えば0がcandidateになったとして, [1]と[3,4]からvoteを受ければリーダーになることが出来る.

Simpler algorithmというのは, シングルサーバの追加・削除に限定した場合の話のようである. 一応読む. 面白ければシェアする.

Overwatch: WiMAX解約して光回線にします

WiMAXでやれることはやった.

クレードルを買って, PS4やマックとは有線で繋いでるし,

こんな感じでアンテナも自作した.

f:id:akiradeveloper529:20170219120634j:plain

ベランダの手すりによる遮蔽を防ぐために出来る限り高いところには置いている. 部屋だって1階じゃあない. 東京都内に住んでいるからエリアとして悪いわけがない.

日中にダウンロードが1Mbpsしか出ない. 日中は制限はかけないと言ってたのになぜ?契約違反だと思う. 消費者を愚弄している. エンジニアがミスったのか?そんな糞エンジニアは殺せ.

6PM以降の制限時間帯では予告通り1Mbpsに絞られているけど, これは耐えられないほど遅い. 実際に今はテザリングを使ってネットをしている. 1Mbpsしか出ないとどんなページを開くのも遅い. 動画なんかまともに見れない.

致命的なのはオーバーウォッチだ. もともとpingはある程度遅いことを許容してプレイしていたが, さらに遅くなった気がする. あるいは帯域が狭いこと自体がプレイに影響を与えている可能性がある. オンラインゲームは送る情報は少ないから, 帯域よりpingが重要と言われているけど, 最低でも帯域は3Mbpsくらいは必要と言われている. これすら満たしていないからか, 着弾が遅れたり, 敵が瞬間ワープしたり, 2/2以前にはなかった素敵な現象が見られている. ボイチャも飛び飛びになることがある. もはやゲームにならない. オーバーウォッチは唯一の癒やしなのに, それを奪われた.

だからおれはWiMAXを解約することにした. FUCK YOU

Overwatch: エイムアシストはハイセンシほど効果がある

CS版に特徴的な機能としてエイムアシストがある.

このエイムアシストによってパッドでのFPSは成り立っていると言っても過言ではない. マウスの場合, エイムアシストを仮に切ったとしてもある程度プレイが成り立つが, パッドではエイムがガバガバになる.

fpslovers.hatenablog.com

にも書いてあるが, 仮にエイムアシスト0の状態でマウス=10, パッド=5だったとしても, エイムアシストをつけるとマウス=11, パッド=10くらいまで近づいてしまうからマウスを使うと一方的に有利かというとそうでもなく, 実戦では位置取りとかリロードの問題, スキルのクールタイムなども加味されるから, 実際にはおれも結構撃ち負ける. この数値というのは感覚的には大体正しい. むしろ最近キルレが上がっているのは, ある程度遠くからでも撃てるという自信から不用意に相手に近寄らなくなったというのと, 単にマウスにしてからも何十時間もプレイしたから立ち回りがうまくなったということだけのように思っている.

おれはマウスでもエイムアシストは60だけつけてる. 原理的にいうとマウスとエイムアシストは相性が悪い. なぜかというと, マウスでエイムするということはマウスの動きとポインタの動きを連動させることなので, エイムアシストによってそれが阻害されると却ってやりづらくなる意味もあるからだ. しかし, CS版では指数ランプかデュアルゾーンの2種類しかなく, マウスの動きとポインタの動きは厳密にいうと正比例しない. 結局, 正比例しないのだから, あくまでも精度の良いスティックとしてマウスを使うという判断をし, 自分の感覚にとって極端に邪魔にならない程度にエイムアシストをつけているというわけだ. 仮にエイムアシストをつけないと, むしろパッドでやった方がエイムが良いくらいになる. それほどエイムアシストというのは強力な機能ということだ. もしエイムアシストがないゲームでマウスを使ったら, おそらく本当に無双出来てしまうだろう.

そしてここからが本題なのだが, おれはトレーニングモードでボットが何台かいる状態で, エイムアシストのあるなしと振り向きcmについて何回かやってみた. その結果, 以下のことがわかった.

  • マウスのDPIが800, in-gameセンシが100, エイムアシスト0の場合, 振り向き x XIM4センシ = 1200が成り立つ
  • エイムアシスト=100の場合, XIM4センシx, y (x>y)について, x * 振り向き(x) > y * 振り向き(y)が成り立つ. これはどういうことかというと, センシが高い時の方がエイムアシストが振り向きに与える影響が大きいということ

おそらくだが, エイムアシストのかかり方は,

  1. in-gameセンシに依って決定する
  2. どのセンシにも影響されない

のどちらかだと思う. 仮に1とすると, エイムアシストの恩恵を受けるためにはin-gameセンシを高くして, DPIを低くする方が理に適ってるということになる. パッドでもある程度センシを高くする方がエイムアシストのかかりが相対的に強くなるから, 操作出来る範囲で高くした方が理に適っていることになる.

マウスについていうと, エイムアシストはあった方がいいが, ありすぎても困る. 相手に合わせたあとに多少フィードバックをかけてくれればそれ以上のことはマウスで制御出来るので, 試行錯誤を繰り返して出来るだけ低い値に納得していくしかないだろう.

ATGスクワットの良さについて語る

今おれはATGスクワットをやっている. ATGというのはAss To the Groundの略であり, ボトムでベタッと座ってしまってから爆発的に立つスクワットのことだ. 深くしゃがむのと, ボトムでほぼ脱力してしまうため, パワーリフティングで採用されているパラレルとフルの中間みたいな怪しいスクワットよりは遥かに重量が扱えなくなる. おれはパワーのスタイルならば190kgを3回出来るが, ATGでやると今日やった135kgを7回がベストだ. 大体40kくらいは低い重量になっている.

重い重量を扱えないことはほとんどのトレーニーにとって, プライドを傷つけるものであるから好ましくないことだ. だから多くの人はハーフスクワット程度の怪しいスクワットをやっている. それで一時的な自尊心は保たれるかも知れないが, 結局トレーニングの質としては疑問が残ってしまう.

ATGの良さを説明するために

  1. 重い重量を扱わなくてもよい
  2. 重い重量を扱わない方がよい

の2つに分解して説明する.

1. 重い重量を扱わなくても良い

ATGスクワットはフルレンジで筋肉を動かすからあらゆる筋肉を使う点で優れており, 浅いレンジでより力を発揮する大腿四頭筋についても十分な負荷が得られていると感じている. それに大腿四頭筋の負荷が足りないと思うならば, 補強をすればいいだけだ. 例えばレッグプレスやレッグエクステンションを追加すればいい. しかしほとんどの場合それは要らないだろう.

ATGでは, 大殿筋やハムストリングも使ってボトムから立ち上がり, 最後は大腿四頭筋で完全に立ち上がるという動きになる. このうち大殿筋やハムストリングの発達は女性トレーニーが望むものだ. 彼女らは大腿四頭筋は発達させたくないが, お尻は引き締めたいと思っている. そんな時はATGをやればいい.

今, 欧米ではクロスフィットなどのHIT(High Intensity Training)が流行っている. パワーリフティングの世界に乗り込んでいる女性は少ないが, クロスフィットには美しくなりたい女性に支持されている. そこでやっているスクワットはやっぱりATGだ. Yeah, 彼女らは本当に良いお尻をしている.

www.youtube.com

日式女子もスクワットをすべきだ. スクワットをしない女は・・・ダメだ.

2. 重い重量を扱わない方が良い

限界に近い重量のバーベルを担ぐことはかなり危険なことだ. まず, 背負った段階でぐらつく. 仮に後ろにバランスを崩してしまったとしよう. どうなるか?そのままバーベルを持っていたらおそらく背骨が壊れる. まっすぐ立っていたとしても背骨にはかなりの圧がかかっていて椎間板を損傷する可能性がある.

首も危ない. バーベルは首で担ぐわけではないが特にハイバーで担ぐと首に近くなる. これによって首を損傷する可能性がある. 特に, 高重量になるとボトムで多少前のめりになってしまうことがある. そうするとバーベルの圧が首寄りにかかってきて, 首がダメージを受ける. 仮につぶれてしまった場合, セーフティバーがあったとしても首には確実にダメージが残る. 実際に潰れた次の日は首が痛い. 軽いムチウチのような感じになるのだ.

日本のジムでは, 潰れる時にバーベルを後に落とすことが禁止されている. 理由はバーベルを落とすと他のお客様がビックリなさるからだそうだがこれが本当に良くない. この糞ローカルルールによって安全にスクワットをすることが出来なくなっている. だから日本のジムでは高重量のスクワットは常に命の危険と隣合わせとなる.

おれにとって135kgやそこらならば, 完全にコントロール可能だ. また, 全身をフルに使って強くなれば, 190kgを扱えるようになった時はやっぱり安全にコントロール可能になっている. 結局浅いスクワットは大腿四頭筋への負荷は高いかも知れないが, 他の筋群への刺激は少なく, 大腿四頭筋を鍛えるならばもっと安全な方法があることを考えると, ただ危険なトレーニングということになってしまうのだ. 結局急がば回れで, フルレンジのATGを伸ばしていくことが, 安全で確実にスクワットを伸ばしていく方法なのだとおれは考えている.