一.?致性Hash算法
1.平常的hash算法在加入一個節(jié)點后，原來存儲在各個節(jié)點的數(shù)據(jù)都會發(fā)生變更
2.因此采用一致性hash算法：
? 2.1構造一個環(huán)，讓幾個節(jié)點均勻分布在環(huán)上，讓key值也分布在環(huán)上，將數(shù)據(jù)存儲在按順時針方向離key值最近的節(jié)點上，這樣當有新節(jié)點加入時，只會影響到離新節(jié)點最近的老節(jié)點（假設為A）的數(shù)據(jù)。
? 2.2這樣會使得新加入的節(jié)點和老節(jié)點平分原來老節(jié)點A的數(shù)據(jù)，等于這兩個節(jié)點只分擔了其他老節(jié)點一半的數(shù)據(jù)，利用率只有50%
3.所以需要再加一層虛擬層
? ? 假設有A,B,C三個節(jié)點，對每個節(jié)點虛擬為3個節(jié)點，比如A變?yōu)锳1,A2,A3三個節(jié)點均勻分布在環(huán)上，當有第四個節(jié)點D加入時，虛擬為D1,D2,D3，那么D1,D2,D3這三個節(jié)點會存儲本該存儲在A1,B1,C3節(jié)點的數(shù)據(jù)，達到新增一個節(jié)點均勻平分三個節(jié)點的數(shù)據(jù)。
??
二.集群時鐘同步問題
集群的各個服務器時間必須一致，不然會有嚴重后果。
策略：
1.所有服務器向國家時間中心注冊。
2.某個服務器向國家時間中心注冊，其他服務器已它為準。
三.分布式ID解決?案
ID是數(shù)據(jù)的唯一標識，傳統(tǒng)的做法是利用UUID和數(shù)據(jù)庫的自增ID，在互聯(lián)網企業(yè)中，大部分公司使用的都是Mysql，并且因為需要事務支持，所以通常會使用Innodb存儲引擎，UUID太長以及無序，所以并不適合在Innodb中來作為主鍵，自增ID比較合適，但是隨著公司的業(yè)務發(fā)展，數(shù)據(jù)量將越來越大，需要對數(shù)據(jù)進行分表，而分表后，每個表中的數(shù)據(jù)都會按自己的節(jié)奏進行自增，很有可能出現(xiàn)ID沖突。這時就需要一個單獨的機制來負責生成唯一ID，生成出來的ID也可以叫做分布式ID，或全局ID
UUID
UUID(Universally Unique Identifier)的標準型式包含32個16進制數(shù)字，以連字號分為五段，形式為8-4-4-4-12的36個字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前為止業(yè)界一共有5種方式生成UUID，詳情見IETF發(fā)布的UUID規(guī)范?A Universally Unique IDentifier (UUID) URN Namespace。
優(yōu)點：
性能非常高：本地生成，沒有網絡消耗。
缺點：
不易于存儲：UUID太長，16字節(jié)128位，通常以36長度的字符串表示，很多場景不適用。innodb一頁16kb，索引越大，一頁存儲的數(shù)據(jù)就越少，從磁盤io次數(shù)就越多，而且uuid無序，插入索引的時候可能引起頁的分裂。更重要的是，UUID 不具有有序性，會導致 B+ 樹索引在寫的時候有過多的隨機寫操作（連續(xù)的 ID 可以產生部分順序寫），還有，由于在寫的時候不能產生有順序的 append 操作，而需要進行 insert 操作，將會讀取整個 B+ 樹節(jié)點到內存，在插入這條記錄后會將整個節(jié)點寫回磁盤，這種操作在記錄占用空間比較大的情況下，性能下降明顯。
信息不安全：基于MAC地址生成UUID的算法可能會造成MAC地址泄露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
ID作為主鍵時在特定的環(huán)境會存在一些問題，比如做DB主鍵的場景下，UUID就非常不適用：
① MySQL官方有明確的建議主鍵要盡量越短越好[4]，36個字符長度的UUID不符合要求。
All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.*** If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key***.
② 對MySQL索引不利：如果作為數(shù)據(jù)庫主鍵，在InnoDB引擎下，UUID的無序性可能會引起數(shù)據(jù)位置頻繁變動，嚴重影響性能。
數(shù)據(jù)庫自增ID
第一種方案仍然還是基于數(shù)據(jù)庫的自增ID，需要單獨使用一個數(shù)據(jù)庫實例，在這個實例中新建一個單獨的表：
表結構如下：
CREATE DATABASE `SEQID`;
CREATE TABLE SEQID.SEQUENCE_ID (
? ? id bigint(20) unsigned NOT NULL auto_increment,
? ? stub char(10) NOT NULL default '',
? ? PRIMARY KEY (id),
? ? UNIQUE KEY stub (stub)
) ENGINE=MyISAM;
可以使用下面的語句生成并獲取到一個自增ID
begin;
replace into SEQUENCE_ID (stub) VALUES ('anyword');
select last_insert_id();
commit;
stub字段在這里并沒有什么特殊的意義，只是為了方便的去插入數(shù)據(jù)，只有能插入數(shù)據(jù)才能產生自增id。而對于插入我們用的是replace，replace會先看是否存在stub指定值一樣的數(shù)據(jù)，如果存在則先delete再insert，如果不存在則直接insert。
這種生成分布式ID的機制，需要一個單獨的Mysql實例，雖然可行，但是基于性能與可靠性來考慮的話都不夠，業(yè)務系統(tǒng)每次需要一個ID時，都需要請求數(shù)據(jù)庫獲取，性能低，并且如果此數(shù)據(jù)庫實例下線了，那么將影響所有的業(yè)務系統(tǒng)。
為了解決數(shù)據(jù)庫可靠性問題，我們可以使用第二種分布式ID生成方案。
數(shù)據(jù)庫多主模式
如果我們兩個數(shù)據(jù)庫組成一個主從模式集群，正常情況下可以解決數(shù)據(jù)庫可靠性問題，但是如果主庫掛掉后，數(shù)據(jù)沒有及時同步到從庫，這個時候會出現(xiàn)ID重復的現(xiàn)象。我們可以使用雙主模式集群，也就是兩個Mysql實例都能單獨的生產自增ID，這樣能夠提高效率，但是如果不經過其他改造的話，這兩個Mysql實例很可能會生成同樣的ID。需要單獨給每個Mysql實例配置不同的起始值和自增步長。
第一臺Mysql實例配置：
set @@auto_increment_offset = 1;? ? -- 起始值
set @@auto_increment_increment = 2;? -- 步長
第二臺Mysql實例配置：
set @@auto_increment_offset = 2;? ? -- 起始值
set @@auto_increment_increment = 2;? -- 步長
經過上面的配置后，這兩個Mysql實例生成的id序列如下：
mysql1,起始值為1,步長為2,ID生成的序列為：1,3,5,7,9,...
mysql2,起始值為2,步長為2,ID生成的序列為：2,4,6,8,10,...
對于這種生成分布式ID的方案，需要單獨新增一個生成分布式ID應用，比如DistributIdService，該應用提供一個接口供業(yè)務應用獲取ID，業(yè)務應用需要一個ID時，通過rpc的方式請求DistributIdService，DistributIdService隨機去上面的兩個Mysql實例中去獲取ID。
實行這種方案后，就算其中某一臺Mysql實例下線了，也不會影響DistributIdService，DistributIdService仍然可以利用另外一臺Mysql來生成ID。
但是這種方案的擴展性不太好，如果兩臺Mysql實例不夠用，需要新增Mysql實例來提高性能時，這時就會比較麻煩。
現(xiàn)在如果要新增一個實例mysql3，要怎么操作呢？
第一，mysql1、mysql2的步長肯定都要修改為3，而且只能是人工去修改，這是需要時間的。
第二，因為mysql1和mysql2是不停在自增的，對于mysql3的起始值我們可能要定得大一點，以給充分的時間去修改mysql1，mysql2的步長。
第三，在修改步長的時候很可能會出現(xiàn)重復ID，要解決這個問題，可能需要停機才行。
為了解決上面的問題，以及能夠進一步提高DistributIdService的性能，如果使用第三種生成分布式ID機制。
號段模式
我們可以使用號段的方式來獲取自增ID，號段可以理解成批量獲取，比如DistributIdService從數(shù)據(jù)庫獲取ID時，如果能批量獲取多個ID并緩存在本地的話，那樣將大大提供業(yè)務應用獲取ID的效率。
比如DistributIdService每次從數(shù)據(jù)庫獲取ID時，就獲取一個號段，比如(1,1000]，這個范圍表示了1000個ID，業(yè)務應用在請求DistributIdService提供ID時，DistributIdService只需要在本地從1開始自增并返回即可，而不需要每次都請求數(shù)據(jù)庫，一直到本地自增到1000時，也就是當前號段已經被用完時，才去數(shù)據(jù)庫重新獲取下一號段。
所以，我們需要對數(shù)據(jù)庫表進行改動，如下：
CREATE TABLE id_generator (
? id int(10) NOT NULL,
? current_max_id bigint(20) NOT NULL COMMENT '當前最大id',
? increment_step int(10) NOT NULL COMMENT '號段的長度',
? PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
這個數(shù)據(jù)庫表用來記錄自增步長以及當前自增ID的最大值（也就是當前已經被申請的號段的最后一個值），因為自增邏輯被移到DistributIdService中去了，所以數(shù)據(jù)庫不需要這部分邏輯了。
這種方案不再強依賴數(shù)據(jù)庫，就算數(shù)據(jù)庫不可用，那么DistributIdService也能繼續(xù)支撐一段時間。但是如果DistributIdService重啟，會丟失一段ID，導致ID空洞。
為了提高DistributIdService的高可用，需要做一個集群，業(yè)務在請求DistributIdService集群獲取ID時，會隨機的選擇某一個DistributIdService節(jié)點進行獲取，對每一個DistributIdService節(jié)點來說，數(shù)據(jù)庫連接的是同一個數(shù)據(jù)庫，那么可能會產生多個DistributIdService節(jié)點同時請求數(shù)據(jù)庫獲取號段，那么這個時候需要利用樂觀鎖來進行控制，比如在數(shù)據(jù)庫表中增加一個version字段，在獲取號段時使用如下SQL：
update id_generator set current_max_id=#{newMaxId},
version=version+1 where version = #{version}
因為newMaxId是DistributIdService中根據(jù)oldMaxId+步長算出來的，只要上面的update更新成功了就表示號段獲取成功了。
為了提供數(shù)據(jù)庫層的高可用，需要對數(shù)據(jù)庫使用多主模式進行部署，對于每個數(shù)據(jù)庫來說要保證生成的號段不重復，這就需要利用最開始的思路，再在剛剛的數(shù)據(jù)庫表中增加起始值和步長，比如如果現(xiàn)在是兩臺Mysql，那么
mysql1將生成號段（1,1001]，自增的時候序列為1，3，4，5，7....
mysql1將生成號段（2,1002]，自增的時候序列為2，4，6，8，10...
雪花算法
snowflake是twitter開源的分布式ID生成算法，是一種算法，所以它和上面的三種生成分布式ID機制不太一樣，它不依賴數(shù)據(jù)庫。
核心思想是：分布式ID固定是一個long型的數(shù)字，一個long型占8個字節(jié)，也就是64個bit。
第一個bit位是標識部分，在java中由于long的最高位是符號位，正數(shù)是0，負數(shù)是1，一般生成的ID為正數(shù)，所以固定為0。
時間戳部分占41bit，這個是毫秒級的時間，一般實現(xiàn)上不會存儲當前的時間戳，而是時間戳的差值（當前時間-固定的開始時間），這樣可以使產生的ID從更小值開始；41位的時間戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
工作機器id占10bit，這里比較靈活，比如，可以使用前5位作為數(shù)據(jù)中心機房標識，后5位作為單機房機器標識，可以部署1024個節(jié)點。
序列號部分占12bit，支持同一毫秒內同一個節(jié)點可以生成4096個ID
根據(jù)這個算法的邏輯，只需要將這個算法用Java語言實現(xiàn)出來，封裝為一個工具方法，那么各個業(yè)務應用可以直接使用該工具方法來獲取分布式ID，只需保證每個業(yè)務應用有自己的工作機器id即可，而不需要單獨去搭建一個獲取分布式ID的應用。
優(yōu)點：
毫秒數(shù)在高位，自增序列在低位，整個ID都是趨勢遞增的。
不依賴數(shù)據(jù)庫等第三方系統(tǒng)，以服務的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的。
可以根據(jù)自身業(yè)務特性分配bit位，非常靈活。
缺點：
強依賴機器時鐘，如果機器上時鐘回撥，會導致發(fā)號重復或者服務會處于不可用狀態(tài)。
在大廠里，其實并沒有直接使用snowflake，而是進行了改造，因為snowflake算法中最難實踐的就是工作機器id，原始的snowflake算法需要人工去為每臺機器去指定一個機器id，并配置在某個地方從而讓snowflake從此處獲取機器id。
但是在大廠里，機器是很多的，人力成本太大且容易出錯，所以大廠對snowflake進行了改造。
百度（uid-generator）
uid-generator使用的就是snowflake，只是在生產機器id，也叫做workId時有所不同。
uid-generator中的workId是由uid-generator自動生成的，并且考慮到了應用部署在docker上的情況，在uid-generator中用戶可以自己去定義workId的生成策略，默認提供的策略是：應用啟動時由數(shù)據(jù)庫分配。說的簡單一點就是：應用在啟動時會往數(shù)據(jù)庫表(uid-generator需要新增一個WORKER_NODE表)中去插入一條數(shù)據(jù)，數(shù)據(jù)插入成功后返回的該數(shù)據(jù)對應的自增唯一id就是該機器的workId，而數(shù)據(jù)由host，port組成。
對于uid-generator中的workId，占用了22個bit位，時間占用了28個bit位，序列化占用了13個bit位，需要注意的是，和原始的snowflake不太一樣，時間的單位是秒，而不是毫秒，workId也不一樣，同一個應用每重啟一次就會消費一個workId。
美團（Leaf）
美團的Leaf也是一個分布式ID生成框架。它非常全面，即支持號段模式，也支持snowflake模式。號段模式這里就不介紹了，和上面的分析類似。
Leaf中的snowflake模式和原始snowflake算法的不同點，也主要在workId的生成，Leaf中workId是基于ZooKeeper的順序Id來生成的，每個應用在使用Leaf-snowflake時，在啟動時都會都在Zookeeper中生成一個順序Id，相當于一臺機器對應一個順序節(jié)點，也就是一個workId。
總結
總得來說，上面兩種都是自動生成workId，以讓系統(tǒng)更加穩(wěn)定以及減少人工成功。
Redis
和利用Mysql自增ID類似，可以利用Redis中的incr命令來實現(xiàn)原子性的自增與返回，比如：
127.0.0.1:6379> set seq_id 1? ? // 初始化自增ID為1
OK
127.0.0.1:6379> incr seq_id? ? ? // 增加1，并返回
(integer) 2
127.0.0.1:6379> incr seq_id? ? ? // 增加1，并返回
(integer) 3
使用redis的效率是非常高的，但是要考慮持久化的問題。Redis支持RDB和AOF兩種持久化的方式。
RDB持久化相當于定時打一個快照進行持久化，如果打完快照后，連續(xù)自增了幾次，還沒來得及做下一次快照持久化，這個時候Redis掛掉了，重啟Redis后會出現(xiàn)ID重復。
AOF持久化相當于對每條寫命令進行持久化，如果Redis掛掉了，不會出現(xiàn)ID重復的現(xiàn)象，但是會由于incr命令過得，導致重啟恢復數(shù)據(jù)時間過長。
