6位顺序号生成_分布式id生成策略,我和面试官扯了一个半小时
一、分布式系統(tǒng)帶來ID生成挑戰(zhàn)
在分布式系統(tǒng)中,往往需要對大量的數據如訂單、賬戶進行標識,以一個有意義的有序的序列號來作為全局唯一的ID。
而分布式系統(tǒng)中我們對ID生成器要求又有哪些呢?
全局唯一性:不能出現重復的ID號,既然是唯一標識,這是最基本的要求。
遞增:比較低要求的條件為趨勢遞增,即保證下一個ID一定大于上一個ID,而比較苛刻的要求是連續(xù)遞增,如1,2,3等等。
高可用高性能:ID生成事關重大,一旦掛掉系統(tǒng)崩潰;高性能是指必須要在壓測下表現良好,如果達不到要求則在高并發(fā)環(huán)境下依然會導致系統(tǒng)癱瘓。
二、業(yè)內方案簡介
1. UUID方案
優(yōu)點:
能夠保證獨立性,程序可以在不同的數據庫間遷移,效果不受影響。
保證生成的ID不僅是表獨立的,而且是庫獨立的,這點在你想切分數據庫的時候尤為重要。
缺點:
性能問題:UUID太長,通常以36長度的字符串表示,對MySQL索引不利:如果作為數據庫主鍵,在InnoDB引擎下,UUID的無序性可能會引起數據位置頻繁變動,嚴重影響性能。
UUID無業(yè)務含義:很多需要ID能標識業(yè)務含義的地方不使用。
不滿足遞增要求。
2. snowflake方案
snowflake是twitter開源的分布式ID生成系統(tǒng)。?Twitter每秒有數十萬條消息的請求,每條消息都必須分配一條唯一的id,這些id還需要一些大致的順序(方便客戶端排序),并且在分布式系統(tǒng)中不同機器產生的id必須不同。
snowflake的結構如下(每部分用-分開):
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 – 000000000000
第一位為未使用,接下來的41位為毫秒級時間(41位的長度可以使用69年),然后是5位datacenterId和5位workerId(10位的長度最多支持部署1024個節(jié)點) ,最后12位是毫秒內的計數(12位的計數順序號支持每個節(jié)點每毫秒產生4096個ID序號)
一共加起來剛好64位,為一個Long型。
snowflake生成的ID整體上按照時間自增排序,并且整個分布式系統(tǒng)內不會產生ID碰撞(由datacenter和workerId作區(qū)分),并且效率較高。snowflake的缺點是:
強依賴時鐘,如果主機時間回撥,則會造成重復ID
ID雖然有序,但是不連續(xù)
snowflake現在有較好的改良方案,比如美團點評開源的分布式ID框架:leaf,通過使用ZooKeeper解決了時鐘依賴問題。
3. 基于數據庫方案
利用數據庫生成ID是最常見的方案。能夠確保ID全數據庫唯一。其優(yōu)缺點如下:
優(yōu)點:
非常簡單,利用現有數據庫系統(tǒng)的功能實現,成本小,有DBA專業(yè)維護。
ID單調自增。
缺點:
不同數據庫語法和實現不同,數據庫遷移的時候或多數據庫版本支持的時候需要處理。
在單個數據庫或讀寫分離或一主多從的情況下,只有一個主庫可以生成。有單點故障的風險。
在性能達不到要求的情況下,比較難于擴展。
如果涉及多個系統(tǒng)需要合并或者數據遷移會比較麻煩。
分表分庫的時候會有麻煩。
4.其他方案簡介
通過Redis生成ID(主要通過redis的自增函數)、ZooKeeper生成ID、MongoDB的ObjectID等均可實現唯一性的要求。
三、我們在實際應用中使用的方案
1. 方案簡介
實際業(yè)務中,除了分布式ID全局唯一之外,還有是否趨勢/連續(xù)遞增的要求。根據具體業(yè)務需求的不同,有兩種可選方案。
一是只保證全局唯一,不保證連續(xù)遞增。二是既保證全局唯一,又保證連續(xù)遞增。
2. 基于ZooKeeper和本地緩存的方案
基于zookeeper分布式ID實現方案有很多種,本方案只使用ZooKeeper作為分段節(jié)點協(xié)調工具。每臺服務器首先從zookeeper緩存一段,如1-1000的id。
此時zk上保存最大值1000,每次獲取的時候都會進行判斷,如果id小于本地最大值,即id<=1000,則更新本地的當前值,如果id大于本地當前值,比如說是1001,則會將從zk再獲取下一個id數據段并在本地緩存。獲取數據段的時候需要更新zk節(jié)點數據,更新的時候使用curator的分布式鎖來實現。
由于id是從本機獲取,因此本方案的優(yōu)點是性能非常好。缺點是如果多主機負載均衡,則會出現不連續(xù)的id,當然將遞增區(qū)段設置為1也能保證連續(xù)的id,但是效率會受到很大影響。
實現關鍵源碼如下:
import org.apache.curator.framework.CuratorFramework;import org.apache.curator.framework.CuratorFrameworkFactory;
import org.apache.curator.framework.recipes.locks.InterProcessSemaphoreMutex;
import org.apache.curator.retry.ExponentialBackoffRetry;
import org.apache.zookeeper.CreateMode;
import org.apache.zookeeper.data.Stat;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.io.UnsupportedEncodingException;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
/**
* 根據開源項目mycat實現基于zookeeper的遞增序列號
*
* 只要配置好ZK地址和表名的如下屬性
* MINID 某線程當前區(qū)間內最小值
* MAXID 某線程當前區(qū)間內最大值
* CURID 某線程當前區(qū)間內當前值
*
* @author wangwanbin
* @version 1.0
* @time 2017/9/1
*/
public class ZKCachedSequenceHandler extends SequenceHandler {
? ?protected static final Logger LOGGER = LoggerFactory.getLogger(ZKCachedSequenceHandler.class);
? ?private static final String KEY_MIN_NAME = ".MINID";// 1
? ?private static final String KEY_MAX_NAME = ".MAXID";// 10000
? ?private static final String KEY_CUR_NAME = ".CURID";// 888
? ?private final static long PERIOD = 1000;//每次緩存的ID段數量
? ?private static ZKCachedSequenceHandler instance = new ZKCachedSequenceHandler();
? ?/**
? ? * 私有化構造方法,單例模式
? ? */
? ?private ZKCachedSequenceHandler() {
? ?}
? ?/**
? ? * 獲取sequence工具對象的唯一方法
? ? *
? ? * @return
? ? */
? ?public static ZKCachedSequenceHandler getInstance() {
? ? ? ?return instance;
? ?}
? ?private Map> tableParaValMap = null;
? ?private CuratorFramework client;
? ?private InterProcessSemaphoreMutex interProcessSemaphore = null;
? ?public void loadZK() {
? ? ? ?try {
? ? ? ? ? ?this.client = CuratorFrameworkFactory.newClient(zkAddress, new ExponentialBackoffRetry(1000, 3));
? ? ? ? ? ?this.client.start();
? ? ? ?} catch (Exception e) {
? ? ? ? ? ?LOGGER.error("Error caught while initializing ZK:" + e.getCause());
? ? ? ?}
? ?}
? ?public Map getParaValMap(String prefixName) {
? ? ? ?if (tableParaValMap == null) {
? ? ? ? ? ?try {
? ? ? ? ? ? ? ?loadZK();
? ? ? ? ? ? ? ?fetchNextPeriod(prefixName);
? ? ? ? ? ?} catch (Exception e) {
? ? ? ? ? ? ? ?LOGGER.error("Error caught while loding configuration within current thread:" + e.getCause());
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?Map paraValMap = tableParaValMap.get(prefixName);
? ? ? ?return paraValMap;
? ?}
? ?public Boolean fetchNextPeriod(String prefixName) {
? ? ? ?try {
? ? ? ? ? ?Stat stat = this.client.checkExists().forPath(PATH + "/" + prefixName + SEQ);
? ? ? ? ? ?if (stat == null || (stat.getDataLength() == 0)) {
? ? ? ? ? ? ? ?try {
? ? ? ? ? ? ? ? ? ?client.create().creatingParentsIfNeeded().withMode(CreateMode.PERSISTENT)
? ? ? ? ? ? ? ? ? ? ? ? ? ?.forPath(PATH + "/" + prefixName + SEQ, String.valueOf(0).getBytes());
? ? ? ? ? ? ? ?} catch (Exception e) {
? ? ? ? ? ? ? ? ? ?LOGGER.debug("Node exists! Maybe other instance is initializing!");
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ? ? ?if (interProcessSemaphore == null) {
? ? ? ? ? ? ? ?interProcessSemaphore = new InterProcessSemaphoreMutex(client, PATH + "/" + prefixName + SEQ);
? ? ? ? ? ?}
? ? ? ? ? ?interProcessSemaphore.acquire();
? ? ? ? ? ?if (tableParaValMap == null) {
? ? ? ? ? ? ? ?tableParaValMap = new ConcurrentHashMap<>();
? ? ? ? ? ?}
? ? ? ? ? ?Map paraValMap = tableParaValMap.get(prefixName);
? ? ? ? ? ?if (paraValMap == null) {
? ? ? ? ? ? ? ?paraValMap = new ConcurrentHashMap<>();
? ? ? ? ? ? ? ?tableParaValMap.put(prefixName, paraValMap);
? ? ? ? ? ?}
? ? ? ? ? ?long now = Long.parseLong(new String(client.getData().forPath(PATH + "/" + prefixName + SEQ)));
? ? ? ? ? ?client.setData().forPath(PATH + "/" + prefixName + SEQ, ((now + PERIOD) + "").getBytes());
? ? ? ? ? ?if (now == 1) {
? ? ? ? ? ? ? ?paraValMap.put(prefixName + KEY_MAX_NAME, PERIOD + "");
? ? ? ? ? ? ? ?paraValMap.put(prefixName + KEY_MIN_NAME, "1");
? ? ? ? ? ? ? ?paraValMap.put(prefixName + KEY_CUR_NAME, "0");
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?paraValMap.put(prefixName + KEY_MAX_NAME, (now + PERIOD) + "");
? ? ? ? ? ? ? ?paraValMap.put(prefixName + KEY_MIN_NAME, (now) + "");
? ? ? ? ? ? ? ?paraValMap.put(prefixName + KEY_CUR_NAME, (now) + "");
? ? ? ? ? ?}
? ? ? ?} catch (Exception e) {
? ? ? ? ? ?LOGGER.error("Error caught while updating period from ZK:" + e.getCause());
? ? ? ?} finally {
? ? ? ? ? ?try {
? ? ? ? ? ? ? ?interProcessSemaphore.release();
? ? ? ? ? ?} catch (Exception e) {
? ? ? ? ? ? ? ?LOGGER.error("Error caught while realeasing distributed lock" + e.getCause());
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return true;
? ?}
? ?public Boolean updateCURIDVal(String prefixName, Long val) {
? ? ? ?Map paraValMap = tableParaValMap.get(prefixName);
? ? ? ?if (paraValMap == null) {
? ? ? ? ? ?throw new IllegalStateException("ZKCachedSequenceHandler should be loaded first!");
? ? ? ?}
? ? ? ?paraValMap.put(prefixName + KEY_CUR_NAME, val + "");
? ? ? ?return true;
? ?}
? ?/**
? ? * 獲取自增ID
? ? *
? ? * @param sequenceEnum
? ? * @return
? ? */
? ?@Override
? ?public synchronized long nextId(SequenceEnum sequenceEnum) {
? ? ? ?String prefixName = sequenceEnum.getCode();
? ? ? ?Map paraMap = this.getParaValMap(prefixName);
? ? ? ?if (null == paraMap) {
? ? ? ? ? ?throw new RuntimeException("fetch Param Values error.");
? ? ? ?}
? ? ? ?Long nextId = Long.parseLong(paraMap.get(prefixName + KEY_CUR_NAME)) + 1;
? ? ? ?Long maxId = Long.parseLong(paraMap.get(prefixName + KEY_MAX_NAME));
? ? ? ?if (nextId > maxId) {
? ? ? ? ? ?fetchNextPeriod(prefixName);
? ? ? ? ? ?return nextId(sequenceEnum);
? ? ? ?}
? ? ? ?updateCURIDVal(prefixName, nextId);
? ? ? ?return nextId.longValue();
? ?}
? ?public static void main(String[] args) throws UnsupportedEncodingException {
? ? ? ?long startTime = System.currentTimeMillis(); ? //獲取開始時間
? ? ? ?final ZKCachedSequenceHandler sequenceHandler = getInstance();
? ? ? ?sequenceHandler.loadZK();
? ? ? ?new Thread() {
? ? ? ? ? ?public void run() {
? ? ? ? ? ? ? ?long startTime2 = System.currentTimeMillis(); ? //獲取開始時間
? ? ? ? ? ? ? ?for (int i = 0; i < 5000; i++) {
? ? ? ? ? ? ? ? ? ?System.out.println("線程1 " + sequenceHandler.nextId(SequenceEnum.ACCOUNT));
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?long endTime2 = System.currentTimeMillis(); //獲取結束時間
? ? ? ? ? ? ? System.out.println("程序運行時間1:" + (endTime2 - startTime2) + "ms");
? ? ? ? ? ?}
? ? ? ?}.start();
? ? ? ?for (int i = 0; i < 5000; i++) {
? ? ? ? ? ?System.out.println("線程2 " + sequenceHandler.nextId(SequenceEnum.ACCOUNT));
? ? ? ?}
? ? ? ?long endTime = System.currentTimeMillis(); //獲取結束時間
? ? ? System.out.println("程序運行時間2:" + (endTime - startTime) + "ms");
? ?}
}
可以看到,由于不需要進行過多的網絡消耗,緩存式的zk協(xié)調方案性能相當了得,生成10000個id僅需553ms(兩個線程耗時較長者) , 平均每個id消耗0.05ms。
?3.利用zk的永久自增節(jié)點策略實現持續(xù)遞增ID
使用zk的永久sequence策略創(chuàng)建節(jié)點,并獲取返回值,然后刪除前一個節(jié)點,這樣既防止zk服務器存在過多的節(jié)點,又提高了效率;節(jié)點刪除采用線程池來統(tǒng)一處理,提高響應速度。
優(yōu)點:能創(chuàng)建連續(xù)遞增的ID。
關鍵實現代碼如下:
package com.zb.p2p.utils;import com.zb.p2p.enums.SequenceEnum;
import org.apache.commons.pool2.PooledObject;
import org.apache.commons.pool2.PooledObjectFactory;
import org.apache.commons.pool2.impl.DefaultPooledObject;
import org.apache.commons.pool2.impl.GenericObjectPool;
import org.apache.commons.pool2.impl.GenericObjectPoolConfig;
import org.apache.curator.framework.CuratorFramework;
import org.apache.curator.framework.CuratorFrameworkFactory;
import org.apache.curator.retry.ExponentialBackoffRetry;
import org.apache.zookeeper.CreateMode;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
/**
* 基于zk的永久型自增節(jié)點PERSISTENT_SEQUENTIAL實現
* 每次生成節(jié)點后會使用線程池執(zhí)行刪除節(jié)點任務
* Created by wangwanbin on 2017/9/5.
*/
public class ZKIncreaseSequenceHandler extends SequenceHandler implements PooledObjectFactory {
? ?protected static final Logger LOGGER = LoggerFactory.getLogger(ZKCachedSequenceHandler.class);
? ?private static ZKIncreaseSequenceHandler instance = new ZKIncreaseSequenceHandler();
? ?private static ExecutorService fixedThreadPool = Executors.newFixedThreadPool(1);
? ?private GenericObjectPool genericObjectPool;
? ?private Queue preNodes = new ConcurrentLinkedQueue<>();
? ?private static String ZK_ADDRESS = ""; //192.168.0.65
? ?private static String PATH = "";// ?/sequence/p2p
? ?private static String SEQ = "";//seq;
? ?/**
? ? * 私有化構造方法,單例模式
? ? */
? ?private ZKIncreaseSequenceHandler() {
? ? ? ?GenericObjectPoolConfig config = new GenericObjectPoolConfig();
? ? ? ?config.setMaxTotal(4);
? ? ? ?genericObjectPool = new GenericObjectPool(this, config);
? ?}
? ?/**
? ? * 獲取sequence工具對象的唯一方法
? ? *
? ? * @return
? ? */
? ?public static ZKIncreaseSequenceHandler getInstance(String zkAddress, String path, String seq) {
? ? ? ?ZK_ADDRESS = zkAddress;
? ? ? ?PATH = path;
? ? ? ?SEQ = seq;
? ? ? ?return instance;
? ?}
? ?@Override
? ?public long nextId(final SequenceEnum sequenceEnum) {
? ? ? ?String result = createNode(sequenceEnum.getCode());
? ? ? ?final String idstr = result.substring((PATH + "/" + sequenceEnum.getCode() + "/" + SEQ).length());
? ? ? ?final long id = Long.parseLong(idstr);
? ? ? ?preNodes.add(id);
? ? ? ?//刪除上一個節(jié)點
? ? ? ?fixedThreadPool.execute(new Runnable() {
? ? ? ? ? ?@Override
? ? ? ? ? ?public void run() {
? ? ? ? ? ? ? ?Iterator iterator = preNodes.iterator();
? ? ? ? ? ? ? ?if (iterator.hasNext()) {
? ? ? ? ? ? ? ? ? ?long preNode = iterator.next();
? ? ? ? ? ? ? ? ? ?if (preNode < id) {
? ? ? ? ? ? ? ? ? ? ? ?final String format = "%0" + idstr.length() + "d";
? ? ? ? ? ? ? ? ? ? ? ?String preIdstr = String.format(format, preNode);
? ? ? ? ? ? ? ? ? ? ? ?final String prePath = PATH + "/" + sequenceEnum.getCode() + "/" + SEQ + preIdstr;
? ? ? ? ? ? ? ? ? ? ? ?CuratorFramework client = null;
? ? ? ? ? ? ? ? ? ? ? ?try {
? ? ? ? ? ? ? ? ? ? ? ? ? ?client = (CuratorFramework) genericObjectPool.borrowObject();
? ? ? ? ? ? ? ? ? ? ? ? ? ?client.delete().forPath(prePath);
? ? ? ? ? ? ? ? ? ? ? ? ? ?preNodes.remove(preNode);
? ? ? ? ? ? ? ? ? ? ? ?} catch (Exception e) {
? ? ? ? ? ? ? ? ? ? ? ? ? ?LOGGER.error("delete preNode error", e);
? ? ? ? ? ? ? ? ? ? ? ?} finally {
? ? ? ? ? ? ? ? ? ? ? ? ? ?if (client != null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?genericObjectPool.returnObject(client);
? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ?});
? ? ? ?return id;
? ?}
? ?private String createNode(String prefixName) {
? ? ? ?CuratorFramework client = null;
? ? ? ?try {
? ? ? ? ? ?client = (CuratorFramework) genericObjectPool.borrowObject();
? ? ? ? ? ?String result = client.create().creatingParentsIfNeeded().withMode(CreateMode.PERSISTENT_SEQUENTIAL)
? ? ? ? ? ? ? ? ? ?.forPath(PATH + "/" + prefixName + "/" + SEQ, String.valueOf(0).getBytes());
? ? ? ? ? ?return result;
? ? ? ?} catch (Exception e) {
? ? ? ? ? ?throw new RuntimeException("create zookeeper node error", e);
? ? ? ?} finally {
? ? ? ? ? ?if (client != null)
? ? ? ? ? ? ? ?genericObjectPool.returnObject(client);
? ? ? ?}
? ?}
? ?public static void main(String[] args) {
? ? ? ?ExecutorService executorService = Executors.newFixedThreadPool(1);
? ? ? ?long startTime = System.currentTimeMillis(); ? //獲取開始時間
? ? ? ?final ZKIncreaseSequenceHandler sequenceHandler = ZKIncreaseSequenceHandler.getInstance("192.168.0.65", "/sequence/p2p", "seq");
? ? ? ?int count = 10;
? ? ? ?final CountDownLatch cd = new CountDownLatch(count);
? ? ? ?for (int i = 0; i < count; i++) {
? ? ? ? ? ?executorService.execute(new Runnable() {
? ? ? ? ? ? ? ?public void run() {
? ? ? ? ? ? ? ? ? ?System.out.printf("線程 %s %d \n", Thread.currentThread().getId(), sequenceHandler.nextId(SequenceEnum.ORDER));
? ? ? ? ? ? ? ? ? ?cd.countDown();
? ? ? ? ? ? ? ?}
? ? ? ? ? ?});
? ? ? ?}
? ? ? ?try {
? ? ? ? ? ?cd.await();
? ? ? ?} catch (InterruptedException e) {
? ? ? ? ? ?LOGGER.error("Interrupted thread",e);
? ? ? ? ? ?Thread.currentThread().interrupt();
? ? ? ?}
? ? ? ?long endTime = System.currentTimeMillis(); //獲取結束時間
? ? ? System.out.println("程序運行時間:" + (endTime - startTime) + "ms");
? ?}
? ?@Override
? ?public PooledObject makeObject() throws Exception {
? ? ? ?CuratorFramework client = CuratorFrameworkFactory.newClient(ZK_ADDRESS, new ExponentialBackoffRetry(1000, 3));
? ? ? ?client.start();
? ? ? ?return new DefaultPooledObject<>(client);
? ?}
? ?@Override
? ?public void destroyObject(PooledObject p) throws Exception {
? ?}
? ?@Override
? ?public boolean validateObject(PooledObject p) {
? ? ? ?return false;
? ?}
? ?@Override
? ?public void activateObject(PooledObject p) throws Exception {
? ?}
? ?@Override
? ?public void passivateObject(PooledObject p) throws Exception {
? ?}
}
測試結果如下,生成10000個id消耗=9443ms(兩個線程耗時較長者), ?平均每個id消耗0.9ms。
這還只是單zk連接的情況下,如果使用連接池來維護多個zk的連接,效率將成倍的提升。
四、結語
分布式ID生成器的實現有很多種。目前各方案也都各有特點。我們可以根據業(yè)務的具體要求,選擇實現合適的方案。
總結
以上是生活随笔為你收集整理的6位顺序号生成_分布式id生成策略,我和面试官扯了一个半小时的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 直接点oracle表编辑器,DbForg
- 下一篇: java手动线程池使用_Java手动配置