Shardingsphere: 基于Snowflake的Hash-Sharding分片算法

[xydonne]

特性：

• 在主键为Snowflake算法生成ID时可使用。
• 极大简化分库分表配置
• 拓展库表不需要做数据迁移

原理：

根据SnowflakeID生成三个维度的值
timestamp：SnowflakeID的前42位
根据此值可以指定一个时间点，对此时间点后的库表关系进行重映射，在不做数据迁移的情况下拓展库表
databaseHash：SnowflakeID通过MurmurHash算法生成32位Hash值的前16位
最大可分65536个库（0x0000 - 0xFFFF）
tableHash：SnowflakeID通过MurmurHash算法生成32位Hash值的后16位
最大可分65536个表（0x0000 - 0xFFFF）

yaml配置

dataSource:
  db0: !!com.alibaba.druid.pool.DruidDataSource
    driverClassName: com.mysql.jdbc.Driver
    url: jdbc:mysql://localhost:3306/db0?useUnicode=true&characterEncoding=utf8
    username: root
    password: root
  db1: !!com.alibaba.druid.pool.DruidDataSource
    driverClassName: com.mysql.jdbc.Driver
    url: jdbc:mysql://localhost:3306/db1?useUnicode=true&characterEncoding=utf8
    username: root
    password: root
  db2: !!com.alibaba.druid.pool.DruidDataSource
    driverClassName: com.mysql.jdbc.Driver
    url: jdbc:mysql://localhost:3306/db2?useUnicode=true&characterEncoding=utf8
    username: root
    password: root
  db3: !!com.alibaba.druid.pool.DruidDataSource
    driverClassName: com.mysql.jdbc.Driver
    url: jdbc:mysql://localhost:3306/db3?useUnicode=true&characterEncoding=utf8
    username: root
    password: root

hash:
  snowflake_hash.id:
    2016-10-31T17:00:00:
      0x0000:
        database: db0
        tables:
          0x0000: t_snowflake_hash_0
          0x8000: t_snowflake_hash_1
      0x8000:
        database: db1
        tables:
          0x0000: t_snowflake_hash_2
          0x8000: t_snowflake_hash_3
    2016-11-20T17:00:00+08:
      0x0000:
        database: db2
        tables:
          0x0000: t_snowflake_hash_4
          0x8000: t_snowflake_hash_5
      0x8000:
        database: db3
        tables:
          0x0000: t_snowflake_hash_6
          0x8000: t_snowflake_hash_7

在此种规则下，原本的BetweenSharding没有太大意义。
所以改成新的查询方式BETWEEN #{lower} AND #{upper}
lower：
前32位（(lowerTimestamp >>> 10)-1<<32 ）
中16位（lowerDatabaseHash）
后16位（lowerTableHash）
upper：
前32位（(upperTimestamp >>> 10)+1<<32 ）
中16位（upperDatabaseHash）
后16位（upperTableHash）
表示查询lowerTimestamp到upperTimestamp时间段内，lowerDatabaseHash到upperDatabaseHash数据库分片，lowerTableHash到upperTableHash表分片的数据。

TODO：

1. 配置的参数校验
2. 目前走的是dynamic=true的方式，将会有一堆问题。

dynamic=true导致的问题：

1. 无法写H2的单元测试，因为实际的语句是SELECT * FROM db.table，H2会把db字段当成schema，导致无法查询。
2. dynamic=true情况下因为没有映射关系，所以无分片键值的情况下无法做全映射，但Hash-Sharding有全映射关系，本质上可以在无分片键值的情况下做全映射。
3. HashDatabaseAlgorithm这个类是多余的，HashAlgorithm足够维护全部的映射关系。
4. 以SELECT * FROM db.table的方式对所有的库进行了查询，实际上可以通过db.table查询指定的库，而非全查。
5. 因为以SELECT * FROM db.table方式查询，所以dsName得和真实dbName一致，不然会出错。

DEMO：

https://github.com/xydonne/sharding-jdbc/tree/hash-sharding/186
参见hash-sharding/186分支，把测试用例当DEMO写了。

[hanahmily]

目前你的这个想法是做了两层映射，第一层其实是一个线性递增，第二层是一个hash均匀。这样达到两个目的，可以横向扩展有能保证数据分布均匀。思想与这篇文章比较接近一种支持自由规划无须数据迁移和修改路由代码的Sharding扩容方案。

关于算法有一个问题：

1. hash部分，为什么要对高位和低位分别对应分库和分表？可以拿同一个hash值去映射嘛？
2. hash后可以做mod运算嘛？如果可以，配置会较为方便

关于yaml配置有几个问题：

1. 如果配置的时候用16进制，那么就太不明确了。可以考虑redis cluster的做法，用十进制数去配置。而且要配置范围，而不是只配置分割数。
2. 不要用数值当做key。且数据要明确

举例来说，如下配置：

2016-10-31T17:00:00:
      0x0000:
        database: db0
        tables:
          0x0000: t_snowflake_hash_0
          0x8000: t_snowflake_hash_1

应该配置为：

timeRange: less than 2016-10-31T17:00:00
databases:
    - databaseRange: less than 32768
       database: db0
       tables:
           - tableRange: less than  32768
              tableName: t_snowflake_hash_0
           - tableRange: less than MAXVALUE
              tableName: t_snowflake_hash_1

关于动态表的问题，由于你实现的只是一个算法。其实不用考虑使用你这个算法的人是否使用动态表或不是动态的表。

最后demo我看了一下 ，Guava实现了murmur3_32 算法，这就不要自己去实现了

[xydonne]

1.1 hash部分，拿同一个hash值去映射。会导致比如库的range（0-100），库下表的range（0-65535），因为库和表的hash映射相同，会导致表中只有0-100有数据，101-65535无数据。

1.2 hash后可以做mod运算。
因为分库分表本身就是蛮复杂的事情，容易出错，为了减轻了认知负担和选择成本。当时的思路是“There should be one-- and preferably only one --obvious way to do it.”

range和mod的选择上，range的分片自由度更大。如果要做库的拆分和合并，相对mod更易理解。

强制用户配置所有库，以及所有库下的所有表。是因为通过表达式算表，虽然配置简单，但对用户建立的表，命名上有要求。

2.1 yaml配置，写16进制，10进制，2进制都行，最终都会装换成Integer。16进制确实不直观。
range配置上，配置范围与配置分割数都行。个人觉得配置range，可以对用户的range配置进行校验；配置分割更简单，怎么配都对，但缺乏校验，会导致不是用户想要的分片。

2.2 这点确实，当时整个配置就是个Map>>> hash
YAML规范里，是不是应该新建一个Bean，key就是Bean中一个字段？

murmur3的算法，需要改成guava的

[hanahmily]

1.1 我理解了由于你是范围映射，所以需要hash值不同。
1.2 正如你说，range会更加灵活，这套配置的算法适用性更强。
以上两点我比较赞同

2.1 我希望能比较明确的进行配置，用户使用不要有歧义产生。所以我还是坚持用range配置

2.2 确实key就是bean中的字段

[hanahmily]

2.0版本后结构发生变化，故放弃该版本合并