一篇讓你學(xué)會雪花算法

作者：盼盼編程 2021-08-26 13:22:46

以前用rand和srand生成過偽隨機(jī)數(shù)，偽隨機(jī)數(shù)的序列是固定的，今天學(xué)習(xí)生成真正的隨機(jī)數(shù)的生成。

[[419666]]

前言

大家好，我是盼盼!

以前用rand和srand生成過偽隨機(jī)數(shù)，偽隨機(jī)數(shù)的序列是固定的，今天學(xué)習(xí)生成真正的隨機(jī)數(shù)的生成。

熵池

利用/dev/urandom可以生成隨機(jī)數(shù)的值，/dev/urandomLinux下的熵池，所謂熵池就是當(dāng)前系統(tǒng)下的環(huán)境噪音，描述了一個系統(tǒng)的混亂程度，環(huán)境噪音由這幾個方面組成，如內(nèi)存的使用，文件的使用量，不同類型的進(jìn)程數(shù)量等等。

#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; 
}

運行結(jié)果：

mapan@mapan-virtual-machine:~/c++$ ./a.out  
randNum is 94961710 
randNum is -523780773 
randNum is 1542169420 
randNum is -1632410867

每次打印的5個隨機(jī)數(shù)都不一樣，其實它的隨機(jī)性也不太好。雪花算法生成的數(shù)的隨機(jī)性很好，通常在分布式系統(tǒng)中生成唯一ID。

雪花算法

SnowFlake算法產(chǎn)生的ID是一個64位的整型，結(jié)構(gòu)如下(每一部分用“-”符號分隔)：

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 00000000000

1位標(biāo)識部分，在java中由于long的最高位是符號位，正數(shù)是0，負(fù)數(shù)是1，一般生成的ID為正數(shù)，所以為0;

41位時間戳部分，這個是毫秒級的時間，一般實現(xiàn)上不會存儲當(dāng)前的時間戳，而是時間戳的差值(當(dāng)前時間-固定的開始時間)，這樣可以使產(chǎn)生的ID從更小值開始;41位的時間戳可以使用69年，(1L << 41) / (1000L 60 60 24 365) = 69年;

10位節(jié)點部分，Twitter實現(xiàn)中使用前5位作為數(shù)據(jù)中心標(biāo)識，后5位作為機(jī)器標(biāo)識，可以部署1024個節(jié)點;

12位序列號部分，支持同一毫秒內(nèi)同一個節(jié)點可以生成4096個ID;

/*  
    snowflake  
 
    ID 生成策略  
    毫秒級時間41位+機(jī)器ID 10位+毫秒內(nèi)序列12位。 
    0 41 51 64 +-----------+------+------+ |time |pc |inc | +-----------+------+------+  
    前41bits是以微秒為單位的timestamp。 
    接著10bits是事先配置好的機(jī)器ID。 
    最后12bits是累加計數(shù)器。 
    macheine id(10bits)標(biāo)明最多只能有1024臺機(jī)器同時產(chǎn)生ID，sequence number(12bits)也標(biāo)明1臺機(jī)器1ms中最多產(chǎn)生4096個ID， *  
      注意點，因為使用到位移運算，所以需要64位操作系統(tǒng)，不然生成的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();//獲取當(dāng)前毫秒數(shù) 
 
  uniqueId = nowtime << 22;   //填補時間戳部分 
 
  //0x3ff 1023,二進(jìn)制對應(yīng)11 1111 1111  
  //100的二進(jìn)制0000 0000 0000 0000 0000 0000 0110 0100 
  //先執(zhí)行移位 
  uniqueId |= (g_info.workid & 0x3ff) << 12;   //填補節(jié)點部分 
 
  if (nowtime < g_info.last_stamp) 
  { 
    perror("error"); 
    exit(-1); 
  } 
 
  if (nowtime == g_info.last_stamp) 
  { 
    //4095的二進(jìn)制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);//獲取大于當(dāng)前時間的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;   
}

運行結(jié)果：

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]