Mongodb存儲布局

mongodb的mongod服務管理一個數據目錄，可包含多個DB，每個DB的數據單獨組織，本文主要介紹mmapv1存儲引擎的數據組織方式。

Database

每個Database(DB)由一個.ns文件及若干個數據文件組成

$ll mydb.*
-rw-------  1 ydzhang  staff  67108864  7  4 14:05 mydb.0
-rw-------  1 ydzhang  staff  16777216  7  4 14:05 mydb.ns

數據文件從0開始編號，依次為mydb.0、mydb.1、mydb.2等，文件大小從64MB起，依次倍增，最大為2GB。

Namespace

每個DB包含多個namespace（對應mongodb的collection名），mydb.ns實際上是一個hash表（采用線性探測方式解決沖突），用于快速定位某個namespace的起始位置。

hash表里的一個節點包含的元數據結構如下，每個節點大小為628Bytes，16M的NS文件最多可存儲26715個namespace。

struct Node {
    int hash;
    Namespace key;
    NamespaceDetails value;
};

• key為namespace的名字，為固定長度128字節的字符數組。
• hash為namespce的hash值，用于快速查找
• value包含一個namespace所有的元數據

namespace元數據結構如下:

class NamespaceDetails {
    DiskLoc firstExtent; // 第一個extent位置
    DiskLoc lastExtent;  // 最后一個extent位置
    DiskLoc deletedListSmall[SmallBuckets]; 
    // 不同大小的刪除記錄列表
    ...
};

其中DiskLoc代表某個數據文件的具體偏移位置，數據文件使用mmap映射到內存空間進行管理，內存的管理（哪些數據何時換入/換出）完全交給OS管理。

 class DiskLoc {
    int _a;  // 數據文件編號，如mydb.0編號為0
    int ofs; // 文件內部偏移
 };

數據文件

每個數據文件被劃分成多個extent，每個extent只包含一個namespace的數據，同一個namespace的所有extent之間以雙向鏈表形式組織。

namesapce的元數據里包含指向第一個及最后一個extent的位置指針，通過這些信息，就可以遍歷一個namespace下的所有extent數據。

每個數據文件包含一個固定長度頭部DataFileHeader

 class DataFileHeader {
    DataFileVersion version;
    int fileLength;
    DiskLoc unused;
    int unusedLength;
    DiskLoc freeListStart;
    DiskLoc freeListEnd;
    char reserve[];
 };

Header中包含數據文件版本、文件大小、未使用空間位置及長度、空閑extent鏈表起始及結束位置。extent被回收時，就會放到數據文件對應的空閑extent鏈表里。

unusedLength為數據文件未被使用過的空間長度，unused則指向未使用空間的起始位置。

Extent

每個extent包含多個Record（對應mongodb的document）,同一個extent下的所有record以雙向鏈表形式組織。

struct Extent {
    unsigned magic;  // 用于檢查extent數據有效性
    DiskLoc myLoc;   // extent自身位置
    /* 前一個/后一個 extent位置指針 */
    DiskLoc xnext;
    DiskLoc xprev;
    int length;  // extent總長度 
    DiskLoc firstRecord;  // extent內第一個record位置指針
    DiskLoc lastRecord;   // extent內最后一個record位置指針
    char _extentData[4];  // extent數據
};

Record

每個Record對應mongodb里的一個文檔，每個Record包含固定長度16bytes的描述信息。

class Record {
    int _lengthWithHeaders;  // Record長度
    int _extentOfs;       // Record所在的extent位置指針
    int _nextOfs;           // 前一個Record位置信息
    int _prevOfs;           // 后一個Record位置信息
    char _data[4];         // Record數據
};

Record被刪除后，會以DeleteRecord的形式存儲，其前兩個字段與Record是一致的。

class DeletedRecord {
   int _lengthWithHeaders;  // record長度
   int _extentOfs;          // record所在的extent位置指針
   DiskLoc _nextDeleted;    // 下一個已刪除記錄的位置
}；

一個namespace下的所有的已刪除記錄（可以回收并復用的存儲空間）以單向鏈表的形式，為了最大化存儲空間利用率，不同size（32B、64B、128B...）的記錄被掛在不同的鏈表上，NamespaceDetail里的deletedListSmall/deletedListLarge包含指向這些不同大小鏈表頭部的指針。

寫入Record

1. 檢查對應的namespace對應的刪除記錄鏈表里是否有合適的DeletedRecord可以利用，如果有，則直接復用刪除空間寫入記錄。
2. 檢查數據文件的freeList里是否有合適大小的空閑extent可以利用，如果有則直接利用空閑的extent，將記錄寫入。
3. 第1、2步都不成功，則寫創建新的extent寫入記錄；創建新extent時，如果當前的數據文件沒有足夠的空閑空間，則創建新的數據文件。