my sql 을 이용 한 눈꽃 알고리즘 사례
1.문제 발생 배경
현재 점점 더 많은 회사 들 이 분포 식,마이크로 서 비 스 를 사용 하고 있다.그러면 대응 하 는 것 은 서로 다른 서비스 에 대해 데이터 베 이 스 를 분리 한 다음 에 데이터 양 이 올 라 올 때 도 표를 나 누 는 것 이다.그러면 이에 따 른 것 은 표 이후 id 의 문제 이다.
예 를 들 어 이전 단일 프로젝트 의 한 표 에 있 는 데이터 메 인 키 id 는 모두 자체 적 으로 증가 하 였 습 니 다.my sql 은 autoincrement 를 이용 하여 자체 증 가 를 실현 하 였 으 며,Oacle 은 서열 을 이용 하여 이 루어 졌 습 니 다.그러나 단일 표 데이터 양 이 올 라 온 후에 수평 분 표를 진행 해 야 합 니 다.아 리 자바 개발 건 의 는 표 가 500 w 이상 일 때 표 로 나 누 어야 합 니 다.그러나 구체 적 으로 업 무 를 봐 야 합 니 다.만약 에 인용 번 호 를 찾 으 면...표 천만 원 짜 리 데이터 도 가능 합 니 다.수평 분 표 는 한 장의 데 이 터 를 여러 장의 표 로 나 누 는 것 이다.그러면 문 제 는 예전 의 자체 증가 에 따라 메 인 키 id 를 만 들 면 id 가 중복 되 고 이 럴 때 어떤 방안 으로 분포 식 id 문 제 를 해결 하 는 지 고려 해 야 한다.
2.해결 방안
2.1 데이터베이스 시트
한 라 이브 러 리 에서 시 계 를 전문 적 으로 유지 할 수 있 습 니 다.그 다음 에 어떤 시계 가 id 를 증가 해 야 할 때마다 이 표 의 기록 을 찾 은 다음 에 for update 로 시 계 를 잠 근 다음 에 얻 은 값 을 하나 더 한 다음 에 돌아 와 서 다시 시 계 를 기록 할 수 있 습 니 다.그러나 이 방법 은 비교적 적은 항목 에 적합 하기 때문에 매번 시 계 를 잠 가 야 합 니 다.
2.2、redis
redis 는 단일 스 레 드 이기 때문에 redis 에서 키 쌍 을 유지 할 수 있 습 니 다.그리고 어떤 시 계 는 redis 에서 값 을 추출 한 다음 에 하 나 를 추가 해 야 합 니까?그러나 이것 은 위 와 마찬가지 로 단일 스 레 드 가 높 은 병행 에 대한 지원 이 높 지 않 기 때문에 병행 량 이 적은 프로젝트 에 만 적합 합 니 다.
2.3、uuid
uid 를 반복 되 지 않 는 메 인 키 id 로 사용 할 수 있 습 니 다.그러나 uid 의 문 제 는 무질서 한 문자열 입 니 다.uid 를 메 인 키 로 사용 하면 메 인 키 색인 이 실 효 됩 니 다.
2.4 눈꽃 알고리즘
눈꽃 알고리즘 은 분포 식 id 를 해결 하 는 효율 적 인 방안 으로 대부분의 인터넷 회사 들 이 눈꽃 알고리즘 을 사용 하고 있 으 며 물론 회사 자체 가 다른 방안 을 실현 하 는 방안 도 있다.
2.눈꽃 알고리즘
1.원리
눈꽃 알고리즘 은 64 비트 long 형식의 데이터 저장 id 를 사용 하 는 것 입 니 다.가장 높 은 비트 는 0 또는 1,0 은 정 수 를 의미 하고 1 은 마이너스 입 니 다.보통 0 이기 때문에 가장 높 은 비트 는 변 하지 않 습 니 다.41 비트 저장 밀리초 급 시간 스탬프,10 비트 저장 장치 코드(5 비트 datacenterId 와 5 비트 workerId 포함),12 저장 시리 얼 번호 입 니 다.이렇게 최대 2 의 10 제곱 기계,즉 1024 대의 기 계 는 최대 밀리초 마다 기계 당 2 의 12 제곱 즉 4096 개의 id 를 생산 한다.다음 코드 구현)
그러나 일반적으로 우 리 는 그렇게 많은 기계 가 없 기 때문에 53 비트 로 id 를 저장 할 수 있다.53 명 을 왜 써 요?
우 리 는 거의 웹 페이지 와 접촉 하기 때문에 js 와 접촉 해 야 한다.js 가 지원 하 는 가장 큰 정형 범 위 는 53 비트 이 고 이 범 위 를 초과 하면 정밀 도 를 잃 게 된다.53 안에 js 에서 직접 읽 을 수 있 고 53 위 를 초과 하면 문자열 로 전환 해 야 js 처리 가 정확 하 다.53 저장 하면 32 비트 저장 초 급 타임 스탬프,5 비트 저장 기계 코드,16 비트 저장 직렬 화 를 통 해 기계 한 대 당 65536 개의 중복 되 지 않 는 id 를 생산 할 수 있 습 니 다.
2.단점
눈꽃 알고리즘 은 시간 에 심각하게 의존 하기 때문에 서버 시계 리 턴 문제 가 발생 하면 중복 되 는 id 가 발생 할 수 있 습 니 다.물론 서버 시간 을 수정 하 는 회 사 는 거의 없다.수정 후 각종 문 제 를 일 으 킬 수 있다.회 사 는 서버 한 대 를 새로 추가 하 더 라 도 서버 시간 을 수정 하 는 것 을 원 하지 않 지만 특수 한 상황 은 배제 하지 않 는 다.
어떻게 시계 가 돌아 오 는 문 제 를 해결 합 니까?직렬 화 된 초기 값 에 보폭 을 설정 할 수 있 습 니 다.시계 리 턴 이 벤트 를 촉발 할 때마다 초기 보폭 은 1w 를 추가 하여 아래 코드 의 85 줄 에서 이 루어 집 니 다.sequence 의 초기 값 을 10000 으로 설정 할 수 있 습 니 다.
3.코드 구현
64 비트 코드 구현:
package com.yl.common;
/**
* Twitter_Snowflake<br>
* SnowFlake ( - ):<br>
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
* 1 ， long Java ， ， 0， 1， id ， 0<br>
* 41 ( )， ，41 ， （ - )
* ）， ， id ， （ IdWorker startTime ）。41 ， 69 ， T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
* 10 ， 1024 ， 5 datacenterId 5 workerId<br>
* 12 ， ，12 ( ， ) 4096 ID <br>
* 64 ， Long 。<br>
* SnowFlake ， ， ID ( ID ID )， ， ，SnowFlake 26 ID 。
*/
public class SnowflakeIdWorker {
// ==============================Fields===========================================
/** (2020-01-01) */
private final long twepoch = 1577808000000L;
/** id */
private final long workerIdBits = 5L;
/** id */
private final long datacenterIdBits = 5L;
/** id， 31 ( ) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** id， 31 */
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
/** id */
private final long sequenceBits = 12L;
/** ID 12 */
private final long workerIdShift = sequenceBits;
/** id 17 (12+5) */
private final long datacenterIdShift = sequenceBits + workerIdBits;
/** 22 (5+5+12) */
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
/** ， 4095 (0b111111111111=0xfff=4095) */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** ID(0~31) */
private long workerId;
/** ID(0~31) */
private long datacenterId;
/** (0~4095) */
private long sequence = 0L;
/** ID */
private long lastTimestamp = -1L;
//==============================Constructors=====================================
/**
*
* @param workerId ID (0~31)
* @param datacenterId ID (0~31)
*/
public SnowflakeIdWorker(long workerId, long datacenterId) {
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;
}
// ==============================Methods==========================================
/**
* ID ( )
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
// ID ，
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
// ，
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
//
if (sequence == 0) {
// ,
timestamp = tilNextMillis(lastTimestamp);
}
}
// ，
else {
sequence = 0L;
}
// ID
lastTimestamp = timestamp;
// 64 ID
return ((timestamp - twepoch) << timestampLeftShift) //
| (datacenterId << datacenterIdShift) //
| (workerId << workerIdShift) //
| sequence;
}
/**
* ，
* @param lastTimestamp ID
* @return
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
*
* @return ( )
*/
protected long timeGen() {
return System.currentTimeMillis();
}
//==============================Test=============================================
/** */
public static void main(String[] args) {
SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
for (int i = 0; i < 100; i++) {
long id = idWorker.nextId();
System.out.println(id);
}
}
}긴 말 안 할 게 요.그냥 코드 보 세 요~
/**
* <p> ：IdWorker.java</p>
* <p> ： ID</p>
* <pre>
* Twitter Snowflake JAVA
* </pre>
* IdWorker ， ， 0 ， ― ：
* 1||0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000
* ， （ long ）， 41 ，
* 5 datacenter ，5 ID（ ， ），
* 12 ， 64 ， Long 。
* ， ， ID （ datacenter ID ），
* ， ，snowflake 26 ID ， 。
* <p>
* 64 ID (42( )+5( ID)+5( )+12( ))
*
* @author Polim
*/
public class IdWorker {
// ， ， （ ）
private final static long twepoch = 1288834974657L;
//
private final static long workerIdBits = 5L;
//
private final static long datacenterIdBits = 5L;
// ID
private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);
// ID
private final static long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
//
private final static long sequenceBits = 12L;
// ID 12
private final static long workerIdShift = sequenceBits;
// ID 17
private final static long datacenterIdShift = sequenceBits + workerIdBits;
// 22
private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private final static long sequenceMask = -1L ^ (-1L << sequenceBits);
/* id */
private static long lastTimestamp = -1L;
// 0，
private long sequence = 0L;
private final long workerId;
// id
private final long datacenterId;
public IdWorker(){
this.datacenterId = getDatacenterId(maxDatacenterId);
this.workerId = getMaxWorkerId(datacenterId, maxWorkerId);
}
/**
* @param workerId
* ID
* @param datacenterId
*
*/
public IdWorker(long workerId, long datacenterId) {
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;
}
/**
* ID
*
* @return
*/
public synchronized long nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
// ， +1
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
// ，
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
// ID ID， ID
long nextId = ((timestamp - twepoch) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift) | sequence;
return nextId;
}
private long tilNextMillis(final long lastTimestamp) {
long timestamp = this.timeGen();
while (timestamp <= lastTimestamp) {
timestamp = this.timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
/**
* <p>
* maxWorkerId
* </p>
*/
protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {
StringBuffer mpid = new StringBuffer();
mpid.append(datacenterId);
String name = ManagementFactory.getRuntimeMXBean().getName();
if (!name.isEmpty()) {
/*
* GET jvmPid
*/
mpid.append(name.split("@")[0]);
}
/*
* MAC + PID hashcode 16
*/
return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}
/**
* <p>
* id
* </p>
*/
protected static long getDatacenterId(long maxDatacenterId) {
long id = 0L;
try {
InetAddress ip = InetAddress.getLocalHost();
NetworkInterface network = NetworkInterface.getByInetAddress(ip);
if (network == null) {
id = 1L;
} else {
byte[] mac = network.getHardwareAddress();
id = ((0x000000FF & (long) mac[mac.length - 1])
| (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
id = id % (maxDatacenterId + 1);
}
} catch (Exception e) {
System.out.println(" getDatacenterId: " + e.getMessage());
}
return id;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
MySQL에서 JSON 인덱싱 - aarondfrancis사람들은 종종 MySQL로 JSON을 인덱싱할 수 없다고 말하지만 완전히 정확하지는 않습니다. MySQL로 JSON 열을 인덱싱하는 것은 완전히 가능합니다! 사람들은 종종 MySQL로 JSON을 인덱싱할 수 없다고 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
