微博推薦靜態數據存儲方案: lushan

基本的socket編程是阻塞/同步的, 每個操作除非已經完成或者出錯才會返回, 這樣對于每一個請求, 要使用一個線程或者單獨的進程去處理, 系統資源沒法支撐大量的請求（所謂c10k problem）, 例如內存：默認情況下每個線程需要占用2～8M的棧空間.

posix定義了可以使用異步的select系統調用, 但是因為其采用了輪詢的方式來判斷某個fd是否變成active, 效率不高[O(n)], 連接數一多, 也還是撐不住.

于是各系統分別提出了基于異步/callback的系統調用, 例如Linux的epoll, BSD的kqueue, Windows的IOCP.
由于在內核層面做了支持, 所以可以用O(1)的效率查找到active的fd.

基本上, libevent就是對這些高效IO的封裝, 提供統一的API, 簡化開發.

lushan的通信模型是基于libevent這個開源的事件驅動網絡庫的, 因此能進行高效的通信服務. 這一小節先介紹libevent的基本原理, 在此基礎上才能更好的理解整個lushan的通信流程.

為了實際處理每個請求, libevent庫提供一種事件機制, 它作為底層網絡后端的包裝器.
事件系統讓連接添加處理函數變得非常簡便, 同時降低了底層I/O復雜性, 這是libevent系統的核心.

創建libevent服務器的基本方法是, 注冊當發生某一操作(比如接受來自客戶端的連接)時應該執行的函數, 然后調用主事件循環event_dispatch().
執行過程的控制現在由libevent系統處理.
注冊事件和將調用的函數之后, 事件系統開始自治.
在應用程序運行時, 可以在事件隊列中添加(注冊)或刪除(取消注冊)事件.
事件注冊非常方便, 可以通過它添加新事件以處理新打開的連接, 從而構建靈活的網絡處理系統.

結構體event和event_base是libevent的兩個核心數據結構, 前者代表一個事件對象, 后者代表整個事件處理框架.
libevent通過event對象將將IO事件, 信號事件, 定時器事件進行封裝, 從而統一處理, 這也是libevent的精妙所在.
libevent主循環函數不斷檢測注冊事件, 如果有事件發生, 則將其放入就緒鏈表, 并調用事件的回調函數, 完成業務邏輯處理

libevent支持的事件

IO事件: EV_READ EV_WRITE
定時事件: EV_TIMEOUT
信號事件: EV_SIGNAL
輔助選項: EV_PERSIST 表明這是一個永久事件

libevent的關鍵函數

event_set()創建新的事件結構
event_add()在事件隊列中添加事件
event_dispatch()啟動事件隊列系統

綁定到event的回調函數原型

typedef void(* event_callback_fn)(evutil_socket_t sockfd, short event_type, void *arg)

lushan在啟動時第一步就是進行初始化, 包括配置信息的初始化, 統計信息的初始化, freeconns的初始化.

配置信息是settings這個結構體, 通過對命令行參數的解析完成(命令行參數又來自于配置文件)結構體的填充. 該結構體主要存儲ip, 端口, 線程數, 最大連接數, 超時時間等屬性, 對應于lushan server這個維度

統計信息是stats這個結構體, 該結構體的各項初始化時都賦值為0或NULL. 該結構體主要存儲當前連接數, 查詢總數, 查詢命中/未命中數, 啟動時間等屬性, 對應于db這個維度

freeconns是一個初始大小為200的動態數組, 它用來保存已經free的conn, 這樣在以后需要conn的時候不用重新新建一個conn, 從該數組中取一個即可, 節省了新建conn帶來的開銷. 數組中的元素是一個指向conn的指針

完成基本屬性的初始化后, 就開始建立socket連接, 得到一個監聽sfd. 該過程通過標準socket的socket(), bind(), listen()函數完成, 注意在這里并沒有進行accept.

創建完socket連接后, 進行REQ隊列和RSP隊列的初始化. 這兩個隊列的數據結構一樣, 是一個有頭指針和尾指針的單向鏈表, 各包括一個隊列鎖和條件變量, 條件變量用來進行線程間通訊. 這里REQ隊列彈出元素是阻塞式的, RSP隊列彈出元素是非阻塞式的

可以看到, REQ/RSP隊列里存儲的是一個個指向conn的指針, conn的結構體如下圖所示, 它存儲了conn當前的狀態, 還有關鍵是存儲了一個event結構體, 這樣每個conn就對應一個事件變量, 用來監聽發生在fd或者POSIX信號量上的事件. 同時還存儲了一塊讀緩沖區和寫緩沖區.

完成請求/響應隊列的初始化后, 接著初始化一個管道, 管道的兩端一端用來接收fd, 另一端用來發送fd, 它們啟到信號通知的作用, 這個過程會在后面有所反映.

繼續初始化hdb, 同時通過對lushan.init文件的解析, 加載hdb_path目錄下的數據, 完成對數據庫的初始化加載

同時新建一個hdb_mgr線程, 用來處理hdb的close_list里的數據

接下來再新建num_threads個worker線程(配置文件中默認是4個), 這里就是傳說中的工作線程
進入worker函數來一探究竟. 該函數的主體部分是一個無限循環, 做了下面幾件事:

1. 阻塞式的從REQ隊列取conn
2. 處理conn里的各種cmd, 比方說有stats, open, close, randomkey, info, get等都在這里.
   處理時將conn相應的wbuff填充, wbuff是用來回顯給客戶端用的
3. 將填充好后的conn塞入RSP隊列
4. 往管道的notify_send_fd端寫一個字符的內容, 啟一個信號的作用, 用來進行事件通知, (通知RSP隊列取conn)
   再寫前后要進行一個加解鎖的操作

接下來進入libevent的部分, 從這里開始將lushan作為一個server啟動, 進行client的監聽, 對相應的事件作出響應.
首先初始化event_init, 然后event_set創建一個通知事件, 該通知事件的回調函數是notify_handler, 當有讀事件時觸發, 在管道讀時進行響應.
接著將該通知事件注冊到event_base上, 并添加到事件隊列中.

說一下notify_handler這個回調函數, 它做了下面幾件事:

1. 讀notify_receive_fd, 起到通過管道進行事件響應的作用(這里如果讀到的不是1個字符的內容, 說明讀有問題)
2. 非阻塞的從RSP隊列里取conn
3. 將取出的conn交給drive_machine函數處理

drive_machine其實就是一個狀態機, 主要進行狀態轉換的功能, 對conn的不同狀態作出不同的處理(lushan有4個狀態, mc有好多個)

1. 當conn處于conn_listening狀態時
   在這里才真正的進行accept, 得到一個sfd后設置為O_NONBLOCK, 接著調用conn_new
2. 當conn處于conn_read狀態時
   通過調用try_read_command和try_read_network, 來處理conn里rbuff留存的數據, 能處理命令的直接處理(如quit, stop, version), 不能處理命令賦值給c->cmd后, 將conn塞給REQ隊列, 之后調用update_event更新事件為讀事件
3. 當conn處于conn_write狀態時
   調用系統函數write, 真正在客戶端顯示結果就在這一步
   當write出現EAGAIN或EWOULDBLOCK錯誤時, 意味著當前沒有數據可寫, 需要調用update_event更新事件為寫事件
   這一步完成后設置conn的狀態為conn_closing
4. 當conn處于conn_closing狀態時
   直接調用conn_close函數, 這里并不真正釋放conn, 而只是把指向conn的指針放到freeconns數組里, 當需要新的conn時, 先從freeconns數組里取, 這樣避免了每次新建conn時都要進行內存分配以及相應釋放時的開銷

對狀態機里用到的event_handler和conn_new兩個函數做一下說明

event_handler, 另一個回調函數, 它的主要作用就是當有事件發生時, 就調用drive_machine處理相應的conn
和notify_handler回調函數不同的是, 它的conn是在事件注冊時通過參數傳遞得到的, 而notfiy_handler的conn是從RSP隊列里得到的

conn_new函數, 顧名思義, 就是新建conn, 如果freeconns數組里有conn, 則直接從里面取一個使用, 沒有的話則需要重新分配一塊內存來生成. 在這個函數里還有比較重要的一個功能就是創建并注冊讀寫事件, 通過回調函數event_handler來進行響應.

整個lushan的通信流程可以參考下面的大圖…

如圖所示, 索引由一個64位的整型key和64位的整型pos組成. 其中key就是key-value結構中需要查詢的key, 而pos則包含兩部分信息, 它的前40位表示value在dat文件中的偏離值off, 后20位表示value的長度length, 通過off和length來共同定位dat文件中的value. 該索引結構也決定了lushan存儲數據的特點, 即一條記錄的索引只需16字節, 而它的key是必須是整型, 同時value的長度最多為2^20=1048576(1M)

一個db由idx索引文件和dat數據文件共同組成, 它的結構體定義如下

從該結構體可以看出, 每個db實際上是一個由雙端鏈表組成的隊列(TAIL QUEUE). 它包括db目錄(path), 索引數(idx_num), 索引數組(idx), dat文件的文件描述符(fd), 打開時間(open_time), 查詢次數(num_qry), 該db引用數(ref), db編號(hdid)等屬性信息. 在這里有兩個地方需要注意一下, 第一就是db實際上是一個隊列, 另一個就是ref(引用計數)這個值, 它們保證了在換庫時兩個庫都是可用的狀態, 并且通過對引用計數的使用來減少了鎖的使用

hdb實際上是整個lushan存儲的結構, 它包含了所有的db, 它的結構體如下定義

hdb有一個open_list鏈表和一個close_list鏈表, 分別存儲已經打開的db和已經關閉的db, 當已經關閉的db中的ref為0時, 才去釋放該db, 如果ref不為0, 則說明其還在使用中, 因此不能釋放, 來確保在庫切換過程中, 同時保持兩個庫都可用的狀態. 同時hdb保存一個有1024個元素的htab數組, 用來存放每個db的隊頭元素

該過程其實就是初始化hdict結構體, 首先為hdict結構體分配一塊內存, 接著根據外部參數path來找到索引文件idx, 在內存中開辟一塊區域將索引文件的所有內容均加載進去(通過fread函數). 完成idx索引文件的加載后, 接著打開dat數據文件, 并將其文件描述符fd存在hdict結構體中

首先加載索引文件和數據文件, 完成hdict的初始化. 指定一個db號, 接著遍歷open_list鏈表里的元素, 如果已經打開的db號里沒有該db號, 則說明這是一個新建的db, 直接在open_list隊尾增加一個hdict, 同時根據db號得到一個哈希值, 在htab的對應槽里插入hdcit的隊頭.

如果open_list鏈表里的元素的db號和指定db號相等, 則說明這是一個換庫的操作. 從open_list里刪掉老的db, 同時把老的db加到clost_list里, 留到以后釋放(ref減為0). 接著在open_list隊尾增加一個hdict, 同時根據db號得到一個哈希值, 在htab的對應槽里插入hdcit的隊頭.

關閉db實際上就是刪除open_list里的元素, 將它增加到close_list里. 同時有一個控制線程在不斷遍歷close_list鏈表, 當發現有db的ref為0時, 則將其從close_list中刪除. 這里有一個巧妙的地方就是在刪除db時并沒有真正進行資源的釋放, 而是先把它們存到一個數組里, 當該數組的元素達到一定個數時, 再統一釋該數組里的所有元素, 這個操作避免了每次釋放資源帶來的開銷問題.

查找數據是通過二分搜索key的值得到的. (這說明了索引文件的key值必須是有序排列的. 當數據來源于hadoop時, 經過reduce操作后, 索引文件天生就是有序的, 當數據不是由hadoop產生時, 如果索引文件沒有排序, 則可以調用index_sort子程序使其變為有序). 在內存中找出key對應的pos后獲得value的off和length信息, 接著調用pread函數即可從dat數據文件里取得真正的數據