一篇讓你學會雪花算法
前言
大家好，我是盼盼!
以前用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 %d\n", randNum);
- }
- return 0;
- }
運行結果：
- mapan@mapan-virtual-machine:~/c++$ ./a.out
- randNum is 94961710
- randNum is -523780773
- randNum is 1542169420
- randNum 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;
- /*
- snowflake
- ID 生成策略
- 毫秒級時間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>
- struct globle
- {
- 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;
- #define sequenceMask (-1L ^ (-1L << 12L)) //L表示long型 4095
- void 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_t uniqueId=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;
- }
運行結果：
- mapan@mapan-virtual-machine:~/c++$ ./a.out
- pthread_id:4970, id [6595660141600063488]
- pthread_id:4970, id [6595660141600063489]
- pthread_id:4970, id [6595660141600063490]
- pthread_id:4970, id [6595660141600063491]
- pthread_id:4970, id [6595660141600063492]
結尾
雪花算法很多大廠都在使用，隨機性比熵池要好。雪花算法的思想在平時工作中也有用到，將多個數據拼到一個值里面是常用套路，要掌握。
