자바 알고리즘 정적 내부 클래스 눈꽃 알고리즘 구현

개술
테이블 의 메 인 키 ID 를 생 성 할 때,우 리 는 메 인 키 가 증가 하거나 UUID 를 고려 할 수 있 지만,그것들 은 모두 뚜렷 한 단점 을 가지 고 있다
홈 키 자체 증가:1.자체 증가 ID 는 파충류 에 의 해 데 이 터 를 옮 겨 다 니 기 쉽다.2.분 표 라 이브 러 리 에서 ID 충돌 이 발생 합 니 다.
UUID:1.너무 길 고 색인 조각 이 있 으 며 색인 이 공간 을 많이 차지 하 는 문제 2.무질서 합 니 다.
눈꽃 알고리즘 은 분포 식 장면 에서 유일한 ID 를 만 드 는 데 적합 하 며 유일 하면 서도 정렬 할 수 있 습 니 다.눈꽃 ID 생산 효율 성 을 높이 기 위해 서 는
이 안에서 데이터 의 연산 은 모두 비트 연산 을 사용한다.
개념
1.원리
SnowFlake 알고리즘 이 ID 를 생 성 한 결 과 는 다음 그림 과 같은 64bit 크기 의 정수 입 니 다.

알고리즘 설명:
1bit 는 이 진 에서 가장 높 은 위 치 는 기호 위치 이 고 1 은 음 수 를 나타 내 며 0 은 정 수 를 나타 내기 때문이다.생 성 된 ID 는 모두 정수 이기 때문에 최고 위 는 0 으로 고정 되 어 있 습 니 다.
41bit-타임 스탬프 는 밀리초 단위 로 정확 하고 41 비트 의 길 이 는 69 년 동안 사용 할 수 있 습 니 다.시간 대 에 따라 정렬 할 수 있 는 중요 한 역할 도 있다.
10bit-작업 기계 id 10 비트 의 기계 표지,10 비트 의 길 이 는 최대 1024 개의 노드 배 치 를 지원 합 니 다.
12bit-시리 얼 번호,즉 일련의 자체 증가 id 로 같은 노드 가 같은 밀리초 에 여러 개의 ID 번 호 를 생 성 하 는 것 을 지원 할 수 있 습 니 다.
12 비트(bit)가 나 타 낼 수 있 는 최대 정 수 는 0,1,2,3,...4094 라 는 4095 개의 숫자 로 같은 기계 의 같은 시간 절단(밀리초)내 에 발생 하 는 4095 개의 ID 번 호 를 나 타 낼 수 있다.
자바 에서 64bit 의 정 수 는 log 형식 이기 때문에 자바 에서 SnowFlake 알고리즘 이 생 성 한 id 는 log 로 저장 된다 는 뜻 이다.
2.정적 클래스 클래스 단일 모드 에서 눈꽃 ID 코드 생산
아래 에 눈꽃 ID 를 생 성 하 는 코드 는 온라인 분포 식 프로젝트 에서 분포 식 메 인 키 ID 를 생 성 하 는 데 사용 할 수 있 습 니 다.디자인 이 사용 하 는 정적 내부 클래스 의 단일 모드 이기 때문에 synchronized 자 물 쇠 를 추가 하여 보장 합 니 다.
같은 서버 스 레 드 가 안전 합 니 다.서로 다른 서버 는 사실 상관 이 없다.그들의 기계 코드 가 일치 하지 않 기 때문에 같은 시각 에 두 서버 가 모두 눈꽃 ID 를 만들어 도 같 지 않다.
1.코드

public class SnowIdUtils {
    /**
     *          
     */
    private static class SnowFlake {

        /**
         *      （    ）
         */
        private static final SnowIdUtils.SnowFlake SNOW_FLAKE = new SnowIdUtils.SnowFlake();
        /**
         *       
         */
        private final long START_TIMESTAMP = 1557489395327L;
        /**
         *        
         */
        private final long SEQUENCE_BIT = 12;
        /**
         *         
         */
        private final long MACHINE_BIT = 10;
        /**
         *        
         */
        private final long TIMESTAMP_LEFT = SEQUENCE_BIT + MACHINE_BIT;
        /**
         *        （4095）
         */
        private final long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);
        /**
         *        （1023）
         */
        private final long MAX_MACHINE_ID = ~(-1L << MACHINE_BIT);
        /**
         *   id      
         */
        private long machineIdPart;
        /**
         *    
         */
        private long sequence = 0L;
        /**
         *       
         */
        private long lastStamp = -1L;

        /**
         *            
         */
        private SnowFlake() {
            //            
            long localIp = 4321;
            //localIp & MAX_MACHINE_ID      1023,    12 
            machineIdPart = (localIp & MAX_MACHINE_ID) << SEQUENCE_BIT;
        }
        /**
         *     ID
         */
        public synchronized long nextId() {
            long currentStamp = timeGen();
            //        
            while (currentStamp < lastStamp) {
                // //         ,ID       .
                throw new RuntimeException(String.format("      .  Refusing to generate id for %d milliseconds", lastStamp - currentStamp));
            }
            if (currentStamp == lastStamp) {
                //   +1
                sequence = (sequence + 1) & MAX_SEQUENCE;
                //        
                if (sequence == 0) {
                    //         ,       
                    currentStamp = getNextMill();
                }
            } else {
                //     ，    0
                sequence = 0L;
            }
            lastStamp = currentStamp;
            //     +      +     
            return (currentStamp - START_TIMESTAMP) << TIMESTAMP_LEFT | machineIdPart | sequence;
        }
        /**
         *         ，         
         */
        private long getNextMill() {
            long mill = timeGen();
            //
            while (mill <= lastStamp) {
                mill = timeGen();
            }
            return mill;
        }
        /**
         *              
         */
        protected long timeGen() {
            return System.currentTimeMillis();
        }
    }

    /**
     *   long    ID
     */
    public static long uniqueLong() {
        return SnowIdUtils.SnowFlake.SNOW_FLAKE.nextId();
    }
    /**
     *   String    ID
     */
    public static String uniqueLongHex() {
        return String.format("%016x", uniqueLong());
    }

    /**
     *   
     */
    public static void main(String[] args) throws InterruptedException {
        //      
        long start = System.currentTimeMillis();
        // 100       
        final CountDownLatch latch = new CountDownLatch(100);
        //     20           
        final Map<Long, Integer> map = new ConcurrentHashMap();
        for (int i = 0; i < 100; i++) {
            //  100   
            new Thread(() -> {
                for (int s = 0; s < 2000; s++) {
                    long snowID = SnowIdUtils.uniqueLong();
                    log.info("    ID={}",snowID);
                    Integer put = map.put(snowID, 1);
                    if (put != null) {
                        throw new RuntimeException("    ");
                    }
                }
                latch.countDown();
            }).start();
        }
        //   100        ，        
        latch.await();
        log.info("  20    ID   ={}", System.currentTimeMillis() - start);
    }
}

2.테스트 결과

그림 에서 우 리 는 얻 을 수 있다.
1.100 개의 스 레 드 와 동시에 20 만 개의 눈꽃 ID 를 생 성 하 는 시간 은 약 1.6 초 정도 이 고 모든 성능 은 만 ok 입 니 다.
2.20 만 개의 눈꽃 ID 를 생 성 하 는데 똑 같은 ID 가 하나 도 없습니다.왜냐하면 하나 가 있 으 면 이상 을 던 집 니 다.
3,왜 41 명 스탬프 최 장 69 년
우리 가 생각 하 는 41 의 2 진법 은 최대 치 인 41 위 가 모두 1 이다.즉,41 위 는 4.567916.밀리초 의 값 을 나 타 낼 수 있 고 단위 년 으로 바 뀌 면?
년
우 리 는 코드 를 불 려 서 알 수 있다.

public static void main(String[] args) {
    //41       
    String minTimeStampStr = "00000000000000000000000000000000000000000";
    //41       
    String maxTimeStampStr = "11111111111111111111111111111111111111111";
    // 10  
    long minTimeStamp = new BigInteger(minTimeStampStr, 2).longValue();
    long maxTimeStamp = new BigInteger(maxTimeStampStr, 2).longValue();
    //        
    long oneYearMills = 1L * 1000 * 60 * 60 * 24 * 365;
    //         
    System.out.println((maxTimeStamp - minTimeStamp) / oneYearMills);
}

실행 결과

그 러 니까 눈꽃 알고리즘 으로 생 성 된 ID 는 69 년 동안 중복 되 지 않 을 수 있 습 니 다.69 년 이 넘 으 면 서버 배 치 를 바 꾸 는 것 도 고려 해 보 세 요.그리고 이 서버 의 ID 와 이전 에는 중복 되 지 않 았 음 을 보증 해 야 합 니 다.
이상 은 자바 알고리즘 의 정적 내부 클래스 가 눈꽃 알고리즘 을 실현 하 는 상세 한 내용 입 니 다.자바 알고리즘 에 관 한 자 료 는 다른 관련 글 을 주목 하 십시오!