江苏龙网

  1. 主页 > 生活百科 > >

聊聊大厂都在用的雪花算法

雪花算法

原文出自：公众号 盼盼编程
原文链接：
https://mp.weixin.qq.com/s/rz7l1yfZvPtXv74dOYyKEA
前言以前用rand和srand生成过伪随机数，伪随机数的序列是固定的，今天学习生成真正的随机数的生成 。
熵池利用/dev/urandom可以生成随机数的值，/dev/urandomlinux下的熵池，所谓熵池就是当前系统下的环境噪音，描述了一个系统的混乱程度，环境噪音由这几个方面组成，如内存的使用，文件的使用量，不同类型的进程数量等等 。
利用/dev/urandom可以生成随机数的值，/dev/urandomLinux下的熵池，所谓熵池就是当前系统下的环境噪音，描述了一个系统的混乱程度，环境噪音由这几个方面组成，如内存的使用，文件的使用量，不同类型的进程数量等等 。
#include <stdio.h>#include <fcntl.h>int main(){int randNum = 0;int fd = 0;for(int i=0;i<5;i++){fd = open("/dev/urandom", O_RDONLY);read(fd, (char *)&randNum, sizeof(int));close(fd);printf("randNum is %dn", randNum);}return 0;}运行结果：
mapan@mapan-virtual-machine:~/c++$ ./a.out randNum is 94961710randNum is -523780773randNum is 1542169420randNum is -1632410867每次打印的5个随机数都不一样，其实它的随机性也不太好 。雪花算法生成的数的随机性很好，通常在分布式系统中生成唯一ID 。
雪花算法SnowFlake算法产生的ID是一个64位的整型，结构如下（每一部分用“-”符号分隔）：
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 00000000000
1位标识部分，在JAVA中由于long的最高位是符号位，正数是0，负数是1，一般生成的ID为正数，所以为0；
41位时间戳部分，这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间-固定的开始时间），这样可以使产生的ID从更小值开始；41位的时间戳可以使用69年，(1L << 41) / (1000L 60 60 24 365) = 69年；
10位节点部分，Twitter实现中使用前5位作为数据中心标识，后5位作为机器标识，可以部署1024个节点；
12位序列号部分，支持同一毫秒内同一个节点可以生成4096个ID；
/*snowflakeID 生成策略毫秒级时间41位+机器ID 10位+毫秒内序列12位 。0 41 51 64 +-----------+------+------+ |time |pc |inc | +-----------+------+------+前41bits是以微秒为单位的timestamp 。接着10bits是事先配置好的机器ID 。最后12bits是累加计数器 。macheine id(10bits)标明最多只能有1024台机器同时产生ID，sequence number(12bits)也标明1台机器1ms中最多产生4096个ID，*注意点，因为使用到位移运算，所以需要64位操作系统，不然生成的ID会有可能不正确 */#include <stdio.h>#include <pthread.h>#include <unistd.h>#include <stdlib.h>#include <sched.h>#include <linux/unistd.h>#include <sys/syscall.h>#include <errno.h>#include<linux/types.h>#include<time.h>#include <stdint.h>#include <sys/time.h>structgloble{int global_int:12;uint64_t last_stamp;int workid;int seqid;};void set_workid(int workid);pid_t gettid( void );uint64_t get_curr_ms();uint64_t wait_next_ms(uint64_t lastStamp);int atomic_incr(int id);uint64_t get_unique_id();#include "snowflake.h"struct globle g_info;#definesequenceMask(-1L ^ (-1L << 12L))//L表示long型4095void set_workid(int workid){ g_info.workid = workid;}pid_t gettid( void )//获取线程ID{return syscall( __NR_gettid );}uint64_t get_curr_ms()//获取毫秒{struct timeval time_now;gettimeofday(&time_now,NULL);uint64_t ms_time =time_now.tv_sec*1000+time_now.tv_usec/1000;return ms_time;}uint64_t wait_next_ms(uint64_t lastStamp){uint64_t cur = 0;do {cur = get_curr_ms();} while (cur <= lastStamp);return cur;}int atomic_incr(int id)//累加{__sync_add_and_fetch(&id, 1);return id;}uint64_t get_unique_id(){uint64_tuniqueId=0;uint64_t nowtime = get_curr_ms();//获取当前毫秒数uniqueId = nowtime << 22;//填补时间戳部分//0x3ff 1023,二进制对应11 1111 1111//100的二进制0000 0000 0000 0000 0000 0000 0110 0100//先执行移位uniqueId |= (g_info.workid & 0x3ff) << 12;//填补节点部分if (nowtime < g_info.last_stamp){perror("error");exit(-1);}if (nowtime == g_info.last_stamp){//4095的二进制0000 1111 1111 1111[long型]g_info.seqid = atomic_incr(g_info.seqid) & sequenceMask;if (g_info.seqid == 0)//seqid=0防止冲突，修改时间{nowtime = wait_next_ms(g_info.last_stamp);//获取大于当前时间的time}}else{g_info.seqid= 0;}g_info.last_stamp = nowtime;uniqueId |= g_info.seqid;//填补序列号部分return uniqueId;}int main(){set_workid(100);int i;for(i=0;i<10;i++){uint64_t unquie = get_unique_id();printf("pthread_id:%u, id [%llu]n",gettid(),unquie);}return;}


推荐阅读


上一篇：五款css布局工具，大大减少你写代码的时间

下一篇：JavaScript 断点调试技巧