分库分表：查询特征提取与表达——以 merger 分发为例

[flycash]

仅限中文

背景

在结果集处理的相关问题下 #182 ，我们能够看到一个问题，即查询特征会直接决定了后续结果集如何处理。实际上，如果单纯站在分库分表的角度，那么不仅仅是结果集处理，连目标 SQL 生成都会收到查询特征的影响。比如说在计算 AVG(age) 的时候，生成的目标 SQL 就不是直接 SELECT AVG(age) 而是 SELECT COUNT and SUM。

于是我们就面临一个问题，如何提取并且表达这些查询特征？如果只考虑目前已知的几个情况：

• 是否使用聚合函数，具体的聚合函数，以及聚合函数有没有附加 DISTINCT 关键字。
• 是否有 HAVING
• 是否有 GROUP BY
• 是否有 DISTINCT
• 是否有 ORDER BY

现在我们的目标是根据这些特征来创建对应的 merger。

创建 merger 可能需要用到这些信息：

• 结果集的列
• GROUP BY 的列
• ORDER BY 的列
• HAVING 条件（如果将来我们支持了 HAVING 的话）

所以我们的困难就是两个：

• 提取这些特征并表达
• 根据这些特征找准 merger 来初始化，在初始化的过程中，我们可能需要用到一些数据，这些数据需要准备好。

如果以 merger 来作为例子，那么就可以归结为一句话：我怎么确定我该使用哪个实现？这方面强调非常高的扩展性.

if-else 方案

if-else 也可以称为飞机场方案（参考自 Redis）。即我们将全部的分发逻辑都放在一个巨大的方法里面。这个方案什么也不需要干，就是根据查询的特征来确定究竟应该使用哪个实现。

唯一需要注意的就是 if-else 代码要有条理。

比如说我们按照 SELECT 语句的顺序来写 if-else。

• 先判断 SELECT XXX 部分，有没有使用聚合函数等
• 再判断 ORDER BY 不分..

伪代码类似于：

func NewMerger(feats...query.Feature) merger.Merger {
     if SELECT xxx {
         if GROUP BY {
               // ....
         }
     } else if GROUP BY {
           // ...
     }
}

在这个伪代码里面，在 if 和 else 分支里面都进行了类似的判断。这是因为本身聚合函数和 ORDER BY 是可以合并使用的，也可以单独使用。所以在两个分支里面都需要判断。

这种写法可以确保我们后续在维护的时候只需要沿着 SELECT 的语法特性去检查，就可以比较容易看出来我们是否已经遗漏了。

状态机

目前我的初步设想是利用状态机的机制。它相当于将这些规则做成一个状态机：

• 如果有聚合函数，但是没有 GROUP BY，ORDER BY，DISTINCT，那么就可以使用 AggregatorMerger 实现
• 如果有聚合函数，有 GROUP BY，而且 GROUP BY 恰好是 SK，那么就可以直接使用普通的合并结果集的方案
• ...

这本质上就是：当我到达状态 A 的时候，我可以触达的下一个状态就有限了。例如在聚合函数的例子里面，我们首先判断有没有聚合函数，在有了聚合函数之后，就步入到有聚合函数的状态。在这个状态下，可以转换过去的就是两个状态：有 GROUP BY 或者没有 GROUP BY。当我进入到有 GROUP BY 之后，我就还可以朝着两个状态前进，即GROUP BY 里面的都是 SK，以及不全是 SK。当我进去全是 SK 的状态之后，我面前就得到了最终状态。这个最终状态就可以决定使用哪个 merger。

这算是一个不怎么常见的设计方案，即利用状态机来解决复杂的分发逻辑，并保持良好的扩展性。所以状态接口可以设计成为：

type State interface {
    Move(s *ShardingSelector) (State, error)
}

它的好处就是可以带来极好的扩展性。缺点就是整个状态转换的逻辑不直观，至少比一大堆的 if-else 更不直观。因为如果我们直接使用 if-else 的话，整个分发逻辑都在一个地方。而这种设计则是将分发逻辑分散到了不同的实现里面。

表格驱动

这是另外一种可行的思路。即我们维护一个表格。表头就是各种特征。那么具体到我们的程序里面，就是维护了一个 bool 数组。

features [N]bool

这个 N 就是我们的特征数量。例如说有聚合函数是一个特征，有AVG又是一个特征。那么类似地，可以用 features[0] 来代表是否有聚合函数， features[3] 是否具备GROUP BY。

事实上我们可以考虑将 [N]bool 替换一个简单的 64 比特的数字。那么我们就可以表达 64 种特征，将来也可以扩展到任意多个字节。

谁来分发

这里始终有一个问题就是，不管是用 if-else，还是状态驱动，还是表格驱动，谁来真正维护这种分发逻辑。

那么按照封装性来说，只有 merger 包才知道各个实现适用于什么场景。那么在这种情况下，只能由 merger 来分发。那么问题进一步就变成，如果 merger 来提供分发逻辑，那么它的接口该怎么设计？

我们无法放过去 merger 包里面，因为存在循环依赖的问题。

第一种可行的是：

// merger/dispatcher

func Dispatch(feat query.Feature, params Params) {

}

当然子包名和方法名都可以换。

接下来要解决的问题是，query.Feature 该如何定义，以及 ShardingSelector 怎么提供这个 Feature。

一种可行的设计是：

// query 包
type Query struct {
    Feature
}
type Feature struct {

}

ShardingSelector 负责准确描述每一个查询的特征。

紧接着又有一个问题。每一个 merger 实现的初始化参数都不一样，但是大致上可以归类为：

• SELECT xxx 的具体内容，如列名，所在位置
• ORDER BY 部分
• GROUP BY 部分

所以

type Params struct {
    OrderBy []merger.Column
   GroupBy []merger.Column
   Select []merger.Column
}

不过目前来看，还是不够优雅，依旧存在扩展性和可维护性的问题。

[juniaoshaonian]

type Selector struct {
	HasGroupBy bool
	HasOrderBy bool
	HasLimit   bool
	// group by 的键是否是分片键
	HasShardingKey bool
	HasAggregate   bool
	HasHaving      bool
}

type State interface {
	Move(s *Selector) (State, error)
}
// 终结状态
type MergerState interface {
	State
	GetMergerType() Merger
}
// 初始状态
type InitialState struct {
}

func (i InitialState) Move(s *Selector) (State, error) {
	// 判断是否含有groupby字句
	if s.HasGroupBy {
		return GroupByState{}, nil
	}
	return NoGroupByState{}, nil
}

type GroupByState struct {
}

// groupby的键是否为分片键
func (g GroupByState) Move(s *Selector) (State, error) {
	if s.HasShardingKey {
		return GroupByShardingKeyState{}, nil
	}
	return NoShardingKeyState{}, nil
}

type GroupByShardingKeyState struct {
}

// 是否含有聚合函数模块
func (g GroupByShardingKeyState) Move(s *Selector) (State, error) {
	if s.HasAggregate {
		return GroupByShardingKeyAggregateState{}, nil
	}
	return GroupByShardingKeyNoAggregateState{}, nil
}

type GroupByShardingKeyAggregateState struct {
}
// 是否含有having字句
func (g GroupByShardingKeyAggregateState) Move(s *Selector) (State, error) {
	if s.HasHaving {
		return GroupByShardingKeyAggregateHavingState, nil
	}
	return GroupByShardingKeyAggregateNoHavingState{},nil
}

type GroupByShardingKeyAggregateNoHavingState struct {
}

// 判断是否含有order by字句
func (g GroupByShardingKeyAggregateNoHavingState) Move(s *Selector) (State, error) {
	if s.HasOrderBy {
		return GroupByShardingKeyAggregateNoHavingOrderByState{}, nil
	}
	return nil, nil
}

// 最终到达最终状态，有groupby且groupby的键为分片键，有聚合函数，没有having字句，有order by字句
type GroupByShardingKeyAggregateNoHavingOrderByState struct {
	
}


// 最终状态move的返回值是nil，通过这个我们可以拿到最后的merger
func (g GroupByShardingKeyAggregateNoHavingOrderByState) Move(s *Selector) (State, error) {
	return nil,nil
}

func (g GroupByShardingKeyAggregateNoHavingOrderByState) GetMergerType() Merger {
	return &sortmerger.Merger{}
}

大佬这样设计我们的分发逻辑是否可行，上面简单展示了分发含groupby且groupby的键是分片键有聚合函数没有having有orderby的情况

[flycash]

牛逼，完全理解了我的思路。

我先确认一个点，就是我提到了两个思路，一个是状态机的思路，一个是 if-else 的思路。你从你个人的实践经验出发，你喜欢哪一个？

[juniaoshaonian]

这个状态机的好一点，但是状态机有个问题就是我的中间状态比较多，有什么方法可以优化吗

[longyue0521]

选if-else还是状态机,问题复杂度及看代码的实现思路.

如果按照上面的示例,Move的职责就是根据判断条件创建下一个状态并在最终状态内部干所有的活.可能if-else更好理解一些,省去不必要的“空”中间态.

func New(* ShardingSelector) (Merger, error) {
     // 有groupby且groupby的键为分片键，有聚合函数，没有having字句，有order by字句
     if  s.HasOrderBy && s.HasShardingKey && s.HasAggregate && !s.HasHaving && s.HasOrderBy {
        return GroupByShardingKeyAggregateNoHavingOrderByState{}.GetMergerType, nil
     }
    // ......
}
// 最终到达最终状态，有groupby且groupby的键为分片键，有聚合函数，没有having字句，有order by字句
type GroupByShardingKeyAggregateNoHavingOrderByState struct {}

// 最终状态move的返回值是nil，通过这个我们可以拿到最后的merger
func (g GroupByShardingKeyAggregateNoHavingOrderByState) Move(s *Selector) (State, error) {
	return nil,nil
}

func (g GroupByShardingKeyAggregateNoHavingOrderByState) GetMergerType() Merger {
	return &sortmerger.Merger{}
}

如果Move还需要解析一些数据,创建“子”merger,那么可能状态机更好——关注点分离,每一个状态处理一部分并在最终状态组合.

initState <--> state1 <-->  state2
                        解析数据        解析数据
                        创建merger1 创建merger2并组合merger1形成最终的merger

如果大部分merger是这种(未来极可能会变成这种情况),分阶段创建“子”merger并在最终状态里组合成最终merger,用状态机比较好.

[flycash]

这里我有两个想法。

• 让使用 merger 的人来控制。也就是说 merger 本身不管分发的事情，它只提供抽象和不同的实现。至于用哪个实现，那么就是用这个包的人去推断。这个设计最开始是按照这个思路来进行的。但是缺点就是 merger 才清楚具体的实现有什么缺陷，所以事实上应该 merger 来执行这个分发。
• 如果是 merger 来执行分发，那么问题就是怎么让 merger 设计一个非常清晰的分发代码。但是在这种思路之下，那么用状态机就不太好设计了，可能一大堆的 if-else 更加合适。

在第二种想法中，困难之处在于怎么让 merger 接收灵活的参数，比如说有没有 HAVING，有没有 GROUP BY 等。在我最开始的设计中，采用了非常偷懒的设计，接收整个 ShardingSelector，merger 包肯定是用不了的，因为这意味着一个循环引用。或许可以考虑定义个一个非常简单的结构体，里面就放这种查询特征。

根据判断条件创建下一个状态并在最终状态内部干所有的活

这也是我犹豫的一个点。如果站在 eorm 本身来说，的确是可以在最终状态内部干所有的活。但是如果我后面用这个 merger 建设一个 driver 形态，或者 proxy 形态的分库分表，那么就无法复用这部分了。我说 merger 看上去是最适合放这种分发逻辑，也是出于这种考虑。