您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

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

时间:2021-08-26 17:10:36  来源:公众号  作者:盼盼编程

原文出自:公众号 盼盼编程

原文链接:
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 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]

结尾

雪花算法很多大厂都在使用,随机性比熵池要好。雪花算法的思想在平时工作中也有用到,将多个数据拼到一个值里面是常用套路,要掌握。



Tags:雪花算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 雪花算法  点击:(24)  评论:(0)  加入收藏
原文出自:公众号 盼盼编程原文链接: https://mp.weixin.qq.com/s/rz7l1yfZvPtXv74dOYyKEA前言以前用rand和srand生成过伪随机数,伪随机数的序列是固定的,今天学习生成真正的随机...【详细内容】
2021-08-26  Tags: 雪花算法  点击:(71)  评论:(0)  加入收藏
本文分享下Spring boot项目下使用JPA操作数据库时关于ID生成器的相关实现代码。在JPA中一个数据表必须要有主键,主键类型一般是推荐使用Long类型,那么在分布式微服务下需要保...【详细内容】
2021-08-17  Tags: 雪花算法  点击:(293)  评论:(0)  加入收藏
导读:唯一ID可以标识数据的唯一性,在分布式系统中生成唯一ID的方案有很多,常见的方式大概有以下三种 依赖数据库,使用如MySQL自增列或Oracle序列等。 UUID随机数 snowflake雪花...【详细内容】
2019-09-05  Tags: 雪花算法  点击:(219)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条