mog project: 2015.06

6.28.2015

Ansible: Installing Graphite + Grafana 2

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

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

mog project: Ansible: Visualizing CloudWatch Metrics with Grafana
過去の状態はこちらのブランチに移動: mogproject/example-ansible-grafana at blog-2014-11-05

主な対応内容

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

セットアップ手順

README 参照。

mogproject/example-ansible-grafana

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

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

References

What's New in Grafana v2.0 - Grafana Documentation

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

Counting the number of True Booleans in a Python List - Stack Overflow

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: デバッグ用のコマンド

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型のカウントとして得られる値である。

6.06.2015

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

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

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

mogproject/easy-scala-bench

前提条件

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

Shell Script Cheat Sheet

6.02.2015

Implement MurmurHash in Scala

Scala: MurmurHash を実装する

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

redis/hyperloglog.c at 3.0 · antirez/redis

コード

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

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)

mog project: HyperLogLog Implementation in Redis, pt.2

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

に対応している。

mog project: HyperLogLog Implementation in Redis, pt.1

登録: 投稿 (Atom)

6.28.2015

主な対応内容

セットアップ手順

References

6.22.2015

References

tl;dr

具体例

ソースコード

カタログの作成

カタログのコンパイル

実行結果

References

6.09.2015

要素の追加

データのマージ

dense 表現について

Related Posts

6.07.2015

カウントの求め方

具体的な例

期待値の補正

Related Posts

6.06.2015

前提条件

使い方

実行例

ワンライナー

for ループ

実行例

References

6.02.2015

コード

実行例

6.01.2015

ハッシュ関数とレジスタ

レジスタ値の求め方

ランレングス圧縮

ZERO

XZERO

VAL

読み解いてみる

Related Posts