雪花算法

前言

大家好，我是盼盼！

以前用 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]

結尾

雪花算法很多大廠都在使用，隨機性比熵池要好。雪花算法的思想在平時工作中也有用到，將多個數據拼到一個值裏面是常用套路，要掌握。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/rz7l1yfZvPtXv74dOYyKEA

猜你喜歡