Chang-Chia-Chi

@Chang-Chia-Chi

Joined on Feb 26, 2021

  • 透過 golang 實作一個基本的 raft,分散式系統有大量鎖及併發的操作,也看了網路上一些心得文章,已經有心理準備會有滿滿的坑了,但分散式系統就是這樣才好玩對吧 XD。在開始實作前建議先看過 [3],[4] & [5],然後 ==Figure 2. 很重要、很重要、很重要==,誠如 TA Guide 所說,請對 Figure 2. 保持敬畏之心,確保 "完整" 的理解圖中所有內容,魔鬼藏在細節裡 Lab2A Leader Election 第一項任務是實作 Leader 選舉的機制,結構體參數的部分我直接參考論文設定,實作上有幾點比較重要的是: 要在正確的時刻重設 election timer轉變為 Follower 跟 Candidate 兩個狀態時,這點比較直觀 Follower 收到 "合法" AppendEntries RPC 時,合法代表請求的 Term >= CurrentTerm,否則代表該請求是由一個過期的 Leader 發送,那重設 timer 反而會觸發不必要的重新選舉 Follower 收到 "合法" RequestVote RPC 時,合法意味著請求的 Term >= CurrentTerm Follower 在該 Term 還沒投過票 (rf.votedFor == -1) 請求的 log 跟自身比較是 up-to-date 的,代表 Candidate 的 log 至少不落於人後,up-to-date 的定義請參閱論文 5-4 Safety 章節中有關 Election Restriction 的部分
     Like  Bookmark
  • 分散式系統論文 MapReduce Google File System MIT6.824 Lecture 4: Primary-Backup Replication Raft 基礎理論 CAP 理論 ACID
     Like  Bookmark
  • 作業系統 CH3 Process 作業系統 CH4 Multithreaded Programming 作業系統 Ch5 Process Scheduling 作業系統 CH6 Process Synchronization 作業系統 Ch7 Deaklock 作業系統 CH8 Memory Management 作業系統CH9 Virtual Memory Management 作業系統CH10 File System Interface 作業系統Ch11 : File System Implementation 作業系統Ch12 : Mass Storage System
     Like 27 Bookmark
  • 完整的 python 實作可參考 Github 連結 [10] Introduction 在論文撰寫的時間點,最常使用的複合(hybrid)排序算法應該是內省排序 (intro sort) [2],內省排序由插入排序 (insertion sort)、堆排序 (heap sort) 以及快速排序 (quick sort) 組合使用而成,當遞迴深度過深時採用堆排序,若分區的尺寸低於某個大小時則改用插入排序。 :::success 堆排序: 確保算法的時間複雜度能維持在 O(NlogN) 插入排序: 節省函式遞迴呼叫的成本,降低記憶體的使用量 (省去 logX 的遞迴棧幀 (stack frame),以 C++ 為例 X = 16 [2]) 並且提昇快取的 locality
     Like 1 Bookmark
  • Xv6 and Unix utilities system calls page tables traps xv6 lazy page allocation Copy-on-Write Fork for xv6 Multithreading net: Network stack
     Like 1 Bookmark
  • CS:APP Proxy Lab 解題筆記 CS:APP Malloc Lab 解題筆記 CS:APP Shell Lab 解題筆記 CS:APP Cache Lab 解題筆記 CS:APP Attack Lab 解題筆記 CS:APP Bomb Lab 解題筆記 CS:APP Data Lab 解題筆記
     Like 1 Bookmark