Subscribe: C++博客-紫月城游戏软件
http://www.cppblog.com/kevinlynx/Rss.aspx
Added By: Feedage Forager Feedage Grade B rated
Language: Chinese simplified
Tags:
Rate this Feed
Rate this feedRate this feedRate this feedRate this feedRate this feed
Rate this feed 1 starRate this feed 2 starRate this feed 3 starRate this feed 4 starRate this feed 5 star

Comments (0)

Feed Details and Statistics Feed Statistics
Preview: C++博客-紫月城游戏软件

C++博客-loop_in_codes



低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx



Published: Mon, 18 Dec 2017 17:01:05 GMT

Last Build Date: Mon, 18 Dec 2017 17:01:05 GMT

 



写了一个分布式名字服务JCM

Sat, 04 Jul 2015 09:50:00 GMT

之前在公司里维护了一个名字服务,这个名字服务日常管理了近4000台机器,有4000个左右的客户端连接上来获取机器信息,由于其基本是一个单点服务,所以某些模块接近瓶颈。后来倒是有重构计划,详细设计做了,代码都写了一部分,结果由于某些原因重构就被终止了。 JCM是我业余时间用Java重写的一个版本,功能上目前只实现了基础功能。由于它是个完全分布式的架构,所以理论上可以横向扩展,大大增强系统的服务能力。 名字服务 在分布式系统中,某个服务为了提升整体服务能力,通常部署了很多实例。这里我把这些提供相同服务的实例统称为集群(cluster),每个实例称为一个节点(Node)。一个应用可能会使用很多cluster,每次访问一个cluster时,就通过名字服务获取该cluster下一个可用的node。那么,名字服务至少需要包含的功能: 根据cluster名字获取可用的node 对管理的所有cluster下的所有node进行健康度的检测,以保证始终返回可用的node 有些名字服务仅对node管理,不参与应用与node间的通信,而有些则可能作为应用与node间的通信转发器。虽然名字服务功能简单,但是要做一个分布式的名字服务还是比较复杂的,因为数据一旦分布式了,就会存在同步、一致性问题的考虑等。 What’s JCM JCM围绕前面说的名字服务基础功能实现。包含的功能: 管理cluster到node的映射 分布式架构,可水平扩展以实现管理10,000个node的能力,足以管理一般公司的后台服务集群 对每个node进行健康检查,健康检查可基于HTTP协议层的检测或TCP连接检测 持久化cluster/node数据,通过zookeeper保证数据一致性 提供JSON HTTP API管理cluster/node数据,后续可提供Web管理系统 以库的形式提供与server的交互,库本身提供各种负载均衡策略,保证对一个cluster下node的访问达到负载均衡 项目地址git jcm JCM主要包含两部分: jcm.server,JCM名字服务,需要连接zookeeper以持久化数据 jcm.subscriber,客户端库,负责与jcm.server交互,提供包装了负载均衡的API给应用使用 架构 基于JCM的系统整体架构如下: cluster本身是不需要依赖JCM的,要通过JCM使用这些cluster,只需要通过JCM HTTP API注册这些cluster到jcm.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文件进行配置,参考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")); // 使用轮询负载均衡策略 RRAllocator rr = new RRAllocator(); subscriber.addListener(rr); subscriber.startup(); for (int i = 0; i < 2; ++i) { // rr.alloc 根据cluster名字获取可用的node System.out.println(rr.alloc("hello9", ProtoType.HTTP)); } subscriber.shutdown(); JCM实现 JCM目前的实现比较简单,参考模块图: model,即cluster/node这些数据结构的描述,同时被jcm.server和jcm.subscriber依赖 storage,持久化数据到zookeeper,同时包含jcm.server实例之间的数据同步 health check,健康检查模块,对各个node进行健康检查 以上模块都不依赖Spring,基于以上模块又有: http api,使[...]



无锁有序链表的实现

Tue, 05 May 2015 11:47:00 GMT

无锁有序链表可以保证元素的唯一性,使其可用于哈希表的桶,甚至直接作为一个效率不那么高的map。普通链表的无锁实现相对简单点,因为插入元素可以在表头插,而有序链表的插入则是任意位置。 本文主要基于论文High Performance Dynamic Lock-Free Hash Tables实现。 主要问题 链表的主要操作包含insert和remove,先简单实现一个版本,就会看到问题所在,以下代码只用作示例: 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函数返回查找到的前序元素和元素本身,代码A和B虽然拿到了pred和item,但在CAS的时候,其可能被其他线程移除。甚至,在l_find过程中,其每一个元素都可能被移除。问题在于,任何时候拿到一个元素时,都不确定其是否还有效。元素的有效性包括其是否还在链表中,其指向的内存是否还有效。 解决方案 通过为元素指针增加一个有效性标志位,配合CAS操作的互斥性,就可以解决元素有效性判定问题。 因为node_t放在内存中是会对齐的,所以指向node_t的指针值低几位是不会用到的,从而可以在低几位里设置标志,这样在做CAS的时候,就实现了DCAS的效果,相当于将两个逻辑上的操作变成了一个原子操作。想象下引用计数对象的线程安全性,其内包装的指针是线程安全的,但对象本身不是。 CAS的互斥性,在若干个线程CAS相同的对象时,只有一个线程会成功,失败的线程就可以以此判定目标对象发生了变更。改进后的代码(代码仅做示例用,不保证正确): 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可能被[...]



并行编程中的内存回收Hazard Pointer

Sun, 03 May 2015 12:46:00 GMT

接上篇使用RCU技术实现读写线程无锁,在没有GC机制的语言中,要实现Lock free的算法,就免不了要自己处理内存回收的问题。 Hazard Pointer是另一种处理这个问题的算法,而且相比起来不但简单,功能也很强大。锁无关的数据结构与Hazard指针中讲得很好,Wikipedia Hazard pointer也描述得比较清楚,所以我这里就不讲那么细了。 一个简单的实现可以参考我的github haz_ptr.c 原理 基本原理无非也是读线程对指针进行标识,指针(指向的内存)要释放时都会缓存起来延迟到确认没有读线程了才对其真正释放。 中的描述: 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.” 关键的结构包括:Hazard pointer、Thread Free list Hazard pointer:一个读线程要使用一个指针时,就会创建一个Hazard pointer包装这个指针。一个Hazard pointer会被一个线程写,多个线程读。 struct HazardPointer { void *real_ptr; // 包装的指针 ... // 不同的实现有不同的成员 }; void func() { HazardPointer *hp = accquire(_real_ptr); ... // use _real_ptr release(hp); } Thread Free List:每个线程都有一个这样的列表,保存着将要释放的指针列表,这个列表仅对应的线程读写 void defer_free(void *ptr) { _free_list.push_back(ptr); } 当某个线程要尝试释放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的主要内容。 Hazard Pointer的管理 上面的代码中没有提到_all_hazard_pointers及accquire的具体实现,这就是Hazard Pointer的管理问题。 《锁无关的数据结构与Hazard指针》文中创建了一个Lock free的链表来表示这个全局的Hazard Pointer List。每个Hazard Pointer有一个成员标识其是否可用。这个List中也就保存了已经被使用的Hazard Pointer集合和未被使用的Hazard Pointer集合,当所有Hazard Pointer都被使用时,就会新分配一个加进这个List。当读线程不使用指针时,需要归还Hazard Pointer,直接设置可用成员标识即可。要gc()时,就直接遍历这个List。 要实现一个Lock free的链表,并且仅需要实现头插入,还是非常简单的。本身Hazard Pointer标识某个指针时,都是用了后立即标识,所以这个实现直接支持了动态线程,支持线程的挂起等。 在nbds项目中也有一个Hazard Pointer的实现,相对要弱一点。它为每个线程都设置了自己的Hazard Pointer池,写线程要释放指针时,就访问所有其他线程的Hazard Pointer池。 typedef struct haz_local { // Free List pending_t *pending; // to be freed int pending_size; int pending_count; // Hazard Pointer 池,动态和静态两种 haz_t static_haz[STATIC_HAZ_PER_THREAD]; haz_t **dynamic; int dynamic_size; int dynamic_count; } __attribute__ ((aligned(CACHE_[...]



使用RCU技术实现读写线程无锁

Sun, 19 Apr 2015 11:10:00 GMT

在一个系统中有一个写线程和若干个读线程,读写线程通过一个指针共用了一个数据结构,写线程改写这个结构,读线程读取该结构。在写线程改写这个数据结构的过程中,加锁情况下读线程由于等待锁耗时会增加。 可以利用RCU (Read Copy Update What is rcu)的思想来去除这个锁。本文提到的主要实现代码:gist RCU RCU可以说是一种替代读写锁的方法。其基于一个事实:当写线程在改变一个指针时,读线程获取这个指针,要么获取到老的值,要么获取到新的值。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指向的内容时,先复制一份新的,基于新的进行改变,更新_ptr指针,最后同步释放老的内存。 读线程: tmp_ptr = _ptr use(tmp_ptr) dereference(tmp_ptr) 读线程直接使用_ptr,使用完后需要告诉写线程自己不再使用_ptr。读线程获取_ptr时,可能会获取到老的也可能获取到新的,无论哪种RCU都需要保证这块内存是有效的。重点在synchroize和dereference。synchroize会等待所有使用老的_ptr的线程dereference,对于新的_ptr使用者其不需要等待。这个问题说白了就是写线程如何知道old_ptr没有任何读线程在使用,可以安全地释放。 这个问题实际上在wait-free的各种实现中有好些解法,how-when-to-release-memory-in-wait-free-algorithms这里有人总结了几种方法,例如Hazard pointers、Quiescence period based reclamation。 简单地使用引用计数智能指针是无法解决这个问题的,因为智能指针自己不是线程安全的,例如: tmp_ptr = _ptr // 1 tmp_ptr->addRef() // 2 use tmp_ptr->release() 代码1/2行不是原子的,所以当取得tmp_ptr准备addRef时,tmp_ptr可能刚好被释放了。 Quiescence period based reclamation方法指的是读线程需要声明自己处于Quiescence period,也就是不使用_ptr的时候,当其使用_ptr的时候实际是进入了一个逻辑上的临界区,当所有读线程都不再使用_ptr的时候,写线程就可以对内存进行安全地释放。 本文正是描述了一种Quiescence period based reclamation实现。这个实现可以用于有一个写线程和多个读线程共用若干个数据的场景。 实现 该方法本质上把数据同步分解为基本的内存单元读写。使用方式上可描述为: 读线程: tmp_ptr = _ptr use update() // 标识自己不再使用任何共享数据 写线程: old_ptr = _ptr tmp_ptr = copy(_ptr) change(tmp_ptr) _ptr = tmp_ptr gc() defer_free(old_ptr) 以下具体描述读写线程的实现。 写线程 写线程负责标识内存需要被释放,以及检查何时可以真正释放内存。其维护了一个释放内存队列: 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找到一个可释放内存位置,在[_tail, find_free_pos())这个区间内所有内存是可以安全被释放的。 队列位置_head/_tail一直增大,PENDING_POS就是对这个位置取模,限定在队列大小范围内也是可行的,无论哪种方式,_head从逻辑上说一直>=_tail,但在实际中可能小于_tail,所以实现时不使用大小判定,而是: gc() { pos = find_free_pos() while (_tail != pos) { free(_pending[PENDING_POS(_tail)]) _tail ++ } } 读线[...]



记一次tcmalloc分配内存引起的coredump

Mon, 06 Apr 2015 10:33:00 GMT

现象 线上的服务出现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=) 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 ... 查看了应用层相关数据结构,基本数据都是没有问题的。所以最初怀疑是tcmalloc内部维护了错误的内存,在分配内存时出错,这个堆栈只是问题的表象。几天后,线上的另一个服务,基于同样的库,也core了,堆栈还是一样的。 最初定位问题都是从最近更新的东西入手,包括依赖的server环境,但都没有明显的问题,所以最后只能从core的直接原因入手。 分析GetStackTrace 确认core的详细位置: # 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]处读取内容,然后出错,这个内存单元不可读。但是具体这个指令在代码中是什么意思,需要将这个指令对应到代码中。获取tcmalloc的源码,发现GetStackTrace根据编译选项有很多实现,所以这里选择最可能的实现,然后对比汇编以确认代码是否匹配。最初选择的是stacktrace_x86-64-inl.h,后来发现完全不匹配,又选择了stacktrace_x86-inl.h。这个实现版本里也有对64位平台的支持。 stacktrace_x86-inl.h里使用了一些宏来生成函数名和参数,精简后代码大概为: 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(0)) { break; } void **next_sp = NextStackFrame(sp, ucp); if (skip_count > 0) { skip_count--; } else { result[n] = *(sp+1); n++; } sp = next_sp; } return n; } NextStackFrame是一个模板函数,包含一大堆代码,精简后非常简单: template 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[...]



基于内存查看STL常用容器内容

Wed, 03 Dec 2014 14:08:00 GMT

有时候在线上使用gdb调试程序core问题时,可能没有符号文件,拿到的仅是一个内存地址,如果这个指向的是一个STL对象,那么如何查看这个对象的内容呢? 只需要知道STL各个容器的数据结构实现,就可以查看其内容。本文描述了SGI STL实现中常用容器的数据结构,以及如何在gdb中查看其内容。 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内有一个指针,指向实际的字符串位置,这个位置前面有一个_Rep结构,其内保存了字符串的长度、可用内存以及引用计数。当我们拿到一个string对象的地址时,可以通过以下代码获取相关值: 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实现就是一块连续的内存,bits/stl_vector.h。 template > class vector : protected _Vector_base<_Tp, _Alloc> ... template 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)=24,其内也就是3个指针,_M_start指向首元素地址,_M_finish指向最后一个节点+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 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 vec; vec.push_back(0x11); vec.push_back(0x22); vec.push_back(0x33); ds_vec_i(&vec); r[...]



linux动态库的种种要点

Mon, 03 Nov 2014 16:55:00 GMT

linux下使用动态库,基本用起来还是很容易。但如果我们的程序中大量使用动态库来实现各种框架/插件,那么就会遇到一些坑,掌握这些坑才有利于程序更稳健地运行。 本篇先谈谈动态库符号方面的问题。 测试代码可以在github上找到 符号查找 一个应用程序test会链接一个动态库libdy.so,如果一个符号,例如函数callfn定义于libdy.so中,test要使用该函数,简单地声明即可: // dy.cpp libdy.so void callfn() { ... } // main.cpp test extern void callfn(); callfn(); 在链接test的时候,链接器会统一进行检查。 同样,在libdy.so中有相同的规则,它可以使用一个外部的符号,在它被链接/载入进一个可执行程序时才会进行符号存在与否的检查。这个符号甚至可以定义在test中,形成一种双向依赖,或定义在其他动态库中: // 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被链接进test时则会进行检查,试着把mfunc函数的定义去掉,就会得到一个链接错误: ./libdy.so: undefined reference to `mfunc()' 同样,如果我们动态载入libdy.so,此时当然可以链接通过,但是在载入时同样得到找不到符号的错误: #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 结论:基于以上,我们知道,如果一个动态库依赖了一些外部符号,这些外部符号可以位于其他动态库甚至应用程序中。我们可以再链接这个动态库的时候就把依赖的其他库也链接上,或者推迟到链接应用程序时再链接。而动态加载的库,则要保证在加载该库时,进程中加载的其他动态库里已经存在该符号。 例如,通过LD_PRELOAD环境变量可以让一个进程先加载指定的动态库,上面那个动态加载启动失败的例子,可以通过预先加载包含mfunc符号的动态库解决: $ LD_PRELOAD=libmfun.so ./test ... 但是如果这个符号存在于可执行程序中则不行: $ nm test | grep mfunc 0000000000400a00 T _Z5mfuncv $ nm test | grep mfunc 0000000000400a00 T _Z5mfuncv $ ./test ... ./test: symbol lookup error: ./libdy.so: undefined symbol: _Z5mfuncv 符号覆盖 前面主要讲的是符号缺少的情况,如果同一个符号存在多分,则更能引发问题。这里谈到的符号都是全局符号,一个进程中某个全局符号始终是全局唯一的。为了保证这一点,在链接或动态载入动态库时,就会出现忽略重复符号的情况。 这里就不提同一个链接单位(如可执行程序、动态库)里符号重复的问题了 函数 当动态库和libdy.so可执行程序test中包含同名的函数时会怎样?根据是否动态加载情况还有所不同。 当直接链接动态库时,libdy.so和test都会链接包含func函数的fun.o,为了区分,我把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 -sha[...]



图解zookeeper FastLeader选举算法

Sun, 19 Oct 2014 07:58:00 GMT

zookeeper配置为集群模式时,在启动或异常情况时会选举出一个实例作为Leader。其默认选举算法为FastLeaderElection

不知道zookeeper的可以考虑这样一个问题:某个服务可以配置为多个实例共同构成一个集群对外提供服务。其每一个实例本地都存有冗余数据,每一个实例都可以直接对外提供读写服务。在这个集群中为了保证数据的一致性,需要有一个Leader来协调一些事务。那么问题来了:如何确定哪一个实例是Leader呢?

问题的难点在于:

  • 没有一个仲裁者来选定Leader
  • 每一个实例本地可能已经存在数据,不确定哪个实例上的数据是最新的

分布式选举算法正是用来解决这个问题的。

本文基于zookeeper 3.4.6 的源码进行分析。FastLeaderElection算法的源码全部位于FastLeaderElection.java文件中,其对外接口为FastLeaderElection.lookForLeader,该接口是一个同步接口,直到选举结束才会返回。同样由于网上已有类似文章,所以我就从图示的角度来阐述。阅读一些其他文章有利于获得初步印象:

主要流程

阅读代码和以上推荐文章可以把整个流程梳理清楚。实现上,包括了一个消息处理主循环,也是选举的主要逻辑,以及一个消息发送队列处理线程和消息解码线程。主要流程可概括为下图:

(image)

推荐对照着推荐的文章及代码理解,不赘述。

我们从感性上来理解这个算法。

每一个节点,相当于一个选民,他们都有自己的推荐人,最开始他们都推荐自己。谁更适合成为Leader有一个简单的规则,例如sid够大(配置)、持有的数据够新(zxid够大)。每个选民都告诉其他选民自己目前的推荐人是谁,类似于出去搞宣传拉拢其他选民。每一个选民发现有比自己更适合的人时就转而推荐这个更适合的人。最后,大部分人意见一致时,就可以结束选举。

就这么简单。总体上有一种不断演化逼近结果的感觉。

当然,会有些特殊情况的处理。例如总共3个选民,1和2已经确定3是Leader,但3还不知情,此时就走入LEADING/FOLLOWING的分支,选民3只是接收结果。

代码中不是所有逻辑都在这个大流程中完成的。在接收消息线程中,还可能单独地回应某个节点(WorkerReceiver.run):

(image)

从这里可以看出,当某个节点已经确定选举结果不再处于LOOKING状态时,其收到LOOKING消息时都会直接回应选举的最终结果。结合上面那个比方,相当于某次选举结束了,这个时候来了选民4又发起一次新的选举,那么其他选民就直接告诉它当前的Leader情况。相当于,在这个集群主从已经就绪的情况下,又开启了一个实例,这个实例就会直接使用当前的选举结果。

状态转换

每个节点上有一些关键的数据结构:

  • 当前推荐人,初始推荐自己,每次收到其他更好的推荐人时就更新
  • 其他人的投票集合,用于确定何时选举结束

每次推荐人更新时就会进行广播,正是这个不断地广播驱动整个算法趋向于结果。假设有3个节点A/B/C,其都还没有数据,按照sid关系为C>B>A,那么按照规则,C更可能成为Leader,其各个节点的状态转换为:

(image)

图中,v(A)表示当前推荐人为A;r[]表示收到的投票集合。

可以看看当其他节点已经确定投票结果时,即不再是LOOKING时的状态:

(image)

代码中有一个特殊的投票集合outofelection,我理解为选举已结束的那些投票,这些投票仅用于表征选举结果。

当一个新启动的节点加入集群时,它对集群内其他节点发出投票请求,而其他节点已不处于LOOKING状态,此时其他节点回应选举结果,该节点收集这些结果到outofelection中,最终在收到合法LEADER消息且这些选票也构成选举结束条件时,该节点就结束自己的选举行为。注意到代码中会logicalclock = n.electionEpoch;更新选举轮数

(image)

Kevin Lynx 2014-10-19 15:58 发表评论



图解分布式一致性协议Paxos

Wed, 15 Oct 2014 14:45:00 GMT

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分布式系统的事务处理>: Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。 <大规模分布式存储系统>: 理解了这两个分布式协议之后(Paxos/2PC),学习其他分布式协议会变得相当容易。 学习Paxos算法有两部分:a) 算法的原理/证明;b) 算法的理解/运作。 理解这个算法的运作过程其实基本就可以用于工程实践。而且理解这个过程相对来说也容易得多。 网上我觉得讲Paxos讲的好的属于这篇:paxos图解及Paxos算法详解,我这里就结合wiki上的实例进一步阐述。一些paxos基础通过这里提到的两篇文章,以及wiki上的内容基本可以理解。 算法内容 Paxos在原作者的《Paxos Made Simple》中内容是比较精简的: 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类消息对应于paxos算法的两个阶段4个过程: phase 1 a) proposer向网络内超过半数的acceptor发送prepare消息 b) acceptor正常情况下回复promise消息 phase 2 a) 在有足够多acceptor回复promise消息时,proposer发送accept消息 b) 正常情况下acceptor回复accepted消息 因为在整个过程中可能有其他proposer针对同一件事情发出以上请求,所以在每个过程中都会有些特殊情况处理,这也是为了达成一致性所做的事情。如果在整个过程中没有其他proposer来竞争,那么这个操作的结果就是确定无异议的。但是如果有其他proposer的话,情况就不一样了。 以paxos中文wiki上的例子为例。简单来说该例子以若干个议员提议税收,确定最终通过的法案税收比例。 以下图中基本只画出proposer与一个acceptor的交互。时间标志T2总是在T1后面。propose number简称N。 情况之一如下图: A3在T1发出accepted给A1,然后在T2收到A5的prepare,在T3的时候A1才通知A5最终结果(税率10%)。这里会有两种情况: A5发来的N5小于A1发出去的N1,那么A3直接拒绝(reject)A5 A5发来的N5大于A1发出去的N1,那么A3回复promise,但带上A1的(N1, 10%) 这里可以与paxos流程图对应起来,更好理解。acceptor会记录(MaxN, AcceptN, AcceptV)。 A5在收到promise后,后续的流程可以顺利进行。但是发出accept时,因为收到了(AcceptN, AcceptV),所以会取最大的AcceptN[...]



淘宝分布式配置管理服务Diamond

Sun, 12 Oct 2014 04:57:00 GMT

在一个分布式环境中,同类型的服务往往会部署很多实例。这些实例使用了一些配置,为了更好地维护这些配置就产生了配置管理服务。通过这个服务可以轻松地管理这些应用服务的配置问题。应用场景可概括为: zookeeper的一种应用就是分布式配置管理(基于ZooKeeper的配置信息存储方案的设计与实现)。百度也有类似的实现:disconf。 Diamond则是淘宝开源的一种分布式配置管理服务的实现。Diamond本质上是一个Java写的Web应用,其对外提供接口都是基于HTTP协议的,在阅读代码时可以从实现各个接口的controller入手。 分布式配置管理 分布式配置管理的本质基本上就是一种推送-订阅模式的运用。配置的应用方是订阅者,配置管理服务则是推送方。概括为下图: 其中,客户端包括管理人员publish数据到配置管理服务,可以理解为添加/更新数据;配置管理服务notify数据到订阅者,可以理解为推送。 配置管理服务往往会封装一个客户端库,应用方则是基于该库与配置管理服务进行交互。在实际实现时,客户端库可能是主动拉取(pull)数据,但对于应用方而言,一般是一种事件通知方式。 Diamond中的数据是简单的key-value结构。应用方订阅数据则是基于key来订阅,未订阅的数据当然不会被推送。数据从类型上又划分为聚合和非聚合。因为数据推送者可能很多,在整个分布式环境中,可能有多个推送者在推送相同key的数据,这些数据如果是聚合的,那么所有这些推送者推送的数据会被合并在一起;反之如果是非聚合的,则会出现覆盖。 数据的来源可能是人工通过管理端录入,也可能是其他服务通过配置管理服务的推送接口自动录入。 架构及实现 Diamond服务是一个集群,是一个去除了单点的协作集群。如图: 图中可分为以下部分讲解: 服务之间同步 Diamond服务集群每一个实例都可以对外完整地提供服务,那么意味着每个实例上都有整个集群维护的数据。Diamond有两种方式保证这一点: 任何一个实例都有其他实例的地址;任何一个实例上的数据变更时,都会将改变的数据同步到mysql上,然后通知其他所有实例从mysql上进行一次数据拉取(DumpService::dump),这个过程只拉取改变了的数据 任何一个实例启动后都会以较长的时间间隔(几小时),从mysql进行一次全量的数据拉取(DumpAllProcessor) 实现上为了一致性,通知其他实例实际上也包含自己。以服务器收到添加聚合数据为例,处理过程大致为: DatumController::addDatum // /datum.do?method=addDatum PersistService::addAggrConfigInfo MergeDatumService::addMergeTask // 添加一个MergeDataTask,异步处理 MergeTaskProcessor::process PersistService::insertOrUpdate EventDispatcher.fireEvent(new ConfigDataChangeEvent // 派发一个ConfigDataChangeEvent事件 NotifyService::onEvent // 接收事件并处理 TaskManager::addTask(..., new NotifyTask // 由此,当数据发生变动,则最终创建了一个NoticyTask // NotifyTask同样异步处理 NotifyTaskProcessor::process foreach server in serverList // 包含自己 notifyToDump // 调用 /notify.do?method=notifyConfigInfo 从mysql更新变动的数据 虽然Diamond去除了单点问题,不过问题都下降到了mysql上。但由于其作为配置管理的定位,其数据量就mysql的应用而言算小的了,所以可以一定程度上保证整个服务的可用性。 数据一致性 由于Diamond服务器没[...]