자바 눈꽃 알고리즘 실현 원리
이 64 개의 bit 중 1 개의 bit 는 사용 하지 않 고 그 중의 41 bit 를 밀리초 로 하고 10 bit 를 작업 기계 id 로 하고 12 bit 를 시리 얼 번호 로 한다.
예 를 들 어 다음 64 bit 의 long 형 숫자 를 들 어 보 겠 습 니 다.
4.567917.첫 번 째 부분 은 bit:0 입 니 다.이것 은 무의미 합 니 다4.567917.두 번 째 부분 은 41 bit 이다.시간 스탬프 를 나타 낸다세 번 째 부분 은 5 bit:기계실 id,10001 을 나타 낸다4.567917.네 번 째 부분 은 5 bit 이다.기계 id,1 1001 을 나타 낸다4.567917.다섯 번 째 부분 은 12 비트 입 니 다.표 시 된 번호 입 니 다.바로 특정한 기관실 의 한 기계 에서 이 밀리초 안에 동시에 생 성 된 id 의 번호 입 니 다.0000 00000000① 1 bit:안 쓰 는데 왜?
이 진 에서 첫 번 째 bit 가 1 이 라면 모두 마이너스 이지 만 우리 가 생 성 한 id 는 모두 양수 이기 때문에 첫 번 째 bit 통일 은 모두 0 이다.
② 41 bit:시간 스탬프 를 나타 내 고 단 위 는 밀리초 입 니 다.
41 bit 가 표시 할 수 있 는 숫자 는 무려 2^41-1 에 달 합 니 다.즉,2^41-1 밀리초 값 을 표시 할 수 있 습 니 다.성인 으로 환산 하면 69 년 의 시간 을 표시 합 니 다.
③ 10 bit:작업 기계 id 를 기록 하 는 것 은 이 서 비 스 를 최대 2^10 대의 기계,즉 1024 대의 기계 에 배치 할 수 있 음 을 나타 낸다.
하지만 10 bit 에 서 는 5 개의 bit 가 기관실 id 를 대표 하고 5 개의 bit 는 기계 id 를 대표 합 니 다.최대 2^5 개의 기관실(32 개의 기관실)을 대표 하고,각 기관실 에 서 는 2^5 개의 기계(32 대의 기계)를 대표 할 수도 있 고,자사 의 실제 상황 에 따라 확정 할 수도 있다 는 뜻 이다.
④ 12 bit:이것 은 같은 밀리초 안에 발생 하 는 서로 다른 id 를 기록 하 는 데 쓰 인 다.
12 bit 가 대표 할 수 있 는 최대 정 수 는 2^12-1=4096 이다.즉,이 12 bit 가 대표 하 는 숫자 로 같은 밀리초 안의 4096 개의 다른 id 를 구분 할 수 있다 는 것 이다.
쉽게 말 하면 특정한 서비스 가설 이 전체 국면 에서 유일한 id 를 생 성 하려 면 SnowFlake 알고리즘 을 배치 한 시스템 에 요청 을 보 낼 수 있 습 니 다.이 SnowFlake 알고리즘 시스템 에서 유일한 id 를 생 성 할 수 있 습 니 다.
이 SnowFlake 알고리즘 시스템 은 먼저 자신 이 있 는 기관실 과 기 계 를 알 고 있 을 것 이다.예 를 들 어 기관실 id=17,기계 id=12.
이 어 SnowFlake 알고리즘 시스템 이 이 요청 을 받 은 후 먼저 바 이 너 리 연산 방식 으로 64 bit 의 long 형 id 를 생 성 합 니 다.64 bit 중 첫 번 째 bit 는 무의미 합 니 다.
이어서 41 개의 bit 를 사용 하면 현재 시간 스탬프(단위 에서 밀리초)를 사용 할 수 있 습 니 다.그리고 5 개의 bit 에 이 기계실 id 를 설정 하고 5 개의 bit 에 기계 id 를 설정 할 수 있 습 니 다.
마지막 으로 다시 한 번 판단 해 보 겠 습 니 다.현재 이 기계 의 이 밀리초 동안 이것 은 몇 번 째 요청 입 니 다.이번 id 생 성 요청 에 번 호 를 추가 하여 마지막 12 bit 로 합 니 다.
마지막 으로 64 비트 의 id 가 나 왔 습 니 다.다음 과 같 습 니 다.
이 알고리즘 은 한 기관실 의 한 기계 에서 같은 밀리초 안에 유일한 id 를 생 성 했다 고 보증 할 수 있다.한 밀리초 안에 여러 개의 id 가 생 성 될 수 있 지만 마지막 12 개의 bit 번호 로 구분 된다.
다음은 이 SnowFlake 알고리즘 의 코드 실현 을 간단하게 살 펴 보 겠 습 니 다.이것 이 바로 예제 입 니 다.여러분 이 이 뜻 을 이해 한 후에 이 알고리즘 을 스스로 개조 해 보 세 요.
한 마디 로 하면 64 bit 의 숫자 중 각 bit 비트 로 서로 다른 표지 위 치 를 설정 하고 모든 id 를 구분 하 는 것 이다.
SnowFlake 알고리즘 구현 코드 는 다음 과 같 습 니 다.
public class IdWorker {
// bit 1， ， id ， bit 0。
// ID 2 5 32 1 31
private long workerId;
// ID 2 5 32 1 31
private long datacenterId;
// id 12 4096 -1 = 4095
private long sequence;
// 2^41 - 1 69
private long twepoch = 1585644268888L;
//5 id
private long workerIdBits = 5L;
//5 id
private long datacenterIdBits = 5L;
// id 2 12
private long sequenceBits = 12L;
// ， 5 bit 31 ， id 32
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
// ， 5 bit 31 ， id 32
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask = -1L ^ (-1L << sequenceBits);
// ， 1
private long lastTimestamp = -1L;
public long getWorkerId(){
return workerId;
}
public long getDatacenterId() {
return datacenterId;
}
public long getTimestamp() {
return System.currentTimeMillis();
}
public IdWorker(long workerId, long datacenterId, long sequence) {
// id id 31 0
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(
String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(
String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
}
this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
}
// ， nextId() ， snowflake id
public synchronized long nextId() {
// ，
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
System.err.printf(
"clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
// ， id
// seqence 1， 4096
if (lastTimestamp == timestamp) {
// 4096 ， ，
// 4096 ， sequence 4096
sequence = (sequence + 1) & sequenceMask;
// ， id 4095， ， ， ID
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
// id ，
lastTimestamp = timestamp;
// ， 64bit id
// ， 41 bit ； id 5 bit ； id 5 bit ； 12 bit
// 64 bit ， 10 long
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) | sequence;
}
/**
* ， id 4095， ， ， ID
* @param lastTimestamp
* @return
*/
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
//
private long timeGen(){
return System.currentTimeMillis();
}
/**
* main
* @param args
*/
public static void main(String[] args) {
System.out.println(1&4596);
System.out.println(2&4596);
System.out.println(6&4596);
System.out.println(6&4596);
System.out.println(6&4596);
System.out.println(6&4596);
// IdWorker worker = new IdWorker(1,1,1);
// for (int i = 0; i < 22; i++) {
// System.out.println(worker.nextId());
// }
}
}(1)고성능 고가 용:생 성 시 데이터베이스 에 의존 하지 않 고 완전히 메모리 에서 생 성 된다.
(2)용량 이 크다:1 초 에 수백 만 의 자체 증가 ID 를 생 성 할 수 있다.
(3)ID 자체 증가:데이터베이스 에 저장 하면 색인 효율 이 높다.
SnowFlake 알고리즘 의 단점:
시스템 시간 과 의 일치 성에 의존 합 니 다.시스템 시간 이 바 뀌 거나 바 뀌 면 id 충돌 이나 중복 이 발생 할 수 있 습 니 다.
실제 적 으로 우리 의 기계실 은 그렇게 많 지 않다.우 리 는 알고리즘 을 개선 하고 10bit 의 기계 id 를 최적화 시 켜 업무 표 나 우리 시스템 과 관련 된 업무 로 만 들 수 있다.
자바 가 눈꽃 알고리즘 을 실현 하 는 원리 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 눈꽃 알고리즘 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
