如何在高并发分布式系统中生成全局唯一Id – 滴答的雨

 

又一个多月没冒泡了,其实最近学了些东西,但是没有安排时间整理成博文,后续再奉上。最近还写了一个发邮件的组件以及性能测试会在这个月整理出来,还弄了个MSSQL参数化语法生成器,会在9月整理出来,有兴趣的园友可以关注下我的博客。

 

分享原由,最近公司用到,并且在找最合适的方案,希望大家多参与讨论和提出新方案。我和我的小伙伴们也讨论了这个主题,我受益匪浅啊……

 

博文示例:

1.         GUID生成Int64值后是否还具有唯一性测试

2.         Random生成高唯一性随机码

 

今天分享的主题是:如何在高并发分布式系统中生成全局唯一Id

但这篇博文实际上是“半分享半讨论”的博文:

1)         半分享是我将说下我所了解到的关于今天主题所涉及的几种方案。

2)         半讨论是我希望大家对各个方案都说说自己的见解,更加希望大家能提出更好的方案。(我还另外提问在此:http://q.cnblogs.com/q/53552/上面已有几位园友回复(感谢dudu站长的参与),若你们有见解和新方案就在本博文留言吧,方便我整理更新到博文中,谢谢!)

 

我了解的方案如下……………………………………………………………………

1、  使用数据库自增Id

优势:编码简单,无需考虑记录唯一标识的问题。

缺陷:

1)         在大表做水平分表时,就不能使用自增Id,因为Insert的记录插入到哪个分表依分表规则判定决定,若是自增Id,各个分表中Id就会重复,在做查询、删除时就会有异常。

2)         在对表进行高并发单记录插入时需要加入事物机制,否则会出现Id重复的问题。

3)         在业务上操作父、子表(即关联表)插入时,需要在插入数据库之前获取max(id)用于标识父表和子表关系,若存在并发获取max(id)的情况,max(id)会同时被别的线程获取到。

4)         等等。

结论:适合小应用,无需分表,没有高并发性能要求。

2、  单独开一个数据库,获取全局唯一的自增序列号或各表的MaxId

1)         使用自增序列号表

专门一个数据库,生成序列号。每次操作插入时,先将数据插入到序列表并返回自增序列号用于做为唯一Id进行业务数据插入。

注意:需要定期清理序列表的数据以保证获取序列号的效率;插入序列表记录时要开启事物。

使用此方案的问题是:每次的查询序列号是一个性能损耗;如果这个序列号列暴了,那就杯具了,你不知道哪个表使用了哪个序列,所以就必须换另一种唯一Id方式如GUID

2)         使用MaxId表存储各表的MaxId

专门一个数据库,记录各个表的MaxId值,建一个存储过程来取Id,逻辑大致为:开启事物,对于在表中不存在记录,直接返回一个默认值为1的键值,同时插入该条记录到table_key表中。而对于已存在的记录,key值直接在原来的key基础上加1更新到MaxId表中并返回key

使用此方案的问题是:每次的查询MaxId是一个性能损耗;不过不会像自增序列表那么容易列暴掉,因为是摆表进行划分的。

详细可参考:《使用MaxId表存储各表的MaxId值,以获取全局唯一Id

                   我截取此文中的sql语法如下:

第一步:创建表
create table table_key
(
table_name varchar(50) not null primary key,
key_value int not null
)

第二步:创建存储过程来取自增ID
create procedure up_get_table_key
(
@table_name varchar(50),
@key_value int output
)
as
begin
begin tran
declare @key int

–initialize the key with 1
set @key=1
–whether the specified table is exist
if not exists(select table_name from table_key where [email protected]_name)
begin
insert into table_key values(@table_name,@key) –default key vlaue:1
end
— step increase
else
begin
select @key=key_value from table_key with (nolock) where [email protected]_name
set @[email protected]+1
–update the key value by table name
update table_key set [email protected] where [email protected]_name
end
–set ouput value
set @[email protected]

–commit tran
commit tran
if @@error>0
rollback tran
end

结论:适用中型应用,此方案解决了分表,关联表插入记录的问题。但是无法满足高并发性能要求。同时也存在单点问题,如果这个数据库cash掉的话……

我们目前正头痛这个问题,因为我们的高并发常常出现数据库访问超时,瓶颈就在这个MaxId表。我们也有考虑使用分布式缓存(egmemcached)缓存第一次访问MaxId表数据,以提高再次访问速度,并定时用缓存数据更新一次MaxId表,但担心的问题是:倘若缓存失效或暴掉了,那缓存的MaxId没有更新到数据库导致数据丢失,必须停掉站点来执行Select max(id)各个表来同步MaxId表。

         网上找到的特别妙的改进方案,帅呆了……

整体思想:建立两台以上的数据库ID生成服务器,每个服务器都有一张记录各表当前IDMaxId表,但是MaxId表中Id的增长步长是服务器的数量,起始值依次错开,这样相当于把ID的生成散列到每个服务器节点上。例如:如果我们设置两台数据库ID生成服务器,那么就让一台的MaxId表的Id起始值为1(或当前最大Id+1),每次增长步长为2,另一台的MaxId表的ID起始值为2(或当前最大Id+2),每次步长也为2。这样就将产生ID的压力均匀分散到两台服务器上,同时配合应用程序控制,当一个服务器失效后,系统能自动切换到另一个服务器上获取ID,从而解决的单点问题保证了系统的容错。(Flickr思想)

结论:适合大型应用,生成Id较短,友好性比较好。(强烈推荐)

3、  Sequence特性

这个特性在SQL Server 2012Oracle中可用。这个特性是数据库级别的,允许在多个表之间共享序列号。它可以解决分表在同一个数据库的情况,但倘若分表放在不同数据库,那将共享不到此序列号。(egSequence使用场景:你需要在多个表之间公用一个流水号。以往的做法是额外建立一个表,然后存储流水号)

相关Sequence特性资料:

SQL Server2012中的SequenceNumber尝试

SQL Server 2012 开发新功能——序列对象(Sequence

identitysequence的区别

Difference between Identity and Sequence in SQL Server 2012

结论:适用中型应用,此方案不能完全解决分表问题,并且存在“单独开一个数据库,获取全局唯一的自增序列号或各表的MaxId”方案中不能解决的问题

4、  通过数据库集群编号+集群内的自增类型两个字段共同组成唯一主键

优点:实现简单,维护也比较简单。

缺点:关联表操作相对比较复杂,需要两个字段。并且业务逻辑必须是一开始就设计为处理复合主键的逻辑,倘若是到了后期,由单主键转为复合主键那改动成本就太大了。

结论:适合大型应用,但需要业务逻辑配合处理复合主键。

5、  通过设置每个集群中自增 ID 起始点(auto_increment_offset),将各个集群的ID进行绝对的分段来实现全局唯一。当遇到某个集群数据增长过快后,通过命令调整下一个 ID 起始位置跳过可能存在的冲突。

优点:实现简单,且比较容易根据 ID 大小直接判断出数据处在哪个集群,对应用透明。缺点:维护相对较复杂,需要高度关注各个集群 ID 增长状况。

结论:适合大型应用,但需要高度关注各个集群 ID 增长状况。

6、  GUID

优点:GUID是最简单的方案,全局唯一的Id,数据间同步、迁移都能简单实现。

缺点:存储占了32位,且无可读性,返回GUID给客户显得很不专业;还占用了珍贵的聚集索引,一般我们不会根据GUID去查单据,并且插入时因为GUID是无需的,在聚集索引的排序规则下可能移动大量的记录。

结论:适合大型应用,生成的Id不够友好。(推荐)

7、  GUID TO Int64

对于GUID的可读性,有园友给出如下方案:(感谢:@黑色的羽翼

/// <summary>
/// 根据GUID获取19位的唯一数字序列
/// </summary>
public static long GuidToLongID()
{
byte[] buffer = Guid.NewGuid().ToByteArray();
return BitConverter.ToInt64(buffer, 0);
}

即将GUID转为了19位数字,数字反馈给客户可以一定程度上缓解友好性问题。EG:

GUID: cfdab168-211d-41e6-8634-ef5ba6502a22    (不友好)

Int64: 5717212979449746068                                      (友好性还行)

不过我的小伙伴说ToInt64后就不唯一了。因此我专门写了个并发测试程序,后文将给出测试结果截图及代码简单说明。

结论:适合大型应用,并且经我测试程序跑了一个晚上没有出现重复Id问题。(推荐)

8、  自己写编码规则

优点:全局唯一Id,符合业务后续长远的发展(可能具体业务需要自己的编码规则等等)。

缺陷:根据具体编码规则实现而不同。

我这边写两个编码规则方案:(可能不唯一,只是个人方案,也请大家提出自己的编码方案)

1)         15位年月日时分秒毫秒+3位服务器编码+3位表编码+4位随机码  (这样就完全单机完成生成全局唯一编码)25

缺陷:因为附带随机码,所以编码缺少一定的顺序感。(生成高唯一性随机码的方案稍后给给出程序)

2)         15位年月日时分秒毫秒+3位服务器编码+3位表编码+4位流水码  (这样流水码就需要结合数据库和缓存)25

缺陷:因为使用到流水码,流水码的生成必然会遇到和MaxId、序列表、Sequence方案中类似的问题

结论:适合大型应用,从业务上来说,有一个规则的编码能体现产品的专业成度。(强烈推荐)

 

 

GUID生成Int64值后是否还具有唯一性测试

测试环境

clip_image002

主要测试思路:

1.         根据内核数使用多线程并发生成Guid后再转为Int64位值,放入集合AB、…N,多少个线程就有多少个集合。

2.         再使用Dictionary字典高效查key的特性,将步骤1中生成的多个集合全部加到Dictionary中,看是否有重复值。

示例注解:测了 Dictionary<long,bool> 最大容量就在5999470左右,所以每次并发生成的唯一值总数控制在此范围内,让测试达到最有效话。

主要代码:

for (int i = 0; i <= Environment.ProcessorCount – 1; i++)
{
ThreadPool.QueueUserWorkItem(
(list) =>
{
List<long> tempList = list as List<long>;
for (int j = 1; j < listLength; j++)
{
byte[] buffer = Guid.NewGuid().ToByteArray();
tempList.Add(BitConverter.ToInt64(buffer, 0));
}
barrier.SignalAndWait();
}, totalList[i]);
}

测试数据截图:                                                                           

clip_image004

 

数据一(循环1000次)

image

数据二(循环5000次)跑了一个晚上……

image

结论:GUID转为Int64值后,也具有高唯一性,可以使用与项目中。

 

Random生成高唯一性随机码

我使用了五种Random生成方案,要Random生成唯一主要因素就是种子参数要唯一。(这是比较久以前写的测试案例了,一直找不到合适的博文放,今天终于找到合适的地方了)

不过该测试是在单线程下的,多线程应使用不同的Random实例,所以对结果影响不会太大。

1.         使用Environment.TickCount做为Random参数(即Random的默认参数),重复性最大。

2.         使用DateTime.Now.Ticks做为Random参数,存在重复。

3.         使用unchecked((int)DateTime.Now.Ticks)做为Random参数,存在重复。

4.         使用Guid.NewGuid().GetHashCode()做为random参数,测试不存在重复(或存在性极小)。

5.         使用RNGCryptoServiceProvider做为random参数,测试不存在重复(或存在性极小)。

即:

        static int GetRandomSeed()

        {

            byte[] bytes = new byte[4];

            System.Security.Cryptography.RNGCryptoServiceProvider rng

= new System.Security.Cryptography.RNGCryptoServiceProvider();

            rng.GetBytes(bytes);

            return BitConverter.ToInt32(bytes, 0);

        }

测试结果:

clip_image007

结论:随机码使用RNGCryptoServiceProviderGuid.NewGuid().GetHashCode()生成的唯一性较高。

 

 

本次博文到此结束,希望大家对本次主题“如何在高并发分布式系统中生成全局唯一Id”多提出自己宝贵的意见。另外看着感觉舒服,还请多帮推荐…推荐……

 

 

===================================================

 

如果你想认识.net朋友的可以加入群:185718116(广深莞·NET技术) 173844862.Net高级部落)

 

===================================================

 

 

本文链接:http://www.cnblogs.com/heyuquan/p/global-guid-identity-maxId.html,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量