snowflake ID 생 성기

배경
Snowflake 는 트 위 터 내부 의 ID 생 성 알고리즘 으로 간단 한 규칙 을 통 해 대규모 분포 식 상황 에서 유일한 ID 번 호 를 생 성 할 수 있 습 니 다.
그 구성 은 첫 번 째 bit 는 사용 되 지 않 은 기호 위치 입 니 다.두 번 째 부분 은 41 비트 의 시간 스탬프 (밀리초) 로 구성 되 어 있 으 며, 그의 수 치 는 현재 시간 이 특정한 시간 에 비해 오프셋 이다.세 번 째 부분 과 네 번 째 부분의 5 개의 bit 위 치 는 데이터 센터 와 기계 ID 를 나타 내 고 표시 할 수 있 는 최대 치 는 2 ^ 5 - 1 = 31 이다.마지막 부분 은 12 개의 bit 로 구성 되 어 있 으 며, 각 작업 노드 가 밀리초 마다 생 성 되 는 시리 얼 번호 ID 를 나타 내 며, 같은 밀리초 내 에 최대 2 ^ 12 - 1 즉 4095 개의 ID 를 생 성 할 수 있다.
주의해 야 할 것 은:

분포 식 환경 에서 5 개의 bit 비트 의 datacenter 와 worker 는 최대 31 개의 데이터 센터 를 배치 할 수 있 고 모든 데이터 센터 는 최대 31 개의 노드 를 배치 할 수 있다 고 밝 혔 다.41 비트 의 이 진 길 이 는 최대 2 ^ 41 - 1 밀리초 즉 69 년 을 나 타 낼 수 있 기 때문에 눈꽃 알고리즘 은 최대 69 년 까지 정상적으로 사용 할 수 있 습 니 다. 이 알고리즘 을 최대한 사용 하기 위해 서 는 시작 시간 을 지정 해 야 합 니 다.

위 에서 알 수 있 듯 이 눈꽃 알고리즘 이 생 성 한 ID 는 유일 하지 않다. 예 를 들 어 두 개의 서로 다른 요청 이 같은 시간 에 같은 데이터 센터 의 같은 노드 에 들 어 갈 때 이 노드 가 생 성 한 sequence 는 동시에 생 성 된 ID 가 중복 된다.

그래서 눈꽃 알고리즘 을 사용 하여 유일한 ID 를 만 들 려 면 같은 노드 가 같은 밀리초 안에 생 성 된 시리 얼 번호 가 유일 하 다 는 것 을 보증 해 야 한다.이 를 바탕 으로 링크 2: RandomSequence Resolver (무 작위 생 성) RedisSequence Resolver (redis psetex 와 incrby 생 성 기반) Laravel Sequence Resolver (laravel 생 성 기반) Swole Sequence Resolver (swoole lock 잠 금 기반) 의 서로 다른 공급 자 는 같은 밀리초 에 생 성 된 시리 얼 번호 만 다 를 수 있 습 니 다.유일한 ID 를 얻 을 수 있 습 니 다

코드
php 구현

/**

   
   
   
   

• ID

• 41 + ID 10 + 12 。

• 0 1 41 46 51 63

• +-------+-----------+---------+-----------+-----------+

• |unused |timestamp |workId |machineId |sequence |

• +-------+-----------+---------+-----------+-----------+

• 1bit

• 41bits timestamp

• 5bits ID

• 5bits ID

• 12bits

• workerId (5bits) 32 ID

• machineId (5bits) 32 ID

• sequence (12bits) 1 1ms 4096 ID
  */
  class Snowflake
  {

  const EPOCH = 1571829625238; // ,

  const SEQUENCE_BITS = 12; // 12
  const SEQUENCE_MAX = -1 ^ (-1 << self::SEQUENCE_BITS); //

  const WORKER_BITS = 5; // 5
  const WORKER_MAX = -1 ^ (-1 << self::WORKER_BITS); //

  const MACHINE_BITS = 5; // 5
  const MACHINE_MAX = -1 ^ (-1 << self::MACHINE_BITS); //

  const TIME_SHIFT = self::WORKER_BITS + self::MACHINE_BITS + self::SEQUENCE_BITS; //
  const WORKER_SHIFT = self::MACHINE_BITS + self::SEQUENCE_BITS; //
  const MACHINE_SHIFT = self::SEQUENCE_BITS; //

  protected $timestamp; // ID
  protected $workerId; // ID
  protected $machineId; // ID
  protected $sequence; //

  public function __construct($machineId = 1, \(workerId = 1) { if (\)machineId < 0 || \(machineId > self::MACHINE_MAX) { throw new \Exception("machineId can't be greater than " .self::MACHINE_MAX. " or less than 0"); } if (\)workerId < 0 || $workerId > self::WORKER_MAX) {
  throw new \Exception("workerId can't be greater than " .self::WORKER_MAX. " or less than 0");
  }

  $this->timestamp = 0;
  $this->machineId = $machineId;
  $this->workerId = $workerId;
  $this->sequence = 0;
  

  }
  /**
• ID 생 성
• @return int
  */
  public function getId()
  {
  $now = \(this->getTimestampM(); if (\)this->timestamp == $now) {
  \(this->sequence ++; if (\)this->sequence > self::SEQUENCE_MAX) {
  / / 현재 밀리초 내 에 생 성 된 번호 가 최대 범 위 를 초과 하여 다음 밀리초 에 다시 생 성 되 기 를 기다 리 고 있 습 니 다.
  / / usleep 사용 (1) 과 같 음
  while ($now <= $this->timestamp) {
  $now = $this->getTimestampM();
  }
  }
  } else {
  $this->sequence = 0;
  }
  $this - > timestamp = $now; / / ID 생 타임 스탬프 업데이트
  \(id = ((\)now - self::EPOCH) << self::TIME_SHIFT) | (\(this->workerId << self::WORKER_SHIFT) | (\)this->machineId << self::MACHINE_SHIFT) | $this->sequence;
  return $id;
  }
/**
• id 생 성 매개 변수 되 돌려 주기
• @param $id
• @return array
  */
  public function restoreId($id)
  {
  \(binary = decbin(\)id);
  return [
  'timestamp' => bindec(substr(\(binary, 0, -self::TIME_SHIFT)) + self::EPOCH, 'workerId' => bindec(substr(\)binary, -self::TIME_SHIFT, self::WORKER_BITS)),
  'machineId' => bindec(substr(\(binary, -self::WORKER_SHIFT, self::MACHINE_BITS)), 'sequence' => bindec(substr(\)binary, -self::SEQUENCE_BITS)),
  ];
  }
/**
• 현재 밀리초 타임 스탬프 가 져 오기
• @return string
  */
  public function getTimestampM()
  {
  $time = explode(' ', microtime());
  \(time2= substr(\)time[0], 2, 3);
  return \(time[1].\)time2;
  }
  }
  
id 의 혼동
• snowflake 방식 을 사용 한 이상 원래 정 리 된 진 변환 방식 을 사용 하여 해당 하 는 문자열 표시 방식
으로 전환 할 수 있 습 니 다.
• 또는 hashids 기 존 라 이브 러 리, hashids
를 사용 합 니 다.
지식 을 보충 하 다
양수 의 이 진 표시 방식: 패 치 와 원 코드 가 같은 음수 의 이 진 표시 방식: 원 코드 의 패 치 형식 으로 표시 합 니 다.
양수 의 패 치 는 바 이 너 리 로 원 코드 와 같다 는 것 을 나타 낸다.음수 의 패 치 는 원 코드 를 기호 위 치 를 제외 한 모든 위 치 를 반 (0 변 1, 1 변 0, 기호 위 는 1 변 하지 않 음) 한 후에 1 을 추가 합 니 다.
- 1 ^ (- 1 < 4) 는 - 1 의 바 이 너 리 가 - 1 을 나타 내 는 패 치 (그 값 은 자릿수 상 모두 1, 11111111) 는 사실 2 의 4 차방 - 1 과 같다.
참조 링크
hashids 참조 링크 1 참조 링크 2