黃振業(yè)

摘? 要：Paxos算法是被廣泛使用的分布式一致算法，為了保障Paxos算法的正確性和高性能，需要配合使用高性能、高可用、全局唯一自增序列號(hào)的生成系統(tǒng)。為此，該文提出了一種全局唯一自增ID的生成方法，該方法以物理機(jī)器時(shí)鐘頻率不會(huì)產(chǎn)生大波動(dòng)的特性為前提，并在實(shí)現(xiàn)上采用多種高性能、高可用技術(shù)。最后構(gòu)建了測(cè)試環(huán)境，通過(guò)實(shí)驗(yàn)證明了該方案在正常態(tài)和異常態(tài)時(shí)，都能正確產(chǎn)生全局唯一自增ID，同時(shí)整個(gè)系統(tǒng)也達(dá)到了預(yù)期的高性能要求。

關(guān)鍵詞：一致性? 唯一自增ID生成? 高性能? 高可用

中圖分類(lèi)號(hào)：TP301? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-3791（2021）03（c）-0001-06

Generation Method of Global Unique Auto Increment ID Generation for Paxos Algorithm

HUANG Zhenye

（School of Information Technology， Zhejiang Financial College， Hangzhou， Zhejiang Province， 310018 China）

Abstract： Paxos is a protocol for solving consensus in a distribution system. Paxos can work in a network with fail-ures， and all processors in the network could be unreliable. While Paxos protocol has a precondition step： generat-ing the unique version numbers for Paxos protocol. This paper proposes a method to generate the unique version numbers for Paxos protocol. And this method should be high available and should have high performance. Aiming to this object， the method utilizes the stability of machine timestamp， and uses high available techniques on imple-mentation. Finally， a test environment is constructed. Experiments show that the method can generate the unique version numbers correctly in normal and abnormal conditions， and the whole system also achieves the expected high performance requirements.

Key Words： Consensus; Unique auto increment ID generation; High performance; High available

目前，有很多分布式一致性算法來(lái)解決分布式系統(tǒng)的一致性問(wèn)題，而Paxos算法是其中重要的一種算法，它已經(jīng)被應(yīng)用到多種系統(tǒng)中[1]。Paxos算法又分為Basic Paxos算法和Multi-Paxos算法[2]。在這兩種算法之上又有一些改進(jìn)的算法[3-6]，但這些算法都需要有一個(gè)機(jī)制來(lái)生成全局唯一自增ID。如果不能保障生成全局唯一自增的ID，就不能保障Paxos算法的正確性。

該文提出了一種新的全局唯一自增ID的生成方法，同時(shí)會(huì)涉及工程上實(shí)現(xiàn)的細(xì)節(jié)。首先，簡(jiǎn)單介紹Paxos算法，其中著重說(shuō)明全局唯一自增ID的生成的必要性;其次，列舉其他一些常用的全局唯一自增的ID的生成方式以及它們的不足;最后，重點(diǎn)介紹新的全局唯一自增ID的生成方法及實(shí)驗(yàn)結(jié)果。

1? Basic Paxos

Paxos算法分為Basic Paxos算法和Multi-Paxos算法，而全局唯一自增ID的生成方法對(duì)兩者并無(wú)區(qū)別，該文就以Basic Paxos算法作為例子來(lái)說(shuō)明Paxos算法。

Paxos算法中的進(jìn)程有3種身份：proposer、acceptor、learner。Paxos算法又分為兩個(gè)階段：準(zhǔn)備階段與批準(zhǔn)階段[2，7]。

1.1 準(zhǔn)備階段

proposer選擇一個(gè)全局唯一遞增的ID，n作為本輪的版本號(hào)。群發(fā)版本號(hào)為n的prepare請(qǐng)求給一個(gè)acceptor的多數(shù)派，即超過(guò)半數(shù)的acceptor。

每個(gè)acceptor會(huì)存儲(chǔ)曾經(jīng)批準(zhǔn)過(guò)提案中最大版本號(hào)的提案，其中w+max_version，w為提案內(nèi)容，max_version為最大的提案版本，具體請(qǐng)參考批準(zhǔn)階段的詳細(xì)敘述。

每當(dāng)acceptor接收到一個(gè)版本號(hào)為n的prepare請(qǐng)求。當(dāng)n>max_version時(shí)，那么把最大版本號(hào)的提案返回給proposer，如果之前沒(méi)有批準(zhǔn)過(guò)任何提案，則返回“空”給proposer;當(dāng)n<=max_version時(shí)，那么proposer不對(duì)這個(gè)版本號(hào)為n的prepare請(qǐng)求做出響應(yīng)，并承諾今后不會(huì)批準(zhǔn)版本號(hào)小于n的任何提案，即版本號(hào)大于等于n的提案才會(huì)被批準(zhǔn)。

1.2 批準(zhǔn)階段

proposer從acceptor的多數(shù)派獲得prepare請(qǐng)求的響應(yīng)，并從這些響應(yīng)中挑出版本號(hào)最大的提案內(nèi)容，假設(shè)該內(nèi)容為w。proposer群發(fā)一個(gè)批準(zhǔn)請(qǐng)求（版本號(hào)為n，內(nèi)容為w）給一個(gè)acceptor的多數(shù)派。如果proposer獲得的所有響應(yīng)都為空，那么群發(fā)的提案可以是任何內(nèi)容。

每個(gè)acceptor接收到一個(gè)批準(zhǔn)請(qǐng)求（版本號(hào)為n，內(nèi)容為w），如果它不違反之前的承諾，即n>=承諾過(guò)的最大版本號(hào)，那么該提案才會(huì)被批準(zhǔn)，并返回批準(zhǔn)響應(yīng)給proposer;否則，對(duì)這個(gè)批準(zhǔn)請(qǐng)求不做回應(yīng)。如果最后某個(gè)proposer沒(méi)有從一個(gè)acceptor的多數(shù)派獲得prepare的響應(yīng)，這個(gè)proposer需要重新生成一個(gè)全局唯一遞增的版本號(hào)，重新從準(zhǔn)備階段開(kāi)始啟動(dòng)算法。

Paxos算法本身的證明可以參閱參考文獻(xiàn)[7]。其中整個(gè)算法中的proposer每次必須生成一個(gè)全局唯一遞增的ID作為該輪算法的版本號(hào)。此版本號(hào)必須滿(mǎn)足兩個(gè)條件：全局唯一和自增。全局唯一就是兩個(gè)獨(dú)立的proposer不能生成相同的版本號(hào)，而自增則是每個(gè)proposer每次生成的版本號(hào)必須是遞增的。

2? 現(xiàn)有方案的缺陷

生成的全局的唯一自增ID要滿(mǎn)足以下幾點(diǎn)需求。

（1）保證生成的ID全局唯一，且每個(gè)進(jìn)程生成的ID自增。

（2）生成的ID最好不大于64位。

（3）生成ID的速度有要求。例如：在一個(gè)高吞吐量的場(chǎng)景中，需要每秒生成幾萬(wàn)個(gè)ID。

（4）整個(gè)服務(wù)沒(méi)有單點(diǎn)。

如果沒(méi)有以上的幾點(diǎn)需求，那么可以有很多簡(jiǎn)單的實(shí)現(xiàn)方案。

2.1 利用數(shù)據(jù)庫(kù)的自增ID方案

利用數(shù)據(jù)庫(kù)的自增ID的方法實(shí)現(xiàn)簡(jiǎn)單，可以保證全局唯一，但是它依賴(lài)中間節(jié)點(diǎn)，而且每個(gè)節(jié)點(diǎn)都需要訪問(wèn)一次數(shù)據(jù)庫(kù)才能得到ID值，這樣就出現(xiàn)了整個(gè)系統(tǒng)的單點(diǎn)問(wèn)題。同時(shí)，由于數(shù)據(jù)庫(kù)本身的性能限制，也不能滿(mǎn)足高吞吐量的需求。

2.2 利用數(shù)據(jù)庫(kù)的其他變種方案

利用多個(gè)寫(xiě)庫(kù)來(lái)解決單數(shù)據(jù)庫(kù)自增ID方案的單點(diǎn)問(wèn)題：使用多個(gè)寫(xiě)庫(kù)，每個(gè)寫(xiě)庫(kù)的自增初始值不同，步長(zhǎng)值不一樣。假設(shè)利用3個(gè)寫(xiě)庫(kù)：A、B、C。其中A庫(kù)的ID序列為0、3、6、9，B庫(kù)為1、4、7、10，C庫(kù)為2、5、8，11。多寫(xiě)庫(kù)的方案避免的單點(diǎn)問(wèn)題，但性能還是會(huì)受到數(shù)據(jù)庫(kù)性能的限制，不滿(mǎn)足高性能需求。

另外，還有使用數(shù)據(jù)庫(kù)MyISAM+Replace Intro模式的方案。這個(gè)方案由Filcker提出，采用了MySQL自增ID的方法。數(shù)據(jù)庫(kù)中只存放單條記錄，每次利用replace into，然后通過(guò)select LAST_INSERT_ID獲取最后一個(gè)插入的ID值。該方案可以擴(kuò)展為多臺(tái)數(shù)據(jù)庫(kù)，也可以使用不同的初始值和步長(zhǎng)值增加可用性，但是同樣不滿(mǎn)足高性能的要求。

2.3 利用中心服務(wù)器生成ID方案

利用一個(gè)中心服務(wù)器來(lái)統(tǒng)一生成unique ID，但是這種方案可能存在單點(diǎn)問(wèn)題。例如：利用開(kāi)源軟件Redis的原子操作方式來(lái)獲取遞增ID序列[8]。由于Redis具備高性能，該方案解決了數(shù)據(jù)庫(kù)方案性能受限的問(wèn)題，但引入了Redis同樣增加了整個(gè)系統(tǒng)對(duì)Redis的強(qiáng)依賴(lài)，出現(xiàn)了單點(diǎn)問(wèn)題，而且引入Redis后要保證Redis系統(tǒng)的高可用性與高可靠性，在工程上有很大的挑戰(zhàn)，實(shí)現(xiàn)難度較大。

2.4 Twitter Snowflake方案

Twitter Snowflake方案是Twitter推出的一種算法[9]，其目的是為了滿(mǎn)足每秒能分配上萬(wàn)個(gè)唯一ID的需求，滿(mǎn)足分布式環(huán)境的需求。其算法核心如下：Snowflake生成的unique ID，從高位到低位分別為：41位的時(shí)間戳、10位的節(jié)點(diǎn)ID和12位的序列號(hào)。為了避免保障機(jī)器號(hào)重復(fù)，每個(gè)進(jìn)程啟動(dòng)時(shí)都需要從Zookeeper集群獲取機(jī)器號(hào)。Snowflake的優(yōu)點(diǎn)是算法簡(jiǎn)單、性能高、保持自增。但是Snowflake的實(shí)現(xiàn)帶來(lái)了的風(fēng)險(xiǎn)：依賴(lài)Zookeeper來(lái)解決單點(diǎn)問(wèn)題。但Zookeeper工程上運(yùn)維代價(jià)過(guò)高，面對(duì)高并發(fā)，Zookeeper的性能較差。一旦proposer所在機(jī)器時(shí)鐘故障，時(shí)鐘被回?fù)?，就不能保障全局唯一且遞增。同樣由于機(jī)器時(shí)鐘可能存在的故障，有可能發(fā)生proposer宕機(jī)后恢復(fù)導(dǎo)致非遞增ID生成的極端情況。

以上列舉的幾種方案，都存在一定的局限或風(fēng)險(xiǎn)，不能很好的滿(mǎn)足Paxos算法的需求。其中Snowflake是最接近高性能需求的方案，該文重點(diǎn)針對(duì)其進(jìn)行優(yōu)化，以達(dá)到高可用和高可靠的目標(biāo)。

3? 全局唯一自增ID生成

Snowflake的主要缺陷就是對(duì)本機(jī)時(shí)鐘有依賴(lài)，一旦本機(jī)時(shí)鐘故障導(dǎo)致時(shí)鐘回?fù)?，就不能正確的工作;同時(shí)由于對(duì)Zookeeper服務(wù)強(qiáng)依賴(lài)，整個(gè)系統(tǒng)較為復(fù)雜。該方案的重點(diǎn)就是在Snowflake的基礎(chǔ)上針對(duì)時(shí)鐘問(wèn)題進(jìn)行改進(jìn)，其核心思想就是引入一個(gè)可靠的時(shí)鐘服務(wù)器，本機(jī)定時(shí)從外部時(shí)鐘服務(wù)器獲取到準(zhǔn)確的時(shí)間，而時(shí)鐘服務(wù)的工程實(shí)現(xiàn)比Zookeeper等開(kāi)源系統(tǒng)簡(jiǎn)單可靠，從而克服了其對(duì)外部一致性服務(wù)依賴(lài)的弊端以及機(jī)器時(shí)鐘回?fù)艿膯?wèn)題，能很好地滿(mǎn)足Paxos算法的需求。同時(shí)，該方法只需要定時(shí)和時(shí)鐘服務(wù)器同步時(shí)間戳，確保系統(tǒng)具有高性能。

Snowflake生成的UniqueID的結(jié)構(gòu)是一個(gè)64位的int類(lèi)型數(shù)據(jù)，具體情況見(jiàn)圖1。其中第一部分共1位，往往不使用;第二部分共41位，用來(lái)記錄時(shí)間戳，以毫秒來(lái)表示;第三部分共10位，用來(lái)記錄分布式節(jié)點(diǎn)ID，包括5位的datacenter ID和5位的worker ID，最大可部署1 024個(gè)節(jié)點(diǎn);第四部分共12位，用來(lái)記錄不同ID同一毫秒時(shí)的序列號(hào)。

3.1 方案改進(jìn)

相對(duì)于Snowflake方案，該系統(tǒng)的關(guān)鍵改進(jìn)為引入一個(gè)節(jié)點(diǎn)ID分配服務(wù)（后續(xù)簡(jiǎn)稱(chēng)為IDCMaster），每個(gè)datacenter有一個(gè)IDCMaster，IDCMaster也同時(shí)作為時(shí)鐘服務(wù)器，向所有的節(jié)點(diǎn)提供時(shí)鐘同步服務(wù)。

用于組裝UniqueID的時(shí)間戳并不是proposer所在機(jī)器的時(shí)間戳，而是使用IDCMaster的時(shí)間戳來(lái)生成UniqueID。這樣所有的proposer全部以IDCMaster的時(shí)間為準(zhǔn)，不存在由于proposer本地時(shí)間戳不對(duì)而導(dǎo)致的各種不一致問(wèn)題。同時(shí)，IDCMaster只是一個(gè)簡(jiǎn)單的保證時(shí)間正確的服務(wù)，相比Zookeeper，實(shí)現(xiàn)和運(yùn)維十分簡(jiǎn)單，易于實(shí)現(xiàn)高性能、高可用。整個(gè)系統(tǒng)架構(gòu)見(jiàn)圖2。

3.2 計(jì)算方法

proposer啟動(dòng)時(shí)會(huì)先連接所在datacenter的IDCMaster，獲取當(dāng)前proposer唯一的workerID。IDCMaster保證分配出來(lái)的workerID在datacenter范圍內(nèi)唯一。proposer會(huì)定時(shí)從IDCMaster獲取到IDCMaster的時(shí)間戳并計(jì)算出proposer所在機(jī)器的時(shí)間戳相對(duì)IDCMaster的時(shí)間偏差并存放在本地，該時(shí)間偏差值設(shè)為diff_time。

當(dāng)提交prepare提案時(shí)，每個(gè)proposer不直接用本機(jī)的時(shí)間戳作為UniqueID的時(shí)間戳，而是用diff_time對(duì)本地時(shí)間戳作一個(gè)修正后來(lái)生成UniqueID。所以雖然本地時(shí)間戳可能不準(zhǔn)確，但可以通過(guò)diff_time來(lái)修正本地時(shí)間戳，保持每次生成ID時(shí)使用的本地時(shí)間戳和IDCMaster的時(shí)間戳一致。同時(shí)，由于本地時(shí)鐘頻率可由硬件保證，就算出現(xiàn)了時(shí)鐘故障導(dǎo)致機(jī)器時(shí)間被回?fù)?，只需定時(shí)和IDCMaster同步，獲取到diff_time就可以保證生成ID唯一遞增的正確性，并具有高性能。

3.3 注意事項(xiàng)

該方案盡管不同于物理機(jī)器的時(shí)間戳可能有偏差，但由于物理機(jī)器的時(shí)鐘頻率由硬件保證，極大情況下時(shí)鐘只會(huì)正向流逝。同時(shí)，即便是時(shí)間出現(xiàn)回?fù)?，也通過(guò)和IDCMasterde定時(shí)同步獲得正確的時(shí)間戳，快速恢復(fù)工作，并不會(huì)影響唯一自增ID的生成。這樣既保證了正確性，又保證了高性能。

proposer每次定時(shí)更新本機(jī)和IDCMaster的偏差 diff_time時(shí)，必須保證修正后的時(shí)間戳單調(diào)遞增。proposer只是定時(shí)訪問(wèn)IDCMaster，所以IDCMaster的高可用方案比較容易實(shí)現(xiàn)。比如可以簡(jiǎn)單地利用較成熟的IP地址漂移技術(shù)實(shí)現(xiàn)。利用IDCMaster Backup作為IDCMaster的備用機(jī)器，當(dāng)IDCMaster宕機(jī)時(shí)，IDCMaster對(duì)外的IP地址漂移到IDCMaster Backup。當(dāng)IDCMaster宕機(jī)恢復(fù)后，proposer會(huì)重連上IDCMaster，恢復(fù)更新本機(jī)和IDCMaster的時(shí)間戳的偏差即可。而且IDCMaster做的工作及其簡(jiǎn)單，只是提供一個(gè)時(shí)間戳，性能極高。當(dāng)然也需要保障IDCMaster Backup的時(shí)間戳保證和IDCMaster的時(shí)間戳一致。

該方法最大的限制就是本機(jī)時(shí)鐘硬件故障。但只要時(shí)鐘流逝是正向的，不出現(xiàn)大幅時(shí)鐘回?fù)艿墓收系那闆r下，就不會(huì)破壞整個(gè)方案的正確性，即生成唯一自增ID。因此，只需要本機(jī)proposer在每次生成ID時(shí)確認(rèn)新生成的ID比上次生成的ID大。如果一旦檢測(cè)到新生成的ID較小的情況，就說(shuō)明這次生成的ID不正確，直接拋棄掉，直到下次和IDCMaster同步后就又能生成正確的自增ID。

當(dāng)某個(gè)proposer下線(xiàn)后，再有一個(gè)新的proposer連上IDCMaster的場(chǎng)景，如果IDCMaster分配了原先的節(jié)點(diǎn)ID給新連上來(lái)的proposer，IDCMaster要保證同步給新proposer時(shí)間戳大于之前的下線(xiàn)的proposer的時(shí)間戳。

4? 實(shí)驗(yàn)

為了驗(yàn)證該方案的性能及唯一ID的產(chǎn)生，構(gòu)建了以下測(cè)試環(huán)境：10臺(tái)位于同一物理機(jī)房的物理機(jī)，其規(guī)格均為4核8G。實(shí)驗(yàn)中逐步加大測(cè)試并發(fā)量，壓測(cè)每臺(tái)物理機(jī)，直到單機(jī)每秒吞吐量達(dá)到5萬(wàn)以上，同時(shí)也會(huì)記錄下平均的延時(shí)和系統(tǒng)負(fù)載。測(cè)試過(guò)程中，會(huì)分別測(cè)試正常態(tài)下和異常態(tài)下系統(tǒng)的性能及產(chǎn)生ID的唯一性。

實(shí)驗(yàn)進(jìn)程如下：初始狀態(tài)為1臺(tái)物理機(jī)連接上IDCMaster，并開(kāi)始消耗唯一ID，然后每間隔1 min新增一臺(tái)物理機(jī)連接到IDCMaster;終態(tài)為10臺(tái)物理機(jī)同時(shí)連上IDCMaster進(jìn)行工作，然后逐步增大工作并發(fā)量直到單機(jī)每秒吞吐量達(dá)到5萬(wàn)。

記錄正常態(tài)的實(shí)驗(yàn)過(guò)程中每次和IDCMaster同步的延時(shí)（系統(tǒng)設(shè)置為每分鐘和IDCMaster同步一次diff master），以及節(jié)點(diǎn)平均產(chǎn)生唯一ID的延時(shí)和最高延時(shí)，并記錄實(shí)驗(yàn)產(chǎn)生的所有ID。正常態(tài)實(shí)驗(yàn)結(jié)果見(jiàn)圖3。

實(shí)驗(yàn)結(jié)果顯示，單個(gè)ID生成的耗時(shí)小于0.02 ms，生成1 000個(gè)ID的耗時(shí)在3 ms以?xún)?nèi)。同時(shí)測(cè)試單機(jī)的平均吞吐量為5萬(wàn)ID/s，并且在測(cè)試過(guò)程中，機(jī)器的負(fù)載很?。?jiǎn)螜C(jī)CPU利用率小于10%，單機(jī)LOAD小于0.5。同時(shí)，驗(yàn)證了所有升級(jí)的ID，滿(mǎn)足無(wú)重復(fù)遞增的要求。通過(guò)正常態(tài)測(cè)試，驗(yàn)證了該方案能滿(mǎn)足分布式高吞吐量場(chǎng)景的正確性。

在正常態(tài)實(shí)驗(yàn)的基礎(chǔ)上，進(jìn)行異常態(tài)測(cè)試。在實(shí)驗(yàn)過(guò)程中，手工回?fù)軉闻_(tái)物理機(jī)的本機(jī)時(shí)間，關(guān)閉NTP服務(wù)，驗(yàn)證服務(wù)器時(shí)鐘故障的場(chǎng)景下ID生成的正確性。異常態(tài)測(cè)試結(jié)果如圖4所示。

通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法可以適應(yīng)時(shí)鐘回?fù)艿墓收?，不影響生成ID的自增屬性。當(dāng)時(shí)鐘回?fù)軙r(shí)，生成節(jié)點(diǎn)可檢測(cè)到時(shí)鐘問(wèn)題，停止分配ID，避免了錯(cuò)誤的ID生成，直到1 min后再次和IDCMaster同步時(shí)間戳后，能夠繼續(xù)分配正確的自增唯一ID。

5? 結(jié)語(yǔ)

該文介紹了一種可應(yīng)用在Paxos算法實(shí)現(xiàn)中的全局唯一自增ID生成方法。該方法基于Snowflake方案，但解決了Snowflake在物理機(jī)器時(shí)間戳不一致場(chǎng)景下不能保證生成的ID唯一自增的缺陷。該方案的核心思想是利用機(jī)器時(shí)鐘頻率變化不會(huì)過(guò)大的特性來(lái)實(shí)現(xiàn)分布式的自增ID的生成;同時(shí)也針對(duì)各種極限情況作了保障，使得即使發(fā)生特殊異常，也不會(huì)破壞整個(gè)Paxos算法的正確性。下一步工作是進(jìn)一步提升生成自增ID的TPS，并探索在云主機(jī)環(huán)境的適應(yīng)性，使該系統(tǒng)能適用于更大規(guī)模的場(chǎng)景。

參考文獻(xiàn)

[1] Chandra TD，Griesemer R，Redstone J.Paxos made live：an engineering perspective[C]//twenty-sixth acm symposium on principles of distributed computing.acm，2007：398-407.

[2] Saksham Chand，Yanhong A.Liu，Scott D.Stoller.Formal Ver-ification of Multi-Paxos for Distributed Consensus[C]//International Symposium on Formal Methods，2016：119-136.

[3] 胡創(chuàng)，馬文韜，王文杰，等.CC-Paxos：整合廣域存儲(chǔ)系統(tǒng)的一致性和可靠性[J].計(jì)算機(jī)工程與設(shè)計(jì)，2017，38（3）：626-632.

[4] 楊革，徐虹.Paxos算法的研究與改進(jìn)[J].科技創(chuàng)新與應(yīng)用，2017（7）：25-26.

[5] 趙守月，葛洪偉.MEPaxos：低延遲的共識(shí)算法[J].計(jì)算機(jī)科學(xué)與探索，2019，13（5）：866-874.

[6] 王江，章明星，武永衛(wèi)，等.類(lèi)Paxos共識(shí)算法研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2019，56（4）：692-707.

[7] Lamport L.Paxos made simple[J].ACM SIGACT News， 2001，32（4）：51-58.

[8] Yao Kan，Ni huxuan，wang yuan，et al.Low Cost and High Concurrency ID Mak-er in Distributed Environment[C]//ITM Web of Conferences，2017：03003.

[9] Jim Bumgardner.Tracking Twitter's Growth after Snow-flake[EB/OL].[2019-05-12].https：//www.jbum.com/papers/TrackingTwittersGrowthAfterSnowflake.pdf.