SciPyで線形計画問題を解く

scipy_logo

Pythonの数値計算ライブラリ SciPy には線形計画問題を解くための scipy.optimize.linprog という関数が存在します。
この関数を使って、線形計画問題を実際にといてみます。

例として次のような線形計画問題を考えましょう

maximize

z = x_1 + 2 x_2

subject to

\\ x_1 + 3 x_2 \leq 24 \\ 4 x_1 + 4 x_2 \leq 48 \\ 2 x_1 + x_2 \leq 22 \\ x_1, x_2 \geq 0

目的関数の右辺に -1 をかけて、目的関数の最大化を目的関数の最小化に変えます。

minimize

z = - x_1 -2 x_2

これを行列で表します。

z = \begin{bmatrix} -1 & -2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}  \\  \begin{bmatrix} x_1 & 3 x_2 \\ 4 x_1 & 4 x_2 \\ 2 x_1 & x_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} 24 \\ 48 \\ 22 \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}.

あとは、行列をリストで表現し、SciPyプログラム(linear-prog.py)に落とします。

# vim: set fileencoding=utf-8
c = [-1, -2] # 目的関数
A = [[1, 3], [4, 4], [2, 1]] # 決定変数の係数
b = [24, 48, 22]

# 決定変数の下限、上限
x0_bounds = (0, None)
x1_bounds = (0, None)

from scipy.optimize import linprog
res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds),
              options={"disp": True})
print res

実行します。

$ python linear-prog.py
Optimization terminated successfully.
         Current function value: -18.000000
         Iterations: 2
  status: 0
   slack: array([ 0.,  0.,  4.])
 success: True
     fun: -18.0
       x: array([ 6.,  6.])
 message: 'Optimization terminated successfully.'
     nit: 2

linprog関数の引数で {"disp": True} にしていると

Optimization terminated successfully.
         Current function value: -18.000000
         Iterations: 2

のブロックのメッセージが表示されます。

“Optimization terminated successfully.” というメッセージからわかるように、問題は無事とけました。

出力結果をもう少し詳しく見てみましょう。

status: 0

最適化の終了ステータスです。

最適解を見つけられると 0 になります。
指定されたイテレーション内にとけないなど、とけなかった時は1以上の値になります。

slack: array([ 0., 0., 4.])

制約の不等式を等式標準形に直します。

subject to
\\ x_1 + 3  x_2 + x_3 = 24 \\ 4  x_1 + 4 x_2 + x_4 = 48 \\ 2  x_1 + x_2 + x_5 = 22 \\ x_1, x_2, x_3, x_4, x_5 \geq 0

目的関数が最小値を取るとき、このスラック変数 x_3, x_4, x_5 はそれぞれ 0, 0, 4 の値を取ります。

fun: -18.0

目的関数の最小値です。

x: array([ 6., 6.])

目的関数が最小値を取るとき、決定変数 x_1, x_2 はともに 6 を取ります。

nit: 2

nit number of iterations のことで、シンプレクス法のイテレーション数です。

補足

線形計画問題を解くためには SciPy よりも PuLP を使っている人のほうが多いように見受けられます。

現在のところ、ソルバーとしてシンプレクス法しか対応していません。

目的関数で最大値を求めることはできません。
-1 をかけて、最小値問題に帰着させます。

最適結果オブジェクト(上の例では res) からは、各種属性 x, slack, success, status, nit, message に対して res.slackというようにしてアクセスできます。

参考リンク

情報検索の評価についてメモ(適合率,再現率,F値)

あるモデルによって情報を分類した時に、どのくらいうまく分類しているのか評価するためのメトリクスについてメモ。

テーマを単純にするために、文書から関連する文書を探すような情報検索システムを考える。したがって、関連する・関連しないの二値分類。

Precisionrecall

適合率(precision)

探した文書に含まれる関連文書の割合。
どれだけ正確に関連文書を探せているかを判定。

precision_calc

再現率(recall)

関連文書をどこまで探し出せているか。
網羅性を判定。

recall_calc

F値(F-score, F-measure, F_1 score)

適合率と再現率はトレードオフの関係にあるため、調和平均してバランスを見るのがF値

f_calc

関連するドキュメントは relevant の頭文字をとって R、関連しないドキュメントは
nonrelevant の頭文字をとって N で表すことにする。

3個だけ関連文書があるとする。

R R N R N N N N N N

例1)極端な例として、システムがすべての文書を関連すると判断した場合

正解 R R N R N N N N N N
検索 1 1 1 1 1 1 1 1 1 1

  • 適合率 = 3 / 10 = 0.3
  • 再現率 = 3 / 3 = 1.0
  • F値 ≒ 0.46

当然ながら再現率は 1.0 で逆に適合率は低い。

例2)極端な例として、システムが関連する1文書だけを関連すると判断した場合

正解 R R N R N N N N N N
検索 1 0 0 0 0 0 0 0 0 0

  • 適合率 = 1 / 1 = 1.0
  • 再現率 = 1 / 3 ≒ 0.33
  • F値 = 0.5

当然ながら適合率は 1.0 で逆に再現率は低い。

例3)システムが関連する2文書・関連しない2文書を関連する判断した場合

正解 R R N R N N N N N N
検索 1 0 1 1 1 0 0 0 0 0

  • 適合率 = 2 / 4 = 0.5
  • 再現率 = 2 / 3 ≒ 0.67
  • F値 = 0.57

F値は例3のバランス型が一番高い。

scikit learnで計算してみる

Pythonの機械学習ライブラリscikit learnにはこれらを計算する関数が存在する

上の例で実際に求めてみる。

In [1]: from sklearn.metrics import precision_score, recall_score, f1_score

In [2]: def ir_metrics(y_true, y_pred):
   ...:         print "true  %s " % y_true
   ...:         print "pred  %s " % y_pred
   ...:         print "precision : %.2f" % precision_score(y_true, y_pred, average='binary')
   ...:         print "recall    : %.2f" % recall_score(y_true, y_pred, average='binary')
   ...:         print "F1        : %.2f" % f1_score(y_true, y_pred, average='binary')
   ...:

In [3]: print "ex1"
ex1

In [4]: y_true = [1, 1, 0, 1, 0, 0, 0, 0, 0, 0]

In [5]: y_pred = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

In [6]: ir_metrics(y_true, y_pred)
true  [1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
pred  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
precision : 0.30
recall    : 1.00
F1        : 0.46

In [7]: print "ex2"
ex2

In [8]: y_pred = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

In [9]: ir_metrics(y_true, y_pred)
true  [1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
pred  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
precision : 1.00
recall    : 0.33
F1        : 0.50

In [10]: print "ex3"
ex3

In [11]: y_pred = [1, 0, 1, 1, 1, 0, 0, 0, 0, 0]

In [12]: ir_metrics(y_true, y_pred)
true  [1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
pred  [1, 0, 1, 1, 1, 0, 0, 0, 0, 0]
precision : 0.50
recall    : 0.67
F1        : 0.57

関連リンク

類似係数(Jaccard/Simpson/Dice)をPythonで求める

語が2つ与えられた時に、どのくらい似ているのか計量評価したいといった目的のために類似指数というのが存在します。

今回は、よく知られていて、かつ、実装の簡単な

  • Jaccard 係数
  • Simpson 係数
  • Dice 係数

を Python で実装します。

これら3つの係数は、0から1までの値を取り、1に近づくほど類似し、0に近づくほど類似していないことを表します。

Jaccard 係数

Jaccard index, Jaccard similarity coefficient などとも呼ばれます。

次の式で表されます。

|X∩Y| / |X∪Y|
  • xとYが完全一致

の場合に1となります。

def jaccard(x, y):
    """
    Jaccard index
    Jaccard similarity coefficient
    https://en.wikipedia.org/wiki/Jaccard_index
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(len(x | y))

Simpson 係数

overlap coefficient, Szymkiewicz-Simpson coefficient などとも呼ばれます。

次の式で表されます。

|X∩Y| / min(|X|, |Y|)
  • XとYが完全一致
  • XがYの部分集合(またはその逆)

の場合に1となります。

def overlap(x, y):
    """
    overlap coefficient
    Szymkiewicz-Simpson coefficient)
    https://en.wikipedia.org/wiki/Overlap_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(min(map(len, (x, y))))

Dice 係数

Dice’s coefficient/Sørensen-Dice coefficient などとも呼ばれます。
次の式で表されます。

2 * |X∩Y| / (|X| + |Y|)

xとYが完全一致

の場合に1となります。

三角不等式を満たさないため、

def dice(x, y):
    """
    Dice's coefficient
    Sørensen-Dice coefficient
    https://en.wikipedia.org/wiki/Dice%27s_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return 2 * len(x & y) / float(sum(map(len, (x, y))))

計算してみる

  • night
  • nacht
  • nuit

の3語に対して、各組み合わせの類似係数を求めてみましょう。

#!/usr/bin/env python
# vim: set fileencoding=utf8 :

def jaccard(x, y):
    """
    Jaccard index
    Jaccard similarity coefficient
    https://en.wikipedia.org/wiki/Jaccard_index
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(len(x | y))

def overlap(x, y):
    """
    overlap coefficient
    Szymkiewicz-Simpson coefficient)
    https://en.wikipedia.org/wiki/Overlap_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return len(x & y) / float(min(map(len, (x, y))))

def dice(x, y):
    """
    Dice's coefficient
    Sørensen-Dice coefficient
    https://en.wikipedia.org/wiki/Dice%27s_coefficient
    """
    x = frozenset(x)
    y = frozenset(y)
    return 2 * len(x & y) / float(sum(map(len, (x, y))))

a = 'night'
b = 'nacht'
c = 'nuit'

for x, y in ((a,b), (a,c), (b, c)):
    print "similarity between [%s] and [%s]" % (x, y)
    print "Jaccard:", jaccard(x, y)
    print "overlap:", overlap(x, y)
    print "dice:", dice(x, y)

実行してみると、次のような結果となりました。

similarity between [night] and [nacht]
Jaccard: 0.428571428571
overlap: 0.6
dice: 0.6
similarity between [night] and [nuit]
Jaccard: 0.5
overlap: 0.75
dice: 0.666666666667
similarity between [nacht] and [nuit]
Jaccard: 0.285714285714
overlap: 0.5
dice: 0.444444444444

その他

今回は類似指数を「語」を対象にしましたが、2つのベクトル間の類似性を求めるなど、広い意味での類似性の抽出に利用出来ます。

関連リンク

MARISA-TrieをコマンドラインとPythonから使う

概要

Matching Algorithm with Recursively Implemented StorAge (MARISA) という Trie に対する高い空間効率とそれなりの時間効率を実現するデータ構造があります。
動的な更新には対応していませんが

  • 辞書引き(Lookup) : 入力文字列が登録されているかどうかを確認
  • 逆引き(Reverse Lookup) : 入力された ID から登録文字列を復元
  • Common Prefix Search : 入力文字列の前半部分に一致する登録文字列を検索
  • Predictive Search : 入力文字列で始まる登録文字列を検索

といった操作が可能です。

今回は marisa-trie 0.2.4 をベースに

  • コマンドラインプログラム
  • Python バインディング

から MARISA を触ってみます。

 Install MARISA

環境は Amazon Linux とします。

まずはC++のプログラムビルドに必要なツール群をインストールします。

$ sudo yum install -y gcc gcc-c++

次に C++ プログラムのよくある手順でインストールします。

$ wget https://marisa-trie.googlecode.com/files/marisa-0.2.4.tar.gz
$ tar zxf marisa-0.2.4.tar.gz
$ cd marisa-0.2.4
$ ./configure
...
marisa 0.2.4 configuration:
-------------------------------
  HOST:      x86_64-unknown-linux-gnu
  CXX:       g++
  CXXFLAGS:  -g -O2
  LDFLAGS:
  PREFIX:    /usr/local

  SSE2:      no
  SSE3:      no
  SSSE3:     no
  SSE4.1:    no
  SSE4.2:    no
  SSE4a:     no
  POPCNT:    no
$ make
$ make check
...
==================
All 5 tests passed

...
$ sudo make install
$ ls -1 /usr/local/bin/
marisa-benchmark
marisa-build
marisa-common-prefix-search
marisa-dump
marisa-lookup
marisa-predictive-search
marisa-reverse-lookup

最後に Python バインディングをインストールします。

marisa-trie には SWIG ベースのバインディングもありますが、今回は pip ベースでインストールできるサードパーティーの marisa-trie をインストールします。

$ pip install marisa-trie

コマンドラインから MARISA を触る

 辞書の構築

まずは辞書を作ります。入力データはスペルチェック用の dict を使います。

$ marisa-build  words.dict
#keys: 479829
#nodes: 618295
size: 1429192

 Lookup

入力文字列が登録されているかどうかを確認します。

$ marisa-lookup  words.dict
monkey
141678    monkey

 Reverse Lookup

入力された ID から登録文字列を復元します。

$ marisa-reverse-lookup words.dict
141678
141678	monkey

 Common Prefix Search
入力文字列の前半部分に一致する登録文字列を検索します。

$ marisa-common-prefix-search words.dict
monkey
5 found
6    m    monkey
191    mo    monkey
2637    mon    monkey
16164    monk    monkey
141678    monkey    monkey

Predictive Search

入力文字列で始まる登録文字列を検索します。

出力は 3語(-n 3)にしぼります。

$ marisa-predictive-search -n 3 words.dict
monk
59 found
16164	monk	monk
141678	monkey	monk
341913	monkey-face	monk

Python から MARISA を触る

次に Python から MARISA を触ります。
先ほどのコマンドラインの操作を Python に読み替えていきます。

辞書の構築

まずは辞書を作ります。入力データはスペルチェック用の dict を使います。

In [1]: import marisa_trie

In [2]: with open("/usr/share/dict/words") as f:
   ...:     trie = marisa_trie.Trie(f.read().splitlines())
   ...:

Lookup

入力文字列が登録されているかどうかを確認します。

以下のいずれかの方法で確認できます。

In [4]: u'awaken' in trie
Out[4]: True

In [5]: trie[u'awaken']
Out[5]: 130909

キーは unicode 型で渡します。string 型で渡すと TypeError が発生します。

In [8]: trie['awaken']
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
 in ()
----> 1 trie['awaken']

TypeError: Argument 'key' has incorrect type (expected unicode, got str)

存在しないキーを渡すと KeyError が発生します。

In [9]: trie[u'awaken-not-exist']
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
 in ()
----> 1 trie[u'awaken-not-exist']

marisa_trie.pyx in marisa_trie.Trie.__getitem__ (src/marisa_trie.cpp:5920)()

marisa_trie.pyx in marisa_trie.Trie.key_id (src/marisa_trie.cpp:5787)()

KeyError: u'awaken-not-exist'

Reverse Lookup

入力された ID から登録文字列を復元します。

In [7]: trie.restore_key(130909)
Out[7]: u'awaken'

Common Prefix Search

入力文字列の前半部分に一致する登録文字列を検索します。

In [10]: trie.prefixes(u'awaken')
Out[10]: [u'a', u'aw', u'awa', u'awake', u'awaken']

イテレーター操作もできます。3件だけ表示させてみましょう。

In [11]: prefixes_iterator = trie.iter_prefixes(u'awaken')

In [12]: for i in range(3):print prefixes_iterator.next()
a
aw
awa

Predictive Search

入力文字列で始まる登録文字列を検索します。

In [13]: trie.keys(u'awaken')
Out[13]:
[u'awaken',
 u'awakener',
 u'awakeners',
 u'awakened',
 u'awakening',
 u'awakeningly',
 u'awakenings',
 u'awakenable',
 u'awakenment',
 u'awakens']

イテレーター操作もできます。3件だけ表示させてみましょう。

In [14]: keys_iterator = trie.iterkeys(u'awaken')

In [15]: for i in range(3):print keys_iterator.next()
awaken
awakener
awakeners

References

tornadoでWebSocketサーバを動かしてみる

  1. Tornado で HTTP サーバを用意
  2. HTML ファイルの JS が WebSocket サーバと通信
  3. ブラウザでこの HTML ファイルを表示。
  4. WebSocket クライアントが WebSocket サーバにメッセージを送信すると、HTML が書き換わる

というようなシナリオを実現するシンプルなデモを作ってみました。

WebSocket Server

サーバには表題の通り Python Tornado を利用します。

パッケージのインストール

Tornado のビルドには Python のヘッダーファイルが必要です。
以下は RedHat 系でのインストール例です。

$ sudo yum install -y python27-devel
$ sudo pip install tornado

コード

クラス Tornado.websocket.WebSocketHandler を継承して WebSocket サーバを実装します。
WebSocket サーバがメッセージを受け取ると、 on_messege ハンドラーが呼びだされます。

import tornado.ioloop
import tornado.web
import tornado.websocket

cl = []

class WebSocketHandler(tornado.websocket.WebSocketHandler):
    def open(self):
        if self not in cl:
            cl.append(self)

    def on_message(self, message):
        for client in cl:
            client.write_message(message)

    def on_close(self):
        if self in cl:
            cl.remove(self)

class MainHandler(tornado.web.RequestHandler):
    def get(self):
        self.render('test_ws.html')

application = tornado.web.Application([
    (r"/", MainHandler),
    (r"/websocket", WebSocketHandler),
])

if __name__ == "__main__":
    application.listen(8080)
    tornado.ioloop.IOLoop.current().start()

HTML/JS ファイル

WebSocket 用の JavaScript は HTML ファイル内にベタッと書きます。

WebSocket クライアント送信されたメッセージは

variable : <span id="variable">default</span>

の箇所に反映されます。


<h1>WebSockets Test</h1>

<script>
  var ws;
  ws = new WebSocket("ws://54.65.113.57:8080/websocket");
  ws.onmessage = function(ev) {
    document.getElementById('variable').innerHTML = ev.data;
  }
</script>


variable : <span id="variable">default</span>


WebSocket Client

クライアントには Python 製の websocket-client を利用します。

パッケージのインストール

pip でインストールします。

$ sudo pip install websocket-client

コード

引数で送信メッセージを受け取り、WebSocket につないでメッセージ送信します。

import sys
from websocket import create_connection
ws = create_connection("ws://localhost:8080/websocket")

if len(sys.argv) > 1:
    message = sys.argv[1]
else:
    message = 'hello world!'

print ws.send(message)
print ws.recv()

ws.close()

実行例

サーバを起動します。

$ python test_ws.py

次にブラウザで HTTP://HOST:8080/ にアクセスします。

この状態で、クライアントプログラムからメッセージ送信します。

$ python test_client.py 'new value'
15
new value

variable の箇所が書き換われば成功です。

tornado-websocket-demo

References

real time/user CPU time/system CPU timeの違いをメモ

time(1) コマンドの出力内容

Linux で time(1) コマンドを実行すると、real time/user CPU time/system CPU timeが出力されます。

$ time prog

real    0m0.200s
user    0m0.098s
sys     0m0.004s

わかるような、わからないようなこの出力される時間の意味についてメモします。

各フィールドについて

Real time について

どの処理に時間がかかっているかはさておき、プログラムの開始から終了までを計測した時間

wall clock timeや wall time と呼ばれることもある。

User CPU time について

プログラムがユーザースペースで CPU が利用された時間

ライブラリコードの実行などがここに含まれます

System CPU timeについて

プログラムがカーネススペースで CPU が利用された時間

システムコール(例えば disk I/O で使う read/write)の実行などがここに含まれます。

User/System CPU time が増えないケース

ネットワークを介するプログラムは、通信の待ちが長いため、 CPU time を合算しても Real time よりはるかに少ない事が多いです。

sleep 処理も CPU は指定時間 idle 状態で busy ではないため、CPU time には加算されません。

Real time < User CPU time となるケース

マルチスレッドプログラムや fork しているプログラムで表示される CPU タイムは、マルチスレッドで言えば、スレッド全体、fork であれば親子の CPU time を合算したものが利用されます。

例えば、マルチコアなマシーンで、マルチスレッドプログラムを実行すると、 Real time < user CPU time となることもあります。

実際にこの動きを確認してみましょう。

検証

検証方法

N コアCPU なマシーンを用意し、負荷テストツール stress でコア数分の CPU に CPU 100% となる負荷を T 秒間かけます。

time でこの負荷を計測すると

  • Real timeは T 秒
  • user CPU time は T x N 秒

となれば期待通りです。

検証環境

4 コアな Linux マシーンがあったので、この上で実験します。

$ cat /proc/cpuinfo | grep processor
processor       : 0
processor       : 1
processor       : 2
processor       : 3

stress で負荷をかける

yumstress パッケージをインストールします。

$ sudo yum install -y stress

10秒間、4CPUに負荷をかけます。

$ time stress -t 10 -c 4

裏で htop コマンドで負荷を確認すると、user CPUが100%ではりついています。

stress htop

実行結果

実際の結果はというと

$ time stress -t 10 -c 4
stress: info: [2712] dispatching hogs: 4 cpu, 0 io, 0 vm, 0 hdd
stress: info: [2712] successful run completed in 10s

real    0m10.001s
user    0m39.924s
sys     0m0.000s

ということで想定通り user = real x 4 という結果が得られました。

References

Ubuntu14.04でNFSv4を動かしてみる

ゴール

  • nfs-server
  • nfs-client

というホスト名の Ubuntu 14.04 のサーバを2台用意し、nfs-server サーバに Network File System バージョン 4(以下 NFSv4) を構築、nfs-client サーバからマウントしてみる。

NFSv4 サーバを構築

まずは nfs-server に NFSv4 サーバを構築します。

必要なパッケージのインストール

NFS サーバに必要な nfs-kernel-server パッケージをインストールします。

$ sudo apt-get install nfs-kernel-server

nfs-kernel-server は NFSv3 にも対応しているようですが、今回は NFSv4 として利用します。

共有ディレクトリを作成

次に共有ディレクトリを作成します。
今回は

  • /tmp/no_root_squash
  • /tmp/root_squash
  • /etc

を共有します。
ディレクトリが存在しない /tmp 以下のディレクトリを作成します。

$ sudo mkdir -p /tmp/no_root_squash
$ sudo chown nobody:nogroup /tmp/no_root_squash
$ sudo mkdir -p /tmp/root_squash
$ sudo chown nobody:nogroup /tmp/root_squash

共有ディレクトリを bind mount する

NFSv3 では export するディレクトリごとに export していましたが、NFSv4 では擬似的に 1 ディレクトリにまとめ(pseudo file system)、実際に共有されるディレクトリは擬似ファイルシステム以下に bind マウントするのがお作法なようです。
今回はこの pseudo file system を /export とします。

# create nfs shared directories

$ sudo mkdir -p /export
$ sudo mkdir -p /export/etc
$ sudo mkdir -p /export/no_root_squash
$ sudo mkdir -p /export/root_squash

# bind mount

$ sudo mount --bind /tmp/no_root_squash /export/no_root_squash
$ sudo mount --bind /tmp/root_squash /export/root_squash
$ sudo mount --bind /etc /export/etc

バインドマウントできているかチェックしましょう。

$ mount | grep bind
/tmp/no_root_squash on /export/no_root_squash type none (rw,bind)
/tmp/root_squash on /export/root_squash type none (rw,bind)
/etc on /export/etc type none (rw,bind)

問題なさそうですね。

共有ディレクトリを export する

次に共有ディレクトリを export します。

/etc/exports を以下のように書き換えます。

$ cat /etc/exports
/export                 *(rw,sync,no_subtree_check,fsid=0,no_subtree_check)
/export/no_root_squash  *(rw,sync,no_root_squash,no_subtree_check)
/export/root_squash     *(rw,sync,no_subtree_check)
/export/etc             *(ro,sync,no_subtree_check)

ルート /exportfsid=0オプションが重要です。

nfs-server で共有しているディレクトリ /export はクライアントからは

  • NFSv3 では nfs-server:/export のようにフルパスで見えていましたが
  • NFSv4 では fsid=0 とかくと nfs-server:/ として見えるようになります。

fsid=/export と書いても同じ意味になります。

この設定を exportfs で NFS テーブルに反映します。

$ sudo exportfs -av
exporting *:/export/etc
exporting *:/export/root_squash
exporting *:/export/no_root_squash
exporting *:/export
$ cat  /var/lib/nfs/etab # NFS テーブル
/export/etc     *(ro,sync,wdelay,hide,nocrossmnt,secure,root_squash,no_all_squash,no_subtree_check,secure_locks,acl,anonuid=65534,anongid=65534)
/export/root_squash     *(rw,sync,wdelay,hide,nocrossmnt,secure,root_squash,no_all_squash,no_subtree_check,secure_locks,acl,anonuid=65534,anongid=65534)
/export/no_root_squash  *(rw,sync,wdelay,hide,nocrossmnt,secure,no_root_squash,no_all_squash,no_subtree_check,secure_locks,acl,anonuid=65534,anongid=65534)
/export *(rw,sync,wdelay,hide,nocrossmnt,secure,root_squash,no_all_squash,no_subtree_check,secure_locks,acl,fsid=0,anonuid=65534,anongid=65534)

NFS サーバを起動します。

$ sudo service nfs-kernel-server start
 * Exporting directories for NFS kernel daemon...
   ...done.
 * Starting NFS kernel daemon
   ...done.

showmount コマンドで export されていることを確認します。

$ showmount  -e
Export list for nfs-server:
/export/etc            *
/export/root_squash    *
/export/no_root_squash *
/export                *

クライントから共有ディレクトリをマウント

次に nfs-client から export された共有ディレクトリをマウントします。

必要なパッケージのインストール

NFS マウント操作に必要な パッケージをインストールします。

$ sudo apt-get install nfs-common

export されているディレクトリを確認

$ showmount  -e nfs-server
Export list for nfs-server:
/export/etc            *
/export/root_squash    *
/export/no_root_squash *
/export                *

h3>NFS マウント

nfs-server の共有ディレクトリをマウントします。
export 時の fsid=0 オプションのおかげで、サーバ側のパス指定は / とだけ記載します。

$ sudo mkdir -p /mnt/nfs
$ sudo mount -t nfs4 nfs-server:/ /mnt/nfs
$ mount -t nfs4
nfs-server:/ on /mnt/nfs type nfs4 (rw,addr=10.0.8.101,clientaddr=10.0.8.102)

NFS マウントしたディレクトリを操作

試しに書き込んで見ましょう。

$ sudo touch /mnt/nfs/etc/foo
touch: cannot touch `/mnt/nfs/etc/foo': Read-only file system
$ sudo touch /mnt/nfs/no_root_squash/foo
$ sudo touch /mnt/nfs/root_squash/foo

export 時に ro のリードオンリーオプションでエクスポートした /etc はエラーメッセージどおり書き込みに失敗します。

root squash の確認

セキュリティ対策として、リモートサーバ(今回のケースでは nfs-server)のファイルを root 権限で好き勝手にいじれないように、リモートでの操作にはより権限の低いユーザー識別子を割り当てる機能があります。
この機能を root squash とよび NFS では export 時のオプション(root_squash/no_root_squash)で指定します。

  • root_squash
  • no_root_squash

に書き込まれたファイルのオーナーを確認します。

$ ls -l /tmp/no_root_squash/
total 0
-rw-r--r-- 1 root root 0 Aug  9 01:52 foo
$ ls -l /tmp/root_squash/
total 0
-rw-r--r-- 1 nobody nogroup 0 Aug  9 01:52 foo
  • root_squash オプションで export した /tmp/root_squash はで権限の低い nobody:nogroup
  • no_root_squash オプションで export した /tmp/no_root_squash ではクライアントの書き込みユーザと同じ root:root

となっています。

当然ながら、root:root 権限のファイルは root_squash が有効な状態はファイル更新できません。

$ ll /mnt/nfs/root_squash/
total 12
drwxr-xr-x 2 nobody nogroup 4096 Aug  9 04:28 ./
drwxr-xr-x 5 root   root    4096 Aug  9 01:25 ../
-rw-r--r-- 1 nobody nogroup    0 Aug  9 01:52 foo
-rw-r--r-- 1 root   root       0 Aug  9 03:28 root
$ sudo touch /mnt/nfs/root_squash/root
touch: cannot touch `/mnt/nfs/root_squash/root': Permission denied

/etc/fstab でマウント

毎回 mount コマンドを実行するのはだるいので、/etc/fstab を修正します。

$ cat /etc/fstab
LABEL=cloudimg-rootfs   /        ext4   defaults        0 0
nfs-server:/    /mnt/nfs        nfs4    auto,intr       0 0
  • auto オプションは、システム起動時に自動的にマウントするオプションです。
  • intr オプションは、 NFS のファイル操作中に割り込みを受け付けるオプションです。

オプションの詳細は NFS(5) をご確認ください。

# 一旦既存のマウントをアンマウント

$ sudo umount /mnt/nfs

#  /etc/fstab の設定に従いマウント

$ sudo mount -a

# マウント状態を確認

$ mount -t nfs4
nfs-server:/ on /mnt/nfs type nfs4 (rw,intr,addr=10.0.8.101,clientaddr=10.0.8.102)

ということで期待どおりにマウントされています。

参考

AWS CLIにオレオレwaitコマンドを追加する

aws
aws cliには API 呼び出し後、特定のステータスになるまでポーリングする wait コマンドがあります。
例えば ec2 インスタンスを起動する API を呼び出し後、インスタンスの起動が完了するまで待つには $ aws ec2 wait instance-running --instance-ids xxx のようにします。

この wait 機能が実装されるまでは

#!/bin/bash
instance_id=$(aws ec2 run-instances –image-id ami-12345 \
  --query Reservations[].Instances[].InstanceId \
  --output text)
instance_state=$(aws ec2 describe-instances –instance-ids $instance_id
  --query 'Reservations[].Instances[].State.Name')
while [ "$instance_state" != "running" ]
do
  sleep 1
  instance_state=$(aws ec2 describe-instances –instance-ids $instance_id \ --query 'Reservations[].Instances[].State.Name')
done

というように、ポーリング処理を自前で実装しなければいけ ませんでした(例外処理も真面目にやるとさらにごちゃごちゃする)。

この wait 系コマンドを独自追加する方法をメモ。

cloudformationでスタック構築完了を待つ

例として cloudformation でスタックの作成APIをたたいたあと
(crete-stack)、スタックの構築が完了するまでポーリングするコマンド $ aws cloudformation wait stack-completed を実装してみましょう。

AWS CLI で wait を使わず cloudformation のスタックを構築

wait を使わずに cloudformation のスタックを構築するには

  • $ aws cloudformation create-stack --stack [STACKNAME] でスタックの作製命令をし
  • $ aws cloudformation describe-stacks --stack-name [STACKNAME] で StackStatus が CREATE_COMPLETE になるかチェックすることになるかと思います。
$ aws cloudformation create-stack --stack-name SampleStack --template-body file://SNSToSQS.template \
  --parameters ParameterKey=MyPublishUserPassword,ParameterValue=password \
  ParameterKey=MyQueueUserPassword,ParameterValue=password \
  --capabilities CAPABILITY_IAM
{
    "StackId": "arn:aws:cloudformation:us-east-1:01234:stack/SampleStack/30811fd0-1215-11e5-aacf-50018ffe9e62"
}

$ aws cloudformation describe-stacks --stack-name SampleStack
{
    "Stacks": [
        {
            "StackId": "arn:aws:cloudformation:ap-northeast-1:01234:stack/SampleStack/db83f660-3753-11e5-a35a-50fa594fb836",
            "Description": "...",
            "Parameters": [
                {
                    "ParameterValue": "****",
                    "ParameterKey": "MyPublishUserPassword"
                },
                {
                    "ParameterValue": "****",
                    "ParameterKey": "MyQueueUserPassword"
                }
            ],
            "Tags": [],
            "CreationTime": "2015-08-01T07:15:00.948Z",
            "Capabilities": [
                "CAPABILITY_IAM"
            ],
            "StackName": "SampleStack",
            "NotificationARNs": [],
            "StackStatus": "CREATE_IN_PROGRESS",
            "DisableRollback": false
        }
    ]
}
$ aws cloudformation describe-stacks --stack-name SampleStack
{
    "Stacks": [
        {
            ...,
            "StackName": "SampleStack",
            "StackStatus": "CREATE_COMPLETE",
            ...,
        }
    ]
}

AWS CLI wait に落としこむ

では、これを AWS CLI の wait コマンドに落としこんでみましょう。

ポイント AWS CLI はデータドリブンであるということです。
API のリクエスト/レスポンスは JSON ファイル(データ)でモデル定義します。

wait コマンドも例外ではなく

  • wait のコマンド名
  • ポーリング時にステータスチェックするコマンド
  • ポーリング間隔

などを JSON で定義します。

天下り的になりますが、cloudformation の stack-completed wait 用の JSON モデルは次のようになります。

{
  "version": 2,
  "waiters": {
    "StackCompleted": {
      "operation": "DescribeStacks",
      "delay": 30,
      "maxAttempts": 30,
      "acceptors": [
        {
          "expected": 200,
          "argument": "Stacks[].StackStatus",
          "expected": "CREATE_COMPLETE",
          "state": "success",
          "matcher": "pathAll"
        }
      ]
    }
  }
}

重要な箇所をかいつまんで説明します。

StackCompleted が wait のコマンド名。
AWS Web API のメソッド名は CamelCase なので、モデルでもそのようにします。
AWS CLI から使うときは FooBar は foo_bar のように変換されるので、 StackCompletedstack_completed となります。

"operation": "DescribeStacks" はポーリング時に問い合わせる API です。

"delay": 30 はポーリング間隔です。単位は秒です。

"maxAttempts": 30 はポーリングのリトライ数です。
この数を超えても適切な状態に遷移しなかった場合、ステータスコード 255 で AWS CLI のプロセスが終了します。

"acceptors" のブロックは "operation"(DescribeStacks) のレスポンスに対する処理を記述します。
今回のケースでは StackStatus が CREATE_COMPLETE に遷移した時に wait 完了と判断します。
より具体的には API DescribeStacks に対するレスポンスボディー

{
    "Stacks": [
        {
            ...,
            "StackName": "SampleStack",
            "StackStatus": "CREATE_COMPLETE",
        }
    ]
}

に対して JMESPATHStacks[].StackStatus というようにステータス を抽出し、期待値 CREATE_COMPLETE と一致するか判定します。
JMESPATH の expressionargument で、期待値を expected で記述します。

"state": "success" により、条件が満たされた時は正常終了します。

"expected": 200 は HTTP レスポンスステータスです。

この JSON ファイルを botocore の cloudformation 用モデル定義ディレクトリ botocore/data/cloudformation/2010-05-15waiters-2.json という名前で新規作成します。
(ec2 などと異なり cloudformation には wait が未定義なので新規ファイルとして作成します)

結果的に、以下の様なファイル構成になります。

botocore/data/cloudformation/
└── 2010-05-15
    ├── paginators-1.json
    ├── service-2.json
    └── waiters-2.json # <- NEW!

botocore のディレクトリは SHELL から以下のコマンドで確認できます。

$ python -c 'import botocore;print (botocore.__file__)'
/Users/jsmith/venv/lib/python2.7/site-packages/botocore/__init__.pyc

オレオレ wait を使ってみる

それでは追加した wait コマンドを実際に使ってみましょう。

ヘルプメッセージの表示

まずはヘルプコマンドを確認

$ aws cloudformation wait help
WAIT()                                                                  WAIT()

NAME
       wait -

DESCRIPTION
       Wait until a particular condition is satisfied.

AVAILABLE COMMANDS
       o stack-completed

                                                                        WAIT()

$ aws cloudformation wait stack-completed help
STACK-COMPLETED()                                            STACK-COMPLETED()

NAME
       stack-completed -

DESCRIPTION
       Wait  until JMESPath query Stacks[].StackStatus returns CREATE_COMPLETE
       for all elements when polling with describe-stacks. It will poll  every
       30  seconds  until  a successful state has been reached. This will exit
       with a return code of 255 after 30 failed checks.

SYNOPSIS
            stack-completed
          [--stack-name <value>]
          [--cli-input-json <value>]
          [--starting-token <value>]
          [--max-items <value>]
          [--generate-cli-skeleton]

OPTIONS
       --stack-name (string)
          The name or the unique stack ID that is associated with  the  stack,
          which are not always interchangeable:
       ...

ヘルプは問題なさそうです。

stack-completed は内部的には action で定義したように describe-stacks を呼び出しているだけなので describe-stacks の引数(--stack-name)がそのまま使えます。

スタックの作製

次の実際にスタックを作成して、wait コマンドで構築完了を待ちます。
SNS/SQS を構築する次のテンプレートを利用します。

$ aws cloudformation create-stack --stack-name SampleStack --template-body file://SNSToSQS.template \
  --parameters ParameterKey=MyPublishUserPassword,ParameterValue=password \
  ParameterKey=MyQueueUserPassword,ParameterValue=password \
  --capabilities CAPABILITY_IAM
$ aws cloudformation wait stack-completed --stack-name SampleStack --debug

wait 実行時に --debug オプションをつけると delay で指定した間隔で DescribeStacks を実行しているのがよく分かるかと思います。

エラー処理の強化

--stack-name に存在しないスタック名を指定すると、次のようにエラーが発生します。

$ aws cloudformation wait stack-completed --stack-name NXStackName

Waiter StackCompleted failed: Unexpected error encountered.

--debug オプションをつけてレスポンスを確認すると、

<ErrorResponse xmlns="http://cloudformation.amazonaws.com/doc/2010-05-15/">
  <Error>
    <Type>Sender</Type>
    <Code>ValidationError</Code>
    <Message>Stack with id SampleStack2 does not exist</Message>
  </Error>
  <RequestId>12345</RequestId>
</ErrorResponse>

というようなレスポンスが返ってきており、先ほど作成したモデルではこのようなレスポンスを考慮していません。

JSON ファイルの acceptorsValidationError 用のモデルを追加します。

{
  "version": 2,
  "waiters": {
    "StackCompleted": {
      "delay": 30,
      "operation": "DescribeStacks",
      "maxAttempts": 30,
      "acceptors": [
        {
          "expected": 200,
          "argument": "Stacks[].StackStatus",
          "state": "success",
          "expected": "CREATE_COMPLETE",
          "matcher": "pathAll"
        },
        {
          "matcher": "error",
          "expected": "ValidationError",
          "state": "success"
        }
      ]
    }
  }
}

"matcher": "error" でレスポンスの Error ブロックを抽出します。

"expected" : "ValidationError" でエラーコードを突き合わせます。

このように JSON を書き換えた上で再度存在しないスタック名を wait コマンドに食わせると、今度は正常に処理されました。

$ aws cloudformation wait stack-completed --stack-name NXStackName
$ echo $?
0

Stack のステータスはロールバック系など様々なステータスが存在するので、本運用で使うなら例外系処理を中心にもっとまじめに条件を書かないといけません。

boto3 から使ってみる

今回ハック下 botocore の JSONモデルは

でも利用されています。

boto3 は JSON モデルだけでなく botocore パッケージそのものが共有されているので、カスタマイズした botocore を boto3 からも呼び出してみましょう。

import boto3
import botocore

StackName = 'TEST'
Template = 'https://s3.amazonaws.com/cloudformation-templates-us-east-1/SNSToSQS.template'

client = boto3.client('cloudformation')
client.create_stack(
    StackName=StackName,
    TemplateURL=Template,
    Parameters=[
        {
            'ParameterKey': 'MyPublishUserPassword',
            'ParameterValue': 'password'
        },
        {
            'ParameterKey': 'MyQueueUserPassword',
            'ParameterValue': 'password'
        }
    ],
    Capabilities=['CAPABILITY_IAM'],
    )

waiter = client.get_waiter('stack_completed') # your own waiter
waiter.wait(StackName=StackName)

print 'do something'

まとめ

AWS CLI の wait 系コマンドはそれほど熱心にはコマンド追加されていないので、業務で必要なものは botocore をいじる(fork)ことで独自に拡張できることを理解いただけたかと思います。

References

bashでコマンドライン引数にファイルの中身を渡す

標準出力先としてファイル名を指定するのではなく、ファイルの中身(body)を引数として渡すにはどうすればよいのか?

実験用スクリプト

確認のため、次の簡易的なシェルスクリプトで各コマンドライン引数を表示させる。

#!/bin/bash
# test.sh — just dump arguments

for i; do
  echo $i;
done

入力ファイルとしては次のように改行やスペースを含んだ JSON ファイルを渡す

$ cat test.json
{
  "firstName": "John",
  "age": 25,
  "address": {
    "state": "NY",
    "postalCode": "10021-3100"
  }
}

実行コマンド

結果論としては、以下のように printfcat をコンボすればよい

$ ./test.sh foo $(printf '%s' $(cat test.json)) bar
foo
{"firstName":"John","age":25,"address":{"state":"NY","postalCode":"10021-3100"}}
bar

解説

ポイントとなるのは次の箇所

$(printf '%s' $(cat test.json)) 

ここを単純に $(cat test.json) や bash 方言のショートカットである $(< test.json) とすると、改行・スペースを引数の区切りとしてみなされてしまう

$ ./test.sh foo $(cat test.json) bar
foo
{
"firstName":
"John",
"age":
25,
"address":
{
"state":
"NY",
"postalCode":
"10021-3100"
}
}
bar

この問題を回避するために、ファイルの中身全体を1文字列として扱うために printf '%s' でラップさせるというわけ。

Reference

HTTP ベンチマークツール wrk についてメモ

モダンな HTTP ベンチマークツール wkr の簡単な使い方についてメモ。

wrk の特徴は以下。

  • C で書かれている
  • マルチコア CPU を 活かした高負荷をかけられる
  • スレッドと epoll/kqueue のイベントドリブンを活用して負荷をスケールさせる(NOTICE ファイルを読むと Redis Event Library(ae event loop) を拝借しているようです)
  • Lua スクリプトで HTTP クライアントの処理や実行結果のレポートをカスタマイズできる

Installing wrk in CentOS 6

まずはビルドに必要なパッケージをインストールします。

$ sudo yum install git
$ sudo yum groupinstall 'Development Tools'
$ sudo yum install openssl-devel

openssl-devel をインストールしていないと、make 時に以下のようなエラーが発生します。

In file included from src/wrk.c:3:
src/wrk.h:11:25: error: openssl/ssl.h: No such file or directory
src/wrk.h:12:25: error: openssl/err.h: No such file or directory

次にソースコードから wrk をビルドします。

$ git clone https://github.com/wg/wrk.git
Initialized empty Git repository in /root/wrk/.git/
remote: Counting objects: 792, done.
remote: Total 792 (delta 0), reused 0 (delta 0), pack-reused 792
Receiving objects: 100% (792/792), 1.12 MiB | 147 KiB/s, done.
Resolving deltas: 100% (430/430), done.
$ cd wrk/
$ make
...
$ ls -1
CHANGES
LICENSE
Makefile
NOTICE
README
SCRIPTING
deps
obj
scripts
src
wrk <- Compiled Binary

Usage

$ ./wrk --help
Usage: wrk<options> <url>
  Options:
    -c, --connections <N>  Connections to keep open
    -d, --duration    <T>  Duration of test
    -t, --threads     <N>  Number of threads to use

    -s, --script      <S>  Load Lua script file
    -H, --header      <H>  Add header to request
        --latency          Print latency statistics
        --timeout     <T>  Socket/request timeout
    -v, --version          Print version details

  Numeric arguments may include a SI unit (1k, 1M, 1G)
  Time arguments may include a time unit (2s, 2m, 2h)
$ ./wrk -t12 -c400 -d30s -H"User-Agent: MyBrowser" --latency --timeout 5 http://127.0.0.1:80/index.html
Running 30s test @ http://127.0.0.1:80/index.html
  12 threads and 400 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency   218.81ms  474.65ms   4.64s    85.41%
    Req/Sec     1.20k     1.09k    7.99k    83.74%
  Latency Distribution
     50%  247.00us
     75%   12.20ms
     90%  999.45ms
     99%    1.81s
  249092 requests in 30.10s, 201.67MB read
  Socket errors: connect 0, read 28, write 0, timeout 25
Requests/sec:   8275.51
Transfer/sec:      6.70MB

上の例では

  • 12 スレッド(-t12)
  • 同時 400 コネクション(-c400)
  • 負荷は 30 秒かける(-d30s)
  • リクエストヘッダー “User-Agent: MyBrowser” を送信(-H"User-Agent: MyBrowser")
  • 通信は5秒でタイムアウト(--timeout 5)
  • ベンチマーク結果にレイテンシの統計情報も表示(--Latency)
  • リクエスト先は http://127.0.0.1:80/index.html

というようになっています。

wrk scripting

wrk は Lua スクリプトで

  • setup フェーズ(スレッド単位のカスタマイズ)
  • running フェーズ(リクエスト単位のカスタマイズ)
  • done フェーズ(レポート処理)

の各フェーズで処理やグローバル変数をカスタマイズできます。

実行環境はスレッドごとに独立しています

Lua スクリプトの詳細は次のファイルを参照

https://github.com/wg/wrk/blob/master/SCRIPTING

Lua スクリプト読み込み例

$ wrk -s /path/to/program.lua URL

というように -s オプションで指定します。
複数指定した場合、一番最後のスクリプトが利用される模様。

サンプルスクリプトの説明

ソースコードの wrk/scripts 以下にサンプルコードが転がっているので、各スクリプトを手短に解説します。
特に次の2つが参考になるかと思います。

  • post.lua
  • setup.lua

addr.lua

wrk.lookup(POSIX getaddrinfo に相当) を setup フェーズで実行し、接続先ホストの IP アドレスをランダムに決定する例
ホストに複数の IP が割り当てられていないと意味を成さない。

auth.lua

running フェーズで response 変数を使い、レスポンスヘッダーの特定のフィールドを次回以降のリクエストで活用する例。

counter.lua

running フェーズで request 関数を使い、リクエストごとにカウンターをインクレメントしてリクエストヘッダーに渡す例

delay.lua

running フェーズで delay 関数を使い、リクエスト前にランダムに遅延を発生させる例。

pipeline.lua

running フェーズで init 関数を使い、HTTP パイプラインする例。

https://en.wikipedia.org/wiki/HTTP_pipelining

post.lua

連想配列(Lua で言うところの Table) を書き換えて、HTTPリクエストのリクエストに含まれる

  • Method
  • Body
  • Request Header

を書き換える例。
コマンドラインからは GET メソッドで URL しか渡せないので、実試験では重宝します。

report.lua

done フェーズで done 関数を使い、実行結果をカスタマイズする例。

setup.lua

一番参考にすべき例。
setup/running/done のすべてのフェーズをカスタマイズ。
スレッドごとに番号を振り、running フェーズでリクエスト数をカウントし、done フェーズでスレッド単位の総リクエスト数を出力。

$ ./wrk -s ./scripts/setup.lua -c3 -d 3s -t 3 http://localhost:80/index.html
thread 1 created
thread 2 created
thread 3 created
Running 3s test @ http://localhost:80/index.html
  3 threads and 3 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     2.47ms    4.19ms  28.29ms   84.44%
    Req/Sec     2.94k   618.72     4.64k    65.56%
  26510 requests in 3.04s, 21.46MB read
Requests/sec:   8732.85
Transfer/sec:      7.07MB
thread 1 made 9130 requests and got 9128 responses
thread 2 made 8930 requests and got 8929 responses
thread 3 made 8454 requests and got 8453 responses

stop.lua

running フェーズで stop 関数を使い、リクエスト数がしきい値を超えたら終了させる例。

補足

負荷試験中の名前解決について

The setup phase begins after the target IP address has been resolved and all threads have been initialized but not yet started.
https://github.com/wg/wrk/blob/master/SCRIPTING

とあるように running フェーズでは名前の再解決をしない。
負荷とともに IP が変わるようなケースでは注意をすること。

listen(2) backlog

To handle the initial connection burst the server’s listen(2) backlog should be greater than the number of concurrent connections being tested.
https://github.com/wg/wrk/blob/master/README

TODO

References