2015年5月18日月曜日

Paxos の解説の解説(その 4)

前回 proposer の振る舞いは説明したので、次は acceptor の説明。

"prepare" request と "accept" request のどちらについても、acceptor は自由に無視できる。無視してもアルゴリズムが誤動作することはない。
"prepare" request を無視すると、proposer は(前回説明した)集合 S を作れなくなり、その提案は破棄される。つまり、合意を取るのが遅れることになるが、誤った値が選択されることはない。
"accept" request を何人かの acceptor が無視し、半数未満の acceptor だけが受理したとする。すると、「値 v がいくつかの acceptor によって受理されるが、全体としては選択していない(合意していない)」という状況が生まれる。これは問題だろうか?
当然ながらこの提案は「選択」されない。ではどういう影響があるかというと、この提案が現時点で最大の proposal number を持つので、次の "prepare" request のときに、値 v が proposer に返される。そして、ペアとなる "accept" request で過半数の acceptor が v を受理することになる。もしかしたら、いくつかの acceptor が "accept" request をまた無視するかもしれないが、何ラウンドか繰り返すことで、いつかは過半数を達成するだろう。なので、これは問題なさそうだ。

(これは私の理解であって、解説には書いてないが)結局 Paxos プロトコルは proposer が acceptor を「説得」していく手続きだと思う。proposer の競合やネットワーク障害によって、1 ラウンドの "prepare"/"accept" request では合意に達しないことがある。そのときは、次の "prepare" request が「最も最近発行された(が合意に達しなかった)値を再提案し、より多くの acceptor に受理させる。」そうすれば、いずれ過半数の acceptor が受理し、合意に達するだろう、というのがポイントだ。
もちろんこのプロトコルが停止することは保証されてなくて、それは解説でも触れられている。2 つの proposer が "prepare"/"accept" を順番に発行すると、いつまでも合意に達しない。(「停止性」を保証した改良版 Paxos もあるらしい)

話を元に戻すと、acceptor はリクエストを自由に無視できる。逆に無視しなくてはいけないリクエストがある。proposal number N の "prepare" に応答したらそれ以降は、proposal number が N より小さいリクエストは「無視しなくてはいけない」。それ以外の場合は受理して良い。
直感的には、"prepare" request とは、proposal number N 未満の世界において過半数の acceptor の集合を確認する操作なので、これを応答した後に、N より小さいリクエストによって状態を変えてはいけない、ということになる。

これを acceptor への条件として要請する。
P1a. acceptor は、proposal number N より大きい "prepare" request を受け付けてないとき、そのときのみ、 proposal number N のリクエストを受理する。
これは「P1. acceptor は最初に受け取った提案を必ず受理する」より厳しい条件である。

この条件によって、acceptor が proposal number N の "prepare" request にすでに応答している場合は、N 未満の "prepare" request は無視して良い、という最適化が可能になる。というのは、仮に "prepare" request M (M < N) に応答したとしても、ペアとなる "accept" request は無視しなくてはならないからだ。(なので、"prepare" request に応答する意味がない)


以上で、最初のエントリの最後に書いたプロトコルで、正しく合意が取れることがわかった。

2015年5月17日日曜日

Paxos の解説の解説(その 3)

前回のエントリで、このプロトコルは、
P1. acceptor は最初に受け取った提案を必ず受理する
P2b. 提案 [m, v] が選択されたとする。ある proposer が n > m となる提案 [n, u] を発行するならば n = v である。
という 2 つの条件を満たせば良いことがわかった。

P2b を満たすには、proposer は、すでに選択されている値 v を、新しい提案を発行する前に知らなくてはならない。どうすれば v を知ることができるのか? その前に、ある提案があったときに、P2b を満たしているかどうか証明する方法を考える。

まず簡単のために、P2b の仮定を拡張し「提案 m, m+1, m+2, ..., n-1 が全て、値 v を持つ」とする。つまり、
P2b'. 提案 [m, v], [m+1, v], [m+2, v], ..., [n-1, v] が選択されたとする。提案 [n, u] が発行されるならば、u = v である。
また、一般に提案が選択されるには、過半数の acceptor から成る集合 C が存在し、C の要素である acceptor は全てその提案を受理しなくてはならない。これと P2b -> P2b' の拡張とを組み合わせると、P2b' の前提部分は次のように書き換えられる。
提案 [m, v], [m+1, v], [m+2, v], ..., [n-1, v] が選択されたならば、過半数の acceptor からなる集合 C が存在し、C の要素である acceptor は、提案 m, m+1, m+2, ..., n-1 を受理する。また m, m+1, m+2, ..., n-1 は値 v を持つ。
ここから、P2b を満たすには P2c を満たせば良い、と書き換えられる。
P2c. 提案 [n, v] を発行するときには、以下の条件を満たす、過半数の acceptor から成る集合 S が存在する。
  • S のどの要素も proposal number が n 未満の提案を受理していない、または
  • S の各要素が今までに受理した n 未満の提案のうち、proposal number が最大の提案は値 v を持つ。
ここは理解が難しいので、逆向きにも考えてみる。つまり、P2c が満たされたら、P2b がなぜ満たされるのかを考えてみる。

まず、「S の各要素が今までに・・・最大の提案は値 v を持つ」ような S が存在せず、「S のどの要素も proposal number が n 未満の提案を受理していない」ような S しか存在しないとする。ということは、n 未満の提案は、発行されていないか、されたとしても半数未満の acceptor にしか受理されていないことになる。したがって、まだ何も選択されていないことになる。この場合は P2b の前提「提案 [m, v] が選択されたとする」が成立しないので、P2b 全体は成立する。

つぎに「S の各要素が今までに受理した n 未満の提案のうち、proposal number が最大の提案は値 v を持つ」ような S が存在したと仮定する。この「proposal number の最大値」を Mn とする。帰納法の仮定により、提案 Mn が少なくとも 1 つの acceptor に受理されたことから、Mn は選択されたことがわかる。

  • Mn == m の場合、提案 [Mn, v] (つまり [m, v])を過半数の acceptor が受理していたことになるので、P2b が成立する。
  • Mn < m の場合、提案 m は選択されなかったので、上と同様の議論で、P2b は成立する。
  • Mn > m の場合、再帰的に P2c を適用することで、P2b が成立することがわかる。

これで、P2c を満たせば、P2b が満たされることはわかった。(この部分を正しく理解できているか怪しい)

したがって、P2c を満たせるようなプロトコルを考えればよい。これが、最初に説明した "prepare" request と "accept" request の 2 種類のリクエストとなる。
"prepare" request は、acceptor に対して「すでに提案を受理したか」「受理したとしたら受理した値は何か」を確認し、P2c における集合 S を確定するためのリクエストだ。注意が必要なのは、非同期なネットワーク通信を仮定しているので、proposal number n を処理した後に、n より小さい提案が届く場合があるということだ。そのため、"prepare" request は「今後 n 以下の request は受理しないように」と要請する必要がある。

これで、proposer のあるべき振る舞いはわかった。あとは acceptor の挙動と、ちょっとした optimization について論じている。それはまた次に。

2015年5月16日土曜日

Paxos の解説の解説(その 2)

前回の続きで、Paxos プロトコルの正しさについて、この解説をもとに解説する。

まず、acceptor が一人しかいない世界を考える。この世界では簡単に合意が取れる(その acceptor が選択した値がただ一つの「合意した」値となる)が、この acceptor が single point of failure となるので良くない。したがって acceptor が複数動いている状況を考える。この状況では、以下の 2 つのルールを守れば、「選択される値は 1 つだけである」という要請を満たせる。(が、以下に書くように、このルールでは結局うまくいかない)

  • acceptor はたかだか 1 つの値しか受理しない
  • 過半数の acceptor が値 x を受理した時に値 x が選択される
この状況において、2 種類以上の値が選択されることはない。

つぎに、proposer が一人しかいない状況で、この proposer が値 x を提案したとする。ネットワーク障害やプロセスダウンなどがない完璧な世界では、x は選択されなくてはならない。そうでないと、いかなる提案も無視されることになり、合意は全く成立しない。したがって、このプロトコルは、
P1. acceptor は最初に受け取った提案を必ず受理する
という条件を満たす必要が有る。
が、しかしこれだけでは十分ではない。2k 個の acceptor が存在する状況で、2 種類の値が同時に提案され、それぞれ k 個の acceptor が受理すると、どちらも過半数に達しないので、どの値も選択されない。

「acceptor は最初に受け取った提案を必ず受理する」という条件と、「過半数の acceptor が値 x を受理した時に値 x が選択される」という条件とを満たした上で、なんらかの値が選択されるために、「acceptor はたかだか 1 つの値しか受理しない」というルールを破棄し、「acceptor は一つ以上の値を受理できる」こととする。
つまり、「acceptor は最初に受け取った提案を必ず受理する」と「acceptor はたかだか 1 つの値しか受理しない」とを同時に要請すると、「最初に受け取った提案を受理し、その後は何もしない」という意味になり、上記の「2k 個の・・・」の例で行き詰まってしまう。

ここまでの議論で、1 つの proposer は複数の提案をする(可能性がある)ことになった。そこで、複数の提案を区別するために、proposal number を導入する。proposal number は自然数とする。また同じ propose による異なる提案は、 異なる proposal number を持つものとする。
つまり、「提案 (proposal)」とは「提案される値 v」と「proposal number n」とのペアとなる。これを [n, v] 書くことにする。「提案」と「提案される値」とを分けて考えることに注意する。acceptor は複数の「提案」を受理することができるが、受理された複数の「提案」は、同じ「提案される値」を含まなくてはならない。したがって、
P2. 提案 [n, v] が選択されたとする。m > n となる提案 [m, u] が選択されたら、u = v でなくてはならない。
という条件が要請される。この条件によって「選択される値は一つである」という要求を満たすことができる。

値が「選択」されるには少なくとも一つの acceptor に「受理」されなくてはならないので、以下の P2a を満たせば P2 を満たすことができる。(P2a は P2 より厳しい条件である。)
P2a. 提案 [n, v] が選択されたとする。m > n となる提案 [m, u] が任意の acceptor に受理されたら、u = v でなくてはならない。

さて、ここで次の状況を考える。
  • 提案 [n, v] がすでに選択されている(= 過半数の acceptor が受理した)
  • acceptor c は(例えばネットワーク障害により)これまでに全く提案を受理しなかった。したがって も受理していない。
  • 新しい proposer が起動し、[m, u] を提案した (m > n and u != v)
この場合、「P1. acceptor は最初に受け取った提案を必ず受理する」というルールにより、c は [m, u] を受理してしまうが、これは P2a に反する。したがって、P2a では不十分だとわかったので、さらに条件を厳しくする。
P2b. 提案 [n, v] が選択されたとする。m > n となる提案 [m, u] が任意の proposer によって提案されたら、u = v でなくてはならない。

P2b を満たすには、proposer は、提案する前に現在選択されている値 v を知らなくてはならない。(そうでないと u != v となる u を提案してしまい、P2b に反する)
どうすればこれが実現できるのか・・・、は次回に続く。

2015年5月15日金曜日

Paxos の解説の解説(その 1)

Google の distributed 系の論文を読んでるとほぼ必ずでてくる Paxos。複数のプロセス間で合意を取るためのプロトコル (consensus protocol) で、リーダー選出などに使われる。
元論文はこちらだが、これが一般人には分かり難かったらしく、同じ著者 Leslie Lamport が解説を書いているので、こっちを読んでみた。

まず基本的な概念から。なお以下で、「値 x が選択される」とは「値 x で合意が取れる」と同じ意味である。
3 種類のエージェントを考える。proposer は値を提案する人。acceptor は提案された値を受理する(もしくは受理しない)人。learner は選択された値を受け取る人である。(実際には一つのインスタンスが複数のエージェントとして振舞うことがある)
ただし、learner については難しいことはないので、特に説明しない。複数の proposer が提案する値の中から、どうやって一つの値 x で合意するか、というのが目的となる。

シンプルだが正しく動かない例を挙げてみる。
2 つの acceptor a1, a2 が存在し、それぞれ最初に受け取った値を accept する(= 選択する = 合意する)ものとする。2 つの proposer p1, p2 が、同時点でそれぞれ値 v1, v2 を提案したが、p1 -> a2 と p2 -> a1 の通信が失敗したとする。すると、a1 は v1 を、a2 は v2 を「選択」してしまい、合意が取れないことになる。これは明らかに良くない。

consensus protocol が満たすべき要求は以下の 3 つだ。

  1. 選択された値は、必ず提案された値である。
    === 誰も提案していない値が選択されることはない。
  2. 選択される値は一つである。
    === みんなが同じ値に合意する。
    === 複数の値が選択されることはない。
  3. 値 x が選択されたときに限って、「値 x が選択された」という情報を受け取る
    === 偽の情報を受け取ることはない。
上記のシンプルな例は 2 を満たしていない。

答えを先に書くと、正しいプロトコルは以下の通りである。まず前提として、

  • "prepare" request と "accept" request との 2 種類がある。全てのリクエストは、提案・合意される「値」とは別に "proposal number" と呼ばれる整数を持っている。
  • proposer は整数カウンタを 持つ。これは proposal number を生成するために使われる。
  • acceptor はいかの 2 つの値を記憶している。
    • これまでに受け取った "prepare" request のうち最大の proposal number。これを Mp と呼ぶ。
    • これまでに受理した「値」とその proposal number。これを Pa と呼ぶ。ただし、まだ何も受理していない場合は Pa = null となる。
このプロトコルは 2 つのフェーズから成る。

Phase 1: prepare phase
  • proposer は proposal number N の "prepare" request を(少なくとも)過半数の acceptor に送る。
  • acceptor は、N <= Mp であれば、この "prepare" request を無視する。N > Mp の場合は、Pa をレスポンスとして送り返す。
Phase 2: accept phase
  • proposer は、"prepare" request に対するレスポンスを過半数の acceptor から受け取った場合は、proposal number N と提案する値 V の "accept" request をその acceptor に送る。V は以下の条件で決まる。(なおレスポンスが過半数に満たない場合は、この「提案」は失敗なので、カウンタを increment して Phase 1 からやり直す。)
    • 一つ以上の acceptor が Pa != null を返した場合は、複数の Pa のうち、最大の proposal number を持つ Pa の値とする。
    • 全ての acceptor が Pa == null を返した場合は、proposer は任意の値を V とする。
  • acceptor は、proposal number N の "accept" request を受け取ったら、N >=(現時点での)Mp なら、値 V を受理する。N < Mp なら無視する。

このようにプロトコル自体はとてもシンプルである。問題は「このプロトコルでなぜ正しく合意が取れるのか」であり、この解説もそこにページ数を割いている。「正しさ」については次のエントリで書きたい。


2015年5月14日木曜日

"The Age of Diminishing Expectations" の切り抜き

ktdiskのブログ」のどこかに書いてあった(記事が見つからない)ように、読んだ本で気になったところを記録する試みを始めようと思う。あんまり本読まない(←良くない)が。とりあえず昔読んだ本から。

クルーグマン教授の経済入門

なぜか手元に見当たらないので、英語版と私の拙い訳でどうぞ。

The Age of Diminishing Expectations -- Paul Krugman

P.18
This is not an answer that inspires fervent political support -- especially when one bears in mind that the causes of the productivity slump are not obviously tied to declining investment in plant and equipment or in education. In fact, the American economy placed about as high a share of its resources into investment, and a higher share into education, in the 1970s and 1980s as it did in the 1950s and 1960s. It just didn't work as well.
拙訳([] 内は私の注釈)
これ [= 生産性向上のためには、今の消費を抑えて投資に回すこと。そうすればいつかはわからないけどいずれ生産性は上がるだろう] は、政治家が熱烈に支持するような答えではない。生産性の落ち込みが、工場・設備投資や教育への投資と結びついていることが明らかでない状況では特に人気がない。実際のところ、アメリカ経済は [生産性が伸びた] 1950 - 60 年代と同等の投資と、それ以上の教育費を 1970 - 80 年代に費やした。でも、生産性は向上しなかった。

これは "Productivity Growth " という章の一節。この章は「生産性は [経済の] 全てではない。でも長期的には生産性でほぼ全て決まる」から始まる。そして「でも、経済学者は、生産性がなぜ落ちるのか、どうしたら向上するのかを説明できない。」と続く。
「重要なことが説明できないから、みんな重要じゃないことを議論するんだ。たとえばインフレとか国際競争とか。」と、何が本質的で何が枝葉かと明快に(そして軽快に)説明できるところが素晴らしい。書いてるのが、怪しい経済評論家(笑)じゃなくて、ノーベル経済学賞を受賞したクルーグマンなので、信頼できる(と思ってる)。

2015年5月13日水曜日

現役 / 老人比率が 1.2 になる国

デマこい! - いま失敗すれば、日本終了。」から抜粋
1.2 人
何の数字か、お分かりだろうか。

2050年における現役世代と老後世代の人口比だ。現在の日本では現役世代2.4人で老人1人を養っている。しかし、2050年にはこれが半分になり、現役1.2人で老人1人を支えることになる。私たちの子供世代は高額の社会保険料と重税に苦しめられ、優秀な人から順番に海外に脱出するだろう。国民皆保険は、たぶん崩壊する。年金は、おそらく有名無実のものになる。
1.2 というのはスゴイ数字だ。現役世代のほぼ全員(6 人中 5 人)に老人 1 人が割り当てられ「この老人の面倒をみてくださいね、あなたの負担で」ということだ。(現状の 2.4 も十分キツイ数字なのだが)

著者の主張はこうだ。

  • 出生率をあげて現役 / 老後比率を改善する
  • そのために年間所得 500 万以上の世帯を増やす
  • そのために賃上げ要求する and 女性の雇用拡大
最初の 2 点はよくわかるが、最後の点は賛成できない。
著者は労働力が不足している社会を想定しているように見える。そういう社会では労働者を確保するのが困難なため、賃上げ要求は通りやすいだろう。また、女性が雇用されることで、共働き世帯が増え、世帯収入も増えるだろう。

しかし、労働力が供給過剰な世界では、全ての労働者が一致して賃上げ要求をしない限り、要求は通らないと思われる。代替の労働力がすぐに見つかるからだ。また女性の雇用拡大した結果、男性の雇用が下がってしまっては、マクロでの家計所得は増えない。

結局、目新しくない結論だが、賃上げ要求と女性の雇用拡大の前に、企業活動を活発にして、労働需要を増やさなくてはいけなくて、そのために現実的にできることは、金融緩和ぐらいしかないのではないか。あと消費増税はするべきではなかった。片足でアクセルを踏みながら、もう一方の足でブレーキを踏むのは良くない。10% への増税が延期されたのは良い傾向だ。

折しも Facebook が契約社員の最低時給を $15 に上げたことがニュースになったが、これは Facebook がとりわけ generous な会社だからではなくて、利益をあげていて、より良い契約社員を集め、契約社員のモチベーションを高めたいからだ。


2015年5月12日火曜日

「人を蹴落として偉くなる」のか?(地獄のシリコンバレーより)

4 月中頃にベイエリアを中心に(小さく)燃え上がった「地獄のシリコンバレー」。すでに完全に鎮火した感があるけど、ちょっと気になったコメントがあったので。

上記リンクにある tweet の一つから抜粋。
これも相対評価だから、どの社員よりも自分が優れてないといけない。人を蹴落としてでも上に登りたい上昇志向で自分のスキルを常に磨く準備はあるのか。
この「人を蹴落としてでも上に登る」という意見は、何回も見た/聞いたことがある。それもアメリカで働いている人や働いたことのある人からだ。
しかし個人的には、(プロモーションも昇給も経験しているが)蹴落とした、蹴落とされたと感じたことはない。どこからこのイメージが生まれてきたのだろうか?

仮説 1. 「人を蹴落とす」業種・業界がある

完全に妄想だけど、そういう業種・業界があるのかもしれない。セールスやトレーダーなんかは蹴落としあってるイメージが私にはある。どちらもコミッションベースの給与であることが多いので、個人プレーになりやすいのかな、と思う。

エンジニアはたいていコストセンターなので、給与にコミッションが入ることはまずない。トレーディングアルゴリズムを開発・運用している会社のように、エンジニアがプロフィットセンターならありえるかもしれない。

仮説 2. 日本の大企業と比べると「人を蹴落とす」感がある

私はいわゆる日本の大企業で働いたことがないのだが、聞くところによると「年次」という概念があって、同じ年に入社した社員は全員同額の給与をもらい、全員等しく昇給していくそうだ。(もちろん役職手当とかはあるが)
こういう給与体系と比べると、(おそらくシリコンバレーでは標準であろう)「パフォーマンスに応じて job level, 給与が変わる」仕組みは、「人を蹴落とす」感があるのかもしれない。でもまぁ「パフォーマンスに応じた給料」は日本でももうそれなりに一般的だよねぇ (?)

仮説 3. 昔のアメリカは「人を蹴落としてた」

この話の他にも「アメリカでは書類を引き出しに入れて鍵を掛けてから帰る。同僚が書類を盗むかもしれないから」みたいな話も聞いたことがある。「アメリカは個人主義」というやつだ。
この手の話はいくつかあるので、そういう時代もあったのかもしれない。また、「Japan as No. 1 の時代の日本企業を研究して、『チームワーク』『会社は家族』のような考え方を取り入れた」という話も読んだことがある。なので、昔は「人を蹴落としてた」けど、今では「チームワーク重視」になった。ということがあるのかもしれない。

仮説 4. 見知らぬ社会での恐怖感の裏返し

これが結構あるのではないかと個人的には思うのだが、人はよく知らないものには恐怖感を持ち、敵意を抱きやすい。見たこともない生物が目の前に現れたら、子供なら興味を持って近づいていくかもしれないが、大人は逃げ出したり攻撃したりするだろう。
というのは極端な例だが、同じ文化の中で育った同じ民族なら、ちょっと会話をするだけで相手のことがわか(ったように思い込んだりす)るが、英語が流暢じゃない日本人が、コミュニケーションの作法が異なる外国人について「コイツ何考えてるのかわからない」と思い、自分を蹴落とそうとしてると感じることはありそうな気がする。
仏頂ずらのまま早口でまるで怒ってるかのようにまくしたててる人は結構いるし、その内容がわからず、「わからないからもう一回言ってみて」と聞き返すこともできない状況で蓄積したフラストレーションが元で、相手に悪感情を持つというのは、自分にも経験はある。


とくに結論はないのですが、「競争社会だから、蹴落としたり蹴落とされたりするんだよ」っていうのは、「アメリカ一般」には該当しないんじゃないですかね。アメリカは日本より多様性がある(と思う)ので「アメリカ一般」というのがそもそも無意味なのですが。