之前在公叔Rl护了一个名字服务，q个名字服务日常理了近4000台机器，?000个左右的客户端连接上来获取机器信息，׃其基本是一个单Ҏ(gu)务，所以某些模块接q瓶颈。后来倒是有重构计划，详细设计做了Q代码都写了一部分Q结果由于某些原因重构就被终止了?/p>
JCM是我业余旉用Java重写的一个版本，功能上目前只实现了基功能。由于它是个完全分布式的架构Q所以理Z可以横向扩展Q大大增强系l的服务能力?/p>
名字服务
在分布式pȝ中，某个服务Z提升整体服务能力Q通常部v了很多实例。这里我把这些提供相同服务的实例l称为集?cluster)Q每个实例称Z个节?Node)。一个应用可能会(x)使用很多clusterQ每ơ访问一个clusterӞ通过名字服务获取该cluster下一个可用的node。那么，名字服务臛_需要包含的功能Q?/p>
- Ҏ(gu)cluster名字获取可用的node
- 对管理的所有cluster下的所有nodeq行健康度的，以保证始l返回可用的node
有些名字服务仅对node理Q不参与应用与node间的通信Q而有些则可能作ؓ(f)应用与node间的通信转发器。虽然名字服务功能简单，但是要做一个分布式的名字服务还是比较复杂的Q因为数据一旦分布式了，׃(x)存在同步、一致性问题的考虑{?/p>
What’s JCM
JCM围绕前面说的名字服务基础功能实现。包含的功能Q?/p>
- 理cluster到node的映?/li>
- 分布式架构，可水qx展以实现理10,000个node的能力，以理一般公司的后台服务集群
- Ҏ(gu)个nodeq行健康查，健康查可ZHTTP协议层的或TCPq接?/li>
- 持久化cluster/node数据Q通过zookeeper保证数据一致?/li>
- 提供JSON HTTP API理cluster/node数据Q后l可提供Web理pȝ
- 以库的Ş式提供与server的交互，库本w提供各U负载均衡策略，保证对一个cluster下node的访问达到负载均?/li>
目地址git jcm
JCM主要包含两部分：(x)
- jcm.serverQJCM名字服务Q需要连接zookeeper以持久化数据
- jcm.subscriberQ客L(fng)库，负责与jcm.server交互Q提供包装了负蝲均衡的APIl应用?/li>
架构
ZJCM的系l整体架构如下：(x)
cluster本n是不需要依赖JCM的，要通过JCM使用q些clusterQ只需要通过JCM HTTP API注册q些cluster到jcm.server上。要通过jcm.server使用q些clusterQ则是通过jcm.subscriber来完成?/p>
使用
可参?a >git READMe.md
需要jre1.7+
- 启动zookeeper
- 下蝲jcm.server git jcm.server-0.1.0.jar
- ?code>jcm.server-0.1.0.jar目录下徏?code>config/application.properties文gq行配置Q参?a >config/application.properties
-
启动jcm.server
java -jar jcm.server-0.1.0.jar -
注册需要管理的集群Q参考cluster描述Q?a >doc/cluster_sample.jsonQ通过HTTP API注册Q?/p>
curl -i -X POST http://10.181.97.106:8080/c -H "Content-Type:application/json" --data-binary @./doc/cluster_sample.json
部v好了jcm.serverQƈ注册了cluster后，可以通过jcm.subscriber使用Q?/p>
// 传入需要用的集群名hello9/helloQ以?qing)传入jcm.server地址Q可以多个：(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名字获取可用的node
System.out.println(rr.alloc("hello9", ProtoType.HTTP));
}
subscriber.shutdown();JCM实现
JCM目前的实现比较简单，参考模块图Q?/p>
- modelQ即cluster/nodeq些数据l构的描qͼ同时被jcm.server和jcm.subscriber依赖
- storageQ持久化数据到zookeeperQ同时包含jcm.server实例之间的数据同?/li>
- health checkQ健h查模块，对各个nodeq行健康?/li>
以上模块都不依赖SpringQ基于以上模块又有：(x)
- http apiQ用spring-mvcQ包装了一些JSON HTTP API
- ApplicationQ基于spring-bootQ将各个基础模块l装hQ提供standalone的模式启动，不用部v到tomcat之类的servlet容器?/li>
jcm.subscriber的实现更单，主要是负责与jcm.serverq行通信Q以更新自己当前的model层数据，同时提供各种负蝲均衡{略接口Q?/p>
- subscriberQ与jcm.server通信Q定期增量拉取数?/li>
- node allocatorQ通过listener方式从subscriber中获取数据，同时实现各种负蝲均衡{略Q对外统一提供
alloc node的接?/li>
接下来看看关键功能的实现
数据同步
既然jcm.server是分布式的，每一个jcm.server instance(实例)都是支持数据d写的Q那么当jcm.server理着一堆cluster上万个nodeӞ每一个instance是如何进行数据同步的Qjcm.server中的数据主要有两c：(x)
- cluster本n的数据，包括cluster/node的描qͼ例如cluster name、node IP、及(qing)其他附属数据
- node健康查的数据
对于cluster数据Q因为cluster对node的管理是一个两层的?wi)状l构Q而对cluster有增删node的操作，所以ƈ不能在每一个instance上都提供真正的数据写入，q样?x)导致数据丢失。假讑一时刻在instance A和instance B上同时对cluster c1d节点N1和N2Q那么instance A写入c1(N1)Q而instance Bq没{到数据同步写入c1(N2)Q那么c1(N1)p覆盖为c1(N2)Q从而导致添加的节点N1丢失?/p>
所以，jcm.server instance是分?code>leader?code>follower的，真正的写入操作只有leaderq行Qfollower收到写操作请求时转发lleader。leader写数据优先更新内存中的数据再写入zookeeperQ内存中的数据更新当然是需要加锁互斥的Q从而保证数据的正确性?/p>
leader和follower是如何确定角色的Q这个很单，标准的利用zookeeper来进行主?a >选D的实?/a>?/p>
jcm.server instance数据间的同步是基于zookeeper watch机制的。这个可以算做是一个JCM的一个瓶颈，每一个instance都会(x)作ؓ(f)一个watchQ得实际上jcm.serverq不能无限水qx展，扩展C定程度后Qwatch的效率就可能不以满x能了，参?a >zookeeper节点Cwatch的性能试 (那个时候我在考虑Ҏ(gu)们系l的重构? ?/p>
jcm.server中对node健康查的数据采用同样的同步机Ӟ但node健康查数据是每一个instance都会(x)写入的，下面看看jcm.server是如何通过分布式架构来分担压力的?/p>
健康?/h3>
jcm.server的另一个主要功能的是对node的健h查，jcm.server集群可以理几万的nodeQ既然已l是分布式了Q那么显然是要把node均分到多个instance的。这里我是以cluster来分配的Q方法就是简单的使用一致性哈希。通过一致性哈希，军_一个cluster是否属于某个instance负责。每个instance都有一个server specQ也是该instance对外提供服务的地址(IP+port)Q这样在M一个instance上，它看到的所有instance server spec都是相同的，从而保证在每一个instance上计cluster的分配得到的l果都是一致的?/p>
健康查按cluster划分Q可以简化数据的写冲H问题，在正常情况下Q每个instance写入的健h查结果都是不同的?/p>
健康查一般以1U的频率q行Qjcm.server做了优化Q当查结果和上一ơ一hQƈ不写入zookeeper。写入的数据包含了node的完整key (IP+Port+Spec)Q这样可以简化很多地方的数据同步问题Q但?x)增加写入数据的大小Q写入数据的大小是会(x)影响zookeeper的性能的，所以这里简单地Ҏ(gu)据进行了压羃?/p>
健康查是可以支持多种查实现的Q目前只实现了HTTP协议层的查。健h查自w是单个U程Q在该线E中Z异步HTTP库，发v异步hQ实际的h在其他线E中发出?/p>
jcm.subscriber通信
jcm.subscriber与jcm.server通信Q主要是Z获取最新的cluster数据。subscriber初始化时?x)拿C个jcm.server instance的地址列表Q访问时使用轮询{略以^衡jcm.server在处理请求时的负载。subscriber每秒都会(x)h一ơ数据，h中描qC本次h惌取哪些cluster数据Q同时携带一个cluster的version。每ơcluster在server变更Ӟversion变_(d)旉戻I。server回复hӞ如果version已最斎ͼ只需要回复node的状态?/p>
subscriber可以拿到所有状态的nodeQ后面可以考虑只拿正常状态的nodeQ进一步减数据大?/p>
压力试
目前只对健康查部分做了压，详细参?a >test/benchmark.md。在A7服务器上试Q发现写zookeeper?qing)zookeeper的watch以满要求Qjcm.server发v的HTTPh是主要的性能热点Q单jcm.server instance大概可以承蝲20000个node的健L(fng)?/p>
|络带宽Q?/p>
1 2 3 4 5 |
|
CPUQ通过jstack查看主要的CPU消耗在HTTP库实现层Q以?qing)健h查线E：(x)
1 2 3 4 |
|
代码中增加了些状态监控：(x)
1
|
|
表示q_每次查耗时542毫秒Q写数据因ؓ(f)开启了cache没有参考h(hun)倹{?/p>
虽然q可以从我自q代码中做不少优化Q但既然单机可以承蝲20000个节点的，一般的应用q远_了?/p>
ȝ
名字服务在分布式pȝ中虽然是基础服务Q但往往承担了非帔R要的角色Q数据同步出现错误、节点状态出现瞬时的错误Q都可能Ҏ(gu)套系l造成较大影响Q业务上出现较大故障。所以名字服务的健壮性、可用性非帔R要。实C需要考虑很多异常情况Q包括网l不E_、应用层的错误等。ؓ(f)了提高够的可用性，一般还?x)加多层的数据cacheQ例如subscriber端的本地cacheQserver端的本地cacheQ以保证在Q何情况下都不?x)媄响应用层的服务?/p>
Kevin Lynx 2015-07-04 17:50 发表评论
]]>接上?a >使用RCU技术实现读写线E无?/a>Q在没有GC机制的语a中，要实现Lock free的算法，免不了要自己处理内存回收的问题?/p>
Hazard Pointer是另一U处理这个问题的法Q而且相比h不但单，功能也很强大?a >锁无关的数据l构与Hazard指针中讲得很好，Wikipedia Hazard pointer也描q得比较清楚Q所以我q里׃讲那么细了?/p>
一个简单的实现可以参?a >我的github haz_ptr.c
原理
基本原理无非也是ȝE对指针q行标识Q指?指向的内?要释放时都会(x)~存h延迟到确认没有读U程了才对其真正释放?/p>
<Lock-Free Data Structures with Hazard Pointers>中的描述Q?/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 pointerQ一个读U程要用一个指针时Q就?x)创Z个Hazard pointer包装q个指针。一个Hazard pointer?x)被一个线E写Q多个线E读?/p>
struct HazardPointer {
void *real_ptr; // 包装的指?/span>
... // 不同的实现有不同的成?/span>
};
void func() {
HazardPointer *hp = accquire(_real_ptr);
... // use _real_ptr
release(hp);
}Thread Free ListQ每个线E都有一个这L(fng)列表Q保存着要释放的指针列表，q个列表仅对应的U程d
void defer_free(void *ptr) {
_free_list.push_back(ptr);
}当某个线E要试释放Free List中的指针Ӟ例如指针ptrQ就查所有其他线E用的Hazard pointerQ检查是否存在包装了ptr的Hazard pointerQ如果没有则说明没有ȝE正在?code>ptrQ可以安全释?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
}
}以上Q其实就?code>Hazard Pointer的主要内宏V?/p>
Hazard Pointer的管?/h2>
上面的代码中没有提到_all_hazard_pointers?code>accquire的具体实玎ͼq就是Hazard Pointer的管理问题?/p>
《锁无关的数据结构与Hazard指针》文中创Z一个Lock free的链表来表示q个全局的Hazard Pointer List。每个Hazard Pointer有一个成员标识其是否可用。这个List中也׃存了已经被用的Hazard Pointer集合和未被用的Hazard Pointer集合Q当所有Hazard Pointer都被使用Ӟ׃(x)新分配一个加q这个List。当ȝE不使用指针Ӟ需要归qHazard PointerQ直接设|可用成员标识即可。要gc()Ӟq接遍历这个List?/p>
要实C个Lock free的链表，q且仅需要实现头插入Q还是非常简单的。本wHazard Pointer标识某个指针Ӟ都是用了后立x识，所以这个实现直接支持了动态线E，支持U程的挂L(fng)?/p>
?a >nbds目中也有一个Hazard Pointer的实玎ͼ相对要弱一炏V它为每个线E都讄了自qHazard Pointer池，写线E要释放指针Ӟp问所有其他线E的Hazard Pointer池?/p>
typedef struct haz_local {
// Free List
pending_t *pending; // to be freed
int pending_size;
int pending_count;
// Hazard Pointer 池，动态和静态两U?/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] = {};每个U程当然涉?qing)?code>haz_local_索引(ID)的分配，像使用RCU技术实现读写线E无?/a>中的一栗这个实Cؓ(f)了支持线E动态创建，需要一套线EID的重用机Ӟ相对复杂多了?/p>
最后，附上一些ƈ行编E中的一些概c(din)?/p>
常常看到附录
Lock Free & Wait Free
Lock Free?code>Wait Free的概念，q些概念用于衡量一个系l或者说一D代码的q行U别Qƈ行别可参?a >q行~程——q发U别
我自q理解Q例如《锁无关的数据结构与Hazard指针》中实现的Hazard Pointer链表可以说是Lock Free的，注意它在插入新元素到链表头时Q因Z?code>CASQd不了一个busy loopQ有q个特征的情况下q?code>Lock FreeQ虽然没锁，但某个线E的执行情况也受其他U程的媄响?/p>
相对而言Q?code>Wait Free则是每个U程的执行都是独立的Q例如《锁无关的数据结构与Hazard指针》中?code>Scan函数?code>“每个U程的执行时间都不依赖于其它MU程的行?#8221;
锁无?Lock-Free)意味着pȝ中d在某个线E能够得以l执行；而等待无?Wait-Free)则是一个更强的条gQ它意味着所有线E都能往下进行?/p>
ABA问题
在实?code>Lock Free法的过E中QL要?code>CAS原语的，?code>CAS׃(x)带来ABA问题?/p>
在进行CAS操作的时候，因ؓ(f)在更改V之前QCAS主要询问“V的值是否仍然ؓ(f)A”Q所以在W一ơ读取V之后以及(qing)对V执行CAS操作之前Q如果将gA改ؓ(f)BQ然后再改回AQ会(x)使基于CAS的算法乱。在q种情况下，CAS操作?x)成功。这c问题称为ABA问题?/p>
Wiki Hazard Pointer提到了一个ABA问题的好例子Q在一个Lock free的栈实现中，现在要出栈，栈里的元素是[A, B, C]Q?code>head指向栈顶Q那么就?code>compare_and_swap(target=&head, newvalue=B, expected=A)。但是在q个操作中，其他U程?code>A B都出栈，且删除了BQ又?code>A压入栈中Q即[A, C]。那么前一个线E的compare_and_swap能够成功Q此?code>head指向了一个已l被删除?code>B。stackoverflow上也有个例子 Real-world examples for ABA in multithreading
对于CAS产生的这个ABA问题Q通常的解x案是采用CAS的一个变UDCAS。DCASQ是对于每一个V增加一个引用的表示修改ơ数的标记符。对于每个VQ如果引用修改了一ơ，q个计数器就?。然后再q个变量需要update的时候，同时检查变量的值和计数器的倹{?/p>
但也早有人提?code>DCAS也不?a >ABA problem 的银?/a>?/p>
Kevin Lynx 2015-05-03 20:46 发表评论
]]>现象
U上的服务出现coredumpQ堆栈ؓ(f)Q?/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
...
查看了应用层相关数据l构Q基本数据都是没有问题的。所以最初怀疑是tcmalloc内部l护了错误的内存Q在分配内存时出错，q个堆栈只是问题的表象。几天后Q线上的另一个服务，Z同样的库Q也core了，堆栈q是一L(fng)?/p>
最初定位问题都是从最q更新的东西入手Q包括依赖的server环境Q但都没有明昄问题Q所以最后只能从core的直接原因入手?/p>
分析GetStackTrace
认core的详l位|：(x)
# core在该指o(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]处读取内容，然后出错Q这个内存单元不可读。但是具体这个指令在代码中是什么意思，需要将q个指o(h)对应C码中。获取tcmalloc的源码，发现GetStackTraceҎ(gu)~译选项有很多实玎ͼ所以这里选择最可能的实玎ͼ然后Ҏ(gu)汇编以确认代码是否匹配。最初选择的是stacktrace_x86-64-inl.hQ后来发现完全不匚wQ又选择?code>stacktrace_x86-inl.h。这个实现版本里也有?4位^台的支持?/p>
stacktrace_x86-inl.h里用了一些宏来生成函数名和参敎ͼ_后代码大概ؓ(f)Q?/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是一个模板函敎ͼ包含一大堆代码Q精后非常简单：(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;
}上面q个代码到汇~的Ҏ(gu)q程q是׃些时_(d)其中汇编中出现的一些常量可以大大羃短对比时_(d)例如上面出现?code>100000Q汇~中有Q?/p>
0x000000000045d176 <_Z13GetStackTracePPvii+70>: cmp $0x186a0,%rbx # 100000=0x186a0
注意NextStackFrame中的 if (STRICT_UNWINDING)使用的是模板参数Q这D生成的代码中Ҏ(gu)没有else部分Q也没?code>1000000q个帔R
在对比代码的q程中，可以知道关键的几个寄存器、内存位|对应到代码中的变量Q从而可以还原core时的现场环境。分析过E中不一定要从第一行汇~读Q可以从较明昄位置读，从而还原整个代码，函数q回指o(h)、蟩转指令、比较指令、读内存指o(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 # 关键位置Q?(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_spQ这里已l是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 存储了返回|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)# 关键位置Qresult[n] = *(sp+1)
0x000000000045d191 <_Z13GetStackTracePPvii+97>: jmp 0x45d15f <_Z13GetStackTracePPvii+47>
分析q程比较耗时Q同时还可以分析?code>GetStackTrace函数的实现原理，其实是利用RBP寄存器不断回溯，从而得到整个调用堆栈各个函数的地址Q严格来说是q回地址Q。简单示意下函数调用中RBP的情况：(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
MQ?strong>一般情况下QQ何一个函CQRBP寄存器指向了当前函数的栈基址Q该栈基址中又存储了调用者的栈基址Q同时该栈基址前面q存储了调用者的q回地址。所以，GetStackTrace的实玎ͼ单来说大概就是：(x)
sp = rbp // 取得当前函数GetStackTrace的栈基址
while (n < max_depth) {
new_sp = *sp
result[n] = *(new_sp+1)
n++
}以上Q最l就知道了以下关键信息：(x)
- r8 对应变量 nQ表C当前取到第几个栈?/li>
- rax 对应变量 spQ代码core?*(sp+1)
- rdi 对应变量 resultQ用于存储取得的各个地址
然后可以看看现场是怎样的：(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
结Q?/strong>
GetStackTrace在取调用__conhash_get_rbnode的函数时出错Q取得了5个函数地址。当前用的RBP?code>0x4e73aa58?/p>
错误的RBP
RBP也是从堆栈中取出来的Q既然这个地址有问题，首先惛_的就是有代码局部变?数组写越界。例?code>sprintf的用。而且Q?strong>一般写界破坏堆栈Q都可能是把调用者的堆栈破坏?/strong>Q例如：(x)
char s[32];
memcpy(s, p, 1024);
因ؓ(f)写入都是从低地址往高地址写，而调用者的堆栈在高地址。当Ӟ也会(x)遇到写坏调用者的调用者的堆栈Q也是跨栈帧越界写Q例如以前遇到的Q?/p>
len = vsnprintf(buf, sizeof(buf), fmt, wtf-long-string);
buf[len] = 0;
__conhash_get_rbnode的RBP是在tcmalloc的堆栈中取的Q?/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)怀疑是tcmallocq个函数里有把堆栈破坏，q个时候就是读代码Q看看有没有疑似危险的地方，未果。这里就陷入了僵局Q怀疑又遇到了跨栈破坏的情况，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);
...q段代码最l发现是没有问题的，q里又耗费了不时间。后来发现若q个函数里的RBP都有点奇怪，q个调用栈比较正常的范围是：(x)0x4e738c90
(gdb) f 8
#8 0x00007f75532cd4c2 in __conhash_get_rbnode (node=0x22c86870, hash=30)
(gdb) p/x $rbp
$6 = 0x4e73aa58 # q个q不特别可?
(gdb) f 9
#9 0x00007f75532cd76e in __conhash_add_replicas (conhash=0x24fbc7e0, iden=<value optimized out>)
(gdb) p/x $rbp
$7 = 0x4e738c60 # q个也不特别可?
(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
Z么很多函CRBP都看h不正常？ 想了想真要是代码里把堆栈破坏了，q错误得发生得多巧妙Q?/p>
错误RBP的来?/h2>
然后转机来了Q脑中H然闪出-fomit-frame-pointer。编译器生成的代码中是可以不需要栈基址指针的，也就是RBP寄存器不作ؓ(f)栈基址寄存器。大部分函数或者说开启了frame-pointer的函敎ͼ其函数头都会(x)有以下指令：(x)
push %rbp
mov %rsp,%rbp
...
表示保存调用者的栈基址到栈中，以及(qing)讄自己的栈基址。看?code>__conhashpd函数Q?/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)
...
q个库是单独~译的，没有昄指定-fno-omit-frame-pointerQ查?a >gcc手册Qo2优化是开启了omit-frame-pinter 的?/p>
在没有RBP的情况下Qtcmalloc?code>GetStackTrace试读RBP取获取调用返回地址Q自然是有问题的。但是，如果整个调用栈中的函敎ͼ要么有RBPQ要么没有RBPQ那?code>GetStackTrace取出的结果最多就是蟩q一些栈帧，不会(x)出错?/strong> 除非Q这中间的某个函数把RBP寄存器另作他用（~译器省个寄存器肯定是要另作他用的）。所以这里l追查这个错误地址 来源已经比较明显Q肯定是 q里打印RSI寄存器的值可能会(x)被误|因ؓ(f)M时候打印寄存器的值可能都是错的，除非它有被显CZ存。不q这里可以看出RSI的值来源于参数(RSI对应W二个参?Q?/p>
q到 扑ֈ?code>0x4e73aa58的来源。这个地址值竟然是一个字W串哈希法出来的Q这里还可以看看q个字符串的内容Q?/p>
q个堡的哈希函数是 以上Q既然只要某个库 有了以上条gQ才使得q个core几率变得很低?/p>
最后，如果你很熟?zhn)tcmallocQ整个问题估计就被秒解了Q?a >tcmalloc INSTALL 另外附上另一个有意思的东西?/p>
在分?code>__conhash_add_replicasӞ其内定义了一?4字节的字W数l，查看其堆栈：(x) 最开始我觉得0x4e73aa58的来源?/p>
__conhash_get_rbnode中设|的Q因个函数的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 # 改写了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> # 调用tcmallocQ汇~到q里卛_
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值由一个字W串哈希函数计算
if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
{
util_rbtree_node_t* rbnode = __conhash_get_rbnode(node, hash); // hash?/span>
...__conhash_add_replicasQ?/p>
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
(gdb) x/1s $rsp
0x4e738bd0: "conhash-00000-00133"
conhash_hash_def?/p>
coredump的条?/h2>
omit-frame-pointerQ那tcmalloc可能出错，Z么发生的频率q不高呢Q这个可以回?code>GetStackTrace其?code>NextStackFrame的实玎ͼ其中包含了几个合法RBP的判定：(x)if (new_sp <= old_sp) return NULL; // 上一个栈帧的RBP肯定比当前的?/span>
if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL; // 指针D围还必须?00000?/span>
...
if ((uintptr_t)new_sp & (sizeof(void *) - 1)) return NULL; // ׃本n保存的是指针Q所以还必须是sizeof(void*)的整数倍，寚wȝ
?/h2>
(gdb) x/20a $rsp
0x4e738bd0: 0x2d687361686e6f63 0x30302d3030303030 # q些是字W串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字节Q也是整个[0x4e738bd0, 0x4e738c10)内存Q但是这块内存里居然有函数地址Q这一度我怀疑这里有问题。后来醒(zhn)这些地址是定?code>buf前调?code>__conhash_create_node产生的，调用q程中写到堆栈里Q调用完后栈指针改变Q但q不需要清I栈中的内容?/p>
Kevin Lynx 2015-04-06 18:33 发表评论]]>
有时候在U上使用gdb调试E序core问题Ӟ可能没有W号文gQ拿到的仅是一个内存地址Q如果这个指向的是一个STL对象Q那么如何查看这个对象的内容呢？
只需要知道STL各个容器的数据结构实玎ͼ可以查看其内容。本文描qCSGI STL实现中常用容器的数据l构Q以?qing)如何在gdb中查看其内容?/p>
string
stringQ即basic_string bits/basic_string.hQ?/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卻Istring内有一个指针，指向实际的字W串位置Q这个位|前面有一?code>_Repl构Q其内保存了字符串的长度、可用内存以?qing)引用计数。当我们拿到一个string对象的地址Ӟ可以通过以下代码获取相关|(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();
}在gdb中拿C个string的地址Ӟ可以以下打印字符串及(qing)长度Q?/p>
(gdb) x/1a p
0x7fffffffe3a0: 0x606028
(gdb) p (char*)0x606028
$2 = 0x606028 "hello"
(gdb) x/1dg 0x606028-24
0x606010: 5
vector
众所周知vector实现是一块连l的内存Q?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>)=24Q其内也是3个指针，_M_start指向首元素地址Q?code>_M_finish指向最后一个节?1Q?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()); }可以通过代码从一个vector对象地址输出其信息：(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输出一个vector中的内容Q?/p>
(gdb) p p
$3 = (void *) 0x7fffffffe380
(gdb) x/1a p
0x7fffffffe380: 0x606080
(gdb) x/3xw 0x606080
0x606080: 0x00000011 0x00000022 0x00000033
list
众所周知list被实Cؓ(f)一个链表。准来说是一个双向链表。list本n是一个特D节点，其代表endQ其指向的下一个元素才是list真正的第一个节点：(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>)=16Q两个指针。每一个真正的节点首先是包含两个指针，然后是元素内?_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();
}在gdb中可以以下方式遍历该listQ?/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使用的是U黑?wi)实玎ͼ实际使用的?code>stl_tree.h实现Q?/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>)=48Q主要的元素是：(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 // 同list中节Ҏ(gu)巧一_(d)后面是实际的元素同list中的实现一_(d)map本n作ؓ(f)一个节点，其不是一个存储数据的节点Q?/p>
_Rb_tree::end
iterator
end()
{ return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }׃节点值在_Rb_tree_node_base后，所以Q意时候拿到节点就可以偏移q个l构体拿到节点|节点的值是一个pairQ包含了key和value?/p>
在gdb中打C下map的内容：(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字节是节点值的地址Q再偏移8则是value的地址
0x606068: 0x00000bbb
(gdb) p *(char**)(0x606040+32) # 偏移32字节是string的地址
$8 = 0x606028 "abc"
或者很多时候没有必要这么装?蛋疼Q?/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配置为集模式时Q在启动或异常情冉|?x)选DZ个实例作为Leader。其默认选D法?code>FastLeaderElection?/p>
不知道zookeeper的可以考虑q样一个问题：(x)某个服务可以配置为多个实例共同构成一个集对外提供服务。其每一个实例本地都存有冗余数据Q每一个实例都可以直接对外提供d服务。在q个集群中ؓ(f)了保证数据的一致性，需要有一个Leader来协调一些事务。那么问题来了：(x)如何定哪一个实例是Leader呢？
问题的难点在于：(x)
- 没有一个仲裁者来选定Leader
- 每一个实例本地可能已l存在数据，不确定哪个实例上的数据是最新的
分布式选D法正是用来解决q个问题的?/p>
本文Zzookeeper 3.4.6 的源码进行分析。FastLeaderElection法的源码全部位?code>FastLeaderElection.java文g中，其对外接口ؓ(f)FastLeaderElection.lookForLeaderQ该接口是一个同步接口，直到选Dl束才会(x)q回。同L(fng)于网上已有类似文章，所以我׃囄的角度来阐述。阅M些其他文章有利于获得初步印象Q?/p>
- 深入出Zookeeper之五 Leader选DQ代码导?/li>
- zookeeper3.3.3源码分析(?FastLeader选D法Q文字描q较l?/li>
主要程
阅读代码和以上推荐文章可以把整个程梳理清楚。实CQ包括了一个消息处理主循环Q也是选D的主要逻辑Q以?qing)一个消息发送队列处理线E和消息解码U程。主要流E可概括Z图：(x)
推荐对照着推荐的文章及(qing)代码理解Q不赘述?/p>
我们从感性上来理解这个算法?/p>
每一个节点，相当于一个选民Q他们都有自q推荐人，最开始他们都推荐自己。谁更适合成ؓ(f)Leader有一个简单的规则Q例如sid够大Q配|）、持有的数据够新(zxid够大)。每个选民都告诉其他选民自己目前的推荐h是谁Q类g出去搞宣传拉拢其他选民。每一个选民发现有比自己更适合的h时就转而推荐这个更适合的h。最后，大部分h意见一致时Q就可以l束选D?/p>
p么简单。M上有一U不断演化Dl果的感觉?/p>
当然Q会(x)有些Ҏ(gu)情况的处理。例如d3个选民Q??已经定3是LeaderQ但3q不知情Q此时就走入LEADING/FOLLOWING的分支，选民3只是接收l果?/p>
代码中不是所有逻辑都在q个大流E中完成的。在接收消息U程中，q可能单独地回应某个节点(WorkerReceiver.run)Q?/p>
从这里可以看出，当某个节点已l确定选Dl果不再处于LOOKING状态时Q其收到LOOKING消息旉?x)直接回应选D的最l结果。结合上面那个比方，相当于某ơ选Dl束了，q个时候来了选民4又发起一ơ新的选DQ那么其他选民q接告诉它当前的Leader情况。相当于Q在q个集群M已经qA的情况下Q又开启了一个实例，q个实例׃(x)直接使用当前的选Dl果?/p>
状态{?/h2>
每个节点上有一些关键的数据l构Q?/p>
- 当前推荐人，初始推荐自己Q每ơ收到其他更好的推荐人时更?/li>
- 其他人的投票集合Q用于确定何旉Dl束
每次推荐人更新时׃(x)q行q播Q正是这个不断地q播驱动整个法向于结果。假设有3个节点A/B/CQ其都还没有数据Q按照sid关系为C>B>AQ那么按照规则，C更可能成为LeaderQ其各个节点的状态{换ؓ(f)Q?/p>
图中Qv(A)表示当前推荐Zؓ(f)AQr[]表示收到的投集合?/p>
可以看看当其他节点已l确定投结果时Q即不再?code>LOOKING时的状态：(x)
代码中有一个特D的投票集合outofelectionQ我理解为选D已结束的那些投票Q这些投仅用于表征选Dl果?/p>
当一个新启动的节点加入集时Q它寚w内其他节点发出投票hQ而其他节点已不处?code>LOOKING状态，此时其他节点回应选Dl果Q该节点攉q些l果?code>outofelection中，最l在收到合法LEADER消息且这些选票也构成选Dl束条gӞ该节点就l束自己的选D行ؓ(f)?em>注意C码中?code>logicalclock = n.electionEpoch;更新选D轮数
?/em>
Kevin Lynx 2014-10-19 15:58 发表评论
]]>Paxos协议/法是分布式pȝ中比较重要的协议Q它有多重要呢？
<分布式系l的事务处理>Q?/p>
Google Chubby的作者Mike Burrows说过q个世界上只有一U一致性算法，那就是PaxosQ其它的法都是D次品?/p>
<大规模分布式存储pȝ>Q?/p>
理解了这两个分布式协议之?Paxos/2PC)Q学?fn)其他分布式协议会(x)变得相当容易?/p>
学习(fn)Paxos法有两部分Qa) 法的原?证明Qb) 法的理?q作?/p>
理解q个法的运作过E其实基本就可以用于工程实践。而且理解q个q程相对来说也容易得多?/p>
|上我觉得讲Paxos讲的好的属于q篇Q?a >paxos图解?a >Paxos法详解Q我q里q?a >wiki上的实例q一步阐q。一些paxos基础通过q里提到的两文章，以及(qing)wiki上的内容基本可以理解?/p>
法内容
Paxos在原作者的《Paxos 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图解文中的流E图可概括ؓ(f)Q?/p>
实例?qing)详?/h2>
Paxos中有三类角色Proposer?code>Acceptor?code>LearnerQ主要交互过E在Proposer?code>Acceptor之间?/p>
Proposer?code>Acceptor之间的交互主要有4cL息通信Q如下图Q?/p>
q?cL息对应于paxos法的两个阶D?个过E：(x)
- phase 1
- a) proposer向网l内过半数的acceptor发送prepare消息
- b) acceptor正常情况下回复promise消息
- phase 2
- a) 在有_多acceptor回复promise消息Ӟproposer发送accept消息
- b) 正常情况下acceptor回复accepted消息
因ؓ(f)在整个过E中可能有其他proposer针对同一件事情发Z上请求，所以在每个q程中都?x)有些特D情况处理，q也是ؓ(f)了达成一致性所做的事情。如果在整个q程中没有其他proposer来竞争，那么q个操作的结果就是确定无异议的。但是如果有其他proposer的话Q情况就不一样了?/p>
?a >paxos中文wiki上的例子Z。简单来说该例子以若q个议员提议E收Q确定最l通过的法案税收比例?/p>
以下图中基本只画出proposer与一个acceptor的交互。时间标志T2L在T1后面。propose numberUN?/p>
情况之一如下图：(x)
A3在T1发出acceptedlA1Q然后在T2收到A5的prepareQ在T3的时候A1才通知A5最l结?E率10%)。这里会(x)有两U情况：(x)
- A5发来的N5于A1发出ȝN1Q那么A3直接拒绝(reject)A5
- A5发来的N5大于A1发出ȝN1Q那么A3回复promiseQ但带上A1?N1, 10%)
q里可以与paxos程囑֯应v来，更好理解?strong>acceptor?x)记?MaxN, AcceptN, AcceptV)?/p>
A5在收到promise后，后箋的流E可以顺利进行。但是发出acceptӞ因ؓ(f)收到?AcceptN, AcceptV)Q所以会(x)取最大的AcceptN对应的AcceptVQ例子中也就是A1?0%作ؓ(f)AcceptV。如果在收到promise时没有发现有其他已记录的AcceptVQ则其值可以由自己军_?/p>
针对以上A1和A5冲突的情况，最lA1和A5都会(x)q播接受的gؓ(f)10%?/p>
其实4个过E中对于acceptor而言Q在回复promise和accepted时由于都可能因ؓ(f)其他proposer的介入而导致特D处理。所以基本上看在q两个时间点收到其他proposer的请求时可以了解整个算法了。例如在回复promise时则可能因ؓ(f)proposer发来的N不够大而rejectQ?/p>
如果在发accepted消息Ӟ对其他更大N的proposer发出qpromiseQ那么也?x)reject该proposer发出的acceptQ如图：(x)
q个对应于Phase 2 b)Q?/p>
it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
ȝ
Leslie Lamport没有用数学描qPaxosQ但是他用英文阐q得很清晰。将Paxos的两个Phase的内容理解清楚，整个法q程q是不复杂的?/p>
至于Paxos中一直提到的一个全局唯一且递增的proposer numberQ其如何实现Q引用如下：(x)
如何产生唯一的编号呢Q在《Paxos made simple》中提到的是让所有的Proposer都从不相交的数据集合中进行选择Q例如系l有5个ProposerQ则可ؓ(f)每一个Proposer分配一个标识j(0~4)Q则每一个proposer每次提出册的编号可以ؓ(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)部|很多实例。这些实例用了一些配|，Z更好地维护这些配|就产生了配|管理服务。通过q个服务可以L地管理这些应用服务的配置问题。应用场景可概括为：(x)
zookeeper的一U应用就是分布式配置理(ZZooKeeper的配|信息存储方案的设计与实?/a>)。百度也有类似的实现Q?a >disconf?/p>
Diamond则是淘宝开源的一U分布式配置理服务的实现。Diamond本质上是一个Java写的Web应用Q其对外提供接口都是ZHTTP协议的，在阅M码时可以从实现各个接口的controller入手?/p>
分布式配|管?/h2>
分布式配|管理的本质基本上就是一U?strong>推?订阅模式的运用。配|的应用Ҏ(gu)订阅者，配置理服务则是推送方。概括ؓ(f)下图Q?/p>
其中Q客L(fng)包括理人员publish数据到配|管理服务，可以理解为添?更新数据Q配|管理服务notify数据到订阅者，可以理解为推送?/p>
配置理服务往往?x)封装一个客L(fng)库，应用方则是基于该库与配置理服务q行交互。在实际实现Ӟ客户端库可能是主动拉?pull)数据Q但对于应用方而言Q一般是一U事仉知方式?/p>
Diamond中的数据是简单的key-valuel构。应用方订阅数据则是Zkey来订阅，未订阅的数据当然不会(x)被推送。数据从cd上又划分合和非聚合。因为数据推送者可能很多，在整个分布式环境中，可能有多个推送者在推送相同key的数据，q些数据如果是聚合的Q那么所有这些推送者推送的数据?x)被合ƈ在一P反之如果是非聚合的，则会(x)出现覆盖?/p>
数据的来源可能是人工通过理端录入，也可能是其他服务通过配置理服务的推送接口自动录入?/p>
架构?qing)实?/h2>
Diamond服务是一个集，是一个去除了单点的协作集。如图：(x)
图中可分Z下部分讲解：(x)
服务之间同步
Diamond服务集群每一个实例都可以对外完整地提供服务，那么意味着每个实例上都有整个集维护的数据。Diamond有两U方式保证这一点：(x)
- M一个实例都有其他实例的地址QQ何一个实例上的数据变更时Q都?x)将改变的数据同步到mysql上，然后通知其他所有实例从mysql上进行一ơ数据拉?
DumpService::dump)Q这个过E只拉取改变了的数据 - M一个实例启动后都会(x)以较长的旉间隔Q几时Q，从mysqlq行一ơ全量的数据拉取(
DumpAllProcessor)
实现上ؓ(f)了一致性，通知其他实例实际上也包含自己。以服务器收到添加聚合数据ؓ(f)例，处理q程大致为：(x)
DatumController::addDatum // /datum.do?method=addDatum
PersistService::addAggrConfigInfo
MergeDatumService::addMergeTask // d一个MergeDataTaskQ异步处?
MergeTaskProcessor::process
PersistService::insertOrUpdate
EventDispatcher.fireEvent(new ConfigDataChangeEvent // z֏一个ConfigDataChangeEvent事g
NotifyService::onEvent // 接收事gq处?
TaskManager::addTask(..., new NotifyTask // 由此Q当数据发生变动Q则最l创Z一个NoticyTask
// NotifyTask同样异步处理
NotifyTaskProcessor::process
foreach server in serverList // 包含自己
notifyToDump // 调用 /notify.do?method=notifyConfigInfo 从mysql更新变动的数?
虽然Diamond去除了单炚w题，不过问题都下降到了mysql上。但׃其作为配|管理的定位Q其数据量就mysql的应用而言小的了Q所以可以一定程度上保证整个服务的可用性?/p>
数据一致?/h3>
׃Diamond服务器没有masterQQ何一个实例都可以d数据Q那么针对同一个key的数据则可能面(f)冲突。这里应该是通过mysql来保证数据的一致性。每一ơ客L(fng)h写数据时QDiamond都将写请求投递给mysqlQ然后通知集群内所有Diamond实例Q包括自己）从mysql拉取数据。当Ӟ拉取数据则可能不是每一ơ写入都能拉出来Q也是最l一致性?/p>
Diamond中没有把数据攑օ内存Q但?x)放到本地文件。对于客L(fng)的读操作而言Q则是直接返回本地文仉的数据?/p>
服务实例列表
Diamond服务实例列表是一份静态数据，直接每个实例的地址存放在一个web server上。无论是Diamond服务q是客户端都从该web server上取出实例列表?/p>
对于客户端而言Q当其取Z该列表后Q则是随机选择一个节?ServerListManager.java)Q以后的h都会(x)发往该节炏V?/p>
数据同步
客户端库中以固定旉间隔从服务器拉取数据(ClientWorker::ClientWorkerQ?code>ClientWorker::checkServerConfigInfo)。只有应用方兛_的数据才可能被拉取。另外，Z数据推送的?qing)时QDiamondq用了一Ulong polling的技术，其实也是ZH破HTTP协议的局限性?em>如果整个服务是基于TCP的自定义协议Q客L(fng)与服务器保持长连接则没有q些问题?/p>
数据的变?/h3>
Diamond中很多操作都?x)检查数据是否发生了变化。标识数据变化则是基于数据对应的MD5值来实现的?/p>
容灾
在整个Diamondpȝ中，几个角色Z提高容灾性，都有自己的缓存，概括Z图：(x)
每一个角色出问题Ӟ都可以尽量保证客L(fng)对应用层提供服务?/p>
参考文?/h2>
Kevin Lynx 2014-10-12 12:57 发表评论
]]>