Multi-PAXOS擬似コード

PAXOSの説明はWikipedia

元々のPAXOSのうち、同じProposerから連続してproposeされる時、チョット効率よく処理をする改良としてMulti-PAXOSというアルゴリズムがある。そのMulti-PAXOSの擬似コードが無かったので作った。まだ試していないので動くかどうかは不明。

  • iの扱いが省略されていたのでnと同じように追加。
  • 参考資料でiの扱いが簡潔に書かれていたり、元の論文がふんわりしているのは、PAXOS以前の実装・条件に依存する動作があるためと思われる。下記の擬似コードも自分で使う用に補完している。
  • 送信コマンドと返信コマンドがペアリングできる必要があるのでは?基本的なPAXOSの擬似コードではnはローカル変数で、ペアリングのキーになっているようだ。
  • 基本的なPAXOSのProposer-5の動作は、Proposerがacceptコマンドを過半数に送り切る前に死んだ場合、Learnerが状態を確定できない状態を対策するためにあるようだ。同状態の検知はLearnerで検知できるので、ProposerがやるよりLearnerがやったほうが状態がわかりやすいかと。
  • Alloyなどの形式手法でうまく動くかどうか確認したいけど、どうやるんだろうね?

参考

もともとのPAXOSの擬似コード

http://people.csail.mit.edu/alinush/6.824-spring-2015/paxos-algorithm.html

   --- Paxos Proposer ---

 1  proposer(v):
 2    while not decided:
 2      choose n, unique and higher than any n seen so far
 3      send prepare(n) to all servers including self
 4      if prepare_ok(n, na, va) from majority:
 5        v' = va with highest na; choose own v otherwise   
 6        send accept(n, v') to all
 7        if accept_ok(n) from majority:
 8          send decided(v') to all


    --- Paxos Acceptor ---

 9  acceptor state on each node (persistent):
10   np     --- highest prepare seen
11   na, va --- highest accept seen

12  acceptor's prepare(n) handler:
13   if n > np
14     np = n
15     reply prepare_ok(n, na, va)
16   else
17     reply prepare_reject


18  acceptor's accept(n, v) handler:
19   if n >= np
20     np = n
21     na = n
22     va = v
23     reply accept_ok(n)
24   else
25     reply accept_reject

作った擬似コード

■Client/Learner

値Vを設定するとき
  • Proposerにset(V)を送る
reply_set()を受信したとき
  • 完了
値を取得する時
  • 全てのAcceptorにlearn()を送る
reply_learn(n, i, v)を受信したとき
  • if 受信した{n, i, v}の数を集計し、過半数を獲得したものがある
    • {n, i, v}を採用
  • else
    • 全てのAcceptorにlearn()を送る

■Proposer

初期状態
  • np=0
  • ip=0
  • reset=true
set(v)を受信したとき
  • np+=1
  • vp=v
  • if reset==true
    • 全てのAcceptorにprepare(np)を送る
  • else
    • 全てのAcceptorにaccept(np, ip, vp)を送る
reply_prepare(res, n, i)を受信したとき
  • if res=='ok'がAcceptor過半数
    • ip=max(i)+1
    • 全てのAcceptorにaccept(np, ip, vp)を送る
  • else(返事が来ない、'ng'が来たなどが過半数)
    • np=max(n)+1
    • reset=true
    • 全てのAcceptorにprepare(np)を送る
reply_accept(res, n, i)を受信したとき
  • if res=='ok'がAcceptor過半数
    • ip=max(i)+1
    • reset=false
    • reply_set()を返信
  • else
    • np=max(n)+1
    • reset=true
    • 全てのAcceptorにprepare(np)を送る

■Acceptor

初期状態
  • np=0
  • na=0
  • ia=0
  • last_nid=null
prepare(n)を受信したとき
  • if n > np
    • if src_nid != last_nid
      • i=0
    • else
      • i=ia
    • reply_prepare('ok', np=n, i)を返信
  • else
    • reply_prepare('ng', na)を返信
accept(n, i, v)を受信したとき
  • if n >= np && ia > i
    • np=na=n, va = v, ia = i, last_nid=src_nid
    • replpy_accept('ok', np, ia)を返信
  • else
    • reply_accept('ng', np)を返信
learn()を受信したとき
  • reply_learn(na, ia, va)を戻す

WebRTC on ネイティブ〜webブラウザ

分散環境の通信メディアとして、WebRTCを使っているが、ネイティブアプリとwebブラウザ間で通信を行うときに切断してしまう不具合がある。バージョンや、そもそもの作り方が悪かったのかと、最小サンプルを作って確認した。最小サンプルは動くので、自分が作った部分に 原因があるようだ。

f:id:llamerad-jp:20171112170318p:plain

github.com

Webブラウザでも分散

Emscriptenを用いてC++JavaScriptに変換することで、Webブラウザとネイティブで同じアルゴリズムで接続できるようにした。 本当はJavaScriptではなく、WebAssemblyに変換したかったが、embindを使ったクラスや関数のエクスポートが最小サンプルでも動かなかったため、今回はスキップした。

ロジックは変換できても、スレッド、POSTアクセス、WebRTCアクセス、タイマーなどの機能は直接変換できないため、JavaScriptで記述して、C++側から呼び出すようにした。

f:id:llamerad-jp:20171108065926p:plain

まだバグっぽいですね。

JavaScriptの非同期処理は、C/C++との連携において、非常に面倒な問題になる。PromiseやGeneratorは、非同期処理を同期処理っぽく書く手段を提供しているが、あくまで「ぽい」だけで、本当に同期処理になっているわけではない。C/C++で書いた同期的なロジック中で、非同期なJavaScriptの機能を使おうとすると、ネイティブな処理とは実行タイミングなどが変わり、処理順序の変化から、バグを引き起こした。C/C++でthreadやwaitを使おうにも、Emscriptenで変換したC/C++は、あくまでJavaScriptエンジン上で動くため、問題の解決はできない。これらの機能は設計段階から非同期なコールバックやタスクとして処理することを前提とした設計にする必要があった。(ので、かなり書き換えた)

遺伝的アルゴリズムを使ったルーティング

遺伝的アルゴリズムを使ったルーティングアルゴリズムにより、接続の偏りが少なくなった。 評価用の点数の付け方も工夫したので、特定のノードに通信が集中しそうになっても経路が分散されるはず。 f:id:llamerad-jp:20171024095332p:plain 計算負荷が上がったためか、120ノード前後でタイムアウトが発生しやすくなった。少しだけ最適化して高性能なマシンでもシミュレーションしておきたい。

ルーティングアルゴリズムの改良がイマイチだった

WebRTCのやTCPのように、コネクション型の通信経路を使う場合、特定のノードに接続が集中すると、そのノードのリソースが不足したり、負荷が上がってしまう。例えば、macOS sierraではユーザがopenできるディスクリプタの数は256に制限されているため、1ノードに64コネクションも接続すると25%も圧迫することになる。そのため、各ノードへの接続は可能な限り分散することが望ましいと考える。※WebRTCの通信はUDP上にSCTPを実装しているため、TCPほどディスクリプタを消費しないと思うが、経路情報などを個別に持つためメモリや計算負荷はTCPより高くなるのでは?という考えからも、接続は分散したい。

新しいルーティングアルゴリズムを実装してみたものの、ノードの多い・少ない、通信が偏っているか・分散しているかによって、接続が集中してしまうことがわかった。ノードが多く通信が偏っていないようなシミュレーション環境であれば、こうはならなかったのだろうが、自分は実用可能なプログラムを作りたいので、これではいただけない。

シミュレーションや計算で正しいと思われていたアルゴリズムを実装しても、現実の制約などから生じた微妙な差により、シミュレーション通りの動きにならないことを体感。(と言って良いものか、単純に考えが浅いのかもしれない)

収穫は、コネクション型通信を利用したノードが等価なルーティングアルゴリズムにおいて、通信経路の確立は互いに合意がなければならない(片方の合意が無ければ、切断してしまう)と考えていたが、ある一定のルールにより合意がなくとも経路の確立を決定できそうなことかな。

f:id:llamerad-jp:20171013062740p:plain

Xcodeの静的解析ツールに、メモリリークの可能性を指摘されたが釈然としない

経緯

本当はパフォーマンス測定ツールを使って、プログラムが想定外に重い処理を行っていないか、確認したかった。 とりあえず、「Analyze」を起動したら、「Potential memory leak」と言われてビクビク検証している。

f:id:llamerad-jp:20171011063104p:plain

プログラム

分散処理インフラのpicojsonを使っている部分が指摘された。問題を切り分けるため、同様の処理を以下のように切り出した。Analyzeでは同様の警告がでることを確認済み。

#include <string>
#include "picojson.h"

int main(int argc, char* argv[]) {
  std::vector<uint8_t> js_buf;
  std::string js("{}");
  js_buf.resize(js.size());
  memcpy(js_buf.data(), js.c_str(), js.size());

  for (int i = 0; i < 10; i++) {
    picojson::value v;
    std::string err;
    picojson::parse(v, js_buf.begin(), js_buf.end(), &err);
    if (!err.empty()) {
      std::cout << err << std::endl;
      return 0;
    }
  }
  return 0;
}

指摘内容

f:id:llamerad-jp:20171011063506p:plain

かなり細かく指摘される。画像のように、どのメソッドの、どの条件が〜という内容まででる。

メモリリークするのか?

コピーコンストラクタで確保した領域が、開放されない可能性がある?と言いたげだが、デストラクタで開放されている。コピーオペレータでswapを使っているが問題ないように読める。試しにvalgrindを使い、動的に検証するも、やはりリークは起きなかった。 プリプロセッサの展開がうまく解析できない(ような初歩的なことは無いと思いつつ)のかと思い、一応手動で展開したものの、状況は変わらず。 コンストラクタでnewを呼び出すと、メモリ確保の失敗時にstd::bad_alloc例外が発生して、その場合デストラクタが実行されず、リークの原因になりうる。しかし、今回に限ればnewは1度しか呼ばれないため、例外が発生してデストラクタが呼ばれなくとも、そもそも確保に失敗しているためリークは発生しない…はず。 picojsonのデータはunionで格納されており、途中で中の型を記録しているtype_変数を書き換えた場合、正常なdeleteが呼ばれず、メモリリークする可能性があるので、それを指摘したかったのか?と思い、以下のコードをAnalyzerにかけるも何も言われない。解せぬ…。

#include <memory>
#include <string>
#include "picojson.h"

class A {
 public:
  union U {
    int* i;
    char* c;
  };
  bool is_int;
  U u;

  A(bool is_int_) : is_int(is_int_) {
    if (is_int) {
      u.i = new int;
    } else {
      u.c = new char;
    }
  }

  virtual ~A() {
    if (is_int) {
      delete u.i;
    } else {
      delete u.c;
    }
  }
};

int main(int argc, char* argv[]) {
  A a(true);
  bool t = a.is_str;
  a.is_str = true;
  a.is_str = t;

  return 0;
}

もう一度見直す

そもそも、コピーコンストラクタやコピーオペレータ単体で使って再現する様なものではないらしい。試しに以下のコードでは警告が出ない。

#include <iostream>
#include <string>
#include "picojson.h"

int main(int argc, char* argv[]) {
  picojson::value v1;
  picojson::value v2(v1);
  v1 = v2;

  std::cout << v1.serialize() << std::endl;
  std::cout << v2.serialize() << std::endl;

  return 0;
}

実はパース処理の別の場所かもしれないと考え、玉ねぎの皮むきのごとく、1枚1枚関数を剥いて行こうとし、偶然以下のようにしたら警告が出なかった。差分は変数vとerrがforの中にあるか、外にあるかだけ。どちらもスタック変数であり、parse関数からすれば、状態は変わらないはず。forの中に変数がある場合、スコープが1ループごとに作る→開放されるので、vとerrのコンストラクタ、デストラクタの呼ばれる回数などは違うが、それによりメモリリークの有無が変化するとは考えにくい。釈然としないまま保留。どなたかご存知でしたら教えてください。(パフォーマンスの確認をしないとだし)

#include <string>
#include "picojson.h"

int main(int argc, char* argv[]) {
  std::vector<uint8_t> js_buf;
  std::string js("{}");
  js_buf.resize(js.size());
  memcpy(js_buf.data(), js.c_str(), js.size());

  picojson::value v;
  std::string err;

  for (int i = 0; i < 10; i++) {
    picojson::parse(v, js_buf.begin(), js_buf.end(), &err);
    if (!err.empty()) {
      std::cout << err << std::endl;
      return 0;
    }
  }
  return 0;
}

安定性の向上

ルーティングアルゴリズムの不具合を幾つか修正することで、安定性が向上した。5〜10%の割合でランダムにノードを突然終了させても、全体では崩壊せずに動作し続ける。 f:id:llamerad-jp:20171008040808p:plain