摘要
??遠(yuǎn)程的內(nèi)存中鍵值（RInK）存儲(chǔ)（例如 Mem 緩存[6]和Redis [7]）在行業(yè)中被廣泛使用，并且是學(xué)術(shù)研究的活躍領(lǐng)域。它們與執(zhí)行業(yè)務(wù)邏輯的無(wú)狀態(tài)應(yīng)用程序服務(wù)器以及提供持久性存儲(chǔ)的類(lèi)似數(shù)據(jù)庫(kù)的系統(tǒng)結(jié)合在一起，構(gòu)成了流行的數(shù)據(jù)中心服務(wù)體系結(jié)構(gòu)的核心組件。我們認(rèn)為 RInK 存儲(chǔ)的時(shí)代已經(jīng)過(guò)去了：它們的獨(dú)立于域的 API（例如PUT / GET）將復(fù)雜性推回到應(yīng)用程序中，從而導(dǎo)致額外的（非）編組開(kāi)銷(xiāo)和網(wǎng)絡(luò)躍點(diǎn)。取而代之的是，應(yīng)該使用具有狀態(tài)的應(yīng)用程序服務(wù)器或具有特定于域的 API 的自定義內(nèi)存存儲(chǔ)來(lái)構(gòu)建數(shù)據(jù)中心服務(wù)，以比 RInK 更低的成本提供更高的性能。避免了此類(lèi)設(shè)計(jì)，因?yàn)樵跊](méi)有適當(dāng)基礎(chǔ)架構(gòu)支持的情況下難以實(shí)現(xiàn)?？紤]到自動(dòng)分片技術(shù)的最新進(jìn)展[8，9]，我們認(rèn)為現(xiàn)在是時(shí)候重新考慮這些決策了。在本文中，我們?cè)u(píng)估了有狀態(tài)設(shè)計(jì)的潛在性能改進(jìn)，提出了一種新的抽象，即鏈接的內(nèi)存中鍵值（LInK）存儲(chǔ)，以使開(kāi)發(fā)人員能夠輕松地實(shí)現(xiàn)有狀態(tài)服務(wù)，并討論需要解決的領(lǐng)域和未來(lái)的研究。
介紹
??現(xiàn)代互聯(lián)網(wǎng)規(guī)模的服務(wù)通常依賴(lài)于遠(yuǎn)程，內(nèi)存中的鍵值（ RInK ）存儲(chǔ)，例如 Redis [7]和Mem緩存[6]（圖1）。 這些存儲(chǔ)服務(wù)至少有兩個(gè)目的。首先，它們可以在存儲(chǔ)系統(tǒng)上提供緩存，以便能夠更快地檢索持久狀態(tài)。 其次，它們可能存儲(chǔ)短期數(shù)據(jù)，例如每個(gè)會(huì)話(huà)狀態(tài)，這些數(shù)據(jù)不能保證持久性[25]。
這些存儲(chǔ)庫(kù)使服務(wù)能夠使用無(wú)狀態(tài)應(yīng)用程序服務(wù)器[16]進(jìn)行部署，該服務(wù)器僅維護(hù)每個(gè)請(qǐng)求狀態(tài)。 所有其他狀態(tài)都駐留在永久性存儲(chǔ)或 RInK 存儲(chǔ)中。 無(wú)狀態(tài)應(yīng)用程序服務(wù)器帶來(lái)了操作上的簡(jiǎn)化：例如，任何請(qǐng)求都可以由任何應(yīng)用程序服務(wù)器處理，這使得添加和刪除應(yīng)用程序服務(wù)器，處理服務(wù)器故障以及處理歪斜變得容易。
??RInK 存儲(chǔ)庫(kù)的關(guān)鍵屬性是它們提供了一個(gè)簡(jiǎn)單且與域無(wú)關(guān)的接口（例如，字符串鍵和字符串值的 PUT / GET，或?qū)χT如列表之類(lèi)的簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)的操作）。 由于 RInK 存儲(chǔ)庫(kù)處理定義明確且簡(jiǎn)單的操作，因此實(shí)現(xiàn)已能夠?qū)崿F(xiàn)異常高的吞吐量和低延遲[14、18、20、24]。 此外，這些存儲(chǔ)的高性能使分布式緩存挑戰(zhàn)（例如負(fù)載平衡）相對(duì)不那么重要：即使工作負(fù)載出現(xiàn)偏差，也可以簡(jiǎn)單地過(guò)度配置 RInK 存儲(chǔ)。
??另一方面，RInK 的與域無(wú)關(guān)的接口將成本和復(fù)雜性推回了應(yīng)用服務(wù)器。 例如，它們迫使應(yīng)用程序在本地語(yǔ)言表示形式和字符串之間重復(fù)轉(zhuǎn)換其內(nèi)部數(shù)據(jù)結(jié)構(gòu)，這既增加了 CPU 成本，又增加了程序員負(fù)擔(dān)。 當(dāng)應(yīng)用程序不使用從 RInK 存儲(chǔ)中檢索到的每個(gè)值的全部時(shí)，此問(wèn)題將更加嚴(yán)重，因?yàn)椴槐匾貍鬏斪止?jié)只是將其丟棄。 最后，網(wǎng)絡(luò)距離會(huì)增加延遲成本，尤其是在必須傳輸較大的值或需要多次往返的情況下。
??我們認(rèn)為，鑒于最近自動(dòng)分片系統(tǒng)[8，9]的改進(jìn)，這些成本被低估了，不再需要了。 開(kāi)發(fā)人員應(yīng)該構(gòu)建有狀態(tài)的應(yīng)用程序服務(wù)器，而不是外部化 RInK 中的內(nèi)存狀態(tài)。 有狀態(tài)應(yīng)用程序服務(wù)器是指在同一進(jìn)程中將應(yīng)用程序代碼和長(zhǎng)期內(nèi)存狀態(tài)耦合在一起的服務(wù)器。 如果有狀態(tài)應(yīng)用程序服務(wù)器不可行（例如，由于狀態(tài)由多種應(yīng)用程序或多種語(yǔ)言共享），則開(kāi)發(fā)人員應(yīng)改為構(gòu)建自定義的內(nèi)存存儲(chǔ)，該存儲(chǔ)區(qū)與應(yīng)用程序服務(wù)器之間的網(wǎng)絡(luò)距離較遠(yuǎn)，但要公開(kāi)特定于域的API。
??建立有狀態(tài)的服務(wù)需要解決新的技術(shù)挑戰(zhàn)，研究界應(yīng)該專(zhuān)注于幫助開(kāi)發(fā)人員解決這些挑戰(zhàn)，而不是建立越來(lái)越快的 RInK 存儲(chǔ)。 盡管它們帶來(lái)了挑戰(zhàn)，但有狀態(tài)服務(wù)仍可顯著改善性能。 例如，ProtoCache（廣泛使用的 Google 應(yīng)用程序的一個(gè)組成部分）在進(jìn)行此體系結(jié)構(gòu)切換時(shí)，將延遲時(shí)間降低了40％，降低了99.9％，而對(duì)模型應(yīng)用程序和合成工作負(fù)載的實(shí)驗(yàn)表明，潛在的延遲時(shí)間最多可提高57％。
??本文做出了三點(diǎn)貢獻(xiàn)。 首先，我們認(rèn)為耦合應(yīng)用程序代碼和緩存在內(nèi)存中的狀態(tài)帶來(lái)了被低估的性能好處。 其次，我們提出了一種新的鏈接的內(nèi)存中鍵值（ LInK ）存儲(chǔ)抽象。 LInK 存儲(chǔ)庫(kù)是鏈接到應(yīng)用程序服務(wù)器或自定義內(nèi)存存儲(chǔ)庫(kù)中的鍵到富對(duì)象的映射，它代替了外部 RInK 存儲(chǔ)庫(kù)。 它實(shí)現(xiàn)了功能，例如在重新分片事件之后進(jìn)行重新配置，我們發(fā)現(xiàn)這給開(kāi)發(fā)人員帶來(lái)了負(fù)擔(dān)。 最后，我們描述了研究社區(qū)可以做出貢獻(xiàn)的其他領(lǐng)域。
??最后，我們關(guān)注通過(guò)消除 RInK 存儲(chǔ)來(lái)提高訪(fǎng)問(wèn)內(nèi)存狀態(tài)時(shí)的應(yīng)用程序性能。 如何確保數(shù)據(jù)的持久性雖然很重要，但仍不在本文討論范圍之內(nèi)。
2. 靈感（Movitation）
2.1 無(wú)狀態(tài)和 RInK 架構(gòu)
??現(xiàn)代互聯(lián)網(wǎng)規(guī)模的服務(wù)需要高度可用且可靠。 保持魯棒性最重要的原則之一就是簡(jiǎn)單性，服務(wù)編寫(xiě)者的目標(biāo)是盡可能簡(jiǎn)單地構(gòu)建其系統(tǒng)，以使其易于實(shí)現(xiàn)，調(diào)試，維護(hù)和操作。
??早在上世紀(jì)90年代末，開(kāi)發(fā)人員就開(kāi)始使用無(wú)狀態(tài)應(yīng)用程序服務(wù)器，其中數(shù)據(jù)中心中的多個(gè)獨(dú)立進(jìn)程處理請(qǐng)求，而無(wú)需維護(hù)任何超出請(qǐng)求壽命的狀態(tài)(“LAMP堆?！?。處理每個(gè)請(qǐng)求所需的狀態(tài)是從存儲(chǔ)系統(tǒng)(如 SQL 數(shù)據(jù)庫(kù)或水平分區(qū)的分布式存儲(chǔ)系統(tǒng)，如HBase[2]、Cassandra[1]、Bigtable[12] 或 Spanner[13])臨時(shí)獲得的。這種設(shè)計(jì)最大化了應(yīng)用服務(wù)器的簡(jiǎn)單性，它只包含業(yè)務(wù)邏輯;特別是，它不包含管理狀態(tài)的代碼。
??純粹的無(wú)狀態(tài)設(shè)計(jì)可帶來(lái)運(yùn)維優(yōu)勢(shì)，因?yàn)槊總€(gè)應(yīng)用程序服務(wù)器都是等效的。 如果服務(wù)上的負(fù)載增加，則可以添加新服務(wù)器以吸收額外的負(fù)載。 如果服務(wù)器崩潰，則可以將請(qǐng)求定向到其余服務(wù)器。 如果服務(wù)器過(guò)載，則可以輕松地減輕負(fù)載，例如，通過(guò)將呼叫定向到負(fù)載最小的服務(wù)器或使用二次冪方法[22]。
??另一方面，在每個(gè)請(qǐng)求上訪(fǎng)問(wèn)持久性存儲(chǔ)既昂貴又緩慢。 服務(wù)可能還具有不適合持久的狀態(tài)，但仍然必須超過(guò)單個(gè)請(qǐng)求的狀態(tài)（例如，會(huì)話(huà)狀態(tài)）。 為了滿(mǎn)足這些需求，開(kāi)發(fā)人員對(duì)無(wú)狀態(tài)架構(gòu)進(jìn)行了改進(jìn)，使其包括一層 RInK 存儲(chǔ)，例如 Memcached [6]和Redis [7]（圖1）。 我們稱(chēng)其為無(wú)狀態(tài)+ RInK 架構(gòu)，即 S + RInK 。 期望 RInK：（1）通過(guò)卸載持久性存儲(chǔ)中的工作來(lái)提高可伸縮性，因?yàn)?RInK 處理大多數(shù)請(qǐng)求； （2）降低了延遲，因?yàn)樗恍枰峁┏志眯浴?/p>
?? 此外，在某些情況下，RInK 存儲(chǔ)提供了多個(gè)不同應(yīng)用程序之間的共享緩存，從而避免了每個(gè)應(yīng)用程序緩存中的數(shù)據(jù)重復(fù)，從而提高了整體效率。最后，RInK 存儲(chǔ)區(qū)比（大多數(shù)）應(yīng)用程序服務(wù)器更具可伸縮性，因?yàn)閼?yīng)用程序服務(wù)器通常執(zhí)行復(fù)雜的邏輯，并且 RInK 存儲(chǔ)區(qū)具有簡(jiǎn)單明了的界面。 高性能可讓 RInK 存儲(chǔ)使用簡(jiǎn)單的技術(shù)進(jìn)行分片（例如，Memcache 中的無(wú)負(fù)載感知一致哈希算法）。 鑒于缺乏自動(dòng)分片的基礎(chǔ)設(shè)施，將分片隔離到 RInK 存儲(chǔ)將很有吸引力。
2.2 無(wú)狀態(tài)和 RInK 架構(gòu)的限制
??S+RInK架構(gòu)試圖同時(shí)提供兩個(gè)方面的最佳效果:同時(shí)提供無(wú)狀態(tài)應(yīng)用服務(wù)器的實(shí)現(xiàn)和操作簡(jiǎn)單性，以及服務(wù)器在RAM中緩存狀態(tài)的性能優(yōu)勢(shì)。我們認(rèn)為架構(gòu)的不足是由于它所提供的抽象的基本限制。
2.2.1 CPU cost due to (un) marshalling
??我們認(rèn)為序列化/反序列化是現(xiàn)實(shí)應(yīng)用的基礎(chǔ)。 抽象數(shù)據(jù)類(lèi)型很有用[21]，其內(nèi)部表示形式不太可能與線(xiàn)性格式相對(duì)應(yīng)。 例如，它可以包括長(zhǎng)度可變的字段或指針。 其次，隨著軟件的發(fā)展，可以在 RInK 中存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)中添加和刪除字段，而 RInK 則爭(zhēng)用不同的有線(xiàn)和內(nèi)存格式。 最后，如果用不同語(yǔ)言編寫(xiě)的程序使用了相同的緩存數(shù)據(jù)，則不可避免地會(huì)進(jìn)行一些序列化/反序列化。
由于將數(shù)據(jù)轉(zhuǎn)換為特定于域的表示形式，因此 RInK API 引入了大量的 CPU 開(kāi)銷(xiāo)。
2.2.2 Overreads
??當(dāng)應(yīng)用程序從 RInK 存儲(chǔ)中讀取的數(shù)據(jù)超出要求時(shí)，就會(huì)發(fā)生超讀，從而導(dǎo)致額外的 CPU 和網(wǎng)絡(luò)成本。 當(dāng)應(yīng)用程序必須獲取整個(gè)值時(shí)，即使只有一小部分對(duì)相應(yīng)的計(jì)算有用，也會(huì)發(fā)生這種情況。 例如，考慮一個(gè)為 RInK 存儲(chǔ)中的所有在線(xiàn)用戶(hù)緩存通訊簿的應(yīng)用程序：對(duì)于每個(gè)用戶(hù)，通訊簿都存儲(chǔ)為單個(gè)鍵值對(duì)。 如果來(lái)自愛(ài)麗絲的要求從其通訊錄中讀取鮑勃的電話(huà)號(hào)碼的請(qǐng)求，則即使只需要一小部分?jǐn)?shù)據(jù)，也必須提取并取消整理愛(ài)麗絲的所有聯(lián)系人。
??將較大的鍵值對(duì)分解為多個(gè)鍵值對(duì)可以減少過(guò)度讀取的程度，但以一致性保證較弱的代價(jià)為代價(jià)：大多數(shù) RInK 存儲(chǔ)庫(kù)不支持原子交叉鍵操作。 另外，設(shè)計(jì)分解表示以加速豐富的操作（例如，在日歷應(yīng)用中找到用戶(hù)的第一個(gè)空閑時(shí)隙）顯然不是簡(jiǎn)單的。 最后，為支持特定操作而對(duì)架構(gòu)進(jìn)行的優(yōu)化越多，隨著需求或工作負(fù)載的變化，架構(gòu)就越難以發(fā)展。 有時(shí)也可以使用存儲(chǔ)中更豐富的數(shù)據(jù)模型來(lái)緩解過(guò)度讀取[7]，但是正如我們下面將要討論的那樣，此類(lèi)解決方案缺乏通用性和靈活性。
舉一個(gè)真實(shí)的例子，對(duì)于 ProtoCache 中的一種常見(jiàn)操作類(lèi)型，在第99個(gè)百分位數(shù)處，響應(yīng)僅占緩存項(xiàng)總數(shù)的2％：避免過(guò)度讀取很重要。 這些操作是使用索引集合實(shí)現(xiàn)的，這意味著不會(huì)將緩存的項(xiàng)目分解為多個(gè)鍵值對(duì)，而這些鍵值對(duì)將適用于所有操作。
最后，我們?cè)诘?節(jié)中的實(shí)驗(yàn)表明，如果只需要部分記錄（10％），則 RInK 存儲(chǔ)會(huì)產(chǎn)生額外的 CPU（46％）和網(wǎng)絡(luò)（85％）成本。
RInK導(dǎo)致不必要的數(shù)據(jù)處理和傳輸
2.2.3 網(wǎng)絡(luò)延遲
??甚至快速的數(shù)據(jù)中心網(wǎng)絡(luò)也會(huì)在無(wú)狀態(tài)和 RInK 架構(gòu)中增加延遲成本。 如果應(yīng)用程序需要多次讀取或?qū)懭氩僮鞑拍軡M(mǎn)足請(qǐng)求，則這些延遲可能會(huì)迅速增加。 除了簡(jiǎn)單的 RTT 之外，要傳輸?shù)臄?shù)據(jù)大小也很重要，這與超讀結(jié)合在一起是一個(gè)特別的問(wèn)題。 例如，盡管網(wǎng)絡(luò)高速，但 ProtoCache 在進(jìn)行重構(gòu)之前，僅從遠(yuǎn)程存儲(chǔ)傳輸大記錄就產(chǎn)生了80毫秒的延遲損失。
使用RInK存儲(chǔ)庫(kù)時(shí)，低延遲數(shù)據(jù)中心網(wǎng)絡(luò)無(wú)法消除數(shù)據(jù)傳輸開(kāi)銷(xiāo)。
2.3 最先進(jìn)的 RINK 存儲(chǔ)
??盡管已經(jīng)提出了許多改進(jìn) RInK 實(shí)現(xiàn)的方法，但是它們都不能解決上述挑戰(zhàn)。
2.3.1基本RInK存儲(chǔ)
??基本的 RInK 存儲(chǔ)提供的接口實(shí)際上僅是 PUT / GET API。 例如，Memcached [6]是最早的和最著名的 RInK 存儲(chǔ)之一； 它已經(jīng)廣泛部署，包括在Facebook的Tao [11]和Dropbox的Edgestore [4]中； 一個(gè)版本也被Google廣泛使用。 除PUT / GET之外，它還包括一些有限的附加操作，例如將值附加到現(xiàn)有值上并遞增現(xiàn)有整數(shù)值。
??最近，學(xué)術(shù)界致力于建立性能更高的基本 RInK 存儲(chǔ)，以及優(yōu)化 Memcached 到死[10、15、26、28]。 FaRM [14]試圖通過(guò)降低使用 RDMA 提取遠(yuǎn)程數(shù)據(jù)的成本來(lái)提高無(wú)狀態(tài)應(yīng)用程序的性能。 網(wǎng)絡(luò)緩存[18]通過(guò)直接在網(wǎng)絡(luò)交換機(jī)中為熱鍵提供額外的緩存層來(lái)解決內(nèi)存中存儲(chǔ)的負(fù)載偏差。 KV-Direct [20] 利用可編程的網(wǎng)卡繞過(guò)遠(yuǎn)程 CPU 并實(shí)現(xiàn)對(duì)遠(yuǎn)程內(nèi)存的高吞吐量訪(fǎng)問(wèn)，同時(shí)提供比傳統(tǒng) RDMA 更豐富的語(yǔ)義。
這些系統(tǒng)側(cè)重于提高 PUT / GET 操作的性能，而不是解決（非）編組成本或超額讀取的問(wèn)題。
2.3.2擴(kuò)展的RInK存儲(chǔ)
??擴(kuò)展的 RInK 存儲(chǔ)庫(kù)提供了比基本 RInK 存儲(chǔ)庫(kù)更豐富的域不可知的 API。Gribble【17】等人建議構(gòu)建一小組集群規(guī)模的分布式數(shù)據(jù)結(jié)構(gòu)。 如此處所考慮的，這類(lèi)似于 Redis [7]，后者也提供了數(shù)據(jù)結(jié)構(gòu)，可以對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行更細(xì)粒度的訪(fǎng)問(wèn)，但是需要應(yīng)用程序使用可用數(shù)據(jù)結(jié)構(gòu)之一對(duì)其對(duì)象進(jìn)行建模。 Redis 也可以使用任意 C 代碼模塊進(jìn)行擴(kuò)展，Splinter [29]允許應(yīng)用程序?qū)⑸倭看a片段發(fā)送到存儲(chǔ)。 這些擴(kuò)展是我們倡導(dǎo)的定制內(nèi)存存儲(chǔ)的精神。 我們主張進(jìn)一步采用這種方法，并在可能的情況下將存儲(chǔ)嵌入到應(yīng)用程序服務(wù)器中，并提供更豐富的功能集，例如動(dòng)態(tài)負(fù)載平衡和復(fù)制。
3. 消除RInK存儲(chǔ)
??我們認(rèn)為實(shí)現(xiàn)可擴(kuò)展的數(shù)據(jù)中心服務(wù)時(shí)不應(yīng)使用 RInK 存儲(chǔ)（圖2a）。 在本節(jié)中，我們描述如何通過(guò)提供兩種用于狀態(tài)服務(wù)的標(biāo)準(zhǔn)體系結(jié)構(gòu)，從現(xiàn)有體系結(jié)構(gòu)中消除 RInK 存儲(chǔ)。 在第4節(jié)中，我們描述了如何使這些體系結(jié)構(gòu)更易于實(shí)現(xiàn)。
3.1有狀態(tài)應(yīng)用程序服務(wù)器
??有狀態(tài)的應(yīng)用程序服務(wù)器將完整的應(yīng)用程序邏輯與鏈接到同一進(jìn)程的內(nèi)存中狀態(tài)緩存結(jié)合在一起（圖 2b）。 這種架構(gòu)有效地將 RInK 與應(yīng)用服務(wù)器合并； 當(dāng)僅由單個(gè)應(yīng)用程序訪(fǎng)問(wèn) RInK 并且所有請(qǐng)求都訪(fǎng)問(wèn)單個(gè) key 時(shí)，這是可行的。 例如，聯(lián)系人應(yīng)用程序服務(wù)器可能會(huì)緩存用戶(hù)地址簿，并直接接受 HTTP 請(qǐng)求以將其呈現(xiàn)在 Web UI 中。
??這種體系結(jié)構(gòu)消除了第2節(jié)中討論的 RInK 問(wèn)題。由于高速緩存存儲(chǔ)應(yīng)用程序?qū)ο?，因此沒(méi)有（取消）編組(序列化)開(kāi)銷(xiāo)或網(wǎng)絡(luò)延遲。 同樣，由于應(yīng)用程序只能直接訪(fǎng)問(wèn)其對(duì)象的所需部分，因此可以消除過(guò)度讀取。 例如，對(duì)于大型對(duì)象的小修改，可以用便宜的本地修改操作代替昂貴的讀取-修改-寫(xiě)入操作。
??為了量化這些好處，我們進(jìn)行了實(shí)驗(yàn)，將 S + RInK 與有狀態(tài)的應(yīng)用程序服務(wù)器進(jìn)行了比較。 我們使用了5個(gè)客戶(hù)端，每種類(lèi)型的5個(gè)服務(wù)器以及如圖2a所示的部署模型。 每個(gè)工作負(fù)載運(yùn)行2個(gè)小時(shí)，具有80％的讀取操作和20％的寫(xiě)入操作，總吞吐量從6 KB / s到250 MB / s。 我們測(cè)量了兩種架構(gòu)的資源消耗（ CPU 和傳輸?shù)淖止?jié)）和端到端延遲的減少。 我們針對(duì)不同的對(duì)象大小和超讀百分比進(jìn)行了實(shí)驗(yàn)。
圖3a，3b和表1顯示了我們的結(jié)果。 在每個(gè)請(qǐng)求/響應(yīng)延遲和資源利用率方面，有狀態(tài)的方法優(yōu)于 S + RInK：
延遲改善了29％到57％（中位），相對(duì)改善程度隨對(duì)象大小的增加而增加（圖3a）；
減少的過(guò)度讀取導(dǎo)致較低的延遲和資源利用率（圖3b，表1）；
3.2自定義內(nèi)存存儲(chǔ)
??自定義內(nèi)存存儲(chǔ)是具有域特定接口的單獨(dú)的內(nèi)存緩存（圖2c）。 相對(duì)于有狀態(tài)的應(yīng)用服務(wù)器，這種體系結(jié)構(gòu)會(huì)引起額外的網(wǎng)絡(luò)躍點(diǎn)，這意味著它只會(huì)緩解而不是消除 RInK 存儲(chǔ)庫(kù)中的問(wèn)題。 例如，它仍然可以使用特定于域的 API 減少解組的開(kāi)銷(xiāo)和超讀。 另一方面，為了交換網(wǎng)絡(luò)躍點(diǎn)，它允許在多個(gè)應(yīng)用程序和語(yǔ)言之間共享單個(gè)緩存。
??例如，日歷服務(wù)可能會(huì)緩存用戶(hù)日歷，并公開(kāi)一個(gè) find-free-slots（user，date）API 以在給定的一天中查找特定用戶(hù)的空閑時(shí)隙，這比要求應(yīng)用程序獲取該消息的開(kāi)銷(xiāo)要小。 用戶(hù)日歷的整體。
??開(kāi)發(fā)人員經(jīng)常認(rèn)為 RInK 存儲(chǔ)至關(guān)重要是有幾個(gè)原因。 我們將簡(jiǎn)要列舉其中的一些內(nèi)容，并描述自定義內(nèi)存存儲(chǔ)如何在提供同等或更好性能的同時(shí)替換 RInK。
Fanout:無(wú)狀態(tài)應(yīng)用程序服務(wù)器在處理單個(gè)邏輯操作時(shí)，常常從一個(gè) RInK 讀取多個(gè) keys 。custom 內(nèi)存存儲(chǔ)也可以支持 fanout ，但是特定于域的 API 可以減少過(guò)度讀取，例如，使用聚合或快速鍵值存儲(chǔ):這種思想已經(jīng)過(guò)時(shí)了。例如，為了安排一個(gè)有多個(gè)參與者的會(huì)議，日程表應(yīng)用程序可能會(huì)發(fā)出許多空閑時(shí)間的 Rpc 來(lái)為每個(gè)參與者獲取候選會(huì)議時(shí)間。
共享：RInK 存儲(chǔ)通常用于提供由多個(gè)不同應(yīng)用程序共享的緩存，以實(shí)現(xiàn)跨應(yīng)用程序集成（例如在電子郵件客戶(hù)端中顯示日歷）或避免在單獨(dú)的緩存中復(fù)制數(shù)據(jù)。 定制的內(nèi)存中存儲(chǔ)也可以擔(dān)當(dāng)此角色，再次可能具有更好的性能。
資源分解：服務(wù)所有者可能希望將工作量中占用大量 CPU 和內(nèi)存的部分隔離在不同的進(jìn)程（即應(yīng)用程序服務(wù)器和 RInK ）中，以便可以分別進(jìn)行調(diào)配。 就 RInK 存儲(chǔ)可以實(shí)現(xiàn)更有效的配置而言，自定義內(nèi)存存儲(chǔ)也可以。
??總之，與基于 RInK 的方法相比，有狀態(tài)應(yīng)用程序服務(wù)器或具有特定于域的緩存的無(wú)狀態(tài)應(yīng)用程序服務(wù)器將始終提供相同或更好的延遲，效率和可伸縮性，因?yàn)檫@些架構(gòu)可以輕松地模仿它。 尤其是，這些體系結(jié)構(gòu)減少或消除了（非）編組(序列化)開(kāi)銷(xiāo)，過(guò)度讀取和網(wǎng)絡(luò)延遲。 但是，RInK 存儲(chǔ)之所以受歡迎，部分原因是它們易于采用。 為了使服務(wù)編寫(xiě)者輕松實(shí)現(xiàn)有狀態(tài)體系結(jié)構(gòu)的好處，我們提出了一種新的存儲(chǔ)抽象，如下所述。
4 LInk 存儲(chǔ):提高抽象度
??本節(jié)介紹了LInK存儲(chǔ)抽象，首先通過(guò)描述自動(dòng)分片器未滿(mǎn)足的需求來(lái)引出它。
4.1 自動(dòng)分片器：必要但不夠
??自動(dòng)分片系統(tǒng)[8,9]是有狀態(tài)應(yīng)用程序服務(wù)器的必要構(gòu)件:如果不能對(duì)服務(wù)器故障和工作負(fù)載的變化(例如熱鍵)進(jìn)行重新操作，那么大規(guī)模部署有狀態(tài)應(yīng)用程序服務(wù)器是不現(xiàn)實(shí)的。然而，我們?cè)诠雀枧c許多內(nèi)部客戶(hù)進(jìn)行了5年的經(jīng)驗(yàn)表明，一個(gè)簡(jiǎn)單地將應(yīng)用程序keys分配給服務(wù)器的自動(dòng)分片系統(tǒng)會(huì)留下一些重要的問(wèn)題沒(méi)有解決。
??特別是，自動(dòng)分配器涉及分區(qū)鍵，但是應(yīng)用程序必須處理值。例如，當(dāng)鍵的分配從一個(gè)服務(wù)器更改到另一個(gè)服務(wù)器時(shí)，自動(dòng)分配器不會(huì)移動(dòng)關(guān)聯(lián)的值。服務(wù)器新分配的鍵必須通過(guò)從影響尾部張力的存儲(chǔ)系統(tǒng)中讀取來(lái)恢復(fù)值。如果值在持久存儲(chǔ)中不存在(例如，會(huì)話(huà)狀態(tài))，那么它就會(huì)丟失，從而影響用戶(hù)體驗(yàn)。
??此外，需要跨多個(gè)服務(wù)器復(fù)制鍵(例如，出于負(fù)載或可用性原因)和相關(guān)值的一致性(強(qiáng)或最終)的應(yīng)用程序必須自己構(gòu)建這樣的功能:自動(dòng)分配器只處理鍵的分配，而不處理對(duì)其值的操作。最后，應(yīng)用程序可能需要保持緩存的狀態(tài)與一些底層數(shù)據(jù)存儲(chǔ)保持同步;自動(dòng)分配器在這里也沒(méi)有幫助。
??為了解決這些應(yīng)用程序需求，我們提出了一種新的抽象，它類(lèi)似于RInK，我們稱(chēng)之為鏈接存儲(chǔ)，用于鏈接內(nèi)存中的鍵值存儲(chǔ)。我們已經(jīng)構(gòu)建了一個(gè)原型，一個(gè)生產(chǎn)團(tuán)隊(duì)目前正在使用它實(shí)現(xiàn)一個(gè)應(yīng)用程序。在本節(jié)的其余部分，我們將描述鏈接存儲(chǔ)。
4.2 LInk 存儲(chǔ)
?? 鏈接存儲(chǔ)是自動(dòng)分配器上的高級(jí)抽象，自動(dòng)分配器提供一個(gè)分布式的、內(nèi)存中的鍵-值映射，其中復(fù)雜的應(yīng)用程序?qū)ο笞鳛橹担皇亲址蚝?jiǎn)單數(shù)據(jù)結(jié)構(gòu)。作為一個(gè)高級(jí)抽象，它提供了比自動(dòng)分配器更豐富的功能。我們特別認(rèn)為下列特點(diǎn)是可取的:
?數(shù)據(jù)一致性。鏈接存儲(chǔ)可以提供跨多個(gè)副本的數(shù)據(jù)一致性，從而改進(jìn)了熱鍵的處理(可以從多個(gè)副本提供熱鍵)。數(shù)據(jù)一致性可能很強(qiáng)，也可能是最終的結(jié)果;相比之下，自動(dòng)分配器本身并沒(méi)有提供數(shù)據(jù)一致性。
?高可用性。鏈接存儲(chǔ)可以提供高可用性的數(shù)據(jù)，例如，通過(guò)復(fù)制。這減少了服務(wù)器故障后狀態(tài)丟失的可能性，盡管鏈接存儲(chǔ)不提供持久性保證。
?重新切分的支持 鏈接存儲(chǔ)通過(guò)將值重新定位到新分配的密鑰的服務(wù)器來(lái)透明地響應(yīng)來(lái)自自動(dòng)分配器的更改。這可以防止重新分片事件導(dǎo)致?tīng)顟B(tài)丟失，從而提高應(yīng)用程序性能。
?狀態(tài)損失通知 服務(wù)器可能會(huì)失敗，導(dǎo)致?tīng)顟B(tài)丟失(因?yàn)樵谛阅芊矫?，狀態(tài)的持久性無(wú)法得到保證)。為了允許應(yīng)用程序檢測(cè)狀態(tài)丟失，鏈接存儲(chǔ)在重新分片后可能丟失狀態(tài)時(shí)通知應(yīng)用程序。
?新鮮 鏈接存儲(chǔ)可以自動(dòng)檢測(cè)底層數(shù)據(jù)存儲(chǔ)中的更改并使其條目無(wú)效，從而提高數(shù)據(jù)的新鮮度。
4.3 api與架構(gòu)
??鏈路存儲(chǔ)的結(jié)構(gòu)如圖5所示。它位于一個(gè)自動(dòng)分配器上，使用一個(gè)連接到客戶(hù)機(jī)的路由器庫(kù)，將請(qǐng)求從應(yīng)用程序客戶(hù)機(jī)直接發(fā)送到應(yīng)用程序服務(wù)器。應(yīng)用服務(wù)器鏈接一個(gè)新的庫(kù)，稱(chēng)為 LInlet ，它是鏈接存儲(chǔ)的實(shí)現(xiàn);它將所有服務(wù)器端交互封裝在自動(dòng)分配器中，在不同的應(yīng)用服務(wù)器上運(yùn)行的 LINKLET 實(shí)例通過(guò) Rpc 交換狀態(tài)。
?? Linklet 公開(kāi)了一個(gè)新的 API，它提供了對(duì)可變應(yīng)用程序?qū)ο蟮囊谩Ｎ覀冊(cè)趫D4中展示了這個(gè) API 的基本屬性。完整的 API 將包括額外的 surface area，例如，通知應(yīng)用程序狀態(tài)丟失，這超出了本文的范圍。
??該 API 的一個(gè)重要方面是，存儲(chǔ)的值是本機(jī)應(yīng)用程序?qū)ο螅０鍏?shù)V）。 為了使 LInklet 能夠響應(yīng)重新分片事件而傳輸值，應(yīng)用程序必須提供代碼以（解組）其對(duì)象。 開(kāi)發(fā)人員在使用 RInK 存儲(chǔ)時(shí)必須編寫(xiě)（取消）編組代碼，因此此 API 不會(huì)增加額外的負(fù)擔(dān)。 與 RInK 存儲(chǔ)不同，序列化和反序列化不在每個(gè)請(qǐng)求的關(guān)鍵路徑上。
5未解決的問(wèn)題和機(jī)會(huì)
??在本節(jié)中，我們將從兩個(gè)角度分析有狀態(tài)體系結(jié)構(gòu)。首先，我們考慮在使用鏈接存儲(chǔ)為有狀態(tài)架構(gòu)提供一流支持方面仍然存在的挑戰(zhàn)，我們認(rèn)為這些都是研究貢獻(xiàn)的領(lǐng)域，也不是難以解決的問(wèn)題。其次，我們提到鏈接存儲(chǔ)可以啟用的應(yīng)用程序。
5.1 未解決的問(wèn)題
負(fù)載平衡算法:有狀態(tài)架構(gòu)需要跨不同應(yīng)用程序和工作負(fù)載操作的負(fù)載平衡算法。Slicer 有一個(gè)這樣的算法，但遺留的問(wèn)題包括:同時(shí)平衡多個(gè)指標(biāo)、對(duì)應(yīng)用程序重新分片的成本建模、快速識(shí)別負(fù)載的突變并對(duì)其做出反應(yīng)而不引起振蕩。我們相信應(yīng)用控制理論將是新穎和有效的。
復(fù)制:復(fù)制是實(shí)現(xiàn)高可用性的重要技術(shù)。在 RInK 存儲(chǔ)中，復(fù)制可以應(yīng)用于存儲(chǔ)的數(shù)據(jù)并與應(yīng)用程序邏輯隔離。在鏈接存儲(chǔ)中，應(yīng)用程序代碼和數(shù)據(jù)的緊密耦合使問(wèn)題更加復(fù)雜。使用邏輯操作的狀態(tài)機(jī)復(fù)制[19,23]需要確定的應(yīng)用程序代碼(這很難保證)，而使用物理操作則需要編組對(duì)象，從而增加了鏈路存儲(chǔ)試圖避免的成本。確定如何處理這些相互沖突的目標(biāo)是一個(gè)有待解決的問(wèn)題。
最小化應(yīng)用程序占用:上面建議的鏈接實(shí)現(xiàn)依賴(lài)于將大量功能鏈接到應(yīng)用程序本身，這有兩個(gè)缺點(diǎn)。首先，它加大了支持多種語(yǔ)言的難度;其次，由于開(kāi)發(fā)人員必須發(fā)布新的二進(jìn)制文件，這使得修復(fù)鏈接實(shí)現(xiàn)的 bug 變得更加困難。確定可以將多少鏈路體系結(jié)構(gòu)提取到一個(gè)獨(dú)立的 RPC-distance 控制服務(wù)中是一個(gè)待解決的問(wèn)題。
5.2機(jī)遇
更快的無(wú)服務(wù)器:無(wú)服務(wù)器計(jì)算為開(kāi)發(fā)人員提供了對(duì)響應(yīng)事件(例如 AWS Lambda[3])執(zhí)行的函數(shù)的抽象。鏈接存儲(chǔ)可以支持跨調(diào)用保留狀態(tài)的函數(shù)的高性能實(shí)現(xiàn)。
上下文和個(gè)性化:依賴(lài)于每個(gè)用戶(hù)狀態(tài)的應(yīng)用程序(例如，基于對(duì)話(huà)的應(yīng)用程序，如Chrome Home、Amazon Alexa 等)需要會(huì)話(huà)上下文來(lái)回答查詢(xún)。并不是所有的狀態(tài)都必須被持久化。例如，如果服務(wù)器故障和狀態(tài)丟失很少見(jiàn)，那么在鏈接存儲(chǔ)中保存狀態(tài)(比如最后一個(gè)問(wèn)題)，而在持久存儲(chǔ)中保存較長(zhǎng)期的狀態(tài)(比如每個(gè)用戶(hù)的語(yǔ)音識(shí)別模型)可能是有意義的。
6 結(jié)論
在15-20年前，在出現(xiàn)高質(zhì)量的通用自動(dòng)分片系統(tǒng)之前，行業(yè)標(biāo)準(zhǔn)體系結(jié)構(gòu)就已經(jīng)在不斷發(fā)展。我們已經(jīng)討論過(guò)，在構(gòu)建快速鍵值存儲(chǔ)以提高此體系結(jié)構(gòu)的性能方面投入了太多精力，行業(yè)應(yīng)該轉(zhuǎn)向基于有狀態(tài)應(yīng)用程序服務(wù)器或自定義內(nèi)存存儲(chǔ)的體系結(jié)構(gòu)。
有狀態(tài)架構(gòu)通過(guò)避免不必要的網(wǎng)絡(luò)和(un)編組成本來(lái)提供更高的性能，這是以對(duì)基礎(chǔ)架構(gòu)軟件更高的需求為代價(jià)的。為了解決這些需求，我們提出了鏈接存儲(chǔ)并描述了未來(lái)研究的領(lǐng)域。
參考文獻(xiàn)
[1] Apache Cassandra. http://cassandra.apache.org.
[2] Apache HBase. http://hbase.apache.org.
[3] AWS Lambda. https://aws.amazon.com/lambda/.
[4] Edgestore. https://blogs.dropbox.com/tech/2016/08/reintroducing-edgestore.
[5] JVM Serializers. https://github.com/eishay/jvm-serializers/wiki.
[6] Memcached. https://memcached.org.
[7] Redis. https://redis.io.
[8] Ringpop. https://ringpop.readthedocs.io/en/latest.
[9] A. Adya, D. Myers, J. Howell, J. Elson, C. Meek, V. Khemani, S. Fulger, P. Gu, L. Bhuvanagiri, J. Hunter, R. Peon, L. Kai, A. Shraer,
A. Merchant, and K. Lev-Ari. Slicer: Auto-sharding for datacenter applications. In OSDI, 2016.
[10] A. Belay, G. Prekas, A. Klimovic, S. Grossman, C. Kozyrakis, and
E. Bugnion. Ix: A protected dataplane operating system for high throughput and low latency. In OSDI, 2014.
[11] N. Bronson, Z. Amsden, G. Cabrera, P. Chakka, P. Dimov, H. Ding,
J. Ferris, A. Giardullo, S. Kulkarni, H. Li, M. Marchukov, D. Petrov,
L. Puzar, Y. J. Song, and V. Venkataramani. Tao: Facebook’s distributed data store for the social graph. In ATC, 2013.
[12] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach,
M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: A distributed storage system for structured data. In OSDI, 2006.
[13] J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman,
S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh,
S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor,
R. Wang, and D. Woodford. Spanner: Google’s globally-distributed database. In OSDI, 2012.
[14] A. Dragojevi?, D. Narayanan, O. Hodson, and M. Castro. Farm: Fast remote memory. In NSDI, 2014.
[15] B. Fan, D. G. Andersen, and M. Kaminsky. Memc3: Compact and concurrent memcache with dumber caching and smarter hashing. In NSDI, 2013.
[16] A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, and P. Gauthier. Cluster-based scalable network services. In SOSP, 1997.
[17] S. D. Gribble, E. A. Brewer, J. M. Hellerstein, and D. Culler. Scalable, distributed data structures for internet service construction. In OSDI, 2000.
[18] X. Jin, X. Li, H. Zhang, R. Soulé, J. Lee, N. Foster, C. Kim, and I. Stoica. Netcache: Balancing key-value stores with fast in-network caching. In SOSP, 2017.
[19] L. Lamport. The part-time parliament. In TOCS, 1998.
[20] B. Li, Z. Ruan, W. Xiao, Y. Lu, Y. Xiong, A. Putnam, E. Chen, and
L. Zhang. Kv-direct: high-performance in-memory key-value store with programmable nic. In SOSP, 2017.
[21] B. Liskov. The power of abstraction - (invited lecture abstract). In DISC, 2010.
[22] M. Mitzenmacher. The power of two choices in randomized load balancing. In TPDC, 2001.
[23] D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In ATC, 2014.
[24] J. Ousterhout, A. Gopalan, A. Gupta, A. Kejriwal, C. Lee, B. Montazeri,
D. Ongaro, S. J. Park, H. Qin, M. Rosenblum, et al. The ramcloud storage system. In TOCS, 2015.
[25] D. R. K. Ports, A. T. Clements, I. Zhang, S. Madden, and B. Liskov. Transactional consistency and automatic management in an application data cache. In OSDI, 2010.
[26] H. Qin, Q. Li, J. Speiser, P. Kraft, and J. Ousterhout. Arachne: core-aware thread management. In OSDI, 2018.
[27] M. Slee, A. Agarwal, and M. Kwiatkowski. Thrift: Scalable cross-language services implementation. Facebook White Paper, 2007.
