一、系統(tǒng)設(shè)計目標

高可用的大文件分布式文件系統(tǒng)。

二、關(guān)鍵點

1. Architecture-架構(gòu)：有哪些Server，每個Server的功能。
2. Master存儲的MetaData的結(jié)構(gòu)。
3. client寫數(shù)據(jù)流程。
4. client讀數(shù)據(jù)流程。
5. 啟動時Master和ChunkServer的交互。
6. ChunkServer發(fā)生故障時，Master和ChunkServer的交互。

三、核心設(shè)計概述

2. Master中存儲的MetaData

class ChunkServer { // ChunkServer在Master中的數(shù)據(jù)結(jié)構(gòu)
  string host; // ip+port信息 回復(fù)給client 用于數(shù)據(jù)讀取
  int64  lastHeartBeat; // 上一次心跳的時間戳
}

map<int32, ChunkServer> chunkSvrInfo; // chunkSvrId ==> ChunkServer

class Chunk { // 文件中數(shù)據(jù)塊的數(shù)據(jù)結(jié)構(gòu)
  int64 handleId; // 該數(shù)據(jù)塊的唯一標識Id
  list<int32> chunkSvrId; // 存儲該數(shù)據(jù)塊的chunkSvrId
  int64 checkSum; // 該數(shù)據(jù)塊checksum的結(jié)果 客戶端讀取數(shù)據(jù)時可根據(jù)checkSum校驗讀取的數(shù)據(jù)是否被破壞 不一定存在Master中 可在ChunkServer中
}

class File { // NameSpace中文件的數(shù)據(jù)結(jié)構(gòu)定義
  string name; // 文件名
  vector<Chunk> chunks; // 順序存儲的chunk數(shù)據(jù) 
  int64 createTime;
  int64 updateTime;
}
class Directory { // NameSpace中目錄的數(shù)據(jù)結(jié)構(gòu)定義
  map<string, Directory>  dirs; // 該目錄下的所有子目錄
  map<string, File> files; // 該目錄下的所有文件
}

// handleId到具體Chunk的映射關(guān)系 ChunkServer只存儲了Chunk對應(yīng)的handleId 
// 數(shù)據(jù)遷移時需要根據(jù)handleId找到對應(yīng)的Chunk做出修改
map<int64, Chunk*> handleMap; 

Master持久化MetaData時，不會包含ChunkServer相關(guān)的信息，在Master和ChunkServer啟動時通過HeartBeat獲取ChunkServer的相關(guān)信息。

3. 一致性模型

consistent：all clients will always see the same data, regardless of which replicas they read from。// 所有client讀的數(shù)據(jù)是一致的
defined：consistent and clients will see what the mutation writes in its entirety。// 修改最終會生效
Q1：寫文件時，如何做數(shù)據(jù)塊合并，即最后一個chunk沒有寫滿，如何追加到這最后一個chunk。
Q2：寫數(shù)據(jù)時，需要同時修改Master中的Meta信息和ChunkServer中的chunk信息，如何同步？
Q3：并發(fā)寫數(shù)據(jù)時，如何做同步，即需要等前面的寫完以后才開始寫后面的數(shù)據(jù)嗎？如果不這樣，中間的寫失敗了如何處理？
Q4：并發(fā)append為什么會導致duplicate？
Q5：并發(fā)write和append的區(qū)別是什么？

四、系統(tǒng)交互

4.1 系統(tǒng)交互類型

1. 寫數(shù)據(jù)。
2. 讀數(shù)據(jù)。
3. 刪除、移動和拷貝。

4.2 鎖機制

對文件進行并發(fā)交互時，沖突會導致數(shù)據(jù)的不確定，因此需要加鎖。鎖分為讀寫鎖，并且針對絕對路徑加鎖，規(guī)則如下：
路徑：/dir1/dir2/dir3/dir_or_file
讀操作：對目錄dir1、dir2、dir3、dir_or_file加讀鎖（即這些路徑只能被并發(fā)讀）。
寫操作：對目錄dir1、dir2、dir3加讀鎖，dir_or_file加寫鎖（dir_or_file不能讀也不能寫）。
Q1：死鎖的處理，操作1：將/dir1/dir2移動到/dir3/dir4目錄下（dir2不能讀寫且需要讀寫dir4），操作2：將dir3/dir4移動到/dir1/dir2目錄下（dir4不能讀寫且需要寫dir2）。當2個操作并發(fā)時，可能會死鎖。

4.3 刪除、移動和拷貝

刪除：采用延遲刪除的方式，刪除時增加標識，后臺線程定時掃描要刪除的文件。步驟如下：

 1. 處理刪除命令，標記Master中的Meta文件刪除，通常在標記為刪除3天后可正式刪除。
 2. 后臺線程定時掃描Master中要刪除的文件，刪除相關(guān)的Meta信息。
 3.  ChunkServer通過心跳上報chunk信息時發(fā)現(xiàn)包含的chunk不對應(yīng)任何有效文件，Master通知ChunkServer刪除該chunk。

移動：在Master中修改Meta信息即可完成。
拷貝：采用COW機制，即使用時拷貝，首先拷貝一份Meta信息，并增加最后一個chunk的引用計數(shù)（如果一個文件有N個chunk，則前N-1個chunk無需拷貝，共享即可）。通過取消租約的方式停止向第N個chunk寫數(shù)據(jù)，當有寫操作時，先拷貝一份第N個chunk，取消引用計數(shù)，然后向拷貝出來的chunk寫數(shù)據(jù)。

4.4 寫數(shù)據(jù)

1. 概述，client寫數(shù)據(jù)時，先向Master具體寫的chunk信息（Master通過租約lease的方式指定一個Primary chunk，其余的為Seondary chunk）。后續(xù)client向chunk發(fā)數(shù)據(jù)并向Primary發(fā)送寫請求。

2. 流程圖

   
   
   寫數(shù)據(jù)流程圖
3. 流程解析
   step1、2：client發(fā)送請求，Master分配租約、返回chunk信息。
   step3：client將要寫的數(shù)據(jù)發(fā)送個chunk。
   step4：client向Primary chunk發(fā)送寫請求。
   step5：Primary確定寫數(shù)據(jù)的offset和順序（即如果有多條數(shù)據(jù)，多條數(shù)據(jù)間的順序），通知Secondary開始寫數(shù)據(jù)。
   step6：Secondary寫數(shù)據(jù)成功，通知Primary。
   step7：Primary通知client寫數(shù)據(jù)成功。
4. lease租約的管理
   前提：當Chunk擁有租約時才會認為自己是Primary并處理寫命令，通常租約為60S。
   case1：寫操作時租約自動到期。通過心跳來續(xù)租約，避免租約自動到期。
   case2：Primary宕機。client重新向Master發(fā)送請求，Master重新分配租約。
   case3：Primary網(wǎng)絡(luò)波動，但新的Primary已產(chǎn)生，存在2個Primary。增加version字段，多個Primary時，比較version，同時Master存儲一個version字段，version大于等于Master中的version時才有效，每次分配lease時，version自增。
5. 特殊Case分析
   case1：單client，數(shù)據(jù)不越界。無需特殊處理。
   case2：單client，數(shù)據(jù)超出chunk容量。寫失敗，將chunk的空白區(qū)填充數(shù)據(jù)。
   case3：單client，寫失敗，重試后成功。重試即可。
   case4：單client，寫失敗，重試后仍失?。ㄈ缒硞€chunk所在物理機宕機）。
   case5：多client，數(shù)據(jù)不越界。無需特殊處理。
   case6：多client，總數(shù)據(jù)超出chunk容量。未超出的部分寫入chunk，超出部分失敗重試。
   case7：多client，總數(shù)據(jù)超出chunk容量，且在舊的chunk上寫數(shù)據(jù)失敗。
6. 數(shù)據(jù)流的優(yōu)化，從client將數(shù)據(jù)傳給所有的chunk可以優(yōu)化為client傳給最近的chunk，由chunk鏈式傳遞給其它的剩下的chunk。
7. 數(shù)據(jù)準確性的保證。在每個chunk末尾，記錄當前chunk數(shù)據(jù)塊的checksum。

4.5 讀數(shù)據(jù)

根據(jù)offset定位到具體的chunk，讀取數(shù)據(jù)，但是如上，存在空白區(qū)，讀取時需特殊處理。

五、高可用的保證

5.1 chunk的復(fù)制

每個chunk都有多個副本，并可以配置副本的數(shù)量。
副本的分布：通常副本要在不同的機房，保證當整個機房出現(xiàn)問題時，數(shù)據(jù)不會丟失。
副本的拷貝：當副本配置數(shù)量增加或者部分副本永久失效時，需要拷貝副本（論文沒有說明如何拷貝副本）。

5.2 chunk的過期檢測

當Chunk服務(wù)器失效時，其中部分chunk數(shù)據(jù)更新不及時，因此上面的數(shù)據(jù)是無效的，在每個chunk中記錄一個version（該version和lease的version相同），如果Master中其它同副本的chunk版本號更高，說明該chunk的數(shù)據(jù)未及時更新，需要刪除該數(shù)據(jù)。

5.3 Master的復(fù)制

主從，RDB，AOF。。。

5.4 checksum保證數(shù)據(jù)完整

每個chunk塊在末尾增加整個chunk的checksum，在讀取時需根據(jù)記錄的checksum校驗該chunk塊的數(shù)據(jù)的準確性。