Tinyid是用Java开发的一款分布式id生成系统，基于数据库号段算法实现。
Tinyid提供了两种调用方式，一种基于Tinyid-server提供的http方式，另一种Tinyid-client客户端方式。
开源地址：https://github.com/didi/tinyid
实现原理
1.Tinyid是基于数据库发号算法实现的，简单来说是数据库中保存了可用的id号段，tinyid会将可用号段加载到内存中，之后生成id会直接内存中产生。
2.可用号段在第一次获取id时加载，如当前号段使用达到一定量时，会异步加载下一可用号段，保证内存中始终有可用号段。
3.(如可用号段1-1000被加载到内存，则获取id时，会从1开始递增获取，当使用到一定百分比时，如20%(默认)，即200时，会异步加载下一可用号段到内存，假设新加载的号段是1001-2000,则此时内存中可用号段为200-1000,1001~2000)，当id递增到1000时，当前号段使用完毕，下一号段会替换为当前号段。依次类推。
优化手段一、号段
Tinyid解决了对DB访问比较频繁，DB压力比较的问题，主要实现思路为生成一批id，可以看成是一个id范围，例如(1000,2000]，这个1000到2000也可以称为一个“号段”，我们一次向DB申请一个号段，加载到内存中，然后采用自增的方式来生成id，这个号段用完后，再次向DB申请一个新的号段，这样对DB的压力就减轻了很多，同时内存中直接生成id，性能则提高了很多。
所以Tinyid数据表设计时，只需要满足存储一个范围即可，一个断点（Tinyid使用右端点）和一个步长可以确定一个范围。
搭建Tinyid都必须提前建表tiny_info、tiny_token。
CREATE TABLE `tiny_id_info` (
`id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',
`biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '业务类型，唯一',
`begin_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '开始id，仅记录初始值，无其他含义。初始化时begin_id和max_id应相同',
`max_id` bigint(20) NOT NULL DEFAULT '0' COMMENT '当前最大id',
`step` int(11) DEFAULT '0' COMMENT '步长',
`delta` int(11) NOT NULL DEFAULT '1' COMMENT '每次id增量',
`remainder` int(11) NOT NULL DEFAULT '0' COMMENT '余数',
`create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '创建时间',
`update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新时间',
`version` bigint(20) NOT NULL DEFAULT '0' COMMENT '版本号',
PRIMARY KEY (`id`),
UNIQUE KEY `uniq_biz_type` (`biz_type`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'id信息表';
CREATE TABLE `tiny_id_token` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增id',
`token` varchar(255) NOT NULL DEFAULT '' COMMENT 'token',
`biz_type` varchar(63) NOT NULL DEFAULT '' COMMENT '此token可访问的业务类型标识',
`remark` varchar(255) NOT NULL DEFAULT '' COMMENT '备注',
`create_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '创建时间',
`update_time` timestamp NOT NULL DEFAULT '2010-01-01 00:00:00' COMMENT '更新时间',
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT 'token信息表';tiny_id_info表是具体业务方号段信息数据表
max_id ：号段的最大值
step：步长，即为号段的长度
biz_type：业务类型
号段获取对max_id字段做一次update操作，update max_id= max_id + step，更新成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]。
tiny_id_token是一个权限表，表示当前token可以操作那些业务的号段信息。
@Override
@Transactional(isolation = Isolation.READ_COMMITTED)
public SegmentId getNextSegmentId(String bizType) {
// 获取nextTinyId的时候，有可能存在version冲突，需要重试
for (int i = 0; i < Constants.RETRY; i++) {
// select id, biz_type, begin_id, max_id, step, delta, remainder, create_time, update_time, version
// from tiny_id_info where biz_type = ?
TinyIdInfo tinyIdInfo = tinyIdInfoDAO.queryByBizType(bizType);
if (tinyIdInfo == null) {
throw new TinyIdSysException("can not find biztype:" + bizType);
}
Long newMaxId = tinyIdInfo.getMaxId() + tinyIdInfo.getStep();
Long oldMaxId = tinyIdInfo.getMaxId();
// update tiny_id_info set max_id= ?, update_time=now(), version=version+1
// where id=? and max_id=? and version=? and biz_type=?
// CAS
int row = tinyIdInfoDAO.updateMaxId(tinyIdInfo.getId(), newMaxId, oldMaxId, tinyIdInfo.getVersion(),
tinyIdInfo.getBizType());
if (row == 1) {
tinyIdInfo.setMaxId(newMaxId);
SegmentId segmentId = convert(tinyIdInfo);
logger.info("getNextSegmentId success tinyIdInfo:{} current:{}", tinyIdInfo, segmentId);
return segmentId;
} else {
logger.info("getNextSegmentId conflict tinyIdInfo:{}", tinyIdInfo);
}
}
throw new TinyIdSysException("get next segmentId conflict");
}以上是获取号段代码，基于CAS（Compare And Swap）思想。该方法事务的隔离级别设置为READ_COMMITTED（提交读），主要为了考虑以下两点：
1.Transactional标记保证query和update使用的是同一连接。
2.MySQL默认事务隔离级别REPEATABLE_READ（可重复读，MySQL底层使用MVCC），保证同一个事务中读到的version字段相同（循环调用tinyIdInfoDAO.queryByBizType(bizType)获取的结果是没有变化的），感知不到其他事务对version字段的改变，可能会导致CAS失败。
优化手段二、双缓存
在一个号段用完后，需要向数据库申请下一个号段，此时客户端需要等待，造成性能波动。
Tinyid使用双缓存（从数据库加载到内存中的号段）解决这个问题，在号段用到一定程序（默认20%）的时候，就去异步加载下一个号段，保证内存中始终有可用号段，则可避免性能波动。
protected SegmentIdService segmentIdService;
protected volatile SegmentId current; // 当前号段
protected volatile SegmentId next; // 下一号段
private volatile boolean isLoadingNext; // 是否正在加载下一号段
private Object lock = new Object();
private ExecutorService executorService = Executors.newSingleThreadExecutor(new NamedThreadFactory("tinyid-generator")); // 加载下一号段的异步线程池nextId()方法用于从缓存中获取一个id。
@Override
public Long nextId() {
while (true) {
if (current == null) {
// 懒加载，申请当前号段
loadCurrent();
continue;
}
// 从当前号段缓存中获取一个id
Result result = current.nextId();
// 当前号段缓存的id用尽
if (result.getCode() == ResultCode.OVER) {
loadCurrent();
} else {
// 当前号段用到一定程度，触发异步加载下一号段
if (result.getCode() == ResultCode.LOADING) {
loadNext();
}
return result.getId();
}
}
}loadCurrent()加载当前号段，使用synchronized关键字保证线程安全。有两个安全地方可能用到这个方法，一个是初始化懒加载当前号段，另一个是当前号段缓存的id用尽，使用下一号段替换当前号段。
public synchronized void loadCurrent() {
if (current == null || !current.useful()) {
if (next == null) {
// 从数据库中查询一个号段
SegmentId segmentId = querySegmentId();
this.current = segmentId;
} else {
// 用下一号段替换当前号段
current = next;
next = null;
}
}
}当前号段用到一定程度，调用loadNext()方法异步加载下一号段。
public void loadNext() {
// double check
if (next == null && !isLoadingNext) {
synchronized (lock) {
if (next == null && !isLoadingNext) {
isLoadingNext = true;
executorService.submit(new Runnable() {
@Override
public void run() {
try {
// 无论获取下个segmentId成功与否，都要将isLoadingNext赋值为false
next = querySegmentId();
} finally {
isLoadingNext = false;
}
}
});
}
}
}
}优化手段三、多db支持
只有一个数据库时，可用性难以保证，当主库挂了会造成申请号段不可用。另外扩展性差，性能有上限，因为写入是单点，数据库主库的写性能决定ID的生成性能上限，并且难以扩展。
为了解决此问题，Tinyid可以增加主库，避免写入单点。为了保证各主库生成的ID不重复，需要为每个主库设置不同的auto_increment初始值，以及相同的增长步长。
例如，有三个主库DB-0，DB-1，DB-2，将auto_increment初始值分别设置为0,1,2，步长都为3，则库DB-0生成0,3,6,9…，库DB-1生成1,4,7,10，库DB-2生成2,5,8,11…；
但数据库需要增加两个字段delta和remainder，分别表示增长步长和auto_increment初始值。
id |
biz_type |
max_id |
step |
delta |
remainder |
vresion |
1 |
100 |
2000 |
1000 |
2 |
0 |
0 |
但是这里有个问题，比如从申请到号段(1000,2000]后，如果delta=3, remainder=0，则这个号段从哪个id开始分配，肯定不是1001，所以这里就需要计算。设置好初始id之后，就以delta的方式递增分配。因为会先递增，所以会浪费一个id，所以做了一次减delta的操作，实际会从999开始增，第一个id还是1002。
public Result nextId() {
init();
// 先自增
long id = currentId.addAndGet(delta);
if (id > maxId) {
return new Result(ResultCode.OVER, id);
}
if (id >= loadingId) {
return new Result(ResultCode.LOADING, id);
}
return new Result(ResultCode.NORMAL, id);
}public void init() {
if (isInit) {
return;
}
// double check
synchronized (this) {
if (isInit) {
return;
}
long id = currentId.get();
if (id % delta == remainder) {
isInit = true;
return;
}
for (int i = 0; i <= delta; i++) {
id = currentId.incrementAndGet();
if (id % delta == remainder) {
// 避免浪费 减掉系统自己占用的一个id
currentId.addAndGet(0 - delta);
isInit = true;
return;
}
}
}
}在决定数据源时，使用一下方法
@Override
protected Object determineCurrentLookupKey() {
// 只有一个数据源时
if(dataSourceKeys.size() == 1) {
return dataSourceKeys.get(0);
}
// 多个数据源时，随机选择一个
Random r = new Random();
return dataSourceKeys.get(r.nextInt(dataSourceKeys.size()));
}从上面可以看出，如果有多个数据源，则随机选择一个，所有生成的id不是严格单调递增的，而是趋势递增，能满足大部分业务场景。
优化手段四、分布式部署
但是Tinyid 作为一个独立服务部署，引入这些组件将增加维护成本，所以呢，Tinyid 提供了SDK，在SDK中做了客户端负载均衡（随机算法)。
private String chooseService(String bizType) {
List<String> serverList = TinyIdClientConfig.getInstance().getServerList();
String url = "";
if (serverList != null && serverList.size() == 1) {
url = serverList.get(0);
} else if (serverList != null && serverList.size() > 1) {
// 多实例部署时，随机选择一个服务
Random r = new Random();
url = serverList.get(r.nextInt(serverList.size()));
}
url += bizType;
return url;
}Tinyid系统架构图
Tinid-client客户端模式
引用tinyid-server包
<dependency>
<groupId>com.xiaoju.uemc.tinyid</groupId>
<artifactId>tinyid-client</artifactId>
<version>${tinyid.version}</version>
</dependency>启动 tinyid-server项目打包后得到 tinyid-server-0.1.0-SNAPSHOT.jar ，设置版本 ${tinyid.version}为0.1.0-SNAPSHOT。
在我们的项目 application.properties 中配置 tinyid-server服务的请求地址 和 用户身份token。
tinyid.server=127.0.0.1:9999
tinyid.token=0f673adf80504e2eaa552f5d791b644c在Java代码调用Tinyid也很简单，只需要一行代码。
// 根据业务类型 获取单个ID
Long id = TinyId.nextId("test");
// 根据业务类型 批量获取10个ID
List<Long> ids = TinyId.nextId("test", 10);Tinyid整个项目的源码实现也是比较简单，像与数据库交互更直接用jdbcTemplate实现。
@Override
public TinyIdInfo queryByBizType(String bizType) {
String sql = "select id, biz_type, begin_id, max_id," +
" step, delta, remainder, create_time, update_time, version" +
" from tiny_id_info where biz_type = ?";
List<TinyIdInfo> list = jdbcTemplate.query(sql, new Object[]{bizType}, new TinyIdInfoRowMapper());
if(list == null || list.isEmpty()) {
return null;
}
return list.get(0);
}优点：方便集成，有成熟的方案和解决实现。
缺点：1.依赖DB的稳定性，需要采用集群主从备份的方式提高DB的可用性。
2.所有生成的id不是严格单调递增的，而是趋势递增。