PolarDB-X中一个表的数据会分布到集群中的每个数据节点上。本文将介绍数据在PolarDB-X中是如何分布的。

Data Node

Data Node（DN），是基于MySQL进行开发的，指一个三节点（默认）的MySQL集群，集群内通过Paxos协议进行数据同步。

Partition

PolarDB-X中，数据切分的最小单位是Partition。

Partition对应于DN（MySQL）中的一张表（也称为物理表），注意，这里的Partition与MySQL中分区表的Parition的概念有所不同。

数据将按照特定的算法被路由到不同的Partition中。

Local Index

Local Index指Partition内部的索引，也即在DN上，由MySQL维护的索引。

Global Index

Global Index，也称为全局索引，由一组同构的Partition构成。

Global Index包含两种类型的字段，Key字段与Covering字段，Key字段为索引字段，其余字段为Covering字段。

Global Index有Partition Key与分区算法两个属性，其Partition Key是Global Index的Key字段。

同时，Global Index在Key字段上也会创建一个Local Index，来提升Partition内的查询效率。

对于Key字段的查询，CN可以直接定位到对应的Partition，并通过Partition上的Local Index定位到数据行的位置，查询比较高效。

如图，一个Global Index的示意：

Global Clustered Index

在Global Index中，有一种特殊的类型称为Global Clustered Index。

Global Clustered Index的Covering字段始终包含了所在Table的所有字段（除了索引的Key字段）。

通过DDL语句向Table中添加或者删除字段，或者修改字段的类型等，Global Clustered Index的Covering字段会同步的做变更。

Global Clustered Index可以有效的避免回表的代价。

Index与Table

Local Index 与 Global Index统称为Index。

PolarDB-X中，一个Table由若干Index（Primary Index与Secondary Index）构成。

默认情况下，Primary Key是Global Clustered Index，Secondary Index是Covering字段仅包含主键的Global Index。

Primary Key也称为主表。

一般情况下，PolarDB-X的用户使用标准的CREATE INDEX/ALTER TABLE ADD INDEX等语句创建索引即可，PolarDB-X会自动选择创建Global Index或者Local Index。

对于一个创建索引的操作，PolarDB-X会创建以下索引：

如果索引的Key字段的类型支持，则创建一个Global Index，同时如上文所属，该Global Index的每个分区内也包含了一个Local Index

在所有的Clustered Index（包括Primary Key）上创建一个Local Index

例如，对于订单表orders：

create table orders (
   id bigint, 
   buyer_id varchar(128) comment '买家', 
   seller_id varchar(128) comment '卖家',
   primary key(id),
   index sdx(seller_id),
   index bdx(buyer_id)
)

orders包含三个Global Index，我们使用SHOW FULL CREATE TABLE可以看到完整的索引信息：：

PRIMARY KEY（主表）：其Key字段为id，其Covering字段为buyer_id与seller_id，其Partition Key为Key字段id。同时包含了seller_id与buyer_id两个Local Index。

mysql> show full create table orders\G
*************************** 1. row ***************************
       TABLE: orders
CREATE TABLE: CREATE PARTITION TABLE `orders` (
        `id` bigint(20) NOT NULL,
        `buyer_id` varchar(128) DEFAULT NULL COMMENT '买家',
        `seller_id` varchar(128) DEFAULT NULL COMMENT '卖家',
        PRIMARY KEY (`id`),
        GLOBAL INDEX /* bdx_$d751 */ `bdx` (`buyer_id`) ...,
        GLOBAL INDEX /* sdx_$145a */ `sdx` (`seller_id`) ...,
        LOCAL KEY `_local_sdx` (`seller_id`),
        LOCAL KEY `_local_bdx` (`buyer_id`)
) ENGINE = InnoDB DEFAULT CHARSET = utf8mb4
...

Secondary Index sdx：其Key字段为seller_id，其Covering字段为orders表的主键id，其Partition Key为Key字段seller_id。同时包含了seller_id上的Local Index。

mysql> show full create table sdx_$145a\G
*************************** 1. row ***************************
       TABLE: sdx_$145a
CREATE TABLE: CREATE TABLE `sdx_$145a` (
        `id` bigint(20) NOT NULL,
        `seller_id` varchar(128) DEFAULT NULL COMMENT '卖家',
        PRIMARY KEY (`id`),
        LOCAL KEY `auto_shard_key_seller_id` USING BTREE (`seller_id`)
) ENGINE = InnoDB DEFAULT CHARSET = utf8mb4
...

Secondary Index bdx：其Key字段为buyer_id，其Covering字段为orders表的主键id，其Partition Key为Key字段buyer_id。同时包含了buyer_id上的Local Index。

mysql> show full create table bdx_$d751\G
*************************** 1. row ***************************
       TABLE: bdx_$d751
CREATE TABLE: CREATE TABLE `bdx_$d751` (
        `id` bigint(20) NOT NULL,
        `buyer_id` varchar(128) DEFAULT NULL COMMENT '买家',
        PRIMARY KEY (`id`),
        LOCAL KEY `auto_shard_key_buyer_id` USING BTREE (`buyer_id`)
) ENGINE = InnoDB DEFAULT CHARSET = utf8mb4
...

各Global Index由自己的分区组成，如图：

分区算法

Partition Key

每个Global Index按照Partition Key进行分布。PolarDB-X的Partition Key支持单列与多列。

支持对以下字段类型创建Global Index：

TINYINT/TINYINT UNSIGNED

SMALLINT/SMALLINT UNSIGNED

MEDIUMINT/MEDIUMINT UNSIGNED

INT/INT UNSIGNED

BIGINT/BIGINT UNSIGNED

DATE

DATETIME

TIMESTAMP

CHAR/VARCHAR

注意：由于Global Index的Key字段即为Partition Key，因此PolarDB-X支持在上述类型的字段上创建Global Index。

Partition Key的值允许做修改，例如将上述例子中，某一行的的seller_id从1修改为2。

Partition Key的字段定义也允许修改，例如将上述例子中，将seller_id的类型varchar修改为bigint。此操作会触发该Global Index数据的重新分布。

Hash

PolarDB-X支持Consistent Hash的分区算法。如图：

使用Consistent Hash的分区算法时，会将哈希值的范围（Long.MIN~Long.MAX）划分成连续的区间，区间和Partition一一对应。

计算一个Key所属的Partition时：

会根据Key字段类型，使用不同的哈希函数计算其哈希值
查找哈希值属于哪个一个区间，这是一个二分查找的过程，区间对应的Partition就是Key所属的Partition

Consistent Hash也支持多字段的情况，当有多个字段时，会将各字段合在一起计算哈希值。

因此，当缺少部分字段值的情况下，便无法计算其哈希值，也即无法做分区裁剪，会导致全分区的扫描。

Consistent Hash支持分区的分裂、合并等操作。

注意：Global Index默认使用Consistent Hash分区算法。

Range

PolarDB-X支持按照数据的范围：

与Consistent Hash分区算法不同的是，Range分区直接按照Key的范围划分区间。

Key是按照字节序来进行比较，来判断属于哪个区间的。

Range分区也支持多字段的情况，多字段下与区间的起始点进行比较时，会依次比较各字段，只有当第N个字段的值相同的情况下，才会比较第N+1个字段。

因此，在缺少部分字段值的情况下，Range分区依然能根据前缀进行分区裁剪，不会导致全分区的扫描。

Range分区同样支持分区的分裂、合并等操作。

List

List分区可以理解为一种特殊的Range分区，其每个Partition的区间只包含一个值。

Join Group（WIP）

Join Group由多个Table构成，在同一个Join Group中的Table，Join操作会尝试进行下推优化，如果成功下推，则效率会更高；不在同一个Join Group中的Table，Join操作不会尝试进行下推优化。

注意：

默认情况下，一个Database只包含一个Join Group，这个Database中的所有Table都属于此Join Group。

推荐根据业务情况，将不可能发生Join的Table划分到多个Join Group中去。

Join Group的变更（例如将一个Table的Join Group从a修改为b）只涉及到元数据的变更，几乎没有代价。

Table Group与Partition Group

Table Group是一组Global Index的集合。

处于同一个Table Group中的索引，必须具备同样的数据分布，包括：

同样的Partition数目

同样的分区算法

同样的分区键（分区键的数据类型相同即可，不需要名字相同）

Global Index所属的Table的Join Group一致

注意，数据类型相同，意味着长度、字符集、collation等均相同，例如，varchar(20)与varchar(30)会视为不同的数据类型。

同一个Table Group中的Global Index，区间（或者下标）相同的Partition组成Partition Group。

例如，对于一个使用Consistent Hash的Table Group：

该Table Group包含了idx1、idx2、idx3三个Global Index，每个Global Index有p0~p90共91个Partition，相同下标的Partition对应的哈希值的区间相同。

该Table Group划分成了Partition Group 0~Partition Group 90共91个Partition Group。

PolarDB-X会确保同一个Table Group中的Global Index在数据分布上是对齐的，这代表：

同一个Partition Group中的所有Partition在一个DN上

分裂、迁移、合并等操作以Partition Group为单位进行

例如：

在上述例子中，初始状态下，Partition Group 45、46、47的所有分区都在DN1上，Partition Group 48的所有分区都在DN2上。

当发生Partition Group 47迁移到DN2时，Partition Group 47中的3个分区需要一起迁移到DN2。

Table Group有显式创建和隐式内建两种。

在创建表或者索引时，如果未指定Table Group，PolarDB-X会自动在当前Join Group（默认的Join Group或者指定的Join Group）中，寻找一个匹配的隐式内建Table Group，如果没有匹配到，则创建一个新的隐式内建Table Group。

例如，当一个空的Database建表：

CREATE TABLE t1 (id INT PRIMARY KEY);

t1的Primary Key会创建一个Partition Key为INT，分区算法为Consistent Hash，Partition数为64（默认预分片数为64）的Table Group，假如此Table Group名字为tg0。

当创建第二张表：

CREATE TABLE t2 (
	id INT PRIMARY KEY，
	c1 INT,
	c2 VARCHAR(64),
	INDEX idx1(c1),
	INDEX idx2(c2)
);

t2包含Primary Key、idx1、idx2三个Global Index。

对于Primary Key与idx1，它们的Partition Key为INT，分区算法为Consistent Hash，Partition数为64，因此它们都会匹配到Table Group tg0，并且添加到tg0中。

对于idx2，由于它的类型为VARCHAR(64)，与已有的Table Group都不匹配，因此它会创建一个新的Table Group。

注意：一般情况下，用户无需关注Table Group的分配，也无需为Global Index指定Table Group。

合理划分Join Group

Table Group与Partition Group的存在，使得Global Index Key上的Join操作具备了下推优化的可能。例如，对于上文的例子中：

idx1 join idx2 on idx1.key=idx2.key

idx1与idx2按key做Join操作，由于他们属于同一个Table Group，意味着Key值相同的idx1和idx2的记录，必然在同一个Partition Group内。

而同一个Partition Group内的idx1和idx2的Partition，必然在同一个DN上。

因此这个Join操作，可以下推到DN上执行，做同一个DN上的两个Partition的Join即可。这种优化称为Join下推。

由于避免了数据跨网络的传输，Join下推能极大的提升Join的性能。

但是，Table Group内的Global Index，在发生迁移、分裂等变更时，必须以Partition Group为单位同步进行，这会提升变更的代价，并且变更的粒度相对于Partition级的变更会更大。

在上文的例子中，假如将idx3放在一个Table Group中，idx1和idx2放在另一个Table Group中。我们可以做更细粒度的迁移操作，例如，只迁移idx3的Partition 47到DN2上，如图：

PolarDB-X在为一个Global Index分配Table Group的时候，会在所属表的Join Group内进行搜索。减小单个Join Group的大小，增加Join Group的个数，可以有效的减小单个Table Group的大小，提升迁移等操作的效率。

因此我们推荐使用方能根据业务，将不会发生Join的Table，划分到不同的Join Group去。

例如，用户表、地址表会发生Join，那它们放在一个Join Group里；商品表、库存表会发生Join，把它们放在一个Join Group里。

这样，虽然用户表的主键<用户id>与商品表的主键<商品id>可能都是同样的数据类型，同样的分区算法，但是他们不会被调度到同一个Table Group中，也就降低了迁移等的代价。

Database

PolarDB-X中每创建一个Database（也称为逻辑库），其所涉及的每个DN上也会创建唯一的一个Database（也称为物理库）。

Locality（WIP）

PolarDB-X的Locality是Database、Join Group、Table Group、Partition Group的一个属性。用来标记所属对象位于那一个或者哪一些DN上。

这些对象的级别从低到高为：

Partition Group
Table Group
Join Group
Database

当低级对象未设置Locality属性时，会继承高级别对象的Locality属性；当低级别对象设置Locality属性时，会忽略高级别对象的Locality属性。

例如：

CREATE DATABASE d1 LOCALITY='DN=DN1,DN2'

为Database d1指定了Locality为DN1和DN2，即代表整个Database的数据默认分布在DN1与DN2两个DN上。

在d1中创建Table Group tg1：

CREATE TABLEGROUP tg1 LOCALITY='DN=DN1'

代表tg1的数据默认只分布在DN1上。

在d1中创建Table Group tg2：

CREATE TABLEGROUP tg2

tg2没有指定Locality属性，因此它会继承d1的Locality属性，其数据分布在DN1与DN2两个DN上。

调整tg2的一个Partition Group的Locality属性：

ALTER TABLEGROUP tg2 ALTER PARTITION GROUP p0 SET LOCALITY='DN=DN3'

将Partition Group p0的Locality设置为DN3，p0的数据会迁移到DN3上。

注意：当使用Locality属性设置了某个对象的DN为单一DN节点时，该对象的数据将不会在集群内被调度，会固定在指定的DN上。

特殊的两种分布

单表

单表是一种Partition数为1的表，没有Partition Key。同时，单表只包含Primary Key一个Global Index。

默认情况下，一个Database所有的单表都在一个Table Group中，此Table Group仅包含一个Partition Group。也即，一个Database所有的单表默认都在一个DN中。

我们可以通过创建更多Table Group，并对这些Table Group指定不同的Locality属性，将单表打散到不同的DN上。

广播表

广播表没有Partition Key，只有一个Partition，所在Database所在的DN节点都会包含这个Partition的副本。

一个Database所有的广播表都在一个Table Group中，此Table Group仅包含一个Partition Group。这个Table Group不允许也没有必要做修改。

当一个新的DN节点添加到集群中，会先将广播表所在的Table Group复制到新的DN上，之后才允许其他Table Group的Partition Group迁移到该DN上。

未完待续

下一篇，我们会分享为什么这样设计，我们会继续探讨：

Hash vs Range

Global Index & Global Clustered Index在分布式数据库中的核心位置

为什么要保留Local Index

Partition Group、Table Group、Join Group，为什么要搞这么多Group，我们应该关注什么

PolarDB-X 数据分布解读（一）