公司的雪花算法

package com.ymm56.trade.order.center.biz.id.util;

/**
 * snowflake改写的ID生成器实现
 */
class SnowflakeOrderIdGenerator implements OrderIdGenerator  {
    //private final long twepoch = 1481515932888L;//2016-12-12 12:12:12

    //7位机器码
    private final long workerIdBits = 8L;

    //2位数据中心编码
    private final long datacenterIdBits = 2L;
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    //8位seq编码
    private final long sequenceBits = 7L;

    private final long workerIdShift = sequenceBits;
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long workerId;

    //用于创建id的datacenterId
    private long datacenterIdForCreate;

    //用于替换id的datacenterId
    private long datacenterIdForPlace;

    private long sequence = 0L;

    private long lastTimestamp = -1L;

    // 现有的比较时间戳
    private static final long COMPARE_TIME_PHASE_A = 1418741106341L;

    // 到达老id后为了跳过老id段的时间戳
    private static final long COMPARE_TIME_PHASE_B = 1414034077413L;

    // 用现有方式到达老id的时间戳
    private static final long OLD_ID_REACH_TIMESTAMP = 2149785353253L;

    // 用于截取7位机器码(老ID是截取5位机器码+2位seq)
    private static final int WORKID_SEQUENCE_TAIL = 0x7F;

    // 用于截取最后8位(截取seq)
    private static final int SEQUENCE_TAIL = 0xFF;


    public SnowflakeOrderIdGenerator(long workerId, long datacenterIdForCreate, long datacenterIdForPlace) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterIdForCreate > maxDatacenterId || datacenterIdForCreate < 0) {
            throw new IllegalArgumentException(String.format("datacenterIdForReplace Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        if (datacenterIdForPlace > maxDatacenterId || datacenterIdForPlace < 0) {
            throw new IllegalArgumentException(String.format("datacenterIdForReplace Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterIdForCreate = datacenterIdForCreate;
        this.datacenterIdForPlace = datacenterIdForPlace;
    }

    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) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        return (calTimestamp(timestamp) << timestampLeftShift) | (datacenterIdForCreate << datacenterIdShift) | (workerId << workerIdShift) | sequence;
    }

    /**
     * 创建老Id的替换Id
     * @param originId
     * @return
     */
    public synchronized long replaceId(long originId, long generateIncreaseId) {
        // step 1 截取时间戳
        long timestamp = originId >> timestampLeftShift;
        // step 2 截取第9到15位(1、新发号器生成的ID是7位机器码  2、老发号器生成的ID是5位机器码+seq前两位)
        long workTail = (originId >> sequenceBits) & WORKID_SEQUENCE_TAIL;
        // step 3 截取sequence的后8位
        long sequence = generateIncreaseId & SEQUENCE_TAIL;
        return (timestamp << timestampLeftShift) | (datacenterIdForPlace << datacenterIdShift) | (workTail << workerIdShift) | sequence;
    }

    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    protected long timeGen() {
        return System.currentTimeMillis();
    }


    /**
     * 绕过可能碰撞上的Id,计算时间戳
     * @param timestamp
     * @return
     */
    protected long calTimestamp(long timestamp){
        long compareTimestamp = COMPARE_TIME_PHASE_A;
        // 跳过现有的 95819431531254381 - 96436391095872324的订单id
        if (timestamp > OLD_ID_REACH_TIMESTAMP) {
            compareTimestamp = COMPARE_TIME_PHASE_B;
        }
        return timestamp - compareTimestamp;
    }

    public static long getTimeStampByOrderId(long orderId) {
        return (orderId >> 17) + COMPARE_TIME_PHASE_A;
    }
}

 

package com.ymm56.trade.order.center.biz.id.util;

import ocean.id.IPv4;
import ocean.id.NetUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.util.CollectionUtils;
import org.springframework.util.StringUtils;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * ID生成器工具类
 */
public class OrderIdUtil {

    private static Logger logger = LoggerFactory.getLogger(ocean.id.IdUtil.class);

    private static OrderIdGenerator orderIdGenerator;

    private static long workerId = 1;

    //用于生成新id时使用的datacenterId
    private static long datacenterIdForCreate = 1;

    //用于替换老id时使用的datacenterId
    private static long datacenterIdForPlace = 3;

    //ip取模值
    private static int WORKER_ID_MO = 127;

    private static OrderZkClient zkClient = OrderZkClient.getInstance();

    //根节点
    private static final String ID_CONFIG_PATH = "/YMM56/ORDERID/";

    /**
     * 生成Id
     * @throws Exception
     */
    public static synchronized long getId(String appName) throws Exception {
        return getOrderIdGenerator(appName).nextId();
    }

    /**
     * 替换Id
     * @param appName
     * @param originId
     * @return
     * @throws Exception
     */
    public static synchronized long replaceId(String appName, long originId, long generateIncreaseId) throws Exception{
        return getOrderIdGenerator(appName).replaceId(originId, generateIncreaseId);
    }

    /**
     * 初始化 idGenerator
     * @return
     * @throws Exception
     */
    private static synchronized OrderIdGenerator getOrderIdGenerator(String appName) throws Exception{
        if(orderIdGenerator == null) {
            workerId = getWorkerId(appName);
            orderIdGenerator = new SnowflakeOrderIdGenerator(workerId, datacenterIdForCreate, datacenterIdForPlace);
        }
        return orderIdGenerator;
    }

    /**
     * 获取workId
     * @param appName
     * @return
     * @throws Exception
     */
    private static long getWorkerId(String appName) throws Exception {
        String ip = NetUtils.getFirstLocalIp();
        String path = ID_CONFIG_PATH + appName;
        Map<String, String> workerIdMap = new HashMap<>();
        if (zkClient.exists(path)) {
            List<String> childPath = zkClient.getChildren(path);

            if (!CollectionUtils.isEmpty(childPath)) {
                for (int i = 0; i < childPath.size(); i++) {
                    String existIp = zkClient.get(path + "/" + childPath.get(i));
                    if (!StringUtils.isEmpty(existIp))  {
                        if(existIp.equals(ip)){
                            return Integer.parseInt(childPath.get(i));
                        }
                        workerIdMap.put(childPath.get(i), existIp);
                    }
                }
            }
        }

        // workerId取机器ip转long后mod 127
        workerId = IPv4.longValue(ip) % WORKER_ID_MO;

        // workerId是否已被占用,如被占用直接+1循环遍历取下一个直到取到未被占用的workerId
        int i = 0;
        do {
            String existIp = workerIdMap.get(workerId + "");
            if (StringUtils.isEmpty(existIp)) {
                if(zkClient.createIfNotExist(path + "/" + workerId + "", ip)){
                    logger.info("机器:[" + ip + "]计算出的workerId为:" + workerId);
                    return workerId;
                }
            }

            workerId = workerId + 1;
            workerId = (WORKER_ID_MO - workerId) >= 0 ? workerId : Math.abs(WORKER_ID_MO + 1 - workerId);
            ++i;
        } while (i <= WORKER_ID_MO);

        logger.error("workerId已经达到最大值,机器:[" + ip + "]使用workerId:" + workerId);
        return workerId;
    }

    public static long getOrderCreateTimestamp(long orderId) {
        return SnowflakeOrderIdGenerator.getTimeStampByOrderId(orderId);
    }
}

 

上一篇:BZOJ2428 HAOI2006均分数据(模拟退火)


下一篇:浅谈雪花算法