loop in codes

Kevin Lynx BLOG

无锁有序链表的实现

无锁有序链表可以保证元素的唯一性,使其可用于哈希表的桶,甚至直接作为一个效率不那么高的map。普通链表的无锁实现相对简单点,因为插入元素可以在表头插,而有序链表的插入则是任意位置。

本文主要基于论文High Performance Dynamic Lock-Free Hash Tables实现。

主要问题

链表的主要操作包含insertremove,先简单实现一个版本,就会看到问题所在,以下代码只用作示例:

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;
            }
        }
    }

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

接上篇使用RCU技术实现读写线程无锁,在没有GC机制的语言中,要实现Lock free的算法,就免不了要自己处理内存回收的问题。

Hazard Pointer是另一种处理这个问题的算法,而且相比起来不但简单,功能也很强大。锁无关的数据结构与Hazard指针中讲得很好,Wikipedia Hazard pointer也描述得比较清楚,所以我这里就不讲那么细了。

一个简单的实现可以参考我的github haz_ptr.c

原理

基本原理无非也是读线程对指针进行标识,指针(指向的内存)要释放时都会缓存起来延迟到确认没有读线程了才对其真正释放。

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

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

关键的结构包括:Hazard pointerThread Free list

Hazard pointer:一个读线程要使用一个指针时,就会创建一个Hazard pointer包装这个指针。一个Hazard pointer会被一个线程写,多个线程读。

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

在一个系统中有一个写线程和若干个读线程,读写线程通过一个指针共用了一个数据结构,写线程改写这个结构,读线程读取该结构。在写线程改写这个数据结构的过程中,加锁情况下读线程由于等待锁耗时会增加。

可以利用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指针,最后同步释放老的内存。

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

现象

线上的服务出现coredump,堆栈为:

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

查看了应用层相关数据结构,基本数据都是没有问题的。所以最初怀疑是tcmalloc内部维护了错误的内存,在分配内存时出错,这个堆栈只是问题的表象。几天后,线上的另一个服务,基于同样的库,也core了,堆栈还是一样的。

最初定位问题都是从最近更新的东西入手,包括依赖的server环境,但都没有明显的问题,所以最后只能从core的直接原因入手。

初识JVM byte code

关于JVM和其上的byte code,网上其实有足够多的资料了,我这里就简单做个提纲和介绍,权当记录吧。

stack-based VM

Java byte code运行在JVM上,就像机器指令运行在物理机上,是需要遵循这个机器的指令规范的。所以认识JVM byte code,是需要稍微了解下JVM的。JVM是一个基于栈(stack-based)的虚拟机。很久以前我还写过类似简单的虚拟机

基于栈的虚拟机其操作数和指令运算的中间结果全部都在一个虚拟栈中,与之对应的是基于寄存器(register-based)的虚拟机,其操作数和指令运算结果会存放在若干个寄存器(也就是存储单元)里。x86机器就可以理解为基于寄存器的机器。

byte code其实和x86汇编代码本质一样,无非是对应机器制定的一堆指令,这里可以举例说明下两类虚拟机的不同:

# stack-based 
push 1       # 压立即数1到栈顶
push 2       # 压立即数2到栈顶
add          # 弹出栈顶2个数相加,将结果3压到栈顶

# register-based
mov ax, 1    # 写立即数到寄存器ax
add ax, 2    # 取ax中的值1与立即数2进行相加,存放结果到ax

关于两类实现的比较,网上也有不少资料,例如Dalvik 虚拟机和 Sun JVM 在架构和执行方面有什么本质区别?

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

有时候在线上使用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对象的地址时,可以通过以下代码获取相关值:

linux动态库的种种要点

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中,形成一种双向依赖,或定义在其他动态库中:

图解zookeeper FastLeader选举算法

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

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

问题的难点在于:

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

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

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

主要流程

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

图解分布式一致性协议Paxos

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢?

<分布式系统的事务处理>

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。

<大规模分布式存储系统>

理解了这两个分布式协议之后(Paxos/2PC),学习其他分布式协议会变得相当容易。

学习Paxos算法有两部分:a) 算法的原理/证明;b) 算法的理解/运作。

理解这个算法的运作过程其实基本就可以用于工程实践。而且理解这个过程相对来说也容易得多。

网上我觉得讲Paxos讲的好的属于这篇:paxos图解Paxos算法详解,我这里就结合wiki上的实例进一步阐述。一些paxos基础通过这里提到的两篇文章,以及wiki上的内容基本可以理解。

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

在一个分布式环境中,同类型的服务往往会部署很多实例。这些实例使用了一些配置,为了更好地维护这些配置就产生了配置管理服务。通过这个服务可以轻松地管理这些应用服务的配置问题。应用场景可概括为:

zookeeper的一种应用就是分布式配置管理(基于ZooKeeper的配置信息存储方案的设计与实现)。百度也有类似的实现:disconf

Diamond则是淘宝开源的一种分布式配置管理服务的实现。Diamond本质上是一个Java写的Web应用,其对外提供接口都是基于HTTP协议的,在阅读代码时可以从实现各个接口的controller入手。

分布式配置管理

分布式配置管理的本质基本上就是一种推送-订阅模式的运用。配置的应用方是订阅者,配置管理服务则是推送方。概括为下图:

其中,客户端包括管理人员publish数据到配置管理服务,可以理解为添加/更新数据;配置管理服务notify数据到订阅者,可以理解为推送。