系統(tǒng)架構(gòu)領(lǐng)域的一些學(xué)習(xí)材料
系統(tǒng)架構(gòu)是一個工程和研究相結(jié)合的領(lǐng)域，既注重實踐又依賴?yán)碚撝笇?dǎo)，入門容易但精通很難，有時候還要講點悟性，很具有“偽科學(xué)”的特征。要在此領(lǐng)域進(jìn)階，除了要不斷設(shè)計并搭建實際系統(tǒng)，也要注意方法論和設(shè)計理念的學(xué)習(xí)和提煉。
經(jīng)常有同學(xué)詢問如何學(xué)習(xí)，特貼一篇學(xué)習(xí)材料，供大家參考。09年時寫的，在系統(tǒng)領(lǐng)域浩如煙海的文獻(xiàn)中提取了一些我認(rèn)為值得研究和學(xué)習(xí)的項目，沒包括近幾年出現(xiàn)的一些工作，也不夠全面。不過，其實也足夠了，看paper是一個從少到多再到少的過程。對問題本質(zhì)、背景和發(fā)展歷史有大致了解，再輔以hands-on的實踐（長期的真正的實踐），足以摸到本領(lǐng)域的門徑。
此文在網(wǎng)上轉(zhuǎn)載不少，但多數(shù)沒有說明出處。今天（@林仕鼎）在這里重發(fā)，也順便向315致敬。
對于工程師來說，到一定階段后往往會遇到成長瓶頸。要突破此瓶頸，需要在所屬技術(shù)領(lǐng)域更深入學(xué)習(xí)，了解本領(lǐng)域的問題本質(zhì)、方法論與設(shè)計理念、發(fā)展歷史等。以下提供一些架構(gòu)相關(guān)領(lǐng)域的學(xué)習(xí)材料，附上簡單點評，供有興趣的工程師參考。希望大家能通過對這些領(lǐng)域的了解和學(xué)習(xí)，掌握更多system design principles，在自己的工作中得心應(yīng)手，步入自由王國。
1. Operating Systems
Mach [Intro: http://www-2.cs.cmu.edu/afs/cs/project/mach/public/www/mach.html,Paper: http://www-2.cs.cmu.edu/afs/cs/project/mach/public/www/doc/publications.html]
傳統(tǒng)的kernel實現(xiàn)中，對中斷的響應(yīng)是在一個“大函數(shù)”里實現(xiàn)的。稱為大函數(shù)的原因是從中斷的入口到出口都是同一個控制流，當(dāng)有中斷重入發(fā)生的時候，實現(xiàn)邏輯將變得非常復(fù)雜。大多數(shù)的OS，如UNIX，都采用這種monolithic kernel architecture。
1985年開始的Mach項目，提出了一種全新的microkernel結(jié)構(gòu)，使得由于70年代UNIX的發(fā)展到了極致而覺得后續(xù)無枝可依的學(xué)術(shù)界頓時找到了興奮點，也開始了沸沸揚(yáng)揚(yáng)的monokernel與microkernel的爭論。
插播一個花絮：Mach的主導(dǎo)者Richard Rashid，彼時是CMU的教授，受BillGates之托去游說JimGray加盟MS。結(jié)果把自己也被繞了進(jìn)來，組建了Microsoft Research。他到中國來做過幾次21Century Computing的keynotes。
Exokernel [Intro:http://pdos.csail.mit.edu/exo/，Paper:http://pdos.csail.mit.edu/PDOS-papers.html#Exokernels]
雖然microkernel的結(jié)構(gòu)很好，但實際中并沒有廣泛應(yīng)用，因為performance太差，而且大家逐漸發(fā)現(xiàn)OS的問題并不在于實現(xiàn)的復(fù)雜性，而更多在于如何提高application使用資源的靈活性。這也就是在kernel extension（例如loadable module in Linux）出現(xiàn)后，有關(guān)OS kernel architecture的爭論就慢慢淡出人們視線的原因。
Exokernel正是在這樣的背景中出現(xiàn)的，它并不提供傳統(tǒng)OS的abstraction（process,virtual memory等），而是專注于資源隔離與復(fù)用（resource isolation and multiplexing），由MIT提出。在exokernel之上，提供了一套庫，著名的libOS，用于實現(xiàn)各種OS的interface。這樣的結(jié)構(gòu)為application提供了最大的靈活度，使不同的application可以或?qū)Ｗ⒂谡{(diào)度公平性或響應(yīng)實時性，或?qū)Ｗ⒂谔岣哔Y源使用效率以優(yōu)化性能。以今天的眼光來看，exokernel更像是一個virtual machine monitor。
Singularity [Intro:http://research.microsoft.com/os/Singularity/,Paper: http://www.
research.microsoft.com/os/singularity/publications/HotOS2005_BroadNewResearch.pdf]
Singularity出現(xiàn)在virus，spyware取之不盡、殺之不絕的21世紀(jì)初期，由Microsoft Research提出。學(xué)術(shù)界和工業(yè)界都在討論如何提供一個trust-worthy computing環(huán)境，如何使計算機(jī)系統(tǒng)更具有manage-ability。Singularity認(rèn)為要解決這些問題，底層系統(tǒng)必須提供hardisolation，而以前人們都依賴的硬件virtual memory機(jī)制并無法提供高靈活性和良好性能。在.Net和Java等runtime出現(xiàn)之后，一個軟件級的解決方案成為可能。
Singularity在microkernel的基礎(chǔ)上，通過.Net構(gòu)建了一套type-safed assembly作為ABI，同時規(guī)定了數(shù)據(jù)交換的message passing機(jī)制，從根本上防止了修改隔離數(shù)據(jù)的可能。再加上對application的安全性檢查，從而提供一個可控、可管理的操作系統(tǒng)。由于.NetCLR的持續(xù)優(yōu)化以及硬件的發(fā)展，加了這些檢查后的Singularity在性能上的損失相對于它提供的這些良好特性，仍是可以接受的。
這種設(shè)計目前還處于實驗室階段，是否能最終勝出，還需要有當(dāng)年UNIX的機(jī)遇。
2. Virtual Machines
VMWare ["MemoryResource Management in VMware ESX Server"，OSDI’02,Best paper award]
耳熟能詳?shù)膙mware，無需多說。
XEN [“Xen and the Art of Virtualization”, OSDI’04]
性能極好的VMM，來自Cambridge。
Denali [“Scaleand Performance in the Denali Isolation Kernel”, OSDI’02, UW]
為internetservices而設(shè)計的application level virtual machine，在普通機(jī)器上可運(yùn)行數(shù)千個VMs。其VMM基于isolation kernel，提供隔離，但并不要求資源分配絕對公平，以此減少性能消耗。
Entropia [“The Entropia VirtualMachine for Desktop Grids”, VEE’05]
要統(tǒng)一利用公司內(nèi)桌面機(jī)器資源來進(jìn)行計算，需要對計算任務(wù)進(jìn)行良好的包裝，以保證不影響機(jī)器正常使用并與用戶數(shù)據(jù)隔離。Entropia就提供了這樣的一個計算環(huán)境，基于windows實現(xiàn)了一個application level virtual machine。其基本做法就是對計算任務(wù)所調(diào)用的syscall進(jìn)行重定向以保證隔離。類似的工作還有FVM：“AFeather-weight Virtual Machine for Windows Applications”。
3. Design Revisited
“Are Virtual Machine Monitors Microkernels Done Right?”，HotOS’05
這個題目乍聽起來，十分費(fèi)解，其意思是VMMs其實就是Microkernel的正確實現(xiàn)方法。里面詳細(xì)討論了VMM和Microkernel，是了解這兩個概念的極好參考。
“Thirty Years Is Long Enough: Getting Beyond C”, HotOS’05
C可能是這個世界上最成功的編程語言，但其缺點也十分明顯。比如不支持thread，在今天高度并行的硬件結(jié)構(gòu)中顯得有點力不從心，而這方面則是functional programming language的長處，如何結(jié)合二者的優(yōu)點，是一個很promising的領(lǐng)域。
4. Programming Model
單使用thread結(jié)構(gòu)的server是很難真正做到高性能的，原因在于內(nèi)存使用、切換開銷、同步開銷和保證鎖正確性帶來的編程復(fù)雜度等。
“SEDA: An Architecture for Well-Conditioned, Scalable Internet Services”，OSDI’01
Thread不好，但event也沒法解決所有問題，于是我們尋找一個結(jié)合的方法。SEDA將應(yīng)用拆分為多個stage，不同stage通過queue相連接，同一個stage內(nèi)可以啟動多個thread來執(zhí)行queue中的event，并且可通過反饋來自動調(diào)整thread數(shù)量。
Software Transactional Memory
如果內(nèi)存可以提供transaction語義，那么我們面對的世界將完全兩樣，language, compiler, OS, runtime都將發(fā)生根本變化。雖然intel現(xiàn)在正在做hardware transactional memory，但估計可預(yù)見的將來不會商用，所以人們轉(zhuǎn)而尋求軟件解決方案。可想而知，這個方案無法base在native assembly上，目前有C#,haskell等語言的實現(xiàn)版本。資料比較多，參見Wikipedia。
5. Distributed Algorithms
Logical clock, [“Time,clocks, and the ordering of events in a distributed system”, Leslie Lamport, 1978]
這是一篇關(guān)于Logic clock, time stamp, distributed synchronization的經(jīng)典paper。
Byzantine [“The ByzantineGenerals Problem”, Leslie Lamport, 1982]
分布式系統(tǒng)中的錯誤各種各樣，有出錯就能停機(jī)的，有出錯了拖后腿的，更嚴(yán)重的是出錯了會做出惡意行為的。最后的這種malicious behavior，就好像出征將軍的叛變，將會對系統(tǒng)造成嚴(yán)重影響。對于這類問題，Lamport提出了Byzantine failure model，對于一個由3f+1個replica組成的statemachine，只要叛變的replica數(shù)量小于等于f，整個state machine還能正常工作。
Paxos [“The part-time parliament”, Leslie Lamport, 1998]
如何在一個異步的分布式環(huán)境中達(dá)成consensus，這是分布式算法研究的最根本問題。Paxos是這類算法的頂峰。不過這篇paper太難了，據(jù)說全世界就3.5人能看懂，所以Lamport后來又寫了一篇普及版paper：“Paxos Made Simple” ，不過還是很難懂。另外，也可參看Butler Lampson寫的“The ABCD’s of Paxos”（PODC’01），其中關(guān)于replicated state machine的描述會嚴(yán)重啟發(fā)你對并行世界本質(zhì)的認(rèn)識，圖靈獎的實力可不是蓋的。
這上面反復(fù)出現(xiàn)了一個名字：Leslie Lamport，他在distributed computing這個領(lǐng)域挖坑不輟，終成一代宗師。關(guān)于他，也有幾則軼事。記得以前他在MSR的主頁是這么寫的，“當(dāng)我在研究logicalclock的時候，BillGates還穿著開襠褲(in diaper)…”（大意如此，原文現(xiàn)在找不到了）。另外，他在寫paper的時候，很喜歡把其他牛人的名字變換一下編排進(jìn)去。這可能也是他還沒拿到圖靈獎的原因。
關(guān)于Lamport的其他成就，還可以參見這篇向他60歲生日獻(xiàn)禮的paper：“Lamport on mutual exclusion: 27 years of planting seeds”, PODC’01。
6. Overlay Networking, and P2P DHT
RON [“Resilient Overlay Networks”, SOSP’01]
RON描述了如何在應(yīng)用層搭建一個overlay，以提供秒級廣域網(wǎng)網(wǎng)絡(luò)層故障恢復(fù)速度，而現(xiàn)有的通過路由協(xié)議來恢復(fù)通信的時間至少在幾十分鐘。這種快速恢復(fù)特性和靈活性使得overlay networking現(xiàn)在被廣泛應(yīng)用。
Application Level Multicast
“End System Multicast”, SigMetrics’00
“Scalable Application Layer Multicast”, SigComm’02
關(guān)于ALM的paper很多，基本上都是描述如何搭建一個mesh network用以魯棒的傳輸控制信息，另外再搭建一個multicast tree用以高效傳輸數(shù)據(jù)，然后再根據(jù)多媒體數(shù)據(jù)的特點做一些layered delivery。前幾年出現(xiàn)的coolstream, pplive等系統(tǒng)都是這類系統(tǒng)的商業(yè)化產(chǎn)品。
P2P
P2P的出現(xiàn)改變了網(wǎng)絡(luò)。按照各種P2P網(wǎng)絡(luò)的結(jié)構(gòu)，可以分為三種。
1. Napster式，集中式目錄服務(wù)，數(shù)據(jù)傳輸Peer to peer。
2. Gnutella式，通過在鄰居間gossip來查詢，也被稱為unstructured P2P。
3. DHT，與unstructured P2P不同的是，DHT進(jìn)行的查詢有保證，如果數(shù)據(jù)存在，可在一定的hop數(shù)內(nèi)返回。這個hop數(shù)通常為logN，N為系統(tǒng)節(jié)點數(shù)。
典型的DHT有CAN, Chord,Pastry, Tapestry等四種。這些研究主要在算法層面，系統(tǒng)方面的工作主要是在其上建立廣域網(wǎng)存儲系統(tǒng)。還有一些人在機(jī)制層面進(jìn)行研究，例如如何激勵用戶共享、防止作弊等。
7. Distributed Systems
GFS/MapReduce/BigTable/Chubby/Sawzall
Google的系列paper，大家比較熟悉，不再多說。在此可查。
Storage
Distributed storage system的paper太多了。下面列出幾篇最相關(guān)的。
“Chain Replication for Supporting High Throughput and Availability”, OSDI’04。
“Dynamo: Amazon’s Highly Available Key-value Store”，SOSP’07。
“BitVault: a Highly Reliable Distributed Data Retention Platform”, SIGOPS OSR’07。
“PacificA: Replication inLog-Based Distributed Storage Systems”, MSR-TR。
Distributed Simulation
“Simulating Large-Scale P2P Systems with the WiDS Toolkit”, MASCOTS’05。Distributed simulation有意思的地方是simulated protocol是distributed的，而這個simulation engine本身也是distributed的。Logical和physical的time和event交雜在系統(tǒng)中，需要仔細(xì)處理。
8. Controversial Computing Models
現(xiàn)在的軟件系統(tǒng)已經(jīng)復(fù)雜到了人已經(jīng)無法掌握的程度，很多系統(tǒng)在發(fā)布時都仍然帶著許多確定性(deterministic)或非確定性(non-deterministic)的bugs，只能不斷的patch。既然作為人類，不夠精細(xì)的特性決定了我們無法把系統(tǒng)的bug fix干凈，我們只能從其他角度入手研究一種讓系統(tǒng)在這令人沮喪的環(huán)境中仍能工作的方法。這就像一個分布式系統(tǒng)，故障無法避免，我們選擇讓系統(tǒng)作為整體來提供高可靠性。
以下3個便是典型代表。基本上，主要研究內(nèi)容都集中于1) 如何正確保存狀態(tài)；2)如何捕捉錯誤并恢復(fù)狀態(tài)；3)在進(jìn)行單元級恢復(fù)時，如何做到不影響整體。
Failure oblivious computing, OSDI’04
Treating Bugs as Allergies, SOSP’05
9. Debugging
系統(tǒng)很復(fù)雜，人類無法從邏輯上直接分析，只能通過data mining的方法在宏觀上進(jìn)行觀察。
Black box debugging[“Performance debugging for distributed systems of black boxes”, SOSP’03]
對大型系統(tǒng)的performance debugging非常困難，因為里面的問題很多都是非確定性的，而且無法重現(xiàn)。只能通過對log的挖掘，找出配對的調(diào)用/消息以定位問題。
CP-miner [“A Tool for Finding Copy-paste and Related Bugs in Operating System Code”, OSDI’04]
很多人在重用代碼的時候，都使用copy-paste。但有時候簡單的CP會帶來嚴(yán)重的問題，例如局部變量的重名等。CP-miner通過分析代碼，建立語法樹結(jié)構(gòu)，然后mine出這類錯誤。
