在歷史工程上修補是件麻煩的事情。
前兩天說起夢幻西游服務器的優化。這幾天我到廣州住下來，打算專門花一周時間搞定這件事。由於以前都是網上聊天，只有坐到一起才能真正理解問題。
目前，夢幻西游，只使用單台機器，最高配置 8 個 CPU ，配置 8G 內存。就算最熱鬧的服務器，也用不完這些資源（大約只用滿了 3 個 CPU ，一半的內存）。核心程序差不多就是 10 年前寫的，從大話西游延續至今。這兩年一直在享受免費的午餐，隨著硬件配置提升，現在單台服務器同時在線容量達到一萬兩千人。觀察服務器回應速度的圖表可以發現，目前的問題在於，定期會出現反應遲鈍的現象。周期性的，服務器回應時間會超過 1000ms 。查得原因在於那個時候，磁盤 IO 非常擁塞。有定期保存玩家數據的服務對 IO 的占用，以及 SA 做的定期備份數據的腳本占用了大量的 IO 時間。最終造成了機器負荷過重。
IO 負荷過重最終怎樣影響到游戲服務的性能，這個暫時不過於深入探討。我這兩天主要是分析以有的系統結構，並想一下改進方案。
其實老的系統並不復雜，代碼量也相當之小。相關的服務代碼僅僅數千行干淨的 C 代碼而已。一直沒有人動它，因為事關重大，牽扯著數百萬用戶的數據，以及記費流程。無論設計是好是壞，實現的性能有無問題，都讓位於穩定。“歷史原因”造成的種種，也只能在閒聊時抱怨一句，如果重新設計，肯定不會這樣寫了。近兩年，我越發的對重構這件事情顯的興趣漠然，為何不這樣做，為何不那樣? 更多的時候都只是程序員們飯局上的聊資。每個系統一旦編寫完成，就充滿了種種的遺憾。如果它能用，最大的可能就是它就將一直用下去。一切的新想法，留給下一次吧。
對於已經穩定運行了很多年的陳舊的系統，找到好的方法去改造的意義不大。最重要的是，如何對已有系統影響最小的增加一些東西，提高性能。模塊間清晰的劃分顯得相當重要。服務的獨立性也是必要的。現在運行的數據服務和記費以及用戶鑒權服務居然放在一個服務程序中恐怕是一個大失誤。它使得我們把數據讀寫剝離出來非常困難。
數據服務采用的是一個 C/S 結構。但沒有使用數據庫，而是直接使用的本地文件系統。整個設計算是良好，但數據服務本身的機制卻很糟糕。C 和 S 之間采用共享內存交換數據，這是為了提高 IPC 性能。C 只有一個，就是游戲主進程，而 S 可以有多個。可以並發的提供服務。多個 S 和 C 之間用管道傳輸命令，用共享內存交換數據。本意是好的，但協議設計是有問題的。因為 C 直接操控數據區，而有唯一性，結果設計時，把數據區的區塊管理放在了 C 上，而不是由 S 提供。
舉例來說，如果游戲進程(C) 需要加載一個用戶的數據，它自己先尋找數據區中的空位，然後通知 S 把這個用戶的數據加載到它指定的數據位置。數據區的清理工作同樣是由 C 這邊做的。這使得 S 不能直接在數據區上做 Cache ，如果需要 Cache 暫時不用的數據（比如一個玩家離線）就得由 C 自己來做。或者額外的再做一個 Cache 服務（這需要多出一倍的內存，以及內存復制的操作）當初這麼實現恐怕是考慮到有多個 S 同時為一個 C 服務的需求，但我只能認為是設計欠佳。
結果就是，整個數據服務，無論是讀還是寫，都是無 Cache 的。Cache 僅僅依賴 OS 來做。對於當初低一個數量級的時候，這沒有問題。但在線人數從千級達到萬級後，問題就顯露出來了。畢竟你為最終需求最更多的定制，越能充分發揮硬件的性能。
下面記錄一下我已經實現好的內存 Key/Value 數據庫的設計思路。
要實現前幾天想好的，只保存差異信息的策略（經實測，可以減少 90% 的寫 IO 操作），必須先統一數據讀寫服務的位置。不能依賴本地文件系統做數據交換。我之前考察過若干內存數據庫，比如 Redis ，最終決定自己實現一個。因為我已經非常了解需求，可以高度定制算法，最大發揮硬件的能力。代碼量也不會太大。（控制在 500 行 C 代碼之內，最後實際寫下來，不過 300 行 C 程序）
我們的需求是這樣的：服務程序每周會停機一次。每周總共涉及的玩家數據 10 萬組。每組數據 4k 到 32K 之間。都是文本數據。可以看成一個 id 到數據串的 key/value 數據儲存服務。經估算，總數據可以全部放入內存。數據會頻繁更新，更新後長度會改變。
我花了一天實現這個 k/v 內存數據服務。為了最大利用內存，並同時保證效率，以及代碼實現的簡潔。我采用預先分配好整塊內存的方案，把內存切割成 1K 為單位的區塊。並用單向鏈表串起來。考慮到內存 cache 的命中效率。鏈表指針本身和數據儲存區分離。（大多數時候，我們只需要訪問鏈表指針，而不需要訪問具體數據）
鏈表指針采用序號，而非內存地址。這樣即使在 64bit 系統上，依然使用 4 字節索引（可以最大可管理 4T 數據，足夠了）。單向鏈表可以比雙向鏈表節省一半的指針操作以及節約少量內存。代價是代碼寫起來繁雜一點。
所有內存區塊分成兩部分：空閒區塊和已用區塊。一開始全部空間都是空閒。一旦向內放入一段數據，就從空閒鏈表上摘下夠用的區塊，放到已用鏈表的尾部。如果 cache 空間滿，則從已用區塊鏈表頭部移掉一些空間還給空間區塊（這些數據區是長久未訪問過的）。每次讀取一段數據，都將其調整到已用鏈表的末尾，保證最後才清理。
另外做一個 hash 表，從 id 映射到在 cache 中區塊段的頭（由於是單向鏈表，具體實現時應保存上一個節點）。這樣可以用 O(1) 時間查詢指定 id 對應的數據區，
保存在 cache 中的數據不必在地址上完全連續，這好比磁盤的分簇管理。和磁盤不同，內存的隨機訪問性能和順序訪問性能差異更小。這樣有利於內存空間利用效率。
