涔嬪墠鍦ㄥ叕鍙擱噷緇存姢浜?jiǎn)涓涓悕瀛楁湇鍔★紝榪欎釜鍚嶅瓧鏈嶅姟鏃ュ父綆＄悊浜?jiǎn)杩?000鍙版満鍣紝鏈?000涓乏鍙崇殑瀹㈡埛绔繛鎺ヤ笂鏉ヨ幏鍙栨満鍣ㄤ俊鎭紝鐢變簬鍏跺熀鏈槸涓涓崟鐐規(guī)湇鍔★紝鎵浠ユ煇浜涙ā鍧楁帴榪戠摱棰堛傚悗鏉ュ掓槸鏈夐噸鏋勮鍒掞紝璇︾粏璁捐鍋氫簡(jiǎn)錛屼唬鐮侀兘鍐欎簡(jiǎn)涓閮ㄥ垎錛岀粨鏋滅敱浜庢煇浜涘師鍥犻噸鏋勫氨琚粓姝簡(jiǎn)銆?/p>
JCM鏄垜涓氫綑鏃墮棿鐢↗ava閲嶅啓鐨勪竴涓増鏈紝鍔熻兘涓婄洰鍓嶅彧瀹炵幇浜?jiǎn)鍩杭媭鍔熻兘銆傜敱浜庡畠鏄釜瀹屽叏鍒嗗竷寮忕殑鏋舵瀯錛屾墍浠ョ悊璁轟笂鍙互妯悜鎵╁睍錛屽ぇ澶у寮虹郴緇熺殑鏈嶅姟鑳藉姏銆?/p>
鍚嶅瓧鏈嶅姟
鍦ㄥ垎甯冨紡緋葷粺涓紝鏌愪釜鏈嶅姟涓轟簡(jiǎn)鎻愬崌鏁翠綋鏈嶅姟鑳藉姏錛岄氬父閮ㄧ講浜?jiǎn)寰堝瀹炰緥銆傝繖閲屾垜鎶婅繖浜涙彁渚涚浉鍚屾湇鍔＄殑瀹炰緥緇熺О涓洪泦緹?cluster)錛屾瘡涓疄渚嬬О涓轟竴涓妭鐐?Node)銆備竴涓簲鐢ㄥ彲鑳戒細(xì)浣跨敤寰堝cluster錛屾瘡嬈¤闂竴涓猚luster鏃訛紝灝遍氳繃鍚嶅瓧鏈嶅姟鑾峰彇璇luster涓嬩竴涓彲鐢ㄧ殑node銆傞偅涔堬紝鍚嶅瓧鏈嶅姟鑷沖皯闇瑕佸寘鍚殑鍔熻兘錛?/p>
- 鏍規(guī)嵁cluster鍚嶅瓧鑾峰彇鍙敤鐨刵ode
- 瀵圭鐞嗙殑鎵鏈塩luster涓嬬殑鎵鏈塶ode榪涜鍋ュ悍搴︾殑媯(gè)嫻嬶紝浠ヤ繚璇佸緇堣繑鍥炲彲鐢ㄧ殑node
鏈変簺鍚嶅瓧鏈嶅姟浠呭node綆＄悊錛屼笉鍙備笌搴旂敤涓巒ode闂寸殑閫氫俊錛岃屾湁浜涘垯鍙兘浣滀負(fù)搴旂敤涓巒ode闂寸殑閫氫俊杞彂鍣ㄣ傝櫧鐒跺悕瀛楁湇鍔″姛鑳界畝鍗曪紝浣嗘槸瑕佸仛涓涓垎甯冨紡鐨勫悕瀛楁湇鍔¤繕鏄瘮杈冨鏉傜殑錛屽洜涓烘暟鎹竴鏃﹀垎甯冨紡浜?jiǎn)锛尀兗?xì)瀛樺湪鍚屾銆佷竴鑷存ч棶棰樼殑鑰冭檻絳夈?/p>
What鈥檚 JCM
JCM鍥寸粫鍓嶉潰璇寸殑鍚嶅瓧鏈嶅姟鍩虹鍔熻兘瀹炵幇銆傚寘鍚殑鍔熻兘錛?/p>
- 綆＄悊cluster鍒皀ode鐨勬槧灝?/li>
- 鍒嗗竷寮忔灦鏋勶紝鍙按騫蟲(chóng)墿灞曚互瀹炵幇綆＄悊10,000涓猲ode鐨勮兘鍔涳紝瓚充互綆＄悊涓鑸叕鍙哥殑鍚庡彴鏈嶅姟闆嗙兢
- 瀵規(guī)瘡涓猲ode榪涜鍋ュ悍媯(gè)鏌ワ紝鍋ュ悍媯(gè)鏌ュ彲鍩轟簬HTTP鍗忚灞傜殑媯(gè)嫻嬫垨TCP榪炴帴媯(gè)嫻?/li>
- 鎸佷箙鍖朿luster/node鏁版嵁錛岄氳繃zookeeper淇濊瘉鏁版嵁涓鑷存?/li>
- 鎻愪緵JSON HTTP API綆＄悊cluster/node鏁版嵁錛屽悗緇彲鎻愪緵Web綆＄悊緋葷粺
- 浠ュ簱鐨勫艦寮忔彁渚涗笌server鐨勪氦浜掞紝搴撴湰韜彁渚涘悇縐嶈礋杞藉潎琛＄瓥鐣ワ紝淇濊瘉瀵逛竴涓猚luster涓媙ode鐨勮闂揪鍒拌礋杞藉潎琛?/li>
欏圭洰鍦板潃git jcm
JCM涓昏鍖呭惈涓ら儴鍒嗭細(xì)
- jcm.server錛孞CM鍚嶅瓧鏈嶅姟錛岄渶瑕佽繛鎺ookeeper浠ユ寔涔呭寲鏁版嵁
- jcm.subscriber錛屽鎴風(fēng)搴擄紝璐熻矗涓巎cm.server浜や簰錛屾彁渚涘寘瑁呬簡(jiǎn)璐熻澆鍧囪 鐨凙PI緇欏簲鐢ㄤ嬌鐢?/li>
鏋舵瀯
鍩轟簬JCM鐨勭郴緇熸暣浣撴灦鏋勫涓嬶細(xì)
cluster鏈韓鏄笉闇瑕佷緷璧朖CM鐨勶紝瑕侀氳繃JCM浣跨敤榪欎簺cluster錛屽彧闇瑕侀氳繃JCM HTTP API娉ㄥ唽榪欎簺cluster鍒癹cm.server涓娿傝閫氳繃jcm.server浣跨敤榪欎簺cluster錛屽垯鏄氳繃jcm.subscriber鏉ュ畬鎴愩?/p>
浣跨敤
鍙弬鑰?a >git READMe.md
闇瑕乯re1.7+
- 鍚姩zookeeper
- 涓嬭澆jcm.server git jcm.server-0.1.0.jar
- 鍦?code>jcm.server-0.1.0.jar鐩綍涓嬪緩绔?code>config/application.properties鏂囦歡榪涜閰嶇疆錛屽弬鑰?a >config/application.properties
-
鍚姩jcm.server
java -jar jcm.server-0.1.0.jar -
娉ㄥ唽闇瑕佺鐞嗙殑闆嗙兢錛屽弬鑰僣luster鎻忚堪錛?a >doc/cluster_sample.json錛岄氳繃HTTP API娉ㄥ唽錛?/p>
curl -i -X POST http://10.181.97.106:8080/c -H "Content-Type:application/json" --data-binary @./doc/cluster_sample.json
閮ㄧ講濂戒簡(jiǎn)jcm.server錛屽茍娉ㄥ唽浜?jiǎn)cluster鍚庯紝灝卞彲浠ラ氳繃jcm.subscriber浣跨敤錛?/p>
// 浼犲叆闇瑕佷嬌鐢ㄧ殑闆嗙兢鍚峢ello9/hello錛屼互鍙?qiáng)浼犲叆jcm.server鍦板潃錛屽彲浠ュ涓細(xì)127.0.0.1:8080
Subscriber subscriber = new Subscriber( Arrays.asList("127.0.0.1:8080"), Arrays.asList("hello9", "hello"));
// 浣跨敤杞璐熻澆鍧囪 絳栫暐
RRAllocator rr = new RRAllocator();
subscriber.addListener(rr);
subscriber.startup();
for (int i = 0; i < 2; ++i) {
// rr.alloc 鏍規(guī)嵁cluster鍚嶅瓧鑾峰彇鍙敤鐨刵ode
System.out.println(rr.alloc("hello9", ProtoType.HTTP));
}
subscriber.shutdown();JCM瀹炵幇
JCM鐩墠鐨勫疄鐜版瘮杈冪畝鍗曪紝鍙傝冩ā鍧楀浘錛?/p>
- model錛屽嵆cluster/node榪欎簺鏁版嵁緇撴瀯鐨勬弿榪幫紝鍚屾椂琚玧cm.server鍜宩cm.subscriber渚濊禆
- storage錛屾寔涔呭寲鏁版嵁鍒皕ookeeper錛屽悓鏃跺寘鍚玧cm.server瀹炰緥涔嬮棿鐨勬暟鎹悓姝?/li>
- health check錛屽仴搴鋒鏌ユā鍧楋紝瀵瑰悇涓猲ode榪涜鍋ュ悍媯(gè)鏌?/li>
浠ヤ笂妯″潡閮戒笉渚濊禆Spring錛屽熀浜庝互涓婃ā鍧楀張鏈夛細(xì)
- http api錛屼嬌鐢╯pring-mvc錛屽寘瑁呬簡(jiǎn)涓浜汮SON HTTP API
- Application錛屽熀浜巗pring-boot錛屽皢鍚勪釜鍩虹妯″潡緇勮璧鋒潵錛屾彁渚泂tandalone鐨勬ā寮忓惎鍔紝涓嶇敤閮ㄧ講鍒皌omcat涔嬬被鐨剆ervlet瀹瑰櫒涓?/li>
jcm.subscriber鐨勫疄鐜版洿綆鍗曪紝涓昏鏄礋璐ｄ笌jcm.server榪涜閫氫俊錛屼互鏇存柊鑷繁褰撳墠鐨刴odel灞傛暟鎹紝鍚屾椂鎻愪緵鍚勭璐熻澆鍧囪 絳栫暐鎺ュ彛錛?/p>
- subscriber錛屼笌jcm.server閫氫俊錛屽畾鏈熷閲忔媺鍙栨暟鎹?/li>
- node allocator錛岄氳繃listener鏂瑰紡浠巗ubscriber涓幏鍙栨暟鎹紝鍚屾椂瀹炵幇鍚勭璐熻澆鍧囪 絳栫暐錛屽澶栫粺涓鎻愪緵
alloc node鐨勬帴鍙?/li>
鎺ヤ笅鏉ョ湅鐪嬪叧閿姛鑳界殑瀹炵幇
鏁版嵁鍚屾
鏃㈢劧jcm.server鏄垎甯冨紡鐨勶紝姣忎竴涓猨cm.server instance(瀹炰緥)閮芥槸鏀寔鏁版嵁璇誨拰鍐欑殑錛岄偅涔堝綋jcm.server綆＄悊鐫涓鍫哻luster涓婁竾涓猲ode鏃訛紝姣忎竴涓猧nstance鏄浣曡繘琛屾暟鎹悓姝ョ殑錛焜cm.server涓殑鏁版嵁涓昏鏈変袱綾伙細(xì)
- cluster鏈韓鐨勬暟鎹紝鍖呮嫭cluster/node鐨勬弿榪幫紝渚嬪cluster name銆乶ode IP銆佸強(qiáng)鍏朵粬闄勫睘鏁版嵁
- node鍋ュ悍媯(gè)鏌ョ殑鏁版嵁
瀵逛簬cluster鏁版嵁錛屽洜涓篶luster瀵筺ode鐨勭鐞嗘槸涓涓袱灞傜殑鏍?wèi)鐘毒l撴瀯錛岃屽cluster鏈夊鍒爊ode鐨勬搷浣滐紝鎵浠ュ茍涓嶈兘鍦ㄦ瘡涓涓猧nstance涓婇兘鎻愪緵鐪熸鐨勬暟鎹啓鍏ワ紝榪欐牱浼?xì)瀵艰嚧鏁版嵁涓㈠け銆傚亣璁懼悓涓鏃跺埢鍦╥nstance A鍜宨nstance B涓婂悓鏃跺cluster c1娣誨姞鑺傜偣N1鍜孨2錛岄偅涔坕nstance A鍐欏叆c1(N1)錛岃宨nstance B榪樻病絳夊埌鏁版嵁鍚屾灝卞啓鍏1(N2)錛岄偅涔坈1(N1)灝辮瑕嗙洊涓篶1(N2)錛屼粠鑰屽鑷存坊鍔犵殑鑺傜偣N1涓㈠け銆?/p>
鎵浠ワ紝jcm.server instance鏄垎涓?code>leader鍜?code>follower鐨勶紝鐪熸鐨勫啓鍏ユ搷浣滃彧鏈塴eader榪涜錛宖ollower鏀跺埌鍐欐搷浣滆姹傛椂杞彂緇檒eader銆俵eader鍐欐暟鎹紭鍏堟洿鏂板唴瀛樹(shù)腑鐨勬暟鎹啀鍐欏叆zookeeper錛屽唴瀛樹(shù)腑鐨勬暟鎹洿鏂板綋鐒舵槸闇瑕佸姞閿佷簰鏂ョ殑錛屼粠鑰屼繚璇佹暟鎹殑姝ｇ‘鎬с?/p>
leader鍜宖ollower鏄浣曠‘瀹氳鑹茬殑錛熻繖涓緢綆鍗曪紝鏍囧噯鐨勫埄鐢▃ookeeper鏉ヨ繘琛屼富浠?a >閫変婦鐨勫疄鐜?/a>銆?/p>
jcm.server instance鏁版嵁闂寸殑鍚屾鏄熀浜巣ookeeper watch鏈哄埗鐨勩傝繖涓彲浠ョ畻鍋氭槸涓涓狫CM鐨勪竴涓摱棰堬紝姣忎竴涓猧nstance閮戒細(xì)浣滀負(fù)涓涓獁atch錛屼嬌寰楀疄闄呬笂jcm.server騫朵笉鑳芥棤闄愭按騫蟲(chóng)墿灞曪紝鎵╁睍鍒頒竴瀹氱▼搴﹀悗錛寃atch鐨勬晥鐜囧氨鍙兘涓嶈凍浠ユ弧瓚蟲(chóng)ц兘浜?jiǎn)锛屽弬鑰?a >zookeeper鑺傜偣鏁頒笌watch鐨勬ц兘嫻嬭瘯 (閭ｄ釜鏃跺欐垜灝卞湪鑰冭檻瀵規(guī)垜浠郴緇熺殑閲嶆瀯浜? 銆?/p>
jcm.server涓node鍋ュ悍媯(gè)鏌ョ殑鏁版嵁閲囩敤鍚屾牱鐨勫悓姝ユ満鍒訛紝浣唍ode鍋ュ悍媯(gè)鏌ユ暟鎹槸姣忎竴涓猧nstance閮戒細(xì)鍐欏叆鐨勶紝涓嬮潰鐪嬬湅jcm.server鏄浣曢氳繃鍒嗗竷寮忔灦鏋勬潵鍒嗘媴鍘嬪姏鐨勩?/p>
鍋ュ悍媯(gè)鏌?/h3>
jcm.server鐨勫彟涓涓富瑕佸姛鑳界殑鏄node鐨勫仴搴鋒鏌ワ紝jcm.server闆嗙兢鍙互綆＄悊鍑犱竾鐨刵ode錛屾棦鐒跺凡緇忔槸鍒嗗竷寮忎簡(jiǎn)錛岄偅涔堟樉鐒舵槸瑕佹妸node鍧囧垎鍒板涓猧nstance鐨勩傝繖閲屾垜鏄互cluster鏉ュ垎閰嶇殑錛屾柟娉曞氨鏄畝鍗曠殑浣跨敤涓鑷存у搱甯屻傞氳繃涓鑷存у搱甯岋紝鍐沖畾涓涓猚luster鏄惁灞炰簬鏌愪釜instance璐熻矗銆傛瘡涓猧nstance閮芥湁涓涓猻erver spec錛屼篃灝辨槸璇nstance瀵瑰鎻愪緵鏈嶅姟鐨勫湴鍧(IP+port)錛岃繖鏍峰湪浠諱綍涓涓猧nstance涓婏紝瀹冪湅鍒扮殑鎵鏈塱nstance server spec閮芥槸鐩稿悓鐨勶紝浠庤屼繚璇佸湪姣忎竴涓猧nstance涓婅綆梒luster鐨勫垎閰嶅緱鍒扮殑緇撴灉閮芥槸涓鑷寸殑銆?/p>
鍋ュ悍媯(gè)鏌ユ寜cluster鍒掑垎錛屽彲浠ョ畝鍖栨暟鎹殑鍐欏啿紿侀棶棰橈紝鍦ㄦ甯告儏鍐典笅錛屾瘡涓猧nstance鍐欏叆鐨勫仴搴鋒鏌ョ粨鏋滈兘鏄笉鍚岀殑銆?/p>
鍋ュ悍媯(gè)鏌ヤ竴鑸互1縐掔殑棰戠巼榪涜錛宩cm.server鍋氫簡(jiǎn)浼樺寲錛屽綋媯(gè)鏌ョ粨鏋滃拰涓婁竴嬈′竴鏍鋒椂錛屽茍涓嶅啓鍏ookeeper銆傚啓鍏ョ殑鏁版嵁鍖呭惈浜?jiǎn)node鐨勫畬鏁磌ey (IP+Port+Spec)錛岃繖鏍峰彲浠ョ畝鍖栧緢澶氬湴鏂圭殑鏁版嵁鍚屾闂錛屼絾浼?xì)澧炲姞鍐欏叆鏁版嵁鐨勫ぇ灏忓Q屽啓鍏ユ暟鎹殑澶у皬鏄細(xì)褰卞搷zookeeper鐨勬ц兘鐨勶紝鎵浠ヨ繖閲岀畝鍗曞湴瀵規(guī)暟鎹繘琛屼簡(jiǎn)鍘嬬緝銆?/p>
鍋ュ悍媯(gè)鏌ユ槸鍙互鏀寔澶氱媯(gè)鏌ュ疄鐜扮殑錛岀洰鍓嶅彧瀹炵幇浜?jiǎn)HTTP鍗忚灞傜殑媯(gè)鏌ャ傚仴搴鋒鏌ヨ嚜韜槸鍗曚釜綰跨▼錛屽湪璇ョ嚎紼嬩腑鍩轟簬寮傛HTTP搴擄紝鍙戣搗寮傛璇鋒眰錛屽疄闄呯殑璇鋒眰鍦ㄥ叾浠栫嚎紼嬩腑鍙戝嚭銆?/p>
jcm.subscriber閫氫俊
jcm.subscriber涓巎cm.server閫氫俊錛屼富瑕佹槸涓轟簡(jiǎn)鑾峰彇鏈鏂扮殑cluster鏁版嵁銆俿ubscriber鍒濆鍖栨椂浼?xì)鎷垮堫C竴涓猨cm.server instance鐨勫湴鍧鍒楄〃錛岃闂椂浣跨敤杞絳栫暐浠ュ鉤琛cm.server鍦ㄥ鐞嗚姹傛椂鐨勮礋杞姐俿ubscriber姣忕閮戒細(xì)璇鋒眰涓嬈℃暟鎹紝璇鋒眰涓弿榪頒簡(jiǎn)鏈璇鋒眰鎯寵幏鍙栧摢浜沜luster鏁版嵁錛屽悓鏃舵惡甯︿竴涓猚luster鐨剉ersion銆傛瘡嬈luster鍦╯erver鍙樻洿鏃訛紝version灝卞彉鏇達(dá)紙鏃墮棿鎴籌級(jí)銆俿erver鍥炲璇鋒眰鏃訛紝濡傛灉version宸叉渶鏂幫紝鍙渶瑕佸洖澶峮ode鐨勭姸鎬併?/p>
subscriber鍙互鎷垮埌鎵鏈夌姸鎬佺殑node錛屽悗闈㈠彲浠ヨ冭檻鍙嬁姝ｅ父鐘舵佺殑node錛岃繘涓姝ュ噺灝戞暟鎹ぇ灝忋?/p>
鍘嬪姏嫻嬭瘯
鐩墠鍙鍋ュ悍媯(gè)鏌ラ儴鍒嗗仛浜?jiǎn)鍘媼箣锛岃缁嗗弬鑰?a >test/benchmark.md銆傚湪A7鏈嶅姟鍣ㄤ笂嫻嬭瘯錛屽彂鐜板啓zookeeper鍙?qiáng)zookeeper鐨剋atch瓚充互婊¤凍瑕佹眰錛宩cm.server鍙戣搗鐨凥TTP璇鋒眰鏄富瑕佺殑鎬ц兘鐑偣錛屽崟jcm.server instance澶ф鍙互鎵胯澆20000涓猲ode鐨勫仴搴風(fēng)洃嫻嬨?/p>
緗戠粶甯﹀錛?/p>
1 2 3 4 5 |
|
CPU錛岄氳繃jstack鏌ョ湅涓昏鐨凜PU娑堣楀湪HTTP搴撳疄鐜板眰錛屼互鍙?qiáng)鍋ュ轰h鏌ョ嚎紼嬶細(xì)
1 2 3 4 |
|
浠ｇ爜涓鍔犱簡(jiǎn)浜涚姸鎬佺洃鎺э細(xì)
1
|
|
琛ㄧず騫沖潎姣忔媯(gè)鏌ヨ楁椂542姣錛屽啓鏁版嵁鍥犱負(fù)寮鍚簡(jiǎn)cache娌℃湁鍙傝冧環(huán)鍊箋?/p>
铏界劧榪樺彲浠ヤ粠鎴戣嚜宸辯殑浠ｇ爜涓仛涓嶅皯浼樺寲錛屼絾鏃㈢劧鍗曟満鍙互鎵胯澆20000涓妭鐐圭殑媯(gè)嫻嬶紝涓鑸殑搴旂敤榪滆繙瓚沖浜?jiǎn)銆?/p>
鎬葷粨
鍚嶅瓧鏈嶅姟鍦ㄥ垎甯冨紡緋葷粺涓櫧鐒舵槸鍩虹鏈嶅姟錛屼絾寰寰鎵挎媴浜?jiǎn)闈炲笖R噸瑕佺殑瑙掕壊錛屾暟鎹悓姝ュ嚭鐜伴敊璇佽妭鐐圭姸鎬佸嚭鐜扮灛鏃剁殑閿欒錛岄兘鍙兘瀵規(guī)暣濂楃郴緇熼犳垚杈冨ぇ褰卞搷錛屼笟鍔′笂鍑虹幇杈冨ぇ鏁呴殰銆傛墍浠ュ悕瀛楁湇鍔＄殑鍋ュ．鎬с佸彲鐢ㄦч潪甯擱噸瑕併傚疄鐜頒腑闇瑕佽冭檻寰堝寮傚父鎯呭喌錛屽寘鎷綉緇滀笉紼沖畾銆佸簲鐢ㄥ眰鐨勯敊璇瓑銆備負(fù)浜?jiǎn)鎻愰珮鑳鲥鐨勫彲鐢ㄦэ紝涓鑸繕?shù)細(xì)鍔犲灞傜殑鏁版嵁cache錛屼緥濡俿ubscriber绔殑鏈湴cache錛宻erver绔殑鏈湴cache錛屼互淇濊瘉鍦ㄤ換浣曟儏鍐典笅閮戒笉浼?xì)濯?jiǎng)鍝嶅簲鐢ㄥ眰鐨勬湇鍔°?/p>
Kevin Lynx 2015-07-04 17:50 鍙戣〃璇勮
]]>鎺ヤ笂綃?a >浣跨敤RCU鎶鏈疄鐜拌鍐欑嚎紼嬫棤閿?/a>錛屽湪娌℃湁GC鏈哄埗鐨勮璦涓紝瑕佸疄鐜癓ock free鐨勭畻娉曪紝灝卞厤涓嶄簡(jiǎn)瑕佽嚜宸卞鐞嗗唴瀛樺洖鏀剁殑闂銆?/p>
Hazard Pointer鏄彟涓縐嶅鐞嗚繖涓棶棰樼殑綆楁硶錛岃屼笖鐩告瘮璧鋒潵涓嶄絾綆鍗曪紝鍔熻兘涔熷緢寮哄ぇ銆?a >閿佹棤鍏崇殑鏁版嵁緇撴瀯涓嶩azard鎸囬拡涓寰楀緢濂斤紝Wikipedia Hazard pointer涔熸弿榪板緱姣旇緝娓呮錛屾墍浠ユ垜榪欓噷灝變笉璁查偅涔堢粏浜?jiǎn)銆?/p>
涓涓畝鍗曠殑瀹炵幇鍙互鍙傝?a >鎴戠殑github haz_ptr.c
鍘熺悊
鍩烘湰鍘熺悊鏃犻潪涔熸槸璇葷嚎紼嬪鎸囬拡榪涜鏍囪瘑錛屾寚閽?鎸囧悜鐨勫唴瀛?瑕侀噴鏀炬椂閮戒細(xì)緙撳瓨璧鋒潵寤惰繜鍒扮‘璁ゆ病鏈夎綰跨▼浜?jiǎn)鎵嶅鍏剁湡姝ｉ噴鏀俱?/p>
<Lock-Free Data Structures with Hazard Pointers>涓殑鎻忚堪錛?/p>
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.”
鍏抽敭鐨勭粨鏋勫寘鎷細(xì)Hazard pointer銆?code>Thread Free list
Hazard pointer錛氫竴涓綰跨▼瑕佷嬌鐢ㄤ竴涓寚閽堟椂錛屽氨浼?xì)鍒涘晦Z竴涓狧azard pointer鍖呰榪欎釜鎸囬拡銆備竴涓狧azard pointer浼?xì)琚竴涓嚎紼嬪啓錛屽涓嚎紼嬭銆?/p>
struct HazardPointer {
void *real_ptr; // 鍖呰鐨勬寚閽?/span>
... // 涓嶅悓鐨勫疄鐜版湁涓嶅悓鐨勬垚鍛?/span>
};
void func() {
HazardPointer *hp = accquire(_real_ptr);
... // use _real_ptr
release(hp);
}Thread Free List錛氭瘡涓嚎紼嬮兘鏈変竴涓繖鏍風(fēng)殑鍒楄〃錛屼繚瀛樼潃灝嗚閲婃斁鐨勬寚閽堝垪琛紝榪欎釜鍒楄〃浠呭搴旂殑綰跨▼璇誨啓
void defer_free(void *ptr) {
_free_list.push_back(ptr);
}褰撴煇涓嚎紼嬭灝濊瘯閲婃斁Free List涓殑鎸囬拡鏃訛紝渚嬪鎸囬拡ptr錛屽氨媯(gè)鏌ユ墍鏈夊叾浠栫嚎紼嬩嬌鐢ㄧ殑Hazard pointer錛屾鏌ユ槸鍚﹀瓨鍦ㄥ寘瑁呬簡(jiǎn)ptr鐨凥azard pointer錛屽鏋滄病鏈夊垯璇存槑娌℃湁璇葷嚎紼嬫鍦ㄤ嬌鐢?code>ptr錛屽彲浠ュ畨鍏ㄩ噴鏀?code>ptr銆?/p>
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
}
}浠ヤ笂錛屽叾瀹炲氨鏄?code>Hazard Pointer鐨勪富瑕佸唴瀹廣?/p>
Hazard Pointer鐨勭鐞?/h2>
涓婇潰鐨勪唬鐮佷腑娌℃湁鎻愬埌_all_hazard_pointers鍙?code>accquire鐨勫叿浣撳疄鐜幫紝榪欏氨鏄疕azard Pointer鐨勭鐞嗛棶棰樸?/p>
銆婇攣鏃犲叧鐨勬暟鎹粨鏋勪笌Hazard鎸囬拡銆嬫枃涓垱寤轟簡(jiǎn)涓涓狶ock free鐨勯摼琛ㄦ潵琛ㄧず榪欎釜鍏ㄥ眬鐨凥azard Pointer List銆傛瘡涓狧azard Pointer鏈変竴涓垚鍛樻爣璇嗗叾鏄惁鍙敤銆傝繖涓狶ist涓篃灝變繚瀛樹(shù)簡(jiǎn)宸茬粡琚嬌鐢ㄧ殑Hazard Pointer闆嗗悎鍜屾湭琚嬌鐢ㄧ殑Hazard Pointer闆嗗悎錛屽綋鎵鏈塇azard Pointer閮借浣跨敤鏃訛紝灝變細(xì)鏂板垎閰嶄竴涓姞榪涜繖涓狶ist銆傚綋璇葷嚎紼嬩笉浣跨敤鎸囬拡鏃訛紝闇瑕佸綊榪楬azard Pointer錛岀洿鎺ヨ緗彲鐢ㄦ垚鍛樻爣璇嗗嵆鍙傝gc()鏃訛紝灝辯洿鎺ラ亶鍘嗚繖涓狶ist銆?/p>
瑕佸疄鐜頒竴涓狶ock free鐨勯摼琛紝騫朵笖浠呴渶瑕佸疄鐜板ご鎻掑叆錛岃繕鏄潪甯哥畝鍗曠殑銆傛湰韜獺azard Pointer鏍囪瘑鏌愪釜鎸囬拡鏃訛紝閮芥槸鐢ㄤ簡(jiǎn)鍚庣珛鍗蟲(chóng)爣璇嗭紝鎵浠ヨ繖涓疄鐜扮洿鎺ユ敮鎸佷簡(jiǎn)鍔ㄦ佺嚎紼嬶紝鏀寔綰跨▼鐨勬寕璧風(fēng)瓑銆?/p>
鍦?a >nbds欏圭洰涓篃鏈変竴涓狧azard Pointer鐨勫疄鐜幫紝鐩稿瑕佸急涓鐐廣傚畠涓烘瘡涓嚎紼嬮兘璁劇疆浜?jiǎn)鑷忿q殑Hazard Pointer姹狅紝鍐欑嚎紼嬭閲婃斁鎸囬拡鏃訛紝灝辮闂墍鏈夊叾浠栫嚎紼嬬殑Hazard Pointer姹犮?/p>
typedef struct haz_local {
// Free List
pending_t *pending; // to be freed
int pending_size;
int pending_count;
// Hazard Pointer 姹狅紝鍔ㄦ佸拰闈?rùn)鎬佷袱縐?/span>
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] = {};姣忎釜綰跨▼褰撶劧灝辨秹鍙?qiáng)鍒?code>haz_local_绱㈠紩(ID)鐨勫垎閰嶏紝灝卞儚浣跨敤RCU鎶鏈疄鐜拌鍐欑嚎紼嬫棤閿?/a>涓殑涓鏍楓傝繖涓疄鐜頒負(fù)浜?jiǎn)鏀寔绾拷E嬪姩鎬佸垱寤猴紝灝遍渶瑕佷竴濂楃嚎紼婭D鐨勯噸鐢ㄦ満鍒訛紝鐩稿澶嶆潅澶氫簡(jiǎn)銆?/p>
鏈鍚庯紝闄勪笂涓浜涘茍琛岀紪紼嬩腑鐨勪竴浜涙蹇點(diǎn)?/p>
甯稿父鐪嬪埌闄勫綍
Lock Free & Wait Free
Lock Free鍜?code>Wait Free鐨勬蹇碉紝榪欎簺姒傚康鐢ㄤ簬琛￠噺涓涓郴緇熸垨鑰呰涓孌典唬鐮佺殑騫惰綰у埆錛屽茍琛岀駭鍒彲鍙傝?a >騫惰緙栫▼——騫跺彂綰у埆
鎴戣嚜宸辯殑鐞嗚В錛屼緥濡傘婇攣鏃犲叧鐨勬暟鎹粨鏋勪笌Hazard鎸囬拡銆嬩腑瀹炵幇鐨凥azard Pointer閾捐〃灝卞彲浠ヨ鏄疞ock Free鐨勶紝娉ㄦ剰瀹冨湪鎻掑叆鏂板厓绱犲埌閾捐〃澶存椂錛屽洜涓轟嬌鐢?code>CAS錛屾誨厤涓嶄簡(jiǎn)涓涓猙usy loop錛屾湁榪欎釜鐗瑰緛鐨勬儏鍐典笅灝辯畻鏄?code>Lock Free錛岃櫧鐒舵病閿侊紝浣嗘煇涓嚎紼嬬殑鎵ц鎯呭喌涔熷彈鍏朵粬綰跨▼鐨勫獎(jiǎng)鍝嶃?/p>
鐩稿鑰岃█錛?code>Wait Free鍒欐槸姣忎釜綰跨▼鐨勬墽琛岄兘鏄嫭绔嬬殑錛屼緥濡傘婇攣鏃犲叧鐨勬暟鎹粨鏋勪笌Hazard鎸囬拡銆嬩腑鐨?code>Scan鍑芥暟銆?code>“姣忎釜綰跨▼鐨勬墽琛屾椂闂撮兘涓嶄緷璧栦簬鍏跺畠浠諱綍綰跨▼鐨勮涓?#8221;
閿佹棤鍏?Lock-Free)鎰忓懗鐫緋葷粺涓誨瓨鍦ㄦ煇涓嚎紼嬭兘澶熷緱浠ョ戶緇墽琛岋紱鑰岀瓑寰呮棤鍏?Wait-Free)鍒欐槸涓涓洿寮虹殑鏉′歡錛屽畠鎰忓懗鐫鎵鏈夌嚎紼嬮兘鑳藉線涓嬭繘琛屻?/p>
ABA闂
鍦ㄥ疄鐜?code>Lock Free綆楁硶鐨勮繃紼嬩腑錛屾繪槸瑕佷嬌鐢?code>CAS鍘熻鐨勶紝鑰?code>CAS灝變細(xì)甯︽潵ABA闂銆?/p>
鍦ㄨ繘琛孋AS鎿嶄綔鐨勬椂鍊欙紝鍥犱負(fù)鍦ㄦ洿鏀筕涔嬪墠錛孋AS涓昏璇㈤棶“V鐨勫兼槸鍚︿粛鐒朵負(fù)A”錛屾墍浠ュ湪絎竴嬈¤鍙朧涔嬪悗浠ュ強(qiáng)瀵筕鎵цCAS鎿嶄綔涔嬪墠錛屽鏋滃皢鍊間粠A鏀逛負(fù)B錛岀劧鍚庡啀鏀瑰洖A錛屼細(xì)浣垮熀浜嶤AS鐨勭畻娉曟販涔便傚湪榪欑鎯呭喌涓嬶紝CAS鎿嶄綔浼?xì)鎴愬姛銆傝繖綾婚棶棰樼О涓篈BA闂銆?/p>
Wiki Hazard Pointer鎻愬埌浜?jiǎn)涓涓狝BA闂鐨勫ソ渚嬪瓙錛氬湪涓涓狶ock free鐨勬爤瀹炵幇涓紝鐜板湪瑕佸嚭鏍堬紝鏍堥噷鐨勫厓绱犳槸[A, B, C]錛?code>head鎸囧悜鏍堥《錛岄偅涔堝氨鏈?code>compare_and_swap(target=&head, newvalue=B, expected=A)銆備絾鏄湪榪欎釜鎿嶄綔涓紝鍏朵粬綰跨▼鎶?code>A B閮藉嚭鏍堬紝涓斿垹闄や簡(jiǎn)B錛屽張鎶?code>A鍘嬪叆鏍堜腑錛屽嵆[A, C]銆傞偅涔堝墠涓涓嚎紼嬬殑compare_and_swap鑳藉鎴愬姛錛屾鏃?code>head鎸囧悜浜?jiǎn)涓涓凡緇忚鍒犻櫎鐨?code>B銆俿tackoverflow涓婁篃鏈変釜渚嬪瓙 Real-world examples for ABA in multithreading
瀵逛簬CAS浜х敓鐨勮繖涓狝BA闂錛岄氬父鐨勮В鍐蟲(chóng)柟妗堟槸閲囩敤CAS鐨勪竴涓彉縐岲CAS銆侱CAS錛屾槸瀵逛簬姣忎竴涓猇澧炲姞涓涓紩鐢ㄧ殑琛ㄧず淇敼嬈℃暟鐨勬爣璁扮銆傚浜庢瘡涓猇錛屽鏋滃紩鐢ㄤ慨鏀逛簡(jiǎn)涓嬈★紝榪欎釜璁℃暟鍣ㄥ氨鍔?銆傜劧鍚庡啀榪欎釜鍙橀噺闇瑕乽pdate鐨勬椂鍊欙紝灝卞悓鏃舵鏌ュ彉閲忕殑鍊煎拰璁℃暟鍣ㄧ殑鍊箋?/p>
浣嗕篃鏃╂湁浜烘彁鍑?code>DCAS涔熶笉鏄?a >ABA problem 鐨勯摱寮?/a>銆?/p>
Kevin Lynx 2015-05-03 20:46 鍙戣〃璇勮
]]>鐜拌薄
綰夸笂鐨勬湇鍔″嚭鐜癱oredump錛屽爢鏍堜負(fù)錛?/p>
#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
...
鏌ョ湅浜?jiǎn)搴旂敤灞傜浉鍏虫暟鎹l撴瀯錛屽熀鏈暟鎹兘鏄病鏈夐棶棰樼殑銆傛墍浠ユ渶鍒濇鐤戞槸tcmalloc鍐呴儴緇存姢浜?jiǎn)閿欒鐨勫唴瀛樺Q屽湪鍒嗛厤鍐呭瓨鏃跺嚭閿欙紝榪欎釜鍫嗘爤鍙槸闂鐨勮〃璞°傚嚑澶╁悗錛岀嚎涓婄殑鍙︿竴涓湇鍔★紝鍩轟簬鍚屾牱鐨勫簱錛屼篃core浜?jiǎn)锛屽爢鏍垬q樻槸涓鏍風(fēng)殑銆?/p>
鏈鍒濆畾浣嶉棶棰橀兘鏄粠鏈榪戞洿鏂扮殑涓滆タ鍏ユ墜錛屽寘鎷緷璧栫殑server鐜錛屼絾閮芥病鏈夋槑鏄劇殑闂錛屾墍浠ユ渶鍚庡彧鑳戒粠core鐨勭洿鎺ュ師鍥犲叆鎵嬨?/p>
鍒嗘瀽GetStackTrace
紜core鐨勮緇嗕綅緗細(xì)
# core鍦ㄨ鎸囦護(hù)
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]澶勮鍙栧唴瀹癸紝鐒跺悗鍑洪敊錛岃繖涓唴瀛樺崟鍏冧笉鍙銆備絾鏄叿浣撹繖涓寚浠ゅ湪浠ｇ爜涓槸浠涔堟剰鎬濓紝闇瑕佸皢榪欎釜鎸囦護(hù)瀵瑰簲鍒頒唬鐮佷腑銆傝幏鍙杢cmalloc鐨勬簮鐮侊紝鍙戠幇GetStackTrace鏍規(guī)嵁緙栬瘧閫夐」鏈夊緢澶氬疄鐜幫紝鎵浠ヨ繖閲岄夋嫨鏈鍙兘鐨勫疄鐜幫紝鐒跺悗瀵規(guī)瘮姹囩紪浠ョ‘璁や唬鐮佹槸鍚﹀尮閰嶃傛渶鍒濋夋嫨鐨勬槸stacktrace_x86-64-inl.h錛屽悗鏉ュ彂鐜板畬鍏ㄤ笉鍖歸厤錛屽張閫夋嫨浜?code>stacktrace_x86-inl.h銆傝繖涓疄鐜扮増鏈噷涔熸湁瀵?4浣嶅鉤鍙扮殑鏀寔銆?/p>
stacktrace_x86-inl.h閲屼嬌鐢ㄤ簡(jiǎn)涓浜涘畯鏉ョ敓鎴愬嚱鏁板悕鍜屽弬鏁幫紝綺劇畝鍚庝唬鐮佸ぇ姒備負(fù)錛?/p>
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鏄竴涓ā鏉垮嚱鏁幫紝鍖呭惈涓澶у爢浠ｇ爜錛岀簿綆鍚庨潪甯哥畝鍗曪細(xì)
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;
}涓婇潰榪欎釜浠ｇ爜鍒版眹緙栫殑瀵規(guī)瘮榪囩▼榪樻槸鑺變簡(jiǎn)浜涙椂闂達(dá)紝鍏朵腑姹囩紪涓嚭鐜扮殑涓浜涘父閲忓彲浠ュぇ澶х緝鐭姣旀椂闂達(dá)紝渚嬪涓婇潰鍑虹幇浜?code>100000錛屾眹緙栦腑灝辨湁錛?/p>
0x000000000045d176 <_Z13GetStackTracePPvii+70>: cmp $0x186a0,%rbx # 100000=0x186a0
娉ㄦ剰NextStackFrame涓殑 if (STRICT_UNWINDING)浣跨敤鐨勬槸妯℃澘鍙傛暟錛岃繖瀵艱嚧鐢熸垚鐨勪唬鐮佷腑鏍規(guī)湰娌℃湁else閮ㄥ垎錛屼篃灝辨病鏈?code>1000000榪欎釜甯擱噺
鍦ㄥ姣斾唬鐮佺殑榪囩▼涓紝鍙互鐭ラ亾鍏抽敭鐨勫嚑涓瘎瀛樺櫒銆佸唴瀛樹(shù)綅緗搴斿埌浠ｇ爜涓殑鍙橀噺錛屼粠鑰屽彲浠ヨ繕鍘焎ore鏃剁殑鐜板満鐜銆傚垎鏋愯繃紼嬩腑涓嶄竴瀹氳浠庣涓琛屾眹緙栬錛屽彲浠ヤ粠杈冩槑鏄劇殑浣嶇疆璇伙紝浠庤岃繕鍘熸暣涓唬鐮侊紝鍑芥暟榪斿洖鎸囦護(hù)銆佽煩杞寚浠ゃ佹瘮杈冩寚浠ゃ佽鍐呭瓨鎸囦護(hù)銆佸弬鏁板瘎瀛樺櫒絳夐兘鏄瘮杈冩槑鏄懼搴旂殑鍦版柟銆?/p>
鍙﹀娉ㄦ剰GetStackTrace鍦?code>RecordGrowth涓皟鐢紝浼犲叆浜?涓弬鏁幫細(xì)
GetStackTrace(t->stack, kMaxStackDepth-1, 3); // kMaxStackDepth = 31
浠ヤ笅鏄垜鍒嗘瀽鐨勭畝鍗曟敞瑙ｏ細(xì)
(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 # 鍏抽敭浣嶇疆錛?(sp+1) -> r9, rax 瀵瑰簲 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錛岃繖閲屽凡緇忔槸NextStackFrame鐨勪唬鐮?
0x000000000045d151 <_Z13GetStackTracePPvii+33>: cmp %rcx,%rax # new_sp <= old_sp ?
0x000000000045d154 <_Z13GetStackTracePPvii+36>: jb 0x45d170 <_Z13GetStackTracePPvii+64> # new_sp > old_sp 璺寵漿
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 瀛樺偍浜?jiǎn)杩斿洖鍊鹼紝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)# 鍏抽敭浣嶇疆錛歳esult[n] = *(sp+1)
0x000000000045d191 <_Z13GetStackTracePPvii+97>: jmp 0x45d15f <_Z13GetStackTracePPvii+47>
鍒嗘瀽榪囩▼姣旇緝鑰楁椂錛屽悓鏃惰繕鍙互鍒嗘瀽涓?code>GetStackTrace鍑芥暟鐨勫疄鐜板師鐞嗭紝鍏跺疄灝辨槸鍒╃敤RBP瀵勫瓨鍣ㄤ笉鏂洖婧紝浠庤屽緱鍒版暣涓皟鐢ㄥ爢鏍堝悇涓嚱鏁扮殑鍦板潃錛堜弗鏍兼潵璇存槸榪斿洖鍦板潃錛夈傜畝鍗曠ず鎰忎笅鍑芥暟璋冪敤涓璕BP鐨勬儏鍐碉細(xì)
...
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
鎬諱箣錛?strong>涓鑸儏鍐典笅錛屼換浣曚竴涓嚱鏁頒腑錛孯BP瀵勫瓨鍣ㄦ寚鍚戜簡(jiǎn)褰撳墠鍑芥暟鐨勬爤鍩哄潃錛岃鏍堝熀鍧涓張瀛樺偍浜?jiǎn)璋冪敤鑰呯殑鏍堝熀鍧錛屽悓鏃惰鏍堝熀鍧鍓嶉潰榪樺瓨鍌ㄤ簡(jiǎn)璋冪敤鑰呯殑榪斿洖鍦板潃銆傛墍浠ワ紝GetStackTrace鐨勫疄鐜幫紝綆鍗曟潵璇村ぇ姒傚氨鏄細(xì)
sp = rbp // 鍙栧緱褰撳墠鍑芥暟GetStackTrace鐨勬爤鍩哄潃
while (n < max_depth) {
new_sp = *sp
result[n] = *(new_sp+1)
n++
}浠ヤ笂錛屾渶緇堝氨鐭ラ亾浜?jiǎn)浠ヤ笅鍏抽敭淇℃伅锛?xì)
- r8 瀵瑰簲鍙橀噺 n錛岃〃紺哄綋鍓嶅彇鍒扮鍑犱釜鏍堝撫浜?/li>
- rax 瀵瑰簲鍙橀噺 sp錛屼唬鐮乧ore鍦?*(sp+1)
- rdi 瀵瑰簲鍙橀噺 result錛岀敤浜庡瓨鍌ㄥ彇寰楃殑鍚勪釜鍦板潃
鐒跺悗鍙互鐪嬬湅鐜板満鏄庢牱鐨勶細(xì)
(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
灝忕粨錛?/strong>
GetStackTrace鍦ㄥ彇璋冪敤__conhash_get_rbnode鐨勫嚱鏁版椂鍑洪敊錛屽彇寰椾簡(jiǎn)5涓嚱鏁板湴鍧銆傚綋鍓嶄嬌鐢ㄧ殑RBP涓?code>0x4e73aa58銆?/p>
閿欒鐨凴BP
RBP涔熸槸浠庡爢鏍堜腑鍙栧嚭鏉ョ殑錛屾棦鐒惰繖涓湴鍧鏈夐棶棰橈紝棣栧厛鎯沖埌鐨勫氨鏄湁浠ｇ爜灞閮ㄥ彉閲?鏁扮粍鍐欒秺鐣屻備緥濡?code>sprintf鐨勪嬌鐢ㄣ傝屼笖錛?strong>涓鑸啓瓚婄晫鐮村潖鍫嗘爤錛岄兘鍙兘鏄妸璋冪敤鑰呯殑鍫嗘爤鐮村潖浜?/strong>錛屼緥濡傦細(xì)
char s[32];
memcpy(s, p, 1024);
鍥犱負(fù)鍐欏叆閮芥槸浠庝綆鍦板潃寰楂樺湴鍧鍐欙紝鑰岃皟鐢ㄨ呯殑鍫嗘爤鍦ㄩ珮鍦板潃銆傚綋鐒?dòng)灱屼篃浼?xì)閬囧埌鍐欏潖璋冪敤鑰呯殑璋冪敤鑰呯殑鍫嗘爤錛屼篃灝辨槸璺ㄦ爤甯ц秺鐣屽啓錛屼緥濡備互鍓嶉亣鍒扮殑錛?/p>
len = vsnprintf(buf, sizeof(buf), fmt, wtf-long-string);
buf[len] = 0;
__conhash_get_rbnode鐨凴BP鏄湪tcmalloc鐨勫爢鏍堜腑鍙栫殑錛?/p>
(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
鎵浠ヨ繖閲屽氨浼?xì)鎬鐤戞槸tcmalloc榪欎釜鍑芥暟閲屾湁鎶婂爢鏍堢牬鍧忥紝榪欎釜鏃跺欏氨鏄浠ｇ爜錛岀湅鐪嬫湁娌℃湁鐤戜技鍗遍櫓鐨勫湴鏂癸紝鏈灉銆傝繖閲屽氨闄峰叆浜?jiǎn)鍍靛眬錛屾鐤戝張閬囧埌浜?jiǎn)璺ㄦ爤鍝徵牬鍧忕殑鎯呭喌锛寴q欎釜鏃跺欏氨鍙兘__conhash_get_rbnode璋冪敤鏍堜腑鍛ㄥ洿鐨勫嚱鏁扮炕緲伙紝渚嬪璋冪敤__conhash_get_rbnode鐨勫嚱鏁?code>__conhash_add_replicas涓伆濂芥湁瀛楃涓叉搷浣滐細(xì)
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);
...榪欐浠ｇ爜鏈緇堝彂鐜版槸娌℃湁闂鐨勶紝榪欓噷鍙堣楄垂浜?jiǎn)涓崬畱鏃堕棿銆傚悗鏉ュ彂鐜拌嫢騫蹭釜鍑芥暟閲岀殑RBP閮芥湁鐐瑰鎬紝榪欎釜璋冪敤鏍堟瘮杈冩甯哥殑鑼冨洿鏄細(xì)0x4e738c90
(gdb) f 8
#8 0x00007f75532cd4c2 in __conhash_get_rbnode (node=0x22c86870, hash=30)
(gdb) p/x $rbp
$6 = 0x4e73aa58 # 榪欎釜榪樹(shù)笉綆楃壒鍒彲鐤?
(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
涓轟粈涔堝緢澶氬嚱鏁頒腑RBP閮界湅璧鋒潵涓嶆甯革紵 鎯充簡(jiǎn)鎯崇湡瑕佹槸浠ｇ爜閲屾妸鍫嗘爤鐮村潖浜?jiǎn)锛寴q欓敊璇緱鍙戠敓寰楀宸у錛?/p>
閿欒RBP鐨勬潵婧?/h2>
鐒跺悗杞満鏉ヤ簡(jiǎn)錛岃剳嫻蜂腑紿佺劧闂嚭-fomit-frame-pointer銆傜紪璇戝櫒鐢熸垚鐨勪唬鐮佷腑鏄彲浠ヤ笉闇瑕佹爤鍩哄潃鎸囬拡鐨勶紝涔熷氨鏄疪BP瀵勫瓨鍣ㄤ笉浣滀負(fù)鏍堝熀鍧瀵勫瓨鍣ㄣ傚ぇ閮ㄥ垎鍑芥暟鎴栬呰寮鍚簡(jiǎn)frame-pointer鐨勫嚱鏁幫紝鍏跺嚱鏁板ご閮戒細(xì)鏈変互涓嬫寚浠わ細(xì)
push %rbp
mov %rsp,%rbp
...
琛ㄧず淇濆瓨璋冪敤鑰呯殑鏍堝熀鍧鍒版爤涓紝浠ュ強(qiáng)璁劇疆鑷繁鐨勬爤鍩哄潃銆傜湅涓?code>__conhash緋誨垪鍑芥暟錛?/p>
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錛屾煡闃?a >gcc鎵嬪唽錛宱2浼樺寲鏄紑鍚簡(jiǎn)omit-frame-pinter 鐨勩?/p>
鍦ㄦ病鏈塕BP鐨勬儏鍐典笅錛宼cmalloc鐨?code>GetStackTrace灝濊瘯璇籖BP鍙栬幏鍙栬皟鐢ㄨ繑鍥炲湴鍧錛岃嚜鐒舵槸鏈夐棶棰樼殑銆備絾鏄紝濡傛灉鏁翠釜璋冪敤鏍堜腑鐨勫嚱鏁幫紝瑕佷箞鏈塕BP錛岃涔堟病鏈塕BP錛岄偅涔?code>GetStackTrace鍙栧嚭鐨勭粨鏋滄渶澶氬氨鏄煩榪囦竴浜涙爤甯э紝涓嶄細(xì)鍑洪敊銆?/strong> 闄ら潪錛岃繖涓棿鐨勬煇涓嚱鏁版妸RBP瀵勫瓨鍣ㄥ彟浣滀粬鐢紙緙栬瘧鍣ㄧ渷鍑?guó)櫩欎釜瀵勫瓨鍣ㄨ偗瀹氭槸瑕佸彟浣滀粬鐢ㄧ殑锛?jí)銆傛墍浠ヨ繖閲岀戶緇拷鏌ヨ繖涓敊璇湴鍧 鏉ユ簮宸茬粡姣旇緝鏄庢樉錛岃偗瀹氭槸 榪欓噷鎵撳嵃RSI瀵勫瓨鍣ㄧ殑鍊煎彲鑳戒細(xì)琚瀵鹼紝鍥犱負(fù)浠諱綍鏃跺欐墦鍗板瘎瀛樺櫒鐨勫煎彲鑳介兘鏄敊鐨勶紝闄ら潪瀹冩湁琚樉紺轟繚瀛樸備笉榪囪繖閲屽彲浠ョ湅鍑篟SI鐨勫兼潵婧愪簬鍙傛暟(RSI瀵瑰簲絎簩涓弬鏁?錛?/p>
榪藉埌 鎵懼埌浜?code>0x4e73aa58鐨勬潵婧愩傝繖涓湴鍧鍊肩珶鐒舵槸涓涓瓧絎︿覆鍝堝笇綆楁硶綆楀嚭鏉ョ殑錛佽繖閲岃繕鍙互鐪嬬湅榪欎釜瀛楃涓茬殑鍐呭錛?/p>
榪欎釜紕夊牎鐨勫搱甯屽嚱鏁版槸 浠ヤ笂錛屾棦鐒跺彧瑕佹煇涓簱 鏈変簡(jiǎn)浠ヤ笂鏉′歡錛屾墠浣垮緱榪欎釜core鍑犵巼鍙樺緱寰堜綆銆?/p>
鏈鍚庯紝濡傛灉浣犲緢鐔熸?zhèn)塼cmalloc錛屾暣涓棶棰樹(shù)及璁″氨琚瑙ｄ簡(jiǎn)錛?a >tcmalloc INSTALL 鍙﹀闄勪笂鍙︿竴涓湁鎰忔濈殑涓滆タ銆?/p>
鍦ㄥ垎鏋?code>__conhash_add_replicas鏃訛紝鍏跺唴瀹氫箟浜?jiǎn)涓涓?4瀛楄妭鐨勫瓧絎︽暟緇勶紝鏌ョ湅鍏跺爢鏍堬細(xì) 鏈寮濮嬫垜瑙夊緱0x4e73aa58鐨勬潵婧愩?/p>
__conhash_get_rbnode涓緗殑錛屽洜涓鴻繖涓嚱鏁扮殑RBP鏄湪琚皟鐢ㄨ?code>tcmalloc涓繚瀛樼殑銆?/p>
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 # 鏀瑰啓浜?jiǎn)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> # 璋冪敤tcmalloc錛屾眹緙栧埌榪欓噷鍗沖彲
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鍊肩敱涓涓瓧絎︿覆鍝堝笇鍑芥暟璁＄畻
if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
{
util_rbtree_node_t* rbnode = __conhash_get_rbnode(node, hash); // hash鍊?/span>
...__conhash_add_replicas錛?/p>
0x00007f75532cd764 <__conhash_add_replicas+164>: mov %ebx,%esi # 鏉ユ簮浜巖bx
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
(gdb) x/1s $rsp
0x4e738bd0: "conhash-00000-00133"
conhash_hash_def銆?/p>
coredump鐨勬潯浠?/h2>
omit-frame-pointer錛岄偅tcmalloc灝卞彲鑳藉嚭閿欙紝涓轟粈涔堝彂鐢熺殑棰戠巼騫朵笉楂樺憿錛熻繖涓彲浠ュ洖鍒?code>GetStackTrace灝ゅ叾鏄?code>NextStackFrame鐨勫疄鐜幫紝鍏朵腑鍖呭惈浜?jiǎn)鍑犱釜鍚堟硶RBP鐨勫垽瀹氾細(xì)if (new_sp <= old_sp) return NULL; // 涓婁竴涓爤甯х殑RBP鑲畾姣斿綋鍓嶇殑澶?/span>
if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL; // 鎸囬拡鍊艱寖鍥磋繕蹇呴』鍦?00000鍐?/span>
...
if ((uintptr_t)new_sp & (sizeof(void *) - 1)) return NULL; // 鐢變簬鏈韓淇濆瓨鐨勬槸鎸囬拡錛屾墍浠ヨ繕蹇呴』鏄痵izeof(void*)鐨勬暣鏁板嶏紝瀵歸綈鎬葷粨
闄?/h2>
(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鍗?4瀛楄妭錛屼篃灝辨槸鏁翠釜[0x4e738bd0, 0x4e738c10)鍐呭瓨錛屼絾鏄繖鍧楀唴瀛橀噷灞呯劧鏈夊嚱鏁板湴鍧錛岃繖涓搴︿嬌鎴戞鐤戣繖閲屾湁闂銆傚悗鏉ラ啋鎮(zhèn)熻繖浜涘湴鍧鏄畾涔?code>buf鍓嶈皟鐢?code>__conhash_create_node浜х敓鐨勶紝璋冪敤榪囩▼涓啓鍒板爢鏍堥噷錛岃皟鐢ㄥ畬鍚庢爤鎸囬拡鏀瑰彉錛屼絾騫朵笉闇瑕佹竻絀烘爤涓殑鍐呭銆?/p>
Kevin Lynx 2015-04-06 18:33 鍙戣〃璇勮]]>
鏈夋椂鍊欏湪綰夸笂浣跨敤gdb璋冭瘯紼嬪簭core闂鏃訛紝鍙兘娌℃湁絎﹀彿鏂囦歡錛屾嬁鍒扮殑浠呮槸涓涓唴瀛樺湴鍧錛屽鏋滆繖涓寚鍚戠殑鏄竴涓猄TL瀵硅薄錛岄偅涔堝浣曟煡鐪嬭繖涓璞＄殑鍐呭鍛紵
鍙渶瑕佺煡閬揝TL鍚勪釜瀹瑰櫒鐨勬暟鎹粨鏋勫疄鐜幫紝灝卞彲浠ユ煡鐪嬪叾鍐呭銆傛湰鏂囨弿榪頒簡(jiǎn)SGI STL瀹炵幇涓父鐢ㄥ鍣ㄧ殑鏁版嵁緇撴瀯錛屼互鍙?qiáng)濡備綍鍦╣db涓煡鐪嬪叾鍐呭銆?/p>
string
string錛屽嵆basic_string bits/basic_string.h錛?/p>
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鍐呮湁涓涓寚閽堬紝鎸囧悜瀹為檯鐨勫瓧絎︿覆浣嶇疆錛岃繖涓綅緗墠闈㈡湁涓涓?code>_Rep緇撴瀯錛屽叾鍐呬繚瀛樹(shù)簡(jiǎn)瀛楃涓茬殑闀垮害銆佸彲鐢ㄥ唴瀛樹(shù)互鍙?qiáng)寮曠敤璁℃暟銆傚綋鎴戜滑鎷垮埌涓涓猻tring瀵硅薄鐨勫湴鍧鏃訛紝鍙互閫氳繃浠ヤ笅浠ｇ爜鑾峰彇鐩稿叧鍊鹼細(xì)
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();
}鍦╣db涓嬁鍒頒竴涓猻tring鐨勫湴鍧鏃訛紝鍙互浠ヤ笅鎵撳嵃鍑?guó)櫙ュ瓧绗︿覆鍙?qiáng)闀垮害錛?/p>
(gdb) x/1a p
0x7fffffffe3a0: 0x606028
(gdb) p (char*)0x606028
$2 = 0x606028 "hello"
(gdb) x/1dg 0x606028-24
0x606010: 5
vector
浼楁墍鍛ㄧ煡vector瀹炵幇灝辨槸涓鍧楄繛緇殑鍐呭瓨錛?code>bits/stl_vector.h銆?/p>
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錛屽叾鍐呬篃灝辨槸3涓寚閽堬紝_M_start鎸囧悜棣栧厓绱犲湴鍧錛?code>_M_finish鎸囧悜鏈鍚庝竴涓妭鐐?1錛?code>_M_end_of_storage鏄彲鐢ㄧ┖闂存渶鍚庣殑浣嶇疆銆?/p>
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()); }鍙互閫氳繃浠ｇ爜浠庝竴涓獀ector瀵硅薄鍦板潃杈撳嚭鍏朵俊鎭細(xì)
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杈撳嚭涓涓獀ector涓殑鍐呭錛?/p>
(gdb) p p
$3 = (void *) 0x7fffffffe380
(gdb) x/1a p
0x7fffffffe380: 0x606080
(gdb) x/3xw 0x606080
0x606080: 0x00000011 0x00000022 0x00000033
list
浼楁墍鍛ㄧ煡list琚疄鐜頒負(fù)涓涓摼琛ㄣ傚噯紜潵璇存槸涓涓弻鍚戦摼琛ㄣ俵ist鏈韓鏄竴涓壒孌婅妭鐐癸紝鍏朵唬琛╡nd錛屽叾鎸囧悜鐨勪笅涓涓厓绱犳墠鏄痩ist鐪熸鐨勭涓涓妭鐐癸細(xì)
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>鎵浠?code>sizeof(list<xx>)=16錛屼袱涓寚閽堛傛瘡涓涓湡姝ｇ殑鑺傜偣棣栧厛鏄寘鍚袱涓寚閽堬紝鐒跺悗鏄厓绱犲唴瀹?_List_node)銆?/p>
閫氳繃浠ｇ爜杈撳嚭list鐨勫唴瀹癸細(xì)
#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();
}鍦╣db涓彲浠ヤ互涓嬫柟寮忛亶鍘嗚list錛?/p>
(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浣跨敤鐨勬槸綰㈤粦鏍?wèi)瀹炵帋图屽疄闄呬娇鐢ㄧ殑鏄?code>stl_tree.h瀹炵幇錛?/p>
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));
}鎵浠ュ彲浠ョ湅鍑猴紝澶ч儴鍒嗘椂鍊?鍙栧喅浜?code>_M_key_compare) sizeof(map<xx>)=48錛屼富瑕佺殑鍏冪礌鏄細(xì)
_Rb_tree_color _M_color; // 鑺傜偣棰滆壊
_Base_ptr _M_parent; // 鐖惰妭鐐?/span>
_Base_ptr _M_left; // 宸﹁妭鐐?/span>
_Base_ptr _M_right; // 鍙寵妭鐐?/span>
_Val _M_value_field // 鍚宭ist涓妭鐐規(guī)妧宸т竴鑷達(dá)紝鍚庨潰鏄疄闄呯殑鍏冪礌鍚宭ist涓殑瀹炵幇涓鑷達(dá)紝map鏈韓浣滀負(fù)涓涓妭鐐癸紝鍏朵笉鏄竴涓瓨鍌ㄦ暟鎹殑鑺傜偣錛?/p>
_Rb_tree::end
iterator
end()
{ return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }鐢變簬鑺傜偣鍊煎湪_Rb_tree_node_base鍚庯紝鎵浠ヤ換鎰忔椂鍊欐嬁鍒拌妭鐐瑰氨鍙互鍋忕Щ榪欎釜緇撴瀯浣撴嬁鍒拌妭鐐瑰鹼紝鑺傜偣鐨勫兼槸涓涓猵air錛屽寘鍚簡(jiǎn)key鍜寁alue銆?/p>
鍦╣db涓墦鍗頒互涓媘ap鐨勫唴瀹癸細(xì)
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 鐪熸鐨勮妭鐐?
0x7fffffffe388: 0x606040
(gdb) x/1xw 0x606040+32+8 # 鍋忕Щ32瀛楄妭鏄妭鐐瑰肩殑鍦板潃錛屽啀鍋忕Щ8鍒欐槸value鐨勫湴鍧
0x606068: 0x00000bbb
(gdb) p *(char**)(0x606040+32) # 鍋忕Щ32瀛楄妭鏄痵tring鐨勫湴鍧
$8 = 0x606028 "abc"
鎴栬呭緢澶氭椂鍊欐病鏈夊繀瑕佽繖涔堣閫?铔嬬柤錛?/p>
(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
瀹?/em>
Kevin Lynx 2014-12-03 22:08 鍙戣〃璇勮
]]>zookeeper閰嶇疆涓洪泦緹ゆā寮忔椂錛屽湪鍚姩鎴栧紓甯告儏鍐墊椂浼?xì)閫変婦鍑轟竴涓疄渚嬩綔涓篖eader銆傚叾榛樿閫変婦綆楁硶涓?code>FastLeaderElection銆?/p>
涓嶇煡閬搝ookeeper鐨勫彲浠ヨ冭檻榪欐牱涓涓棶棰橈細(xì)鏌愪釜鏈嶅姟鍙互閰嶇疆涓哄涓疄渚嬪叡鍚屾瀯鎴愪竴涓泦緹ゅ澶栨彁渚涙湇鍔°傚叾姣忎竴涓疄渚嬫湰鍦伴兘瀛樻湁鍐椾綑鏁版嵁錛屾瘡涓涓疄渚嬮兘鍙互鐩存帴瀵瑰鎻愪緵璇誨啓鏈嶅姟銆傚湪榪欎釜闆嗙兢涓負(fù)浜?jiǎn)淇濊瘉鏁版嵁鐨勪竴鑷存э紝闇瑕佹湁涓涓狶eader鏉ュ崗璋冧竴浜涗簨鍔°傞偅涔堥棶棰樻潵浜?jiǎn)锛?xì)濡備綍紜畾鍝竴涓疄渚嬫槸Leader鍛紵
闂鐨勯毦鐐瑰湪浜庯細(xì)
- 娌℃湁涓涓徊瑁佽呮潵閫夊畾Leader
- 姣忎竴涓疄渚嬫湰鍦板彲鑳藉凡緇忓瓨鍦ㄦ暟鎹紝涓嶇‘瀹氬摢涓疄渚嬩笂鐨勬暟鎹槸鏈鏂扮殑
鍒嗗竷寮忛変婦綆楁硶姝ｆ槸鐢ㄦ潵瑙ｅ喅榪欎釜闂鐨勩?/p>
鏈枃鍩轟簬zookeeper 3.4.6 鐨勬簮鐮佽繘琛屽垎鏋愩侳astLeaderElection綆楁硶鐨勬簮鐮佸叏閮ㄤ綅浜?code>FastLeaderElection.java鏂囦歡涓紝鍏跺澶栨帴鍙ｄ負(fù)FastLeaderElection.lookForLeader錛岃鎺ュ彛鏄竴涓悓姝ユ帴鍙ｏ紝鐩村埌閫変婦緇撴潫鎵嶄細(xì)榪斿洖銆傚悓鏍風(fēng)敱浜庣綉涓婂凡鏈夌被浼兼枃绔狅紝鎵浠ユ垜灝變粠鍥劇ず鐨勮搴︽潵闃愯堪銆傞槄璇諱竴浜涘叾浠栨枃绔犳湁鍒╀簬鑾峰緱鍒濇鍗拌薄錛?/p>
- 娣卞叆嫻呭嚭Zookeeper涔嬩簲 Leader閫変婦錛屼唬鐮佸璇?/li>
- zookeeper3.3.3婧愮爜鍒嗘瀽(浜?FastLeader閫変婦綆楁硶錛屾枃瀛楁弿榪拌緝緇?/li>
涓昏嫻佺▼
闃呰浠ｇ爜鍜屼互涓婃帹鑽愭枃绔犲彲浠ユ妸鏁翠釜嫻佺▼姊崇悊娓呮銆傚疄鐜頒笂錛屽寘鎷簡(jiǎn)涓涓秷鎭鐞嗕富寰幆錛屼篃鏄変婦鐨勪富瑕侀昏緫錛屼互鍙?qiáng)涓涓秷鎭彂閫侀槦鍒楀鐞嗙嚎紼嬪拰娑堟伅瑙ｇ爜綰跨▼銆備富瑕佹祦紼嬪彲姒傛嫭涓轟笅鍥撅細(xì)
鎺ㄨ崘瀵圭収鐫鎺ㄨ崘鐨勬枃绔犲強(qiáng)浠ｇ爜鐞嗚В錛屼笉璧樿堪銆?/p>
鎴戜滑浠庢劅鎬т笂鏉ョ悊瑙ｈ繖涓畻娉曘?/p>
姣忎竴涓妭鐐癸紝鐩稿綋浜庝竴涓夋皯錛屼粬浠兘鏈夎嚜宸辯殑鎺ㄨ崘浜猴紝鏈寮濮嬩粬浠兘鎺ㄨ崘鑷繁銆傝皝鏇撮傚悎鎴愪負(fù)Leader鏈変竴涓畝鍗曠殑瑙勫垯錛屼緥濡俿id澶熷ぇ錛堥厤緗級(jí)銆佹寔鏈夌殑鏁版嵁澶熸柊(zxid澶熷ぇ)銆傛瘡涓夋皯閮藉憡璇夊叾浠栭夋皯鑷繁鐩墠鐨勬帹鑽愪漢鏄皝錛岀被浼間簬鍑哄幓鎼炲浼犳媺鎷㈠叾浠栭夋皯銆傛瘡涓涓夋皯鍙戠幇鏈夋瘮鑷繁鏇撮傚悎鐨勪漢鏃跺氨杞屾帹鑽愯繖涓洿閫傚悎鐨勪漢銆傛渶鍚庯紝澶ч儴鍒嗕漢鎰忚涓鑷存椂錛屽氨鍙互緇撴潫閫変婦銆?/p>
灝辮繖涔堢畝鍗曘傛諱綋涓婃湁涓縐嶄笉鏂紨鍖栭艱繎緇撴灉鐨勬劅瑙夈?/p>
褰撶劧錛屼細(xì)鏈変簺鐗規(guī)畩鎯呭喌鐨勫鐞嗐備緥濡傛誨叡3涓夋皯錛?鍜?宸茬粡紜畾3鏄疞eader錛屼絾3榪樹(shù)笉鐭ユ儏錛屾鏃跺氨璧板叆LEADING/FOLLOWING鐨勫垎鏀紝閫夋皯3鍙槸鎺ユ敹緇撴灉銆?/p>
浠ｇ爜涓笉鏄墍鏈夐昏緫閮藉湪榪欎釜澶ф祦紼嬩腑瀹屾垚鐨勩傚湪鎺ユ敹娑堟伅綰跨▼涓紝榪樺彲鑳藉崟鐙湴鍥炲簲鏌愪釜鑺傜偣(WorkerReceiver.run)錛?/p>
浠庤繖閲屽彲浠ョ湅鍑猴紝褰撴煇涓妭鐐瑰凡緇忕‘瀹氶変婦緇撴灉涓嶅啀澶勪簬LOOKING鐘舵佹椂錛屽叾鏀跺埌LOOKING娑堟伅鏃墮兘浼?xì)鐩存帴鍥炲簲閫変婦鐨勬渶緇堢粨鏋溿傜粨鍚堜笂闈㈤偅涓瘮鏂癸紝鐩稿綋浜庢煇嬈￠変婦緇撴潫浜?jiǎn)锛寴q欎釜鏃跺欐潵浜?jiǎn)閫夋皯4鍙堝彂璧蜂竴嬈℃柊鐨勯変婦錛岄偅涔堝叾浠栭夋皯灝辯洿鎺ュ憡璇夊畠褰撳墠鐨凩eader鎯呭喌銆傜浉褰撲簬錛屽湪榪欎釜闆嗙兢涓諱粠宸茬粡灝辯華鐨勬儏鍐典笅錛屽張寮鍚簡(jiǎn)涓涓疄渚嬶紝榪欎釜瀹炰緥灝變細(xì)鐩存帴浣跨敤褰撳墠鐨勯変婦緇撴灉銆?/p>
鐘舵佽漿鎹?/h2>
姣忎釜鑺傜偣涓婃湁涓浜涘叧閿殑鏁版嵁緇撴瀯錛?/p>
- 褰撳墠鎺ㄨ崘浜猴紝鍒濆鎺ㄨ崘鑷繁錛屾瘡嬈℃敹鍒板叾浠栨洿濂界殑鎺ㄨ崘浜烘椂灝辨洿鏂?/li>
- 鍏朵粬浜虹殑鎶曠エ闆嗗悎錛岀敤浜庣‘瀹氫綍鏃墮変婦緇撴潫
姣忔鎺ㄨ崘浜烘洿鏂版椂灝變細(xì)榪涜騫挎挱錛屾鏄繖涓笉鏂湴騫挎挱椹卞姩鏁翠釜綆楁硶瓚嬪悜浜庣粨鏋溿傚亣璁炬湁3涓妭鐐笰/B/C錛屽叾閮借繕娌℃湁鏁版嵁錛屾寜鐓id鍏崇郴涓篊>B>A錛岄偅涔堟寜鐓ц鍒欙紝C鏇村彲鑳芥垚涓篖eader錛屽叾鍚勪釜鑺傜偣鐨勭姸鎬佽漿鎹負(fù)錛?/p>
鍥句腑錛寁(A)琛ㄧず褰撳墠鎺ㄨ崘浜轟負(fù)A錛況[]琛ㄧず鏀跺埌鐨勬姇紲ㄩ泦鍚堛?/p>
鍙互鐪嬬湅褰撳叾浠栬妭鐐瑰凡緇忕‘瀹氭姇紲ㄧ粨鏋滄椂錛屽嵆涓嶅啀鏄?code>LOOKING鏃剁殑鐘舵侊細(xì)
浠ｇ爜涓湁涓涓壒孌婄殑鎶曠エ闆嗗悎outofelection錛屾垜鐞嗚В涓洪変婦宸茬粨鏉熺殑閭ｄ簺鎶曠エ錛岃繖浜涙姇紲ㄤ粎鐢ㄤ簬琛ㄥ緛閫変婦緇撴灉銆?/p>
褰撲竴涓柊鍚姩鐨勮妭鐐瑰姞鍏ラ泦緹ゆ椂錛屽畠瀵歸泦緹ゅ唴鍏朵粬鑺傜偣鍙戝嚭鎶曠エ璇鋒眰錛岃屽叾浠栬妭鐐瑰凡涓嶅浜?code>LOOKING鐘舵侊紝姝ゆ椂鍏朵粬鑺傜偣鍥炲簲閫変婦緇撴灉錛岃鑺傜偣鏀墮泦榪欎簺緇撴灉鍒?code>outofelection涓紝鏈緇堝湪鏀跺埌鍚堟硶LEADER娑堟伅涓旇繖浜涢夌エ涔熸瀯鎴愰変婦緇撴潫鏉′歡鏃訛紝璇ヨ妭鐐瑰氨緇撴潫鑷繁鐨勯変婦琛屼負(fù)銆?em>娉ㄦ剰鍒頒唬鐮佷腑浼?code>logicalclock = n.electionEpoch;鏇存柊閫変婦杞暟
瀹?/em>
Kevin Lynx 2014-10-19 15:58 鍙戣〃璇勮
]]>Paxos鍗忚/綆楁硶鏄垎甯冨紡緋葷粺涓瘮杈冮噸瑕佺殑鍗忚錛屽畠鏈夊閲嶈鍛紵
<鍒嗗竷寮忕郴緇熺殑浜嬪姟澶勭悊>錛?/p>
Google Chubby鐨勪綔鑰匨ike Burrows璇磋繃榪欎釜涓栫晫涓婂彧鏈変竴縐嶄竴鑷存х畻娉曪紝閭ｅ氨鏄疨axos錛屽叾瀹冪殑綆楁硶閮芥槸孌嬫鍝併?/p>
<澶ц妯″垎甯冨紡瀛樺偍緋葷粺>錛?/p>
鐞嗚В浜?jiǎn)杩欎袱涓垎甯冨紡鍗忚涔嬪?Paxos/2PC)錛屽涔?fàn)鍏朵粬鍒嗗竷寮忓崗璁細(xì)鍙樺緱鐩稿綋瀹规槗銆?/p>
瀛︿範(fàn)Paxos綆楁硶鏈変袱閮ㄥ垎錛歛) 綆楁硶鐨勫師鐞?璇佹槑錛沚) 綆楁硶鐨勭悊瑙?榪愪綔銆?/p>
鐞嗚В榪欎釜綆楁硶鐨勮繍浣滆繃紼嬪叾瀹炲熀鏈氨鍙互鐢ㄤ簬宸ョ▼瀹炶返銆傝屼笖鐞嗚В榪欎釜榪囩▼鐩稿鏉ヨ涔熷鏄撳緱澶氥?/p>
緗戜笂鎴戣寰楄Paxos璁茬殑濂界殑灞炰簬榪欑瘒錛?a >paxos鍥捐В鍙?a >Paxos綆楁硶璇﹁В錛屾垜榪欓噷灝辯粨鍚?a >wiki涓婄殑瀹炰緥榪涗竴姝ラ槓榪般備竴浜沺axos鍩虹閫氳繃榪欓噷鎻愬埌鐨勪袱綃囨枃绔狅紝浠ュ強(qiáng)wiki涓婄殑鍐呭鍩烘湰鍙互鐞嗚В銆?/p>
綆楁硶鍐呭
Paxos鍦ㄥ師浣滆呯殑銆奝axos Made Simple銆嬩腑鍐呭鏄瘮杈冪簿綆鐨勶細(xì)
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鍥捐В鏂囦腑鐨勬祦紼嬪浘鍙鎷負(fù)錛?/p>
瀹炰緥鍙?qiáng)璇﹁?/h2>
Paxos涓湁涓夌被瑙掕壊Proposer銆?code>Acceptor鍙?code>Learner錛屼富瑕佷氦浜掕繃紼嬪湪Proposer鍜?code>Acceptor涔嬮棿銆?/p>
Proposer涓?code>Acceptor涔嬮棿鐨勪氦浜掍富瑕佹湁4綾繪秷鎭氫俊錛屽涓嬪浘錛?/p>
榪?綾繪秷鎭搴斾簬paxos綆楁硶鐨勪袱涓樁孌?涓繃紼嬶細(xì)
- phase 1
- a) proposer鍚戠綉緇滃唴瓚呰繃鍗婃暟鐨刟cceptor鍙戦乸repare娑堟伅
- b) acceptor姝ｅ父鎯呭喌涓嬪洖澶峱romise娑堟伅
- phase 2
- a) 鍦ㄦ湁瓚沖澶歛cceptor鍥炲promise娑堟伅鏃訛紝proposer鍙戦乤ccept娑堟伅
- b) 姝ｅ父鎯呭喌涓媋cceptor鍥炲accepted娑堟伅
鍥犱負(fù)鍦ㄦ暣涓繃紼嬩腑鍙兘鏈夊叾浠杙roposer閽堝鍚屼竴浠朵簨鎯呭彂鍑轟互涓婅姹傦紝鎵浠ュ湪姣忎釜榪囩▼涓兘浼?xì)鏈変簺鐗箤D婃儏鍐靛鐞嗭紝榪欎篃鏄負(fù)浜?jiǎn)杈炬垚涓鑷存ф墍鍋氱殑浜嬫儏銆傚鏋滃湪鏁翠釜榪囩▼涓病鏈夊叾浠杙roposer鏉ョ珵浜夛紝閭ｄ箞榪欎釜鎿嶄綔鐨勭粨鏋滃氨鏄‘瀹氭棤寮傝鐨勩備絾鏄鏋滄湁鍏朵粬proposer鐨勮瘽錛屾儏鍐靛氨涓嶄竴鏍蜂簡(jiǎn)銆?/p>
浠?a >paxos涓枃wiki涓婄殑渚嬪瓙涓轟緥銆傜畝鍗曟潵璇磋渚嬪瓙浠ヨ嫢騫蹭釜璁憳鎻愯紼庢敹錛岀‘瀹氭渶緇堥氳繃鐨勬硶妗堢◣鏀舵瘮渚嬨?/p>
浠ヤ笅鍥句腑鍩烘湰鍙敾鍑簆roposer涓庝竴涓猘cceptor鐨勪氦浜掋傛椂闂存爣蹇桾2鎬繪槸鍦═1鍚庨潰銆俻ropose number綆縐癗銆?/p>
鎯呭喌涔嬩竴濡備笅鍥撅細(xì)
A3鍦═1鍙戝嚭accepted緇橝1錛岀劧鍚庡湪T2鏀跺埌A5鐨刾repare錛屽湪T3鐨勬椂鍊橝1鎵嶉氱煡A5鏈緇堢粨鏋?紼庣巼10%)銆傝繖閲屼細(xì)鏈変袱縐嶆儏鍐碉細(xì)
- A5鍙戞潵鐨凬5灝忎簬A1鍙戝嚭鍘葷殑N1錛岄偅涔圓3鐩存帴鎷掔粷(reject)A5
- A5鍙戞潵鐨凬5澶т簬A1鍙戝嚭鍘葷殑N1錛岄偅涔圓3鍥炲promise錛屼絾甯︿笂A1鐨?N1, 10%)
榪欓噷鍙互涓巔axos嫻佺▼鍥懼搴旇搗鏉ワ紝鏇村ソ鐞嗚В銆?strong>acceptor浼?xì)璁板?MaxN, AcceptN, AcceptV)銆?/p>
A5鍦ㄦ敹鍒皃romise鍚庯紝鍚庣畫(huà)鐨勬祦紼嬪彲浠ラ『鍒╄繘琛屻備絾鏄彂鍑篴ccept鏃訛紝鍥犱負(fù)鏀跺埌浜?AcceptN, AcceptV)錛屾墍浠ヤ細(xì)鍙栨渶澶х殑AcceptN瀵瑰簲鐨凙cceptV錛屼緥瀛愪腑涔熷氨鏄疉1鐨?0%浣滀負(fù)AcceptV銆傚鏋滃湪鏀跺埌promise鏃舵病鏈夊彂鐜版湁鍏朵粬宸茶褰曠殑AcceptV錛屽垯鍏跺煎彲浠ョ敱鑷繁鍐沖畾銆?/p>
閽堝浠ヤ笂A1鍜孉5鍐茬獊鐨勬儏鍐碉紝鏈緇圓1鍜孉5閮戒細(xì)騫挎挱鎺ュ彈鐨勫間負(fù)10%銆?/p>
鍏跺疄4涓繃紼嬩腑瀵逛簬acceptor鑰岃█錛屽湪鍥炲promise鍜宎ccepted鏃剁敱浜庨兘鍙兘鍥犱負(fù)鍏朵粬proposer鐨勪粙鍏ヨ屽鑷寸壒孌婂鐞嗐傛墍浠ュ熀鏈笂鐪嬪湪榪欎袱涓椂闂寸偣鏀跺埌鍏朵粬proposer鐨勮姹傛椂灝卞彲浠ヤ簡(jiǎn)瑙ｆ暣涓畻娉曚簡(jiǎn)銆備緥濡傚湪鍥炲promise鏃跺垯鍙兘鍥犱負(fù)proposer鍙戞潵鐨凬涓嶅澶ц宺eject錛?/p>
濡傛灉鍦ㄥ彂accepted娑堟伅鏃訛紝瀵瑰叾浠栨洿澶鐨刾roposer鍙戝嚭榪噋romise錛岄偅涔堜篃浼?xì)reject璇roposer鍙戝嚭鐨刟ccept錛屽鍥撅細(xì)
榪欎釜瀵瑰簲浜嶱hase 2 b)錛?/p>
it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
鎬葷粨
Leslie Lamport娌℃湁鐢ㄦ暟瀛︽弿榪癙axos錛屼絾鏄粬鐢ㄨ嫳鏂囬槓榪板緱寰堟竻鏅般傚皢Paxos鐨勪袱涓狿hase鐨勫唴瀹圭悊瑙ｆ竻妤氾紝鏁翠釜綆楁硶榪囩▼榪樻槸涓嶅鏉傜殑銆?/p>
鑷充簬Paxos涓竴鐩存彁鍒扮殑涓涓叏灞鍞竴涓旈掑鐨刾roposer number錛屽叾濡備綍瀹炵幇錛屽紩鐢ㄥ涓嬶細(xì)
濡備綍浜х敓鍞竴鐨勭紪鍙峰憿錛熷湪銆奝axos made simple銆嬩腑鎻愬埌鐨勬槸璁╂墍鏈夌殑Proposer閮戒粠涓嶇浉浜ょ殑鏁版嵁闆嗗悎涓繘琛岄夋嫨錛屼緥濡傜郴緇熸湁5涓狿roposer錛屽垯鍙負(fù)姣忎竴涓狿roposer鍒嗛厤涓涓爣璇唈(0~4)錛屽垯姣忎竴涓猵roposer姣忔鎻愬嚭鍐寵鐨勭紪鍙峰彲浠ヤ負(fù)5*i + j(i鍙互鐢ㄦ潵琛ㄧず鎻愬嚭璁鐨勬鏁?
鍙傝冩枃妗?/h2>
- 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
Kevin Lynx 2014-10-15 22:45 鍙戣〃璇勮
]]>鍦ㄤ竴涓垎甯冨紡鐜涓紝鍚岀被鍨嬬殑鏈嶅姟寰寰浼?xì)閮ň|插緢澶氬疄渚嬨傝繖浜涘疄渚嬩嬌鐢ㄤ簡(jiǎn)涓浜涢厤緗紝涓轟簡(jiǎn)鏇村ソ鍦扮淮鎶よ繖浜涢厤緗氨浜х敓浜?jiǎn)閰嵕|鐞嗘湇鍔°傞氳繃榪欎釜鏈嶅姟鍙互杞繪澗鍦扮鐞嗚繖浜涘簲鐢ㄦ湇鍔＄殑閰嶇疆闂銆傚簲鐢ㄥ満鏅彲姒傛嫭涓猴細(xì)
zookeeper鐨勪竴縐嶅簲鐢ㄥ氨鏄垎甯冨紡閰嶇疆綆＄悊(鍩轟簬ZooKeeper鐨勯厤緗俊鎭瓨鍌ㄦ柟妗堢殑璁捐涓庡疄鐜?/a>)銆傜櫨搴︿篃鏈夌被浼肩殑瀹炵幇錛?a >disconf銆?/p>
Diamond鍒欐槸娣樺疂寮婧愮殑涓縐嶅垎甯冨紡閰嶇疆綆＄悊鏈嶅姟鐨勫疄鐜般侱iamond鏈川涓婃槸涓涓狫ava鍐欑殑Web搴旂敤錛屽叾瀵瑰鎻愪緵鎺ュ彛閮芥槸鍩轟簬HTTP鍗忚鐨勶紝鍦ㄩ槄璇諱唬鐮佹椂鍙互浠庡疄鐜板悇涓帴鍙ｇ殑controller鍏ユ墜銆?/p>
鍒嗗竷寮忛厤緗鐞?/h2>
鍒嗗竷寮忛厤緗鐞嗙殑鏈川鍩烘湰涓婂氨鏄竴縐?strong>鎺ㄩ?璁㈤槄妯″紡鐨勮繍鐢ㄣ傞厤緗殑搴旂敤鏂規(guī)槸璁㈤槄鑰咃紝閰嶇疆綆＄悊鏈嶅姟鍒欐槸鎺ㄩ佹柟銆傛鎷負(fù)涓嬪浘錛?/p>
鍏朵腑錛屽鎴風(fēng)鍖呮嫭綆＄悊浜哄憳publish鏁版嵁鍒伴厤緗鐞嗘湇鍔★紝鍙互鐞嗚В涓烘坊鍔?鏇存柊鏁版嵁錛涢厤緗鐞嗘湇鍔otify鏁版嵁鍒拌闃呰咃紝鍙互鐞嗚В涓烘帹閫併?/p>
閰嶇疆綆＄悊鏈嶅姟寰寰浼?xì)灏佽涓涓鎴風(fēng)搴擄紝搴旂敤鏂瑰垯鏄熀浜庤搴撲笌閰嶇疆綆＄悊鏈嶅姟榪涜浜や簰銆傚湪瀹為檯瀹炵幇鏃訛紝瀹㈡埛绔簱鍙兘鏄富鍔ㄦ媺鍙?pull)鏁版嵁錛屼絾瀵逛簬搴旂敤鏂硅岃█錛屼竴鑸槸涓縐嶄簨浠墮氱煡鏂瑰紡銆?/p>
Diamond涓殑鏁版嵁鏄畝鍗曠殑key-value緇撴瀯銆傚簲鐢ㄦ柟璁㈤槄鏁版嵁鍒欐槸鍩轟簬key鏉ヨ闃咃紝鏈闃呯殑鏁版嵁褰撶劧涓嶄細(xì)琚帹閫併傛暟鎹粠綾誨瀷涓婂張鍒掑垎涓鴻仛鍚堝拰闈炶仛鍚堛傚洜涓烘暟鎹帹閫佽呭彲鑳藉緢澶氾紝鍦ㄦ暣涓垎甯冨紡鐜涓紝鍙兘鏈夊涓帹閫佽呭湪鎺ㄩ佺浉鍚宬ey鐨勬暟鎹紝榪欎簺鏁版嵁濡傛灉鏄仛鍚堢殑錛岄偅涔堟墍鏈夎繖浜涙帹閫佽呮帹閫佺殑鏁版嵁浼?xì)琚悎迤堝湪涓璧鳳紱鍙嶄箣濡傛灉鏄潪鑱氬悎鐨勶紝鍒欎細(xì)鍑虹幇瑕嗙洊銆?/p>
鏁版嵁鐨勬潵婧愬彲鑳芥槸浜哄伐閫氳繃綆＄悊绔綍鍏ワ紝涔熷彲鑳芥槸鍏朵粬鏈嶅姟閫氳繃閰嶇疆綆＄悊鏈嶅姟鐨勬帹閫佹帴鍙ｈ嚜鍔ㄥ綍鍏ャ?/p>
鏋舵瀯鍙?qiáng)瀹炵?/h2>
Diamond鏈嶅姟鏄竴涓泦緹わ紝鏄竴涓幓闄や簡(jiǎn)鍗曠偣鐨勫崗浣滈泦緹ゃ傚鍥撅細(xì)
鍥句腑鍙垎涓轟互涓嬮儴鍒嗚瑙ｏ細(xì)
鏈嶅姟涔嬮棿鍚屾
Diamond鏈嶅姟闆嗙兢姣忎竴涓疄渚嬮兘鍙互瀵瑰瀹屾暣鍦版彁渚涙湇鍔★紝閭ｄ箞鎰忓懗鐫姣忎釜瀹炰緥涓婇兘鏈夋暣涓泦緹ょ淮鎶ょ殑鏁版嵁銆侱iamond鏈変袱縐嶆柟寮忎繚璇佽繖涓鐐癸細(xì)
- 浠諱綍涓涓疄渚嬮兘鏈夊叾浠栧疄渚嬬殑鍦板潃錛涗換浣曚竴涓疄渚嬩笂鐨勬暟鎹彉鏇存椂錛岄兘浼?xì)灏嗘敼鍙樼殑鏁版嵁鍚屾鍒癿ysql涓婏紝鐒跺悗閫氱煡鍏朵粬鎵鏈夊疄渚嬩粠mysql涓婅繘琛屼竴嬈℃暟鎹媺鍙?
DumpService::dump)錛岃繖涓繃紼嬪彧鎷夊彇鏀瑰彉?shù)簡(jiǎn)鐨勬暟鎹?/li> - 浠諱綍涓涓疄渚嬪惎鍔ㄥ悗閮戒細(xì)浠ヨ緝闀跨殑鏃墮棿闂撮殧錛堝嚑灝忔椂錛夛紝浠巑ysql榪涜涓嬈″叏閲忕殑鏁版嵁鎷夊彇(
DumpAllProcessor)
瀹炵幇涓婁負(fù)浜?jiǎn)涓鑷存э紝閫氱煡鍏朵粬瀹炰緥瀹為檯涓婁篃鍖呭惈鑷繁銆備互鏈嶅姟鍣ㄦ敹鍒版坊鍔犺仛鍚堟暟鎹負(fù)渚嬶紝澶勭悊榪囩▼澶ц嚧涓猴細(xì)
DatumController::addDatum // /datum.do?method=addDatum
PersistService::addAggrConfigInfo
MergeDatumService::addMergeTask // 娣誨姞涓涓狹ergeDataTask錛屽紓姝ュ鐞?
MergeTaskProcessor::process
PersistService::insertOrUpdate
EventDispatcher.fireEvent(new ConfigDataChangeEvent // 媧懼彂涓涓狢onfigDataChangeEvent浜嬩歡
NotifyService::onEvent // 鎺ユ敹浜嬩歡騫跺鐞?
TaskManager::addTask(..., new NotifyTask // 鐢辨錛屽綋鏁版嵁鍙戠敓鍙樺姩錛屽垯鏈緇堝垱寤轟簡(jiǎn)涓涓狽oticyTask
// NotifyTask鍚屾牱寮傛澶勭悊
NotifyTaskProcessor::process
foreach server in serverList // 鍖呭惈鑷繁
notifyToDump // 璋冪敤 /notify.do?method=notifyConfigInfo 浠巑ysql鏇存柊鍙樺姩鐨勬暟鎹?
铏界劧Diamond鍘婚櫎浜?jiǎn)鍗曠倸w棶棰橈紝涓嶈繃闂閮戒笅闄嶅埌浜?jiǎn)mysql涓娿備絾鐢變簬鍏朵綔涓洪厤緗鐞嗙殑瀹氫綅錛屽叾鏁版嵁閲忓氨mysql鐨勫簲鐢ㄨ岃█綆楀皬鐨勪簡(jiǎn)錛屾墍浠ュ彲浠ヤ竴瀹氱▼搴︿笂淇濊瘉鏁翠釜鏈嶅姟鐨勫彲鐢ㄦс?/p>
鏁版嵁涓鑷存?/h3>
鐢變簬Diamond鏈嶅姟鍣ㄦ病鏈塵aster錛屼換浣曚竴涓疄渚嬮兘鍙互璇誨啓鏁版嵁錛岄偅涔堥拡瀵瑰悓涓涓猭ey鐨勬暟鎹垯鍙兘闈復(fù)鍐茬獊銆傝繖閲屽簲璇ユ槸閫氳繃mysql鏉ヤ繚璇佹暟鎹殑涓鑷存с傛瘡涓嬈″鎴風(fēng)璇鋒眰鍐欐暟鎹椂錛孌iamond閮藉皢鍐欒姹傛姇閫掔粰mysql錛岀劧鍚庨氱煡闆嗙兢鍐呮墍鏈塂iamond瀹炰緥錛堝寘鎷嚜宸憋級(jí)浠巑ysql鎷夊彇鏁版嵁銆傚綋鐒?dòng)灱屾媺鍙栨暟鎹垯鍙兘涓嶆槸姣忎竴嬈″啓鍏ラ兘鑳芥媺鍑烘潵錛屼篃灝辨槸鏈緇堜竴鑷存с?/p>
Diamond涓病鏈夋妸鏁版嵁鏀懼叆鍐呭瓨錛屼絾浼?xì)鏀惧埌鏈湴鏂囦欢銆傚浜庡鎴風(fēng)鐨勮鎿嶄綔鑰岃█錛屽垯鏄洿鎺ヨ繑鍥炴湰鍦版枃浠墮噷鐨勬暟鎹?/p>
鏈嶅姟瀹炰緥鍒楄〃
Diamond鏈嶅姟瀹炰緥鍒楄〃鏄竴浠介潤(rùn)鎬佹暟鎹紝鐩存帴灝嗘瘡涓疄渚嬬殑鍦板潃瀛樻斁鍦ㄤ竴涓獁eb server涓娿傛棤璁烘槸Diamond鏈嶅姟榪樻槸瀹㈡埛绔兘浠庤web server涓婂彇鍑哄疄渚嬪垪琛ㄣ?/p>
瀵逛簬瀹㈡埛绔岃█錛屽綋鍏跺彇鍑轟簡(jiǎn)璇ュ垪琛ㄥ悗錛屽垯鏄殢鏈洪夋嫨涓涓妭鐐?ServerListManager.java)錛屼互鍚庣殑璇鋒眰閮戒細(xì)鍙戝線璇ヨ妭鐐廣?/p>
鏁版嵁鍚屾
瀹㈡埛绔簱涓互鍥哄畾鏃墮棿闂撮殧浠庢湇鍔″櫒鎷夊彇鏁版嵁(ClientWorker::ClientWorker錛?code>ClientWorker::checkServerConfigInfo)銆傚彧鏈夊簲鐢ㄦ柟鍏沖績(jī)鐨勬暟鎹墠鍙兘琚媺鍙栥傚彟澶栵紝涓轟簡(jiǎn)鏁版嵁鎺ㄩ佺殑鍙?qiáng)鏃跺Q孌iamond榪樹(shù)嬌鐢ㄤ簡(jiǎn)涓縐峫ong polling鐨勬妧鏈紝鍏跺疄涔熸槸涓轟簡(jiǎn)紿佺牬HTTP鍗忚鐨勫眬闄愭с?em>濡傛灉鏁翠釜鏈嶅姟鏄熀浜嶵CP鐨勮嚜瀹氫箟鍗忚錛屽鎴風(fēng)涓庢湇鍔″櫒淇濇寔闀胯繛鎺ュ垯娌℃湁榪欎簺闂銆?/p>
鏁版嵁鐨勫彉鏇?/h3>
Diamond涓緢澶氭搷浣滈兘浼?xì)妫鏌ユ暟鎹槸鍚﹀彂鐢熶簡(jiǎn)鍙樺寲銆傛爣璇嗘暟鎹彉鍖栧垯鏄熀浜庢暟鎹搴旂殑MD5鍊兼潵瀹炵幇鐨勩?/p>
瀹圭伨
鍦ㄦ暣涓狣iamond緋葷粺涓紝鍑犱釜瑙掕壊涓轟簡(jiǎn)鎻愰珮瀹圭伨鎬э紝閮芥湁鑷繁鐨勭紦瀛橈紝姒傛嫭涓轟笅鍥撅細(xì)
姣忎竴涓鑹插嚭闂鏃訛紝閮藉彲浠ュ敖閲忎繚璇佸鎴風(fēng)瀵瑰簲鐢ㄥ眰鎻愪緵鏈嶅姟銆?/p>
鍙傝冩枃妗?/h2>
Kevin Lynx 2014-10-12 12:57 鍙戣〃璇勮
]]>