SmartStack Airbnb的自动服务发现和注册框架

Micro-service引发的问题

在几年前做企业快盘的时候,为了构建一个高可用的分布式系统,我们采用了一个模块一个服务,不同服务之间通过HTTP交互的架构模型,除了数据存储服务(MySQL,Redis等),我们其他的服务都是无状态的,这样就能非常方便的进行水平扩展,满足不断增加的业务需求。现在才知道,这种架构模式就是俗称的micro-service,如果当初我们就能拿这些概念出去忽悠,没准能让自己的产品更加高大上一点的。:-)

micro-service虽然方便,毕竟各个模块是相互独立,我们可以独立开发,独立部署,只要约定好相互之间的HTTP Restful API就成了。但是,随着服务的增多,我们会面临一个问题,就是某一个服务到底在哪里?我们如何才能发现该服务并进行调用。

在项目初期,服务数量不多的情况下面,我们可以将所有服务的地址写到一个配置文件里面(或者更改hosts),部署升级的时候通过puppet或者其它工具进行整个系统的更新,但这样,就会面临一个问题,任何增加删除服务的操作,都可能引起整个系统的更新。随着系统规模的扩大,服务数量的增多,谁都知道不可行了。

Airbnb的工程师一定也碰到了类似了问题,否则他们不会开发了SmartStack。关于SmartStack的详细介绍,可以参考这篇文章SmartStack: Service Discovery in the Cloud,国内的oschina已经有相关翻译SmartStack 介绍 —— 云端的服务发现,所以我就不用考虑再将这篇文章重复翻译一遍了。下面我只是想说说我的一些理解。

不怎么好的解决方案

Airbnb的这篇文章同时列出了一些不怎么好的解决方案,个人觉得对我们设计分布式系统也是很有借鉴意义的。

DNS

DNS应该是一个非常简单地解决方案了,一个服务配置一个Domain,通过DNS解析,客户端对某个服务的请求就能被路由到某一台具体的机器上面处理。

虽然很简单,但是DNS也有很严重的问题,首先就是延时,如果我们更新了DNS,我们无法保证一些客户端能及时的收到DNS变更的消息。同时,在机器上面,DNS通常都有缓存,所以更加增大了变更DNS的延时。

另外,DNS是随机路由的,我们不能自定义自己的路由算法,所以很有可能我们会面临一个服务里面,一些机器繁忙的在处理请求,而另一些机器则几乎被闲置。

还有一个很严重的问题,一些应用程序譬如Nginx在程序启动的时候会缓存DNS的结果,也就是如果不做任何特殊处理,DNS的任何变更对当前运行中的Nginx是完全无效的。

综上,如果服务的节点动态变更比较频繁,使用DNS来进行服务发现并不是一个很好的解决方案。但对于一些节点长时间不会变动的服务,譬如Zookeeper,使用DNS则是一个比较好的方式。

中心化的负载均衡

我们可以使用一个中心化的负载均衡器来进行服务的路由。所有的路由信息都存储到这个负载均衡器里面。但我们如何发现这个负载均衡器,通常的做法就是DNS,不过这又会出现上面DNS的问题。

同时,因为这个负载均衡器是一个中心化的节点,必然面临单点性能问题,而且如果负载均衡器当掉了,我们就会面临整个系统不可用的问题了(这时候完全不知道其他服务在哪里了)。

因为负载均衡器是一个单点,所以我们需要考虑将其做HA处理,另外,我们还需要考虑性能问题。如果有钱,考虑购入F5,不过这种硬件路由方案真心很贵。LVS, Nginx或者HAProxy也是一个不错的选择。如果在AWS上面,可以考虑使用ELB,但只能针对外网IP。

其实中心化的负载均衡方案,后续可以演化为无状态proxy方案,我们通过zookeeper或者其他coordinator来存储整个集群的路由信息,并通过2PC的方式同步更新到所有proxy上面,因为proxy是无状态,所以非常方便的进行水平扩展。当然proxy的发现也是一个问题,我们可以使用DNS,也可以使用LVS。

服务自己内部注册并发现

其实依赖zookeeper等协调服务来处理的。服务会自己注册到zookeeper上面,其他的服务节点通过zookeeper的watch方式实时的感知到整个集群的变化。

当然,使用这种方式也是有限制的。如果我们使用同一种语言进行开发,譬如java,那么每个服务嵌入一个zookeeper的client library是很容易的,但如果用了不同的语言,譬如有go,node.js,等等,让所有服务都能很好的跟zookeeper进行交互就比较困难了。

同时,如果我们希望一些其他第三方应用(譬如Nginx)也能享受到zookeeper的好处,这就比较麻烦了,因为这些服务压根不支持zookeeper。

另外,即使zookeeper存储了整个路由信息,我们仍然没有很好的办法定制路由算法,即使连最简单地round-robin都没法很好的支持,譬如一个客户端将第一个请求发给了第一个节点,如何将第二个请求发给第二个节点?

总之,单纯地使用zookeeper是不可能的,但正如我在前面说的,我们可以引入一个无状态的proxy,由proxy负责跟zookeeper打交道。

SmartStack: Nerve and Synapse

Airbnb列出了通用的三种不可取的做法,我想他们应该是都尝试过并且踩了坑,所以才有了后续的SmartStack。:-)

SmartStack由两个模块构成,nerve和synapse,当然还依赖zookeeper和haproxy。

部署的时候,service跟nerve一起部署,client则跟synapse以及local haproxy一起部署。

nerve负责管控其对应的service,并通过ephemeral的方式挂载到zookeeper上面,这样如果nerve所在的机器当掉,或者nerve负责的service挂掉了(nerve会每隔一段时间进行service存活检测),nerve与zookeeper的连接就会断开,外部就能感知节点的动态变更了。

synapse负责watch zookeeper的变更,当获取到节点变更事件之后,将最新的路由信息更新到本机local haproxy上面,客户端要访问对应的service,都是通过local haproxy路由到相应节点进行访问。

可以看到,SmartStack是一个非常简单地实现方式,但是它很好的解决了分布式系统中服务的发现与注册问题。SmartStack通过nerve进行服务的注册以及注销,通过synapse + local haproxy的方式进行服务的发现。如果一个client要访问对应的服务,只能通过local haproxy,这里local haproxy有点类似于中心化的负载均衡器,但是它仅仅限于本机,所以不存在DNS以及单点等问题。

SmartStack的不足

SmartStack的实现是很巧妙的,并且非常的简单,但是它也有一些自身的问题,最主要的就是友好的可用性问题。这套系统依赖了zookeeper,需要额外部署nerve,synapse以及local haproxy,运维上面略显复杂,相比较而言,Consul(Hashicorp的分布式服务发现程序)就只有一个二进制文件,部署更加方便。(后续如果有时间,可以写写SmartStack vs Consul)

为什么我特别关注运维,主要在于现在我们开发的一个分布式kv:RebornDB也存在同样的问题,运维步骤略显繁琐,导致很多时候我们开发自己都烦如何很好的构建一个可运行环境。

不过,这年头,因为有了docker以及mesos,kubernate等技术,没准运维的复杂度会降低很多。

总结

总的来说,SmartStack是一个很好的服务发现解决方案,原理非常简单,但功能却很强大。不过,如果我们将local haproxy往上提升变成一个haproxy cluster,这不就跟我前面说的无状态proxy差不多呢?没准后续也可以用go整一个出来,毕竟SmartStack的ruby代码看得我挺头大的。 

浮点数字节序比较

在开发LedisDB的时候,我曾考虑将zset的score使用跟redis一样的double类型,但是却没想好如何将double在底层LevelDB或者RocksDB下存储,使其能够支持zset中zrangebyscore等命令,所以只能考虑使用int64类型来代替。但在开发qdb的时候,最开始我们仍然只是支持int64,但最终通过努力,支持了double,使其能跟redis的zset api完全兼容。其实后来发现,实现很简单。

LevelDB和ZSet

这里需要简单说明一下LevelDB(RocksDB只是它的一个衍生优化版本,但最核心基本的原理还是一样的)。

LevelDB是一个高性能的KV存储库,数据在LevelDB里面是根据key来进行排序存储的,而key和value是任意的字节数组。在外部看来,LevelDB里面的数据就是一个有序map,map里面的key是顺序存储的,如下:

{
    "key1" : "value1",
    "key2" : "value2",
    ...
}

在redis里面,zset是一个有序集合,每一个member都对应一个score,member是唯一的,score则可能重复。我们可以通过score进行很多处理,譬如获取[score1, score2]这个区间的所有元素,或者获取某个member对应的score再整个zset里面的rank。为了实现上面的需求,我们需要在内部用一个有序的数据结构来存储score以及其对应的member,redis使用skip list来进行处理,那如何将这样的映射关系在LevelDB里面很好的处理呢?

因为LevelDB将数据是按照key顺序存储的,所以我们只需要将score的信息绑定到key上面,就能很容易的实现一个简易的skip list。对于一个zset里面的member,可能在LevelDB里面实际的key结构如下:

key:score:member

对于一个zset来说,key和member都是arbitrary bytes array,可以很方便的绑定到LevelDB的key上面,但是score可是double的,如何绑定上去参与排序呢?

LedisDB ZSet int64 score

再说double之前,先来聊聊LedisDB的做法,LedisDB使用的score是int64,对于一个int64来说,计算机内部是使用8 bytes进行存储的,下面是例子,会打印不同int64数据在小端序和大端序下8字节array十六进制表现:

import "fmt"
import "math"
import "encoding/binary"

func p(a int64) {
    b1 := make([]byte, 8)
    b2 := make([]byte, 8)

    binary.LittleEndian.PutUint64(b1, uint64(a))
    binary.BigEndian.PutUint64(b2, uint64(a))

    fmt.Printf("%0x\t%0x\n", b1, b2)
}

func main() {
    p(0)
    p(1)
    p(0xFFFF0000)
    p(math.MaxInt64)

    p(-1)
    p(-200)
    p(-300)
    p(math.MinInt64)
}

输出结果如下:

0000000000000000    0000000000000000

0100000000000000    0000000000000001
0000ffff00000000    00000000ffff0000
ffffffffffffff7f    7fffffffffffffff

ffffffffffffffff    ffffffffffffffff
38ffffffffffffff    ffffffffffffff38
d4feffffffffffff    fffffffffffffed4
0000000000000080    8000000000000000

第一列是小端序打印的结果,第二列是大端序打印的结果。首先我们可以看到,对于0来说,无论什么端序,都是全0,对于正整数来说,我们可以看到,0xFFFF0000是铁定大于1的,但是在对应的小端序存储的bytes array里面,会发现如果按照字节序进行排序0100000000000000是大于0000ffff00000000的,而大端序的结果0000000000000001是小于00000000ffff0000的。对于负整数也是一样,-200是大于-300的,但是小端序的结果是小于,而大端序的结果是大于。

所以我们可以知道,对于一个整数,我们需要使用大端序的方式将其绑定到LevelDB的key上面,这样才能参与正常的排序。但是我们又发现,如果直接这样处理,负数的大端序结果是铁定大于正数的,譬如-1的ffffffffffffffff就大于1的0000000000000001,所以为了正常的处理整数的排序,我们只需要在key上面加一个前缀标志就可以了。LedisDB里面做了如下处理:

key<38ffffffffffffff:member
key<ffffffffffffffff:member
key=0000000000000000:member
key=0000000000000001:member

因为=的ascii值大于<,我们将正整数和0前面加上=,将负数前面加上<,这样在进行字节序排序的时候,正数和0一定能排在负数的后面,也就是完全能满足从小到大排序的需求了。

QDB ZSet double score

上面可以知道,我们使用大端序加上一个前缀标志,就能很好的处理int64类型的score的排序,但double可没有这么简单,不然LedisDB早就支持了。

首先我们来看看double类型IEEE754规范,对于一个double来说,使用8 bytes存储,格式如下:

  • 符号: 1 bit (0为正,1为负)
  • 指数: 11 bits
  • 分数: 52 bits

double format

对于一个64 bits的double,如果指数为e,那么它对应的值计算方式为:

如果指数越大,那么double的值越大,如果分数越大,在相同指数的情况下面double值也越大。所以我们如果将double使用大端序存放到8字节array里面,我们就能直接进行字节序比较,但这个仅限于正的double情况下。因为对于负的double,它除了最高位bit为1这一点不一样之外,其余完全跟相反的正数底层存储方式一模一样,所以如果我们直接将其转为大端序比较,会发现结果是相反的。一个简单地例子:

func d(a float64) {
    b := make([]byte, 8)

    binary.BigEndian.PutUint64(b, math.Float64bits(a))

    fmt.Printf("%064b\n", binary.BigEndian.Uint64(b))
}

func main() {
    d(0)

    d(1)
    d(2)

    d(-1)
    d(-2)
}

结果如下:

0000000000000000000000000000000000000000000000000000000000000000
0011111111110000000000000000000000000000000000000000000000000000
0100000000000000000000000000000000000000000000000000000000000000
1011111111110000000000000000000000000000000000000000000000000000
1100000000000000000000000000000000000000000000000000000000000000

这里在插入一片广告文章,推荐阅读,这里

当初LedisDB就是因为没有办法很好的处理负double的排序比较问题,才采用了int64,但是真的没有办法吗?为啥int64类型的负数能通过大端序进行字节序比较呢?我们知道,在计算机内部,负数是使用补码存储的,也就是反码加1,负数的反码,就是在源码的基础上,符号位不变,其余各个位取反。对于-1来说,它的源码为[10000001],反码为[11111110],补码为[11111111]。(为了简单,使用int8表示的)。就因为它有了取反的这一步,我们才能直接用大端序字节序比较。

所以对于double的负数,我们也仅仅需要干一件事情,就是取反,那么它的大端序字节序比较就是正常的了。在QDB里面,对于一个double,我们做了如下处理:

// We can not use lexicographically bytes comparison for negative and positive float directly.
// so here we will do a trick below.
func float64ToUint64(f float64) uint64 {
    u := math.Float64bits(f)
    if f >= 0 {
        u |= 0x8000000000000000
    } else {
        u = ^u
    }
    return u
}

func uint64ToFloat64(u uint64) float64 {
    if u&0x8000000000000000 > 0 {
        u &= ^uint64(0x8000000000000000)
    } else {
        u = ^u
    }
    return math.Float64frombits(u)
}

如果一个double数据值大于等于0,那么我们将最高位bit设置为1,而对于负数,我们直接取反,就这一步简单的操作,就能让我们完美的支持double的score了。

总结

让QDB的zset支持double score,其实很简单的一件事情,但我在开发LedisDB的时候竟然没有想到如何去解决。我们很多时候,往往追求高大上的东西,譬如架构,设计模式等,但忽略了计算机最基本的底层知识(上面这些其实也就是大小端序,补码,反码等),所以有时候还真的重新好好把最基本的东西给回顾一下。

最后,在推荐一下QDB,QDB是一个类似Redis的KV数据库,底层使用LevelDB/RocksDB作为存储引擎,解决了Redis内存限制问题,同时能支持string,hash,list,set和zset这几种数据结构,性能卓越,你也可以认为它是LedisDB的升级版本。

网址 https://github.com/reborndb/qdb。 

我为什么从python转向go

应puppet大拿刘宇的邀请,我去西山居运维团队做了一个简短分享,谈谈为什么我要将我们的项目从python转向go。

坦白的讲,在一帮python用户面前讲为什么放弃python转而用go其实是一件压力蛮大的事情,语言之争就跟vim和emacs之争一样,是一个永恒的无解话题,稍微不注意就可能导致粉丝强烈地反击。所以我只会从我们项目实际情况出发,来讲讲为什么我最终选择了go。

为什么放弃python

首先,我其实得说说为什么我们会选择python。在我加入企业快盘团队之前,整个项目包括更早的金山快盘都是采用python进行开发的。至于为什么这么选择,当时的架构师葱头告诉我,主要是因为python上手简单,开发迅速。对于团队里面大部分完全没服务端开发经验的同学来说,python真的是一个很好的选择。

python的简单高效,我是深有体会的。当时私有云项目也就几个程序员,但是我们要服务多家大型企业,进行定制化的开发,多亏了python,我们才能快速出活。后来企业快盘挂掉之后,我们启动轻办公项目,自然也使用python进行了原始版本的构建。

python虽然很强大,但我们在使用的时候也碰到了一些问题,主要由如下几个方面:

  • 动态语言

    python是一门动态强类型语言。但是,仍然可能出现int + string这样的运行时错误,因为对于一个变量,在写代码的时候,我们有时候很容易就忘记这个变量到底是啥类型的了。

    在python里面,可以允许同名函数的出现,后一个函数会覆盖前一个函数,有一次我们系统一个很严重的错误就是因为这个导致的。

    上面说到的这些,静态语言在编译的时候就能帮我们检测出来,而不需要等到运行时出问题才知道。虽然我们有很完善的测试用例,但总有case遗漏的情况。所以每次出现运行时错误,我心里都想着如果能在编译的时候就发现该多好。

  • 性能

    其实这个一直是很多人吐槽python的地方,但python有它适合干的事情,硬是要用python进行一些高性能模块的开发,那也有点难为它了。

    python的GIL导致无法真正的多线程,大家可能会说我用多进程不就完了。但如果一些计算需要涉及到多进程交互,进程之间的通讯开销也是不得不考虑的。

    无状态的分布式处理使用多进程很方便,譬如处理http请求,我们就是在nginx后面挂载了200多个django server来处理http的,但这么多个进程自然导致整体机器负载偏高。

    但即使我们使用了多个django进程来处理http请求,对于一些超大量请求,python仍然处理不过来。所以我们使用openresty,将高频次的http请求使用lua来实现。可这样又导致使用两种开发语言,而且一些逻辑还得写两份不同的代码。

  • 同步网络模型

    django的网络是同步阻塞的,也就是说,如果我们需要访问外部的一个服务,在等待结果返回这段时间,django不能处理任何其他的逻辑(当然,多线程的除外)。如果访问外部服务需要很长时间,那就意味着我们的整个服务几乎在很长一段时间完全不可用。

    为了解决这个问题,我们只能不断的多开django进程,同时需要保证所有服务都能快速的处理响应,但想想这其实是一件很不靠谱的事情。

  • 异步网络模型

    tornado的网络模型是异步的,这意味着它不会出现django那样因为外部服务不可用导致这个服务无法响应的问题。话说,比起django,我可是非常喜欢tornado的,小巧简单,以前还写过几篇深入剖析tornado的文章了。

    虽然tornado是异步的,但是python的mysql库都不支持异步,这也就意味着如果我们在tornado里面访问数据库,我们仍然可能面临因为数据库问题造成的整个服务不可用。

    其实异步模型最大的问题在于代码逻辑的割裂,因为是事件触发的,所以我们都是通过callback进行相关处理,于是代码里面就经常出现干一件事情,传一个callback,然后callback里面又传callback的情况,这样的结果就是整个代码逻辑非常混乱。

    python没有原生的协程支持,虽然可以通过gevent,greenlet这种的上patch方式来支持协程,但毕竟更改了python源码。另外,python的yield也可以进行简单的协程模拟,但毕竟不能跨堆栈,局限性很大,不知道3.x的版本有没有改进。

  • 开发运维部署

    当我第一次使用python开发项目,我是没成功安装上项目需要的包的,光安装成功mysql库就弄了很久。后来,是一位同事将他整个python目录打包给我用,我才能正常的将项目跑起来。话说,现在有了docker,是多么让人幸福的一件事情。

    而部署python服务的时候,我们需要在服务器上面安装一堆的包,光是这一点就让人很麻烦,虽然可以通过puppet,salt这些自动化工具解决部署问题,但相比而言,静态编译语言只用扔一个二进制文件,可就方便太多了。

  • 代码失控

    python非常灵活简单,写c几十行代码才能搞定的功能,python一行代码没准就能解决。但是太简单,反而导致很多同学无法对代码进行深层次的思考,对整个架构进行细致的考量。来了一个需求,啪啪啪,键盘敲完开速实现,结果就是代码越来越混乱,最终导致了整个项目代码失控。

    虽然这也有我们自身的原因,譬如没好的代码review机制,没有好的项目规范,但个人感觉,如果一个程序员没经过良好的编码训练,用python很容易就写出烂的代码,因为太自由了。

    当然,我这里并不是说用python无法进行大型项目的开发,豆瓣,dropbox都是很好的例子,只是在我们项目中,我们的python代码失控了。

上面提到的都是我们在实际项目中使用python遇到的问题,虽然最终都解决了,但是让我愈发的觉得,随着项目复杂度的增大,流量性能压力的增大,python并不是一个很好的选择。

为什么选择go

说完了python,现在来说说为什么我们选择go。其实除了python,我们也有其他的选择,java,php,lua(openresty),但最终我们选择了go。

虽然java和php都是最好的编程语言(大家都这么争的),但我更倾向一门更简单的语言。而openresty,虽然性能强悍,但lua仍然是动态语言,也会碰到前面说的动态语言一些问题。最后,前金山许式伟用的go,前快盘架构师葱头也用的go,所以我们很自然地选择了go。

go并不是完美,一堆值得我们吐槽的地方。

  • error,好吧,如果有语言洁癖的同学可能真的受不了go的语法,尤其是约定的最后一个返回值是error。项目里面经常会充斥这样的代码:

      if _, err := w.Write(data1); err != nil {
          returun err
      }
      if _, err := w.Write(data2); err != nil {
          returun err
      }
    

    难怪有个梗是对于一个需求,java的程序员在写配置的时候,go程序员已经写了大部分代码,但是当java的程序员写完的时候,go程序员还在写err != nil

    这方面,errors-are-values倒是推荐了一个不错的解决方案。

  • 包管理,go的包管理太弱了,只有一个go get,也就是如果不小心更新了一个外部库,很有可能就导致现有的代码编译不过了。虽然已经有很多开源方案,譬如godep以及现在才出来的gb等,但毕竟不是官方的。貌似google也是通过vendor机制来管理第三方库的。希望go 1.5或者之后的版本能好好处理下这个问题。

  • GC,java的GC发展20年了,go才这么点时间,gc铁定不完善。所以我们仍然不能随心所欲的写代码,不然在大请求量下面gc可能会卡顿整个服务。所以有时候,该用对象池,内存池的一定要用,虽然代码丑了点,但好歹性能上去了。

  • 泛型,虽然go有inteface,但泛型的缺失会让我们在实现一个功能的时候写大量的重复代码,譬如int32和int64类型的sort,我们得为分别写两套代码,好冗余。go 1.4之后有了go generate的支持,但这种的仍然需要自己根据go的AST库来手动写相关的parser,难度也挺大的。虽然也有很多开源的generate实现,但毕竟不是官方的。

当然还有很多值得吐槽的地方,就不一一列举了,但是go仍旧有它的优势。

  • 静态语言,强类型。静态编译能帮我们检查出来大量的错误,go的强类型甚至变态到不支持隐式的类型转换。虽然写代码感觉很别扭,但减少了犯错的可能。
  • gofmt,应该这是我知道的第一个官方提供统一格式化代码工具的语言了。有了gofmt,大家的代码长一个样了,也就没有花括号到底放到结尾还是新开一行这种蛋疼的代码风格讨论了。因为大家的代码风格一样,所以看go的代码很容易。
  • 天生的并行支持,因为goroutine以及channel,用go写分布式应用,写并发程序异常的容易。没有了蛋疼的callback导致的代码逻辑割裂,代码逻辑都是顺序的。
  • 性能,go的性能可能赶不上c,c++以及openresty,但真的也挺强悍的。在我们的项目中,现在单机就部署了一个go的进程,就完全能够胜任以前200个python进程干的事情,而且CPU和MEM占用更低。
  • 运维部署,直接编译成二进制,扔到服务器上面就成,比python需要安装一堆的环境那是简单的太多了。当然,如果有cgo,我们也需要将对应的动态库给扔过去。
  • 开发效率,虽然go是静态语言,但我个人感觉开发效率真的挺高,直觉上面跟python不相上下。对于我个人来说,最好的例子就是我用go快速开发了非常多的开源组件,譬如ledisdb,go-mysql等,而这些最开始的版本都是在很短的时间里面完成的。对于我们项目来说,我们也是用go在一个月就重构完成了第一个版本,并发布。

实际项目中一些Go Tips

到现在为止,我们几乎所有的服务端项目都已经转向go,当然在使用的时候也遇到了一些问题,列出来算是经验分享吧。

  • godep,我们使用godep进行第三方库管理,但是godep我碰到的最大的坑就是build tag问题,如果一个文件有build tag,godep很有可能就会忽略这个文件。
  • IO deadline,如果能自己在应用层处理的都自己处理,go的deadline内部是timer来控制,但timer内部采用一个array来实现的heap,全局共用一个锁,如果大并发量,并且timer数量过多,timeout变动太频繁,很容易就引起性能问题。
  • GC,这个前面也说了,多用内存池,对象池,另外,我还发现,如果对象的生命周期跟goroutine一致,对性能的提升也不错,也在go的group问过相关问题,大家猜测可能是因为一些对象其实是在goroutine的8k栈上面分配的,所以一起回收没有额外GC了。
  • Go gob,如果要做RPC服务,gob并不是一个很好的选择,首先就跟python的pickle不通用,然后为了做不同系统的数据传入,任何包都必须带上类型的详细信息,size太大。go里面现在还没一套官方的RPC方案,gRPC貌似有上位的可能。

总结

虽然我现在选择了go,但是并不表示我以后不会尝试其他的语言。语言没有好坏,能帮我解决问题的就是好语言。但至少在很长的一段时间,我都会用go来进行开发。Let’ go!!!

Use Hashicorp Raft to build a Redis sentinel

Redis Sentinel

We use Redis not only for cache, but also storing important data, and we build up a Master/Slave replication topology to guarantee data security.

Master/Slave architecture works well, but sometimes we need a more powerful high availability solution. If master is down, we must check this immediately, reselect a new master from the slaves and do failover.

The official Redis supplies a solution named redis-sentinel, which is very powerful to use. But I still want to build my own sentinel solution, why?

  • I want to monitor not only Redis but also LedisDB, maybe other services using Redis serialization Protocol too.
  • I want to embed it into xcodis or other go service easily.
  • I want to study some consensus algorithms and use them in practice.
    Sentinel Cluster and Election

Building a single sentinel application is easy: checking master every second, and do failover when master is down. But if the sentinel is down too, how do we do?

Using sentinel cluster is a good choice, if one sentinel is down, other sentinel will still work. But let’s consider below scenario, if two sentinels in the cluster both see the master is down, and do failover at same time, sentinel1 may select slave1 as master, but sentinel2 may select slave2 as master, this may be a horrible thing for us.

A common use way is to elect a leader sentinel in the cluster and let it monitor and do failover. So we need a consensus algorithm helping us do this thing.

Paxos and Raft

Paxos may be the most famous consensus algorithm in the world, many companies use it in their distributed system. However, Paxos is very hard to understand and if you write a paxos lib by yourself, you even cann’t testify its correctness easily. Luckly, we have zookeeper, an open source centralized service based on Paxos. We can use zookeeper to manage our clusters like electing a leader.

Raft was born on 2013 in Stanford, it’s very new but awesome. Raft is easy to understand, everyone reading the Raft paper can write its own Raft implentation easily than Paxos. Now many projects use Raft, like Etcd, InfluxDB, CockroachDB, etc…

The above projects I list using Raft all use Go, and I will develop my own redis sentinel with Go too, so I decide to use Raft.

Use Hashicorp Raft

There are some Go raft projects, but I prefer Hashicorp Raft which is easy to be integrated in other project, and this package is used in Consul product and has already been tested in production environment (maybe!).

The create raft function declaration is below:

func NewRaft(conf *Config, fsm FSM, logs LogStore, stable StableStore, snaps SnapshotStore, peerStore PeerStore, trans Transport) (*Raft, error)

Although it looks a little complex, it’s still easy to use, we only need do following things:

  • Create a configuration using raft own DefaultConfig function. We should know that raft should be used with at least three nodes, but if we just want to try it with only one node, or first start a raft node, than add others later, we must set EnableSingleNode to true.
  • Define our own FSM struct, FSM is a state machine applying replicated log, generating point-in-time snapshot, and restoring from a snapshot. In our sentinel, the only data need to care is all Redis masters, whenever we add a master, remove a master or reset all masters, we should let all sentinels know. So my FSM struct is very easy, like below:
type masterFSM struct {
    sync.Mutex

    // below holding all Redis master addresses
    masters map[string]struct{}
}
  • Define our own FSMSnapshot struct. In our sentinel, this is a list of masters at some point. The struct like this:
type masterSnapshot struct {
    masters []string
}
  • Create a log storage storing and retrieving logs and a stable storage storing key configurations. Hashicorp supplies a LMDB lib and a BoltDB lib for both storage, we use BoltDB because of the pure Go implementation.
  • Create a snapshot storage saving FSM snapshot, we use raft own NewFileSnapshotStore generating a file saving this.
  • Create a peer storage storing all raft nodes, we use raft own NewJSONPeers generating a file saving all nodes with JSON format.
  • Create a transport allowing a raft node to communicate with other nodes, we use raft own NewTCPTransport generating a TCP transport.

After do that, we can create a raft, we can use LeaderCh and Leader function to check whether a raft node is leader or not. Only the leader node can handle operations. If the leader is down, raft can re-elect a new leader.

You can see the source here for more information.

Summary

Our redis sentinel is named redis-failover, although it looks a little simple and needs improvement, it still the first trial and later we will use raft in more projects, maybe instead of zookeeper.

redis-failover: https://github.com/siddontang/redis-failover

构建一个简易的中心化锁服务

为什么需要锁服务?

有时候,在分布式系统中,不同的服务实例需要操作同一份资源,所以我们需要一套机制保证对该资源并发操作的数据一致性。

最通常的做法,就是lock。各个服务在操作资源之前,首先lock住该资源,处理完成之后在释放lock。也就是说,我们通过lock使得并行操作串行化,保证了资源的数据一致性。

为什么要实现重新实现一个?

虽然现在有很多不错的锁服务实现,譬如基于Zookeeper,Etcd,甚至Redis,但这里我仍然想自己实现一个简易的lock服务,主要有以下几点原因:

Multi Lock

同时获取多个lock,有时候我们想同时对多个资源进行操作,所以需要多把lock,但是无论是Zookeeper还是Redis,我们都需要对其进行多次调用,影响整体性能。

Hierarchical Lock

支持hierarchical lock,我称之为path lock,我们的系统是有类似文件夹的概念的,假设现在我们需要往文件夹a/b/c下面增加一个文件,我们就必须得保证另一个进程不会同时操作该文件夹以及其祖先和后继(譬如删除a,或者a/b,或者也往a/b/c下面增加文件),但是允许操作其兄弟(譬如在a/b/d下面增加文件)。

仍然是上面那个例子,假设我们需要操作a/b/c,首先我们需要对a加read lock,然后对a/b加read lock,最后在对a/b/c加write lock,如果这个通过Zookeeper来实现,真心很麻烦,而且性能存疑。

TLock

tlock是一个简单的中心化lock service,现阶段为了性能没有High Availability支持,所以如果当掉了后果还是有点严重的。:-)

tlock支持两种模式,key和path,key就是最通常的对某个资源进行操作,而path则是我上面说的Hierarchical Lock。同时tlock支持Multi Lock。

tlock提供Restful API以及RESP(Redis Serialization Protocol) API,所以你可以通过任意HTTP客户端或者Redis客户端使用。

一个简单的HTTP例子:

// shell1

// 同时lock a,b,c三个资源,如果30s之后仍没lock成功,返回超时错误
// 返回lockid供后续unlock使用
POST http://localhost/lock?names=a,b,c&type=key&timeout=30

// Unlock
DELETE http://localhost/lock?id=lockid

// shell2
POST http://localhost/lock?names=a,b,c&type=key&timeout=30

DELETE http://localhost/lock?id=lockid

一个简单的RESP例子:

# shell1 redis-cli
redis>LOCK abc TYPE key TIMEOUT 10
redis>lockid
redis>UNLOCK lockid
redis>OK

# shell2 redis-cli 
redis>LOCK abc TYPE key TIMEOUT 10
// 一直挂起直到shell1 unlock 
redis>lockid
redis>UNLOCK lockid
redis>OK

tlock同时提供了RESP的客户端:

import "github.com/siddontang/tlock"

client := NewRESPClient(addr)
locker, _ := client.GetLocker("key", "abc")
locker.Lock()
locker.Unlock()

Todo

可以看到,tlock是一个非常简单的服务,虽然是一个单点并且没有HA支持,但是已经能满足我们项目的需求,毕竟我们只是需要一个简单的锁服务。

后续,我可能会基于Zookeeper尝试实现path lock,虽然这样HA能够保证,但是性能怎样,到时候压测了再说吧。

Dive into MySQL Replication

Dive into MySQL replication protocol

Preface

Let’s consider following scenario, we store huge data in MySQL and want to know data changes immediately(data inserted, deleted or updated), then do something for these changes like updating associated cache data.

Using MySQL trigger + UDF may be a feasible way, but I have not used it and would not recommend this. If we have many tables, maintaining so many triggers is horrible. At the same time, UDF may fail so that we will lost some changes, and even worse, a bad UDF implementation may block service or even crash MySQL.

We need a better solution, and this is binlog. MySQL records every changes into binlog, so if we can sync the binlog, we will know the data changes immediately, then do something.

Using rsync may be a good way, but I prefer another: acting as a slave and using MySQL replication protocol to sync.

MySQL Packet

First, we must know how to send or receive data with MySQL, and this is packet:

Split the data into packets of size 16MB.
Prepend to each chunk a packet header.

A packet header has 3 bytes for following payload data length and 1 byte for sequence ID.

The sequence ID is incremented with each packet between client and server communication, it starts at 0 and is reset to 0 when a new command begins, e.g, we send a packet, the sequence ID is 0, and the response packet sequence ID must be 1, if not, some error happens between the communication.

So a packet looks like below:

3              payload length
1              Sequence ID
string[len]    payload

As you see, sending data with packet is very easy, I have implemented a base library in go-mysql packet pkg.

Connection phase

When we first connect to MySQL server, we must do a handshake to let server authorizing us to communicate with it later, this is called connection phase.

Let’s consider a popular common connection phase.

  • Client connects server using socket connect API.
  • Server sends a initial handshake packet which contains server’s capabilities and a 20 bytes random salt.
  • Client answers with a handshake response packet, telling server its capabilities and a 20 bytes scrambled password.
  • Server response ok packet or err packet.

Although MySQL supports many authentication method, I only use username + password, you can see codes in go-mysql client and server pkg.

Now we know how to send/receive data, how to establish the connection, and it’s time to move on for syncing binlog. :-)

Register a Slave

When we want to sync binlog, we must register a slave at master first, that is acting as a pseudo slave.

We only need to send COM_REGISTER_SLAVE command, the payload is:

1              COM_REGISTER_SLAVE
4              server-id
1              slaves hostname length
string[$len]   slaves hostname
1              slaves user len
string[$len]   slaves user
1              slaves password len
string[$len]   slaves password
2              slaves mysql-port
4              replication rank
4              master-id

We must use an unique server id for our pseudo slave, I prefer using a ID bigger than 1000 which is different from our real MySQL servers.

Dump BinLog from master

After register, we should send COM_BINLOG_DUMP command, it is very easy too, payload is:

1              COM_BINLOG_DUMP
4              binlog-pos
2              flags
4              server-id
string[EOF]    binlog-filename

If the binlog filename is empty, server will use the first known binlog.

You can set flags to 1 to tell server to reply a EOF packet instead of blocking connection if there is no more binlog event. But I prefer blocking so that if there is any new event, server can send to us immediately.

Although MySQL supports COM_BINLOG_DUMP_GTID commands, I still prefer using command binlog filename + position, because it is very easy and for our pseudo slave, we only need to sync binlog, save it in a place and let other applications like MHA use it.

After we send COM_BINLOG_DUMP command, server will response a binlog network stream which contains many binlog events.

BinLog Event

A MySQL binlog event has many versions, but we only care version 4(MySQL 5.0+) and don’t support earlier versions.

A binlog event contains three parts, header, post header and payload, but I like parsing post header and payload at same time.

A event header looks below:

4              timestamp
1              event type
4              server-id
4              event-size
4              log pos
2              flags

You can see all binlog event types here. The log pos is position of the next event, we can save this position for resuming syncing later.

The first binlog event in the binlog file is FORMAT_DESCRIPTION_EVENT, this event is very important, we use it to determine table ID size for row based event, and check the last 5 bytes to see whether CRC32 is enabled or not for the following events, etc…

Another event we should care is ROTATE_EVENT, it tells us a new binlog coming.

Parsing a binlog event is very easy, we only need to refer the document and parse it one by one, except row based replication event.

Row Based Replication

Parsing row based replication event is very hard if we want to know the real data changes for a column in one row.

First, we must parse TABLE_MAP_EVENT, payload is:

post-header:
    if post_header_len == 6 {
  4              table id
    } else {
  6              table id
    }
  2              flags

payload:
  1              schema name length
  string         schema name
  1              [00]
  1              table name length
  string         table name
  1              [00]
  lenenc-int     column-count
  string.var_len [length=$column-count] column-def
  lenenc-str     column-meta-def
  n              NULL-bitmask, length: (column-count + 8) / 7

The post_header_len is saved in FORMAT_DESCRIPTION_EVENT, column count and def tells us how many columns in one row and their data types, like tiny int, short int, float, set, etc. column meta def is tricky, but we must use it to parse following ROWS_EVENT.

A ROWS_EVENT contains WRITE_ROWS_EVENT(insert), DELETE_ROWS_EVENT(delete) and UPDATE_ROWS_EVENT(update), every event contains v0, v1 and v2 three versions, most of time, we only need to care v1 and v2.

A ROWS_EVENT looks below:

header:
  if post_header_len == 6 {
4                    table id
  } else {
6                    table id
  }
2                    flags
  if version == 2 {
2                    extra-data-length
string.var_len       extra-data
  }

body:
lenenc_int           number of columns
string.var_len       columns-present-bitmap1, length: (num of columns+7)/8
  if UPDATE_ROWS_EVENTv1 or v2 {
string.var_len       columns-present-bitmap2, length: (num of columns+7)/8
  }

rows:
string.var_len       nul-bitmap, length (bits set in 'columns-present-bitmap1'+7)/8
string.var_len       value of each field as defined in table-map
  if UPDATE_ROWS_EVENTv1 or v2 {
string.var_len       nul-bitmap, length (bits set in 'columns-present-bitmap2'+7)/8
string.var_len       value of each field as defined in table-map
  }
  ... repeat rows until event-end

I promise that if you don’t dive into the MySQL source, you can not understand how to parse it at all.

First, let’s see columns-present-bitmap, for a column, it will not be saved in the row data if the associated bit in columns-present-bitmap is 0, and we will skip this column when parsing.

For every row data, first we should calculate the null-bitmap, a big pitfall here, we calculate columns-present-bitmap using (num of columns+7)/8, but we must use (bits set in ‘columns-present-bitmap’+7)/8 for null-bitmap. (You should google bits set if you don’t understand it).

From MySQL 5.6, it supports another two binlog row images: minimal and noblob. For minimal row image update, if we have 16 columns and only the first column data changed, if we use (num of columns+7)/8, we should use 2 bytes to store null bitmap, but if we use (bits set in ‘columns-present-bitmap’+7)/8, we will only use 1 bytes to store null bitmap, saving 1 byte(is it really necessary?). By the way, I sent a pull request for python-mysql-replication to handle minimal and noblob row image paring.

Now we get column-present-bitmap and null-bitmap, for a column, if it’s not set in column-present-bitmap or set in null-bitmap, we will know that this column is null for the current row data.

Then we will parse the rest of none null columns. For some special columns, like MYSQL_TYPE_LONG or MYSQL_TYPE_FLOAT, we can know the data length directly, e.g, MYSQL_TYPE_LONG is 4 bytes and MYSQL_TYPE_TINY_INT is 1 byte.

But for other columns, we should use column meta in TABLE_MAP_EVENT to help us determine the data length. For example, a MYSQL_TYPE_BLOB column, if meta is 1, the data is tiny blob and the first 1 byte in data is the length for payload, if meta is 2, the data is short blob and the first 2 bytes is the lenght for payload.

Paring the real data is very hard and I can not illustrate here fully and clearly. I hope you can see the source in MySQL or go-mysql replication pkg if you have some interest.

Semi Sync Replication

At first, I didn’t support semi sync replication in go-mysql, but after I develop go-mysql-elasticsearch, I realize that if I want to sync MySQL changes into elasticsearch more quickly and immediately, supporting semi sync replication is a good choice and it’s easy to do like below:

  • Check whether master supports semi sync or not, using “SHOW VARIABLES LIKE ‘rpl_semi_sync_master_enabled’”.
  • Tell master we support semi sync using “SET @rpl_semi_sync_slave = 1”.

If all is ok, server will prepend two byte before every binlog event. The first byte is 0xef indicating semi sync and the second byte is semi sync ACK flag, if 1, we must reply a semi sync ACK packet.

It now seems that this is a wise decision. In facebook, they even develop a semi sync binlog, you can see more here. I develop a similar go-mysqlbinlog supporting semi sync too, but it still needs improvement for production environment.

Summary

Learning mysql protocol is a hard but happy journey for me, and I have done some interesting things too, like mixer, a MySQL proxy which the modified version(cm) has been used in production in wandoujia company. go-mysql-elasticsearch, a tool to sync MySQL data into elasticsearch immediately.

Now I have been developing go-mysql, a powerful MySQL toolset. I would be very glad if some people find it can help them for their own MySQL development too.

Later I will also try to use go-mysqlbinlog + MHA to build our own MySQL HA solution, I don’t know perl, but luckily, I can understand MHA code.

Below is my contact, any advice and feedback is very welcome.

  • Email: siddontang@gmail.com

  • Skype: live:siddontang_1

Build up a High Availability Distributed Key-Value Store

Preface

There are many awesome and powerful distributed NoSQL in the world, like Couchbase, MongoDB, Canssandra, etc. but developing a new one is still a challengeable, interesting and attractive thing for me, why?

  • It can satisfy our special needs for our cloud services.
  • We just need a key-value store, with some simple additional functionalities, we don’t need a complex solution.
  • We can control the whole thing, especially for fixing bugs and improvement.
  • Inventing the wheel is not good, but I can learn much in the process.

A key-value store may need below features:

  • Simple protocol.
  • Simple API.
  • High performance.
  • High availability.
  • Cluster support.

I knew this would be a hard journey first. But after a long hard work, I develop ledis-cluster, a key-value store based on LedisDB + xcodis + redis-failover.

Pre Solution Thinking

Before I develop ledis-cluster, I thought some other solutions which are valuable to be recorded here too.

MySQL

Aha, first I just wanted to use MySQL as a key-value store. This thought amazed my colleagues before, and I think now it may surprise many other guys too.

MySQL is a relational database and can be used as a key-value store easily and sufficiently. We can use a simple table to store key value data like below:

CREATE TABLE kv (
    k varbinary(256),
    v blob,
    PRIMARY KEY(k),
) ENGINE=innodb;

When I worked in Tencent game infrastructure department, we used this way to serve many Tencent games and it works well.

But I don’t want to use MySQL as a key-value store now, MySQL is a little heavy and needs some experienced operations people, this is impossible for our team.

Redis

Redis is an awesome NoSQL, it has an amazing performance, supports many useful data structures (kv, hash, list, set and zset), supplies a simple protocol for client user.

I have read the Redis’s code (it is very simple!) many times, used it for about three years in many productions, and I am absolutely confident of maintaining it.

But Redis has a serious problem: memory limitation. We can not store huge data in one machine. Using redis cluster is a good way to solve memory limitation, and there are many existing solutions, like official redis cluster, twemproxy or codis , but I still think another stuff saving huge data exceeding memory limitation in one machine is needed, so I develop LedisDB.

LedisDB

LedisDB is a fast NoSQL, similar to Redis. It has some good features below:

  • Uses Redis protocol, most of the Redis clients can use LedisDB directly.
  • Supports multi data structures(kv, hash, list, set, zset).
  • Uses rocksdb, leveldb or other fast databases as the backend to store huge data, exceeding memory limitation.
  • High performance, see benchmark. Although it is a little slower than Redis, it can still be used in production.

A simple example:

//start ledis server
ledis-server
//another shell
ledis-cli -p 6380
ledis> set a 1
OK
ledis> get a
“1"

As we see, LedisDB is simple, we can switch to it easily if we used Redis before.

LedisDB now supports rocksdb, leveldb, goleveldb, boltdb and lmdb as the backend storage, we can choose the best one for our actual environment. In our company projects, we use rocksdb which has a awesome performance and many configurations to be tuned, and I will also use it for the following example.

Data Security Guarantee

LedisDB can store huge data in one machine, so the data security needs to be considered cautiously. LedisDB uses below ways to guarantee it.

Backup

We can back up LedisDB and then restore later. Redis saving RDB may block service for some time, but LedisDB doesn’t have this problem. Thanks to rocksdb fast generating snapshot technology, backing up LedisDB is very fast and easy.

Binlog

LedisDB will first log write operations in binlog, then commit changes into backend storage, this is similar to MySQL.

Redis also has AOF, but the AOF file may grow largely, then rewriting AOF may also block service for some time. LedisDB will rotate binlog and write to the new one when current binlog is larger than maximum size (1GB).

Replication

An old saying goes like this: “don’t put all your eggs in one basket”. Similarly, don’t put all our data in one machine.

LedisDB supports asynchronous or semi-synchronous replication. We can not break CAP(Consistency, Availability, Partition tolerance) theorem, for replication, partition tolerance must exist, so we have to choose between consistency and availability.

If we want to guarantee full data security, we may use semi-synchronous replication, but most of time, asynchronous replication is enough.

Monitor and Failover

In the actual production environment, we use a master LedisDB and one or more slaves to construct the topology. We must monitor them in real time because any machine in the topology may be down at any time.

If a slave is down, we may not care too much, this is not a serious problem. But if the master is down (aha, a terrible accident!), we must resolve it quickly.

Generally, we can not expect the master to re-work quickly and infallibly, so electing a best new master from current slaves and doing failover is a better way when master is down.

Redis uses a sentinel feature to monitor the topology and do failover when the master is down. But this sentinel can not be used in LedisDB, so I develop another sentinel: redis-failover, monitoring and doing failover for Redis/LedisDB.

redis-failover uses ROLE command to check master and get all slaves every second. If the master is down, redis-failover will select the best slave from last ROLE returned slaves. The election algorithm is simple, using INFO command to get “slave_priority” and “slave_repl_offset” value, if a slave has a higher priority or a larger repliction offset with same priority, the slave will be elected as the new master.

redis-failover may have single point problem too, I use zookeeper or raft to support redis-failover cluster. Zookeeper or raft will elect a leader and let it monitor and do failover, if the leader is down, a new leader will be elected quickly.

Cluster

Although LedisDB can store huge data, the growing data may still exceed the capability of the system in the near future.

Splitting data and storing them into multi machines may be the only feasible way(We don’t have money to buy a mainframe), but how to split the data? and how to find the data by a key? I think an easy solution is to define a key routing rule (mapping key to the actual machine).

For example, we have two machines, n0 and n1, and the key routing rule is simple hash like crc32(key) % 2. For key “abc”, the calculation result is 0, so we know that the corresponding data is in n0.

The above solution is easy, but we can not use it in production. If we add another machine, the machine number is 3, all the old data mapping relationship will be broken, and we have to relocate huge amount of data.

Using consistency hash may be better, but I prefer using hash + routing table. We don’t map a key to a machine directly, but to a virtual node named slot, then define a routing table mapping slot to the actual machine.

Continuing with the example, assume we use 1024 slots and 2 machines, the slot and machine mapping is [slot0 — slot511] -> n0, [slot512 — slot1023] -> n1. For a key, first using crc32(key) % 1024 to get a slot index, then we can find the machine with this slot from the routing table.

This solution may be complex but have a big advantage for re-sharding. If we add another machine n2, change the routing table that mapping slot0 to n2, and we only need to migrate all slot0 data from n0 to n2. The bigger for slot number, the smaller for split data in a slot, and we only migrate little data for one slot.

xcodis uses above way to support LedisDB cluster. Now the slot number is 256, which is a little small that may increase the probability of mapping some busy keys into a slot.

Because of origin LedisDB db index implementation limitation, xcodis can not use bigger slot number than 256, so a better way is to support customizing a routing table for a busy key later. For example, for a key, xcodis should first try to find the associated slot in the routing table, if not found, then use hash.

Another radical choice is to change LedisDB code and upgrade all data saved before. This is may be a huge work, so I will not consider it unless I have no idea to resolve above problems.

xcodis is a proxy supporting redis/LedisDB cluster, the benefit of proxy is that we can hide all cluster information from client users and users can use it easily like using a single server.

In addition to proxy, there are also some other ways to support cluster too:

Official Redis cluster, but it is still in development and should not be used in production now, and it can not be used in LedisDB.
Customizing client SDK, the SDK can know whole cluster information and do the right key routing for the user. But this way is not universal and we must write many SDKs for different languages (c, java, php, go, etc.), a hard work!

Final Architecture

At last, the final architecture may look below:

kv architecture

  • Use LedisDB to save huge data in one machine.
  • Use Master/slave to guarantee data security.
  • Use redis-failover to monitor the system and do failover.
  • Use xcodis to support cluster.

This architecture may be not perfect, but is simple and enough for us. Now we have only use LedisDB and xcodis in our projects, not the whole architecture, but we have been testing and will try to deploy it in production in the near future.

Summary

Building up a key-value store is not a easy work, and I don’t think what I do above can beat other existing awesome NoSQLs, but it’s a valuable attempt, I have learned much and meet many new friends in the progress.

Now, I’am the only person to develop the whole thing and need help, if you have interested in what I do, please contact me, maybe we really can build up an awesome NoSQL. :-)

Mail: siddontang@gmail.com

Github: github.com/siddontang

构建高可用分布式Key-Value存储服务

前言

当我们构建服务端应用的时候,都会面临数据存放的问题。不同的数据类型有不同的存放方式,譬如关系型数据通常使用MySQL来存储,文档型数据则会考虑使用MongoDB,而这里,我们仅仅考虑最简单的kv(key-value)。

kv的使用场景很多,一个很典型的场景就是用户session的存放,key为用户当前的session id,而value则是用户当前会话需要保存的一些信息。因为kv的场景很多,所以选择一个好的kv服务就很重要了。

对于笔者来说,一个不错的kv服务可能仅仅需要满足如下几点就够了:

  • 协议简单
  • 高性能
  • 高可用
  • 易扩容

市面上已经有很多满足条件kv服务,但笔者秉着no zuo no die的精神,决定使用LedisDB + xcodis + redis-failover来构建一个高可用分布式kv存储服务。

现有解决方案

在继续说明之前,笔者想说说曾经考虑使用或者已经使用的一些解决方案。

MySQL

好吧,别笑,我真的说的是MySQL。MySQL作为一个关系型数据库,用来存储kv性能真心一点都不差。table的结构很简单,可能如下:

CREATE TABLE kv (
    k VARBINARY(256),
    v BLOB,
    PRIMARY KEY(k),
) ENGINE=innodb;

当我还在腾讯互动娱乐部门的时候,一些游戏项目就仅仅将MySQL作为kv来使用,譬如用来存放玩家数据,游戏服务器通过玩家id读取对应的数据,修改,然后更新。鉴于腾讯游戏恐怖的用户量,MySQL能撑住直接就能说明将MySQL作为一个kv来用是可行的。

不过不知道现在还有多少游戏项目仍然采用这种做法,毕竟笔者觉得,将MySQL作为一个kv服务,有点杀鸡用牛刀的感觉,MySQL还是有点重了。

Couchbase

Couchbase是一个高性能的分布式NoSQL,它甚至能支持跨data center的备份。笔者研究了很长一段时间,但最终并没有决定采用,主要笔者没信心去搞定它的代码。

Redis

Redis是一个高性能NoSQL,它不光支持kv,同时还提供了其他的数据结构如hash,list,set,zset供外部使用。

笔者在三年前就开始使用Redis,加之Redis的代码简单,很容易就能理解掌控。所以一直到现在,笔者都会优先使用Redis来存储很多非关系型数据。自然对于kv,笔者也是采用Redis来存放的。

但Redis也有一些不足,最大的莫过于内存限制,Redis存储的总数据大小最好别超过物理内存,不然性能会有问题。同时,笔者觉得Redis的RDB和AOF机制也比较蛋疼,RDB的时候系统可能会出现卡顿,而AOF在rewrite的时候也可能出现类似的问题。

因为内存的限制,所以Redis不能存储超大量的数据,为了解决这个问题,我们只能采用cluster的方案,但是Redis官方的cluster仍然处于开发阶段,并不能真正在生产环境中使用。所以笔者开发了LedisDB

LedisDB

开发LedisDB,主要就是为了解决Redis内存限制问题,它主要有如下特性:

  • 采用Redis协议,大部分Redis的client都能直接使用。
  • 提供类似Redis的API,支持kv,hash,list,set,zset。
  • 底层采用多种db存储实际数据,支持rocksdb(推荐),leveldb,goleveldb,boltdb,lmdb,没有Redis内存限制问题,因为将数据放到硬盘里面了。
  • 高性能,参考benchmark,虽然比Redis略慢,但完全可用于生产环境。

一个简单地例子:

//start ledis server
ledis-server 

//another shell
ledis-cli -p 6380

ledis> set a 1
OK
ledis> get a
"1"

可以看到,LedisDB非常类似Redis,所以用户能很方便的从Redis迁移到LedisDB上面。在实际生产环境中,笔者建议底层选择rocksdb作为其存储模块,它不光性能高,同时提供了很多配置方便用户根据特定情况进行调优(当然,理解这一堆配置可是一件很蛋疼的事情)。后续,笔者对于LedisDB的使用说明都会是基于rocksdb的。

数据安全

虽然LedisDB能存储大量数据,并且易于使用,但是作为一个数据存储服务,数据的安全性是一个非常需要考虑的问题。

  • LedisDB提供了dump和load工具,我们可以很方便的对其备份。在dump的时候,我们仅仅使用的是rocksdb的snapshot机制,非常快速,同时不会阻塞当前服务。这点可能是相对于Redis RDB的优势。虽然Redis的RDB在save的时候也是fork一个子进程进行处理,但如果Redis的数据量巨大,仍然可能造成Redis的卡顿。
  • LedisDB提供类似MySQL的binlog支持,任何操作都是写入binlog之后再最终提交到底层db的。如果服务崩溃,我们能通过binlog进行数据恢复。binlog文件有大小限制,当超过阀值之后,LedisDB会写入一个新的binlog中,而不是像Redis的AOF一样进行rewrite处理。
  • LedisDB支持同步或者异步replication,同步复制能保证数据的强一致,但是会牺牲系统的性能,而异步复制虽然高效,但可能会面对数据丢失问题。这其实就是一个CAP选择问题,在P(partition tolerance)铁定存在的情况下,选择C(consistency)还是选择A(availability)?通常情况下,笔者会选择A。

故障转移

在生产环境中,为了保证数据安全,一个master我们会通常配备一个或者多个slave(笔者喜欢将其称为replication topology),当master当掉的时候,监控系统会选择一个最优的slave(也就是拥有master数据最多的那个),将其提升为新的master,并且将其他slave指向该new master。这套流程也就是我们通常说的failover。

Redis提供了sentinel机制来实现整个replication topology的failover。但sentinel是跟redis绑定的,所以不能直接在LedisDB上面使用,所以笔者开发了redis-failover,一个能支持redis,或者LedisDB failover的sentinel。

redis-failover通过定期向master发送role命令来获知当前replication topology,主要是slaves的信息。当master当掉之后,redis-failover就会从先前获取的slaves里面选择一个最优的slave,提升为master,选择最优的算法很简单,通过info命令得到”slave_priority”和”slave_repl_offset”,如果哪个slave的priority最大,就选择那个,如果priority都一样,则选择replication offset最大的那个。

redis-failover会存在单点问题,所以redis-failover自身需要支持cluster。redis-failover的cluster在内部选举一个leader用来进行实际的monitor以及failover处理,当leader当掉之后,则进行重新选举。

现阶段,redis-failover可以通过外部的zookeeper进行leader选举,同时也支持内部自身通过raft算法进行leader选举。

分布式集群

随着数据量的持续增大,单台机器最终无法存储所有数据,我们不得不考虑通过cluster的方式来解决,也就是将数据放到不同的机器上面去。

要构建LedisDB的cluster,笔者考虑了如下三种方案,这里,我们不说啥hash取模或者consistency hash了,如果cluster真能通过这两种技术简单搞定,那还要这么费力干啥。

  • Redis cluster。

    redis cluster是redis官方提供的cluster解决方案,性能高,并且能支持resharding。可是直到现在,redis cluster仍处于开发阶段,至少笔者是不敢将其用于生产环境中。另外,笔者觉得它真的很复杂,还是别浪费脑细胞去搞定这套架构了。

  • 定制client。

    通过定制client,我们可以知道不同key的路由规则,自然就能找到实际的数据了。这方面的工作我的一位盆友正在进行,但定制client有一个很严重的问题在于所有的client都必须自己实现,其实不算是一个通用的解决方案。

  • Proxy

    记得有人说过,计算机科学领域的任何问题, 都可以通过添加一个中间层来解决。而proxy则是用来解决cluster问题的一个中间层。

    Twemproxy是一个很不错的选择,但是它不能支持resharding,而且貌似twitter内部也没在使用了,所以笔者并不考虑使用。

    本来笔者打算自己写一个proxy,但这时候,codis横空出世,它是一个分布式的proxy,同时支持resharding,并且在豌豆荚的生产环境中得到验证,笔者立刻就决定使用codis了。

    但codis并不支持LedisDB,同时为了满足他们自身的需求,使用的也是一个修改版的redis,鉴于此,笔者实现了xcodis,一个基于codis的,支持LedisDB以及原生redis的proxy。

架构

最终的架构如下。

kv architecture

我们通过使用LedisDB来解决了Redis单机数据容量问题,通过replication机制保证数据安全性,通过redis-failover用来进行failover处理,最后通过xcodis进行集群管理。

当前,这套架构并没有在生产环境中得到验证,但我们一直在内部不断测试,而且国外也有用户在帮助笔者验证这套架构,所以笔者对其还是很有信心的,希望能早日上线。如果有哪位童鞋也对这套架构感兴趣,想吃螃蟹的,笔者非常愿意提供支持。

学习redis sort命令

LedisDB本来是没有sort命令的,而且实际我们也没有使用过该命令,但一位用户给我反应他迫切需要这个功能,我决定首先考察一下redis相关的实现,再看是否提供。

然后我一看redis的sort命令,真的是震惊了,这可能算得上redis里面最复杂的一个命令了,命令原型如下:

SORT key [BY pattern] [LIMIT offset count] [GET pattern [GET pattern ...]] [ASC|DESC] [ALPHA] [STORE destination]

如果不仔细看文档,或者看源码,一下子真的不知道这个命令怎么用。首先我们可以去掉LIMIT offset count这个选项,这个很容易理解,就是排好序之后取偏移数据。ASC和DESC这个也比较容易,就是正向和逆向排序。STORE destination这个其实就是将排好序的数据放到destination这个list里面,也比较容易理解。好了,去掉这些,那么sort的原型就是这个样子了:

SORT key [BY pattern] [GET pattern [GET pattern ...]] [ALPHA]

key里面存储的就是需要排序的东西,所以key只能是list,set或者zset类型,我们以list为例。假设做如下操作:

redis> lpush a 1 2 3
redis> lrange a 0 -1
1) "3"
2) "2"
3) "1"

如果使用sort,则排序结果如下:

redis> sort a
1) "1"
2) "2"
3) "3"

呢么ALPHA是什么意思呢?我们可以做如下操作解释:

redis> lpush b a1 a2 a3
redis> sort b
(error) ERR One or more scores can't be converted into double
redis> sort b alpha
1) "a1"
2) "a2"
3) "a3"

我们在b里面压入的是字符串,所以不能直接sort,必须指定alpha方式。所以alpha就是明确告知sort使用字节序排序,不然sort就会尝试将需要排序的数据转成double类型。

理解了alpha,我们再来看看by的含义,如下例子:

redis> set w_1 3
redis> set w_1 30
redis> set w_2 20
redis> set w_3 10
redis> sort a by w_*
1) "3"
2) "2"
3) "1"
127.0.0.1:6379>

如果有by了,sort就会首先取出对应的数据,也就是1,2,3,然后跟by的pattern进行组合,变成w_1,w_2,w_3,然后以这个作为key去获取对应的值,也就是30,20,10,在按照这些值进行排序。上面这个例子,1对应的by值最大,为30,所以升序排列的时候在最后。

说完了by,我们再来说说get,get是不参与排序的,只是在拍完序之后,将排好序的值依次跟get的pattern组合,获取对应的数据,进行返回,如下例子:

redis> set o_1 10
redis> set o_2 20
redis> set o_3 30
redis> sort a get o_*
1) "10"
2) "20"
3) "30"

再来一个多个get的例子:

redis> set oo_1 100
redis> set oo_2 200
redis> set oo_3 300
redis> sort a get o_* get oo_*
1) "10"
2) "100"
3) "20"
4) "200"
5) "30"
6) "300"

从上面可以看到,如果有多个get,那么sort的做法是对于排好序的一个值,依次通过get获取值,放到结果中,然后在处理下一个值。

如果有get,我们就能获取到相关的值,但这时候我们还需要返回原有的值怎么办?只需要get #就成了,如下:

redis> sort a get o_* get #
1) "10"
2) "1"
3) "20"
4) "2"
5) "30"
6) "3"

好了,折腾了这么久,我算是终于理解了sort的原理,然后在看完sort的实现,依葫芦画瓢在LedisDB里面支持了sort。当然在一些底层细节上面还是稍微跟redis不一样的。

深入解析MySQL replication协议

Why

最开始的时候,go-mysql只是简单的抽象mixer的代码,提供一个基本的mysql driver以及proxy framework,但做到后面,笔者突然觉得,既然研究了这么久mysql client/server protocol,干脆顺带把replication protocol也给弄明白算了。现在想想,幸好当初决定实现了replication的支持,不然后续go-mysql-elasticsearch这个自动同步MySQL到Elasticsearch的工具就不可能在短时间完成。

其实MySQL replication protocol很简单,client向server发送一个MySQL binlog dump的命令,server就会源源不断的给client发送一个接一个的binlog event了。

Register

首先,我们需要伪造一个slave,向master注册,这样master才会发送binlog event。注册很简单,就是向master发送COM_REGISTER_SLAVE命令,带上slave相关信息。这里需要注意,因为在MySQL的replication topology中,都需要使用一个唯一的server id来区别标示不同的server实例,所以这里我们伪造的slave也需要一个唯一的server id。

Binlog dump

最开始的时候,MySQL只支持一种binlog dump方式,也就是指定binlog filename + position,向master发送COM_BINLOG_DUMP命令。在发送dump命令的时候,我们可以指定flag为BINLOG_DUMP_NON_BLOCK,这样master在没有可发送的binlog event之后,就会返回一个EOF package。不过通常对于slave来说,一直把连接挂着可能更好,这样能更及时收到新产生的binlog event。

在MySQL 5.6之后,支持了另一种dump方式,也就是GTID dump,通过发送COM_BINLOG_DUMP_GTID命令实现,需要带上的是相应的GTID信息,不过笔者觉得,如果只是单纯的实现一个能同步binlog的工具,使用最原始的binlog filename + position就够了,毕竟我们不是MySQL,解析GTID还是稍显麻烦的。这里,顺带吐槽一下MySQL internal文档,里面关于GTID encode的格式说明竟然是错误的,文档格式如下:

4                n_sids
  for n_sids {
string[16]       SID
8                n_intervals
    for n_intervals {
8                start (signed)
8                end (signed)
    }

但实际坑爹的是n_sids的长度是8个字节。这个错误可以算是血的教训,笔者当时debug了很久都没发现为啥GTID dump一直出错,直到笔者查看了MySQL的源码。

MariaDB虽然也引入了GTID,但是并没有提供一个类似MySQL的GTID dump命令,仍是使用的COM_BINLOG_DUMP命令,不过稍微需要额外设置一些session variable,譬如要设置slave_connect_state为当前已经完成的GTID,这样master就能知道下一个event从哪里发送了。

Binlog Event

对于一个binlog event来说,它分为三个部分,header,post-header以及payload。但实际笔者在处理event的时候,把post-header和payload当成了一个整体body。

MySQL的binlog event有很多版本,但这里笔者只关心version 4的,也就是从MySQL 5.1.x之后支持的版本。而且笔者也只支持这个版本的event解析,首先是不想写过多的兼容代码,另一个更主要的原因就在于现在几乎都没有人使用低版本的MySQL了。

Binlog event的header格式如下:

4              timestamp
1              event type
4              server-id
4              event-size
4              log pos
2              flags

header的长度固定为19,event type用来标识这个event的类型,event size则是该event包括header的整体长度,而log pos则是下一个event所在的位置。

在v4版本的binlog文件中,第一个event就是FORMAT_DESCRIPTION_EVENT,格式为:

2                binlog-version
string[50]       mysql-server version
4                create timestamp
1                event header length
string[p]        event type header lengths

我们需要关注的就是event type header length这个字段,它保存了不同event的post-header长度,通常我们都不需要关注这个值,但是在解析后面非常重要的ROWS_EVENT的时候,就需要它来判断TableID的长度了。这个后续在说明。

而binlog文件的结尾,通常(只要master不当机)就是ROTATE_EVENT或者STOP_EVENT。这里我们重点关注ROTATE_EVENT,格式如下:

Post-header
8              position
Payload
string[p]      name of the next binlog

它里面其实就是标明下一个event所在的binlog filename和position。这里需要注意,当slave发送binlog dump之后,master首先会发送一个ROTATE_EVENT,用来告知slave下一个event所在位置,然后才跟着FORMAT_DESCRIPTION_EVENT。

其实我们可以看到,binlog event的格式很简单,文档都有着详细的说明。通常来说,我们仅仅需要关注几种特定类型的event,所以只需要写出这几种event的解析代码就可以了,剩下的完全可以跳过。

Row Based Replication

如果真要说处理binlog event有啥复杂的,那铁定属于row based replication相关的ROWS_EVENT了,对于一个ROWS_EVENT来说,它记录了每一行数据的变化情况,而对于外部来说,是需要准确的知道这一行数据到底如何变化的,所以我们需要获取到该行每一列的值。而如何解析相关的数据,是非常复杂的。笔者也是看了很久MySQL,MariaDB源码,以及mysql-python-replication的实现,才最终搞定了这个个人觉得最困难的部分。

在详细说明ROWS_EVENT之前,我们先来看看TABLE_MAP_EVENT,该event记录的是某个table一些相关信息,格式如下:

post-header:
    if post_header_len == 6 {
  4              table id
    } else {
  6              table id
    }
  2              flags

payload:
  1              schema name length
  string         schema name
  1              [00]
  1              table name length
  string         table name
  1              [00]
  lenenc-int     column-count
  string.var_len [length=$column-count] column-def
  lenenc-str     column-meta-def
  n              NULL-bitmask, length: (column-count + 8) / 7

table id需要根据post_header_len来判断字节长度,而post_header_len就是存放到FORMAT_DESCRIPTION_EVENT里面的。这里需要注意,虽然我们可以用table id来代表一个特定的table,但是因为alter table或者rotate binlog event等原因,master会改变某个table的table id,所以我们在外部不能使用这个table id来索引某个table。

TABLE_MAP_EVENT最需要关注的就是里面的column meta信息,后续我们解析ROWS_EVENT的时候会根据这个来处理不同数据类型的数据。column def则定义了每个列的类型。

ROWS_EVENT包含了insert,update以及delete三种event,并且有v0,v1以及v2三个版本。

ROWS_EVENT的格式很复杂,如下:

header:
  if post_header_len == 6 {
4                    table id
  } else {
6                    table id
  }
2                    flags
  if version == 2 {
2                    extra-data-length
string.var_len       extra-data
  }

body:
lenenc_int           number of columns
string.var_len       columns-present-bitmap1, length: (num of columns+7)/8
  if UPDATE_ROWS_EVENTv1 or v2 {
string.var_len       columns-present-bitmap2, length: (num of columns+7)/8
  }

rows:
string.var_len       nul-bitmap, length (bits set in 'columns-present-bitmap1'+7)/8
string.var_len       value of each field as defined in table-map
  if UPDATE_ROWS_EVENTv1 or v2 {
string.var_len       nul-bitmap, length (bits set in 'columns-present-bitmap2'+7)/8
string.var_len       value of each field as defined in table-map
  }
  ... repeat rows until event-end

ROWS_EVENT的table id跟TABLE_MAP_EVENT一样,虽然table id可能变化,但是ROWS_EVENT和TABLE_MAP_EVENT的table id是能保证一致的,所以我们也是通过这个来找到对应的TABLE_MAP_EVENT。

为了节省空间,ROWS_EVENT里面对于各列状态都是采用bitmap的方式来处理的。

首先我们需要得到columns present bitmap的数据,这个值用来表示当前列的一些状态,如果没有设置,也就是某列对应的bit为0,表明该ROWS_EVENT里面没有该列的数据,外部直接使用null代替就成了。

然后就是null bitmap,这个用来表明一行实际的数据里面有哪些列是null的,这里最坑爹的是null bitmap的计算方式并不是(num of columns+7)/8,也就是MySQL计算bitmap最通用的方式,而是通过columns present bitmap的bits set个数来计算的,这个坑真的很大,为啥要这么设计,最主要的原因就在于MySQL 5.6之后binlog row image的格式增加了minimal和noblob,尤其是minimal,update的时候只会记录相应更改字段的数据,譬如我一行有16列,那么用2个byte就能搞定null bitmap了,但是如果这时候只有第一列更新了数据,其实我们只需要使用1个byte就能记录了,因为后面的铁定全为0,就不需要额外空间存放了,不过话说真有必要这么省空间吗?

null bitmap的计算需要通过columns present bitmap的bits set计算,bits set其实也很好理解,就是一个byte按照二进制展示的时候1的个数,譬如1的bits set就是1,而3的bits set就是2,而255的bits set就是8了。

好了,得到了present bitmap以及null bitmap之后,我们就能实际解析这行对应的列数据了,对于每一列,首先判断是否present bitmap标记了,如果为0,则跳过用null表示,然后在看是否在null bitmap里面标记了,如果为1,表明值为null,最后我们就开始解析真有有数据的列了。

但是,因为我们得到的是一行数据的二进制流,我们怎么知道一列数据如何解析?这里,就要靠TABLE_MAP_EVENT里面的column def以及meta了。

column def定义了该列的数据类型,对于一些特定的类型,譬如MYSQL_TYPE_LONG, MYSQL_TYPE_TINY等,长度都是固定的,所以我们可以直接读取对应的长度数据得到实际的值。但是对于一些类型,则没有这么简单了。这时候就需要通过meta来辅助计算了。

譬如对于MYSQL_TYPE_BLOB类型,meta为1表明是tiny blob,第一个字节就是blob的长度,2表明的是short blob,前两个字节为blob的长度等,而对于MYSQL_TYPE_VARCHAR类型,meta则存储的是string长度。这里,笔者并没有列出MYSQL_TYPE_NEWDECIMAL,MYSQL_TYPE_TIME2等,因为它们的实现实在是过于复杂,笔者几乎对照着MySQL的源码实现的。

搞定了这些,我们终于可以完整的解析一个ROWS_EVENT了,顺带说一下,python-mysql-replication里面minimal/noblob row image的支持,也是笔者提交的pull request,貌似是笔者第一次给其他开源项目做贡献。

总结

实现MySQL replication protocol的解析真心是一件很有挑战的事情,虽然辛苦,但是让笔者更加深入的学习了MySQL的源码,为后续笔者改进LedisDB的replication以及更深入的了解MySQL的replication打下了坚实的基础。

话说,现在成果已经显现,不然go-mysql-elasticsearch不可能如此快速实现,后续笔者准备基于此做一个更新cache的服务,这样我们的代码里面就不会到处出现更新cache的代码了。