伊春网站优化,有域名后怎么做网站,好听的房地产公司名字,信阳做网站推广信阳网站建设文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题
问题出现
使用ShardingSphere框架自带的雪花算法生成分布式主… 文章目录 雪花算法结合分库分表的问题问题出现原因分析解决思路 分布式主键要考虑的问题主键生成策略雪花算法详解时间戳位问题工作进程位问题序列号位问题根据雪花算法扩展基因分片法 雪花算法结合分库分表的问题
问题出现
使用ShardingSphere框架自带的雪花算法生成分布式主键如果和分片算法结合使用不当就很有可能造成数据分布不均匀的情况
如下所示我使用分布式主键生成策略是SNOWFLAKE分表策略是常见的取模运算 rules:sharding:# 分片键生成策略key-generators:# 雪花算法alg_snowflake:type: SNOWFLAKEprops:worker:id: 1sharding-algorithms:# 定义分库策略db_alg:type: MODprops:sharding-count: 2# 分表策略sys_user_tab_alg:type: INLINEprops:algorithm-expression: sys_user$-{((uid1)%4).intdiv(2)1}进行新增操作后这里并没有均匀的分布在四个数据表中只存在两个数据表中 原因分析
造成这个问题的原因是ShardingSPhere自带的雪花算法的序列号位是一个单位时间内自增如果不是一个单位时间内那么就重置为0重新自增。
// 全类名 org.apache.shardingsphere.sharding.algorithm.keygen.SnowflakeKeyGenerateAlgorithmOverride
public synchronized Long generateKey() {long currentMilliseconds timeService.getCurrentMillis();// 处理雪花算法41bit时间戳位 时钟回拨 if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {currentMilliseconds timeService.getCurrentMillis();}// 处理12bit序列号位if (lastMilliseconds currentMilliseconds) {// 单位时间内 sequence序列号位每次都是自增if (0L (sequence (sequence 1) SEQUENCE_MASK)) {currentMilliseconds waitUntilNextTime(currentMilliseconds);}} else {// 如果不是一个单位时间内序列号位就又重置vibrateSequenceOffset();sequence sequenceOffset;}lastMilliseconds currentMilliseconds;// 时间戳位 | 工作进程位 | 序列号位return ((currentMilliseconds - EPOCH) TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}进一步编写测试类验证
取出插入数据库中的uid值进行位 运算最终就可以发现序列号位基本上都是 0 或者是1 那么这样我们就进行简单的 %2 %4 运算所以就导致了上方的数据分布不均匀问题
public void testSequence(ListLong uidList) {int mask (1 3) - 1;for (Long uid : uidList) {log.info(uid:{} 的后3位的结果为 {}, uid, uid mask);}
}uid:1027514136331812864 的后3位的结果为 0
uid:1027514137086787584 的后3位的结果为 0
uid:1027514137128730624 的后3位的结果为 0
uid:1027514137166479360 的后3位的结果为 0
uid:1027514137204228096 的后3位的结果为 0
uid:1027514137057427457 的后3位的结果为 1
uid:1027514137107759105 的后3位的结果为 1
uid:1027514137149702145 的后3位的结果为 1
uid:1027514137183256577 的后3位的结果为 1
uid:1027514137216811009 的后3位的结果为 1解决思路
修改现有的雪花算法让序列号位不要每次都重置。这种方式的确能解决当前业务功能。
Override
public synchronized Long generateKey() {long currentMilliseconds timeService.getCurrentMillis();if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {currentMilliseconds timeService.getCurrentMillis();}if (lastMilliseconds currentMilliseconds) {
// if (0L (sequence (sequence 1) SEQUENCE_MASK)) {currentMilliseconds waitUntilNextTime(currentMilliseconds);
// }} else {vibrateSequenceOffset();
// sequence sequenceOffset;// SEQUENCE_MASK (1 12L) - 1sequence sequence SEQUENCE_MASK ? 0:sequence1;}lastMilliseconds currentMilliseconds;return ((currentMilliseconds - EPOCH) TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}但是带来的问题是分布式场景下雪花算法的序列号位相当于没用了。因为雪花算法的初始目标就是分布式主键生成不冲突它是靠 时间戳位工作进程位序列号位保证的。
如果在单位时间内并且没有设置工作进程位多台服务器中的序列号位相同了那么也就导致了后续生成的id都可能出现重复的情况。 分布式主键要考虑的问题
主键除了要标识数据的唯一性之外还通常会要求主键与业务不直接相关。因为这样不管业务如何变化都不会影响主键来控制数据的生命周期但是另外一个方面我们通常又会要求主键包含一部分的业务属性这样可以加速对数据的检索。主键也需要考虑安全性让别人无法通过规律猜出主键来。
所以对于主键一方面要求他与业务不直接相关。这就要求分配主键的服务要足够稳定足够快速。不能说我辛辛苦苦把业务给弄完了然后等着分配主键的时候还要等半天甚至等不到。另一方面要求他能够包含某一些业务特性。这就要求分配主键的服务能够进行一定程度的扩展。 主键生成策略 数据库策略
业务层面不设置主键直接使用数据库的自增长。这种方式实现简单但是分库分表场景下就会造成主键冲突。当然也可以通过为各个数据库设置自增长步长来解决。但是又不能满足分库分表扩缩容的场景。 应用单独生成
数据库生成的主键不靠谱那么就应用层面自己来生成。比较常见的算法就是UUID、NANOID、SnowFlaks雪花算法
优点简单使用。比如UUID使用JDK自带的工具类即可、SnowFlaks按照它定义的规则自行组合。比较容易扩展可以随意组合生成主键。
缺点
算法不能太复杂会消耗cpu计算资源与内存空间要考虑多线程并发安全问题不能主键冲突。考虑数据库产品结合因素比如mysql的InnoDB存储引擎B树索引需要使用趋势递增的主键来避免B树的分裂。UUID这类无序字符串主键就不能满足 第三方服务统一生成
借助第三方服务来生成主键比如redis、zookeeper、MongoDB
redis通过incr指令配合lua脚本比较容易防并发
zookeeper使用它的序列号节点或者是在apache提供的Zookeeper客户端Curator中提供了DistributedAtomicIntegerDistributedAtomicLong等工具可以用来生成分布式递增的ID。
MongoDB使用MongoDB的ObjectID。 缺点
这些原生的方式大都不是为了分布式主键场景而设计的所以如果要保证高效以及稳定在使用这些工具时还是需要非常谨慎。每一次生成主键都需要调用第三方服务效率问题也需要考虑 与第三方结合的segment策略
还是从第三方获取主键只不过是一次获取一批主键缓存在本地当使用完后再去申请一批。
比如我们设计下面这种数据表 biz_tag表示具体的某一业务标识用户或订单他们都对应的一整个集群服务。max_id表示当前已经分配的最大idstep表示每次分配的步长。max_id会随着每一次分配id而增加。
这种方式的缺点是应用向第三方申请id有网络消耗这段时间内应用会出现无主键可用的情况。 与第三方结合的多segment策略
双Buffer写入向第三方服务申请两个segment放入本地缓存。避免出现应用在向第三方申请主键这段期间没有主键可用的情况 扩展点
比较依赖DB上方max_id 和step这两个字段都是保存在数据库的。我们可以保存在其他存储方式第三方应用宕机在我服务中双buffer中的id使用完之前重新提供服务这样问题都不大。所以我服务中保存的buffer个数可以多一些进而提高容错性 雪花算法详解
雪花算法使用8字节的二进制序列来生成一个主键 41bit的时间戳为主体时间戳位保证趋势递增放在最高位 10bit的工作进程位标识服务器中运行的进程而不是标识机器需要应用自行扩展 12bit序列号位是用来区分单位时间内 单机器内的自增序列。
而在具体实现时雪花算法实际上只是提供了一个思路并没有提供现成的框架。比如ShardingSphere中的雪花算法就是这样生成的。 时间戳位问题
41bit的时间戳为主体时间戳位保证趋势递增放在最高位
时间戳位存在时钟回拨的问题。
一台服务器上获取时钟只能依赖于内核的电信号维护而电信号很难保持稳定。在高并发场景下获取高精度的时间戳有时会往前跳有时会往回拨。
一旦时钟回拨就有可能产生重复的id。 各个框架的雪花算法都有对时钟回拨的问题做相应的处理基本思路就是记录上一次生成主键的时间lastMilliseconds和当前时间进行比较如果lastMilliseconds大于当前时间就表示出现了时钟回拨处理方式要么sleep()一段时间要么直接抛异常。就比如ShardingSPhere的SnowFlake雪花算法就是sleep()而cosID_SnowFlake就是抛异常
// 全类名 org.apache.shardingsphere.sharding.algorithm.keygen.SnowflakeKeyGenerateAlgorithm
SneakyThrows(InterruptedException.class)
private boolean waitTolerateTimeDifferenceIfNeed(final long currentMilliseconds) {// 上一次生成主键的时间 和 当前时间进行比较if (lastMilliseconds currentMilliseconds) {return false;}long timeDifferenceMilliseconds lastMilliseconds - currentMilliseconds;Preconditions.checkState(...);// 解决时钟回拨的方式采用sleep()Thread.sleep(timeDifferenceMilliseconds);return true;
}// 全类名 me.ahoo.cosid.snowflake.AbstractSnowflakeId
public synchronized long generate() {long currentTimestamp this.getCurrentTime();// 时钟回拨if (currentTimestamp this.lastTimestamp) {// 抛异常throw new ClockBackwardsException(this.lastTimestamp, currentTimestamp);} else {// 序列号处理 不是同一个单位时间点值2^12 就重置0if (currentTimestamp this.lastTimestamp this.sequence this.sequenceResetThreshold) {this.sequence 0L;}// 序列号位自增this.sequence this.sequence 1L this.maxSequence;if (this.sequence 0L) {currentTimestamp this.nextTime();}this.lastTimestamp currentTimestamp;long diffTimestamp currentTimestamp - this.epoch;if (diffTimestamp this.maxTimestamp) {throw new TimestampOverflowException(this.epoch, diffTimestamp, this.maxTimestamp);} else {// 时间戳 | 进程号 | 序列位return diffTimestamp (int)this.timestampLeft | this.machineId (int)this.machineLeft | this.sequence;}}
}上方只能处理单台服务器上的时钟回拨如果是多台服务器一个集群就无法保证时间戳的统一了。
可以为每个应用配置一个工作进程位来防止不同服务器之间的主键冲突。但是万一应用没有配置嘞大部分应用不会为了一个雪花算法去单独考虑如何分配工作进程位。
也可以使用ntpd这样的时间同步服务来把多个服务器的时间同步一下。但同样的不会有人仅仅为了雪花算法去这么做
第三种方案是将时间戳从本地扔到第三方服务上去比如zookeeper这样多个服务就可以根据共同的时间戳往前推进省了服务器之间同步时间的麻烦。美团的leaf就是这么做的。缺点是给雪花算法添加强绑定降低了效率因为多了一个访问第三方的步骤。
这有变为了方案取舍、实现优化的头疼环节。就像整个分布式主键一样。 工作进程位问题
10bit的工作进程位标识服务器中运行的进程而不是标识机器需要应用自行扩展它是分布式场景下保证id不重复很重要的字段。
因为一台服务器上面可以运行多个进程实例所以这个标识是工作进程的而不能简单理解为标识机器。工作进程是需要各个应用自己设定值所以这里就分为了手动指定和自动获取两种方式。
对于一些小集群就可以简单使用手动指定的方式在配置文件中为当前应用指定一个工作进程。但如果是大型集群上百个微服务肯定就不能手动指定了。 现在就有一个思路把MachineId(比如ip端口)当做一个短的并发不是很高的分布式主键来处理用其他分布式主键生成的方式生成工作进程位。我们现在需要依赖于一个工作进程位来生成分布式唯一主键然后现在又要依赖于一个分布式唯一主键生成策略来生成工作进程位完美闭环鸡生蛋 蛋生鸡问题。 首先工作进程位是不需要考虑高并发问题通常工作进程位只需要在一个应用启动时分配一个就可以了应用的运行过程中不需要什么变化。所以工程进程位每次单步推进申请一次分配一个就行
其次工程进程位有一个天然的就带有唯一性的因素比如使用ip地址如果服务器运行多个应用那么也可以使用ip端口区分。所以工作进程位天生就有很多唯一性因素不需要像雪花算法那样去设计复杂的结构。
最后工作进程位的分配需要保持稳定。工作进程要与一个应用建立绑定关系。给一个应用分配工作进程号位之后如果应用崩溃了重启服务之后所生成的雪花算法还是需要保持一个稳定的区分度。所以可以使用一个本地缓存保存这个应用的工作进程位应用重启后还需要保持那么这个缓存可以持久化到本地文件中。
其实把这几个方面想明白了Cosid当中的工作进程位分配机制也就大致成型了。 序列号位问题
序列号位就是一个连续性问题。就比如上文中的结合分库分表的问题。
如果不是一个单位时间内那么就将序列为重置为0进而导致了我们使用取模分片策略使得数据分配不均匀。 根据雪花算法扩展基因分片法
业务场景对User用户表进行分库分表最简单的处理就是根据userId作为分片键之后每次查询都根据userId这个分片键来进行查询。但用户登录这个场景嘞此时只有一个用户名你甚至都不知道这个用户名是否存在难道就只能全路由查询这肯定是不能接受的。
此时就可以使用基因法的分片算法来解决这个问题。它的基础思想是再给用户分配userId时就把用户名当中的某种序列信息插入到userId当中。从而保证userId和用户名可以按照某一种对应规则分到同一个分片上。这样就可以根据用户名确定对应的用户信息在哪一个分片上 具体在实现时可以参照雪花算法的实现。
Test
public void testGene() {// 初始值Long userId 1257458L;String userName testroy;// 基因序列位数int dataSize 3;//掩码二进制表述为全部是1. 111int mask ((1 dataSize) - 1);// 只取 datasize 个bit位long userGene userName.hashCode() mask;// 给ID添加用户名的基因片段后的新ID保持了原id的一致性long newUserId (userId dataSize) | userGene;// 对新用户id对8取模进行数据分片long actualNode newUserId % 8;System.out.println(用户信息实际保存的分片 actualNode);long userNode (userName.hashCode() mask) % 8;System.out.println(根据用户名判断用户信息可能的分片 userNode);
}用户信息实际保存的分片2
根据用户名判断用户信息可能的分片2
