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 の接続に失敗する場合の対処方法の自分用メモ。随時更新していく。

ssh が繋がらないときのトラブルシューティングまとめ

`ssh -vvvv` 出力例

OpenSSH_6.2p2, OSSLShim 0.9.8r 8 Dec 2011
debug1: Reading configuration data /Users/xxx/.ssh/config
debug1: Reading configuration data /etc/ssh_config
debug1: /etc/ssh_config line 20: Applying options for *
debug1: /etc/ssh_config line 53: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to xxx.xxx.xxx.xxx [xxx.xxx.xxx.xxx] port 22.
[[a]]
debug1: Connection established.
debug3: Incorrect RSA1 identifier
debug3: Could not load "/Users/xxx/.ssh/xxx.pem" as a RSA1 public key
debug1: identity file /Users/xxx/.ssh/xxx.pem type -1
debug1: identity file /Users/xxx/.ssh/xxx.pem-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.2
[[b]]
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.2
debug1: match: OpenSSH_6.2 pat OpenSSH*
debug2: fd 3 setting O_NONBLOCK
debug3: load_hostkeys: loading entries for host "xxx.xxx.xxx.xxx" from file "/Users/xxx/.ssh/known_hosts"
debug3: load_hostkeys: found key type RSA in file /Users/xxx/.ssh/known_hosts:106
debug3: load_hostkeys: loaded 1 keys
debug3: order_hostkeyalgs: prefer hostkeyalgs: ssh-rsa-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-rsa
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa-cert-v01@openssh.com,ssh-rsa-cert-v00@openssh.com,ssh-rsa,ssh-dss-cert-v01@openssh.com,ssh-dss-cert-v00@openssh.com,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: hmac-md5-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-ripemd160-etm@openssh.com,hmac-sha1-96-etm@openssh.com,hmac-md5-96-etm@openssh.com,hmac-md5,hmac-sha1,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-ripemd160-etm@openssh.com,hmac-sha1-96-etm@openssh.com,hmac-md5-96-etm@openssh.com,hmac-md5,hmac-sha1,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,zlib@openssh.com,zlib
debug2: kex_parse_kexinit: none,zlib@openssh.com,zlib
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: kex_parse_kexinit: ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: hmac-md5-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-ripemd160-etm@openssh.com,hmac-sha1-96-etm@openssh.com,hmac-md5-96-etm@openssh.com,hmac-md5,hmac-sha1,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-64-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-256-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-ripemd160-etm@openssh.com,hmac-sha1-96-etm@openssh.com,hmac-md5-96-etm@openssh.com,hmac-md5,hmac-sha1,umac-64@openssh.com,umac-128@openssh.com,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,zlib@openssh.com
debug2: kex_parse_kexinit: none,zlib@openssh.com
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: mac_setup: found hmac-md5-etm@openssh.com
debug1: kex: server->client aes128-ctr hmac-md5-etm@openssh.com none
debug2: mac_setup: found hmac-md5-etm@openssh.com
debug1: kex: client->server aes128-ctr hmac-md5-etm@openssh.com none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug2: dh_gen_key: priv key bits set: 129/256
debug2: bits set: 502/1024
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Server host key: RSA xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx
debug3: load_hostkeys: loading entries for host "xxx.xxx.xxx.xxx" from file "/Users/xxx/.ssh/known_hosts"
debug3: load_hostkeys: found key type RSA in file /Users/xxx/.ssh/known_hosts:106
debug3: load_hostkeys: loaded 1 keys
debug1: Host 'xxx.xxx.xxx.xxx' is known and matches the RSA host key.
debug1: Found key in /Users/xxx/.ssh/known_hosts:106
debug2: bits set: 504/1024
debug1: ssh_rsa_verify: signature correct
debug2: kex_derive_keys
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /Users/xxx/.ssh/yyy.pem (0x7fbedbd015f0),
debug2: key: /Users/xxx/.ssh/id_rsa (0x7fbedbd01770),
(snip)
debug2: key: /Users/xxx/.ssh/xxx.pem (0x0), explicit
debug1: Authentications that can continue: publickey
debug3: start over, passed a different list publickey
debug3: preferred publickey,keyboard-interactive,password
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /Users/xxx/.ssh/yyy.pem
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey
debug1: Offering RSA public key: /Users/xxx/.ssh/id_rsa
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey
debug1: Trying private key: /Users/xxx/.ssh/xxx.pem
debug1: read PEM private key done: type RSA
debug3: sign_and_send_pubkey: RSA xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx
debug2: we sent a publickey packet, wait for reply
[[c]]
debug1: Authentication succeeded (publickey).
Authenticated to xxx.xxx.xxx.xxx ([xxx.xxx.xxx.xxx]:22).
debug1: channel 0: new [client-session]
debug3: ssh_session2_open: channel_new: 0
debug2: channel 0: send open
debug1: Requesting no-more-sessions@openssh.com
debug1: Entering interactive session.
debug2: callback start
debug2: fd 3 setting TCP_NODELAY
debug3: packet_set_tos: set IP_TOS 0x10
debug2: client_session2_setup: id 0
debug2: channel 0: request pty-req confirm 1
debug1: Sending environment.
debug3: Ignored env Apple_PubSub_Socket_Render
debug3: Ignored env COMMAND_MODE
debug3: Ignored env DISPLAY
(snip)
debug1: Sending env LANG = ja_JP.UTF-8
debug2: channel 0: request env confirm 0
debug1: Sending env LC_ALL = ja_JP.UTF-8
debug2: channel 0: request env confirm 0
debug3: Ignored env LOGNAME
(snip)
debug3: Ignored env __GIT_PROMPT_DIR
debug2: channel 0: request shell confirm 1
debug2: callback done
debug2: channel 0: open confirm rwindow 0 rmax 32768
debug2: channel_input_status_confirm: type 99 id 0
debug2: PTY allocation request accepted on channel 0
debug2: channel 0: rcvd adjust 2097152
debug2: channel_input_status_confirm: type 99 id 0
debug2: shell request accepted on channel 0
Last login: Sun Jun 28 05:27:51 2015 from xxx.example.com

       __|  __|_  )
       _|  (     /   Amazon Linux AMI
      ___|\___|___|

https://aws.amazon.com/amazon-linux-ami/2015.03-release-notes/
19 package(s) needed for security, out of 47 available
Run "sudo yum update" to apply all updates.
[ec2-user@ip-xxx-xxx-xxx-xxx ~]$

停止箇所別の原因と対策

a: ネットワーク層の疎通に失敗

追加調査

各種ネットワーク層の疎通確認コマンドを実行する

dig host.your.domain.com
traceroute xxx.xxx.xxx.xxx
telnet xxx.xxx.xxx.xxx 22

Msg	原因	対応
-	ホスト名・IPアドレスの入力間違い
-	名前解決(`/etc/hosts`, DNSなど)の失敗
-	ルーティングの失敗	機器(ルータ等)のルーティング設定を見直し
-	ネットワーク経路上のTCPフィルタによる遮断	機器(ルータ等)のフィルタ設定を見直し
-	サーバOS上のセキュリティフィルタによる遮断	サーバ上のセキュリティ(iptables, `/etc/hosts.deny`,SELinux等) を見直し
-	サーバOSが停止している
-	サーバ上で sshd デーモンが起動していない

b: サーバ上の sshd からの応答が返ってこない

追加調査

サーバ上で -d オプションを付けて sshd を起動し、デバッグログを有効にする
サーバのリソース状況(メモリ使用率・CPU使用率・ディスク使用率)を確認する

Msg	原因	対応
-	サーバのリソース不足	メモリなどのリソースに十分な空きがある状態にする

c: SSH認証に失敗

Msg	原因	対応
Received disconnect from xxx.xxx.xxx.xxx: 2: Too many authentication failures for xxx	公開鍵認証以外の試行回数が制限値を超えた	ssh 接続時に `-o IdentitiesOnly=yes` を追加 `~/.ssh/config`に `IdentitiesOnly yes` を追加する対応でもOK
	パスワード認証が行われる前に試行回数が制限値を超えた	ssh 接続時に `-o PreferredAuthentications=password` を追加 `~/.ssh/config`に `PreferredAuthentications password` を追加する対応でもOK
debug1: No more authentication methods to try. Permission denied (publickey).	秘密鍵の指定が正しくない	秘密鍵のパスを確認するサーバ上の `~/.ssh/authorized_keys` と公開鍵の内容が合っているか確認する

view raw SSHTroubleshooting.md hosted with ❤ by GitHub

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)を作成。
そして所定の位置に配備する。

具体例

ソースコード

hello_i18n.pyimport gettext
 
_ = gettext.translation('hello_i18n', 'locale', fallback=True).ugettext
 
print(_('hello i18n'))
print(_('hello %(world)s') % {'world': 'i18n'})

hello_i18n.py
1 2 3 4 5 6	`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

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、こんにちは"

hello_i18n.po
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27	`# 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 を正しく扱うのがポイント。

ワンライナー

1	`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

ssh -vvvv 出力例

停止箇所別の原因と対策

a: ネットワーク層の疎通に失敗

追加調査

b: サーバ上の sshd からの応答が返ってこない

追加調査

c: SSH認証に失敗

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

`ssh -vvvv` 出力例