解决海量数据的新思路——分布式数据库

   目前，分布式的概念越来越流行，但是在数据库领域里，分布式的应用相对较少。在参阅了Google的Map/Reduce概念后，我构思了一种分布式数据库的架构，并实现了其雏形，现在将其基本思路写出来，希望能起到抛砖引玉的作用。我工作时间不长，其中错误，不完善之处还请大家多多指出，谢谢。

    设计这个分布式数据库的目的在于快速的处理海量数据。基本思路其实很简单，将数据分布到多个数据节点中，在执行SQL语句时，分析SQL语句的语义，对一个或多个数据库进行操作。这样就可以使查询的压力分散到每一个节点上面，面对海量数据时的处理时间大大缩短。

    先拿几个简单的SQL语句做分析，看看在分布式的环境下和平常有何不同。假设我们现在有两个数据节点A和B，表名为Table，其中ID为1~100的数据保存在节点A，ID为101~200的数据保存在节点B。以下的SQL语句都是同时对2个数据库执行。

    Select * from Table where ID=1
    这样A数据库将返回ID为1的数据，数据库B返回为空。这时简单的合并A和B的数据，就可以得到正确的结果。

    Select top 10 * from Table
    这时A数据库将返回10条数据，B数据库返回10条数据，这时如果合并A和B，将返回20条结果。这时必须移除多余的10条数据才是正确的结果。

    Select * from Table order by ID
    这时A，B数据库将返回所有的数据，但是要使得数据符合order by的条件，很显然应该进行一次排序操作。

    Select top 10 * from Table order by ID
    这时A，B数据库都返回10条数据，经过合并后，还要经过排序，移除的操作，才能确保结果正确。

    SQL语句中需要处理的关键字还有max，min，count，sum，avg等，这里就不写出来了。经过这几个例子我们可以看到，其实只要经过一些处理，分别对不同数据节点上的查询，可以转化成对单一数据库查询等效的结果。而这些处理归纳起来，只有合并，排序，移除这三种情况，其实这和Map/Reduce思想非常的类似，无论什么复杂的动作，最终归结都可以通过几个简单操作来完成。这些处理当然需要一定的时间，但是在面对海量数据时，很多情况下，处理所需要的时间可以小到忽略不计。

    上面只是一些简单的SQL语句，面对一些复杂的SQL语句，要在SQL语句处理的过程中，进行数据节点之间的数据交换才能完成的（例子在文末会给出）。因此要实现一个完全能够处理SQL语句的分布式数据库，需要在数据库的内核部分进行改动。在实现这个组件时，时间是有限的，进行内核部分的改造不现实，所以我采取了中间件的方式，来实现了这个分布式数据库的雏形，采用的数据库是MSSQL2000，下图是我设计的分布式数据库的概念图（参见附件1）：


    如图所示，数据根据一定规则分布（一般可以直接Hash主键）到每一个数据节点中，由分布式数据库服务器对每个数据节点进行访问，进行归并/排序/移除操作，然后通过数据接口，返回给程序。

    其中几个数据接口所适用的场景为：

    Reader：提供对数据库的查询结果，逐条进行读取的接口。在海量数据下，有时候需要读取大量数据进行处理，如果一次读取到内存中显然不现实。此时可以使用Reader模式逐条读取，进行分批处理。

    DataFiller：提供对数据的XML包装，适用于小数据量的读取，主要是给Web应用提供一个方便的接口。

    Command：执行delete，update，insert等不返回数据的SQL语句。

    BulkCopy：批量插入接口。主要是为大数据量的导入提供高速接口。

    实现这个中间件，难点应该是在SQL语句的语义分析上。这块应该使用编译原理来实现，但是在我的实现中，并没有用到，原因一个是时间问题，另外一个是因为基于中间件的方式，对一些复杂的SQL语句无法得到正确的结果。所以使用了正则表达式和一些方法来对SQL语句进行分析，分析出应该如何对执行结果进行处理，以及SQL语句应该发送到单个节点还是多个节点。以下是处理的流程示意图（参见附件2）：

    在实现时需要注意的地方是，一定要让SQL语句从发送到执行，到返回结果之间没有任何延迟，否则每秒能够执行的SQL语句最多只有几十条。一开始我使用的模型是很常见的查询线程模型（参见附件3）：

    每个语句执行完毕之后，在HashMap中将执行状态设置为执行完毕。使用一个查询线程，不断的遍历HashMap，发现有执行完毕的语句，便将其发往结果处理模块。为了避免CPU占用率100%，查询线程必须要有Sleep语句，但是windows下线程轮切的最小时间段为15ms，并且在Sleep的过程中，CPU将优先处理其他线程，这样Sleep一次至少需要20ms。这样，无论SQL查询再快，分布式数据库的处理速度也会被限制在1000/20=50条/秒以下。在我做的第一个模型中，每秒最多只能处理20多条SQL语句，在面对Web应用时，显然是不够的。

    后来我采用的是信号量机制，即在生成Query线程时，给其分配一个信号量，执行每个SQL语句都会将一个监视线程加入线程池，监视线程堵塞住，等待所有信号量置为发信状态，然后立刻将结果送入结果处理模块。Windows处理信号量是非常快的，可以以CPU指令周期来计量。经过这个改进，分布式数据库处理一个查询的语句，基本等同于执行查询所需的时间。当然，这样的设计造成了使用的线程比较多，调试起来非常困难，需要非常小心的设计，而且在数据节点多的时候，必须维护一个成百上千线程的线程池，个人觉得是非常不好的。我注意到无论处理多少数据，MSSQL中的线程只有20多个，可以判断出他们的设计是非常精巧的，肯定和我的这种设计不同。如果有更好的方法解决这个问题，请不吝赐教，谢谢。

    以上便是一个分布式数据库中间件的基本概念和一个基本实现。当然，实现一个商用的中间件，还有很多工作需要做，例如权限，数据安全，节点故障处理，日志等模块，都有很多改进的地方。目前我实现的这个中间件非常简陋，由于MSSQL本身的限制，有很多模块实现得不够优雅，不过唯一值得欣慰的是，性能上来说是非常不错的，达到了分布式系统的初衷。目前有3台机器作为数据节点运行，进行随机数据访问时，负载基本平均分到了每一个节点上。大数据量读取，大数据量写入一般都有单数据库2倍以上的速度。当然，分布式不是万能的，目前有些问题是无法解决的。例如：

    1、多表问题：简单的举个例子，例如有一张用户表，一张产品ID表，还有一张交易记录表，以用户表，产品ID表为外键，如果执行诸如

    Select * from 交易记录表 where 交易记录表.产品ID=产品ID表.ID and 交易记录表.用户ID=用户表.用户ID

    这样的语句时，如果只对执行完的结果进行处理，无论如何架构这几张表，都会出错。为什么？原因有点难说清楚，有兴趣的话仔细思考一下就知道了。
    对于这样的语句，中间件根本无法处理，只有修改内核，在执行语句的过程中，对每个数据节点进行数据交换，才可以解决。目前的解决方法是把其中一张表放到单个数据库上。不过这样程序看起来就很怪异，一个查询动作要用到两个不同的数据库访问类，没有弄明白整个框架的程序员都不知道为什么要这样做。

    2、语意分析：在分布式的环境下，SQL语意转换为操作原语的难度更加高了，确保其逻辑完全正确很困难，我离散数学学得很差，目前还不能达到100%的正确率，所以不得不在数据接口中保留了手动模式，即手工决定该如何处理数据，非常的丑陋。以目前的识别率，一些复杂的SQL语句要么分开几次写，要么使用手动模式自定义其处理流程才能确保其正确，目前也没时间去完善分析模块，只能随它去了。

    提出这些问题希望能得到大家的指点，毕竟独自一人开发思路会有很多局限性，个人感觉其中还有很多地方可以挖掘，完全可能成为另外一种处理海量数据的方式。最后，谢谢你的观赏。

建议本文作者看看c-jdbc实现的原理

几点意见：
1.如果是oracle等大型数据库，显然应该使用表分区等技术，你的想法似乎没多大意义
2.如果针对mysql等数据库，有一定的意义。记得几年前看过一篇文章，是个tom.com的程序员写的，他识别不同的表，插入到不同的数据库服务器，他的机制是通过分析mysql网络协议完成的。
3.多表问题看来是无解的，所以，你的想法只能用于专用系统。比如，海量的会员信息（比如国内门户网站），这些网站常会使用mysql+文件系统，或者一个简单的hash算法把会员存储到不同的数据库。
4.语法分析可以使用antlr之类的工具来做，hibernate也是这么做的
5.个人认为你这样的分布式数据库解决方案并没有多大用处

作者的目的很明显是想通过分布式数据服务让mysql和firebird等免费开源数据库来提供大容量的数据服务，提供低成本的解决方案
但是作者没有考虑到大的数据量一般背后都存在有较大的资源投入，所以一台200多万甚至更贵的服务器不是问题而oracle同样也不是问题
我们做的业务数据量在每天4000多万就是一个200多万的服务器上跑得oracle，8表关联提取1000万左右的数据在4个小时左右的样子比较理想了，而且由于公司的人土都没做表分区，反正他跑的很好
其实优秀的性能还是要跟着应用走的，数据库的优化复杂不是分布式就能全部解决的
不过楼主的想法很好，如果实现对于中型数据量的应用是很有吸引力的

加油

还有oracle的服务确实很到位

最后支持楼主+++++++++++++油

“Select top 10 * from Table ”
问题，如果分页每页10条，我取第二页的记录，你怎么办。不会每个表取20条记录，然后归并处理吧。如果取第20页哪，100页哪，你的这套还有效率吗

看一下hibernate shard

谢谢,会抽空看下

如果采用mysql，可以试一下：
http://amoeba.sourceforge.net/amoeba.pdf



目前amoeba已经实现了amoeba for mysql，即将实现 amoeba for oracle。

最终目标: amoeba driver + amoeba proxy server + dbServers(mysql/oracle/postgresql/h2/javadb)

amoeba big picture：
http://amoeba.sourceforge.net/amoeba-big-picture.pdf

TOP问题实质就是排序问题,对于排序问题,其实有个简单的办法可以解决的,举个例子:

    A,B两队人都按照高矮顺序排好,要选择最矮的10个人,只需要比较在A,B两队人最前面的那个人,选择矮的那个,并他拉到另外一边,反复10边,就选出最矮的10个了.
    用在分布式数据库中,可以采用Reader模式,每次读取每个数据库的第一条数据,并选择最大的一条,放到结果里.这样就不会产生所有数据都归并过后再排序一遍.
    这同Map/Reduce思想很类似,把一个大规模的计算划分为很多小规模计算,排序1亿条数据需要多大内存?多长时间?我把它分到100台机器上运行,速度提高虽然没有100倍,但是这100台机器都是很普通的机器,我想应该会比超级计算机要便宜吧.现在在上班,晚上再回大家的帖子.

LZ好似初生牛犊，选择了一条艰难的道路。

不过还是想确认一下先：

在你的应用中，有几个表需要分布？ 其数据量有多大？ 数据更新频繁么？