loop in codes

Kevin Lynx BLOG

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

之前在公司里维护了一个名字服务,这个名字服务日常管理了近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给应用使用

基于servlet实现一个web框架

servlet作为一个web规范,其本身就算做一个web开发框架,但是其web action (响应某个URI的实现)的实现都是基于类的,不是很方便,并且3.0之前的版本还必须通过web.xml配置来增加新的action。servlet中有一个filter的功能,可以配置所有URI的功能都经过filter。我们可以基于filter的功能来实现一个简单的web框架。在这个框架中,主要改进URI action的映射,就像play framework中route的配置:

GET     /hello      com.codemacro.webdemo.test.TestController.hello
GET     /route      com.codemacro.webdemo.test.TestController.route
POST    /hello      com.codemacro.webdemo.test.TestController.sayHello

即把某个URI映射到类接口级别。基于servlet实现web框架的好处不仅实现简单,还能运行在所有支持servlet容器规范的web server上,例如Tomcat、Jetty。

本文提到的web framework demo可以从我的github 上取得:servlet-web-framework-demo

功能

这个web framework URI action部分(或者说URI routing)如同前面描述,action的编写如:

public class TestController extends BaseController {
  // 返回字符串
  public Result index() {
    return ok("hello world");
  }

  // HTTP 404
  public Result code404() {
    return status(404, "not found");
  }

  // 使用JSP模板渲染
  public Result template() {
    String[] langs = new String[] {"c++", "java", "python"};
    return ok(jsp("index.jsp")
        .put("name", "kevin")
        .put("langs",  langs)
        );
  }
}

Java中的反射及Bean容器的实现

编程语言中的反射(Refection)指的是可以在程序运行期动态加载一个类。与之相关的是自省(Introspection),这个指的是程序自己可以获取一个类型的描述信息,例如获取一个类的所有接口定义、一个接口的所有形参。当编程语言有了这些语言特性之后,可以在很大程度上解决代码耦合问题,所以在Java的世界里,可以看到很多库/框架使用了反射技术。

类似Spring的Bean容器实现就是大量运用了反射机制。Bean容器维护了一些Bean对象,简单来说就是一些普通对象。Bean容器可以根据配置创建这些对象,创建时如果这些对象依赖了其他对象,Bean容器还会负责将依赖的对象注入到目标对象中,也就是所谓的依赖注入(dependence injection)。放在模块设计中,又衍生出控制反转(IoC, Inverse of Control)概念,用于描述应用程序在使用一个框架时,不是框架来控制/限制应用程序的架构模式,而是由应用程序来控制框架。

本文就简单描述下Bean容器是如何使用反射来实现的,最终代码参考github ioc-sample

类的动态加载

可以简单地使用Class.forName,传入某个class的完整名:

public Class<?> loadClass(String fullName) throws ClassNotFoundException {
  return Class.forName(fullName);
}

类的加载涉及到class loader,这块内容是可以进一步深化的。加载了类之后就可以创建出类的实例,但还没有完成依赖注入的功能:

Class<?> c = loadClass("com.codemacro.bean.test.Test1");
Object o = c.newInstance();

Drill中实现HTTP storage plugin

Apache Drill可用于大数据的实时分析,引用一段介绍:

受到Google Dremel启发,Apache的Drill项目是对大数据集进行交互式分析的分布式系统。Drill并不会试图取代已有的大数据批处理框架(Big Data batch processing framework),如Hadoop MapReduce或流处理框架(stream processing framework),如S4和Storm。相反,它是要填充现有空白的——对大数据集的实时交互式处理

简单来说,Drill可接收SQL查询语句,然后后端从多个数据源例如HDFS、MongoDB等获取数据并分析产出分析结果。在一次分析中,它可以汇集多个数据源的数据。而且基于分布式的架构,可以支持秒级查询。

Drill在架构上是比较灵活的,它的前端可以不一定是SQL查询语言,后端数据源也可以接入Storage plugin来支持其他数据来源。这里我就实现了一个从HTTP服务获取数据的Storage plugin demo。这个demo可以接入基于GET请求,返回JSON格式的HTTP服务。源码可从我的Github获取:drill-storage-http

例子包括:

select name, length from http.`/e/api:search` where $p=2 and $q='avi'
select name, length from http.`/e/api:search?q=avi&p=2` where length > 0 

实现

要实现一个自己的storage plugin,目前Drill这方面文档几乎没有,只能从已有的其他storage plugin源码入手,例如mongodb的,参考Drill子项目drill-mongo-storage。实现的storage plugin打包为jar放到jars目录,Drill启动时会自动载入,然后web上配置指定类型即可。

主要需要实现的类包括:

AbstractStoragePlugin
StoragePluginConfig
SchemaFactory
BatchCreator
AbstractRecordReader
AbstractGroupScan

无锁有序链表的实现

无锁有序链表可以保证元素的唯一性,使其可用于哈希表的桶,甚至直接作为一个效率不那么高的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对象的地址时,可以通过以下代码获取相关值: