Redis on the Raspberry Pi: adventures in unaligned lands

2017-02-24

Raspberry PiでRedisを動かす：アラインされていない世界での冒険

1000万台の販売を達成し、センサーやディスプレイをはじめとする膨大な種類の用途や周辺機器が生まれた今、Raspberry Piは単なる成功作にとどまらず、組み込み分野でプログラマが実験を行う際のお気に入りプラットフォームの一つになったと言ってよいでしょう。Pi Zeroのようなモデルも登場し、垂直統合型の専用デバイスを一から設計・製造し、ソフトウェアを書く際のリスクやコストを負うことなく、ハードウェア製品を作るためのプラットフォームにもなりつつあります。

私自身、Redisもまた、プログラマが何かを作ったり、試したり、新しいものを作ったりする際に好んで使うプラットフォームだと思っています。さらに、組み込み／IoT用途のデバイスでは、たとえばセンサーから受け取ったデータなどを一時的に、あるいは永続的にデバイス上に保存し、デバイス上で計算を行ったり、リモートサーバーに送信したりする必要がしばしば生じます。Redisには「Stream」というデータ型が追加されようとしています。これはデータストリームや時系列データの保存に特化したもので、現時点で仕様はほぼ完成し、今後数週間で実装が始まる予定です。Redisの既存のデータ構造と新しいStream、そして小さなメモリフットプリント、小さなハードウェア上でも発揮できる十分な性能（ひいては低い消費電力）は、Raspberry Piでの活用、ひいては小型のARMデバイス全般と相性が良いように思えました。足りないピースは明らかでした。Pi上で快適に動作することです。

Piの素晴らしい点の一つは、その開発環境が数年前の組み込み開発環境のようではないことです。単にLinuxが動き、Debian系でおなじみのツールが一通り揃っています。基本的に、RedisをPiで動作するように適応させる作業は、それほど大変ではありませんでした。LinuxのシステムプログラムとPiの間で起こりうる最も根本的なミスマッチは、性能やフットプリントに関するものですが、Redis自体の設計のおかげでこれは問題になりません。空のインスタンスが消費する常駐メモリ（RSS）はわずか1MBで、クエリはメモリから処理されるため十分に高速で、フラッシュストレージへの負荷も大きくありません。永続化が必要な場合も、追記専用の書き込みパターンを持つAOFが使われます。しかしPiはARMプロセッサを搭載しており、アラインされていないアクセスを扱う際には注意が必要です。

この記事では、RedisとRaspberry Piをより仲良くさせるために私が行ったことを紹介しながら、x86のようにアラインされていないアクセスを透過的に処理しないアーキテクチャへの対応について概観してみたいと思います。

ARMプロセッサについて知っておきたいこと

RedisをARMに移植する際に最も興味深いのは、ARMプロセッサが――正確には「かつては」ですが――アラインされていないメモリアクセスをあまり好まないという点です。高水準言語だけでプログラミングしていると気づかないかもしれませんが、多くのプロセッサアーキテクチャでは、歴史的にワードサイズの倍数ではないアドレスに対して、ワード単位のロードやストアができませんでした。たとえば32ビットプロセッサでワードサイズが4バイトの場合、アドレス0x4や0x8からはワードをロード／ストアできますが、0x7からはできません。その結果はCPUやその設定によって、例外が発生したり、奇妙な挙動を示したりします。

その後x86プロセッサファミリが世界を席巻し、誰もがこの問題を忘れてしまいました（SSE命令などを扱う場合を除けば――ただ今ではそれらの命令にもアンアラインド版が用意されています）。もっとも、最初から忘れられていたわけではありません。x86プロセッサはアラインされていないアクセスでも例外を発生させずに処理できましたが、性能上のペナルティは小さくありませんでした。ワード境界をまたがる部分的な読み書きでは、2倍の処理が必要になったのです。しかし最近のx86プロセッサでは、アラインされていないアクセスをほとんどの場合アラインされたアクセスと同じ速さで処理できる最適化が施されており、今日のx86にとってこれはもはや問題ではありません。

ARMはv5までは、アラインされていないアクセスが奇妙な、しかも非常に予期しない結果を引き起こすプラットフォームの一つでした。ARMの公式ドキュメントにはこうあります。「アドレスが4の倍数でない場合、LDR命令は真のアンアラインドなワードロードを行うのではなく、ローテートされた結果を返します。一般に、このローテートはプログラマが期待するものではありません」。まったく、期待通りではありませんね。しかし初代Raspberry PiでさえARM v6プロセッサを搭載していました。v6は性能ペナルティはあるものの、ワードサイズのアンアラインドアクセスは処理できます。ただし複数のワードを扱う命令では例外が発生し、プログラムはバスエラー（SIGBUS）で終了するか、後述するようにカーネルに助けを求めることになります。つまり、RedisがPi上で実行された際にすぐさまクラッシュしなかったのは、Redisが行っていたアンアラインドアクセスのほとんどがワードサイズだったからです。しかし時折、コンパイラが計算を高速化するために複数ロード／ストア命令を使ったコードを生成したり、Redisのコード自体がアラインされていないアドレスから64ビット値をロード／ストアしようとしたりしました。これは本来であればクラッシュを引き起こすはずですが、Linuxがある程度助けてくれます。

クラッシュする代わりに、カーネルに頼る

ARMプロセッサ上で動作するLinuxカーネルは、CPUが通常サポートしないアンアラインドなアドレスへの操作が実行された際でも、ユーザープロセスが期待通りに動作するように支援できます。その方法は、カーネル内にそうした例外用のハンドラを登録しておくことです。カーネルは失敗した操作を調べ、関数内でそれをエミュレートし、プロセッサが実行したかのような結果を作り出したうえで、問題を起こしたプロセスを再開して実行を続けさせます。

低水準プログラミングに興味がある方は、このLinuxカーネルのファイルを見る価値があります。http://lxr.free-electrons.com/source/arch/arm/mm/alignment.c

CPUがアンアラインドアクセス例外を発生させた際のカーネルの実際の挙動は、/proc/cpu/alignmentファイルで制御されています。

$ cat /proc/cpu/alignment
User:		0
System:		12590 (ip6_datagram_recv_common_ctl+0xc8/0xd4 [ipv6])
Skipped:	0
Half:		0
Word:		0
DWord:		0
Multi:		12590
User faults:	2 (fixup)

ご覧の通り、カーネルによって修正されたすべてのアンアラインドアクセスについて、ユーザ空間とカーネル空間それぞれのカウンタが分かれて記録されています。上記の例では、カーネル空間で12590件のアクセスが修正されています。ユーザ空間のプロセスは一件も修正されていません。なお「User faults」の行は、ユーザ空間のプロセスがCPUで処理できないアンアラインドアクセスを行った際にカーネルが何をするかの設定を示しています。問題を修正するか、SIGBUSを送るか、カーネルログに記録するかです。これは/proc/cpu/alignmentに書き込む整数値の各ビットで制御され、たとえばユーザ空間のアンアラインドアクセスを修正に加えてログにも残したい場合は「echo 3 > /proc/cpu/alignment」とします（ビット1がログの有効化、ビット2が修正の有効化に対応します）。

私の印象では、Linuxカーネルがこの機能を有効にしているのは、カーネルの開発者がアンアラインドなメモリアクセスを扱えないユーザ空間のプログラマを気遣ったからというより、カーネル自身が必ずしもアラインされたアクセスばかりを行うわけではないからです。Systemカウンタを見てもわかる通りです。ですから、コードのあらゆる箇所をチェックするよりも、これがLinuxのARM対応を修正する最も簡単な方法だったのでしょう。

Linuxがこの問題を透過的に処理してくれるとなると、「/proc/cpu/alignmentを透過的に修正するように設定しておけば、Redisは期待通りに動くのだから、修正すべきことは何もないのでは」と考えたくなるかもしれません。しかし実際にはそうではありません。理由は二つあります。

アンアラインドアクセスが発生してカーネルが修正を行うと、実行速度は極端に遅くなります。その速度低下は、たとえばワードサイズのアンアラインドアクセスで必要になる2回目のメモリアクセスよりもはるかに大きいのです。これが起こるのは複数ロード／ストア命令の場合に限られますが、それでも特定の条件下でRedisが本来よりもずっと遅くなるのは残念なことです。
LinuxカーネルのARMにおけるミスアラインドアクセスの実装は完全ではありません。GCCが出力するコードの中には、Linux 4.4.34ではうまく扱えない命令が含まれているのです。

些細な例を挙げます。

#include <stdlib.h>

int main(int argc, char **argv) {
        int count = 1000;
        char *buf = malloc(count*sizeof(double));
        double sum = 0;
        double *l = (double*) (buf+1);
        while(count--) {
                l++;
                sum += *l;
        }
        return 0;
}

$ gcc foo.c -g -ggdb
$ ./a.out
Bus error

Piのカーネル設定がアンアラインドアクセスを修正するように設定されていても、プログラムはSIGBUSを受け取ってしまいました。GDBでどこで発生しているか見てみましょう。

$ gdb ./a.out
(gdb) run

Program received signal SIGBUS, Bus error.
0x00010484 in main (argc=1, argv=0xbefff3b4) at foo.c:10
10	                sum += *l;

予想通り、内側のループでアラインされていないdoubleポインタがデリファレンスされた箇所です。さらに何が起きているのか、例外を発生させたARM命令を確認してみましょう。

(gdb) x/i $pc
=> 0x10484 <main+100>:	vldr	d6, [r11, #-20]	; 0xffffffec

VLDR命令は拡張レジスタにメモリ上の値をロードするために使われ、浮動小数点演算で利用されます。何らかの理由で、Linuxカーネルのアンアラインドアクセス修正の実装は、この命令を処理できません（実装が本来あるべきほど完全ではないのでしょう）。実際「dmesg」コマンドを見ると、アンアラインドアクセスを修正する関数がこの命令を認識できなかったことがわかります。

[317778.925569] Alignment trap: not handling instruction ed937b00 at [<00010480>]
[317778.925610] Unhandled fault: alignment exception (0x011) at 0x01cb8011

つまり、PiのデフォルトのCコンパイラが、デフォルトのLinuxカーネルでは処理できないコードを出力しうるのであれば、たとえカーネルがアンアラインドアクセスを修正しない設定になっていても、Redisが問題なく動作できるようにしたいと考えました。そのためには、Redis on ARMではCPUが透過的に処理できる唯一のものである、ワードサイズのアンアラインドアクセスだけを行うようにする必要があります。

バグの修正

ARMがほとんどのアンアラインドなメモリアクセスをうまく処理できることもあり、RedisはPi上でも一見問題なく動作しているように見えました。特に、カーネルがデフォルトでサポート外のアンアラインドアクセスの多くを修正するように設定されているためです。アライメント修正を無効にしても、表面的にはまだ動作していました。しかしテストを実行すると、特にビット演算やハッシュ関数といった分かりやすい箇所で、さまざまなクラッシュが明らかになりました。

Redisがまず行うようにしたのは、アンアラインドアクセスをサポートしないアーキテクチャでコンパイルされる際にUSE_ALIGNED_ACCESSを定義することです。あとは、アンアラインドアクセスを行っていた高速化パスを避けるか、ポインタのデリファレンスをmemcpy()呼び出しに置き換えることでコードを修正するだけでした。memcpy()を使うのはポインタのデリファレンスよりずっと遅いのではと思われるかもしれませんが、実際はそこまで悪くありません。memcpy(src,dst,sizeof(uint64_t))のようなサイズが固定されたmemcpy呼び出しでは、コンパイラは賢く関数呼び出しを回避します。アドレスがアラインされていなくても正しく動作する、最も高速な一連の命令を生成してくれるのです。たとえばx86プロセッサでは、この関数呼び出しは実際には単一のMOV命令に置き換えられます。

これらの修正の後、私の2台のRaspberry Pi――初代モデルBと、はるかに高速なPi 3――とRedisはすっかり仲良くなりました。すべてのテストがパスするようになりましたが、クラッシュレポートでコールトレースを生成するテストだけは例外でした（これもいずれ修正します）。また、Piがマスターとスレーブのセットアップに時間がかかるため、統合テストで時折失敗することがありました。しかしこの時点で、私の正確さへの欲求はさらに刺激されました。もっとアライメントの問題を見つけたいと思うようになったのです。

もう一歩先へ：SPARC

ARM向けにRedisを修正している間、GitHubリポジトリでは並行してSolaris/SPARCでRedisをきちんと動作させるためのissueが開かれていました。SPARCはARMほど寛容ではありません。いかなるアンアラインドアクセスも処理できないのです。このことは、私がCプログラミングを始めた初期のころに、とても古いSPARCstation 4を買った経験からよく覚えていました。ビッグエンディアンで、しかも一切のアンアラインドアクセスを扱えない――同時にその両方を抱えた環境は、プログラムの移植について多くの視点を与えてくれました。数か月後にウォッカをこぼしてマザーボードを永遠に壊してしまったのは残念でしたが、今でも実家に置いてあります。

Solaris/SPARCにおけるアンアラインドアクセスの扱いは、Linux/ARMよりも複雑です。32ビットのアンアラインドアクセスは常にカーネルが修正しますが、64ビットのアンアラインドアクセスはコンパイル時のフラグに応じてユーザ空間のトラップを登録することで処理されます。Sun Studio Cコンパイラには、何が起こるかを非常に精密に制御するための専用オプションや、そうしたアンアラインドアクセスを簡単に検出・修正するためのツールさえ用意されています。

Redisで非ワードサイズのアンアラインドアクセスがまれだったとすれば、ワードサイズのアンアラインドアクセスは至る所にあると予想されるかもしれません。しかし実際にはそうではありませんでした。Redis 3.0までは、時折OpenBSD/SPARCマシンでRedisをテストし、修正していたからです。そのため最大の問題は、キーをハッシュする関数にありました。元々のRedisの文字列ライブラリであるSDSは、ヘッダのサイズが固定だったため、キーをハッシュする際のアクセスは常にアラインされていました。Redis 3.2からはSDSヘッダのサイズが可変になったため、もはやそうではありません。さらに、前回SPARCでRedisをテストした数年前以降に蓄積された、その他の新しいアンアラインドアクセスもあちこちに存在していました。

ハッシュ関数を修正するために、SipHashへの切り替えも行いました。これによりHashDoS攻撃に対するセキュリティ修正にもなっています。ただし、現在使っているのはCラウンドとDラウンドの回数を減らしたSipHashの亜種、SipHash1-2であることに注意してください。そうしなければ無視できない速度低下が生じてしまうためです。しかし私の知る限りSipHash1-2に対する実用的な攻撃は存在せず、少なくとも以前使っていたMurmurHash2よりは確実に安全です。MurmurHash2はこの点で非常に脆弱で、シードに依存しない衝突を生成することさえ可能です。

私が使っているSipHashの実装は、コードを簡素化し、大文字小文字を区別しない亜種を用意するために少し手を加えたリファレンス実装です。アンアラインドアクセスに対応し、エンディアンに依存しないように設計されています。これまで見た中で、おそらく最もよく書かれたハッシュ関数のリファレンス実装です。

その他のSPARC関連の修正は、Solaris/SPARC環境を提供してくれた親切なRedisユーザーのおかげで大幅に容易になりました。アンアラインドアクセスを修正する過程で、Solaris/SPARCでのRedisのビルドやテストについても修正を試みたため、これは全般的に移植性を向上させる良い機会にもなりました。この作業が完了したことで、少なくともスタンドアロン部分のコードについては、Redisはついに「アライメントセーフ」になりました。Cluster周りではまだやるべきことが残っています。

Raspberry PiにおけるRedisの性能

さて、Piの話に戻りましょう。このような小さなハードウェア上でRedisはどれくらい速く動くのでしょうか。Piにも複数のモデルがあるため、この問いに対する答えも一つではありません。Pi 3上のRedisは驚くほど高速です。私のベンチマークはループバックインターフェース経由で行っています。Pi上のRedisは、主にローカルのプログラムがデータを書き込んだり、IPCやクラウド・エッジ間の情報交換のためのメッセージバスとして使われたりすることを想定しているからです（ここで言うクラウドとは機器の中央サーバー、エッジとは機器のローカル設置環境を指します）。とはいえ、イーサネットポート経由でアクセスした場合でも良好に動作します。

Pi 3では次のような数値が得られました。

テスト1：100万キーに対して500万回の書き込み（キー間の均等な分布）。永続化なし、パイプラインなし。28000 ops/秒。
テスト2：テスト1と同様だが、8件ずつまとめたパイプラインを使用：80000 ops/秒。
テスト3：テスト1と同様だが、AOF有効、fsyncは1秒ごと：23000 ops/秒
テスト4：テスト3と同様だが、AOFリライト実行中：21000 ops/秒

基本的に、Pi 3上のRedisはどんなユースケースにも十分な速さに見えます。Redisは基本的にシングルスレッドで、AOFログを書き換える際にはバックグラウンドプロセスがもう一つ動くため2スレッドになると考えてください。そのため、上記の性能を発揮しながら同時に他のプロセスをPi上で動かすことも期待できます。要するに、これらの数値はPiを使い切っているわけではないということです。

初代モデルBでは状況はかなり異なります。数値ははるかに低く、パイプラインなしで2000 ops/秒程度、パイプライン使用時で15000 ops/秒程度です。この大きな差は、writeやreadのようなコンテキストスイッチを要するシステムコールの処理が非常に非効率であることを示唆しています。しかし、これらの数値でもほとんどのアプリケーションには十分です。Redisが外部クライアントにサービスを提供することはほとんどの場合ありませんし、負荷の高いデータロギングが必要な場合でも、パイプラインはしばしば簡単に実装できるからです。

ただ現時点では、Pi 3以外で最も興味深いデバイスの一つであるPi Zeroを手元に持っていないためテストできていません。どれくらいの数値が出るのか、とても楽しみです。私が使っているモデルBよりは良い結果になるはずです。

Piとの歩みを続ける

RedisがPi上で快適に動作することについて私が気に入っている点の一つは、Pi Zeroのような製品によって、Raspberry PiがIoT製品の定番プラットフォームになる可能性にワクワクしていることです。最終ユーザ向けの完成品でさえもです。もし時間があればハードウェアの分野で自分が何をしたいか、考えずにはいられません。センサー、ディスプレイ、GPIOポート、そして非常に安い価格。これらによって、過去に比べてはるかに簡単にハードウェアスタートアップを立ち上げることができます。そして世界中のハッカーたちが今やさまざまなスマート家電を出荷できるという発想が大好きです。たとえわずかでも、この流れの一部でありたいと思っています。Pi（そして将来的にはAndroidやその他のARMベースシステム）で優れたRedis体験を提供することで。Redisは、リソース要件が低く、操作が追記型で、データのロギングとデバイス内でのデータ分析の両方に適したデータモデルを持つため、履歴イベントに基づいてアクションを起こすといった用途にも向いており、この分野で役立つと心から信じています。

ですから今後は、Raspberry PiをRedisの主要なターゲットプラットフォームの一つと位置付けます。かつてLinuxサーバーをRedisの「標準」と定めたようにです。今後数週間にわたって修正を続け、それらはすべてRedis 4.0に取り込まれる予定です。同時に、Redis公式サイトにRedisとPiに関する新しいセクションを設け、さまざまなデバイスでのベンチマークやベストプラクティスなどを掲載していきます。将来的には、IoTデバイスとクラウド間のデータバスとしてRedisを利用するための概念実証（PoC）エージェントもリリースできればと考えています。デバイスはデータをRedisにログするだけで、エージェントが外部との接続が利用可能なときにデータをクラウドへ移動させ、同時にデバイスが実行すべきコマンドを取得して応答を返す、といった仕組みです。これはRedis 4.2でStreamデータ構造が利用可能になれば、さらに面白くなるでしょう。

組み込み環境でRedisが役立ちそうなアプリケーションや、そのために私に何ができるかについて、ぜひ皆さんの意見を聞かせてください。