xiaoxiaoling

將博客搬至CSDN

ET和LT:   
   LT一般用在單線程。
   ET和EPOLLONESHOT配合用在多線程共享一個epoll環境下，EPOLLONESHOT標記觸發過的事件從epoll中移除，下次必須重新注冊，用來防止多線程同時取到同一個socket的事件產生沖突。

epoll_wait 第三個參數 取事件數量：
   單線程模型當然盡可能一次多取一些效率高，多線程為了防止一個線程把所有事件取完其他線程饑餓，ACE實現是只取1個。

錯誤處理：
   EAGIN | EINTR | EWOULDBLOCK 重試。
   EPOLLERR | EPOLLHUP | EPOLLRDHUP 斷開連接。

驚群：
   默認系統都會有這問題，據說新系統有修復不過還是處理一下比較好，一般解決方案是同時只有一個線程等待accept，可以單獨線程accept，將連接在分給其他工作線程。nginx是多進程模型，使用了基于共享內存的互斥鎖，使得同時只有一個工作進程的epoll含有accept的socket，通過這種方式實現連接數上的負載均衡（連接數少的工作進程得到accept鎖的概率高）。

   為了避免大數據量io時，et模式下只處理一個fd,其他fd被餓死的情況發生。linux建議可以在fd聯系到的結構（一般都會自己封裝一個包含fd和讀寫緩沖的結構體）中增加ready位，然后epoll_wait觸發事件之后僅將其置位為ready模式，然后在下邊輪詢ready fd列表。

epoll實現：  
   epoll內部用了一個紅黑樹記錄添加的socket，用了一個雙向鏈表接收內核觸發的事件。

   注冊的事件掛載在紅黑樹中(紅黑樹的插入時間效率是logN，其中n為樹的高度)。

   掛載的事件會與設備(網卡)驅動建立回調關系，也就是說，當相應的事件發生時會調用這個回調方法。這個回調方法在內核中叫ep_poll_callback,它會將發生的事件添加到rdlist雙鏈表中。

   使用mmap映射內存，減少內核態和用戶態的不同內存地址空間拷貝開銷。每次注冊新的事件到epoll中時，會把fd拷貝進內核，通過內核于用戶空間mmap同一塊內存保證了只會拷貝一次。（返回的時候不需要拷貝，select要）

   執行epoll_ctl時，除了把socket放到紅黑樹上，還會給內核中斷處理程序注冊一個回調函數，告訴內核，如果這個句柄的中斷到了，就把它放到準備就緒list鏈表里。所以，當一個socket上有數據到了，內核在把網卡上的數據copy到內核中后就把socket插入到準備就緒鏈表里了。鏈表又是通過mmap映射的空間，所以在傳遞給用戶程序的時候不需要復制（這也是為什么比select效率高的原因，epoll_wait返回的只是就緒隊列，不需要輪詢 不需要復制完成的事件列表，select，poll實現需要自己不斷輪詢所有fd集合，直到設備就緒）。

   epoll_wait最后會檢查socket，如果是 LT，并且這些socket上確實有未處理的事件時，又把該句柄放回到剛剛清空的準備就緒鏈表了（LT比ET低效的原因）。

 

可見，如果沒有大量的空閑，無效連接，epoll效率不比select高。

測試數據（僅是剛接觸go的時候好奇做的參考意義的測試）：  

   同樣的環境，echo服務器測并發io，單線程epoll qps:45000左右，每連接/協程 go： 50000多，多線程epoll（開6個epoll，每個epoll開8線程，一共48線程）：qps 70000多。

 

慢啟動：一開始指數級的增加擁塞窗口，到一個門閥值后變成線性的， 之后每次超時都把門閥值降低到原來一半（并且rto翻倍，TCP超時計算是RTOx2，這樣連續丟三次包就變成RTOx8了，十分恐怖），擁塞窗口設置為1重新開始慢啟動（指數級增加）。一切都是為了讓路由器有時間處理積壓的緩沖。（所以不適用于頻繁斷開連接的移動網絡，這也是為什么以前的下載工具開多條tcp傳輸速度更快的原因）。

Nagle算法：第一次（此時沒有等待ack確認，空閑連接）發送小包成功，第二次繼續發送 ：哪怕發送窗口，擁塞窗口都很大，之前的包沒有ack確認依舊不讓發直到收到之前的 ack確認。

shutdown和close的區別:

close只是遞減引用計數， shutdown的半關閉會影響所有的進程。

   工作上雖然和cdn沒關系但是技術方向還是很多相似之處的，例如：負載均衡，緩存，分布式，路由等。
   cdn簡單的說就是個復雜的大緩存，由于目標用戶（包括源和端）廣泛直接導致了其復雜性，遍布廣節點多則需要分流負載甚至自組織，應用繁雜則需要分流路由，提速則需要緩存，穩定則需要監控調度，為了透明則需要各種映射。
   由于接入面廣和網絡的復雜性，不可能讓客戶端直接面對源，于是就有了專門接入客戶端的邊緣服務器/組，這些邊緣服務器和后端的調度，監控，源服務器通訊。既然是緩存就涉及到數據一致性的問題，最簡單的就是各接入端的邊緣服務器在需要的時候到后臺拉取，或者更智能的他們之間可以相互拉取，甚至后臺調度提前推送。
   邊緣接收到請求后首當其沖的問題就是對請求的內容 “去哪找”和“怎么去”，想要知道內容的位置，一般緩存的實現不外乎就是統一到一個目錄服務器找，或者廣播所有自己知道的節點問一圈，更高效的方法是將請求url哈希后直接找到目的地址，當然只要是緩存都會過期也就有TTL的概念。“怎么去”的方式多種多樣，由于互聯網web服務居多基于DNS的路由使用最廣泛，缺點是客戶端和中繼點會緩存，更新需要一定時間。HTTP重定向，URL改寫，也有直接在網絡設備路由器上做，直接在路由表中保持路徑。這些方法在cdn這個龐雜的系統中根據需要使用，例如邊緣服務器為了接收到客戶端的請求可以使用dns重定向，然后再用哈?；蛘遳rl改寫轉發到后端的源。 
   現如今的網絡內容有許多是動態生成的，對這些無法提前緩存的內容可以直接略過只存靜態內容（分段緩存），組裝的時候發送回客戶端或者直接賦予邊緣服務器生成動態內容的能力（邊緣計算）當然這對網頁的制作有規范。
   面向大眾的服務都有潮汐效應，在熱點時段的訪問量是平時的幾十上百倍（根據二八理論，80%的問題都是在20%的地方出現的，熱點訪問量也是大多訪問小部分數據，如果能提前將熱點緩存于各邊緣服務器最直接有效），如果有自適應的動態調整功能整個服務會健壯很多。邊緣服務器是離用戶最近的，可以將每個節點看成組，組長監控負載自適應的添加刪除組員（緩存服務器）以及更新dns，不允許組員跨組拉數據。當然如果客戶端之間可以使用P2P相互取數據也是一個辦法。   
   當前出現了基于流媒體的cdn，視頻內容分發在后端以文件的形式傳輸（適合傳輸的格式更高效），到邊緣服務器再以流的形式和客戶端傳輸（不需要全部傳完即可開始播放）。同時也要綜合考慮時段需求，視頻編碼策略也很重要。

dpdk是通過許多不同的緯度來加速包處理的，其中主要包括：

 

hugepage大頁內存(進程使用的是虛擬地址，一般頁表(4k)能映射的虛擬地址空間有限，使用大頁能減少換頁次數提高cache命中，通過mmap把大頁映射到用戶態的虛擬地址空間有用過mmap的都知道這是實現共享內存的手段，所以dpdk還支持多進程共享內存)

 

cache預取 (每次預讀當前數據相鄰前后的數據)，批量操作數據，cache line對齊(通過浪費一點內存將要操作的數據對齊)

 

接管了網卡用戶態驅動使用輪詢而不是網卡中斷

 

將網卡rx tx隊列映射到用戶態空間實現真正的零拷貝（傳統堆棧至少也得一次拷貝，因為隊列空間在內核而內核和用戶態使用不同的地址空間）(傳統堆棧為了支持通用性，例如ipx等其他網絡，將包處理過程分了很多層次，層之間的接口標準統一數據結構就需要轉換，無形中帶來了巨大的成本，如osi七層模型而實用的就是tcp/ip四層模型)

 

線程綁定cpu

 

支持NUMA，不同的core屬于不同的node，每個node有自己的mempool減少沖突

 

無鎖環形隊列(沖突發生時也是一次cas的開銷)

 

dpdk通過tools/dpdk-setup.sh的腳本，通過編譯、掛載內核模塊， 綁定網卡（先把網卡ifconfig down），設置hugepage后就可以使用了。

 

 

在內核模塊igb加載時，會注冊pci設備驅動

static struct pci_driver igbuio_pci_driver = {

.name = "igb_uio",

.id_table = NULL,

.probe = igbuio_pci_probe,

.remove = igbuio_pci_remove,

};

 

在綁定網卡時，會調用igbuio_pci_probe，使用用戶態驅動uio接管網卡(中斷處理、mmap映射設備內存到用戶空間)

系統啟動時，bios會將設備總線地址信息記錄在/sys/bus/pci/devices，dpdk程序啟動時會去這里掃描pci設備，根據不同類型的NIC有對應的初始化流程。在后面配置隊列的時候會把用戶態的隊列內存地址通過硬件指令交給NIC，從而實現零拷貝。

 

如果NIC收到包，會做標記，輪詢的時候通過標記取數據包

while (nb_rx < nb_pkts) {

/*

 * The order of operations here is important as the DD status

 * bit must not be read after any other descriptor fields.

 * rx_ring and rxdp are pointing to volatile data so the order

 * of accesses cannot be reordered by the compiler. If they were

 * not volatile, they could be reordered which could lead to

 * using invalid descriptor fields when read from rxd.

 */

rxdp = &rx_ring[rx_id];

staterr = rxdp->wb.upper.status_error;

if (! (staterr & rte_cpu_to_le_32(E1000_RXD_STAT_DD)))

break;

rxd = *rxdp;

發包的輪詢就是輪詢發包結束的硬件標志位，硬件發包完成會寫回標志位，驅動發現后再釋放對應的描述符和緩沖塊。

 

KNI

通過創建一個虛擬網卡，將收到的包丟給協議棧

 /* 發送skb到協議棧 */

            /* Call netif interface */

            netif_receive_skb(skb);

 

POWER

在負載小的時候沒有必要使用輪詢模式，這時可以打開網卡中斷 使用eventfd  epoll通知用戶層

 

Ring

無鎖環形隊列的核心就是操作頭尾索引，先將頭尾索引賦給臨時變量，再把尾索引往后跳n個位置，利用cas判斷頭如果還是在原來的位置就指向尾否則就重復這個過程，然后在操作中間跳過的n個元素就是安全的了，此時頭尾索引應該指向同一個位置，如果不同應該是有別的線程也在操作，重復等待即可。(這里有個細節，索引是只加不減的，因為是環形隊列索引又是unsigned 32bits，所以每次取數據前把索引模隊列長度-1， uint32_t mask;           /**< Mask (size-1) of ring. */即可)

 

Windows下使用vmware虛擬機的時候出現EAL: Error reading from file descriptor，根據網上的說法打了patch還是不行，后來嘗試掛載內核模塊的時候不加載vfio模塊就可以了

 

Redis是工作中很常用的，這里將比較普遍使用的結構研究了下做個備忘。

 

hash

實現和dnspod的dataset半斤八兩，本質上是個二維數組，通過將key哈希作為一維的下表，第二維的數組存相同哈希的元素，查找使用遍歷的方式，所以這里redis做了優化，當滿足條件的時候(數組數量太大)會進行rehash，動態擴大桶的數量來減少最后一維遍歷的次數.

函數名稱	作用	復雜度
dictCreate	創建一個新字典	O(1)
dictResize	重新規劃字典的大小	O(1)
dictExpand	擴展字典	O(1)
dictRehash	對字典進行N步漸進式Rehash	O(N)
_dictRehashStep	對字典進行1步嘗試Rehash	O(N)
dictAdd	添加一個元素	O(1)
dictReplace	替換給定key的value值	O(1)
dictDelete	刪除一個元素	O(N)
dictRelease	釋放字典	O(1)
dictFind	查找一個元素	O(N)
dictFetchValue	通過key查找value	O(N)
dictGetRandomKey	隨機返回字典中一個元素	O(1)

 

字典結構

typedef struct dict {

    // 類型特定函數

    dictType *type;

    // 私有數據

    void *privdata;

    // 哈希表

    dictht ht[2];

    // rehash 索引

    // 當 rehash 不在進行時，值為 -1

    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在運行的安全迭代器的數量

    int iterators; /* number of iterators currently running */

} dict;

這里哈希表有兩個，一般都用ht[0]，當需要rehash的時候會創建一個比ht[0]大的 2 的 N 次方的ht[1]，然后漸進式的將數據dictEntry移過去(除了定時的rehash，在每次操作哈希表時都會_dictRehashStep)，完成后將ht[1]替換ht[0]

 

zset

zset本質就是list,只不過每個元素都有若干個指向后繼span長的指針，這樣簡單的設計大大提高了效率，使得可以比擬平衡二叉樹，查找、刪除、插入等操作都可以在對數期望時間內完成，對比平衡樹，跳躍表的實現要簡單直觀很多。

 

 

/* ZSETs use a specialized version of Skiplists */

/*

 * 跳躍表節點

 */

typedef struct zskiplistNode {

    // 成員對象

    robj *obj;

    // 分值

    double score;

    // 后退指針

    struct zskiplistNode *backward;

    // 層

    struct zskiplistLevel {

        // 前進指針

        struct zskiplistNode *forward;

        // 跨度

        unsigned int span;

    } level[];

} zskiplistNode;

 

/*

 * 跳躍表

 */

typedef struct zskiplist {

    // 表頭節點和表尾節點

    struct zskiplistNode *header, *tail;

    // 表中節點的數量

    unsigned long length;

    // 表中層數最大的節點的層數

    int level;

} zskiplist;

 

/*

 * 有序集合

 */

typedef struct zset {

 

    // 字典，鍵為成員，值為分值

    // 用于支持 O(1) 復雜度的按成員取分值操作

    dict *dict;

    // 跳躍表，按分值排序成員

    // 用于支持平均復雜度為 O(log N) 的按分值定位成員操作

    // 以及范圍操作

    zskiplist *zsl;

 

} zset;

 

雖然這種方式排序查找很快，但是修改的話就得多做些工作了

 

/* Delete an element with matching score/object from the skiplist.

 *

 * 從跳躍表 zsl 中刪除包含給定節點 score 并且帶有指定對象 obj 的節點。

 *

 * T_wrost = O(N^2), T_avg = O(N log N)

 */

int zslDelete(zskiplist *zsl, double score, robj *obj)

 

intset

typedef struct intset {  

uint32_t encoding; //所使用類型的長度，4\8\16  

uint32_t length; //元素個數  

int8_t contents[]; //保存元素的數組  

} intset;  

 

intset其實就是數組，有序、無重復地保存多個整數值，查找用的是二分查找 * T = O(log N)，添加的話在找到對應的數組中應該存在的位子后使用memmove向后移出空位填補(當然需要先realloc預分配空間)，同理刪除也是用memmove向前移動

 

set

當使用整數時，使用intset，否則使用哈希表

 

 

其他的關于網絡事件處理，epoll，回調，拆包都和正常使用差不多，關于錯誤處理EINTR(系統調用期間發生中斷)和EAGAIN 繼續重試而如果是EPOLLHUP或EPOLLERR則讓io該讀讀該寫寫，有錯處理就是了。

 

 

 

 

dns的遞歸解析過程還是挺繁瑣的，要知道一個域名可能有cname、ns 而請求的cname、ns可能還有cname、ns，如果按照線性的處理每個請求那邏輯就變成毛線團了

dnspod的處理還是挺巧妙的，通過一個公共的數據集dataset將所有域名對應的a、cname、ns等類型的數據作為單獨的條目存入，當有需要某個域名的信息時先去dataset找，找不到在加入qlist請求根，有專門的線程不間斷的將qlist輪詢dataset找（這里只要次數允許，沒得到想要的結果就輪詢所有qlist到dataset找雖然可以簡化邏輯分離的徹底但是會是個性能瓶頸，后面有方案）當根返回以后只是簡單的將記錄(通常是一個域名的cname、ns或者a)存入dataset(而不是繼續流程，因為根據這個返回是cname還是ns或者a處理不同邏輯復雜，而這樣處理對于用到相同域名的請求還有優化作用)，剩下的工作交給那邊不間斷輪詢的線程

 

Dnspod主要由3個run（若干個線程）組成

 

run_sentinel  監聽53端口接收客戶端請求，將請求放到隊列中

run_fetcher   從隊列中取出請求，根據qname取得最后一級cname，查看本地dataset 是否有記錄，如果有則返回，沒有則將該請求放入qlist中

 

run_quizzer    

1.不間斷的遍歷qlist，只要狀態為PROCESS_QUERY且dataset中沒有的就向對應的根發送請求。

2.通過epoll等待根返回，解析返回的數據加入 dataset

3.檢查記錄的ttl，在將記錄加入dataset時還會將這些記錄以紅黑樹的形式組織起來，取得ttl最早到期的，將其放入qlist中等待刷新，注意這里不是刪除，如果收不到不返回則該記錄一直存在

 

關于dataset的實現

dataset是使用哈希表實現的，本質上是個二維數組，將域名哈希成一個值，模上數組的數量作為下標，找到對應的數組接著遍歷查找，根據需要可以擴大數組的數量提升性能。

 

我們的優化手段

之前提到dnspod的qlist會不間斷輪詢，屬于主動查詢，對性能有不小的影響，這里我們采取的做法是被動(類似回調的方式)，我們將請求的域名和類型分類，相同的放在一組，當dataset找不到向根發出請求后我們并不每次主動輪詢，而是在等到應答后，觸發該域名和類型的請求組，讓他們根據自己的邏輯走下一步（一般是先找該域名的最后一級cname，根據這個cname查是否存在他的對應請求類型的記錄，一般是a或者ns，如果沒有，則找這個cname的ns）

 

以上可以看出dataset很重要，負載也不小，還經常需要并發訪問，這里我們每次接收到根的回復后，除了將記錄的答案加進dataset，還創建一個臨時的dataset，只存該次回復的信息，在后面的流程會優先到這里去找，沒有的再找dataset。

     摘要: 最近在研究DPDK，這是sigcomm 2014的論文，紀錄在此備忘Ps:  文中關鍵詞的概念：segment : 對應于tcp的PDU(協議傳輸單元)，這里應該指tcp層的包，如果一個包太大tcp負責將它拆分成多個segment（這個概念對理解后文有幫助）根據unix網絡編程卷1 第8頁注解2：packet是IP層傳遞給鏈路層并且由鏈路層打包好封裝在幀中的數據（不包括幀頭）而IP層的包...  閱讀全文

一直想用cegui，但是沒機會用，只是抽空看其代碼

最近聽朋友說0.7 debug下幀數提高100多，挺驚訝的，重新到久違了的官網上下了0.7.1

看了下渲染的實現(GL)

首先，添加了GeometryBuffer玩意，使得每個window保存了屬于自己的頂點和紋理信息

然后在RenderingSurface中有GeometryBuffer隊列，使得每個擁有AutoRenderingSurface屬性的window有屬于自己的隊列(默認只有FrameWindow才有)

而在drawself中執行的則是先通過looknfeel，把需要渲染的信息丟到每個部件自己的GeometryBuffer里，然后把GeometryBuffer丟到RenderingSurface的隊列中(一般為

FrameWindow的GeometryBuffer隊列，每個面板就有自己的渲染隊列了)

要知道以往都是只有一個隊列的，要渲染啥直接往里塞。 。 。
這樣一改就不必每個小部件有更改都要全部重新清空渲染了

再往后就是把每個窗口隊列里的GeometryBuffer渲染到各自的RenderingSurface表面上，這里要注意的是并不是渲染到屏幕上而是表面上，cegui在這里使用了渲染到紋理，GL

用的是fbo實現的。

注意RenderingSurface只有兩個來源，一是通過設置AutoRenderingSurface屬性，另一個就是RenderingRoot了，RenderingRoot只有一個，在render中，通過第一個來源的使

用的是fbo的渲染，而第二個來源則直接渲染到屏幕了。

所有的這些執行完后就可以渲染到屏幕了，通過RenderingRoot執行，注意這里的RenderingRoot中的RenderTarget和之前的不一樣，這里用的是OpenGLViewportTarget而不是

OpenGLFBOTextureTarget。

     摘要: 這個看代碼里面batch相關的。[Direct3D] 實現批次渲染、硬件 T&L 的渲染器和 D3DPipeline 在是否從 D3DRender 提供頂點緩存區操作給流水線時做了一些權衡，最后決定暫時使用 IDirect3DDevice9::DrawPrimitiveUP 來渲染，因為它更容易書寫，而且開銷是一次頂點拷貝，流水線也不用操心對緩存的使用。 (DrawPrimitive的...  閱讀全文