Redis on the Raspberry Pi: adventures in unaligned lands

2017-02-24

在 Raspberry Pi 上執行 Redis：未對齊領域的冒險

銷量已突破一千萬台，加上幾乎無窮無盡的各種應用與周邊裝置，例如感測器與顯示器，我認為可以說 Raspberry Pi 不只是成功，更已成為程式設計師在嵌入式領域進行實驗時的首選平台之一。或許隨著 Pi Zero 這類產品的出現，它也正成為打造硬體產品的平台，讓人不必承擔為垂直整合裝置進行設計、製造與撰寫軟體所需的全部風險與成本。

我很喜歡這樣想：Redis 同樣也是程式設計師喜歡用來動手實作、實驗與打造新事物的平台。此外，可用於嵌入式／IoT 應用的裝置，往往需要在裝置端暫時或永久地儲存資料，例如感測器接收到的資料，以便在裝置上進行運算或傳送至遠端伺服器。Redis 正在新增一種特別適用於資料串流與時序資料儲存的 Stream 資料型別，目前規格已接近完成，實作工作將在未來幾週內展開。Redis 現有的資料結構加上新的 Stream，搭配極小的記憶體佔用，以及即使在小型硬體上也能提供的不俗效能（進而帶來低耗電），看起來與 Raspberry Pi 的潛在應用，以及廣義的小型 ARM 裝置非常契合。唯一缺少的、也是最顯而易見的一環就是：讓它在 Pi 上順暢執行。

Pi 許多酷炫之處之一，在於它的開發環境一點也不像幾年前的嵌入式開發環境……它就只是執行 Linux，具備你預期會看到的所有 Debian 風格工具。基本上，要讓 Redis 在 Pi 上運作並不是什麼艱鉅的任務。一個 Linux 系統程式與 Pi 之間最根本的落差，可能是效能／佔用空間上的不匹配，但由於 Redis 本身的設計，這根本不是問題：一個空的執行個體僅消耗總計 1MB 的 Resident Set Size(常駐記憶體大小)，從記憶體中處理查詢，因此速度夠快，也不會對快閃儲存裝置造成太大負擔；而在需要持久化時，它使用具有 append-only(僅附加)寫入模式的 AOF。不過，Pi 採用的是 ARM 處理器，這在處理未對齊存取時就需要格外留意。

在這篇部落格文章中，我一邊展示自己為了讓 Redis 與 Raspberry Pi 更契合所做的工作，一邊試著概述如何處理那些不像 x86 平台那樣能透明處理未對齊存取的架構。

關於 ARM 處理器的幾件事

將 Redis 移植到 ARM 最有趣的地方在於，ARM 處理器過去——其實應該說曾經——不太喜歡未對齊的記憶體存取。如果你一直從事高階程式設計，可能會不知道，但歷史上許多處理器架構並無法在非字組大小倍數的位址上載入或儲存記憶體字組。因此，若字組大小為 4 位元組（以 32 位元處理器為例），你可以在位址 0x4、0x8 等處載入或儲存一個字組，但不能在位址 0x7。這會導致有時產生例外，有時則出現奇怪的行為，取決於 CPU 及其確切組態。

後來 x86 處理器家族稱霸世界，大家也就漸漸忘了這個問題（除了處理 SEE 指令及類似指令時，但如今即使這些指令也有支援未對齊的變體）。不過，一開始並非真的就此遺忘。即使 x86 處理器能在不引發例外的情況下處理未對齊存取，這樣做仍會帶來不可忽視的效能損失：在字組邊界上的部分讀取／寫入需要兩倍的工作量。但後來較新的 x86 處理器加入了最佳化，使得未對齊存取在大多數情況下與對齊存取一樣快，因此如今對 x86 而言，這真的不是個問題。

直到 ARM v5 為止，ARM 都是那種會因未對齊存取而產生奇怪結果——而且是非常出乎意料的結果——的平台之一。根據 ARM 官方文件：「若位址不是 4 的倍數，LDR 指令會回傳旋轉後的結果，而非執行真正的未對齊字組載入。一般而言，這種旋轉並非程式設計師所預期的。」嗯，這*絕對*不是程式設計師所預期的。不過，即使是最初代的 Raspberry Pi 也已採用 ARM v6 處理器。v6 雖然會有效能損失，但已能處理字組大小的未對齊存取。然而，處理多個字組的指令仍會引發例外，導致程式收到 bus 訊號而終止，或向核心求助（如稍後將更詳細看到的）。這意味著 Redis 在 Pi 上執行時不會立刻慘烈當掉，因為 Redis 所執行的未對齊存取大多是字組大小的。不過，編譯器有時會為了加速運算而產生使用多重載入／儲存指令的程式碼，或 Redis 程式碼本身會嘗試從未對齊的位址載入／儲存 64 位元的值。理論上這通常會導致當機，不過 Linux 在這方面提供了一些協助。

與其當掉，不如求助核心！

Linux 核心在 ARM 處理器上執行時，即使使用者行程對 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」計數器所見。因此，這是修正 ARM 上 Linux 移植最簡單的方法，而不必逐一檢查程式碼的每個地方。

鑑於 Linux 能透明地處理此事，人們可能會想，唉……或許這裡根本沒什麼好修的，只要將 /proc/cpu/alignment 設為透明修正，Redis 就會如預期般運作。實際上並非如此，原因有二：

當執行未對齊存取並由核心修正時，會導致*非常*緩慢的執行。速度上的損失遠大於例如執行未對齊字組大小存取時所需的第二次記憶體存取。雖然這只會在多重載入與儲存指令時發生，但在某些情況下 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 也能毫無問題地執行。這意味著在 ARM 上的 Redis 應該只執行字組大小的未對齊存取，也就是 CPU 能夠透明處理的唯一類型。

修正錯誤

由於 ARM 能妥善處理大多數未對齊的記憶體存取，Redis 在 Pi 上看起來大多已經能運作。尤其是在預設情況下，核心已被設為修正許多不被支援的未對齊存取。即使停用對齊修正，它表面上仍能運作。然而，執行測試後卻顯示出不同的當機情況，特別是在位元運算與雜湊函式這類顯而易見的領域。

現在 Redis 首先會在編譯至不支援未對齊存取的架構時定義 USE_ALIGNED_ACCESS。接著只需修正程式碼，以避免執行未對齊存取的快速路徑，或將指標解參考替換為 memcpy() 操作。你可能會認為使用 memcpy() 會比解參考指標慢得多，但實際情況要好得多：對於像 memcpy(src,dst,sizeof(uint64_t)) 這樣固定大小的 mecpy 呼叫，編譯器足夠聰明，能夠避免實際呼叫該函式。它實際上會產生即使在位址未對齊時也能完成任務的最快指令組合。舉例來說，在 x86 處理器上，這個函式呼叫實際上會被轉譯為單一的 MOV 指令。

在這些修正之後，Redis 與我的兩台 Raspberry Pi——一台是初代 Model B，另一台是快上許多的 Pi 3——開始成為好朋友：所有測試皆通過，只有一項關於在當機報告中產生呼叫追蹤的測試除外（但我也會修正它），以及整合測試中偶爾因 Pi 在建立主從架構時速度過慢而出現的少數失敗。然而在這個階段，我對正確性的追求已被激起，我想要更多與對齊相關的問題。

更進一步：SPARC

在我著手修正 Redis 以支援 ARM 的同時，GitHub 儲存庫中也有一個平行議題，是關於讓 Redis 在 Solaris/SPARC 上順暢執行。SPARC 可不像 ARM 那麼溫和，它完全無法處理*任何*未對齊存取。對此我記得非常清楚，因為在我學習 C 語言的最初幾年，曾買過一台非常老舊的 SPARCstation 4：同時具備 big endian(大端序)且完全無法處理任何形式的未對齊存取，這讓我對程式移植有了一些體會。遺憾的是，擁有它幾個月後，我把伏特加灑在上面，永遠燒壞了主機板，但我至今仍把它放在父母家中。

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 更為安全，後者在這方面非常脆弱，甚至有可能產生與種子無關的碰撞。

我所使用的 SipHash 實作是參考實作，稍作修改以簡化程式碼並提供不區分大小寫的變體。它被設計為能處理未對齊存取，且與位元組順序無關。或許這是我第一次看到寫得如此之好的雜湊函式參考實作……

其他針對 SPARC 的修正，在一位熱心的 Redis 使用者提供 Solaris/SPARC 存取權限後，得以大幅簡化。在修正未對齊存取的過程中，我也嘗試修正 Redis 在 Solaris/SPARC 上的建置與測試，因此整體而言這是一次很好的可攜性改進練習。在完成這項任務後，Redis 至少在單機程式碼方面終於達到了「對齊安全」。在 Cluster 方面仍有更多工作要做。

Redis 在 Raspberry Pi 上的效能

好，回到 Pi :-) 在這樣小巧的硬體上，Redis 執行起來有多快呢？由於市面上有多種 Pi 型號，這個問題有多個答案。Redis 在 Pi 3 上出乎意料地快。我的效能測試是透過 loopback 介面進行的，因為在 Pi 上的 Redis 主要用途是供本機程式寫入資料，或作為訊息匯流排，用於 IPC(行程間通訊)以及雲端與邊緣之間的資訊交換（此處的雲端指的是設備的中央伺服器，而邊緣則指設備的本地部署）。不過，透過乙太網路埠存取時，它的表現也很好。

在 Pi 3 上，我得到以下數據：

測試 1：以 100 萬個鍵進行 500 萬次寫入（鍵之間均勻分布）。無持久化、無管線化。28000 ops/sec。
測試 2：如同測試 1，但使用每組 8 個操作的管線化：80000 ops/sec。
測試 3：如同測試 1，但啟用 AOF，fsync 設為 1 秒：23000 ops/sec
測試 4：如同測試 3，但在進行 AOF 重寫期間：21000 ops/sec

基本上，Redis 在 Pi 3 上的速度對任何使用情境來說都已足夠。請考量 Redis 大多是單執行緒，或在重寫 AOF 日誌時為雙執行緒，因為還有另一個背景行程，因此你可以預期在 Pi 上同時執行其他行程的情況下，仍能達到上述效能。重點是：這些數字並不代表我們已經讓 Pi 達到飽和。

至於初代 Model B，情況則*大不相同*，這些數字要低得多，例如在未使用管線化時約為 2000 ops/sec，而使用管線化時為 15000 ops/sec。這種巨大的差距似乎暗示了對於像 write 與 read 這類需要內容切換的 syscall(系統呼叫)處理非常沒有效率。不過，對於大多數應用而言，這些數字仍然足夠，因為 Redis 大多數時候並非用來服務外部客戶端，而且當需要執行高負載的資料記錄時，管線化往往很容易實作。

不過目前我手邊還沒有最令人感興趣的（除了 Pi 3 之外）可供測試的裝置，也就是 Pi Zero。看看它能帶來怎樣的數據將會很有趣，其表現應該會比我正在使用的 Model B 更好。

Pi 的延續

我喜歡 Redis 在 Pi 上順暢執行的一點是，我對於 Raspberry 能夠藉由 Pi Zero 這類產品，有望成為 IoT 產品首選平台感到興奮。我指的是甚至是面向終端使用者的成品。我不禁一直思考，如果我有時間，會想在硬體領域做些什麼：感測器、顯示器、GPIO 埠，以及極低的價格，使得相較於過去，打造一家硬體新創變得簡單許多，而我很喜歡全世界的駭客如今能夠推出各種智慧家電的想法。我想在其中盡一份力，即使只是些微的貢獻，在 Pi 上（以及未來在 Android 與其他 ARM 架構系統上）提供良好的 Redis 體驗。Redis 具備低資源需求、僅附加操作以及適合用於記錄與裝置內資料分析的資料模型等良好組合，能夠根據歷史事件採取行動，因此我真心相信它能在這個領域提供幫助。

因此從現在起，Raspberry Pi 對我而言是 Redis 的主要目標平台之一，就像最初將 Linux 伺服器設定為 Redis 的「標準」一樣。在接下來的幾週內，我將繼續進行修正，這些修正都將納入 Redis 4.0。同時，我也會在 Redis 官方網站上撰寫一個新章節，提供所有關於 Redis 與 Pi 的資訊：不同裝置上的效能測試、最佳實務等等。或許未來我還能發布概念驗證的「代理程式」，以便將 Redis 用作 IoT 裝置與雲端之間的資料匯流排，讓裝置只需將資料記錄至 Redis 內，由代理程式在對外連線正常時負責將資料搬移至雲端，同時擷取要讓裝置執行的指令並回傳回覆。當 Redis 4.2 中提供 Stream 資料結構後，這將會變得更加有趣。

我很樂意聽聽你認為 Redis 能在哪些嵌入式應用場景中提供協助，以及我可以做些什麼來在這方面讓它變得更好。