6.28.2015

Ansible: Installing Graphite + Grafana 2

Ansible: Graphite + Grafana 2系をインストールする Playbook

 

以前作った Playbook が最新の Amazon Linux に対応できなくなっていたので更新。

主な対応内容

  • Amazon Linux のデフォルトの Python バージョンが、いつの間にか 2.7 に上がっていた。
    yum でインストールされる Python ライブラリは 2.6 向けにパッケージングされているので使えない。
  • インストールパスを標準準拠に。カスタマイズ箇所を最小限に留めるよう意識した。
  • MySQL の使用もやめた
  • Grafana 2系の導入
    • WebサービスやDBが内包されている。つまり Nginx, ElasticSearch も不要になった

セットアップ手順

README 参照。

色々ハマリどころも多かったが、いったん Playbook に反映。プロビジョニングしてすぐにグラフが作れるようになった。

 

s

S

 

ただし、Graphite はやはり依存関係が複雑で保守性が悪いので、今後は Grafana + InfluxDB の組み合わせを選択するのが主流になりそう。

 

References

Troubleshooting Guide for SSH Connection Error

SSH接続エラーのトラブルシューティング情報まとめ

 

SSH の接続に失敗する場合の対処方法の自分用メモ。随時更新していく。

6.22.2015

Counting True in the Python List

Python: リスト内の True の個数を数える

 

sum を使えば、True: 1, False: 0 としてカウントされるので便利。

>>> [False, True, True, False, True].count(True)
3
>>> sum([False, True, True, False, True])
3
>>> sum(x % 2 == 1 for x in range(5))
2

 

 

References

How to Internationalize Messages in Python

Python アプリケーション内のメッセージの国際化 (i18n) について

 

思ったよりも面倒だったのでメモ。

 

tl;dr

  • GNU gettext API よりも クラスベース API が推奨されている
  • ロケール辞書の置き場所が必要
  • 翻訳対象のメッセージにマーク _('text') を付けてアプリケーション・コードを書く
  • ソースコードからカタログ(.po)を作成する。
    これを実現するツールは lingua, babel, po-utils, xpot, xgettext など多数ある模様。
  • カタログを編集して翻訳後の文字列を記述し、コンパイルしてバイナリファイル(.mo)を作成。
    そして所定の位置に配備する。

 

具体例

 

ソースコード
import gettext

_ = gettext.translation('hello_i18n', 'locale', fallback=True).ugettext

print(_('hello i18n'))
print(_('hello %(world)s') % {'world': 'i18n'})

 

カタログの作成

今回は、xgettext + msgfmt で実現する。

### Macの場合
$ brew install gettext

### バージョンは環境に合わせて適宜変更
$ /usr/local/Cellar/gettext/0.19.4/bin/xgettext --language=python --from-code=UTF-8 \
--keyword=_ --add-comments=NOTE -o hello_i18n.po hello_i18n.py

$ vi hello_i18n.po
# SOME DESCRIPTIVE TITLE.
# Copyright (C) YEAR THE PACKAGE'S COPYRIGHT HOLDER
# This file is distributed under the same license as the PACKAGE package.
# FIRST AUTHOR , YEAR.
#
#, fuzzy
msgid ""
msgstr ""
"Project-Id-Version: PACKAGE VERSION\n"
"Report-Msgid-Bugs-To: \n"
"POT-Creation-Date: 2015-06-21 23:48+0900\n"
"PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
"Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
"Language-Team: LANGUAGE <LL@li.org>\n"
"Language: \n"
"MIME-Version: 1.0\n"
"Content-Type: text/plain; charset=UTF-8\n"
"Content-Transfer-Encoding: 8bit\n"

#: hello_i18n.py:5
msgid "hello i18n"
msgstr "こんにちは i18n"

#: hello_i18n.py:6
#, python-format
msgid "hello %(world)s"
msgstr "%(world)s、こんにちは"

 

カタログのコンパイル
$ mkdir -p locale/ja_JP/LC_MESSAGES
$ /usr/local/Cellar/gettext/0.19.4/bin/msgfmt -o locale/ja_JP/LC_MESSAGES/hello_i18n.mo \
./hello_i18n.po

 

実行結果
$ python2 ./hello_i18n.py
こんにちは i18n
i18n、こんにちは
$ LC_ALL=C python2 ./hello_i18n.py
hello i18n
hello i18n

 

GNU gettext との結び付きが強すぎるし、コンパイルが必須なのもあって、あまり使う気がしない設計という印象。

 

References

6.09.2015

HyperLogLog Implementation in Redis, pt.4

Redis: HyperLogLog の実装について その4

 

その他のトピック。

 

要素の追加

追加する要素のハッシュを求め、インデックスと base-2 rank を求める。
各インデックスごとにより大きい値をレジスタに保存するだけ。

 

データのマージ

$2^{14}$ 個の全てのレジスタを走査し、各位置に対して値の大きいほうを保持する。
非常に高速なマージ処理も HyperLogLog の特長である。

 

dense 表現について

dense 表現では、sparse 表現と異なり、全部のインデックスの値が配列的に保持されている。

Redis では以下のような構造のバイト配列を定義することで、メモリ使用量を圧縮している。
(各レジスタの値は 0〜50 の範囲内であるため、それぞれ 6 ビットで表現可能)

 * +--------+--------+--------+------//
 * |11000000|22221111|33333322|55444444
 * +--------+--------+--------+------//

sparse から dense へ変換が行われるタイミングは以下。

  • PFADD
    • 追加する要素の base-2 rank が 33 以上だった場合 (sparse では表現不可)
    • sparse 表現の使用サイズが サーバ変数 server.hll_sparse_max_bytes を超えた場合
      (デフォルトは 3000)

  • PFMERGE: マージ実行後は必ず dense 表現になる
  • PFDEBUG TODENSE key: デバッグ用のコマンド

 

 

Related Posts

6.07.2015

HyperLogLog Implementation in Redis, pt.3

Redis: HyperLogLog の実装について その3

 

前回は sparse 表現のバイナリについて中身をざっと見た。

今回は HyperLogLog の目的である、カーディナリティを求める処理 pfcount についてその実装を確かめてみる。

 

カウントのコア部分の処理は hllCount 関数に記述されている。

 

カウントの求め方

論文によれば、カーディナリティの期待値 $E$ は以下のように求められる。

  • レジスタの個数を $m$ とする。Redis の場合 $$m = 2^{14} = 16384$$
  • このとき $$E = \frac{\alpha_{m}m^2}{\sum_{j=1}^{m} 2^{-M^{(j)}}}$$
  • ここで $$\alpha_{m} = \left(m \int_{0}^{\infty} \left(\text{log}_2 \left(\frac{2+u}{1+u}\right)\right)^m du\right)^{-1}$$
    Redis の場合、これは $\alpha_{m} \approx 0.7213 \cdot \left({1 + \frac{1.079}{m}}\right)^{-1} \approx 0.7213$ で近似される。
  • また、$M^{(j)}$ は $j$番目のレジスタの値である。

 

具体的な例

これまで見てきたように、Redis の HyperLogLog 型に "A", "B", "C" という 3つの値を追加すると、レジスタの状態は以下のようになる。

  • index:4477 -> 3 (C)
  • index:12352 -> 1 (A)
  • index:12964 -> 3 (B)
  • 上記以外の index -> 0

この例で実際に $E$ を求めてみる。

  • $2^0 = 1, \qquad 2^{-1} = 0.5, \qquad 2^{-3} = 0.125$ であるから $$\sum_{j=1}^{m} 2^{-M^{(j)}} = 1 \cdot (m-3) + 0.5 \cdot 1 + 0.125 \cdot 2 = 16381.75$$
  • したがって $$E = \frac{\alpha_{m}m^2}{\sum_{j=1}^{m} 2^{-M^{(j)}}} \approx \frac{0.7213 \cdot 16384^2}{16381.75} \approx 11819.40$$

実際のカーディナリティは 3 なので、大きなズレがあるように見える。

期待値の補正

このように、HyperLogLog は小さいカーディナリティに対して大きな誤差が出るという性質がある。
この問題を解決するため、Redis では一旦期待値を算出した後で、以下のルールに従ってその値を補正している。

  • i) $E \lt 2.5 \cdot m = 40960$ かつ 値が 0 であるレジスタが存在する場合

    以下の式 (Redis のコメントには「LINEARCOUNTING アルゴリズム」と書かれている) によって期待値を計算し直す。値が 0 であるレジスタの個数を $z$ として $$E := m \cdot \text{log} \left( \frac{m}{z} \right)$$

    上記の具体例では、$z = 16384 - 3 = 16381$ なので $$E := m \cdot \text{log} \left( \frac{m}{z} \right) = 16384 \cdot \text{log} \left( \frac{16384}{16381} \right) \approx 3.0003$$
    正しいカーディナリティ 3 を得ることができた。

  • ii) i)に該当せず $E \lt 72000$ の場合
    以下の多項式バイアスを適用して期待値を調整している。これは $m = 2^{14}$ の場合に限り適用可能。 $$ \begin{align} bias &= 5.9119 \cdot 10^{-18}E^4 - 1.4253 \cdot 10^{-12}E^3 + 1.2940 \cdot 10^{-7}E^2-5.2921 \cdot 10^{-3}E + 83.3216 \\ E :&= E - E \cdot \frac{bias}{100} \end{align}$$
  • iii) その他の場合は補正なし

こうして得られた値 $E$ を 64ビット非負整数に変換したものが、HyperLogLog型のカウントとして得られる値である。

 

Related Posts

6.06.2015

easy-scala-bench - Run sbt-jmh in Easy Way

easy-scala-bench - 手軽に sbt-jmh を実行する

 

ワン・ライナーないしは数行の Scala スクリプトに対して簡単に JMH でマイクロ・ベンチマークを実行できるようにシェルを書いた。

 

 

前提条件

  • 0.13 系の sbt がインストールされていること
  • Bash (/bin/bash) が使えること

 

使い方

  • リポジトリのクローン
    $ cd your/work/dir
    $ git clone https://github.com/mogproject/easy-scala-bench.git
    $ cd easy-scala-bench
  • 測定したい Scala コードを easy-scala-bench スクリプトの入力に与える
    $ echo 'for (i <- 1 to 1000) for (j <- 1 to 1000) i + j' | ./easy-scala-bench

    これだけ。

    入力をもとに自動的に Scala コード (src/main/scala/Bench.scala) が生成され、
    コマンド sbt 'run -i 3 -wi 3 -f 1 -t 1 easy_scala_bench.Bench' が実行される。

  • 測定対象外の準備コードを書くこともできる
    $ echo '
    val xs = (1 to 1000000).toList
    ====
    xs.length
    ' | ./easy-scala-bench

    準備用コードと計測用コードを「====」(イコール 4個 完全一致) という行で区切れば、区切り以降のコードだけが計測対象になる。

  • シェルスクプトに対してシンボリック・リンクを張っても正しく動作する

    たとえば

    ln -s path/to/easy-scala-bench /usr/local/bin/

    のようにパスの通る場所にリンクを作ってコマンド化してしまえば、実行ファイルのパスを意識する必要がなくなる。

 

実行例

$ echo 'for (i <- 1 to 1000) for (j <- 1 to 1000) i + j' | ./easy-scala-bench
(snip)
[info] Compiling 1 Scala source to /private/tmp/easy-scala-bench/target/scala-2.11/classes...
[info] Generating JMH benchmark Java source files...
Processing 3 classes from /private/tmp/easy-scala-bench/target/scala-2.11/classes with "reflection" generator
Writing out Java source to /private/tmp/easy-scala-bench/target/scala-2.11/generated-sources/jmh and resources to /private/tmp/easy-scala-bench/target/scala-2.11/classes
[info] Compiling generated JMH benchmarks...
[info] Compiling 1 Scala source and 9 Java sources to /private/tmp/easy-scala-bench/target/scala-2.11/classes...
[info] Running org.openjdk.jmh.Main -i 3 -wi 3 -f 1 -t 1 easy_scala_bench.Bench
[info] # JMH 1.9.1 (released 43 days ago)
[info] # VM invoker: /Library/Java/JavaVirtualMachines/jdk1.7.0_75.jdk/Contents/Home/jre/bin/java
[info] # VM options: 
[info] # Warmup: 3 iterations, 1 s each
[info] # Measurement: 3 iterations, 1 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Throughput, ops/time
[info] # Benchmark: easy_scala_bench.Bench.bench
[info]
[info] # Run progress: 0.00% complete, ETA 00:00:06
[info] # Fork: 1 of 1
[info] # Warmup Iteration   1: 120.743 ops/s
[info] # Warmup Iteration   2: 214.615 ops/s
[info] # Warmup Iteration   3: 222.462 ops/s
[info] Iteration   1: 226.371 ops/s
[info] Iteration   2: 230.060 ops/s
[info] Iteration   3: 226.733 ops/s
[info]
[info]
[info] Result "bench":
[info]   227.722 ±(99.9%) 37.095 ops/s [Average]
[info]   (min, avg, max) = (226.371, 227.722, 230.060), stdev = 2.033
[info]   CI (99.9%): [190.626, 264.817] (assumes normal distribution)
[info]
[info]
[info] # Run complete. Total time: 00:00:06
[info]
[info] Benchmark     Mode  Cnt    Score    Error  Units
[info] Bench.bench  thrpt    3  227.722 ± 37.095  ops/s
[success] Total time: 17 s, completed Jun 6, 2015 11:08:17 PM
$ echo '
val xs = (1 to 1000000).toList
xs.length
' | ./easy-scala-bench
(snip)
[info] # Run complete. Total time: 00:00:06
[info]
[info] Benchmark     Mode  Cnt   Score    Error  Units
[info] Bench.bench  thrpt    3  24.990 ± 71.849  ops/s
(snip)
$ echo '
val xs = (1 to 1000000).toList
====
xs.length
' | ./easy-scala-bench
(snip)
[info] # Run complete. Total time: 00:00:07
[info]
[info] Benchmark     Mode  Cnt    Score    Error  Units
[info] Bench.bench  thrpt    3  212.187 ± 35.787  ops/s
(snip)
$ echo '
val xs = (1 to 1000000).toVector
====
xs.length
' | ./easy-scala-bench
(snip)
[info] # Run complete. Total time: 00:00:06
[info]
[info] Benchmark     Mode  Cnt           Score           Error  Units
[info] Bench.bench  thrpt    3  1291414027.800 ± 568908317.371  ops/s
(snip)

How to capture input lines to array in Bash

Bash: 入力された内容を行単位で配列に格納する

 

readarray は互換性が不十分なので使いたくない。
IFS を正しく扱うのがポイント。

 

ワンライナー

IFS=$'\n' lines=($(cat))

 

for ループ

declare -a lines
while IFS= read line; do
    lines+=("$line")
done

 

実行例

bash-3.2$ IFS=$'\n' lines=($(cat))
  a b  c
d
e
        f

g
bash-3.2$ printf '[%s]\n' "${lines[@]}"
[  a b  c]
[d]
[e   ]
[       f       ]
[g      ]
bash-3.2$ lines=()
bash-3.2$ while IFS= read line; do lines+=("$line"); done
  a b  c
d
e
        f

g
bash-3.2$ printf '[%s]\n' "${lines[@]}"
[  a b  c]
[d]
[e   ]
[       f       ]
[]
[g      ]

 

References

6.02.2015

Implement MurmurHash in Scala

Scala: MurmurHash を実装する

 

Redis の MurmurHash2 実装をそのまま Scala で書いてみる。

 

コード

効率よりも分かりやすさを優先。

object MurmurHash {

  private val defaultSeed = 0xadc83b19L

  def murmurHash64A(data: Seq[Byte], seed: Long = defaultSeed): Long = {
    val m = 0xc6a4a7935bd1e995L
    val r = 47

    val f: Long => Long = m.*
    val g: Long => Long = x => x ^ (x >>> r)

    val h = data.grouped(8).foldLeft(seed ^ f(data.length)) { case (y, xs) =>
      val k = xs.foldRight(0L)((b, x) => (x << 8) + (b & 0xff))
      val j: Long => Long = if (xs.length == 8) f compose g compose f else identity
      f(y ^ j(k))
    }
    (g compose f compose g)(h)
  }

}

13行目は、Redis のコードの big endian の場合の分岐に相当。
Byte 型を 0xff と論理積を取れば、非負の Int 値が手に入る。

 

実行例

scala> MurmurHash.murmurHash64A("A".getBytes).toHexString
res1: String = fc089b66b14af040

scala> MurmurHash.murmurHash64A("AB".getBytes).toHexString
res2: String = 24fb508dc42efb7f

scala> MurmurHash.murmurHash64A("ABCDEFGHabcdefgh".getBytes).toHexString
res3: String = 40055074d92b389f

scala> MurmurHash.murmurHash64A(Seq.fill[Byte](100)(-1)).toHexString
res4: String = 78be0c4f11cdc6d5

Redis の HyperLogLog で行われるカウント処理の結果も前回の調査内容と一致した。

scala> def count(x: Long): (Int, Int) = (
     |   (x & ((1L << 14) - 1)).toInt,
     |   (14 until 64).find(i => ((x >>> i) & 1L) != 0L).getOrElse(63) - 13
     | )
count: (x: Long)(Int, Int)

scala> count(MurmurHash.murmurHash64A("A".getBytes))
res7: (Int, Int) = (12352,1)

scala> count(MurmurHash.murmurHash64A("B".getBytes))
res8: (Int, Int) = (12964,3)

scala> count(MurmurHash.murmurHash64A("C".getBytes))
res9: (Int, Int) = (4477,3)

6.01.2015

HyperLogLog Implementation in Redis, pt.2

Redis: HyperLogLog の実装について その2

 

前回、Redis の HyperLogLog に 対して "A", "B", "C" という 3つの文字列を与えると
registers に 0x51, 0x7c, 0x88, 0x5e, 0xc1, 0x80, 0x42, 0x62, 0x88, 0x4d, 0x5a というバイト配列が格納された。

今回は、sparse 表現の実装をより詳しく見ていくことにする。

 

ハッシュ関数とレジスタ

そもそも Redis におけるレジスタとは何なのか。
ソースコードのコメントには、HyperLogLog型のキーは 16,384個の 6ビットレジスタで表現されるとある。

従って、キー 1個あたり
6 bit x 16,384 = 98,304 bit = 12,288 Byte = 12 KB
でカーディナリティが表現されることになる。

 

レジスタ値の求め方

任意のバイト配列から、記録すべきレジスタのインデックスと 6ビットの値を求める手順は以下のとおり。

  • 入力に対して 64ビット版の MurmurHash2 アルゴリズムを適用し、
    ハッシュ値 (64ビット符号無し整数値) を得る
    • MurmurHash とは、衝突困難性と一様性に優れ、MD5 よりも高速なハッシュ関数
    • 実際の実装ではエンディアン・ニュートラル (ビッグエンディアンにもリトルエンディアンにも対応可能) に改変されている
  • ハッシュ値の下位 14ビットの値をレジスタ・インデックスとして使う
    • 0 〜 16383 の値が得られ、何番目の箱にレジスタをセットするかが決まる。
  • ハッシュ値の 下位から数えて 15ビット目から上位へ向かってビットを走査し、初めて「1」が登場する位置を調べる(=「0」のビットが何個連続しているかを数え、1を足す)
    • ただし、最上位のビットにはあらかじめ「1」をセットしておく
    • 1 〜 50 の値が得られ、これがレジスタの値となる
    • この値が 33 以上だった場合、sparse 表現ができないので自動的に dense 表現に変換される。

 

ランレングス圧縮

sparse 表現とは、すなわち上記のレジスタ情報をランレングス圧縮したバイト列である。

それは、Redis 独自の以下3種類のオペコードで構成される。

ZERO

00xxxxxx という 1バイトの表現。
xxxxxx を 6ビットの符号無し整数として解釈し、1 を足す。(1 <= x <= 64 とする)
「x」の個数ぶん、値が「0」のレジスタが連続していることを示す。

XZERO

01xxxxxx yyyyyyyy という 2バイトの表現。
xxxxxxyyyyyyyy を 14ビットの符号無し整数として解釈し、1 を足す。(1 <= x <= 16384 とする)
「x」の個数ぶん、値が「0」のレジスタが連続していることを示す。

VAL

1vvvvvxx という 1バイトの表現。
vvvvv を 5ビットの符号無し整数、xx を 2ビットの符号無し整数として解釈し、それぞれ 1 を足す。
(1 <= v <=32, 1 <= x <= 4 とする)
「x」の個数ぶん、値が「v」のレジスタが連続していることを示す。

 

読み解いてみる

冒頭の例をランレングス圧縮のオペコードに読み替えてみると、以下のようになる。

  • 0x51, 0x7c => 0b01010001, 0b01111100 => XZERO:4477
  • 0x88 => 0b10001000 => VAL:3,1
  • 0x5e, 0xc1 => 0b01011110, 0b11000001 => XZERO:7874
  • 0x80 => 0b10000000 => VAL:1,1
  • 0x42, 0x62 => 0b01000010, 0b01100010 => XZERO:611
  • 0x88 => 0b10001000 => VAL:3,1
  • 0x4d, 0x5a => 0b01001101, 0b01011010 => XZERO:3419

従って、レジスタの状態は index:4477 -> 3、index:12352 -> 1、index:12964 -> 3 がセットされており
他は全てゼロであることがわかった。

レジスタの個数も、4477 + 1 + 7874 + 1 + 611 + 1 + 3419 = 12964 とピッタリ合っている。

実際、入力した 3個の文字列は

  • A: index:12352 -> 1
  • B: index:12964 -> 3
  • C: index:4477 -> 3

に対応している。

 

 

Related Posts