亚洲国产精品久久久天堂,日韩中文久久,久久99国产精品成人欧美

寫了一個分布式名字服務(wù)JCM

之前在公司里維護(hù)了一個名字服務(wù)，這個名字服務(wù)日常管理了近4000臺機(jī)器，有4000個左右的客戶端連接上來獲取機(jī)器信息，由于其基本是一個單點服務(wù)，所以某些模塊接近瓶頸。后來倒是有重構(gòu)計劃，詳細(xì)設(shè)計做了，代碼都寫了一部分，結(jié)果由于某些原因重構(gòu)就被終止了。

JCM是我業(yè)余時間用Java重寫的一個版本，功能上目前只實現(xiàn)了基礎(chǔ)功能。由于它是個完全分布式的架構(gòu)，所以理論上可以橫向擴(kuò)展，大大增強(qiáng)系統(tǒng)的服務(wù)能力。

名字服務(wù)

在分布式系統(tǒng)中，某個服務(wù)為了提升整體服務(wù)能力，通常部署了很多實例。這里我把這些提供相同服務(wù)的實例統(tǒng)稱為集群(cluster)，每個實例稱為一個節(jié)點(Node)。一個應(yīng)用可能會使用很多cluster，每次訪問一個cluster時，就通過名字服務(wù)獲取該cluster下一個可用的node。那么，名字服務(wù)至少需要包含的功能：

根據(jù)cluster名字獲取可用的node
對管理的所有cluster下的所有node進(jìn)行健康度的檢測，以保證始終返回可用的node

有些名字服務(wù)僅對node管理，不參與應(yīng)用與node間的通信，而有些則可能作為應(yīng)用與node間的通信轉(zhuǎn)發(fā)器。雖然名字服務(wù)功能簡單，但是要做一個分布式的名字服務(wù)還是比較復(fù)雜的，因為數(shù)據(jù)一旦分布式了，就會存在同步、一致性問題的考慮等。

What’s JCM

JCM圍繞前面說的名字服務(wù)基礎(chǔ)功能實現(xiàn)。包含的功能：

管理cluster到node的映射
分布式架構(gòu)，可水平擴(kuò)展以實現(xiàn)管理10,000個node的能力，足以管理一般公司的后臺服務(wù)集群
對每個node進(jìn)行健康檢查，健康檢查可基于HTTP協(xié)議層的檢測或TCP連接檢測
持久化cluster/node數(shù)據(jù)，通過zookeeper保證數(shù)據(jù)一致性
提供JSON HTTP API管理cluster/node數(shù)據(jù)，后續(xù)可提供Web管理系統(tǒng)
以庫的形式提供與server的交互，庫本身提供各種負(fù)載均衡策略，保證對一個cluster下node的訪問達(dá)到負(fù)載均衡

項目地址git jcm

JCM主要包含兩部分：

jcm.server，JCM名字服務(wù)，需要連接zookeeper以持久化數(shù)據(jù)
jcm.subscriber，客戶端庫，負(fù)責(zé)與jcm.server交互，提供包裝了負(fù)載均衡的API給應(yīng)用使用

架構(gòu)

基于JCM的系統(tǒng)整體架構(gòu)如下：

cluster本身是不需要依賴JCM的，要通過JCM使用這些cluster，只需要通過JCM HTTP API注冊這些cluster到j(luò)cm.server上。要通過jcm.server使用這些cluster，則是通過jcm.subscriber來完成。

使用

可參考git READMe.md

需要jre1.7+

啟動zookeeper
下載jcm.server git jcm.server-0.1.0.jar
在jcm.server-0.1.0.jar目錄下建立config/application.properties文件進(jìn)行配置，參考config/application.properties
啟動jcm.server
```
 java -jar jcm.server-0.1.0.jar
```

注冊需要管理的集群，參考cluster描述：doc/cluster_sample.json，通過HTTP API注冊：

 curl -i -X POST http://10.181.97.106:8080/c -H "Content-Type:application/json" --data-binary @./doc/cluster_sample.json

部署好了jcm.server，并注冊了cluster后，就可以通過jcm.subscriber使用：

// 傳入需要使用的集群名hello9/hello，以及傳入jcm.server地址，可以多個：127.0.0.1:8080
Subscriber subscriber = new Subscriber( Arrays.asList("127.0.0.1:8080"), Arrays.asList("hello9", "hello"));
// 使用輪詢負(fù)載均衡策略
RRAllocator rr = new RRAllocator();
subscriber.addListener(rr);
subscriber.startup();
for (int i = 0; i < 2; ++i) {
  // rr.alloc 根據(jù)cluster名字獲取可用的node
  System.out.println(rr.alloc("hello9", ProtoType.HTTP));
}
subscriber.shutdown();

JCM實現(xiàn)

JCM目前的實現(xiàn)比較簡單，參考模塊圖：

impl-module

model，即cluster/node這些數(shù)據(jù)結(jié)構(gòu)的描述，同時被jcm.server和jcm.subscriber依賴
storage，持久化數(shù)據(jù)到zookeeper，同時包含jcm.server實例之間的數(shù)據(jù)同步
health check，健康檢查模塊，對各個node進(jìn)行健康檢查

以上模塊都不依賴Spring，基于以上模塊又有：

http api，使用spring-mvc，包裝了一些JSON HTTP API
Application，基于spring-boot，將各個基礎(chǔ)模塊組裝起來，提供standalone的模式啟動，不用部署到tomcat之類的servlet容器中

jcm.subscriber的實現(xiàn)更簡單，主要是負(fù)責(zé)與jcm.server進(jìn)行通信，以更新自己當(dāng)前的model層數(shù)據(jù)，同時提供各種負(fù)載均衡策略接口：

subscriber，與jcm.server通信，定期增量拉取數(shù)據(jù)
node allocator，通過listener方式從subscriber中獲取數(shù)據(jù)，同時實現(xiàn)各種負(fù)載均衡策略，對外統(tǒng)一提供alloc node的接口

接下來看看關(guān)鍵功能的實現(xiàn)

數(shù)據(jù)同步

既然jcm.server是分布式的，每一個jcm.server instance(實例)都是支持?jǐn)?shù)據(jù)讀和寫的，那么當(dāng)jcm.server管理著一堆cluster上萬個node時，每一個instance是如何進(jìn)行數(shù)據(jù)同步的？jcm.server中的數(shù)據(jù)主要有兩類：

cluster本身的數(shù)據(jù)，包括cluster/node的描述，例如cluster name、node IP、及其他附屬數(shù)據(jù)
node健康檢查的數(shù)據(jù)

對于cluster數(shù)據(jù)，因為cluster對node的管理是一個兩層的樹狀結(jié)構(gòu)，而對cluster有增刪node的操作，所以并不能在每一個instance上都提供真正的數(shù)據(jù)寫入，這樣會導(dǎo)致數(shù)據(jù)丟失。假設(shè)同一時刻在instance A和instance B上同時對cluster c1添加節(jié)點N1和N2，那么instance A寫入c1(N1)，而instance B還沒等到數(shù)據(jù)同步就寫入c1(N2)，那么c1(N1)就被覆蓋為c1(N2)，從而導(dǎo)致添加的節(jié)點N1丟失。

所以，jcm.server instance是分為leader和follower的，真正的寫入操作只有l(wèi)eader進(jìn)行，follower收到寫操作請求時轉(zhuǎn)發(fā)給leader。leader寫數(shù)據(jù)優(yōu)先更新內(nèi)存中的數(shù)據(jù)再寫入zookeeper，內(nèi)存中的數(shù)據(jù)更新當(dāng)然是需要加鎖互斥的，從而保證數(shù)據(jù)的正確性。

leader和follower是如何確定角色的？這個很簡單，標(biāo)準(zhǔn)的利用zookeeper來進(jìn)行主從選舉的實現(xiàn)。

jcm.server instance數(shù)據(jù)間的同步是基于zookeeper watch機(jī)制的。這個可以算做是一個JCM的一個瓶頸，每一個instance都會作為一個watch，使得實際上jcm.server并不能無限水平擴(kuò)展，擴(kuò)展到一定程度后，watch的效率就可能不足以滿足性能了，參考zookeeper節(jié)點數(shù)與watch的性能測試 (那個時候我就在考慮對我們系統(tǒng)的重構(gòu)了) 。

jcm.server中對node健康檢查的數(shù)據(jù)采用同樣的同步機(jī)制，但node健康檢查數(shù)據(jù)是每一個instance都會寫入的，下面看看jcm.server是如何通過分布式架構(gòu)來分擔(dān)壓力的。

健康檢查

jcm.server的另一個主要功能的是對node的健康檢查，jcm.server集群可以管理幾萬的node，既然已經(jīng)是分布式了，那么顯然是要把node均分到多個instance的。這里我是以cluster來分配的，方法就是簡單的使用一致性哈希。通過一致性哈希，決定一個cluster是否屬于某個instance負(fù)責(zé)。每個instance都有一個server spec，也就是該instance對外提供服務(wù)的地址(IP+port)，這樣在任何一個instance上，它看到的所有instance server spec都是相同的，從而保證在每一個instance上計算cluster的分配得到的結(jié)果都是一致的。

健康檢查按cluster劃分，可以簡化數(shù)據(jù)的寫沖突問題，在正常情況下，每個instance寫入的健康檢查結(jié)果都是不同的。

健康檢查一般以1秒的頻率進(jìn)行，jcm.server做了優(yōu)化，當(dāng)檢查結(jié)果和上一次一樣時，并不寫入zookeeper。寫入的數(shù)據(jù)包含了node的完整key (IP+Port+Spec)，這樣可以簡化很多地方的數(shù)據(jù)同步問題，但會增加寫入數(shù)據(jù)的大小，寫入數(shù)據(jù)的大小是會影響zookeeper的性能的，所以這里簡單地對數(shù)據(jù)進(jìn)行了壓縮。

健康檢查是可以支持多種檢查實現(xiàn)的，目前只實現(xiàn)了HTTP協(xié)議層的檢查。健康檢查自身是單個線程，在該線程中基于異步HTTP庫，發(fā)起異步請求，實際的請求在其他線程中發(fā)出。

jcm.subscriber通信

jcm.subscriber與jcm.server通信，主要是為了獲取最新的cluster數(shù)據(jù)。subscriber初始化時會拿到一個jcm.server instance的地址列表，訪問時使用輪詢策略以平衡jcm.server在處理請求時的負(fù)載。subscriber每秒都會請求一次數(shù)據(jù)，請求中描述了本次請求想獲取哪些cluster數(shù)據(jù)，同時攜帶一個cluster的version。每次cluster在server變更時，version就變更（時間戳）。server回復(fù)請求時，如果version已最新，只需要回復(fù)node的狀態(tài)。

subscriber可以拿到所有狀態(tài)的node，后面可以考慮只拿正常狀態(tài)的node，進(jìn)一步減少數(shù)據(jù)大小。

壓力測試

目前只對健康檢查部分做了壓測，詳細(xì)參考test/benchmark.md。在A7服務(wù)器上測試，發(fā)現(xiàn)寫zookeeper及zookeeper的watch足以滿足要求，jcm.server發(fā)起的HTTP請求是主要的性能熱點，單jcm.server instance大概可以承載20000個node的健康監(jiān)測。

網(wǎng)絡(luò)帶寬：

Time              ---------------------traffic--------------------
Time               bytin  bytout   pktin  pktout  pkterr  pktdrp
01/07/15-21:30:48   3.2M    4.1M   33.5K   34.4K    0.00    0.00
01/07/15-21:30:50   3.3M    4.2M   33.7K   35.9K    0.00    0.00
01/07/15-21:30:52   2.8M    4.1M   32.6K   41.6K    0.00    0.00

CPU，通過jstack查看主要的CPU消耗在HTTP庫實現(xiàn)層，以及健康檢查線程：

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
admin     20   0 13.1g 1.1g  12m R 76.6  2.3   2:40.74 java         httpchecker
admin     20   0 13.1g 1.1g  12m S 72.9  2.3   0:48.31 java
admin     20   0 13.1g 1.1g  12m S 20.1  2.3   0:18.49 java

代碼中增加了些狀態(tài)監(jiān)控：

checker HttpChecker stat count 20 avg check cost(ms) 542.05, avg flush cost(ms) 41.35

表示平均每次檢查耗時542毫秒，寫數(shù)據(jù)因為開啟了cache沒有參考價值。

雖然還可以從我自己的代碼中做不少優(yōu)化，但既然單機(jī)可以承載20000個節(jié)點的檢測，一般的應(yīng)用遠(yuǎn)遠(yuǎn)足夠了。

總結(jié)

名字服務(wù)在分布式系統(tǒng)中雖然是基礎(chǔ)服務(wù)，但往往承擔(dān)了非常重要的角色，數(shù)據(jù)同步出現(xiàn)錯誤、節(jié)點狀態(tài)出現(xiàn)瞬時的錯誤，都可能對整套系統(tǒng)造成較大影響，業(yè)務(wù)上出現(xiàn)較大故障。所以名字服務(wù)的健壯性、可用性非常重要。實現(xiàn)中需要考慮很多異常情況，包括網(wǎng)絡(luò)不穩(wěn)定、應(yīng)用層的錯誤等。為了提高足夠的可用性，一般還會加多層的數(shù)據(jù)cache，例如subscriber端的本地cache，server端的本地cache，以保證在任何情況下都不會影響應(yīng)用層的服務(wù)。

posted @ 2015-07-04 17:50 Kevin Lynx 閱讀(1744) | 評論 (0) | 編輯收藏

無鎖有序鏈表的實現(xiàn)

無鎖有序鏈表可以保證元素的唯一性，使其可用于哈希表的桶，甚至直接作為一個效率不那么高的map。普通鏈表的無鎖實現(xiàn)相對簡單點，因為插入元素可以在表頭插，而有序鏈表的插入則是任意位置。

本文主要基于論文High Performance Dynamic Lock-Free Hash Tables實現(xiàn)。

主要問題

鏈表的主要操作包含insert和remove，先簡單實現(xiàn)一個版本，就會看到問題所在，以下代碼只用作示例：

struct node_t {
        key_t key;
        value_t val;
        node_t *next;
    };

    int l_find(node_t **pred_ptr, node_t **item_ptr, node_t *head, key_t key) {
        node_t *pred = head;
        node_t *item = head->next;
        while (item) {
            int d = KEY_CMP(item->key, key);
            if (d >= 0) {
                *pred_ptr = pred;
                *item_ptr = item;
                return d == 0 ? TRUE : FALSE;
            }
            pred = item;
            item = item->next;
        } 
        *pred_ptr = pred;
        *item_ptr = NULL;
        return FALSE;
    }

    int l_insert(node_t *head, key_t key, value_t val) {
        node_t *pred, *item, *new_item;
        while (TRUE) {
            if (l_find(&pred, &item, head, key)) {
                return FALSE;
            }
            new_item = (node_t*) malloc(sizeof(node_t));
            new_item->key = key;
            new_item->val = val;
            new_item->next = item;
            // A. 如果pred本身被移除了
            if (CAS(&pred->next, item, new_item)) {
                return TRUE;
            }
            free(new_item);
        }
    }

    int l_remove(node_t *head, key_t key) {
        node_t *pred, *item;
        while (TRUE) {
            if (!l_find(&pred, &item, head, key)) {
                return TRUE;
            }
            // B. 如果pred被移除；如果item也被移除
            if (CAS(&pred->next, item, item->next)) {
                haz_free(item);
                return TRUE;
            }
        }
    }

l_find函數(shù)返回查找到的前序元素和元素本身，代碼A和B雖然拿到了pred和item，但在CAS的時候，其可能被其他線程移除。甚至，在l_find過程中，其每一個元素都可能被移除。問題在于，任何時候拿到一個元素時，都不確定其是否還有效。元素的有效性包括其是否還在鏈表中，其指向的內(nèi)存是否還有效。

解決方案

通過為元素指針增加一個有效性標(biāo)志位，配合CAS操作的互斥性，就可以解決元素有效性判定問題。

因為node_t放在內(nèi)存中是會對齊的，所以指向node_t的指針值低幾位是不會用到的，從而可以在低幾位里設(shè)置標(biāo)志，這樣在做CAS的時候，就實現(xiàn)了DCAS的效果，相當(dāng)于將兩個邏輯上的操作變成了一個原子操作。想象下引用計數(shù)對象的線程安全性，其內(nèi)包裝的指針是線程安全的，但對象本身不是。

CAS的互斥性，在若干個線程CAS相同的對象時，只有一個線程會成功，失敗的線程就可以以此判定目標(biāo)對象發(fā)生了變更。改進(jìn)后的代碼（代碼僅做示例用，不保證正確）：

typedef size_t markable_t;
    // 最低位置1，表示元素被刪除
    #define HAS_MARK(p) ((markable_t)p & 0x01)
    #define MARK(p) ((markable_t)p | 0x01)
    #define STRIP_MARK(p) ((markable_t)p & ~0x01)

    int l_insert(node_t *head, key_t key, value_t val) {
        node_t *pred, *item, *new_item;
        while (TRUE) {
            if (l_find(&pred, &item, head, key)) { 
                return FALSE;
            }
            new_item = (node_t*) malloc(sizeof(node_t));
            new_item->key = key;
            new_item->val = val;
            new_item->next = item;
            // A. 雖然find拿到了合法的pred，但是在以下代碼之前pred可能被刪除，此時pred->next被標(biāo)記
            //    pred->next != item，該CAS會失敗，失敗后重試
            if (CAS(&pred->next, item, new_item)) {
                return TRUE;
            }
            free(new_item);
        }
        return FALSE;
    }

    int l_remove(node_t *head, key_t key) {
        node_t *pred, *item;
        while (TRUE) {
            if (!l_find(&pred, &item, head, key)) {
                return FALSE;
            }
            node_t *inext = item->next;
            // B. 刪除item前先標(biāo)記item->next，如果CAS失敗，那么情況同insert一樣，有其他線程在find之后
            //    刪除了item，失敗后重試
            if (!CAS(&item->next, inext, MARK(inext))) {
                continue;
            }
            // C. 對同一個元素item刪除時，只會有一個線程成功走到這里
            if (CAS(&pred->next, item, STRIP_MARK(item->next))) {
                haz_defer_free(item);
                return TRUE;
            }
        }
        return FALSE;
    }

    int l_find(node_t **pred_ptr, node_t **item_ptr, node_t *head, key_t key) {
        node_t *pred = head;
        node_t *item = head->next;
        hazard_t *hp1 = haz_get(0);
        hazard_t *hp2 = haz_get(1);
        while (item) {
            haz_set_ptr(hp1, pred);
            haz_set_ptr(hp2, item);
            /* 
             如果已被標(biāo)記，那么緊接著item可能被移除鏈表甚至釋放，所以需要重頭查找
            */
            if (HAS_MARK(item->next)) { 
                return l_find(pred_ptr, item_ptr, head, key);
            }
            int d = KEY_CMP(item->key, key);
            if (d >= 0) {
                *pred_ptr = pred;
                *item_ptr = item;
                return d == 0 ? TRUE : FALSE;
            }
            pred = item;
            item = item->next;
        } 
        *pred_ptr = pred;
        *item_ptr = NULL;
        return FALSE;
    }

haz_get、haz_set_ptr之類的函數(shù)是一個hazard pointer實現(xiàn)，用于支持多線程下內(nèi)存的GC。上面的代碼中，要刪除一個元素item時，會標(biāo)記item->next，從而使得insert時中那個CAS不需要做任何調(diào)整。總結(jié)下這里的線程競爭情況：

insert中find到正常的pred及item，pred->next == item，然后在CAS前有線程刪除了pred，此時pred->next == MARK(item)，CAS失敗，重試；刪除分為2種情況：a) 從鏈表移除，得到標(biāo)記，pred可繼續(xù)訪問；b) pred可能被釋放內(nèi)存，此時再使用pred會錯誤。為了處理情況b，所以引入了類似hazard pointer的機(jī)制，可以有效保障任意一個指針p只要還有線程在使用它，它的內(nèi)存就不會被真正釋放
insert中有多個線程在pred后插入元素，此時同樣由insert中的CAS保證，這個不多說
remove中情況同insert，find拿到了有效的pred和next，但在CAS的時候pred被其他線程刪除，此時情況同insert，CAS失敗，重試
任何時候改變鏈表結(jié)構(gòu)時，無論是remove還是insert，都需要重試該操作
find中遍歷時，可能會遇到被標(biāo)記刪除的item，此時item根據(jù)remove的實現(xiàn)很可能被刪除，所以需要重頭開始遍歷

ABA問題

ABA問題還是存在的，insert中：

if (CAS(&pred->next, item, new_item)) {
        return TRUE;
    }

如果CAS之前，pred后的item被移除，又以相同的地址值加進(jìn)來，但其value變了，此時CAS會成功，但鏈表可能就不是有序的了。pred->val < new_item->val > item->val

為了解決這個問題，可以利用指針值地址對齊的其他位來存儲一個計數(shù)，用于表示pred->next的改變次數(shù)。當(dāng)insert拿到pred時，pred->next中存儲的計數(shù)假設(shè)是0，CAS之前其他線程移除了pred->next又新增回了item，此時pred->next中的計數(shù)增加，從而導(dǎo)致insert中CAS失敗。

// 最低位留作刪除標(biāo)志
    #define MASK ((sizeof(node_t) - 1) & ~0x01)

    #define GET_TAG(p) ((markable_t)p & MASK)
    #define TAG(p, tag) ((markable_t)p | (tag))
    #define MARK(p) ((markable_t)p | 0x01)
    #define HAS_MARK(p) ((markable_t)p & 0x01)
    #define STRIP_MARK(p) ((node_t*)((markable_t)p & ~(MASK | 0x01)))

remove的實現(xiàn)：

/* 先標(biāo)記再刪除 */
    if (!CAS(&sitem->next, inext, MARK(inext))) {
        continue;
    }
    int tag = GET_TAG(pred->next) + 1;
    if (CAS(&pred->next, item, TAG(STRIP_MARK(sitem->next), tag))) {
        haz_defer_free(sitem);
        return TRUE;
    }

insert中也可以更新pred->next的計數(shù)。

總結(jié)

無鎖的實現(xiàn)，本質(zhì)上都會依賴于CAS的互斥性。從頭實現(xiàn)一個lock free的數(shù)據(jù)結(jié)構(gòu)，可以深刻感受到lock free實現(xiàn)的tricky。最終代碼可以從這里github獲取。代碼中為了簡單，實現(xiàn)了一個不是很強(qiáng)大的hazard pointer，可以參考之前的博文。

posted @ 2015-05-05 19:47 Kevin Lynx 閱讀(22648) | 評論 (0) | 編輯收藏

并行編程中的內(nèi)存回收Hazard Pointer

接上篇使用RCU技術(shù)實現(xiàn)讀寫線程無鎖，在沒有GC機(jī)制的語言中，要實現(xiàn)Lock free的算法，就免不了要自己處理內(nèi)存回收的問題。

Hazard Pointer是另一種處理這個問題的算法，而且相比起來不但簡單，功能也很強(qiáng)大。鎖無關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針中講得很好，Wikipedia Hazard pointer也描述得比較清楚，所以我這里就不講那么細(xì)了。

一個簡單的實現(xiàn)可以參考我的github haz_ptr.c

原理

基本原理無非也是讀線程對指針進(jìn)行標(biāo)識，指針(指向的內(nèi)存)要釋放時都會緩存起來延遲到確認(rèn)沒有讀線程了才對其真正釋放。

<Lock-Free Data Structures with Hazard Pointers>中的描述：

Each reader thread owns a single-writer/multi-reader shared pointer called “hazard pointer.” When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), “I am reading this map. You can replace it if you want, but don’t change its contents and certainly keep your deleteing hands off it.”

關(guān)鍵的結(jié)構(gòu)包括：Hazard pointer、Thread Free list

Hazard pointer：一個讀線程要使用一個指針時，就會創(chuàng)建一個Hazard pointer包裝這個指針。一個Hazard pointer會被一個線程寫，多個線程讀。

struct HazardPointer {
        void *real_ptr; // 包裝的指針
        ... // 不同的實現(xiàn)有不同的成員
    };

    void func() {
        HazardPointer *hp = accquire(_real_ptr);
        ... // use _real_ptr
        release(hp);
    }

Thread Free List：每個線程都有一個這樣的列表，保存著將要釋放的指針列表，這個列表僅對應(yīng)的線程讀寫

void defer_free(void *ptr) {
        _free_list.push_back(ptr);
    }

當(dāng)某個線程要嘗試釋放Free List中的指針時，例如指針ptr，就檢查所有其他線程使用的Hazard pointer，檢查是否存在包裝了ptr的Hazard pointer，如果沒有則說明沒有讀線程正在使用ptr，可以安全釋放ptr。

void gc() {
        for(ptr in _free_list) {
            conflict = false
            for (hp in _all_hazard_pointers) {
                if (hp->_real_ptr == ptr) {
                    confilict = true
                    break
                }
            }
            if (!conflict)
                delete ptr
        }
    }

以上，其實就是Hazard Pointer的主要內(nèi)容。

Hazard Pointer的管理

上面的代碼中沒有提到_all_hazard_pointers及accquire的具體實現(xiàn)，這就是Hazard Pointer的管理問題。

《鎖無關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針》文中創(chuàng)建了一個Lock free的鏈表來表示這個全局的Hazard Pointer List。每個Hazard Pointer有一個成員標(biāo)識其是否可用。這個List中也就保存了已經(jīng)被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合，當(dāng)所有Hazard Pointer都被使用時，就會新分配一個加進(jìn)這個List。當(dāng)讀線程不使用指針時，需要歸還Hazard Pointer，直接設(shè)置可用成員標(biāo)識即可。要gc()時，就直接遍歷這個List。

要實現(xiàn)一個Lock free的鏈表，并且僅需要實現(xiàn)頭插入，還是非常簡單的。本身Hazard Pointer標(biāo)識某個指針時，都是用了后立即標(biāo)識，所以這個實現(xiàn)直接支持了動態(tài)線程，支持線程的掛起等。

在nbds項目中也有一個Hazard Pointer的實現(xiàn)，相對要弱一點。它為每個線程都設(shè)置了自己的Hazard Pointer池，寫線程要釋放指針時，就訪問所有其他線程的Hazard Pointer池。

typedef struct haz_local {
        // Free List
        pending_t *pending; // to be freed
        int pending_size;
        int pending_count;

        // Hazard Pointer 池，動態(tài)和靜態(tài)兩種
        haz_t static_haz[STATIC_HAZ_PER_THREAD];

        haz_t **dynamic;
        int dynamic_size;
        int dynamic_count;

    } __attribute__ ((aligned(CACHE_LINE_SIZE))) haz_local_t;

    static haz_local_t haz_local_[MAX_NUM_THREADS] = {};

每個線程當(dāng)然就涉及到haz_local_索引(ID)的分配，就像使用RCU技術(shù)實現(xiàn)讀寫線程無鎖中的一樣。這個實現(xiàn)為了支持線程動態(tài)創(chuàng)建，就需要一套線程ID的重用機(jī)制，相對復(fù)雜多了。

附錄

最后，附上一些并行編程中的一些概念。

Lock Free & Wait Free

常常看到Lock Free和Wait Free的概念，這些概念用于衡量一個系統(tǒng)或者說一段代碼的并行級別，并行級別可參考并行編程——并發(fā)級別。總之Wait Free是一個比Lock Free更牛逼的級別。

我自己的理解，例如《鎖無關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針》中實現(xiàn)的Hazard Pointer鏈表就可以說是Lock Free的，注意它在插入新元素到鏈表頭時，因為使用CAS，總免不了一個busy loop，有這個特征的情況下就算是Lock Free，雖然沒鎖，但某個線程的執(zhí)行情況也受其他線程的影響。

相對而言，Wait Free則是每個線程的執(zhí)行都是獨立的，例如《鎖無關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針》中的Scan函數(shù)。“每個線程的執(zhí)行時間都不依賴于其它任何線程的行為”

鎖無關(guān)(Lock-Free)意味著系統(tǒng)中總存在某個線程能夠得以繼續(xù)執(zhí)行；而等待無關(guān)(Wait-Free)則是一個更強(qiáng)的條件，它意味著所有線程都能往下進(jìn)行。

ABA問題

在實現(xiàn)Lock Free算法的過程中，總是要使用CAS原語的，而CAS就會帶來ABA問題。

在進(jìn)行CAS操作的時候，因為在更改V之前，CAS主要詢問“V的值是否仍然為A”，所以在第一次讀取V之后以及對V執(zhí)行CAS操作之前，如果將值從A改為B，然后再改回A，會使基于CAS的算法混亂。在這種情況下，CAS操作會成功。這類問題稱為ABA問題。

Wiki Hazard Pointer提到了一個ABA問題的好例子：在一個Lock free的棧實現(xiàn)中，現(xiàn)在要出棧，棧里的元素是[A, B, C]，head指向棧頂，那么就有compare_and_swap(target=&head, newvalue=B, expected=A)。但是在這個操作中，其他線程把A B都出棧，且刪除了B，又把A壓入棧中，即[A, C]。那么前一個線程的compare_and_swap能夠成功，此時head指向了一個已經(jīng)被刪除的B。stackoverflow上也有個例子 Real-world examples for ABA in multithreading

對于CAS產(chǎn)生的這個ABA問題，通常的解決方案是采用CAS的一個變種DCAS。DCAS，是對于每一個V增加一個引用的表示修改次數(shù)的標(biāo)記符。對于每個V，如果引用修改了一次，這個計數(shù)器就加1。然后再這個變量需要update的時候，就同時檢查變量的值和計數(shù)器的值。

但也早有人提出DCAS也不是ABA problem 的銀彈。

posted @ 2015-05-03 20:46 Kevin Lynx 閱讀(20016) | 評論 (0) | 編輯收藏

使用RCU技術(shù)實現(xiàn)讀寫線程無鎖

在一個系統(tǒng)中有一個寫線程和若干個讀線程，讀寫線程通過一個指針共用了一個數(shù)據(jù)結(jié)構(gòu)，寫線程改寫這個結(jié)構(gòu)，讀線程讀取該結(jié)構(gòu)。在寫線程改寫這個數(shù)據(jù)結(jié)構(gòu)的過程中，加鎖情況下讀線程由于等待鎖耗時會增加。

可以利用RCU (Read Copy Update What is rcu)的思想來去除這個鎖。本文提到的主要實現(xiàn)代碼：gist

RCU

RCU可以說是一種替代讀寫鎖的方法。其基于一個事實：當(dāng)寫線程在改變一個指針時，讀線程獲取這個指針，要么獲取到老的值，要么獲取到新的值。RCU的基本思想其實很簡單，參考What is RCU中Toy implementation可以很容易理解。一種簡單的RCU流程可以描述為：

寫線程：

old_ptr = _ptr
tmp_ptr = copy(_ptr)     // copy
change(tmp_ptr)          // change 
_ptr = tmp_ptr           // update
synchroize(tmp_ptr)

寫線程要更新_ptr指向的內(nèi)容時，先復(fù)制一份新的，基于新的進(jìn)行改變，更新_ptr指針，最后同步釋放老的內(nèi)存。

讀線程：

tmp_ptr = _ptr
use(tmp_ptr)
dereference(tmp_ptr)

讀線程直接使用_ptr，使用完后需要告訴寫線程自己不再使用_ptr。讀線程獲取_ptr時，可能會獲取到老的也可能獲取到新的，無論哪種RCU都需要保證這塊內(nèi)存是有效的。重點在synchroize和dereference。synchroize會等待所有使用老的_ptr的線程dereference，對于新的_ptr使用者其不需要等待。這個問題說白了就是寫線程如何知道old_ptr沒有任何讀線程在使用，可以安全地釋放。

這個問題實際上在wait-free的各種實現(xiàn)中有好些解法，how-when-to-release-memory-in-wait-free-algorithms這里有人總結(jié)了幾種方法，例如Hazard pointers、Quiescence period based reclamation。

簡單地使用引用計數(shù)智能指針是無法解決這個問題的，因為智能指針自己不是線程安全的，例如：

tmp_ptr = _ptr      // 1
tmp_ptr->addRef()   // 2
use
tmp_ptr->release()

代碼1/2行不是原子的，所以當(dāng)取得tmp_ptr準(zhǔn)備addRef時，tmp_ptr可能剛好被釋放了。

Quiescence period based reclamation方法指的是讀線程需要聲明自己處于Quiescence period，也就是不使用_ptr的時候，當(dāng)其使用_ptr的時候?qū)嶋H是進(jìn)入了一個邏輯上的臨界區(qū)，當(dāng)所有讀線程都不再使用_ptr的時候，寫線程就可以對內(nèi)存進(jìn)行安全地釋放。

本文正是描述了一種Quiescence period based reclamation實現(xiàn)。這個實現(xiàn)可以用于有一個寫線程和多個讀線程共用若干個數(shù)據(jù)的場景。

實現(xiàn)

該方法本質(zhì)上把數(shù)據(jù)同步分解為基本的內(nèi)存單元讀寫。使用方式上可描述為：

讀線程：

tmp_ptr = _ptr
use
update() // 標(biāo)識自己不再使用任何共享數(shù)據(jù)

寫線程：

old_ptr = _ptr
tmp_ptr = copy(_ptr)
change(tmp_ptr)
_ptr = tmp_ptr
gc()
defer_free(old_ptr)

以下具體描述讀寫線程的實現(xiàn)。

寫線程

寫線程負(fù)責(zé)標(biāo)識內(nèi)存需要被釋放，以及檢查何時可以真正釋放內(nèi)存。其維護(hù)了一個釋放內(nèi)存隊列：

void *_pending[8]
    uint64_t _head, _tail

    void defer_free(void *p) {
        _head ++
        _pending[PENDING_POS(_head)] = p
    }

    gc() {
        for (_tail -> find_free_pos())
            free(_pending[_tail])
    }

find_free_pos找到一個可釋放內(nèi)存位置，在[_tail, find_free_pos())這個區(qū)間內(nèi)所有內(nèi)存是可以安全被釋放的。

隊列位置_head/_tail一直增大，PENDING_POS就是對這個位置取模，限定在隊列大小范圍內(nèi)也是可行的，無論哪種方式，_head從邏輯上說一直>=_tail，但在實際中可能小于_tail，所以實現(xiàn)時不使用大小判定，而是：

gc() {
        pos = find_free_pos()
        while (_tail != pos) {
            free(_pending[PENDING_POS(_tail)])
            _tail ++
        }
    }

讀線程

讀線程不再使用共享內(nèi)存時，就標(biāo)識自己：

update() {
        static __thread int tid
        _tmark[tid] = _head
    }

讀線程的狀態(tài)會影響寫線程的回收邏輯，其狀態(tài)分為：

初始
活躍，會調(diào)用到update
暫停，其他地方同步，或被掛起
退出

讀線程處于活躍狀態(tài)時，它會不斷地更新自己可釋放內(nèi)存位置(_tmark[tid])。寫線程檢查所有讀線程的_tmark[tid]，[_tail, min(_tmark[]))是所有讀線程都不再使用的內(nèi)存區(qū)間，可以被安全釋放。

find_free_pos() {
        min = MAX_INTEGER
        pos = 0
        for (tid = 0; tid < max_threads; ++tid) {
            tpos = _tmark[tid]
            offset = tpos - tail
            if (offset < min) {
                min = offset
                pos = tpos
            }
        }
        return pos
    }

當(dāng)讀線程暫停時，其_tmark[tid]可能會在很長一段時間里得不到更新，此時會阻礙寫線程釋放內(nèi)存。所以需要方法來標(biāo)識讀線程是否進(jìn)入暫停狀態(tài)。通過設(shè)置一個上次釋放內(nèi)存位置_tfreeds[tid]，標(biāo)識每個線程當(dāng)前內(nèi)存釋放到的位置。如果一個線程處于暫停狀態(tài)了，那么在一定時間后，_tfreeds[tid] == _tmark[tid]。在查找可釋放位置時，就需要忽略暫停狀態(tài)的讀線程：

find_free_pos() {
        min = MAX_INTEGER
        pos = _head
        for (tid = 0; tid < max_threads; ++tid) {
            tpos = _tmark[tid]
            if (tpos == _tfreeds[tid]) continue
            offset = tpos - tail
            if (offset < min) {
                min = offset
                pos = tpos
            }
        }
        for (tid = 0; tid < max_threads; ++tid) {
            if (_tfreeds[tid] != _tmark[tid]) 
                _tfreeds[tid] = pos
        }
        return pos
    }

但是當(dāng)所有線程都處于暫停狀態(tài)時，寫線程可能還在工作，上面的實現(xiàn)就會返回_head，此時寫線程依然可以正常釋放內(nèi)存。

小結(jié)，該方法原理可用下圖表示：

線程動態(tài)增加/減少

如果讀線程可能中途退出，中途動態(tài)增加，那么_tmark[]就需要被復(fù)用，此時線程tid的分配調(diào)整為動態(tài)的即可：

class ThreadIdPool {
    public:
        // 動態(tài)獲取一個線程tid，某線程每次調(diào)用該接口返回相同的值
        int get()
        // 線程退出時回收該tid
        void put(int id)
    }

ThreadIdPool的實現(xiàn)無非就是利用TLS，以及在線程退出時得到通知以回收tid。那么對于讀線程的update實現(xiàn)變?yōu)椋?/p>

update() {
        tid = _idPool->get()
        _tmark[tid] = _head
    }

當(dāng)某個線程退出時，_tmark[tid]和_tfreeds[tid]不需要做任何處理，當(dāng)新創(chuàng)建的線程復(fù)用了該tid時，可以立即復(fù)用_tmark[tid]和_tfreeds[tid]，此時這2個值必然是相等的。

以上，就是整個方法的實現(xiàn)。

線程可讀可寫

以上方法適用場景還是不夠通用。在nbds項目（實現(xiàn)了一些無鎖數(shù)據(jù)結(jié)構(gòu)的toy project）中有一份雖然簡單但也有啟發(fā)的實現(xiàn)(rcu.c)。該實現(xiàn)支持任意線程defer_free，所有線程update。update除了聲明不再使用任何共享內(nèi)存外，還可能回收內(nèi)存。任意線程都可能維護(hù)一些待釋放的內(nèi)存，任意一塊內(nèi)存可能被任意其他線程使用。那么它是如何內(nèi)存回收的？

本文描述的方法是所有讀線程自己聲明自己，然后由寫線程主動來檢查。不同于此方法， nbds的實現(xiàn)，基于一種通知擴(kuò)散的方式。該方式以這樣一種方式工作：

當(dāng)某個線程嘗試內(nèi)存回收時，它需要知道所有其他線程的空閑位置（相當(dāng)于_tmark[tid]），它通知下一個線程我需要釋放的范圍。當(dāng)下一個線程update時（離開臨界區(qū)），它會將上個線程的通知繼續(xù)告訴下一個線程，直到最后這個通知回到發(fā)起線程。那么對于發(fā)起線程而言，這個釋放請求在所有線程中走了一遍，得到了大家的認(rèn)可，可以安全釋放。每個線程都以這樣的方式工作。

void rcu_defer_free (void *x) {
        ...
        rcu_[next_thread_id][tid_] = rcu_last_posted_[tid_][tid_] = pending_[tid_]->head;
        ...
    }

    void rcu_update (void) {
        ...
        for (i = 0; i < num_threads_; ++i) {
            ...     
            uint64_t x = rcu_[tid_][i]; // 其它線程發(fā)給自己的通知
            rcu_[next_thread_id][i] = rcu_last_posted_[tid_][i] = x; // 擴(kuò)散出去
            ...
        }
        ...
        while (q->tail != rcu_[tid_][tid_]) {
            free
        }     
        ...
    }

這個實現(xiàn)相對簡單，不支持線程暫停，以及線程動態(tài)增加和減少。

posted @ 2015-04-19 19:10 Kevin Lynx 閱讀(11452) | 評論 (3) | 編輯收藏

記一次tcmalloc分配內(nèi)存引起的coredump

現(xiàn)象

線上的服務(wù)出現(xiàn)coredump，堆棧為：

#0  0x000000000045d145 in GetStackTrace(void**, int, int) ()
#1  0x000000000045ec22 in tcmalloc::PageHeap::GrowHeap(unsigned long) ()
#2  0x000000000045eeb3 in tcmalloc::PageHeap::New(unsigned long) ()
#3  0x0000000000459ee8 in tcmalloc::CentralFreeList::Populate() ()
#4  0x000000000045a088 in tcmalloc::CentralFreeList::FetchFromSpansSafe() ()
#5  0x000000000045a10a in tcmalloc::CentralFreeList::RemoveRange(void**, void**, int) ()
#6  0x000000000045c282 in tcmalloc::ThreadCache::FetchFromCentralCache(unsigned long, unsigned long) ()
#7  0x0000000000470766 in tc_malloc ()
#8  0x00007f75532cd4c2 in __conhash_get_rbnode (node=0x22c86870, hash=30)
        at build/release64/cm_sub/conhash/conhash_inter.c:88
#9  0x00007f75532cd76e in __conhash_add_replicas (conhash=0x24fbc7e0, iden=<value optimized out>)
        at build/release64/cm_sub/conhash/conhash_inter.c:45
#10 0x00007f75532cd1fa in conhash_add_node (conhash=0x24fbc7e0, iden=0) at build/release64/cm_sub/conhash/conhash.c:72
#11 0x00007f75532c651b in cm_sub::TopoCluster::initLBPolicyInfo (this=0x2593a400)
        at build/release64/cm_sub/topo_cluster.cpp:114
#12 0x00007f75532cad73 in cm_sub::TopoClusterManager::processClusterMapTable (this=0xa219e0, ref=0x267ea8c0)
        at build/release64/cm_sub/topo_cluster_manager.cpp:396
#13 0x00007f75532c5a93 in cm_sub::SubRespMsgProcess::reinitCluster (this=0x9c2f00, msg=0x4e738ed0)
        at build/release64/cm_sub/sub_resp_msg_process.cpp:157
...

查看了應(yīng)用層相關(guān)數(shù)據(jù)結(jié)構(gòu)，基本數(shù)據(jù)都是沒有問題的。所以最初懷疑是tcmalloc內(nèi)部維護(hù)了錯誤的內(nèi)存，在分配內(nèi)存時出錯，這個堆棧只是問題的表象。幾天后，線上的另一個服務(wù)，基于同樣的庫，也core了，堆棧還是一樣的。

最初定位問題都是從最近更新的東西入手，包括依賴的server環(huán)境，但都沒有明顯的問題，所以最后只能從core的直接原因入手。

分析GetStackTrace

確認(rèn)core的詳細(xì)位置：

# core在該指令
0x000000000045d145 <_Z13GetStackTracePPvii+21>: mov    0x8(%rax),%r9

(gdb) p/x $rip              # core 的指令位置
$9 = 0x45d145
(gdb) p/x $rax              
$10 = 0x4e73aa58
(gdb) x/1a $rax+0x8         # rax + 8 = 0x4e73aa60
0x4e73aa60:     0x0

該指令嘗試從[0x4e73aa60]處讀取內(nèi)容，然后出錯，這個內(nèi)存單元不可讀。但是具體這個指令在代碼中是什么意思，需要將這個指令對應(yīng)到代碼中。獲取tcmalloc的源碼，發(fā)現(xiàn)GetStackTrace根據(jù)編譯選項有很多實現(xiàn)，所以這里選擇最可能的實現(xiàn)，然后對比匯編以確認(rèn)代碼是否匹配。最初選擇的是stacktrace_x86-64-inl.h，后來發(fā)現(xiàn)完全不匹配，又選擇了stacktrace_x86-inl.h。這個實現(xiàn)版本里也有對64位平臺的支持。

stacktrace_x86-inl.h里使用了一些宏來生成函數(shù)名和參數(shù)，精簡后代碼大概為：

int GET_STACK_TRACE_OR_FRAMES {
      void **sp;
      unsigned long rbp;
      __asm__ volatile ("mov %%rbp, %0" : "=r" (rbp));
      sp = (void **) rbp;

      int n = 0;
      while (sp && n < max_depth) {
        if (*(sp+1) == reinterpret_cast<void *>(0)) {
          break;
        }
        void **next_sp = NextStackFrame<!IS_STACK_FRAMES, IS_WITH_CONTEXT>(sp, ucp);
        if (skip_count > 0) {
          skip_count--;
        } else {
          result[n] = *(sp+1);
          n++;
        }
        sp = next_sp;
      }
      return n;
    }

NextStackFrame是一個模板函數(shù)，包含一大堆代碼，精簡后非常簡單：

template<bool STRICT_UNWINDING, bool WITH_CONTEXT>
    static void **NextStackFrame(void **old_sp, const void *uc) {
      void **new_sp = (void **) *old_sp;
      if (STRICT_UNWINDING) {
        if (new_sp <= old_sp) return NULL;
        if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL;
      } else {
        if (new_sp == old_sp) return NULL;
        if ((new_sp > old_sp)
            && ((uintptr_t)new_sp - (uintptr_t)old_sp > 1000000)) return NULL;
      }
      if ((uintptr_t)new_sp & (sizeof(void *) - 1)) return NULL;

      return new_sp;
    }

上面這個代碼到匯編的對比過程還是花了些時間，其中匯編中出現(xiàn)的一些常量可以大大縮短對比時間，例如上面出現(xiàn)了100000，匯編中就有：

0x000000000045d176 <_Z13GetStackTracePPvii+70>: cmp    $0x186a0,%rbx  # 100000=0x186a0

注意NextStackFrame中的 if (STRICT_UNWINDING)使用的是模板參數(shù)，這導(dǎo)致生成的代碼中根本沒有else部分，也就沒有1000000這個常量

在對比代碼的過程中，可以知道關(guān)鍵的幾個寄存器、內(nèi)存位置對應(yīng)到代碼中的變量，從而可以還原core時的現(xiàn)場環(huán)境。分析過程中不一定要從第一行匯編讀，可以從較明顯的位置讀，從而還原整個代碼，函數(shù)返回指令、跳轉(zhuǎn)指令、比較指令、讀內(nèi)存指令、參數(shù)寄存器等都是比較明顯對應(yīng)的地方。

另外注意GetStackTrace在RecordGrowth中調(diào)用，傳入了3個參數(shù)：

GetStackTrace(t->stack, kMaxStackDepth-1, 3); // kMaxStackDepth = 31

以下是我分析的簡單注解：

(gdb) disassemble
Dump of assembler code for function _Z13GetStackTracePPvii:
0x000000000045d130 <_Z13GetStackTracePPvii+0>:  push   %rbp
0x000000000045d131 <_Z13GetStackTracePPvii+1>:  mov    %rsp,%rbp
0x000000000045d134 <_Z13GetStackTracePPvii+4>:  push   %rbx
0x000000000045d135 <_Z13GetStackTracePPvii+5>:  mov    %rbp,%rax
0x000000000045d138 <_Z13GetStackTracePPvii+8>:  xor    %r8d,%r8d
0x000000000045d13b <_Z13GetStackTracePPvii+11>: test   %rax,%rax
0x000000000045d13e <_Z13GetStackTracePPvii+14>: je     0x45d167 <_Z13GetStackTracePPvii+55>
0x000000000045d140 <_Z13GetStackTracePPvii+16>: cmp    %esi,%r8d        # while ( .. max_depth > n ?
0x000000000045d143 <_Z13GetStackTracePPvii+19>: jge    0x45d167 <_Z13GetStackTracePPvii+55>
0x000000000045d145 <_Z13GetStackTracePPvii+21>: mov    0x8(%rax),%r9    # 關(guān)鍵位置：*(sp+1) -> r9, rax 對應(yīng) sp變量
0x000000000045d149 <_Z13GetStackTracePPvii+25>: test   %r9,%r9          # *(sp+1) == 0 ?
0x000000000045d14c <_Z13GetStackTracePPvii+28>: je     0x45d167 <_Z13GetStackTracePPvii+55>
0x000000000045d14e <_Z13GetStackTracePPvii+30>: mov    (%rax),%rcx      # new_sp = *old_sp，這里已經(jīng)是NextStackFrame的代碼
0x000000000045d151 <_Z13GetStackTracePPvii+33>: cmp    %rcx,%rax        # new_sp <= old_sp ? 
0x000000000045d154 <_Z13GetStackTracePPvii+36>: jb     0x45d170 <_Z13GetStackTracePPvii+64>  # new_sp > old_sp 跳轉(zhuǎn)
0x000000000045d156 <_Z13GetStackTracePPvii+38>: xor    %ecx,%ecx
0x000000000045d158 <_Z13GetStackTracePPvii+40>: test   %edx,%edx        # skip_count > 0 ?
0x000000000045d15a <_Z13GetStackTracePPvii+42>: jle    0x45d186 <_Z13GetStackTracePPvii+86>
0x000000000045d15c <_Z13GetStackTracePPvii+44>: sub    $0x1,%edx        # skip_count--
0x000000000045d15f <_Z13GetStackTracePPvii+47>: mov    %rcx,%rax        
0x000000000045d162 <_Z13GetStackTracePPvii+50>: test   %rax,%rax        # while (sp ?
0x000000000045d165 <_Z13GetStackTracePPvii+53>: jne    0x45d140 <_Z13GetStackTracePPvii+16>
0x000000000045d167 <_Z13GetStackTracePPvii+55>: pop    %rbx
0x000000000045d168 <_Z13GetStackTracePPvii+56>: leaveq 
0x000000000045d169 <_Z13GetStackTracePPvii+57>: mov    %r8d,%eax        # r8 存儲了返回值，r8=n
0x000000000045d16c <_Z13GetStackTracePPvii+60>: retq                    # return n
0x000000000045d16d <_Z13GetStackTracePPvii+61>: nopl   (%rax)
0x000000000045d170 <_Z13GetStackTracePPvii+64>: mov    %rcx,%rbx        
0x000000000045d173 <_Z13GetStackTracePPvii+67>: sub    %rax,%rbx        # offset = new_sp - old_sp
0x000000000045d176 <_Z13GetStackTracePPvii+70>: cmp    $0x186a0,%rbx    # offset > 100000 ?
0x000000000045d17d <_Z13GetStackTracePPvii+77>: ja     0x45d156 <_Z13GetStackTracePPvii+38> # return NULL
0x000000000045d17f <_Z13GetStackTracePPvii+79>: test   $0x7,%cl         # new_sp & (sizeof(void*) - 1)
0x000000000045d182 <_Z13GetStackTracePPvii+82>: je     0x45d158 <_Z13GetStackTracePPvii+40>
0x000000000045d184 <_Z13GetStackTracePPvii+84>: jmp    0x45d156 <_Z13GetStackTracePPvii+38>
0x000000000045d186 <_Z13GetStackTracePPvii+86>: movslq %r8d,%rax        # rax = n
0x000000000045d189 <_Z13GetStackTracePPvii+89>: add    $0x1,%r8d        # n++
0x000000000045d18d <_Z13GetStackTracePPvii+93>: mov    %r9,(%rdi,%rax,8)# 關(guān)鍵位置：result[n] = *(sp+1)
0x000000000045d191 <_Z13GetStackTracePPvii+97>: jmp    0x45d15f <_Z13GetStackTracePPvii+47>

分析過程比較耗時，同時還可以分析下GetStackTrace函數(shù)的實現(xiàn)原理，其實就是利用RBP寄存器不斷回溯，從而得到整個調(diào)用堆棧各個函數(shù)的地址（嚴(yán)格來說是返回地址）。簡單示意下函數(shù)調(diào)用中RBP的情況：

   ...
saved registers          # i.e push rbx
local variabes           # i.e sub 0x10, rsp
return address           # call xxx
last func RBP            # push rbp; mov rsp, rbp
saved registers
local variables 
return address
last func RBP
...                      # rsp

總之，一般情況下，任何一個函數(shù)中，RBP寄存器指向了當(dāng)前函數(shù)的棧基址，該棧基址中又存儲了調(diào)用者的棧基址，同時該棧基址前面還存儲了調(diào)用者的返回地址。所以，GetStackTrace的實現(xiàn)，簡單來說大概就是：

sp = rbp  // 取得當(dāng)前函數(shù)GetStackTrace的棧基址
    while (n < max_depth) {
        new_sp = *sp
        result[n] = *(new_sp+1)
        n++
    }

以上，最終就知道了以下關(guān)鍵信息：

r8 對應(yīng)變量 n，表示當(dāng)前取到第幾個棧幀了
rax 對應(yīng)變量 sp，代碼core在 *(sp+1)
rdi 對應(yīng)變量 result，用于存儲取得的各個地址

然后可以看看現(xiàn)場是怎樣的：

(gdb) x/10a $rdi
0x1ffc9b98:     0x45a088 <_ZN8tcmalloc15CentralFreeList18FetchFromSpansSafeEv+40>       0x45a10a <_ZN8tcmalloc15CentralFreeList11RemoveRangeEPPvS2_i+106>
0x1ffc9ba8:     0x45c282 <_ZN8tcmalloc11ThreadCache21FetchFromCentralCacheEmm+114>      0x470766 <tc_malloc+790>
0x1ffc9bb8:     0x7f75532cd4c2 <__conhash_get_rbnode+34>        0x0
0x1ffc9bc8:     0x0     0x0
0x1ffc9bd8:     0x0     0x0

(gdb) p/x $r8
$3 = 0x5

(gdb) p/x $rax
$4 = 0x4e73aa58

小結(jié)：

GetStackTrace在取調(diào)用__conhash_get_rbnode的函數(shù)時出錯，取得了5個函數(shù)地址。當(dāng)前使用的RBP為0x4e73aa58。

錯誤的RBP

RBP也是從堆棧中取出來的，既然這個地址有問題，首先想到的就是有代碼局部變量/數(shù)組寫越界。例如sprintf的使用。而且，一般寫越界破壞堆棧，都可能是把調(diào)用者的堆棧破壞了，例如：

char s[32];
memcpy(s, p, 1024);

因為寫入都是從低地址往高地址寫，而調(diào)用者的堆棧在高地址。當(dāng)然，也會遇到寫壞調(diào)用者的調(diào)用者的堆棧，也就是跨棧幀越界寫，例如以前遇到的：

len = vsnprintf(buf, sizeof(buf), fmt, wtf-long-string);
buf[len] = 0;

__conhash_get_rbnode的RBP是在tcmalloc的堆棧中取的：

(gdb) f 7
#7  0x0000000000470766 in tc_malloc ()
(gdb) x/10a $rsp
0x4e738b80:     0x4e73aa58      0x22c86870
0x4e738b90:     0x4e738bd0      0x85
0x4e738ba0:     0x4e73aa58      0x7f75532cd4c2 <__conhash_get_rbnode+34>   # 0x4e73aa58

所以這里就會懷疑是tcmalloc這個函數(shù)里有把堆棧破壞，這個時候就是讀代碼，看看有沒有疑似危險的地方，未果。這里就陷入了僵局，懷疑又遇到了跨棧幀破壞的情況，這個時候就只能__conhash_get_rbnode調(diào)用棧中周圍的函數(shù)翻翻，例如調(diào)用__conhash_get_rbnode的函數(shù)__conhash_add_replicas中恰好有字符串操作：

void __conhash_add_replicas(conhash_t *conhash, int32_t iden)
    {
        node_t* node = __conhash_create_node(iden, conhash->replica);
        ...
        char buf[buf_len]; // buf_len = 64
        ...
        snprintf(buf, buf_len, VIRT_NODE_HASH_FMT, node->iden, i);
        uint32_t hash = conhash->cb_hashfunc(buf);
        if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
        {
            util_rbtree_node_t* rbnode = __conhash_get_rbnode(node, hash);
            ...

這段代碼最終發(fā)現(xiàn)是沒有問題的，這里又耗費了不少時間。后來發(fā)現(xiàn)若干個函數(shù)里的RBP都有點奇怪，這個調(diào)用棧比較正常的范圍是：0x4e738c90

(gdb) f 8
#8  0x00007f75532cd4c2 in __conhash_get_rbnode (node=0x22c86870, hash=30)
(gdb) p/x $rbp
$6 = 0x4e73aa58     # 這個還不算特別可疑
(gdb) f 9
#9  0x00007f75532cd76e in __conhash_add_replicas (conhash=0x24fbc7e0, iden=<value optimized out>)
(gdb) p/x $rbp
$7 = 0x4e738c60     # 這個也不算特別可疑
(gdb) f 10
#10 0x00007f75532cd1fa in conhash_add_node (conhash=0x24fbc7e0, iden=0) at build/release64/cm_sub/conhash/conhash.c:72
(gdb) p/x $rbp      # 可疑
$8 = 0x0
(gdb) f 11
#11 0x00007f75532c651b in cm_sub::TopoCluster::initLBPolicyInfo (this=0x2593a400)
(gdb) p/x $rbp      # 可疑
$9 = 0x2598fef0

為什么很多函數(shù)中RBP都看起來不正常？ 想了想真要是代碼里把堆棧破壞了，這錯誤得發(fā)生得多巧妙？

錯誤RBP的來源

然后轉(zhuǎn)機(jī)來了，腦海中突然閃出-fomit-frame-pointer。編譯器生成的代碼中是可以不需要棧基址指針的，也就是RBP寄存器不作為棧基址寄存器。大部分函數(shù)或者說開啟了frame-pointer的函數(shù)，其函數(shù)頭都會有以下指令：

push   %rbp
mov    %rsp,%rbp
...

表示保存調(diào)用者的棧基址到棧中，以及設(shè)置自己的棧基址。看下__conhash系列函數(shù)；

Dump of assembler code for function __conhash_get_rbnode:
0x00007f75532cd4a0 <__conhash_get_rbnode+0>:    mov    %rbx,-0x18(%rsp)
0x00007f75532cd4a5 <__conhash_get_rbnode+5>:    mov    %rbp,-0x10(%rsp)
...

這個庫是單獨編譯的，沒有顯示指定-fno-omit-frame-pointer，查閱gcc手冊，o2優(yōu)化是開啟了omit-frame-pinter 的。

在沒有RBP的情況下，tcmalloc的GetStackTrace嘗試讀RBP取獲取調(diào)用返回地址，自然是有問題的。但是，如果整個調(diào)用棧中的函數(shù)，要么有RBP，要么沒有RBP，那么GetStackTrace取出的結(jié)果最多就是跳過一些棧幀，不會出錯。 除非，這中間的某個函數(shù)把RBP寄存器另作他用（編譯器省出這個寄存器肯定是要另作他用的）。所以這里繼續(xù)追查這個錯誤地址0x4e73aa58的來源。

來源已經(jīng)比較明顯，肯定是__conhash_get_rbnode中設(shè)置的，因為這個函數(shù)的RBP是在被調(diào)用者tcmalloc中保存的。

Dump of assembler code for function __conhash_get_rbnode:
0x00007f75532cd4a0 <__conhash_get_rbnode+0>:    mov    %rbx,-0x18(%rsp)
0x00007f75532cd4a5 <__conhash_get_rbnode+5>:    mov    %rbp,-0x10(%rsp)
0x00007f75532cd4aa <__conhash_get_rbnode+10>:   mov    %esi,%ebp                    # 改寫了RBP
0x00007f75532cd4ac <__conhash_get_rbnode+12>:   mov    %r12,-0x8(%rsp)
0x00007f75532cd4b1 <__conhash_get_rbnode+17>:   sub    $0x18,%rsp
0x00007f75532cd4b5 <__conhash_get_rbnode+21>:   mov    %rdi,%r12
0x00007f75532cd4b8 <__conhash_get_rbnode+24>:   mov    $0x30,%edi
0x00007f75532cd4bd <__conhash_get_rbnode+29>:   callq  0x7f75532b98c8 <malloc@plt>  # 調(diào)用tcmalloc，匯編到這里即可

這里打印RSI寄存器的值可能會被誤導(dǎo)，因為任何時候打印寄存器的值可能都是錯的，除非它有被顯示保存。不過這里可以看出RSI的值來源于參數(shù)(RSI對應(yīng)第二個參數(shù))：

void __conhash_add_replicas(conhash_t *conhash, int32_t iden)
    {
        node_t* node = __conhash_create_node(iden, conhash->replica);
        ...
        char buf[buf_len]; // buf_len = 64
        ...
        snprintf(buf, buf_len, VIRT_NODE_HASH_FMT, node->iden, i);
        uint32_t hash = conhash->cb_hashfunc(buf); // hash值由一個字符串哈希函數(shù)計算
        if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
        {
            util_rbtree_node_t* rbnode = __conhash_get_rbnode(node, hash);  // hash值
            ...

追到__conhash_add_replicas：

0x00007f75532cd764 <__conhash_add_replicas+164>:        mov    %ebx,%esi    # 來源于rbx
0x00007f75532cd766 <__conhash_add_replicas+166>:        mov    %r15,%rdi
0x00007f75532cd769 <__conhash_add_replicas+169>:        callq  0x7f75532b9e48 <__conhash_get_rbnode@plt>

(gdb) p/x $rbx
$11 = 0x4e73aa58
(gdb) p/x hash
$12 = 0x4e73aa58      # 0x4e73aa58

找到了0x4e73aa58的來源。這個地址值竟然是一個字符串哈希算法算出來的！這里還可以看看這個字符串的內(nèi)容：

(gdb) x/1s $rsp
0x4e738bd0:      "conhash-00000-00133"

這個碉堡的哈希函數(shù)是conhash_hash_def。

coredump的條件

以上，既然只要某個庫omit-frame-pointer，那tcmalloc就可能出錯，為什么發(fā)生的頻率并不高呢？這個可以回到GetStackTrace尤其是NextStackFrame的實現(xiàn)，其中包含了幾個合法RBP的判定：

if (new_sp <= old_sp) return NULL;  // 上一個棧幀的RBP肯定比當(dāng)前的大
        if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL; // 指針值范圍還必須在100000內(nèi)
        ...
    if ((uintptr_t)new_sp & (sizeof(void *) - 1)) return NULL; // 由于本身保存的是指針，所以還必須是sizeof(void*)的整數(shù)倍，對齊

有了以上條件，才使得這個core幾率變得很低。

總結(jié)

最后，如果你很熟悉tcmalloc，整個問題估計就被秒解了：tcmalloc INSTALL

附

另外附上另一個有意思的東西。

在分析__conhash_add_replicas時，其內(nèi)定義了一個64字節(jié)的字符數(shù)組，查看其堆棧：

(gdb) x/20a $rsp
0x4e738bd0:     0x2d687361686e6f63      0x30302d3030303030          # 這些是字符串conhash-00000-00133
0x4e738be0:     0x333331        0x0
0x4e738bf0:     0x0     0x7f75532cd69e <__conhash_create_node+78>
0x4e738c00:     0x24fbc7e0      0x4e738c60
0x4e738c10:     0x24fbc7e0      0x7f75532cd6e3 <__conhash_add_replicas+35>
0x4e738c20:     0x0     0x24fbc7e8
0x4e738c30:     0x4e738c20      0x24fbc7e0
0x4e738c40:     0x22324360      0x246632c0
0x4e738c50:     0x0     0x0
0x4e738c60:     0x0     0x7f75532cd1fa <conhash_add_node+74>

最開始我覺得buf占64字節(jié)，也就是整個[0x4e738bd0, 0x4e738c10)內(nèi)存，但是這塊內(nèi)存里居然有函數(shù)地址，這一度使我懷疑這里有問題。后來醒悟這些地址是定義buf前調(diào)用__conhash_create_node產(chǎn)生的，調(diào)用過程中寫到堆棧里，調(diào)用完后棧指針改變，但并不需要清空棧中的內(nèi)容。

posted @ 2015-04-06 18:33 Kevin Lynx 閱讀(8086) | 評論 (2) | 編輯收藏

基于內(nèi)存查看STL常用容器內(nèi)容

有時候在線上使用gdb調(diào)試程序core問題時，可能沒有符號文件，拿到的僅是一個內(nèi)存地址，如果這個指向的是一個STL對象，那么如何查看這個對象的內(nèi)容呢？

只需要知道STL各個容器的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，就可以查看其內(nèi)容。本文描述了SGI STL實現(xiàn)中常用容器的數(shù)據(jù)結(jié)構(gòu)，以及如何在gdb中查看其內(nèi)容。

string

string，即basic_string bits/basic_string.h：

mutable _Alloc_hider  _M_dataplus;
    ... 
      const _CharT*
      c_str() const
      { return _M_data(); }
    ...    
      _CharT*
      _M_data() const 
      { return  _M_dataplus._M_p; }

    ...
      struct _Alloc_hider : _Alloc
      {
    _Alloc_hider(_CharT* __dat, const _Alloc& __a)
    : _Alloc(__a), _M_p(__dat) { }

    _CharT* _M_p; // The actual data.
      };
   
      size_type
      length() const
      { return _M_rep()->_M_length; }

      _Rep*
      _M_rep() const
      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

      ...
       struct _Rep_base
      {
    size_type       _M_length;
    size_type       _M_capacity;
    _Atomic_word        _M_refcount;
      };

      struct _Rep : _Rep_base

即，string內(nèi)有一個指針，指向?qū)嶋H的字符串位置，這個位置前面有一個_Rep結(jié)構(gòu)，其內(nèi)保存了字符串的長度、可用內(nèi)存以及引用計數(shù)。當(dāng)我們拿到一個string對象的地址時，可以通過以下代碼獲取相關(guān)值：

void ds_str_i(void *p) {
        char **raw = (char**)p;
        char *s = *raw;
        size_t len = *(size_t*)(s - sizeof(size_t) * 3);
        printf("str: %s (%zd)\n", s, len);
    }

    size_t ds_str() {
        std::string s = "hello";
        ds_str_i(&s);
        return s.size();
    }

在gdb中拿到一個string的地址時，可以以下打印出該字符串及長度：

(gdb) x/1a p
0x7fffffffe3a0: 0x606028
(gdb) p (char*)0x606028
$2 = 0x606028 "hello"
(gdb) x/1dg 0x606028-24
0x606010:       5

vector

眾所周知vector實現(xiàn)就是一塊連續(xù)的內(nèi)存，bits/stl_vector.h。

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>

    ...
    template<typename _Tp, typename _Alloc>
    struct _Vector_base
    {
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

      struct _Vector_impl
      : public _Tp_alloc_type
      {
    _Tp*           _M_start;
    _Tp*           _M_finish;
    _Tp*           _M_end_of_storage;
    _Vector_impl(_Tp_alloc_type const& __a)
    : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
    { }
      };


      _Vector_impl _M_impl;

可以看出sizeof(vector<xxx>)=24，其內(nèi)也就是3個指針，_M_start指向首元素地址，_M_finish指向最后一個節(jié)點+1，_M_end_of_storage是可用空間最后的位置。

iterator
      end()
      { return iterator (this->_M_impl._M_finish); }
      const_iterator
      ...
      begin() const
      { return const_iterator (this->_M_impl._M_start); }
      ...
      size_type
      capacity() const
      { return size_type(const_iterator(this->_M_impl._M_end_of_storage)
             - begin()); }

可以通過代碼從一個vector對象地址輸出其信息：

template <typename T>
    void ds_vec_i(void *p) {
        T *start = *(T**)p;
        T *finish = *(T**)((char*)p + sizeof(void*));
        T *end_storage = *(T**)((char*)p + 2 * sizeof(void*));
        printf("vec size: %ld, avaiable size: %ld\n", finish - start, end_storage - start); 
    }

    size_t ds_vec() {
        std::vector<int> vec;
        vec.push_back(0x11);
        vec.push_back(0x22);
        vec.push_back(0x33);
        ds_vec_i<int>(&vec);
        return vec.size();
    }

使用gdb輸出一個vector中的內(nèi)容：

(gdb) p p
$3 = (void *) 0x7fffffffe380
(gdb) x/1a p
0x7fffffffe380: 0x606080
(gdb) x/3xw 0x606080
0x606080:       0x00000011      0x00000022      0x00000033

list

眾所周知list被實現(xiàn)為一個鏈表。準(zhǔn)確來說是一個雙向鏈表。list本身是一個特殊節(jié)點，其代表end，其指向的下一個元素才是list真正的第一個節(jié)點：

bits/stl_list.h

bool
      empty() const
      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }

      const_iterator
      begin() const
      { return const_iterator(this->_M_impl._M_node._M_next); }

      iterator
      end()
      { return iterator(&this->_M_impl._M_node); }

      ...

    struct _List_node_base
    {
        _List_node_base* _M_next;   ///< Self-explanatory
        _List_node_base* _M_prev;   ///< Self-explanatory
        ...
    };
         
    template<typename _Tp>
    struct _List_node : public _List_node_base
    {
      _Tp _M_data;                ///< User's data.
    };
      
    template<typename _Tp, typename _Alloc>
    class _List_base
    {
        ...
      struct _List_impl
      : public _Node_alloc_type
      {
    _List_node_base _M_node;
        ...
      };

      _List_impl _M_impl;

          
    template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class list : protected _List_base<_Tp, _Alloc>

所以sizeof(list<xx>)=16，兩個指針。每一個真正的節(jié)點首先是包含兩個指針，然后是元素內(nèi)容(_List_node)。

通過代碼輸出list的內(nèi)容：

#define NEXT(ptr, T) do { \
        void *n = *(char**)ptr; \
        T val = *(T*)((char**)ptr + 2); \
        printf("list item %p val: 0x%x\n", ptr, val); \
        ptr = n; \
    } while (0)

    template <typename T>
    void ds_list_i(void *p) {
        void *ptr = *(char**)p;

        NEXT(ptr, T);
        NEXT(ptr, T);
        NEXT(ptr, T);
    }

    size_t ds_list() {
        std::list<int> lst;
        lst.push_back(0x11);
        lst.push_back(0x22);
        lst.push_back(0x33);
        ds_list_i<int>(&lst);
        return lst.size();
    }

在gdb中可以以下方式遍歷該list：

(gdb) p p
$4 = (void *) 0x7fffffffe390
(gdb) x/1a p
0x7fffffffe390: 0x606080
(gdb) x/1xw 0x606080+16         # 元素1 
0x606090:       0x00000011
(gdb) x/1a 0x606080
0x606080:       0x6060a0
(gdb) x/1xw 0x6060a0+16         # 元素2
0x6060b0:       0x00000022

map

map使用的是紅黑樹實現(xiàn)，實際使用的是stl_tree.h實現(xiàn)：

bits/stl_map.h

typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
               key_compare, _Pair_alloc_type> _Rep_type;
    ...
     _Rep_type _M_t;
    ... 

      iterator
      begin()
      { return _M_t.begin(); }

bits/stl_tree.h

struct _Rb_tree_node_base
      {
        typedef _Rb_tree_node_base* _Base_ptr;
        typedef const _Rb_tree_node_base* _Const_Base_ptr;

        _Rb_tree_color  _M_color;
        _Base_ptr       _M_parent;
        _Base_ptr       _M_left;
        _Base_ptr       _M_right;
        
        ...
      };

    template<typename _Val>
    struct _Rb_tree_node : public _Rb_tree_node_base
    {
      typedef _Rb_tree_node<_Val>* _Link_type;
      _Val _M_value_field;
    };


    template<typename _Key_compare,
           bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
        struct _Rb_tree_impl : public _Node_allocator
        {
      _Key_compare      _M_key_compare;
      _Rb_tree_node_base    _M_header;
      size_type         _M_node_count; // Keeps track of size of tree.
      ...
        }
    
    _Rb_tree_impl<_Compare> _M_impl;
    ...

      iterator
      begin()
      {
    return iterator(static_cast<_Link_type>
            (this->_M_impl._M_header._M_left));
      }

所以可以看出，大部分時候(取決于_M_key_compare) sizeof(map<xx>)=48，主要的元素是：

_Rb_tree_color  _M_color; // 節(jié)點顏色
        _Base_ptr       _M_parent; // 父節(jié)點
        _Base_ptr       _M_left; // 左節(jié)點
        _Base_ptr       _M_right; // 右節(jié)點
        _Val            _M_value_field // 同list中節(jié)點技巧一致，后面是實際的元素

同list中的實現(xiàn)一致，map本身作為一個節(jié)點，其不是一個存儲數(shù)據(jù)的節(jié)點，

_Rb_tree::end

iterator
      end()
      { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }

由于節(jié)點值在_Rb_tree_node_base后，所以任意時候拿到節(jié)點就可以偏移這個結(jié)構(gòu)體拿到節(jié)點值，節(jié)點的值是一個pair，包含了key和value。

在gdb中打印以下map的內(nèi)容：

size_t ds_map() {
        std::map<std::string, int> imap;
        imap["abc"] = 0xbbb;
        return imap.size();
    }

(gdb) p/x &imap
$7 = 0x7fffffffe370
(gdb) x/1a (char*)&imap+24       # _M_left 真正的節(jié)點
0x7fffffffe388: 0x606040          
(gdb) x/1xw 0x606040+32+8        # 偏移32字節(jié)是節(jié)點值的地址，再偏移8則是value的地址
0x606068:       0x00000bbb
(gdb) p *(char**)(0x606040+32)   # 偏移32字節(jié)是string的地址
$8 = 0x606028 "abc"

或者很多時候沒有必要這么裝逼+蛋疼：

(gdb) p *(char**)(imap._M_t._M_impl._M_header._M_left+1)
$9 = 0x606028 "abc"
(gdb) x/1xw (char*)(imap._M_t._M_impl._M_header._M_left+1)+8
0x606068:       0x00000bbb

完

posted @ 2014-12-03 22:08 Kevin Lynx 閱讀(3836) | 評論 (2) | 編輯收藏

linux動態(tài)庫的種種要點

linux下使用動態(tài)庫，基本用起來還是很容易。但如果我們的程序中大量使用動態(tài)庫來實現(xiàn)各種框架/插件，那么就會遇到一些坑，掌握這些坑才有利于程序更穩(wěn)健地運(yùn)行。

本篇先談?wù)剟討B(tài)庫符號方面的問題。

測試代碼可以在github上找到

符號查找

一個應(yīng)用程序test會鏈接一個動態(tài)庫libdy.so，如果一個符號，例如函數(shù)callfn定義于libdy.so中，test要使用該函數(shù)，簡單地聲明即可：

// dy.cpp libdy.so
void callfn() {
    ...
}

// main.cpp test
extern void callfn();

callfn();

在鏈接test的時候，鏈接器會統(tǒng)一進(jìn)行檢查。

同樣，在libdy.so中有相同的規(guī)則，它可以使用一個外部的符號，在它被鏈接/載入進(jìn)一個可執(zhí)行程序時才會進(jìn)行符號存在與否的檢查。這個符號甚至可以定義在test中，形成一種雙向依賴，或定義在其他動態(tài)庫中：

// dy.cpp libdy.so
extern void mfunc();

mfunc();

// main.cpp test
void mfunc() {
    ...
}

在生成libdy.so時mfunc可以找不到，此時mfunc為未定義：

$ nm libdy.so | grep mfun
U _Z5mfuncv

但在libdy.so被鏈接進(jìn)test時則會進(jìn)行檢查，試著把mfunc函數(shù)的定義去掉，就會得到一個鏈接錯誤：

./libdy.so: undefined reference to `mfunc()'

同樣，如果我們動態(tài)載入libdy.so，此時當(dāng)然可以鏈接通過，但是在載入時同樣得到找不到符號的錯誤：

#ifdef DY_LOAD
    void *dp = dlopen("./libdy.so", RTLD_LAZY);
    typedef void (*callfn)();
    callfn f = (callfn) dlsym(dp, "callfn");
    f();
    dlclose(dp);
#else
    callfn();
#endif

得到錯誤：

./test: symbol lookup error: ./libdy.so: undefined symbol: _Z5mfuncv

結(jié)論：基于以上，我們知道，如果一個動態(tài)庫依賴了一些外部符號，這些外部符號可以位于其他動態(tài)庫甚至應(yīng)用程序中。我們可以再鏈接這個動態(tài)庫的時候就把依賴的其他庫也鏈接上，或者推遲到鏈接應(yīng)用程序時再鏈接。而動態(tài)加載的庫，則要保證在加載該庫時，進(jìn)程中加載的其他動態(tài)庫里已經(jīng)存在該符號。

例如，通過LD_PRELOAD環(huán)境變量可以讓一個進(jìn)程先加載指定的動態(tài)庫，上面那個動態(tài)加載啟動失敗的例子，可以通過預(yù)先加載包含mfunc符號的動態(tài)庫解決：

$ LD_PRELOAD=libmfun.so ./test
...

但是如果這個符號存在于可執(zhí)行程序中則不行：

$ nm test | grep mfunc
0000000000400a00 T _Z5mfuncv
$ nm test | grep mfunc
0000000000400a00 T _Z5mfuncv
$ ./test
...
./test: symbol lookup error: ./libdy.so: undefined symbol: _Z5mfuncv

符號覆蓋

前面主要講的是符號缺少的情況，如果同一個符號存在多分，則更能引發(fā)問題。這里談到的符號都是全局符號，一個進(jìn)程中某個全局符號始終是全局唯一的。為了保證這一點，在鏈接或動態(tài)載入動態(tài)庫時，就會出現(xiàn)忽略重復(fù)符號的情況。

這里就不提同一個鏈接單位（如可執(zhí)行程序、動態(tài)庫）里符號重復(fù)的問題了

函數(shù)

當(dāng)動態(tài)庫和libdy.so可執(zhí)行程序test中包含同名的函數(shù)時會怎樣？根據(jù)是否動態(tài)加載情況還有所不同。

當(dāng)直接鏈接動態(tài)庫時，libdy.so和test都會鏈接包含func函數(shù)的fun.o，為了區(qū)分，我把func按照條件編譯得到不同的版本：

// fun.cpp
#ifdef V2
extern "C" void func() {
    printf("func v2\n");
}
#else
extern "C" void func() {
    printf("func v1\n");
}
#endif

// Makefile
test: libdy obj.o mainfn
    g++ -g -Wall -c fun.cpp -o fun.o # 編譯為fun.o
    g++ -g -Wall -c main.cpp #-DDY_LOAD
    g++ -g -Wall -o test main.o obj.o fun.o -ldl mfun.o -ldy -L.

libdy: obj
    g++ -Wall -fPIC -c fun.cpp -DV2 -o fun-dy.o  # 定義V2宏，編譯為fun-dy.o
    g++ -Wall -fPIC -shared -o libdy.so dy.cpp -g obj.o fun-dy.o

這樣，test中的func就會輸出func v1；libdy.so中的func就會輸出func v2。test和libdy.o確實都有func符號：

$ nm libdy.so | grep func
0000000000000a60 T func

$nm test | grep func
0000000000400a80 T func

在test和libdy.so中都會調(diào)用func函數(shù)：

// main.cpp test
int main(int argc, char **argv) {
    func();
    ...
    callfn(); // 調(diào)用libdy.so中的函數(shù)
    ...
}

// dy.cpp libdy.so
extern "C" void callfn() {
    ... 
    printf("callfn\n");
    func();
    ...
}

運(yùn)行后發(fā)現(xiàn)，都調(diào)用的是同一個func：

$ ./test
...
func v1
...
callfn
func v1

結(jié)論，直接鏈接動態(tài)庫時，整個程序運(yùn)行的時候符號會發(fā)生覆蓋，只有一個符號被使用。在實踐中，如果程序和鏈接的動態(tài)庫都依賴了一個靜態(tài)庫，而后他們鏈接的這個靜態(tài)庫版本不同，則很有可能因為符號發(fā)生了覆蓋而導(dǎo)致問題。(靜態(tài)庫同普通的.o性質(zhì)一樣，參考淺析靜態(tài)庫鏈接原理)

更復(fù)雜的情況中，多個動態(tài)庫和程序都有相同的符號，情況也是一樣，會發(fā)生符號覆蓋。如果程序里沒有這個符號，而多個動態(tài)庫里有相同的符號，也會覆蓋。

但是對于動態(tài)載入的情況則不同，同樣的libdy.so我們在test中不鏈接，而是動態(tài)載入：

int main(int argc, char **argv) {
    func();
#ifdef DY_LOAD
    void *dp = dlopen("./libdy.so", RTLD_LAZY);
    typedef void (*callfn)();
    callfn f = (callfn) dlsym(dp, "callfn");
    f();
    func();
    dlclose(dp);
#else
    callfn();
#endif
    return 0;
}

運(yùn)行得到：

$ ./test
func v1
...
callfn
func v2
func v1

都正確地調(diào)用到各自鏈接的func。

結(jié)論，實踐中，動態(tài)載入的動態(tài)庫一般會作為插件使用，那么其同程序鏈接不同版本的靜態(tài)庫（相同符號不同實現(xiàn)），是沒有問題的。

變量

變量本質(zhì)上也是符號(symbol)，但其處理規(guī)則和函數(shù)還有點不一樣(是不是有點想吐槽了)。

// object.h
class Object {
public:
    Object() {
#ifdef DF
        s = malloc(32);
        printf("s addr %p\n", s);
#endif
        printf("ctor %p\n", this);
    }

    ~Object() {
        printf("dtor %p\n", this);
#ifdef DF
        printf("s addr %p\n", s);
        free(s);
#endif
    }

    void *s;
};

extern Object g_obj;

我們的程序test和動態(tài)庫libdy.so都會鏈接object.o。首先測試test鏈接libdy.so，test和libdy.so中都會有g_obj這個符號：

// B g_obj 表示g_obj位于BSS段，未初始化段

$ nm test | grep g_obj
0000000000400a14 t _GLOBAL__I_g_obj
00000000006012c8 B g_obj
$ nm libdy.so | grep g_obj
000000000000097c t _GLOBAL__I_g_obj
0000000000200f30 B g_obj

運(yùn)行：

$ ./test
ctor 0x6012c8
ctor 0x6012c8
...
dtor 0x6012c8
dtor 0x6012c8

g_obj被構(gòu)造了兩次，但地址一樣。全局變量只有一個實例，似乎在情理之中。

動態(tài)載入libdy.so，變量地址還是相同的：

$ ./test
ctor 0x6012a8
...
ctor 0x6012a8
...
dtor 0x6012a8
dtor 0x6012a8

結(jié)論，不同于函數(shù)，全局變量符號重復(fù)時，不論動態(tài)庫是動態(tài)載入還是直接鏈接，變量始終只有一個。

但詭異的情況是，對象被構(gòu)造和析構(gòu)了兩次。構(gòu)造兩次倒無所謂，浪費點空間，但是析構(gòu)兩次就有問題。因為析構(gòu)時都操作的是同一個對象，那么如果這個對象內(nèi)部有分配的內(nèi)存，那就會對這塊內(nèi)存造成double free，因為指針相同。打開DF宏實驗下：

$ ./test
s addr 0x20de010
ctor 0x6012b8
s addr 0x20de040
ctor 0x6012b8
...
dtor 0x6012b8
s addr 0x20de040
dtor 0x6012b8
s addr 0x20de040

因為析構(gòu)的兩次都是同一個對象，所以其成員s指向的內(nèi)存被釋放了兩次，從而產(chǎn)生了double free，讓程序coredump了。

總結(jié)，全局變量符號重復(fù)時，始終會只使用一個，并且會被初始化/釋放兩次，是一種較危險的情況，應(yīng)當(dāng)避免在使用動態(tài)庫的過程中使用全局變量。

完

posted @ 2014-11-04 00:55 Kevin Lynx 閱讀(7961) | 評論 (1) | 編輯收藏

圖解zookeeper FastLeader選舉算法

zookeeper配置為集群模式時，在啟動或異常情況時會選舉出一個實例作為Leader。其默認(rèn)選舉算法為FastLeaderElection。

不知道zookeeper的可以考慮這樣一個問題：某個服務(wù)可以配置為多個實例共同構(gòu)成一個集群對外提供服務(wù)。其每一個實例本地都存有冗余數(shù)據(jù)，每一個實例都可以直接對外提供讀寫服務(wù)。在這個集群中為了保證數(shù)據(jù)的一致性，需要有一個Leader來協(xié)調(diào)一些事務(wù)。那么問題來了：如何確定哪一個實例是Leader呢？

問題的難點在于：

沒有一個仲裁者來選定Leader
每一個實例本地可能已經(jīng)存在數(shù)據(jù)，不確定哪個實例上的數(shù)據(jù)是最新的

分布式選舉算法正是用來解決這個問題的。

本文基于zookeeper 3.4.6 的源碼進(jìn)行分析。FastLeaderElection算法的源碼全部位于FastLeaderElection.java文件中，其對外接口為FastLeaderElection.lookForLeader，該接口是一個同步接口，直到選舉結(jié)束才會返回。同樣由于網(wǎng)上已有類似文章，所以我就從圖示的角度來闡述。閱讀一些其他文章有利于獲得初步印象：

深入淺出Zookeeper之五 Leader選舉，代碼導(dǎo)讀
zookeeper3.3.3源碼分析(二)FastLeader選舉算法，文字描述較細(xì)

主要流程

閱讀代碼和以上推薦文章可以把整個流程梳理清楚。實現(xiàn)上，包括了一個消息處理主循環(huán)，也是選舉的主要邏輯，以及一個消息發(fā)送隊列處理線程和消息解碼線程。主要流程可概括為下圖：

推薦對照著推薦的文章及代碼理解，不贅述。

我們從感性上來理解這個算法。

每一個節(jié)點，相當(dāng)于一個選民，他們都有自己的推薦人，最開始他們都推薦自己。誰更適合成為Leader有一個簡單的規(guī)則，例如sid夠大（配置）、持有的數(shù)據(jù)夠新(zxid夠大)。每個選民都告訴其他選民自己目前的推薦人是誰，類似于出去搞宣傳拉攏其他選民。每一個選民發(fā)現(xiàn)有比自己更適合的人時就轉(zhuǎn)而推薦這個更適合的人。最后，大部分人意見一致時，就可以結(jié)束選舉。

就這么簡單。總體上有一種不斷演化逼近結(jié)果的感覺。

當(dāng)然，會有些特殊情況的處理。例如總共3個選民，1和2已經(jīng)確定3是Leader，但3還不知情，此時就走入LEADING/FOLLOWING的分支，選民3只是接收結(jié)果。

代碼中不是所有邏輯都在這個大流程中完成的。在接收消息線程中，還可能單獨地回應(yīng)某個節(jié)點(WorkerReceiver.run)：

從這里可以看出，當(dāng)某個節(jié)點已經(jīng)確定選舉結(jié)果不再處于LOOKING狀態(tài)時，其收到LOOKING消息時都會直接回應(yīng)選舉的最終結(jié)果。結(jié)合上面那個比方，相當(dāng)于某次選舉結(jié)束了，這個時候來了選民4又發(fā)起一次新的選舉，那么其他選民就直接告訴它當(dāng)前的Leader情況。相當(dāng)于，在這個集群主從已經(jīng)就緒的情況下，又開啟了一個實例，這個實例就會直接使用當(dāng)前的選舉結(jié)果。

狀態(tài)轉(zhuǎn)換

每個節(jié)點上有一些關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)：

當(dāng)前推薦人，初始推薦自己，每次收到其他更好的推薦人時就更新
其他人的投票集合，用于確定何時選舉結(jié)束

每次推薦人更新時就會進(jìn)行廣播，正是這個不斷地廣播驅(qū)動整個算法趨向于結(jié)果。假設(shè)有3個節(jié)點A/B/C，其都還沒有數(shù)據(jù)，按照sid關(guān)系為C>B>A，那么按照規(guī)則，C更可能成為Leader，其各個節(jié)點的狀態(tài)轉(zhuǎn)換為：

圖中，v(A)表示當(dāng)前推薦人為A；r[]表示收到的投票集合。

可以看看當(dāng)其他節(jié)點已經(jīng)確定投票結(jié)果時，即不再是LOOKING時的狀態(tài)：

代碼中有一個特殊的投票集合outofelection，我理解為選舉已結(jié)束的那些投票，這些投票僅用于表征選舉結(jié)果。

當(dāng)一個新啟動的節(jié)點加入集群時，它對集群內(nèi)其他節(jié)點發(fā)出投票請求，而其他節(jié)點已不處于LOOKING狀態(tài)，此時其他節(jié)點回應(yīng)選舉結(jié)果，該節(jié)點收集這些結(jié)果到outofelection中，最終在收到合法LEADER消息且這些選票也構(gòu)成選舉結(jié)束條件時，該節(jié)點就結(jié)束自己的選舉行為。注意到代碼中會logicalclock = n.electionEpoch;更新選舉輪數(shù)

完

posted @ 2014-10-19 15:58 Kevin Lynx 閱讀(4488) | 評論 (0) | 編輯收藏

圖解分布式一致性協(xié)議Paxos

Paxos協(xié)議/算法是分布式系統(tǒng)中比較重要的協(xié)議，它有多重要呢？

<分布式系統(tǒng)的事務(wù)處理>：

Google Chubby的作者M(jìn)ike Burrows說過這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

<大規(guī)模分布式存儲系統(tǒng)>：

理解了這兩個分布式協(xié)議之后(Paxos/2PC)，學(xué)習(xí)其他分布式協(xié)議會變得相當(dāng)容易。

學(xué)習(xí)Paxos算法有兩部分：a) 算法的原理/證明；b) 算法的理解/運(yùn)作。

理解這個算法的運(yùn)作過程其實基本就可以用于工程實踐。而且理解這個過程相對來說也容易得多。

網(wǎng)上我覺得講Paxos講的好的屬于這篇：paxos圖解及Paxos算法詳解，我這里就結(jié)合wiki上的實例進(jìn)一步闡述。一些paxos基礎(chǔ)通過這里提到的兩篇文章，以及wiki上的內(nèi)容基本可以理解。

算法內(nèi)容

Paxos在原作者的《Paxos Made Simple》中內(nèi)容是比較精簡的：

Phase 1

(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.

Phase 2

(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

借用paxos圖解文中的流程圖可概括為：

實例及詳解

Paxos中有三類角色Proposer、Acceptor及Learner，主要交互過程在Proposer和Acceptor之間。

Proposer與Acceptor之間的交互主要有4類消息通信，如下圖：

這4類消息對應(yīng)于paxos算法的兩個階段4個過程：

phase 1
- a) proposer向網(wǎng)絡(luò)內(nèi)超過半數(shù)的acceptor發(fā)送prepare消息
- b) acceptor正常情況下回復(fù)promise消息
phase 2
- a) 在有足夠多acceptor回復(fù)promise消息時，proposer發(fā)送accept消息
- b) 正常情況下acceptor回復(fù)accepted消息

因為在整個過程中可能有其他proposer針對同一件事情發(fā)出以上請求，所以在每個過程中都會有些特殊情況處理，這也是為了達(dá)成一致性所做的事情。如果在整個過程中沒有其他proposer來競爭，那么這個操作的結(jié)果就是確定無異議的。但是如果有其他proposer的話，情況就不一樣了。

以paxos中文wiki上的例子為例。簡單來說該例子以若干個議員提議稅收，確定最終通過的法案稅收比例。

以下圖中基本只畫出proposer與一個acceptor的交互。時間標(biāo)志T2總是在T1后面。propose number簡稱N。

情況之一如下圖：

A3在T1發(fā)出accepted給A1，然后在T2收到A5的prepare，在T3的時候A1才通知A5最終結(jié)果(稅率10%)。這里會有兩種情況：

A5發(fā)來的N5小于A1發(fā)出去的N1，那么A3直接拒絕(reject)A5
A5發(fā)來的N5大于A1發(fā)出去的N1，那么A3回復(fù)promise，但帶上A1的(N1, 10%)

這里可以與paxos流程圖對應(yīng)起來，更好理解。acceptor會記錄(MaxN, AcceptN, AcceptV)。

A5在收到promise后，后續(xù)的流程可以順利進(jìn)行。但是發(fā)出accept時，因為收到了(AcceptN, AcceptV)，所以會取最大的AcceptN對應(yīng)的AcceptV，例子中也就是A1的10%作為AcceptV。如果在收到promise時沒有發(fā)現(xiàn)有其他已記錄的AcceptV，則其值可以由自己決定。

針對以上A1和A5沖突的情況，最終A1和A5都會廣播接受的值為10%。

其實4個過程中對于acceptor而言，在回復(fù)promise和accepted時由于都可能因為其他proposer的介入而導(dǎo)致特殊處理。所以基本上看在這兩個時間點收到其他proposer的請求時就可以了解整個算法了。例如在回復(fù)promise時則可能因為proposer發(fā)來的N不夠大而reject：

如果在發(fā)accepted消息時，對其他更大N的proposer發(fā)出過promise，那么也會reject該proposer發(fā)出的accept，如圖：

這個對應(yīng)于Phase 2 b)：

it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

總結(jié)

Leslie Lamport沒有用數(shù)學(xué)描述Paxos，但是他用英文闡述得很清晰。將Paxos的兩個Phase的內(nèi)容理解清楚，整個算法過程還是不復(fù)雜的。

至于Paxos中一直提到的一個全局唯一且遞增的proposer number，其如何實現(xiàn)，引用如下：

如何產(chǎn)生唯一的編號呢？在《Paxos made simple》中提到的是讓所有的Proposer都從不相交的數(shù)據(jù)集合中進(jìn)行選擇，例如系統(tǒng)有5個Proposer，則可為每一個Proposer分配一個標(biāo)識j(0~4)，則每一個proposer每次提出決議的編號可以為5*i + j(i可以用來表示提出議案的次數(shù))

參考文檔

paxos圖解, http://coderxy.com/archives/121
Paxos算法詳解, http://coderxy.com/archives/136
Paxos算法 wiki, http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95#.E5.AE.9E.E4.BE.8B

posted @ 2014-10-15 22:45 Kevin Lynx 閱讀(10344) | 評論 (6) | 編輯收藏

淘寶分布式配置管理服務(wù)Diamond

在一個分布式環(huán)境中，同類型的服務(wù)往往會部署很多實例。這些實例使用了一些配置，為了更好地維護(hù)這些配置就產(chǎn)生了配置管理服務(wù)。通過這個服務(wù)可以輕松地管理這些應(yīng)用服務(wù)的配置問題。應(yīng)用場景可概括為：

zookeeper的一種應(yīng)用就是分布式配置管理(基于ZooKeeper的配置信息存儲方案的設(shè)計與實現(xiàn))。百度也有類似的實現(xiàn)：disconf。

Diamond則是淘寶開源的一種分布式配置管理服務(wù)的實現(xiàn)。Diamond本質(zhì)上是一個Java寫的Web應(yīng)用，其對外提供接口都是基于HTTP協(xié)議的，在閱讀代碼時可以從實現(xiàn)各個接口的controller入手。

分布式配置管理

分布式配置管理的本質(zhì)基本上就是一種推送-訂閱模式的運(yùn)用。配置的應(yīng)用方是訂閱者，配置管理服務(wù)則是推送方。概括為下圖：

其中，客戶端包括管理人員publish數(shù)據(jù)到配置管理服務(wù)，可以理解為添加/更新數(shù)據(jù)；配置管理服務(wù)notify數(shù)據(jù)到訂閱者，可以理解為推送。

配置管理服務(wù)往往會封裝一個客戶端庫，應(yīng)用方則是基于該庫與配置管理服務(wù)進(jìn)行交互。在實際實現(xiàn)時，客戶端庫可能是主動拉取(pull)數(shù)據(jù)，但對于應(yīng)用方而言，一般是一種事件通知方式。

Diamond中的數(shù)據(jù)是簡單的key-value結(jié)構(gòu)。應(yīng)用方訂閱數(shù)據(jù)則是基于key來訂閱，未訂閱的數(shù)據(jù)當(dāng)然不會被推送。數(shù)據(jù)從類型上又劃分為聚合和非聚合。因為數(shù)據(jù)推送者可能很多，在整個分布式環(huán)境中，可能有多個推送者在推送相同key的數(shù)據(jù)，這些數(shù)據(jù)如果是聚合的，那么所有這些推送者推送的數(shù)據(jù)會被合并在一起；反之如果是非聚合的，則會出現(xiàn)覆蓋。

數(shù)據(jù)的來源可能是人工通過管理端錄入，也可能是其他服務(wù)通過配置管理服務(wù)的推送接口自動錄入。

架構(gòu)及實現(xiàn)

Diamond服務(wù)是一個集群，是一個去除了單點的協(xié)作集群。如圖：

圖中可分為以下部分講解：

服務(wù)之間同步

Diamond服務(wù)集群每一個實例都可以對外完整地提供服務(wù)，那么意味著每個實例上都有整個集群維護(hù)的數(shù)據(jù)。Diamond有兩種方式保證這一點：

任何一個實例都有其他實例的地址；任何一個實例上的數(shù)據(jù)變更時，都會將改變的數(shù)據(jù)同步到mysql上，然后通知其他所有實例從mysql上進(jìn)行一次數(shù)據(jù)拉取(DumpService::dump)，這個過程只拉取改變了的數(shù)據(jù)
任何一個實例啟動后都會以較長的時間間隔（幾小時），從mysql進(jìn)行一次全量的數(shù)據(jù)拉取(DumpAllProcessor)

實現(xiàn)上為了一致性，通知其他實例實際上也包含自己。以服務(wù)器收到添加聚合數(shù)據(jù)為例，處理過程大致為：

DatumController::addDatum // /datum.do?method=addDatum
    PersistService::addAggrConfigInfo 
    MergeDatumService::addMergeTask // 添加一個MergeDataTask，異步處理

MergeTaskProcessor::process
    PersistService::insertOrUpdate
        EventDispatcher.fireEvent(new ConfigDataChangeEvent // 派發(fā)一個ConfigDataChangeEvent事件

NotifyService::onEvent // 接收事件并處理
    TaskManager::addTask(..., new NotifyTask // 由此，當(dāng)數(shù)據(jù)發(fā)生變動，則最終創(chuàng)建了一個NoticyTask

// NotifyTask同樣異步處理
NotifyTaskProcessor::process
    foreach server in serverList // 包含自己
        notifyToDump // 調(diào)用 /notify.do?method=notifyConfigInfo 從mysql更新變動的數(shù)據(jù)

雖然Diamond去除了單點問題，不過問題都下降到了mysql上。但由于其作為配置管理的定位，其數(shù)據(jù)量就mysql的應(yīng)用而言算小的了，所以可以一定程度上保證整個服務(wù)的可用性。

數(shù)據(jù)一致性

由于Diamond服務(wù)器沒有master，任何一個實例都可以讀寫數(shù)據(jù)，那么針對同一個key的數(shù)據(jù)則可能面臨沖突。這里應(yīng)該是通過mysql來保證數(shù)據(jù)的一致性。每一次客戶端請求寫數(shù)據(jù)時，Diamond都將寫請求投遞給mysql，然后通知集群內(nèi)所有Diamond實例（包括自己）從mysql拉取數(shù)據(jù)。當(dāng)然，拉取數(shù)據(jù)則可能不是每一次寫入都能拉出來，也就是最終一致性。

Diamond中沒有把數(shù)據(jù)放入內(nèi)存，但會放到本地文件。對于客戶端的讀操作而言，則是直接返回本地文件里的數(shù)據(jù)。

服務(wù)實例列表

Diamond服務(wù)實例列表是一份靜態(tài)數(shù)據(jù)，直接將每個實例的地址存放在一個web server上。無論是Diamond服務(wù)還是客戶端都從該web server上取出實例列表。

對于客戶端而言，當(dāng)其取出了該列表后，則是隨機(jī)選擇一個節(jié)點(ServerListManager.java)，以后的請求都會發(fā)往該節(jié)點。

數(shù)據(jù)同步

客戶端庫中以固定時間間隔從服務(wù)器拉取數(shù)據(jù)(ClientWorker::ClientWorker，ClientWorker::checkServerConfigInfo)。只有應(yīng)用方關(guān)心的數(shù)據(jù)才可能被拉取。另外，為了數(shù)據(jù)推送的及時，Diamond還使用了一種long polling的技術(shù)，其實也是為了突破HTTP協(xié)議的局限性。如果整個服務(wù)是基于TCP的自定義協(xié)議，客戶端與服務(wù)器保持長連接則沒有這些問題。

數(shù)據(jù)的變更

Diamond中很多操作都會檢查數(shù)據(jù)是否發(fā)生了變化。標(biāo)識數(shù)據(jù)變化則是基于數(shù)據(jù)對應(yīng)的MD5值來實現(xiàn)的。

容災(zāi)

在整個Diamond系統(tǒng)中，幾個角色為了提高容災(zāi)性，都有自己的緩存，概括為下圖：

每一個角色出問題時，都可以盡量保證客戶端對應(yīng)用層提供服務(wù)。

posted @ 2014-10-12 12:57 Kevin Lynx 閱讀(2717) | 評論 (4) | 編輯收藏

僅列出標(biāo)題

導(dǎo)航

統(tǒng)計

公告

常用鏈接

留言簿(52)

隨筆分類

隨筆檔案

收藏夾

C++

關(guān)注的開源項目

其他關(guān)注

網(wǎng)絡(luò)編程

我的項目

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

名字服務(wù)

What’s JCM

架構(gòu)

使用

JCM實現(xiàn)

數(shù)據(jù)同步

健康檢查

jcm.subscriber通信

壓力測試

總結(jié)

主要問題

解決方案

ABA問題

總結(jié)

原理

Hazard Pointer的管理

附錄

Lock Free & Wait Free

ABA問題

RCU

實現(xiàn)

寫線程

讀線程

線程動態(tài)增加/減少

線程可讀可寫

現(xiàn)象

分析GetStackTrace

錯誤的RBP

錯誤RBP的來源

coredump的條件

總結(jié)

附

string

vector

list

map

符號查找

符號覆蓋

函數(shù)

變量

主要流程

狀態(tài)轉(zhuǎn)換

算法內(nèi)容

實例及詳解

總結(jié)

參考文檔

分布式配置管理

架構(gòu)及實現(xiàn)

服務(wù)之間同步

數(shù)據(jù)一致性

服務(wù)實例列表

數(shù)據(jù)同步

數(shù)據(jù)的變更

容災(zāi)

參考文檔