xiaoxiaoling

將博客搬至CSDN

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

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

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

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

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

epoll實現(xiàn)：  
   epoll內(nèi)部用了一個紅黑樹記錄添加的socket，用了一個雙向鏈表接收內(nèi)核觸發(fā)的事件。

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

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

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

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

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

 

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

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

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

 

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

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

shutdown和close的區(qū)別:

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

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

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

 

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

 

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

 

接管了網(wǎng)卡用戶態(tài)驅(qū)動使用輪詢而不是網(wǎng)卡中斷

 

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

 

線程綁定cpu

 

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

 

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

 

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

 

 

在內(nèi)核模塊igb加載時，會注冊pci設備驅(qū)動

static struct pci_driver igbuio_pci_driver = {

.name = "igb_uio",

.id_table = NULL,

.probe = igbuio_pci_probe,

.remove = igbuio_pci_remove,

};

 

在綁定網(wǎng)卡時，會調(diào)用igbuio_pci_probe，使用用戶態(tài)驅(qū)動uio接管網(wǎng)卡(中斷處理、mmap映射設備內(nèi)存到用戶空間)

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

 

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

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;

發(fā)包的輪詢就是輪詢發(fā)包結(jié)束的硬件標志位，硬件發(fā)包完成會寫回標志位，驅(qū)動發(fā)現(xiàn)后再釋放對應的描述符和緩沖塊。

 

KNI

通過創(chuàng)建一個虛擬網(wǎng)卡，將收到的包丟給協(xié)議棧

 /* 發(fā)送skb到協(xié)議棧 */

            /* Call netif interface */

            netif_receive_skb(skb);

 

POWER

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

 

Ring

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

 

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

 

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

 

hash

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

函數(shù)名稱	作用	復雜度
dictCreate	創(chuàng)建一個新字典	O(1)
dictResize	重新規(guī)劃字典的大小	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)

 

字典結(jié)構

typedef struct dict {

    // 類型特定函數(shù)

    dictType *type;

    // 私有數(shù)據(jù)

    void *privdata;

    // 哈希表

    dictht ht[2];

    // rehash 索引

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

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

    // 目前正在運行的安全迭代器的數(shù)量

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

} dict;

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

 

zset

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

 

 

/* ZSETs use a specialized version of Skiplists */

/*

 * 跳躍表節(jié)點

 */

typedef struct zskiplistNode {

    // 成員對象

    robj *obj;

    // 分值

    double score;

    // 后退指針

    struct zskiplistNode *backward;

    // 層

    struct zskiplistLevel {

        // 前進指針

        struct zskiplistNode *forward;

        // 跨度

        unsigned int span;

    } level[];

} zskiplistNode;

 

/*

 * 跳躍表

 */

typedef struct zskiplist {

    // 表頭節(jié)點和表尾節(jié)點

    struct zskiplistNode *header, *tail;

    // 表中節(jié)點的數(shù)量

    unsigned long length;

    // 表中層數(shù)最大的節(jié)點的層數(shù)

    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 中刪除包含給定節(jié)點 score 并且?guī)в兄付▽ο?obj 的節(jié)點。

 *

 * 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; //元素個數(shù)  

int8_t contents[]; //保存元素的數(shù)組  

} intset;  

 

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

 

set

當使用整數(shù)時，使用intset，否則使用哈希表

 

 

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

 

 

 

 

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

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

 

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

 

run_sentinel  監(jiān)聽53端口接收客戶端請求，將請求放到隊列中

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

 

run_quizzer    

1.不間斷的遍歷qlist，只要狀態(tài)為PROCESS_QUERY且dataset中沒有的就向?qū)母l(fā)送請求。

2.通過epoll等待根返回，解析返回的數(shù)據(jù)加入 dataset

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

 

關于dataset的實現(xiàn)

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

 

我們的優(yōu)化手段

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

 

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

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

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

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

看了下渲染的實現(xiàn)(GL)

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

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

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

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

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

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

用的是fbo實現(xiàn)的。

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

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

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

OpenGLFBOTextureTarget。

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