在首届阿里巴巴中间件峰会上，来自阿里巴巴DRDS团队的梦实分享了《分布式数据库——从线性扩展谈分布式JOIN》。他主要从OLTP数据库的线性扩展、水平扩容、IN查询、分布式JOIN四个方面进行了分享。在分享中，他主要通过买家与订单场景、家庭与孩子场景介绍了IN查询，通过同维度的JOIN、广播表的JOIN、Nested Loop Join详细介绍了分布式JOIN的坑与填坑。
以下内容根据直播视频整理而成。
在数据库的使用过程中，我们难免会问到这样的问题，为什么分库分表？答案是为了达到线性扩展。在本次分享中，我们能够知道分布式数据库中线性扩展的含义，学会判定一个系统与查询能否达到线性扩展的目的，达到使用分布式数据库的目标。
OLTP数据库的线性扩展
数据库主要有两类：OLAP数据库，SQL一般比较复杂，执行时间可能在秒级至分钟级，响应时间越快越好（单SQL占据更多的资源，例如Map Reduce模型），提供尽可能高的并发度；OLTP数据库，SQL一般比较简单，执行时间一般在毫秒级，响应时间在可接受范围（例如10ms）内即可（单SQL一般只有一个线程执行），提供尽可能高系统容量。
对于OLTP，来说，是否机器越多，SQL执行越快？答案是否定的。对于OLTP数据库中的线性扩展，增加机器数，单SQL的响应时间基本不会发生太大变化；增加机器数，能线性增加整个系统的容量（并发度、吞吐量、TPS）。并且，在资源一定的情况下，从单机到分布式并不能带来更高的系统容量。
水平扩容
比如做一个全表的count（*）操作，每个分库上的时间可能是10ms，如果不带拆分键的话则需要到所有的表上去执行一个count（*）操作，如果将这些SQL并行的发下去，则会发现查询也只消耗了10ms的时间，与只在一个分库上执行的时间差不多。那为什么还要带拆分键？
比如我们有两台DB实例，如果带拆分键的话，往分布式数据库里面提交一个查询，到DB这边也是一个查询，那么提交6条查询之后，系统容量是6QPS。我们把提交到分布式数据库中的查询称为逻辑查询，把分布式数据库到底层所执行的查询称为物理查询。对于业务来说，分布式数据库是相对透明的，它关注的容量指的是逻辑QPS。
发现系统容量不够时，需要进行扩容，我们需要加1台DB，成本提升了50%。如图所示，性能确实提高了50%。
假如我们的SQL没有带拆分键，那么它需要路由到所有的分片上去执行。一条逻辑SQL会生成2条物理SQL。扩容之后，成本提升了50%，一条逻辑SQL会生成3条物理SQL，系统性能也没有变化。所以得出一个结论：系统一定要带拆分键，否则没有可扩展性。
IN查询
买家与订单场景
具体场景是：提供一个买家的所有订单ID，查出这些订单的信息，订单表按照订单ID进行拆分，SELECT * FROM ORDER WHERE ORDER_ID IN (?,?,?,?...)，假设单DB容量是1000QPS。
比如，2005年数据分片数为16，平均一个买家的订单数：2，IN查询涉及的分片数：期望值接近2，系统容量：16*1000/2=8000。到了2015年，数据分片数为64，平均一个买家的订单数：200，IN查询涉及的分片数：期望值接近64≈全表扫描，系统容量：64*1000/64=1000。在这种场景下，IN查询不具备线性扩展能力。
家庭与孩子场景
具体场景是：提供一个家庭的所有孩子ID，查出这些孩子的信息，孩子表按照孩子ID进行拆分，SELECT * FROM CHILD WHERE CHILD_ID IN (?,?)，假设单DB容量是1000QPS。跟前面的区别在于，订单数会随着时间的推移飞速发展，但是孩子数不会随着时间发生太明显的变化。
假设，2005年，数据分片数：16，平均一个家庭的孩子数：1-2，IN查询涉及的分片数：期望值接近2，系统容量：16*1000/2=8000。2015年，数据分片数：64，平均一个家庭的孩子数：1-2，IN查询涉及的分片数：期望值接近2，系统容量：64*1000/2=32000。在这种情况下，成本提升了50%，系统容量也提升了50%，IN查询实现了线性扩展。
线性扩展
对IN查询来说，必须满足下述条件才能做到线性扩展：IN的值的数目远远小于分片数；一般情况下，IN的值的数目在2-3个；IN的值的数目不会随着业务的发展而增长。相反的，只要有一条不满足，那么IN查询就无法做到线性扩展。
分布式JOIN
分布式JOIN有很多种情况，主要分为两大类：可下推的JOIN，JOIN操作由存储完成，DRDS层针对JOIN的结果进行处理，效率会高一些，因为存储和计算在一起；不可以下推的JOIN，存储层只做单表的查询，DRDS完成JOIN的操作。
同维度的JOIN
可下推的JOIN中很重要的是同维度的JOIN，JOIN的两个表是按照拆分键做的JOIN，简单例子如下：
SELECT* FROM
user JOIN user_address
ON user.user_id= user_address.user_id
user与user_address需要JOIN，并且均以user_id为拆分键。这样的结果是，对于同一个用户，其地址与它在同一个分片内。所以只需要在存储层把JOIN做好就可以了。对于DRDS来说，这个JOIN操作由下面的MySQL或者RDS来完成。DRDS层只需要把JOIN结果返回去就可以了。这种JOIN线性判断的标准是与单表SQL相同。
广播表的JOIN
另外一个比较常用的JOIN是广播表的JOIN。有些表具有以下特点：比较小，总会与其他表进行关联，这时候就不适合将其放在其中一个库上面，那么，这个JOIN就没有办法下推了。广播表是指所有分片中都存在一个完整的副本，一般用于变更比较少，容量比较小，需要频繁与其表发生关联的表。一张拆分表JOIN一张广播表的简单例子如下：
SELECT* FROM
user JOIN user_address
ON user.user_id= user_address.user_id
此时，选择把level表作为广播表复制到每一个分片上去，这样的JOIN也可以做下推，只要做分片内的JOIN就可以了。这样一个查询的线性判断标准与单表SQL相同，由拆分表上的查询决定。
Nested Loop Join
Nested Loop Join是不可下推的分布式JOIN。具体例子如下：
SELECT* FROM
order JOIN user
ON order.buyer_id=user.user_id
user以user_id为拆分键，order（订单）以order_id为拆分键。JOIN不能由存储来完成，只能由DRDS层完成。具体的算法等价于在左表把需要的数据拿出来然后再去右表做应用查询，即以小表驱动（经过WHERE条件过滤后数据量较少的表为小表）。
对于这种JOIN，线性判断标准直观来说是对两个表的查询均需要能够线性。即对驱动表的判断与单表查询相同；对被驱动表的判断：被驱动表的JOIN列是否是拆分键，被驱动表做的IN查询的数目。
实例分析
主要有两张表，order表拆分键为order_id，user表拆分键为User_id。
SELECT* FROM order JOIN user ON order.buyer_id = user.user_id
结果分析：两张表均是全表扫描。
SELECT* FROM order JOIN user ON order.buyer_id = user.user_id WHERE order.id = 1
结果分析：order为驱动表，user表的JOIN列是拆分键，一个order只有唯一一个user。
SELECT* FROM user JOIN order ON user.user_id = order.buyer_id WHERE user.id = 1
结果分析：user为驱动表，并且带了拆分键上的等值条件，order表的JOIN列不是拆分键，对于order表是全表扫描。
SELECT* FROM user_oders JOIN order ON user_oders.order_id = order.order_id WHERE user_oders.user_id = 1
结果分析：user_orders记录了一个用户有哪些订单，拆分键为user_id，user_oders表为驱动表，并且带了拆分键上的等值条件，order表的JOIN列是拆分键，一个user对应的order会随业务的增长而增长，在order表做的IN查询也会增长。
买卖家问题
具体场景是：一个订单，包含买家id（buyer_id）与卖家id（seller_id），买家希望根据买家来查，而卖家则希望根据卖家来查。那么一张表通过买家来拆还是通过卖家来拆？
传统的解法是空间换时间，模仿单机数据库中建索引的这种方式，将数据存两份，一份按买家id拆分，一份按照卖家id拆分。这个方案的缺点是占的空间太大，因为把整个表都冗余起来了。
或许有人认为，一种较好的解决方案是只冗余id列，只需要买家id到卖家id的映射关系和卖家id到买家id的映射关系。在JOIN查询时，随着时间发展，一个买家对应的卖家会越来越多，那么这就是一个错误的方案。更好的方案是把关联关系做一个全冗余，使其避免出现这样的JOIN查询，用更多的空间来换取时间、线性扩展的能力。
