分布式架構下，唯一序列号生成是我們在設計一個系統，尤其是資料庫使用分庫分表的時候常常會遇見的問題。當分成若幹個sharding表後，如何能夠快速拿到一個唯一序列号，是經常遇到的問題。
特征需求
1. 全局唯一
2. 支援高并發
3. 能夠展現一定屬性
4. 高可靠，容錯單點故障
5. 高性能
常用方案
生成ID的方法有很多，來适應不同的場景、需求以及性能要求。
常見方式有：
利用資料庫遞增，全資料庫唯一
優點：明顯，可控。
缺點：單庫單表，資料庫壓力大。
UUID
生成的是length=32的16進制格式的字元串，如果回退為byte數組共16個byte元素，即UUID是一個128bit長的數字，一般用16進制表示。
優點：對資料庫壓力減輕
缺點：排序不靈活
此外還有UUID的變種，增加一個時間拼接，但是會造成id非常長。
Cassandra
把存儲系統從MySQL遷移到Cassandra的過程中由于Cassandra沒有順序ID生成機制，于是自己開發了一套全局唯一ID生成服務：Snowflake。
1. 41位的時間序列（精确到毫秒，41位的長度可以使用69年）
2. 10位的機器辨別（10位的長度最多支援部署1024個節點）
3. 12位的計數順序号（12位的計數順序号支援每個節點每毫秒産生4096個ID序号） ***位是符号位，始終為0。
優點：高性能，低延遲；獨立的應用；按時間有序。
缺點：需要獨立的開發和部署。
Redis生成ID
當使用資料庫來生成ID性能不夠要求的時候，我們可以嘗試使用Redis來生成ID。這主要依賴于Redis是單線程的，是以也可以用生成全局唯一的ID。可以用Redis的原子操作INCR和INCRBY來實作。
可以使用Redis叢集來擷取更高的吞吐量。假如一個叢集中有5台Redis。可以初始化每台Redis的值分别是1,2,3,4,5，然後步長都是5。各個Redis生成的ID為：
A：1,6,11,16,21
B：2,7,12,17,22
C：3,8,13,18,23
D：4,9,14,19,24
E：5,10,15,20,25
比較适合使用Redis來生成每天從0開始的流水号。比如訂單号=日期+當日自增長号。可以每天在Redis中生成一個Key，使用INCR進行累加。
優點：
不依賴于資料庫，靈活友善，且性能優于資料庫。
數字ID天然排序，對分頁或者需要排序的結果很有幫助。
使用Redis叢集也可以防止單點故障的問題。
缺點：
如果系統中沒有Redis，還需要引入新的元件，增加系統複雜度。
需要編碼和配置的工作量比較大，多環境運維很麻煩，
在開始時，程式執行個體負載到哪個redis執行個體一旦确定好，未來很難做修改。
Flicker的解決方案
因為MySQL本身支援auto_increment操作，很自然地，我們會想到借助這個特性來實作這個功能。
Flicker在解決全局ID生成方案裡就采用了MySQL自增長ID的機制（auto_increment +replace into + MyISAM）。
其它方案
還有其他一些方案，比如京東淘寶等電商的訂單号生成。因為訂單号和使用者id在業務上的差別，訂單号盡可能要多些備援的業務資訊，比如：
滴滴：時間+起點編号+車牌号
淘寶訂單：時間戳+使用者ID
其他電商：時間戳+下單管道+使用者ID，有的會加上訂單***個商品的ID。
snowflake算法
snowflake是Twitter開源的分布式ID生成算法，結果是一個long型的ID。其核心思想是：使用41bit作為毫秒數，10bit作為機器的ID（5個bit是資料中心，5個bit的機器ID），12bit作為毫秒内的流水号（意味着每個節點在每毫秒可以産生 4096 個 ID），最後還有一個符号位，永遠是0。
SnowFlake算法生成id的結果是一個64bit大小的整數，它的結構如下圖：
- 1位，不用。二進制中最高位為1的都是負數，但是我們生成的id一般都使用整數，是以這個最高位固定是0
- 41位，用來記錄時間戳（毫秒）。
- 41位可以表示$2^{41}-1$個數字，
- 如果隻用來表示正整數（計算機中正數包含0），可以表示的數值範圍是：0 至 $2^{41}-1$，減1是因為可表示的數值範圍是從0開始算的，而不是1。
- 也就是說41位可以表示$2^{41}-1$個毫秒的值，轉化成機關年則是$(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年
- 10位，用來記錄工作機器id。
- 可以部署在$2^{10} = 1024$個節點，包括5位datacenterId和5位workerId
- 5位（bit）可以表示的最大正整數是$2^{5}-1 = 31$，即可以用0、1、2、3、....31這32個數字，來表示不同的datecenterId或workerId
- 12位，序列号，用來記錄同毫秒内産生的不同id。
- 12位（bit）可以表示的最大正整數是$2^{12}-1 = 4095$，即可以用0、1、2、3、....4094這4095個數字，來表示同一機器同一時間截（毫秒)内産生的4095個ID序号
由于在Java中64bit的整數是long類型，是以在Java中SnowFlake算法生成的id就是long來存儲的。
SnowFlake可以保證：
- 所有生成的id按時間趨勢遞增
- 整個分布式系統内不會産生重複id（因為有datacenterId和workerId來做區分）
該算法實作基本就是二進制操作，單機每秒内理論上最多可以生成1000*(2^12)，也就是409.6萬個ID，java實作代碼基本上就是類似這樣的
/**
* 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===========================================
/** 開始時間截 (2015-01-01) */
private final long twepoch = 1420041600000L;
/** 機器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 < 1000; i++) {
long id = idWorker.nextId();
System.out.println(Long.toBinaryString(id));
System.out.println(id);
}
}
} 雙序列全局比對及算法
Needleman-Wunsch 算法：動态規劃法
輸入值：兩條序列、替換記分矩陣以确定不同字母間的相似度得分，以及空位罰分
雙序列局部比對算法
局部比對的計算公式在全局比對的基礎上增加了第四個元素“0”。得分矩陣初始值仍是0，但第一行和第一列與全局比對不同，全是0。
一緻度和相似度
兩條長度不同的序列做全局比對，然後計算全局比對中一緻字元的個數和相似字元的個數，再除以全局比對的長度，就可以得到它們的一緻度和相似度了。比如下面這兩條序列：
首先做出它們的全局比對，比對中一緻字元的個數是 4 個，全局比對長度 6，一緻度=67%。相似字元個數 1，相似度就是(4+1)/6=83%。
把長度相同的兩個序列計算一緻度和相似度的方法重新規範一下。盡管長度相同，但是做出的全局比對的長度并不一定等于序列的長度，比如下面這兩條序列：
上下各加入一個空位，全局比對的長度就不等于序列的長度了。是以不管兩條序列長度是否相同，都要先對它們做全局比對。讓兩條序列先以最優的方式比對起來，再從全局比對中數出一緻字元和相似字元的個數，除以全局比對的長度，來得到它們的一緻度和相似度。
EMBL全局雙序列比對工具
目前，使用率最高的是 EMBL 網站的雙序列比對工具。輸入值非常簡單，把要比較的兩條蛋白質序列貼在輸入框裡或者上傳。如果想要進一步設定比對的參數，可以點 More options。從這裡可以選擇使用哪種替換記分矩陣。按照之前講過的原則，選擇 PAM 矩陣或 BLOSUM 矩陣。如果實在不知道選哪個矩陣，就閉着眼睛選 BLOSUME62，下拉菜單裡預設選的就是BLOSUM62。