ledisdb

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进行集群管理。

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

LedisDB Replication设计

对于使用SQL或者NoSQL的童鞋来说,replication都是一个避不开的话题,通过replication,能极大地保证你的数据安全性。毕竟谁都知道,不要把鸡蛋放在一个篮子里,同理,也不要把数据放到一台机器上面,不然机器当机了你就happy了。

在分布式环境下,对于任何数据存储系统,实现一套好的replication机制是很困难的,毕竟CAP的限制摆在那里,我们不可能实现出一套完美的replication机制,只能根据自己系统的实际情况来设计和对CAP的取舍。

对于replication更详细的说明与解释,这里推荐Distributed systems
for fun and profit
,后面,我会根据LedisDB的实际情况,详细的说明我在LedisDB里面使用的replication是如何实现的。

BinLog

最开始的时候,Ledisdb采用的是类似MySQL通用binlog的replication机制,即通过binlog的filename + position来决定需要同步的数据。这套方式实现起来非常简单,但是仍然有一些不足,主要就在于hierarchical replication情况下如果master当掉,选择合适的slave提升为master是比较困难的。举个最简单的例子,假设A为master,B,C为slave,如果A当掉了,我们会在B,C里面选择同步数据最多的那个,但是是哪一个呢?这个问题,在MySQL的replication中也会碰到。

MySQL GTID

在MySQL 5.6之后,引入了GTID(Global transaction ID)的概念来解决上述问题,它通过Source:ID的方式来在binlog里面表示一个唯一的transaction。Source为当前server的uuid,这个是全局唯一的,而ID则是该server内部的transaction ID(采用递增保证唯一)。具体到上面那个问题,采用GTID,如果A当掉了,我们只需要在B和C的binlog里面查找比较最后一个A这个uuid的transaction id的大小,譬如B的为uuid:10,而C的为uuid:30,那么铁定我们会选择C为新的master。

当然使用GTID也有相关的限制,譬如slave也必须写binlog等,但它仍然足够强大,解决了早期MySQL replication的时候一大摊子的棘手问题。但LedisDB并不准备使用,主要就在于应用场景没那么复杂的情况,我需要的是一个更加简单的解决方案。

Google Global Transaction ID

早在MySQL的GTID之前,google的一个MySQL版本就已经使用了global transaction id,在binlog里面,它对于任何的transaction,使用了group id来唯一标示。group id是一个全局的递增ID,由master负责维护生成。当master当掉之后,我们只需要看slave的binlog里面谁的group id最大,那么那一个就是能被选为master了。

可以看到,这套方案非常简单,但是限制更多,譬如slave端的binlog只能由replication thread写入,不支持Multi-Masters,不支持circular replication等。但我觉得它已经足够简单高效,所以LedisDB准备参考它来实现。

Raft

弄过分布式的童鞋应该都或多或少的接触过Paxos(至少我是没完全弄明白的),而Raft则号称是一个比Paxos简单得多的分布式一致性算法。

Raft通过replicated log来实现一致性,假设有A,B,C三台机器,A为Leader,B和C为follower,(其实也就是master和slave的概念)。A的任何更新,都必须首先写入Log(每个Log有一个LogID,唯一标示,全局递增),然后将其Log同步到至少Follower,然后才能在A上面提交更新。如果A当掉了,B和C重新选举,如果哪一台机器当前的LogID最大,则成为Leader。看到这里,是不是有了一种很熟悉的感觉?

LedisDB在支持consensus replication上面,参考了Raft的相关做法。

名词解释

在详细说明LedisDB replication的实现前,有必要解释一些关键字段。

  • LogID:log的唯一标示,由master负责生成维护,全局递增。
  • LastLogID:当前程序最新的logid,也就是记录着最后一次更新的log。
  • FirstLogID:当前程序最老的logid,之前的log已经被清除了。
  • CommitID:当前程序已经处理执行的log。譬如当前LastLogID为10,而CommitID为5,则还有6,7,8,9,10这几个log需要执行处理。如果CommitID = LastLogID,则证明程序已经处于最新状态,不再需要处理任何log了。

LedisDB Replication

LedisDB的replication实现很简单,仍然是上面的例子,A,B,C三台机器,A为master,B和C为slave。

当master有任何更新,master会做如下事情:

  1. 记录该更新到log,logid = LastLogID + 1,LastLogID = logid
  2. 同步该log到slaves,等待slaves的确认返回,或者超时
  3. 提交更新
  4. 更新CommitID = logid

上面还需要考虑到错误处理的情况。

  • 如果1失败,记录错误日志,然后我们会认为该次更新操作失败,直接返回。
  • 如果3失败,不更新CommitID返回,因为这时候CommitID小于LastLogID,master进入read only模式,replication thread尝试执行log,如果能执行成功,则更新CommitID,变成可写模式。
  • 如果4失败,同上,因为LedisDB采用的是Row-Base Format的log格式,所以一次更新操作能够幂等多次执行。

对于slave

如果是首次同步,则进入全同步模式:

  1. master生成一个snapshot,连同当前的LastLogID一起发送给slave。
  2. slave收到该dump文件之后,load载入,同时更新CommitID为dump文件里面的LastLogID。

然后进入增量同步模式,如果slave已经有相关log,则直接进入增量同步模式。

在增量模式下面,slave向master发送sync命令,sync的参数为下一个需要同步的log,如果slave当前没有binlog(譬如上面提到的全同步情况),则logid = CommitID + 1, 否则logid = LastLogID + 1。

master收到sync请求之后,有如下处理情况:

  • sync的logid小于FirstLogID,master没有该log,slave收到该错误重新进入全同步模式。
  • master有该sync的log,于是将log发送给slave,slave收到之后保存,并再次发送sync获取下一个log,同时该次请求也作为ack告知master同步该log成功。
  • sync的log id已经大于LastLogID了,表明master和slave的状态已经到达一致,没有log可以同步了,slave将会等待新的log直到超时再次发送sync。

在slave端,对于接受到的log,由replication thread负责执行,并更新CommitID。

如果master当机,我们只需要选择具有最大LastLogID的那个slave为新的master就可以了。

Limitation

总的来说,这套replication机制很简单,易于实现,但是仍然有许多限制。

  • 不支持Multi-Master,因为同时只能有一个地方进行全局LogID的生成。不过我真的很少见到Multi-Master这样的架构模式,即使在MySQL里面。
  • 不支持Circular-Replication,slave写入的log id不允许小于当前的LastLogID,这样才能保证只同步最新的log。
  • 没有自动master选举机制,不过我觉得放到外部去实现更好。

Async/Sync Replication

LedisDB是支持强一致性的同步replication的,如果配置了该模式,那么master会等待slave同步完成log之后再提交更新,这样我们就能保证当master当机之后,一定有一台slave具有跟master一样的数据。但在实际中,可能因为网络环境等问题,master不可能一直等待slave同步完成log,所以通常都会有一个超时机制。所以从这点来看,我们仍然不能保证数据的强一致性。

使用同步replication机制会极大地降低master的写入性能,如果对数据一致性不敏感的业务,其实采用异步replication就可以了。

Failover

LedisDB现在没有自动的failover机制,master当机之后,我们仍然需要外部的干预来选择合适的slave(具有最大LastLogID那个),提升为master,并将其他slave重新指向该master。后续考虑使用外部的keeper程序来处理。而对于keeper的单点问题,则考虑使用raft或者zookeeper来处理。

后记

虽然LedisDB现在已经支持replication,但仍然需要在生产环境中检验完善。

LedisDB是一个采用Go实现的高性能NoSQL,接口类似Redis,现在已经用于生产环境,欢迎大家使用。

Official Website

Github

高性能NoSQL LedisDB设计2

ledisdb现在已经支持replication机制,为ledisdb的高可用做出了保障。

使用

假设master的ip为10.20.187.100,端口6380,slave的ip为10.20.187.101,端口为6380.

首先我们需要master打开binlog支持,在配置文件中指定:

use_bin_log : true

在slave的机器上面我们可以通过配置文件指定slaveof开启replication,或者通过命令slaveof显示的开启或者关闭。

slaveof 10.20.187.100 6380

ledisdb的replication机制参考了redis以及mysql的相关实现,下面简单说明。

redis replication

redis的replication机制主要介绍在这里,已经说明的很详细了。

  • slave向master发送sync命令
  • master将其当前的数据dump到一个文件,同时在内存中缓存新增的修改命令
  • 当数据dump完成,master就将其发送给slave
  • slave接受完成dump数据之后,将其本机先前的数据清空,然后在导入dump的数据
  • master再将先前缓存的命令发送给slave

在redis2.8之后,为了防止断线导致重新生成dump,redis增加了psync命令,在断线的时候master会记住当前的同步状态,这样下次就能进行断点续传了。

mysql replication

mysql的replication主要是通过binlog的同步来完成的。在master的任何数据更新,都会写入binlog,至于binlog的格式这里不再累述。

假设binlog的basename为mysql,index文件名字为mysql-bin.index,该文件记录着当前所有的binlog文件。

binlog有max file size的配置,当binlog写入的的文件大小超过了该值,mysql就会生成一个新的binlog文件。当mysql服务重启的时候,也会生成一个新的binlog文件。

在Percona的mysql版本中,binlog还有一个max file num的设置,当binlog的文件数量超过了该值,mysql就会删除最早的binlog。

slave有一个master.info的文件,用以记录当前同步master的binlog的信息,主要就是当前同步的binlog文件名以及数据偏移位置,这样下次重新同步的时候就能从该位置继续进行。

slave同步的数据会写入relay log中,同时在后台有另一个线程将relay log的数据存入mysql。

因为master的binlog可能删除,slave同步的时候可能会出现binlog丢失的情况,mysql通过dump+binlog的方式解决,其实也就是slave完全的dump master数据,在生成的dump中也同时会记录当前的binlog信息,便于下次继续同步。

ledisdb replication

ledisdb的replication机制参考了redis以及mysql,支持fullsync以及增量sync。

master没有采用aof机制,而是使用了binlog,通过指定max file size以及max file num用来控制binlog的总体大小,这样我就无需关心aof文件持续增大需要重新rewrite的过程了。

binlog文件名格式如下:

ledis-bin.0000001
ledis-bin.0000002

binlog文件名的后缀采用数字递增,后续我们使用index来表示。

slave端也有一个master.info文件,因为ledisdb会严格的保证binlog文件后缀的递增,所以我们只需要记录当前同步的binlog文件后缀的index即可。

整个replication流程如下:

  • 当首次同步或者记录的binlog信息因为master端binlog删除导致不一致的时候,slave会发送fullsync进行全同步。
  • master收到fullsync信息之后,会将当前的数据以及binlog信息dump到文件,并将其发送给slave。
  • slave接受完成整个dump文件之后,清空所有数据,同时将dump的数据导入leveldb,并保存当前dump的binlog信息。
  • slave通过sync命令进行增量同步,sync命令格式如下:

      sync binlog-index binlog-pos
    

    master通过index定位到指定的binlog文件,并seek至pos位置,将其后面的binlog数据发送给slave。

  • slave接收到binlog数据,导入leveldb,如果sync没有收到任何新增数据,1s之后再次sync。

对于最后一点,最主要就是一个问题,即master新增的binlog如何让slave进行同步。对于这点无非就是两种模型,push和pull。

对于push来说,任何新增的数据都能非常及时的通知slave去获取,而pull模型为了性能考虑,不可能太过于频繁的去轮询,略有延时。

mysql采用的是push + pull的模式,当binlog有更新的时候,仅仅通知slave有了更新,slave则是通过pull拉取实际的数据。但是为了支持push,master必须得维持slave的一些状态信息,这稍微又增加了一点复杂度。

ledisdb采用了非常简单的一种方式,定时pull,使用1s的间隔,这样既不会因为轮询太过频繁导致性能开销增大,同时也能最大限度的减少当机数据丢失的风险。

总结

ledisdb的replication机制才刚刚完成,后续还有很多需要完善,但足以使其成为一个高可用的nosql选择了。

ledisdb的网址在这里https://github.com/siddontang/ledisdb,希望感兴趣的童鞋共同参与。

高性能NoSQL LedisDB设计1

ledisdb是一个用go实现的基于leveldb的高性能nosql数据库,它提供多种数据结构的支持,网络交互协议参考redis,你可以很方便的将其作为redis的替代品,用来存储大于内存容量的数据(当然你的硬盘得足够大!)。

同时ledisdb也提供了丰富的api,你可以在你的go项目中方便嵌入,作为你app的主要数据存储方案。

与redis的区别

ledisdb提供了类似redis的几种数据结构,包括kv,hash,list以及zset,(set因为我们用的太少现在不予支持,后续可以考虑加入),但是因为其基于leveldb,考虑到操作硬盘的时间消耗铁定大于内存,所以在一些接口上面会跟redis不同。

最大的不同在于ledisdb对于在redis里面可以操作不同数据类型的命令,譬如(del,expire),是只支持kv操作的。也就是说,对于del命令,ledisdb只支持删除kv,如果你需要删除一个hash,你得使用ledisdb额外提供的hclear命令。

为什么要这么设计,主要是性能考量。leveldb是一个高效的kv数据库,只支持kv操作,所以为了模拟redis中高级的数据结构,我们需要在存储kv数据的时候在key前面加入相关数据结构flag。

譬如对于kv结构的key来说,我们按照如下方式生成leveldb的key:

func (db *DB) encodeKVKey(key []byte) []byte {
    ek := make([]byte, len(key)+2)
    ek[0] = db.index
    ek[1] = kvType
    copy(ek[2:], key)
    return ek
}

kvType就是kv的flag,至于第一个字节的index,后面我们在讨论。

如果我们需要支持del删除任意类型,可能的一个做法就是在另一个地方存储该key对应的实际类型,然后del的时候根据查出来的类型再去做相应处理。这不光损失了效率,也提高了复杂度。

另外,在使用ledisdb的时候还需要明确知道,它只是提供了一些类似redis接口,并不是redis,如果想用redis的全部功能,这个就有点无能为力了。

db select

redis支持select的操作,你可以根据你的业务选择不同的db进行数据的存放。本来ledisdb只打算支持一个db,但是经过再三考虑,我们决定也实现select的功能。

因为在实际场景中,我们不可能使用太多的db,所以select db的index默认范围就是[0-15],也就是我们最多只支持16个db。redis默认也是16个,但是你可以配置更多。不过我们觉得16个完全够用了,到现在为止,我们的业务也仅仅使用了3个db。

要实现多个db,我们开始定了两种方案:

  • 一个db使用一个leveldb,也就是最多ledisdb将打开16个leveldb实例。
  • 只使用一个leveldb,每个key的第一个字节用来标示该db的索引。

这两种方案我们也不知道如何取舍,最后决定采用使用同一个leveldb的方式。可能我们觉得一个leveldb可以更好的进行优化处理吧。

所以我们任何leveldb key的生成第一个字节都是存放的该db的index信息。

KV

kv是最常用的数据结构,因为leveldb本来就是一个kv数据库,所以对于kv类型我们可以很简单的处理。额外的工作就是生成leveldb对应的key,也就是前面提到的encodeKVKey的实现。

Hash

hash可以算是一种两级kv,首先通过key找到一个hash对象,然后再通过field找到或者设置相应的值。

在ledisdb里面,我们需要将key跟field关联成一个key,用来存放或者获取对应的值,也就是key:field这种格式。

这样我们就将两级的kv获取转换成了一次kv操作。

另外,对于hash来说,(后面的list以及zset也一样),我们需要快速的知道它的size,所以我们需要在leveldb里面用另一个key来实时的记录该hash的size。

hash还必须提供keys,values等遍历操作,因为leveldb里面的key默认是按照内存字节升序进行排列的,所以我们只需要找到该hash在leveldb里面的最小key以及最大key,就可以轻松的遍历出来。

在前面我们看到,我们采用的是key:field的方式来存入leveldb的,那么对于该hash来说,它的最小key就是“key:”,而最大key则是“key;”,所以该hash的field一定在“(key:, key;)”这个区间范围。至于为什么是“;”,因为它比“:”大1。所以“key:field”一定小于“key;”。后续zset的遍历也采用的是该种方式,就不在说明了。

List

list只支持从两端push,pop数据,而不支持中间的insert,这样主要是为了简单。我们使用key:sequence的方式来存放list实际的值。

sequence是一个int整形,相关常量定义如下:

listMinSeq     int32 = 1000
listMaxSeq     int32 = 1<<31 - 1000
listInitialSeq int32 = listMinSeq + (listMaxSeq-listMinSeq)/2

也就是说,一个list最多存放1<<31 - 2000条数据,至于为啥是1000,我说随便定得你信不?

对于一个list来说,我们会记录head seq以及tail seq,用来获取当前list开头和结尾的数据。

当第一次push一个list的时候,我们将head seq以及tail seq都设置为listInitialSeq。

当lpush一个value的时候,我们会获取当前的head seq,然后将其减1,新得到的head seq存放对应的value。而对于rpush,则是tail seq + 1。

当lpop的时候,我们会获取当前的head seq,然后将其加1,同时删除以前head seq对应的值。而对于rpop,则是tail seq - 1。

我们在list里面一个meta key来存放该list对应的head seq,tail seq以及size信息。

ZSet

zset可以算是最为复杂的,我们需要使用三套key来实现。

  • 需要用一个key来存储zset的size
  • 需要用一个key:member来存储对应的score
  • 需要用一个key:score:member来实现按照score的排序

这里重点说一下score,在redis里面,score是一个double类型的,但是我们决定在ledisdb里面只使用int64类型,原因一是double还是有浮点精度问题,在不同机器上面可能会有误差(没准是我想多了),另一个则是我不确定double的8字节memcmp是不是也跟实际比较结果一样(没准也是我想多了),其实更可能的原因在于我们觉得int64就够用了,实际上我们项目也只使用了int的score。

因为score是int64的,我们需要将其转成大端序存储(好吧,我假设大家都是小端序的机器),这样通过memcmp比较才会有正确的结果。同时int64有正负的区别,负数最高位为1,所以如果只是单纯的进行binary比较,那么负数一定比正数大,这个我们通过在构建key的时候负数前面加”<”,而正数(包括0)加”=”来解决。所以我们score这套key的格式就是这样:

key<score:member //<0
key=score:member //>=0

对于zset的range处理,其实就是确定某一个区间之后通过leveldb iterator进行遍历获取,这里我们需要明确知道的事情是leveldb的iterator正向遍历的速度和逆向遍历的速度完全不在一个数量级上面,正向遍历快太多了,所以最好别去使用zset里面带有rev前缀的函数。

总结

总的来说,用leveldb来实现redis那些高级的数据结构还算是比较简单的,同时根据我们的压力测试,发现性能还能接受,除了zset的rev相关函数,其余的都能够跟redis保持在同一个数量级上面,具体可以参考ledisdb里面的性能测试报告以及运行ledis-benchmark自己测试。

后续ledisdb还会持续进行性能优化,同时提供expire以及replication功能的支持,预计6月份我们就会实现。

ledisdb的代码在这里https://github.com/siddontang/ledisdb,希望感兴趣的童鞋共同参与。

LedisDB嵌入使用介绍

ledisdb现在可以支持嵌入式使用。你可以将其作为一个独立的lib(类似leveldb)直接嵌入到你自己的应用中去,而无需在启动单独的服务。

ledisdb提供的API仍然类似redis接口。首先,你需要创建ledis对象:

import "github.com/siddontang/ledisdb/ledis"

configJson = []byte('{
    "data_db" : 
    {
        "path" : "/tmp/testdb",
        "compression":true,
        "block_size" : 32768,
        "write_buffer_size" : 2097152,
        "cache_size" : 20971520
    }    
}
')

l, _ := ledis.Open(configJson)

data_db就是数据存储的leveldb位置,简单起见,所有的size配置全部使用byte作为单位。

然后我们选择一个db使用,

db, _ := l.Select(0)

类似redis,我们也只支持数字类型的db,最多16个db,索引范围为[0-15]。支持太多的db真没啥意义。

下面是一些简单的例子:

kv

db.Set(key, value)
db.Get(key)
db.SetNX(key, value)
db.Incr(key)
db.IncrBy(key, 10)
db.Decr(key)
db.DecrBy(key, 10)

db.MSet(KVPair{key1, value1}, KVPair{key2, value2})
db.MGet(key1, key2)

list

db.LPush(key, value1, value2, value3)
db.RPush(key, value4, value5, value6)

db.LRange(key, 1, 10)
db.LIndex(key, 10)

db.LLen(key)

hash

db.HSet(key, field1, value1)
db.HMSet(key, FVPair{field1, value1}, FVPair{field2, value2})

db.HGet(key, field1)

db.HGetAll()
db.HKeys()

zset

db.ZAdd(key, ScorePair{score1, member1}, ScorePair{score2, member2})

db.ZCard(key)

//range by score [0, 100], withscores = true and no limit
db.ZRangeByScore(key, 0, 100, true, 0, -1)

//range by score [0, 100], withscores = true and limit offset = 10, count = 10
db.ZRangeByScore(key, 0, 100, true, 10, 10)

db.ZRank(key, member1)

db.ZCount(key, member1)

ledisdb的源码在这里https://github.com/siddontang/ledisdb,欢迎反馈。

高性能NoSQL LedisDB介绍

起因

ledisdb是一个参考ssdb,采用go实现,底层基于leveldb,类似redis的高性能nosql数据库,提供了kv,list,hash以及zset数据结构的支持。

我们现在的应用极大的依赖redis,但随着我们用户量越来越大,redis的内存越来越不够用,并且replication可能还会导致超时问题。虽然后续我们可以通过添加多台机器来解决,但是在现有机器配置下面,我们仍希望单台机器承载更多的用户。另外,因为业务的特性,我们其实并不需要将所有的数据放到内存,只需要存放当前活跃用户。

经过我们的调研,发现ssdb已经很好的帮我们解决了这个问题,它提供了跟redis一致的接口(当然有些地方还是稍微不同),但是底层采用leveldb进行存储。根据其官网的描述,性能已经接近甚至超越了redis。

本着造轮子的精神,我决定用go实现一个类似的db,取名为ledisdb,也就是level-redis-db,为啥不用现成的ssdb,我觉得有如下几个原因:

  • go语言开发的快速,这点毋庸置疑,虽然性能上面铁定离c++的代码有差距,但是我能够快速的进行原型搭建并实验。实际上,我在很短的时间里面就开发出了ledisdb,让我后续继续开发有了信心。
  • leveldb的研究,我一直很想将leveldb应用到我们的项目中,作为本机热点数据的首选数据存储方式,通过ledisdb,让我对leveldb的使用有了很多经验。
  • redis的熟悉,虽然我用了很久的redis,但是很多redis的命令仍然需要去查手册,通过实现ledisdb,我更加熟悉了redis的命令,同时,因为要了解这个命令redis如何实现,对redis内部又重新来了一次剖析。

在准备开发ledisdb的时候,我就在思索一个问题,我需不需要开发另一个redis?其实这是一个很明确的问题,我不需要另一个redis。ledisdb虽然参考了redis,但为了实现简单,有时候我做了很多减法或者变更,譬如对于zset这种数据结构,我就只支持int64类型的score,而redis的score是double类型的,具体原因后续讲解zset的时候详细说明。

所以,我们可以认为,ledisdb是一个基于redis通信协议,提供了多种高级数据结构的nosql数据库,它并不是另一个redis。

编译安装

因为ledisdb是用go写的,所以首先需要安装go以及配置GOROOT,GOPATH。

mkdir $WORKSPACE
cd $WORKSPACE
git clone git@github.com:siddontang/ledisdb.git src/github.com/siddontang/ledisdb

cd src/github.com/siddontang/ledisdb

#构建leveldb,如果已经安装了,可忽略
./build_leveldb.sh  

#安装ledisdb go依赖
. ./bootstap.sh     

#配置GOPATH等环境变量
. ./dev.sh          

go install ./... 

具体的安装说明,可以查看代码目录下面的readme。

Example

使用ledisdb很简单,只需要运行:

./ledis-server -config=/etc/ledis.json

ledisdb的配置文件采用json格式,为啥选用json,我在使用json作为主要的配置格式里面有过说明。

我们可以使用任何redis客户端连接ledisdb,譬如redis-cli,如下:

127.0.0.1:6380> set a 1
OK
127.0.0.1:6380> get a
"1"
127.0.0.1:6380> incr a
(integer) 2
127.0.0.1:6380> mset b 2 c 3
OK
127.0.0.1:6380> mget a b c
1) "2"
2) "2"
3) "3"

leveldb

因为leveldb是c++写的,所以在go里面需要使用,cgo是一种很好的方式。这里,我直接使用了levigo这个库,并在上面进行了封装,详见这里。虽然有一个go-leveldb,无奈仍不能用。

cgo的性能开销还是有的,这点在我做benchmark的时候就明显感觉出来,不过后续优化的空间很大,譬如将多个leveldb的调用逻辑该用c重写,这样只需要一次cgo就可以了。不过这个后续在考虑。

leveldb的一些参数在构建编译的时候是需要调整的,这点我没啥经验,只能google和参考ssdb。譬如下面这几个:

+ db/dbformat.h

// static const int kL0_SlowdownWritesTrigger = 8;
static const int kL0_SlowdownWritesTrigger = 16;

// static const int kL0_StopWritesTrigger = 12;
static const int kL0_StopWritesTrigger = 64;

+ db/version_set.cc

//static const int kTargetFileSize = 2 * 1048576;
static const int kTargetFileSize = 32 * 1048576;

//static const int64_t kMaxGrandParentOverlapBytes = 10 * kTargetFileSize;
static const int64_t kMaxGrandParentOverlapBytes = 20 * kTargetFileSize;

相关参数的调优,只能等我后续深入研究leveldb了在好好考虑。

性能测试

任何一个服务端服务没有性能测试报告那就是耍流氓,我现在只是简单的用了redis_benchmark进行测试,测试环境为一台快两年的老爷mac air机器。

测试语句:

redis-benchmark -n 10000 -t set,incr,get,lpush,lpop,lrange,mset -q

redis-benchmark默认没有hash以及zset的测试,后续我在自己加入。

leveldb配置:

compression       = false
block_size        = 32KB
write_buffer_size = 64MB
cache_size        = 500MB

redis

SET: 42735.04 requests per second
GET: 45871.56 requests per second
INCR: 45248.87 requests per second
LPUSH: 45045.04 requests per second
LPOP: 43103.45 requests per second
LPUSH (needed to benchmark LRANGE): 44843.05 requests per second
LRANGE_100 (first 100 elements): 14727.54 requests per second
LRANGE_300 (first 300 elements): 6915.63 requests per second
LRANGE_500 (first 450 elements): 5042.86 requests per second
LRANGE_600 (first 600 elements): 3960.40 requests per second
MSET (10 keys): 33003.30 requests per second

ssdb

SET: 35971.22 requests per second
GET: 47393.37 requests per second
INCR: 36630.04 requests per second
LPUSH: 37174.72 requests per second
LPOP: 38167.94 requests per second
LPUSH (needed to benchmark LRANGE): 37593.98 requests per second
LRANGE_100 (first 100 elements): 905.55 requests per second
LRANGE_300 (first 300 elements): 327.78 requests per second
LRANGE_500 (first 450 elements): 222.36 requests per second
LRANGE_600 (first 600 elements): 165.30 requests per second
MSET (10 keys): 33112.59 requests per second

ledisdb

SET: 38759.69 requests per second
GET: 40160.64 requests per second
INCR: 36101.08 requests per second
LPUSH: 33003.30 requests per second
LPOP: 27624.31 requests per second
LPUSH (needed to benchmark LRANGE): 32894.74 requests per second
LRANGE_100 (first 100 elements): 7352.94 requests per second
LRANGE_300 (first 300 elements): 2867.79 requests per second
LRANGE_500 (first 450 elements): 1778.41 requests per second
LRANGE_600 (first 600 elements): 1590.33 requests per second
MSET (10 keys): 21881.84 requests per second

可以看到,ledisdb的性能赶redis以及ssdb还是有差距的,但也不至于不可用,有些差别并不大。至于为啥lrange比ssdb高,我比较困惑。

后续的测试报告,我会不断在benchmark文件里面更新。

Todo。。。。。。

ledisdb还是一个非常新的项目,比起ssdb已经在生产环境中用了很久,还有很多路要走,还有一些重要的功能需要实现,譬如replication等。

欢迎有兴趣的童鞋一起参与进来,在漫漫程序开发路上有一些好基友可是很幸运的。