<第一周>key-value数据库集群的发现与思考（兼锻炼坚持能力）

1. 目标是找到一种如下的key-value数据库集群方案：
- 具备高性能的读写，支持亿级PV
- 具备灵活的可扩展性，同时也是支持上一条的基础
- 数据自动切分，即不依赖于业务逻辑
- 具备分布式事务功能以及不同隔离级别
- 具备数据的一致性或局部一致，最终全部一致
- 可独立提供网络层服务，以支持N（数据库集群）*M（WEB集群）结构，并支持二进制的网络协议
- 方便的客户端API

2. 我最初的思路
- 使用Memcachedb，由客户端API（改造spymemcached）实现分布式事务和隔离
- 由客户端API使用Consistent Hashing进行数据切分

3. 关于自己思路的发现
- 读写性能不错
- 不具备良好的可扩展性，由于Consistent Hashing，由于负载过高需要增加一倍的节点时，数据转移量是巨大的（5星级问题）
- 数据可以自动切分
- 分布式事务和隔离的实现只交由客户端API非常困难（5星级问题）
- 一致性满足
- 有独立的网络层服务，可以实现N*M架构，但不支持二进制协议（2星级问题）
- 客户端API相对方便，如spymemcached

4. 继续发现
由于自己是初学者，在这方面没有太多的经验，无法想出一个解决方案。于是我首先做的是去找其他已有的框架，并做粗浅的了解。
根据"菜鸟"和Robbin以及Google的提示，做了下大概的了解，除了上述提到的Memcachedb外，还包括：
- Cassandra，看看它能否解决我3中出现的三个问题，通过了解发现，它的扩展性是很好的，但没有分布式事务处理。
- Voldemort，面临跟Cassandra一样的问题，所以也让人纠结。
- Redis，主张以内存为主的存储，感觉用于生产会有问题。同时也不能解决分布式事务。
- JBossCache，提供了BDB Loader，但没有独立的网络层，需要与APP SERVER（如JBoss等）配合提供服务，有锁机制，由于配置复杂，也因为下面的Scalaris，我没有做进一步的了解。
- Scalaris，让我激动的框架，因为它支持分布式事务和隔离级别，并且以TC作为底层存储，目前正在研究它的扩展性和使用。由于不懂Erlang，这个过程比较费劲，但我仿佛看到一点光亮……

由于是这方面的初学者，加上基础不足，有些见解可能是错误的或不足的，敬请各位大侠指正，谢谢！

评论

36 楼 fxsc 2010-03-28  

魔力猫咪 写道

根据CAP理论，Consistency(一致性), Availability(可用性), Partition tolerance(分布)这3点最多只能满足2点。感觉楼主的说法是打算寻找一个3者全部满足的方案，但是目前还真没有这样的方案。目前的案例大多是采用牺牲C以满足分布要求，没有专门的事务API帮忙，只能你自己编码实现柔性事务。
现在基本上是小型系统牺牲P，大型系统牺牲C。

如果理论上已经否定了这样的解决方案，那么至少不可能用单独的系统实现。
银行之类的大概算是牺牲P满足CA，所以用大型机的多，当然有钱也是一方面。

35 楼 魔力猫咪 2010-03-17  

根据CAP理论，Consistency(一致性), Availability(可用性), Partition tolerance(分布)这3点最多只能满足2点。感觉楼主的说法是打算寻找一个3者全部满足的方案，但是目前还真没有这样的方案。目前的案例大多是采用牺牲C以满足分布要求，没有专门的事务API帮忙，只能你自己编码实现柔性事务。
现在基本上是小型系统牺牲P，大型系统牺牲C。

34 楼 超级潜水艇 2010-03-15  

中文论坛，英文发言，牛B机中的战斗机~

33 楼 cbc009 2010-03-15  

标记一下，回头接着看。。。

32 楼 hankesi2000 2010-01-22  

体谅下不能打中文的朋友吧，呵呵

文章挺好的，希望能多看到些有意思的回复！

31 楼 mwmw 2010-01-22  

不知道为什么要在这个论坛上一直说英语。

一个普通的讨论，中文应该能搞定的。

如果说英语的话，那就到TSS，INFOQ上折腾呗。

30 楼 nkadun 2010-01-21  

jellyfish 写道

Ok, it's getting intensive now. Be warned, this is going to cause a lot of headaches, :-).

I can't type in chinese, even if I could, I can type only as slow as a turtle, so bear with me.

I had two posts, one is here: http://jellyfish.iteye.com/admin/blogs/100840
another is here:
http://www.cjsdn.net/post/view?bid=62&id=195175&sty=1&tpg=1&age=0

Updates:
1. tried Terracotta, if we go to distributed, then it's commericial. There was a war going on between Terracotta and Tangosol(looked like Terracotta started it). From the exchange fire, I sensed that Terracotta is far behind(~4 years behind).

2. I suddenly realized that the lock has to be distributed as well. Damn, more salts on the wound.

3. Here is the list of the rest features I think are useful(copied from the cjsdn link)

-----------------------------

If I understand the distributed cache correctly, the following are the key points on a distributed cache solution:
1. clusted: all different JVMs carry the same content, replicated.
2. fault tolerant: >1 copies in the cache. Normally this feature and #1 are implemented as one, i.e., users can specify how many copies they want in the entire cache.
3. scalable: meaning, increase machines/JVMs to expand memory, not copies. Whether this is transparent to the users, i.e., whether users need to change code for new cache servers.
4. network protocols: UDP/TCP
5. transactions
6. backup to files/databases asynchronously.
7. API for other languages, JDBC/ODBC drivers
8. SQL language manipulations.
9. near cache/far cache memory management.
10. locking
11. distributed event handling, such as JMS. This is essential for intersystem updates.

A big memeory cache is on the main course because db is limited and slow without customization. Hooking a lot of small machines into a gaint memory is the way to go. Google and Tangosol did it right. But the idea is way old. I used to play a game called MOM(master of orion, version 1, dated earlier 90's), it used the same idea, build thousands of small ships and stack them together to form a gaint monster. I talked with my fellow gamers about this idea, someone would do it right one day.


just my experience, hopefully this is useful for you(or scare you away from it, :-)).

先回复再看，不会吓退我的～～～

29 楼 jellyfish 2010-01-21  

Ok, it's getting intensive now. Be warned, this is going to cause a lot of headaches, :-).

I can't type in chinese, even if I could, I can type only as slow as a turtle, so bear with me.

I had two posts, one is here: http://jellyfish.iteye.com/admin/blogs/100840
another is here:
http://www.cjsdn.net/post/view?bid=62&id=195175&sty=1&tpg=1&age=0

Updates:
1. tried Terracotta, if we go to distributed, then it's commericial. There was a war going on between Terracotta and Tangosol(looked like Terracotta started it). From the exchange fire, I sensed that Terracotta is far behind(~4 years behind).

2. I suddenly realized that the lock has to be distributed as well. Damn, more salts on the wound.

3. Here is the list of the rest features I think are useful(copied from the cjsdn link)

-----------------------------

If I understand the distributed cache correctly, the following are the key points on a distributed cache solution:
1. clusted: all different JVMs carry the same content, replicated.
2. fault tolerant: >1 copies in the cache. Normally this feature and #1 are implemented as one, i.e., users can specify how many copies they want in the entire cache.
3. scalable: meaning, increase machines/JVMs to expand memory, not copies. Whether this is transparent to the users, i.e., whether users need to change code for new cache servers.
4. network protocols: UDP/TCP
5. transactions
6. backup to files/databases asynchronously.
7. API for other languages, JDBC/ODBC drivers
8. SQL language manipulations.
9. near cache/far cache memory management.
10. locking
11. distributed event handling, such as JMS. This is essential for intersystem updates.

A big memeory cache is on the main course because db is limited and slow without customization. Hooking a lot of small machines into a gaint memory is the way to go. Google and Tangosol did it right. But the idea is way old. I used to play a game called MOM(master of orion, version 1, dated earlier 90's), it used the same idea, build thousands of small ships and stack them together to form a gaint monster. I talked with my fellow gamers about this idea, someone would do it right one day.


just my experience, hopefully this is useful for you(or scare you away from it, :-)).

28 楼 nkadun 2010-01-21  

Stero 写道

nkadun 写道

Stero 写道

Bigtable/HBase/Hypertable could meet your requirements, except they are column based with version control, heavier than simple key-value caused some overhead.

While Tokyo Tyrant/Tokyo Cabinet or MemcacheDB is more agile, but missing distribution functions.

So my idea is:
1. B tree instead of hashing should be used to keep keys ordered for sharding.
2. Key-value store node is be able to splite it self when data grows. Node should write logs in case if fails, data could be rebuild on other nodes.
3. Using the same master/slave architecture as Bigtable uses to manage key shards and shard server assignment. And also a meta0 and meta1 indexes for key shards. I think this task could be even abstracted as a standard open source project.

That's it.

I'm trying to understand your ideas though I can't quite follow you. By the way, why don't u reply in Chinese since you can read my topic which is written in Chinese and if you don't have EN input method only?

呵呵，这些天英文看多，也看到JavaEye上有很多英文回复，所以就习惯了，呵呵。

首先我对你说的“具备分布式事务功能以及不同隔离级别 ”不是很理解，感觉你说的不是很明确。我觉得事物/隔离这些东西和最优化性能还是有些设计上的冲突，应该让应用层来处理数据的隔离和同步问题。现有key-value实现里类似memcached的incr和cas操作能够帮助应用层解决很多事物性的问题。

所以，我就集中精力来讨论分布式高性能的key-value数据库：

1. 整个数据库应该是分片的(sharded)，shards由集群里的众多shard server来提供服务。
2. 当一个shard里面的数据超过一定大小，为了保证高性能，应该进行拆分。
3. 每个shard server应该记录日志文件，当shard server失败后，可以根据日志文件由其他shard server重建shards里的内容。日志文件应该被分不到不同的机器上来避免单点失败。GFS和HDFS可以达到这个目的，但是响应有点长。可以考虑用rsync进行日志的同步备份。
4. 有一个主节点，来记录各个shard和shard server的对应关系，。客户端根据各个shard的起始结束key的范围（B+数存储方式）或者key hash值的范围（Hash存储方式）来向相应的shard server发出请求。主节点还要处理当一个shard server失败后shard的重新分配问题。

实际上这个就是Google Bigtable/Hadoop HBase的集群模型，除了数据简化为基于内存的key-value模型。
Bigtable和HBase的问题是：
1. 数据模型有列，每个cell还有版本控制，对于简单的高性能的key-value存储有些overhead。
2. 存储基于网络的GFS/HDFS，延迟较大。我们只需要基于硬盘的日志备份就可以了。

因此照搬Bigtable的集群模型，节点换为TT+TC和定制的日志文件备份机制。这就是我的想法。
参考文献：
http://labs.google.com/papers/bigtable-osdi06.pdf

我继续学习中～～

27 楼 nkadun 2010-01-21  

xianglei 写道

我们最近做的新鲜事的项目使用的就是tc ，我们对事务基本没什么要求，对于事务这块可以自己去实现，通过记录日志的方式去搞定。 你可以看看新浪已经开源的项目（http://blog.developers.api.sina.com.cn/?paged=4）里面对亚马逊的Amazon Dynamo 设计实现。

关注一下看看

26 楼 Stero 2010-01-21  

nkadun 写道

Stero 写道

Bigtable/HBase/Hypertable could meet your requirements, except they are column based with version control, heavier than simple key-value caused some overhead.

While Tokyo Tyrant/Tokyo Cabinet or MemcacheDB is more agile, but missing distribution functions.

So my idea is:
1. B tree instead of hashing should be used to keep keys ordered for sharding.
2. Key-value store node is be able to splite it self when data grows. Node should write logs in case if fails, data could be rebuild on other nodes.
3. Using the same master/slave architecture as Bigtable uses to manage key shards and shard server assignment. And also a meta0 and meta1 indexes for key shards. I think this task could be even abstracted as a standard open source project.

That's it.

I'm trying to understand your ideas though I can't quite follow you. By the way, why don't u reply in Chinese since you can read my topic which is written in Chinese and if you don't have EN input method only?

呵呵，这些天英文看多，也看到JavaEye上有很多英文回复，所以就习惯了，呵呵。

首先我对你说的“具备分布式事务功能以及不同隔离级别 ”不是很理解，感觉你说的不是很明确。我觉得事物/隔离这些东西和最优化性能还是有些设计上的冲突，应该让应用层来处理数据的隔离和同步问题。现有key-value实现里类似memcached的incr和cas操作能够帮助应用层解决很多事物性的问题。

所以，我就集中精力来讨论分布式高性能的key-value数据库：

1. 整个数据库应该是分片的(sharded)，shards由集群里的众多shard server来提供服务。
2. 当一个shard里面的数据超过一定大小，为了保证高性能，应该进行拆分。
3. 每个shard server应该记录日志文件，当shard server失败后，可以根据日志文件由其他shard server重建shards里的内容。日志文件应该被分不到不同的机器上来避免单点失败。GFS和HDFS可以达到这个目的，但是响应有点长。可以考虑用rsync进行日志的同步备份。
4. 有一个主节点，来记录各个shard和shard server的对应关系，。客户端根据各个shard的起始结束key的范围（B+数存储方式）或者key hash值的范围（Hash存储方式）来向相应的shard server发出请求。主节点还要处理当一个shard server失败后shard的重新分配问题。

实际上这个就是Google Bigtable/Hadoop HBase的集群模型，除了数据简化为基于内存的key-value模型。
Bigtable和HBase的问题是：
1. 数据模型有列，每个cell还有版本控制，对于简单的高性能的key-value存储有些overhead。
2. 存储基于网络的GFS/HDFS，延迟较大。我们只需要基于硬盘的日志备份就可以了。

因此照搬Bigtable的集群模型，节点换为TT+TC和定制的日志文件备份机制。这就是我的想法。
参考文献：
http://labs.google.com/papers/bigtable-osdi06.pdf

25 楼 xianglei 2010-01-21  

我们最近做的新鲜事的项目使用的就是tc ，我们对事务基本没什么要求，对于事务这块可以自己去实现，通过记录日志的方式去搞定。 你可以看看新浪已经开源的项目（http://blog.developers.api.sina.com.cn/?paged=4）里面对亚马逊的Amazon Dynamo 设计实现。

24 楼 nkadun 2010-01-21  

xianglei 写道

自己实现或者改造现成的开源项目

不过既要实现高性能又要实现分布式事务这个还真是比较头疼

我已经头疼一周了，估计还要头疼很久

23 楼 rainv 2010-01-21  

豆瓣就有啊。。。。
豆瓣发布开源KeyValue存储系统BeansDB
http://code.google.com/p/beansdb/

22 楼 xianglei 2010-01-21  

自己实现或者改造现成的开源项目

不过既要实现高性能又要实现分布式事务这个还真是比较头疼

21 楼 nkadun 2010-01-21  

qaplwsok 写道

楼主可以尝试一下GigaSpaces.

不错的东西，好像我的目标有点扯远了，或者可能要实现我的目标本来就需要很大的系统……

20 楼 qaplwsok 2010-01-21  

楼主可以尝试一下GigaSpaces.

19 楼 nkadun 2010-01-21  

Stero 写道

Bigtable/HBase/Hypertable could meet your requirements, except they are column based with version control, heavier than simple key-value caused some overhead.

While Tokyo Tyrant/Tokyo Cabinet or MemcacheDB is more agile, but missing distribution functions.

So my idea is:
1. B tree instead of hashing should be used to keep keys ordered for sharding.
2. Key-value store node is be able to splite it self when data grows. Node should write logs in case if fails, data could be rebuild on other nodes.
3. Using the same master/slave architecture as Bigtable uses to manage key shards and shard server assignment. And also a meta0 and meta1 indexes for key shards. I think this task could be even abstracted as a standard open source project.

That's it.

I'm trying to understand your ideas though I can't quite follow you. By the way, why don't u reply in Chinese since you can read my topic which is written in Chinese and if you don't have EN input method only?

18 楼 nkadun 2010-01-21  

抛出异常的爱 写道

1.重写client hash分布算法
当增加节点时可以进行两次hash从而增加节点
原:A-B-C
加过节点一次hash:A-虚B-C
加过节点二次hash:A-B-B1-C
可以减少数据迁移

2.你需要一个路由软件.

增加一个节点时受影响的节点只有一到两个，但增加一个节点是为了解决负载不均的情况（跟调整原有的节点是一样的），为了提高系统的整体处理能力，需要增加一倍节点的时候，这方法就行不通了。

17 楼 nkadun 2010-01-21  

zozoh 写道

如果用 JAVA 的话， H2 挺不错的： http://www.h2database.com

大概看了一下，还是SQL DB，我相信它的性能不会高到哪里去