数据库 - 分布式主键方案

创建时间:
2017-04-01 01:26
最近更新:
2018-10-05 21:10

Resource

  1. flickr - 分布式唯一主键生成策略的一种开销比较小的方法
  2. 每次生成 100 个唯一 ID
  3. 微博发号器考量
  4. ObjectId - 分布式主键生成策略
  1. 高并发分布式系统中生成全局唯一 ID 汇总
  2. C# 算法
  3. 涉及
  4. Leaf - 美团点评分布式 ID 生成系统

Resource - ID 生成器

  1. 一个完整的 ID 生成器,并极大地降低了并发重复的概率
  2. 小议 ID 生成算法
  3. ID 生成器 - 生成唯一 ID 的基本原理

评估

所有表 INSERT 时均使用 预定义主键 而非 自增列主键,优点:

  • 增 与 改删 相同,均返回 受影响的行数,而非 最新自增值。

Keywords

  • ID
  • 主键
  • 分布式
  • 全局
  • 自增
  • 单调递增
  • 发号器

需求

  • 最好是 int32。
  • 集群内唯一。
  • 单调递增。索引友好。(新 ID 大于 旧 ID。如无法满足此要求,至少要大于大部分已有的 ID)
  • 递增步长无规律,无法由此推断数据量。
  • 无中心,任何机器均可生成,各机器间无需同步。水平拆分友好。
  • 本地生成,无需网络往返。

无序的 GUID/UUID 插入性能差 的原因

众所周知 关系型数据库的索引 大都是 B+树 的结构。例如 ID 字段,索引树的每一个节点都存储着若干个 ID。
如果 ID 按递增的顺序插入,例如 陆续插入 8、9、10,新的 ID 都只会插入到最后一个节点当中。当最后一个节点满了,会裂变出新的节点。因为这样节点的分裂次数最少,而且充分利用了每一个节点的空间,因此 这样的插入 性能比较高,
但是如果 插入完全无序,不但会导致一些中间节点产生分裂,也会白白创造出很多不饱和的节点,这样会大大降低数据库插入的性能。

Tony Note: Twitter-Snowflake、MongoDB-ObjectId 等任何依赖系统时间的方案都会有暂未解决的回拨问题

2018-06-08 因为 未找到 "系统时间 回拨/回退 问题" 的解决方案,未采用 Twitter-Snowflake 以及 任何依赖系统时间的方案。

~~~~~~~~~~ 以下为各种方案 ~~~~~~~~~~

数据库自增列 (SqlServer, MySQL)

优点

  • 数据库 与 代码 均易于实现。
  • 空间占用小。
  • 性能好。
  • 按顺序增长,有利于排序、分页、索引。

缺点

  • 不是所有的数据库都提供了自增列的功能。
  • 不同厂商的数据库的语法及实现不一致。
  • INSERT 前无法指定 ID。
  • 水平分表时不适用
  • 在数据库之间进行 同步、复制、合并、迁移 可能会有重复值导致冲突。
  • 容易被采集。假设文章页面是 article.aspx?id=1,那么采集程序一个循环就能够拿走全部文章。而 article.aspx?id=xxxx-xxxxxxxx-xxxx-xxxx,那么简单的循环就不行了。
  • 容易被猜测记录数量。

Sequence (Oracle, DB2 etc.)

  • 可多个表共享一个 Sequence,也可每个表独享一个 Sequence。
  • 详见本站专文

复合主键 (集群编号 + 集群内的自增值)

优点

  • 实现简单

缺点

  • 相比单列主键代码更复杂
  • 若是后期才由单列主键转为复合主键改动成本相当大。

MAX() + 1

  • 插入记录前先查询主键列的最大值,+1 后用作新记录的 ID。

专用自增ID数据库

一个数据库,专用于自动生成并获取自增 ID。

专用 MAX() + 1 数据库

一个数据库,专用于记录各个对象的主键值的当前最大值。主要有两列: 对象名、当前最大值。取数逻辑为: 如对象名不存在则创建并返回 自增起点值; 如存在则当前最大值 +1 并返回。

为避免单点故障,可投入多台服务器,每台服务器都布署一个这种 "专用 MAX() + 1 数据库",区别是 "增长起点 (auto_increment_offset)" 错开,"增长步长 (auto_increment_increment)" 为服务器数量,使得每台服务器生成的 ID 错开。这样相当于把生成 ID 的压力分散到各个服务器节点上。当其中某台服务器故障,系统自动切换到另一台服务器上获取 ID。

优点

  • ID 短。
  • 支持分表。
  • 适合大型应用。

缺点

  • 每次查询 MAX() + 1 需 1 次网络往返。
  • 单点,故障将导致整体不可用。

集群中每台机设置不同的 自增起点 (auto_increment_offset),使得每台机生成不重叠的 ID 段。

优点

  • 实现简单
  • 易于根据 ID 判断数据处在哪个库

缺点

  • 更易超出自增上限,需关注各 ID 增长状况。
  • 集群中每台机设置不同的 自增起点 (auto_increment_offset) 与 自增步长 (auto_increment_increment),使得每台服务器生成的 ID 错开。

Redis 生成集群内全局唯一 ID

利用 Redis 的原子操作 INCR 和 INCRBY 来实现。

优点

  • 不依赖于数据库,灵活方便,且性能优于数据库。
  • 数字ID天然排序,对分页或者需要排序的结果很有帮助。

缺点

  • 如果系统中没有Redis,还需要引入新的组件,增加系统复杂度。
  • 需要编码和配置的工作量比较大。

Flickr Ticket 服务器

MySQL 配置

节点一:
auto_increment_increment=2;
auto_increment_offset=1;

节点二:
auto_increment_increment=2;
auto_increment_offset=2;

Note: 上述配置最好放在配置文件中,否则 MySQL 服务重启将丢失配置;如果直接通过 set 来设置,已经建立的连接不会改变变量的值,特别是使用连接池的时候。

分别在两个库里建表

// Ticket32 和 Ticket64 表,分别用于提供 int32 和 int64 主键。
CREATE TABLE `tickets64` (
    `id` bigint(20) unsigned NOT NULL auto_increment,
    `stub` char(1) NOT NULL default '',
    PRIMARY KEY (`id`),
    UNIQUE KEY `stub` (`stub`)
) ENGINE=MyISAM
//通过 replace 促使 id 自增,这样表中只有一条记录:
REPLACE INTO Ticket64 (stub) VALUES ('a');
//在同一个连接内,获取自增值:
SELECT LAST_INSERT_ID();
  • 注意建的是 MyISAM 表, MyISAM 是表级锁,能保证所有 replace 的原子性。
  • 对 MyISAM 性能影响比较大的参数是 key_buffer_size ,可以适当调整。

优点

  • 对于数据量不是特别大的应用,长度最小,从零开始。
  • 如果已经有应用是基于 sequence 或者 mysql 的自增 id ,采用此方案非常容易迁移,兼容性好。

这种方案是没有绝对顺序的,只能有一个近似顺序。有可能一个实例跑的更快。
基于 MySQL 自增列实现,至少需要两个节点容灾。

Random (System.Security.Cryptography.RNGCryptoServiceProvider)

timestamp + random

GUID

优点

  • 不限机器、进程,全局唯一
  • 实现最简单
  • 便于库间同步、合并、迁移。

缺点

  • 不能使用聚集索引。无序 (GUID 最大的问题),不利于索引。例如 SQL SERVER 会默认在主键列上建立聚集索引。聚集索引与物理存储位置保持一致,由于 GUID 无序,INSERT 时通常需要将新记录插入已有的某两条记录之间,这时会产生页面分割,导致插入性能下降并产生磁盘碎片。
  • 磁盘占用 为 int 的 4 倍,性能不如 int。
  • 不易读。编码时没有 int 方便。

GUID 递增变体

自定义编码规则

MongoDB ObjectId - 详见本站专文

  • 12byte。仅比 GUID 少 16-12=4byte。

Twitter Snowflake - 详见本站专文

  • int64 = 8byte = 64bit = 1位符号 + 41位毫秒级时间 + 10位机器ID + 12位毫秒内序列。
  • 可以调整 机器位数 和 毫秒内序列位数。