Redis on the Raspberry Pi: adventures in unaligned lands

2017-02-24

Raspberry Piで動くRedis：アンアラインドな世界での冒険

原文は Salvatore Sanfilippo により 2017-02-24 に公開されました。このブログを購読する

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プロセッサが――というか、かつては――アンアラインドなメモリアクセスをあまり好まないことだ。高水準プログラミングの世界だけで生きてきた人には馴染みがないかもしれないが、歴史的に多くのプロセッサアーキテクチャは、ワードサイズの倍数ではないアドレスに対してメモリのワードをロード／ストアすることができなかった。たとえばワードサイズが4バイト（32ビットプロセッサの場合）なら、アドレス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件のアクセスが修正されている。ユーザランドのプロセスは1件も修正されていない。「User faults」の行は、CPUが処理できないアンアラインドアクセスをユーザ空間のプロセスが実行した際に何をすべきかというカーネルの設定を示している。問題を修正する、SIGBUSを送る、カーネルログに記録する、といった動作だ。これは/proc/cpu/alignmentに書き込む整数値の個々のビットで制御され、たとえばユーザ空間のアンアラインドアクセスを（修正に加えて）ログに残したい場合は「echo 3 > /proc/cpu/alignment」とすればよい（ビット1がログを有効にし、ビット2が修正を有効にする）。

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

Linuxがこれを透過的に処理してくれるなら、「まあ……/proc/cpu/alignmentを透過的に修正するように設定しておけば、Redisは期待通りに動くのだから、直す必要なんてないのでは？」と思いたくなるかもしれない。実際には、2つの理由からそうはいかない。

アンアラインドアクセスが発生し、カーネルによって修正されると、実行速度は*非常に*遅くなる。その速度ペナルティは、たとえばワードサイズのアンアラインドアクセスで必要になる2回目のメモリアクセスよりもはるかに大きい。これが起こるのは複数ワードのロード／ストア命令の場合だけだが、それでも特定の条件下でRedisが必要以上に大幅に遅くなるのは残念なことだ。
ARMのミスアラインドアクセスに対するLinuxカーネルの実装は完全ではない。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はカーネルがアンアラインドアクセスを修正しない設定になっていても問題なく動作できるようにしたかった。それはつまり、ARM上のRedisは、CPUが透過的に処理できる唯一のものであるワードサイズのアンアラインドアクセスだけを行うべきだということだ。

バグを修正する

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

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

これらの修正の後、Redisと私の2台のRaspberry Pi――1台はオリジナルのModel B、もう1台はずっと高速なPi 3――はすっかり仲良くなった。すべてのテストがパスし、残ったのはクラッシュレポートでのコールトレース生成に関する1件だけだった（これもいずれ修正する予定だ）。あとは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をテストし、修正していたからだ。そこで最大の問題となったのは、キーをハッシュする関数だった。SDSと呼ばれるもともとのRedis文字列ライブラリは固定サイズのヘッダを持っていたため、キーをハッシュする際のアクセスは常にアラインされていた。Redis 3.2からはSDSヘッダが可変サイズになったため、もはやそうではなくなった。さらに、数年前に最後にSPARCでRedisをテストして以来、あちこちで新たなアンアラインドアクセスが蓄積されていた。

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

私が使っているSipHashの実装はリファレンス実装をベースに、コードを簡素化し、大文字小文字を区別しないバリアントを持たせるために少し修正を加えたものだ。これはアンアラインドアクセスを扱えるように、かつエンディアンに依存しないように設計されている。おそらく初めて目にした、よく書かれたハッシュ関数のリファレンス実装だ。

その他のSPARC向け修正は、親切なRedisユーザーがSolaris/SPARC環境へのアクセスを提供してくれたことで大いに容易になった。アンアラインドアクセスを修正する過程で、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ログをリライトする際にはバックグラウンドプロセスがもう一つ動くためダブルスレッドになると考えれば、上記のパフォーマンスを発揮しながら、同時にPi上で他のプロセスが動いている状態を期待できる。要するに、これらの数値はPiを使い切っていることを意味しないのだ。

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

ただ現時点では、Pi 3以外で最も興味深いデバイスであるPi Zeroをテスト用に持っていない。どれくらいの数値が出るのか見るのが楽しみだ。私が使っているModel Bよりは良いはずだ。

Piのこれから

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

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

組み込み環境でRedisが役立つと思うアプリケーションや、この点でより良くするために私に何ができるかについて、ぜひ意見を聞かせてほしい。