愛鋒貝

• 字節(jié)碼的底層表示
  
• 匯編語言的理解
  
• x86架構(gòu)的指令執(zhí)行
  
• 內(nèi)存結(jié)構(gòu)與布局
  
• 硬件緩存與策略
  
• 虛擬內(nèi)存的架構(gòu)實現(xiàn)
  
• 信號、中斷、異常
  
• 基礎(chǔ)網(wǎng)絡(luò)通信
  
• 基礎(chǔ)并發(fā)編程
  

• data lab是熱身lab, 熟悉一下各種位運算的小tricks
  
• cache lab是寫一個in-memory cache
  
• malloc lab是在一個虛擬出來的heap上分配管理內(nèi)存, 需要由簡到難逐步實現(xiàn)implicit list, explicit list 和 segregate list 外加一些mini-block管理的優(yōu)化. 是所有l(wèi)ab里代碼量上最多的一個, 大概得有1500-2000行左右最后.
  
• shell lab是要實現(xiàn)一個terminal, 能支持前端/后端運行指令. 這個lab是個人覺得最詭異的一個, 因為本身對signal信號不是很了解, 做的時候有點懵懂, 犯了好多race condition的錯. 但其實做完后吧, 還是感覺對signal信號有點心里發(fā)怵, 敬而遠(yuǎn)之.
  
• proxy lab是要實現(xiàn)一個坐落于client和server中間的網(wǎng)絡(luò)代理層來進(jìn)行緩存, 加快服務(wù)器的響應(yīng)時間. 這個lab其實是比較輕松的, 因為底層套接字socket都被提供的starter code封裝好了, 很大程度上調(diào)包就完事兒了.
  

• AutoScaling: 讓你用Amazon AWS的Java或Python API集來監(jiān)考你的cluster的workload, 如果高了就要加機(jī)器, 如果低了就要減機(jī)器, 最后根據(jù)滿足的requests數(shù)量和VM的時間總和來算分. 中規(guī)中矩的一個project, 代碼量倒是不少, 需要仔細(xì)的閱讀Amazon AWS的API手冊
  
• Web Tier: 這個project主要是讓我們熟悉Web的不同tier的結(jié)構(gòu)和使用Helm來操作K8S cluster. 最終是需要為了容災(zāi)的考慮, 把服務(wù)器同時部署在Microsoft Azure和Google GCP的云上, 并分流. 還是比較讓人開眼界的
  
• Database: 這個project是讓我們操練不同的database. 從正常的relational的MySQL開始, 然后是NoSQL的HBase, 最后是GraphSQL. 感覺還是比較有趣的, 工作量中等
  
• Large-Scale Processing: 這個project是讓人用Spark做一個PageRank的算法. 要求用Scala完成. 非常的簡單, 代碼加起來不超過50行就能做得到. 之前從沒用過Scala, 稍微看了一會兒入門手冊, 函數(shù)式編程倒是讓人感覺有點意思.
  
• Kafka/Samza: 這個project是讓人操作流式Streaming數(shù)據(jù)的. 具體的是說有一個打車軟件, 你需要實時匹配乘客和司機(jī)并更新大家的位置. 純調(diào)Apache Kafka和Samza的包, 問題不是很大, 還算挺有意思的.
  
• Machine Learning: 沒做. 只需要完成6個projects里的5個, 由于我前5個都做了, 這個直接跳過沒做.
  

• 數(shù)據(jù)存儲形式與壓縮
  
• 哈希索引和B+數(shù)索引
  
• 并發(fā)管理算法
  
• 排序、集合、Join的不同算法
  
• Two-Phase Locking
  
• Timestamp Locking
  
• MVCC
  
• 故障恢復(fù)
  
• 分布式數(shù)據(jù)庫簡介
  

• P1 (緩沖池 Buffer Pool Manager): 為了更好的管理磁盤頁和內(nèi)存頁之間的映射同步, 要求實現(xiàn)可擴(kuò)展哈希表(Extensible HashTable)和LRU-K置換算法
  
• P2 (B+ Tree Index B+樹索引): 為了更快地檢索和遍歷數(shù)據(jù)表中的大量數(shù)據(jù), 要求實現(xiàn)了一個支持并發(fā)的B+樹索引和迭代器
  
• P3 (查詢執(zhí)行 Query Execution): 為支持SQL查詢(最新版的BusTub增加了基礎(chǔ)SQL語句的Parse和Query Planning), 要求實現(xiàn)了順序掃描,索引掃描,插入,刪除,投影,過濾,嵌套循環(huán)join,索引join,哈希join,聚合,排序,limit,top-N等核心執(zhí)行功能
  
• P4 (并發(fā)事務(wù)管理 Lock Manager): 為了管理并發(fā)事務(wù), 要求實現(xiàn)資源鎖管理器來根據(jù)不同的事務(wù)授予/阻塞資源鎖請求.它支持READ_UNCOMMITED,READ_COMMITTED和REPEATABLE_READ作為事務(wù)隔離級別和分層的資源鎖
  

• 鏈路層: Routing算法(Distance Vector, Linked State Routing, SDN)
  
• 網(wǎng)絡(luò)層: IP Routing, Ipv4/6, Subnetting, BGP算法, Gao-Rexford條件
  
• 傳輸層: UDP, TCP(三次握手四次揮手, 阻塞調(diào)控)
  
• DNS, CDN, 視頻傳輸?shù)腂BA算法
  
• TLS, 對稱與非對稱性加密傳輸, 安全認(rèn)證
  
• 網(wǎng)絡(luò)虛擬化
  

• Mixnet安全混合源路由:為了在網(wǎng)絡(luò)中實現(xiàn)安全通信,Mixnet實現(xiàn)了鏈路層(Linker Layer)的報文路由的加密,重定向和混合, 以防止網(wǎng)絡(luò)中的竊聽者. 從生成樹協(xié)議(Spanning Tree Protocol)來構(gòu)建網(wǎng)絡(luò)拓?fù)? 并用Dijkstra最短路徑加上混合路由來傳包
  
• TCP Protocol: 直接了當(dāng), 請實現(xiàn)個TCP協(xié)議. 使得可以在兩端用戶之間建立雙向有序可靠的數(shù)據(jù)傳輸, 是網(wǎng)絡(luò)模型結(jié)構(gòu)中傳輸層的一個協(xié)議. 要點包括:三次握手四次揮手(SYN/FIN),數(shù)據(jù)塊排序重組(stream reassembl),流量控制(滑動窗口),重發(fā)機(jī)制(指數(shù)補(bǔ)償),狀態(tài)轉(zhuǎn)換(有限狀態(tài)自動機(jī)), 等
  
• Http: 分別實現(xiàn)HTTP server和client. 服務(wù)器端解析和驗證HTTP請求, 并支持GET,HEAD,POST方法且能I/O復(fù)用同時服務(wù)多個客戶端. 客戶端會根據(jù)依賴關(guān)系構(gòu)建圖, 并為單個客戶端實現(xiàn)流水線多請求和并行連接, 以獲得更好的性能
  

• 分布式系統(tǒng)的歷史與演進(jìn)
  
• 網(wǎng)絡(luò)通信的不穩(wěn)定性對分布式系統(tǒng)帶來的挑戰(zhàn)
  
• RPC與實現(xiàn)
  
• 緩存和Prefetching的重要性
  
• 分布式系統(tǒng)中各種錯誤的可能性與防范
  
• 系統(tǒng)擴(kuò)容
  
• 分布式共識協(xié)議: Two-Phase Commit, Quorum, Paxos
  
• 分布式系統(tǒng)的安全
  

• (C) 文件rpc遠(yuǎn)程過程調(diào)用: 用TCP Socket實現(xiàn)rpc call來"重載"一系列基本的如open, write, read, lseek, close等system call使得這些指令被傳輸?shù)竭h(yuǎn)程機(jī)器上執(zhí)行并打包返回. 服務(wù)端可以并發(fā)地處理對不同文件進(jìn)行操作的多個客戶端, 并來回序列化/反序列化參數(shù)和錯誤碼. 比較扎實和tedious的一個project, 讓人深刻的明白寫rpc的stub是多么的麻煩, 所以在現(xiàn)實生活中應(yīng)該盡可能去調(diào)現(xiàn)成的rpc的包
  
• (Java) 分布式文件緩存代理: 多個客戶端可以連接到一個本地代理; 多個本地代理可以連接到一個中心服務(wù)器. 文件緩存提供打開文件時會話語義的一致性(session-semantics consistency)，并使用Check-On-Use方法保證緩存的新鮮度
  
• (Java) 自擴(kuò)容與縮容: 這是我個人覺得比較無聊的一個project. 它用Process來模擬VM, 然后會不斷的給你的Server發(fā)請求, server需要根據(jù)當(dāng)前的流量決定是否需要擴(kuò)容或者縮容. 和15619的第一個project非常的類似. 但有點搞笑的是, starter code里給了一些library 是 java class的形式, 但是用現(xiàn)代IDE比如IntelliJ打開后, 可以直接反編譯讀到一些重要變量的值, 比如一個request需要多久執(zhí)行, 前后端process所需要用時等等, 直接就能很簡單的計算出需要多少的VM了. 我很懷疑老師是不是以為給大家一個Java class而不給源碼大家就看不到這些值了
  
• (Java) 分布式事務(wù)-兩階段提交: 這個就是比較經(jīng)典的Two-Phase Commit的實現(xiàn). 在階段一中, 主節(jié)點向每個參與節(jié)點提出事務(wù), 希望獲得一致同意. 在收集完所有參與者節(jié)點的投票后, 主節(jié)點做出最終決定(提交Commit或中斷Abort)并進(jìn)入第二階段, 將該決定分發(fā)給每個參與節(jié)點. 為了應(yīng)對各種可能的故障, 主節(jié)點和參與節(jié)點都使用預(yù)寫式日志(Write-Ahead Logging)來實現(xiàn)狀態(tài)持久化和崩潰恢復(fù). 整體比較的直觀, 很快就能寫完. 感覺autolab的test case其實是不太全的, 稍微處理一下failure case就能過, 但我其實心里知道某個角落里估計代碼還有些小問題
  

• 不同的并行編程模型概述
  
• GPU架構(gòu)與CUDA編程
  
• 共享內(nèi)存并行 OpenMP, Clik
  
• 進(jìn)程間通信并行 MPI
  
• 調(diào)度scheduling和locaity
  
• 硬件緩存一致性(cache coherence)的架構(gòu)與實行
  
• Interconnect的不同硬件建筑方式
  
• 內(nèi)存一致性模型(memory consistency)
  
• 精細(xì)鎖與lock-free無鎖編程
  
• 事務(wù)性內(nèi)存(transactional memory)
  
• 深度學(xué)習(xí)中的并行運用
  

• ISPC: 用Intel的ispc指令集來寫vectorization向量化的代碼來加速計算
  
• CUDA: 用CUDA來編寫GPU的程序來處理一個圖像處理的問題
  
• OpenMP: 用共享內(nèi)存的并行編程的方式來加速經(jīng)典物理模擬問題N-body-simulation
  
• MPI: 用進(jìn)程間通信的方式來加速同一個N-body-simulation問題