[TOC]

NetCahe:Balancing Key-Value Stores with Fast In-Network Caching

NetCache:利用快速網(wǎng)內(nèi)緩存平衡鍵值存儲系統(tǒng)

出處：SOSP2017

作者：Xin Jin, Xiaozhou Li, Haoyu Zhang, Robert Soulé, Jeongkeun Lee,
Nate Foster, Changhoon Kim, Ion Stoica

單位：Johns Hopkins University, Barefoot Networks, Princeton University,
Cornell University, UC Berkeley

Concept

1.key-value 數(shù)據(jù)庫

• Key-Value鍵值存儲原理初識(NOSQL)
• Key-value數(shù)據(jù)庫比關(guān)系型數(shù)據(jù)庫更加新嗎玖绿？
• 自己動手構(gòu)建Key-Value Store系統(tǒng)
• key-value store
• Key-value存儲簡介
• Key-value數(shù)據(jù)庫比關(guān)系型數(shù)據(jù)庫更加新嗎硫惕？
• Relational DB vs. Key-Value store

2.in-memory 數(shù)據(jù)庫

• 內(nèi)存數(shù)據(jù)庫 (in-memory database) 的發(fā)展現(xiàn)狀和前景如何雹顺？
• 內(nèi)存數(shù)據(jù)庫
• 內(nèi)存數(shù)據(jù)庫優(yōu)劣勢有那些？

3.ASIC（Application Specific Integrated Circuits）是專用集成電路厕鹃，指應特定用戶要求和特定電子系統(tǒng)的需要而設(shè)計兢仰、制造的集成電路，里面的電路結(jié)構(gòu)式固定不可變的剂碴。文中提到的Barefoot Tofino和Broadcom Tomahawk都是內(nèi)置這種電路芯片的交換機把将，可以高速處理網(wǎng)絡數(shù)據(jù)。

4.Cache寫操作策略

由于Cache的內(nèi)容只是主存內(nèi)容的一個子集汗茄，應當與主存內(nèi)容保持一致秸弛，而CPU對Cache的寫入更改了Cache的內(nèi)容铭若。為此洪碳，可選用寫操作策略使Cache內(nèi)容與主存內(nèi)容保持一致。

• 寫回法（Write-Back）叼屠，當CPU寫Cache命中時瞳腌，只修改Cache的內(nèi)容，而不是立即寫入主存镜雨；只有當此塊被換出時才寫回主存嫂侍。使用這種方法寫Cache和寫主存異步進行，顯著減少了訪問主存的次數(shù)荚坞，但是存在數(shù)據(jù)不一致的隱患挑宠。實現(xiàn)這種方法時，每個Cache塊必須配置一個修改位颓影，以反映此塊是否被CPU修改過各淀。
• 全寫法（Write-Through），當寫 Cache命中時诡挂，Cache與主存同時發(fā)生寫修改碎浇。使用這種方法寫Cache和寫主存同步進行，因而較好地維護了Cache與主存的內(nèi)容一致性璃俗。實現(xiàn)這種方法時奴璃，Cache中的每個塊無需設(shè)置修改位以及相應的判斷邏輯，但由于Cache對CPU向主存的寫操作沒有高速緩沖功能城豁，從而降低了Cache的功效苟穆。
• 寫一次法（Write-Once），寫一次法是基于寫回法并結(jié)合全寫法的寫操作策略，寫命中與寫未命中的處理方法與寫回法基本相同雳旅，只是第一次寫命中時要同時寫入主存剖膳，以便于維護系統(tǒng)全部Cache的一致性。

Abstract

• 主題：NetCache岭辣，一種新型的鍵值存儲結(jié)構(gòu)吱晒。
• 作用：利用新一代可編程交換機的靈活性、可編程性處理熱點數(shù)據(jù)條目的查詢沦童，同時平衡存儲結(jié)點間的負載仑濒。
• 效果：1）NetCache即使在高偏斜(負載極度不均)和快速變化的工作負載下依然能同時提供高吞吐量和低延遲的服務。2）同時該解決方案以最低的開銷保證了cache的一致性偷遗。
• 核心：NetCache的核心是一個分組處理管道墩瞳，它利用了現(xiàn)代可編程交換機的功能實現(xiàn)了高效地檢測、索引和處理交換機數(shù)據(jù)區(qū)域內(nèi)的熱數(shù)據(jù)對氏豌。
• 實驗：在Barefoot Tofino交換機以及商用服務器上實現(xiàn)了NetCache的原型喉酌，實驗證明單個交換機能處理每秒2億多的查詢(每個條目64K，16byte鍵泵喘，128byte值泪电？？纪铺？) 相速，同時僅消耗很小一部分的硬件資源。
• 意義：網(wǎng)內(nèi)緩存的應用層研究方面鲜锚，這是首次在可編程交換機上以線性比率運行如此復雜的應用層功能突诬。(？芜繁？旺隙？run at line rate ？骏令？)蔬捷，而且NetCache提高了3到10倍的吞吐量，同時減少40%到50%的查詢延時伏社。

Introduction

1.技術(shù)背景

現(xiàn)代的網(wǎng)絡服務對高性能的鍵值存儲（[key-value store](key-value store)抠刺，key_value分布式存儲系統(tǒng)）非常依賴，甚至往往一個web頁面都需要成百上千次存儲器訪問摘昌，故當用戶量很大時速妖，急劇上升的操作需要依賴內(nèi)存鍵值存儲來滿足吞吐量和延時需求。

ps:簡單說聪黎，就是訪問量太大罕容，不能再直接訪問存儲設(shè)備备恤，改用內(nèi)存緩存的方法解決

2.技術(shù)難點

不論是內(nèi)存緩存還是存儲器結(jié)點做鍵值數(shù)據(jù)對的存儲，都有一個主要的難題锦秒，就是處理偏斜露泊、動態(tài)的工作負載。熱條目的查詢次數(shù)往往比其他條目要多得多旅择，但“熱條目”的集合又會快速變化（時下熱點惭笑、趨勢、內(nèi)容提供方的時限等因素）生真。根據(jù)對facebook的Memcached deployment研究顯示10%的條目占據(jù)了60%到90%的查詢量沉噩。這種偏斜（skew）導致系統(tǒng)負載不均衡，造成系統(tǒng)性能退化柱蟀，吞吐量下降川蒙，響應時間變慢。當服務器采用（per-core sharding长已，每核心分片）技術(shù)處理高并發(fā)訪問時畜眨，以上性能退化問題會被進一步放大。

對于高性能的內(nèi)存數(shù)據(jù)對存儲术瓮，工作負載不均問題尤為急切康聂。傳統(tǒng)的閃存或磁盤存儲器可以通過快速內(nèi)存緩存層來平衡工作負載（在數(shù)據(jù)的實際存儲設(shè)備之上添加一層緩存層，nvram + memory形式）斤斧≡缈伲或者霎烙，采用選擇性副本機制撬讽，比如將熱數(shù)據(jù)條目拷貝到一個額外附加的存儲結(jié)點上，但是這種副本機制需要額外的硬件開銷悬垃，同時需要復雜的機制來處理數(shù)據(jù)的移動游昼、一致性、查詢路由等問題尝蠕，造成系統(tǒng)設(shè)計的復雜性烘豌，提高系統(tǒng)開銷。（比如一種簡單處理方法看彼，查詢的時候先查這個存儲結(jié)點就可以了廊佩，命中率會高很多，但是這個結(jié)點的負載非常高靖榕，對該結(jié)點硬件要求很高标锄，整個系統(tǒng)的性能會受到這個結(jié)點的影響——類似于“短板效應”）

ps:技術(shù)難點：1）in-memory和NVRAM存儲都會存在偏斜、動態(tài)負載造成系統(tǒng)性能退化茁计，降低吞吐量料皇，增加延時的問題。2）針對NVRAM存在兩種解決方案，a）增加cache層践剂，或者b）采用副本機制鬼譬。前者in-memory存儲不適用，后者存在附加的問題逊脯。

4.本文解決方案

本文提出NetCache优质，一種新型的存儲架構(gòu)，利用新一代可編程交換機在網(wǎng)絡中緩存數(shù)據(jù)军洼。交換機在數(shù)據(jù)流動中被充分利用盆赤，相對傳統(tǒng)的存儲服務器提供了更好的性能，為高性能內(nèi)存存儲提供了一個理想的構(gòu)建緩沖層的地點(switch)歉眷。傳統(tǒng)的緩存通常需要很高的緩存命中率（>90%）來承受大部分的查詢牺六，NetCache使用交換機作為均衡負載的緩存，僅需要中等的緩存命中率(<50%)汗捡。熱點數(shù)據(jù)條目使用負載均衡緩存訪問爵卒，使得服務器中剩下的負載更加均勻诚隙。雖然交換機片內(nèi)內(nèi)存有限，NetCache在理論上僅需緩存$O(NlogN)$的條目就足以平衡N個存儲服務器（或CPU核心）的工作負載，通過全部的哈希劃分的鍵值存儲簇爵憎。總的來說车酣，整個系統(tǒng)能保證很高的整體吞吐量和低延時外遇，即使在偏斜工作負載下。

NetCache的核心是一個分組處理管道女阀，它可以檢測宅荤、索引、存儲和查詢數(shù)據(jù)對浸策。使用match-action table(??表)對keys做分類冯键，這些keys由數(shù)據(jù)包頭部攜帶，可編程交換機的片內(nèi)內(nèi)存中存儲values庸汗。利用現(xiàn)代交換機ASICs的多管線多級結(jié)構(gòu)更加有效得索引和壓縮變長的values到有限的交換機表和內(nèi)存資源中惫确。

為了在交換機的數(shù)據(jù)區(qū)平面區(qū)分熱點條目，NetCache為每一個緩存了的key維護一個計數(shù)器蚯舱，以及一個未緩存key的熱數(shù)據(jù)檢測器（heavy-hitter detector改化，heavy-hitter，數(shù)據(jù)流及網(wǎng)絡檢測研究中的常用術(shù)語枉昏，在數(shù)據(jù)流方面陈肛，指頻繁出現(xiàn)的數(shù)據(jù)項，在網(wǎng)絡監(jiān)測中凶掰，通常認為是發(fā)出的數(shù)據(jù)包超過一定閾值的流）燥爷。這里利用了一點蜈亩，交換機自然得處于數(shù)據(jù)路徑上，介入系統(tǒng)的所有查詢前翎。這個熱數(shù)據(jù)檢測器包含一個Count-Min sketch算法（統(tǒng)計一個實時的數(shù)據(jù)流中元素出現(xiàn)的頻率稚配，并且隨時反應某個元素出現(xiàn)的頻率，非精確統(tǒng)計港华，稍大估計）用于報告熱點的但未緩存的keys道川，和一個布隆過濾器（Bloom filter，可以用于檢索一個元素是否在一個集合中立宜，優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法冒萄，缺點是有一定的誤識別率和刪除困難,常用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重）去過濾重復的熱數(shù)據(jù)報告橙数。兩種數(shù)據(jù)結(jié)構(gòu)（counter for cached keys and heavy-hitter detector）都能在交換機的數(shù)據(jù)區(qū)域以線性方式實現(xiàn)尊流，使用最小的資源。熱數(shù)據(jù)檢測器避免了在服務器上獨立建立部署和管理一個用于計數(shù)統(tǒng)計key訪問情況的監(jiān)視組件灯帮。

NetCache架構(gòu)的另一個優(yōu)勢是用很小的開銷就能自動保證緩存一致性崖技。對于交換機緩存的條目的讀請求可以無需訪問存儲服務器直接由交換機處理，而緩存條目的寫請求钟哥，會使所有交換機上存儲的該key的副本條目無效迎献，數(shù)據(jù)存儲服務器會自動更新新的value到交換機上（讀的時候，直接交換機讀腻贰，寫的時候吁恍，不理交換機，在server上更新播演，然后刷新switches）冀瓦。因此，控制平面基于緩存計數(shù)器和熱數(shù)據(jù)檢測報告僅對某些key的插入和刪除操作負責宾巍。

NetCache是易部署的咕幻，它尤為適合當今的rack-scale(機架規(guī)模？)存儲系統(tǒng)（每個機架rack包含上千個核心顶霞，為了更高的性能需求使用每個核心數(shù)據(jù)分庫分表方式。什么情況下使用分布式數(shù)據(jù)庫）锣吼，僅需要安排一個ToR交換機就能增加NetCache的功能选浑，網(wǎng)絡的其他部分不需修改。NetCache完全兼容已有的路由協(xié)議和網(wǎng)絡功能玄叠，我們?yōu)榭蛻舳颂峁┝艘粋€NetCache的庫用于訪問key-value存儲系統(tǒng)古徒，它使用類似于已有的key-value store的API。我們還為存儲服務器提供了一個簡單的中介層（shim layer）读恃，使得已有的key-value存儲系統(tǒng)與NetCache的整合很容易實現(xiàn)隧膘。

總的來說代态，我們做了一下工作：

• 設(shè)計了NetCache，一種新的key-value存儲架構(gòu)疹吃，利用新一代可編程交換機緩存網(wǎng)絡數(shù)據(jù)用以動態(tài)負載均衡蹦疑。（part 3）
• 設(shè)計了一個分組處理管道（packet-processing pipline），能在交換機的數(shù)據(jù)平面上高效得檢測萨驶、索引歉摧、存儲和查詢熱數(shù)據(jù)對，同時實現(xiàn)一種保證緩存一致性的機制腔呜。（part 4）
• 在Barefoot Tofino交換機和商用服務器上實現(xiàn)了NetCache的原型叁温，僅僅使用了Tofino的很小一部分片內(nèi)資源，為傳統(tǒng)的數(shù)據(jù)包處理留下足夠的資源核畴。（part 6）
• 對NetCache原型做了評估實驗膝但，證明NetCache能以直線比率運行在可編程交換機上。并極大提高了性能谤草。（part 7）
• 討論了系統(tǒng)的局限性和可能的解決方案锰镀。（part 5）

ps:這里緊接著之前的描述，傳統(tǒng)存儲系統(tǒng)和內(nèi)存數(shù)據(jù)存儲系統(tǒng)都會遇到共同的問題咖刃，有兩個解決方案泳炉，其一不適合in-memory系統(tǒng)，其二本身存在很多問題嚎杨，接著該部分給出本文的解決方案花鹅，NetCache，利用交換機在網(wǎng)絡中緩存熱數(shù)據(jù)條目枫浙。簡要介紹了NetCache的以下幾個情況：

• 單個switch滿足的命中率要求
• 緩存量刨肃，也是資源占用量
• 核心，packet-process pipline
• 組成箩帚，cached keys' counter + uncached keys’ heavy-hitter detector（包含兩個算法組成真友，counter-min sketch + bloom filter）
• 一致性策略（寫、更改的處理）
• 實際部署難易度

Motivation

NetCahce的提出源于目前高性能內(nèi)存鍵值存儲系統(tǒng)的火熱趨勢紧帕，我們討論認為類似于NetCache這樣在網(wǎng)絡中緩存熱數(shù)據(jù)自然能在高偏斜和動態(tài)的實際工作負載中為內(nèi)存數(shù)據(jù)存儲提供性能和強一致性保證盔然。

1.負載平衡

作為大規(guī)模英特網(wǎng)服務器的關(guān)鍵性構(gòu)建塊，鍵值存儲系統(tǒng)為為十億級的用戶提供服務是嗜，故希望能提供高性能的保證以滿足嚴格的服務等級協(xié)定（service level agreement愈案，簡稱SLA，也稱“服務水平協(xié)議” 服務級別協(xié)議是指提供 服務 的 企業(yè) 與 客戶 之間就服務的 品質(zhì) 鹅搪、水準站绪、 性能等方面所達成的雙方共同認可的協(xié)議或契約）。理想情況下丽柿，如果每個存儲結(jié)點的吞吐量是T恢准，一個具有N個結(jié)點的鍵值存儲系統(tǒng)能保證總體吞吐量為N*T魂挂，已知每個結(jié)點實際處理量不會超過T，且查詢延時有限（不會無限延時阻塞）馁筐，這些性能保證能使服務提供方很容易得擴展存儲系統(tǒng)以滿足特定的SLAs涂召。

然而，真實的工作負載具有動態(tài)和偏斜性眯漩，很難提供上述保證芹扭，熱點數(shù)據(jù)條目查詢次數(shù)遠遠高于其他條目，這會造成系統(tǒng)的失衡赦抖。系統(tǒng)的瓶頸受限于過載的結(jié)點舱卡，導致其他許多結(jié)點不能充分利用，所以整個系統(tǒng)不能到達預期的總體吞吐量队萤。而且轮锥，過載的結(jié)點查詢量高于它能處理的量，造成很高的系統(tǒng)延時要尔。

ps：理想和實際情況下系統(tǒng)的負載和延時在滿足SLA時的差異舍杜，文章討論的技術(shù)的一個實際場景（原因）

2.快速且小量緩存實現(xiàn)負載平衡

緩存是一種有效的減輕負載不均衡的技術(shù)。理論證明赵辕，緩存器僅需存儲O(NlogN)的條目數(shù)就能平衡N個存儲結(jié)點組成的一個key-value哈希劃分簇的負載既绩，而與key-value的條目總數(shù)無關(guān)。具體說还惠，已知N個結(jié)點具有NT的系統(tǒng)總負載饲握，如果緩存能承受所有的查詢的最熱的O(NlogN)的條目，那么極大的可能情況下將沒有結(jié)點會受到超過T的負載蚕键，不論查詢的負載分布如何救欧。由于O(NlogN)相對而言是比較小的，所以熱條目能被拷貝到所有的緩存結(jié)點上以避免在緩存層出現(xiàn)循環(huán)負載平衡問題锣光。雖然O(NlogN)小到足以可分發(fā)到每個客戶端笆怠，但是保證緩存一致性很難，如果有許多用戶訪問一個共同的熱數(shù)據(jù)集誊爹，但這個集并不是對每個用戶都是最熱的蹬刷，那么用戶緩存就不會從這種緩存機制中受利。因此替废，在存儲服務器上構(gòu)建緩存層是更有效的箍铭。（ps：這里主要是動態(tài)問題，熱點是變得椎镣，比如，hot items set分發(fā)到每個用戶兽赁，但是此后活躍用戶會的頻繁訪問會改變這個hot set状答，對于非活躍用戶的hot set緩存來說冷守，它緩存的數(shù)據(jù)失效了，故只能在用戶到存儲服務器之間建立一個cache layer*）

為了處理偏斜的工作負載惊科，緩存層必須根據(jù)存儲層提供一個總體吞吐量拍摇。(大致這樣一個比例，緩存結(jié)點*每個結(jié)點的負載 約等于= 存儲節(jié)點*每個結(jié)點的負載)馆截。故負載近似時充活，緩存結(jié)點數(shù)需要和存儲結(jié)點數(shù)近似，這成本太高蜡娶，開銷也高混卵，因為存儲結(jié)點熱數(shù)據(jù)的修改要更新到每一個緩存結(jié)點上。因此為了構(gòu)建高效率低開銷的緩存層窖张，需要緩存結(jié)點的負載遠高于存儲結(jié)點的負載幕随。（緩存層的緩存結(jié)點負載需求）

ps：該部分介紹如何通過緩存平衡負載，為何需要緩存層宿接，以及緩存層的負載要求

3.內(nèi)存存儲系統(tǒng)的網(wǎng)絡緩存

內(nèi)存緩存對于flash或disk存儲系統(tǒng)很有效赘淮，因為DRAMs比SSDs或者HDDs快的多，但是當數(shù)據(jù)庫本身就是內(nèi)存數(shù)據(jù)庫睦霎，那么內(nèi)存緩存就不再有效了梢卸。一個內(nèi)存鍵值存儲系統(tǒng)有128個服務器，每個提供一千萬QPS（每秒查詢率副女，以每秒查詢量衡量）蛤高，那么系統(tǒng)總體能到達12.8億的QPS吞吐量，緩存層需要提供相對應的吞吐量肮塞。

將緩存層建立在網(wǎng)絡中是一種很自然的解決方案襟齿。交換機能夠被IO充分利用。交換機有足夠的處理能力枕赵，而且不需要額外添加硬件猜欺，不會有額外的延遲懲罰。另外FPGA或者NPU（Neural-network Processing Unit拷窜，嵌入式神經(jīng)網(wǎng)絡處理器）要么部署不方便开皿，要么吞吐量達不到，要么太昂貴篮昧。

4.用于網(wǎng)絡緩存的可編程交換機

現(xiàn)代的商用交換機具有數(shù)十MB的片內(nèi)內(nèi)存赋荆，而鍵值存儲系統(tǒng)的values通常很小，故交換機足以在內(nèi)存中存儲O(NlogN)的數(shù)據(jù)用于平衡負載懊昨，同時留有足夠的資源處理傳統(tǒng)的網(wǎng)絡功能窄潭。而對于大value，可以采用數(shù)據(jù)包劃分的方式解決酵颁。(large item divided into smaller chunks to multiple packets)

傳統(tǒng)交換機的ASIC處理電路功能固定嫉你，添加新功能需要重新設(shè)計制造新的ASIC月帝，但新一代可編程交換機的ASIC允許用戶編程控制分組處理管道而不需要替換交換機的ASIC。

• 可編程控制交換機識別特定的數(shù)據(jù)包格式幽污，custom packet formats
• 可編程實現(xiàn)片內(nèi)內(nèi)存存儲特定狀態(tài)（熱數(shù)據(jù)及查詢統(tǒng)計）
• 可編程switch table去執(zhí)行特定操作嚷辅，如從內(nèi)存中復制value到packets中，或者detect heavy hitters

ps：本節(jié)介紹了NetCache的設(shè)計動機距误、思路簸搞。從問題產(chǎn)生（實際workload通常不能滿足SLA，到最終采用可編程交換機建立網(wǎng)絡cache layer解決問題）

NetCache Overview

假設(shè)整個機架用于鍵值存儲系統(tǒng)准潭，數(shù)據(jù)條目key-value采用哈希劃分到存儲服務器上趁俊。使用ToR交換機連接到服務器，作為負載平衡緩存層惋鹅。整個系統(tǒng)由ToR交換機则酝、控制器、存儲服務器三部分組成闰集。

1.Switch

交換機是NetCache的核心組件沽讹，負責實現(xiàn)路徑上的item緩存（on-path caching）以及傳統(tǒng)的數(shù)據(jù)包路由工作（L2/L3協(xié)議）。本文預留了L4端口用于區(qū)分NetCache數(shù)據(jù)包武鲁，這樣可以和傳統(tǒng)網(wǎng)絡協(xié)議和功能兼容爽雄。

cache模塊存儲熱數(shù)據(jù)，讀請求直接由switch處理沐鼠，寫請求會繼續(xù)分發(fā)到存儲服務器上挚瘟。緩存一致性由一種輕量級的“直寫”機制（write-though，直寫模式饲梭，在數(shù)據(jù)更新時乘盖，同時寫入緩存Cache和后端存儲。此模式的優(yōu)點是操作簡單憔涉；缺點是因為數(shù)據(jù)修改需要同時寫入存儲订框，數(shù)據(jù)寫入速度較慢，對應的有write-back兜叨，回寫模式）來保證穿扳。

查詢統(tǒng)計模塊給controller提供key-access的統(tǒng)計，用于緩存更新（熱數(shù)據(jù)集更新）国旷。這實現(xiàn)了NetCache平衡動態(tài)負載矛物。它包含兩部分：1）cached items’ per-key counters。2）heavy hitter detector to identify hot keys which uncached跪但。

switch是一個讀緩存履羞，switch宕機后，重啟或直接采用后備ToR交換機即可，NetCache緩存量很小吧雹，重啟后可以很快得refill骨杂。

ps：本節(jié)介紹了NetCache的關(guān)鍵組件switch的兩個主要功能模塊（存儲涂身、檢測動態(tài)熱數(shù)據(jù)）雄卷，以及容災問題（簡單，直接重啟蛤售？丁鹉？這里關(guān)注一下下文的cache一致性如何解決，交換機重啟后cache為空悴能，如何同步cache）

2.Controller

控制器主要負責更新緩存（熱數(shù)據(jù)）揣钦，它接受HH reports（熱數(shù)據(jù)報告，heavy-hitter通過兩個算法檢測去重后發(fā)出該報告）漠酿，然后對比cached keys‘ counter冯凹，決定哪些該插入cache，哪些刪除炒嘲。

3.Storage servers

兩個功能：1）映射NetCache packets到鍵值數(shù)據(jù)庫的API宇姚，簡單說就是什么packet該做什么操作。2）實現(xiàn)cache和storage的一致性策略夫凸。一種中間件的形式使得NetCache很容易整合到內(nèi)存數(shù)據(jù)庫中浑劳。

4.Clients

NetCache提供給用戶一個client library，應用可以使用該庫訪問遠程數(shù)據(jù)存儲服務器夭拌，該庫的接口與已有的數(shù)據(jù)庫接口類似魔熏。

ps：這部分簡要描述了NetCache的各個組成部分及其功能

NetCache Design

1.網(wǎng)絡協(xié)議

a）包結(jié)構(gòu)：NetCache屬于應用層協(xié)議，嵌入到L4數(shù)據(jù)包的負載中鸽扁，與其他的key-value存儲系統(tǒng)一樣蒜绽，使用UDP進行讀請求以滿足低延時，使用TCP進行寫請求以保證可靠性桶现。NetCache字段包含在TCP/UDP數(shù)據(jù)包的負載中躲雅，并為NetCache保留了一個特定的TCP/UDP端口。NetCache交換機使用這個端口調(diào)用特定的packet處理邏輯巩那，其他交換機不用了解NetCache的數(shù)據(jù)格式吏夯，正常處理packet就可以了。

b）網(wǎng)絡路由：NetCache利用已有的路由協(xié)議轉(zhuǎn)發(fā)數(shù)據(jù)包即横。NetCache對于整個而言是透明的噪生，僅在NetCache交換機上處理NetCache的部分。這樣它和其他的網(wǎng)絡協(xié)議和功能能共存东囚。

2.請求處理

NetCache的一個關(guān)鍵優(yōu)勢就是網(wǎng)絡路徑中的緩存提供了直接的處理跺嗽。讀請求直接由路由器處理而無需交付到存儲服務器，具有很低的延時，寫請求直接交付到存儲服務器桨嫁，中間無額外性能開銷植兰。

a）處理讀請求：1）檢查cache命中，且valid璃吧，在packet header添加value字段楣导，從cache中取出value設(shè)置到字段上，增加該key的counter畜挨，交換packet header的源地址和目的地址筒繁，作為reply返回packet到用戶端。2）若沒有命中巴元，HH detector計數(shù)毡咏，如果是hot數(shù)據(jù)就通知controller。非hot數(shù)據(jù)及新的未緩存的hot key逮刨，轉(zhuǎn)發(fā)到服務器呕缭，由服務器處理。

b）處理寫請求：檢查cache是否存在修己，是則將cache中的value置無效恢总，防止接下來的請求從cache讀取到舊版本的該數(shù)據(jù)。寫請求之后發(fā)送到服務器由服務器處理箩退。

3.緩存一致性及緩存更新

1.緩存一致性

“直寫”方式保證緩存一致性离熏。當寫請求的key是已緩存的，switch會將緩存的value置無效戴涝，然后修改packet header的操作字段為一個特殊值以通知服務器滋戳，本次請求的key是緩存在cache中的（服務器除了更新，還需要對switch做同步）啥刻。

服務器會更新本次寫請求的數(shù)據(jù)奸鸯，然后直接reply給client，不等待switch更新可帽。同時服務器會從packet header識別這次更新的key在switch中有緩存娄涩，故會給switch發(fā)送another packet去更新switch。本次更新對應的switch沒有更新之前映跟，所有后續(xù)同一key的寫請求會被服務器阻塞蓄拣，以保證服務器和cache的一致性。switch的update完成之后努隙，item重新valid球恤，可以為后續(xù)的read queries服務。

2.緩存更新

為了處理動態(tài)工作負載荸镊，控制器頻繁更新緩存咽斧。存在的主要問題是有限的交換表和注冊更新速率堪置。解決方案是由于NetCache僅需要50%的命中率，所以不用每一次請求到達都調(diào)整cache张惹，做一個熱度篩選舀锨，HH detection實現(xiàn)，足夠熱才會去調(diào)整cache宛逗。這樣降低了處理量坎匿。

4.交換機數(shù)據(jù)平面設(shè)計

1.Switch Data Plane

主要包含三個部分：入口管道，流量控制拧额，出口管道碑诉。一個交換機有多個出入口管道，一個管道又有多個端口（接口）侥锦。packet到達入口ingress pipe，先由入口的tables處理德挣，然后在traffic manager中排隊分發(fā)到出口egress pipe恭垦，最后由出口管道發(fā)送出去。

每個管道有三段（stage）格嗅，三段按序處理番挺，三段通過共享packet的header中的fields實現(xiàn)信息傳遞協(xié)同工作。每一段都有特定的tables屯掖，去匹配packet中特定的部分（a few header fields）玄柏，然后做相應的action。

可編程交換機允許開發(fā)者自定義packet格式贴铜，指定自定義的處理流程粪摘，通過指定每個stage的table和它相匹配的fields及action。通過P4編寫交換機程序绍坝，由交換機廠商提供的編譯器編譯P4程序到交換機能識別的二進制文件徘意。

2.Variable-Length On-chip Key-Value Store

NetCache將key-value條目存儲在每個stage內(nèi)的memory的register array中，通過這個memory位置的索引可以直接線性的找到或更新該item轩褐。（流程：match-action table對packet header中的key做匹配椎咧，得到action data，即index把介，通過index及packet header中的operation type對memory中的數(shù)據(jù)做相應處理）

由于硬件資源問題勤讽，每個stage的每個register array從每個packet中讀寫的數(shù)據(jù)長度是固定的，故針對變長的items的values拗踢，需要使用多個register array脚牍，然后從多個stages中提取組合成一個大的value。這里就涉及到如何設(shè)計以實現(xiàn)最高的效率秒拔。我們的設(shè)計方式是使用一個lookup table對每個key做匹配莫矗，包含一個bitmap指示這個key對應的value所在的arrays的集合飒硅，一個index指示具體的value的data所在的arrays的location（每個register array處理的是同一個index）。

內(nèi)存管理 ：NetCache的controller管理register array的index和item之間的映射作谚。之后就是策略算法進行裝箱問題（箱就是arrys的各個index三娩，物品就是不同長度的values）

3.請求統(tǒng)計

請求統(tǒng)計模塊包含三個組件：cached items' counters、Count-Min sketch妹懒、Bloom filter雀监。三個組件都通過哈希函數(shù)構(gòu)建在交換機數(shù)據(jù)平面的register arrays上（內(nèi)存上）。

一個已緩存的item請求到來（key命中）眨唬，那么它對應的counter array的index上的元素+1.

Count-Min sketch（計數(shù)最小略圖）由4個register arrays組成会前，它用四個獨立的哈希函數(shù)將一個key映射到arrays的4個index上，統(tǒng)計的時候這4個位置都+1匾竿，查詢的時候采用最小的那個值作為該key的frequency（4個index的元素值中最小的）（防止哈希沖突）瓦宜，當這個frequency值超過一個閾值值，就認為是hot的岭妖，就需要向controller發(fā)送report临庇。

Bloom filter作用就是防止一個uncached key多次report給controller，減少了不必要的開銷昵慌。

4.Put Everything Together:Pipeline Layout

所有入口管道復制一份同樣的lookup table做key的match假夺，出口管道僅存儲該管道對應的port鏈接的數(shù)據(jù)服務器的cached items' values。

之后就是各種類型key（是否是NetCache請求斋攀，已緩存已卷，未緩存，有效或無效）的流動情況淳蔼。

DISCUSSION

NetCache的一些缺陷侧蘸，如它只針對單個服務器機架rack，不支持長度的key肖方，不支持太大的value闺魏，不能很好的處理極度偏斜的負載，不能處理寫密集型工作負載俯画。

1.多機架服務器組的負載平衡問題析桥。將NetCache交換機假設(shè)到更高的關(guān)口上，當然也需要更強大的硬件資源艰垂。

2.突破定長key的限制泡仗。通過將變長key映射到定長的hash key實現(xiàn)，需要處理hash碰撞問題猜憎，更加復雜娩怎。

3.密集寫的工作負載問題。直接在switch進行hot item的寫操作胰柑。但是要做容災處理和一致性處理截亦。

Evaluation

結(jié)論

• NetCache可以在可編程交換機上at line rate運行
• 提供巨大的性能提升爬泥，在吞吐量和延時方面
• 有效得處理很大范圍的動態(tài)負載

細節(jié)：略

PPT概要

• 相關(guān)知識介紹：分布式-內(nèi)存-鍵值數(shù)據(jù)服務器、switch崩瓤、cache同步袍啡。
• NetCache主要思想：問題-解決方案。
• 問題場景
• 已有方案
• NetCache方案
• NetCache設(shè)計細節(jié)却桶，按各個組件的構(gòu)成
• 總體的工作流程境输，按不同類型的query的流動描述
• 實驗方法及性能提升結(jié)果
• 不足之處及可能的改進方案