CPU架构

早期时，个人电脑及小型服务器的架构如下：所有CPU之间是通过FSB（Front Side Bus， FSB）进行相互连接，并通过它来连接北桥，北桥连接高速设备（如主存等），通过北桥可以连接南桥，南迁连接低速设备（如硬盘、外设等）。

这样的架构有这样一些特点：

• CPU之间的交互需要共用连接比较的总线（FSB）
• 每个RAM只有一个接口
• CPU同主存之间的交互要通过北桥
• CPU同南桥上的设备间的交互必须通过北桥

这样的一个架构容易引入这样一些瓶颈：

• 第一个瓶颈是对RAM的访问。早期时，所有设备的交互都要通过CPU来进行，这样会严重影响整个系统的性能。为了解决这个问题，直接内存访问（DMA，direct memory access ）技术被发明出来了，DMA允许外设通过北桥直接同RAM进行交互。这样能极大降低CPU负载，提升系统整体性能。
• 第二个瓶颈是通过从北桥连接RAM的总线。早期时系统是通过一条总线来连接所有RAM，所以无法并行访问内存，最近的RAM都支持多条总线连接来提升内存访问带宽

但内存访问带宽受限时，合理安排内存访问顺序对于提升系统性能是非常重要的。众所周知，即使使用了CPU缓存后，CPU的运行速度（内部寄存器的访问速度）也比主存的访问速度快多了。如果多个线程、CPU核心、CPU处理器同时访问某块内存，那么整体的内存访问延迟是很高的。在一些现代系统中，在北桥上不是直接连接RAM，而是会连接一些外部内存分配器，如下所示：

这个架构的好处是有多个内存总线存在，能提升整体的内存访问带宽，同时能提升系统的内存总量，并且通过访问不同内存条的方式可以降低并发内存访问的延迟。此时，系统的整体内存访问带宽主要受限于北桥的传输速度，这即使传统SMP（对称多核处理器）架构。

在北桥之间接入多个外部内存分配器并不是提升内存访问带宽的唯一方法，在一些系统中，内存分配器被放入CPU中，内存条也是直连每个CPU的，如下所示：

这就是NUMA（非均匀性内存访问）架构，采用这种架构也有这样的问题：

• 内存访问不再是对称的，本地内存还能以正常的速度访问，然而访问其他处理的内存需要通过对应的CPU来进行交互，这样会导致访问远程内存的速度较慢

存储器

随机访问存储器（RAM）

RAM分为两类：静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）。SRAM比DRAM访问速度快得多，但也更加昂贵，SRAM通常都是用来做高速缓存，DRAM通常用来做主存。SRAM与DRAM都是易失性存储，只要断电，其中存储的数据便会丢失。

磁盘

磁盘是应用最广的数据存储设备，容量比RAM大得多，但是访问延迟也高。从磁盘读取信息时间为ms级别，DRAM的访问速度比磁盘快10万倍，而SRAM比磁盘快100万倍。

磁盘是由盘片构成的，每个盘片有两面被称之为表面，盘片中央有一个可旋转的主轴，盘片以固定速率围绕主轴旋转，如下图所示展示了一个典型的磁盘结构：

每个表面由一组称为磁道的同心圆组成，每个磁道被划分为一组扇区，扇区间由间隙隔开，扇区是磁盘存储的最小单位，柱面是所有表面上到主轴距离相等的磁道的集合。

磁盘以扇区为基本单位，使用磁头来读写盘面上的数据，对扇区的访问时间主要由一下三个部分组成：

• 寻道时间：磁头移动到目标扇区所在磁道的位置
• 旋转时间：盘面旋转将目标扇区转到到磁头下
• 传送时间：磁头读取扇区中的数据

相对来说，传送时间远小于寻道时间和旋转时间，这也是为什么硬盘的顺序读写要比随机读写速度快得多。因为寻道时间和旋转时间大致是相等的，所以将寻道时间乘于2是估计磁盘访问时间的简单办法。

固态硬盘（ssd）

固态硬盘是一种基于闪存的技术，相对磁盘来说，ssd上随机访问的速度较顺序访问的速度不会相差太多。

各级存储设备访问延迟

以一个CPU时钟周期为单位，各级设备的访问延迟如下：

本文主要讲述在Linux服务上数据从应用层写入磁盘的关键路径，聚焦于其中涉及到的各种缓存，讲述在c编程中如何确保数据能被持久化存储，避免系统异常时造成数据丢失。

IO buffering

Linux下，用户数据在最终达到持久化存储层之前会经过多层，如下所示：

最顶层是需要存入数据的应用，数据首先是以block的方式存储在应用本身的memory或者buffer中，这些buffer也可能会被转交给运行库，由运行库来管理这些缓存。无论这些数据是在应用程序本身的buffer或者运行库的buffer中，此时这些数据都还是停留在用户地址空间。用户空间的下一层是内核空间，它也会内存中维护自身的写回缓存，即page cache。脏页在page cache中停留一段时间后会被写入存储设备中（如硬盘）。同时存储设备也可能会维护自身的易失性缓存，在掉电时缓存中的数据是会丢失的。最后，在最底层的是非易失性存储设备，数据只有在到达此层时，才是安全的，不会在系统异常退出时丢失。

为了更详细阐述如上所述的各种缓存机制，以这样的一个应用程序为例：它通过一个socket读入数据后将数据写入本地文件中。在关闭这个socket之前，服务端会确认数据已经持久化存储，主要代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

 0 int
 1 sock_read(int sockfd, FILE *outfp, size_t nrbytes)
 2 {
 3      int ret;
 4      size_t written = 0;
 5      char *buf = malloc(MY_BUF_SIZE);
 6 
 7      if (!buf)
 8              return -1;
 9
10      while (written < nrbytes) {
11              ret = read(sockfd, buf, MY_BUF_SIZE);
12              if (ret =< 0) {
13                      if (errno == EINTR)
14                              continue;
15                      return ret;
16              }
17              written += ret;
18              ret = fwrite((void *)buf, ret, 1, outfp);
19              if (ret != 1)
20                      return ferror(outfp);
21      }
22 
23      ret = fflush(outfp);
24      if (ret != 0)
25              return -1;
26 
27      ret = fsync(fileno(outfp));
28      if (ret < 0)
29              return -1;
30      return 0;
31 }

在接受client端的连接之后，应用会将从socket中读出的数据写入自身buffer之中，如上函数的调用者在调用前已经知道client端发送的数据大小，同时打开一个文件流用以写入数据，该函数在返回前会确认将数据持久化存储。
其中L5就是一个应用层的buffer，从socket中读出的数据首先会放入这个buffer中，同时鉴于网络传输的突发性或者低效，我们决定使用libc的流式函数（fwrite()及fflush(),代表上图中的运行库缓存）来缓存应用层读出的数据。L10-21就是用于从socket读出数据并写入文件流中，L23用以将文件流进行刷写，使数据进入内核空间。之后，在L27，数据被写入上图的Stable Storage这层。

IO APIs

下面我们来看各个API同上图中每层的关系，在下面的讨论中，我们将IO分成3类：系统IO（system IO）、流式IO以及内存映射IO（mmap）。

系统IO

系统IO是指通过系统调用将内核空间的数据写入storage层的操作，如下是部分相关的系统IO接口：

流式IO

流式IO是指调用C的运行库中流式接口的IO操作，调用这些函数进行数据写入时可能不会引发系统调用，这意味着数据仍在用户空间中，如下是部分相关的流式IO接口：

内存映射IO

内存映射文件同前文的系统IO比较相似，文件仍旧是通过相同的接口来打开和关闭，它是通过将文件数据通用户空间映射来实现文件访问，然后执行同其他应用层buffer一样的内存读写操作来读写文件，如下是部分相关的mmap接口：

在打开文件时，有两个选项可以改变时的缓存行为:O_SYNC及O_DIRECT。使用O_DIRECR打开的文件的读写操作会绕过内核空间的page cache,直接将数据写入存储设备中，但是存储设备自身仍可能存在缓存，所以仍旧需要使用fsync()来将数据持久化存储,即O_DIRECR只和系统IO的API相关。裸设备(/dev/raw/raw/V)提供一种特殊的O_DIRECT IO方式，这些设备在打开时不需指定O_DIRECT选项，但仍旧提供direct IO语义。

同步IO是指对于一个使用O_SYNC或者O_DSYNC打开的IO操作（包括不管是否使用了O_DIRECT的系统IO及流式IO），POSIX语义定义了一下几种同步操作模式：

• O_SYNC：文件数据及所有元数据被同步写入磁盘中
• O_DSYNC：只有文件数据及访问该数据需要的元数据需要被同步写入磁盘
• O_RSYNC：尚未实现
  在同步模式下，用户数据及相关的元数据会立马被写入持久化存储设备中，需要注意的是，其他元数据（不涉及到访问该部分数据）可能不会立马被写入持久化设备中，这些元数据可能包括文件的访问时间、创建时间或者修改时间等。
  另外需要注意使用O_SYNC或O_DSYNC 打开一个文件，然后通过libc的流式接口来操作这个文件的情况，通过fwrite()写入的数据都会被从的运行库缓存，直到调用fflush()后数据才被写入磁盘中。因此，通过此类流式解救操作一个同步文件描述符时，不需要调用fsync()来同步数据，但是fflush()仍旧是必需的。

合理使用fsync

通过如下几条原则来判断是否调用fsync()：

• 首先，将数据持久化存储是否那么重要。如果是可擦洗或可再生的数据，那是没必要的
• 在创建新文件或者覆盖现有文件时，使用fsync()不止是同步文件数据本身，同时也是同步它的目录项，才能确保之后能访问到这个文件，这个行为同文件系统及挂载选项也是相关的。
• 最后，如果在覆盖现有文件时系统了奔溃，可能会造成数据的丢失，为了解决这个问题，一个通用做法是先将数据写入一个临时文件，确保这个临时文件持久化存储后将这个临时文件重命名为待覆盖文件名，这样能确保文件的原子更新。相关的流程如下：
  1. 创建一个临时文件
  2. 将数据写入临时文件
  3. fsync()这个临时文件
  4. 将临时文件重命名
  5. fsync()文件所在目录

写回(write-back)缓存

本节简单讨论下磁盘层面的缓存以及操作系统对于此种缓存的控制，本节中讨论的选项不影响应用程序该如何构造。
存储设备的写回缓存有许多不同的形式，如前文所述的易失性缓存，此类缓存在系统异常时会丢失。在实际中，大部分存储设备都可以被配置为无缓存模式或者写穿(write-through)模式，这些模式在数据被持久化存储之前是不会返回成功给客户端的。此外一些外部存储阵列可能有非易失性缓存或者带电的写入缓存，这样可以在系统掉电时仍旧持久化存储数据。
一些文件系统提供控制缓存刷写的挂载选项，例如在2.6.35之后的linux版本中，ext3、ext4及btrfs提供-o barrier这个选项来打开屏障（write-back cache，该选项是默认开的），或者-o nobarrier来关闭它。但是应用层不需要过多考虑这个选项，当文件系统的barriers被禁用后，fsync不会导致磁盘缓存的刷写。

O_DIRECT同O_SYNC的区别

如前文所述，O_DIRECT可以是IO绕过page cache直达storage层，但是storage层可能仍旧会存在缓存，此时数据仍旧可能是不安全的。但是使用O_DIRECT需要遵守一些限制：

• 用以传递数据的应用层缓存区，其内存边界必须对其块大小的整数倍
• 数据传输的开始点，即在文件中的偏移值必须也是块大小的整数倍
• 传输的数据长度必须是块大小的整数倍
  这些限制都要有应用层来确保，否则会导致EINVAL错误，显而易见的是，使用O_DIRECT容易造成存储空间的浪费

而O_SYNC用以将缓存中的数据刷写至磁盘中，此时数据还是会写入page cache中，但是会被立马刷写至磁盘中，直到数据持久化存储才会返回，可以确保数据的安全性。但是通过fsync的manual手册可以看到在一些老的内核或者小众文件系统中，fsync可能不知道如何刷写存储设备的缓存，此时需要别的方式来关闭存储设备的缓存，如下所示：

在实际使用过程可以同时使用O_DIRECT及O_DSYNC这个两个选项来确保数据的安全性，这样数据在写入时会直接绕过page cache，持久化存储后才会返回。

References

• Ensuring data reaches disk
• How are the O_SYNC and O_DIRECT flags in open(2) different/alike

PUT

LevelDB的写入性能较高，整体步骤就是先写wal日志再写入memtable中，由于wal日志是append写入的，性能较高，所以写入一般不存在瓶颈。但是如果写入速度过快，导致memtable来不及flush或者lelvel 0中的文件数较多时，系统的写入可能会被限制，这就是LevelDB的write stall问题，整体写入流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

struct DBImpl::Writer {
  Status status; // 写入结果
  WriteBatch* batch; 
  bool sync; //本次写入对应的log是否立刻刷盘
  bool done; //本次写入是否完成
  port::CondVar cv; //条件锁，会被之前的写入线程唤醒

  explicit Writer(port::Mutex* mu) : cv(mu) { }
};

Status DBImpl::Write(const WriteOptions& options, WriteBatch* my_batch) {
  Writer w(&mutex_);
  
  //先加锁，保证只有一个线程能写入，在开始写log和memtable的时候会释放
  MutexLock l(&mutex_);
  //加入等待队列中排队
  writers_.push_back(&w);
  //如果此次写入没有被执行且不处于队列头部，则等待之前的写入完成
  while (!w.done && &w != writers_.front()) {
    w.cv.Wait();
  }
  //如果此次写入已经执行了，则直接返回
  //其他写入请求在写入时可能会将队列中的写入请求一起取出合并写入DB中
  if (w.done) {
    return w.status;
  }

  //写入前的检查，memtable、wal日志、compaction等，可能会阻塞住此次写入
  Status status = MakeRoomForWrite(my_batch == NULL);
  uint64_t last_sequence = versions_->LastSequence();
  Writer* last_writer = &w;
  if (status.ok() && my_batch != NULL) {
    //合并队列里的多个写入
    WriteBatch* updates = BuildBatchGroup(&last_writer);
    WriteBatchInternal::SetSequence(updates, last_sequence + 1);
    last_sequence += WriteBatchInternal::Count(updates);

    // 写入wal日志和memtable，写入前可以先释放锁，让后续write请求进入队列中排队，
    //这样也能保证写入时互斥的，因为此时已经确定是只有w来负责写入 ，这样可以减小互斥时间
    {
      mutex_.Unlock();
      status = log_->AddRecord(WriteBatchInternal::Contents(updates));
      bool sync_error = false;
      if (status.ok() && options.sync) {
        status = logfile_->Sync();
        if (!status.ok()) {
          sync_error = true;
        }
      }
      if (status.ok()) {
        status = WriteBatchInternal::InsertInto(updates, mem_);
      }
      //更新versions时需要加锁，确保last_sequence正确修改
      mutex_.Lock();
      if (sync_error) {
        //wal日志sync失败
        RecordBackgroundError(status);
      }
    }
    if (updates == tmp_batch_) tmp_batch_->Clear();

    versions_->SetLastSequence(last_sequence);
  }

  //修改合并写入请求的状态
  while (true) {
    Writer* ready = writers_.front();
    writers_.pop_front();
    if (ready != &w) {
      ready->status = status;
      ready->done = true;
      ready->cv.Signal();
    }
    if (ready == last_writer) break;
  }

  // 唤醒队列头部的请求
  if (!writers_.empty()) {
    writers_.front()->cv.Signal();
  }

  return status;
}

GET

LevelDB支持获取，某个key的指定版本对应的值，如果没有指定版本的话，则获取最新的kv对，整体流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   std::string* value) {
  Status s;
  //获取快照和version时先加锁，保证相关引用的正确修改
  MutexLock l(&mutex_);
  SequenceNumber snapshot;
  //获取相关sequenceNUmber
  if (options.snapshot != NULL) {
    snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
  } else {
    snapshot = versions_->LastSequence();
  }

  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  //memtable引用加1
  mem->Ref();
  if (imm != NULL) imm->Ref();
  //version引用加1
  current->Ref();

  bool have_stat_update = false;
  Version::GetStats stats;

  //ref已经设置完成，可以释放锁了
  {
    mutex_.Unlock();
    // 在memtable中查找
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // 在imm中查找
    } else if (imm != NULL && imm->Get(lkey, value, &s)) {
      // Done
    } else {
      //通过version查找，一个version代表DB中sstable文件的一个状态
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
    }
    //确保只有一个线程修改引用
    mutex_.Lock();
  }

  if (have_stat_update && current->UpdateStats(stats)) {
    //如果扫描次数过多可能会触发compaction
    MaybeScheduleCompaction();
  }
  mem->Unref();
  if (imm != NULL) imm->Unref();
  current->Unref();
  return s;
}

其中要注意的是，要通过锁来确保只有一个线程来修改相关的引用计数，修改完引用后可以释放锁，即读取memtable和sstable不是互斥的。

作用

LevelDB中将随机写在内存中缓存并进行排序(memtable)，从而将随机写转化成顺序写来提高数据的写入速度，在磁盘上它是以sstable的格式来持久化存储数据的。磁盘上的sstable文件是分层存储的，层级越高，容量就越大，存储的文件就越旧。随着数据的持续写入，memtable达到阈值之后会flush到level 0的sstable中，这个过程被称之为minor compaction，由于这一层级的文件是有memtable直接刷写下来的，所以sstable之间的key可能会存在重叠。

在查找一个key时，系统会先去memtable中查找，若未找到，则会按层级去sstable中查找。由于level 0中的sstable中的key是可能重叠的，所以在查找level0时可能要遍历多个sstable文件，这样会导致查询效率较低。所以当level 0中的文件数较多时，会出发major compaction，将该层的文件同下层合并。

level 0以上的文件是通过compaction来生成的，所以同一层的文件之间的key是不存在重叠的，但是该层的文件量也不能太大，否则会降低key的查找效率。同时，文件量太大也会造成major compaction的时候IO负载过高，影响系统的正常读写。所以LevelDB中会分多层来存储sstable文件，层级越高，容量越大，所存储的文件也越久。

综上，Compaction的机制如下：

• 当memtable达到阈值时，会触发minor compaction，将memtable中的数据flush成sstable文件，防止占用过多内存
• 当level 0中的文件数过多时，会触发major compaction，将该层的部分文件与上层合并，提高查询效率
• 当level 0以上某层文件总量过大时，会触发major compaction，提高查询效率，同时避免之后参与compaction的数据量过大

流程

Compaction

Compaction最终是通过调用BackgroundCompaction来执行的，执行流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

BackgroundCompaction() {
	if(imm_ != NULL) {
      	//minor compaction
		CompactMemtable() ;
		return ;
	}
	
    //major compaction
	if(is_manual) {
		ManualCompaction* m = manual_compaction_;
    	c = versions_->CompactRange(m->level, m->begin, m->end);
	} else {
		 c = versions_->PickCompaction();
	}

	if (c == NULL) {
    	// Nothing to do
  	} else if (!is_manual && c->IsTrivialMove()) {
      	//平移文件至下一层
	    c->edit()->DeleteFile(c->level(), f->number);
    	c->edit()->AddFile(c->level() + 1, f->number, f->file_size, f->smallest, f->largest);
    	status = versions_->LogAndApply(c->edit(), &mutex_);
  	} else {
  		DoCompactionWork(compact);
  	}
}

整体的流程图如下：

Minor Compaction

其中，CompactMemtable用以将memtable中的文件flush成sstable文件，它的流程如下：

1
2
3
4
5
6
7
8

CompactMemtable() {
	VersionEdit edit;
  	Version* base = versions_->current();
  	//将数据刷写至sstable中
  	Status s = WriteLevel0Table(imm_, &edit, base);
  	versions_->LogAndApply(&edit, &mutex_);
  	DeleteObsoleteFiles();
}

以上流程中，Version是系统用来管理系统中sstable文件的，每次进行compact后，都会新生成一个Version用来管理磁盘上sstable文件的状态，VersionEdit则代表此次compact中文件的变化情况，关于Version机制会在下节讨论。

在CompactMemtable中会调用WriteLevel0Table将memtable刷写至sstable中，机制如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base) {
	FileMetaData meta; 
	BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);

	if(meta.file_size > 0) {
		if (base != NULL) {
			//为minor compact形成的sstfile选择合适的层级，memtable不一定是compact至level0中
			//如果level0中存在与此次compact key重叠的文件，则直接flush至level0
			//否则可以沉降至没有重叠区间的一个level，且沉降至该level后不会造成之后的大量compaction（与level+1层的重叠不能过多）
      		level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
    	}
    	//添加一个sstfile
    	edit->AddFile(level, meta.number, meta.file_size,
                meta.smallest, meta.largest);
	}
}

其中，需要注意的是，memtable不总是直接flush值level 0中的，如果level 0中没有文件与memtable的数据重合，则可以直接刷写至更高的层级，这样可以减少compaction的次数。但同时，如果某一层（level层）没有文件与memtable中的数据重合，但是下一层（level+1）中与memtable中重合的文件尺寸较大，也不能直接放入level中，否则的话会导致之后该文件compaction的时候设计到的数据量太大，影响系统的正常读写。

Major Compaction

Major Compaction的第一步是选择生成compaction的信息，根据compaction是否是手动触发的，具体机制又有不同，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

//根据手动compact时输入的level及key的范围生成compact信息
//compact信息中最重要的信息就是inputs，即参与compaction的sstfile
//其中inputs[0]中存储的是level层的文件
//inputs是与inputs[0]中的key存在交集的level+1层的文件
CompactRange(level, begin, end) {
	//获取第一层待compact的文件
	current_->GetOverlappingInputs(level, begin, end, &inputs);
  	if (inputs.empty()) {
   		return NULL;
  	}

  	Compaction* c = new Compaction(options_, level);
  	c->inputs_[0] = inputs;
  	//获取下一层被compact的文件
  	SetupOtherInputs(c);
}

PickCompaction() {
	//根据某层的总容量或者查找次数来触发compaction，其中容量触发的优先级更高
	const bool size_compaction = (current_->compaction_score_ >= 1);
  	const bool seek_compaction = (current_->file_to_compact_ != NULL);

  	if (size_compaction) {
  		level = current_->compaction_level_;
    	c = new Compaction(options_, level);

    // Pick the first file that comes after compact_pointer_[level]
    // compact_pointer_中记录的是每层上次compaction中最大的key，选择上次最大的key后的一个文件
    for (size_t i = 0; i < current_->files_[level].size(); i++) {
      FileMetaData* f = current_->files_[level][i];
      if (compact_pointer_[level].empty() ||
          icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) {
        c->inputs_[0].push_back(f);
        break;
      }
    }
    if (c->inputs_[0].empty()) {
      // Wrap-around to the beginning of the key space
      //未选到文件的话，则选择第一个文件来进行compact
      c->inputs_[0].push_back(current_->files_[level][0]);
      }
  	} else if (seek_compaction) {
  		c->inputs_[0].push_back(current_->file_to_compact_)a
  	} else {
  		return NULL;
  	}
  	//根据inputs[0]来生成inputs[1]
  	SetupOtherInputs(c);
  	return c;
}

生成compaction信息后，便可开始compaction流程，如果level+1没有文件与待compaction的文件存在重叠，则可以考虑将文件直接下移，但是下移后也不能造成之后的compaction数据量过大，LevelDB这里是通过grandparent层级(level+2)的重叠数据量来判断的:

1
2
3
4
5
6

IsTrivialMove() {
	//如果level+2层存在与compact_range重合的数据较大，则不允许直接移动文件，否则之后会造成大量的compaction
	 return (num_input_files(0) == 1 && num_input_files(1) == 0 &&
          TotalFileSize(grandparents_) <=
            MaxGrandParentOverlapBytes(vset->options_));
}

如果不是直接平移，则调用DoCompactionWork来修改sstable，机制如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

//根据输入在高层生成新的sstfile
DoCompactionWork() {
	//对所有传入的sstfile中的键值使用归并排序合并
	Iterator* input = versions_->MakeInputIterator(compact->compaction);
	input->SeekToFirst();
	//遍历所有key
	for ( input->Valid() ) {
		bool drop = false;
		 if (!ParseInternalKey(key, &ikey)) {
      		// Do not hide error keys
     		current_user_key.clear();
      		has_current_user_key = false;
     		last_sequence_for_key = kMaxSequenceNumber;
    	} else {
    		if (!has_current_user_key ||
          user_comparator()->Compare(ikey.user_key,
                                     Slice(current_user_key)) != 0) {
        //这个user_key是第一次出现
        current_user_key.assign(ikey.user_key.data(), ikey.user_key.size());
        has_current_user_key = true;
        last_sequence_for_key = kMaxSequenceNumber;
      	}

      	if (last_sequence_for_key <= compact->smallest_snapshot) {
        // last_sequence_for_key比快照中的key还旧，需要删除
        drop = true;    // rule A
      } else if (ikey.type == kTypeDeletion &&
                 ikey.sequence <= compact->smallest_snapshot &&
                 compact->compaction->IsBaseLevelForKey(ikey.user_key)) {
       			// 一个被标记为删除的key满足如下所有条件，才可删除：
        		// (1) 更高层不会出现该key
        		// (2) 更低层的key的sequence number更小
        		// (3) 符合如上规则A
        		drop = true;
      		}

      		last_sequence_for_key = ikey.sequence;
    	}

	 	//如果该key不需要删除，则写入新的sstfile中
	 	if(!drop) {
	 		//如果当前output file为空则打开一个output file

	 		if (compact->builder->NumEntries() == 0) {
        		compact->current_output()->smallest.DecodeFrom(key);
     		}
      		compact->current_output()->largest.DecodeFrom(key);
      		compact->builder->Add(key, input->value());

      		//如果当前output file过大，则关闭它
	 	}
	 	input->Next();
	 }
}

其中，LogAndApply是根据VersionEdit来生成新的version，并将新生成的version数据append到manifest中来进行持久化存储，这部分会在下节展开。

Version

Version机制作用简要概括如下：

• 维护sstfile的索引信息，包括每层由哪些文件，每个文件的key range等
• 根据sstfile信息，生成compaction相关的信息
• 在每次compaction后，将元数据持久化至manifest中，供DB启动或恢复时加载
• 维护版本信息，在此基础之上生成快照

Version机制涉及到数据结构主要有三个：Version，VersionEdit，VersionSet，其中每个Version都记录了当前sstfile的索引信息，每次compaction后都会生成一个新的version，而这次compaction的文件变化情况就是用VersionEdit来记录的，简单来说就是：

1

version0 + versionedit = version1

此外，为了支持快照及MVCC，老的version不会马上就删除，而是通过VersionSet来管理，VersionSet中所有的version是通过双向链表来连接的，这样可以方便地查找各个version对应的数据，简单来说就是：

1

versionset = version0 + version1 + ... + currentversion

如下所示：

VersionEdit

VersionEdit的主要结构如下，它记录了一次compaction后sstfile的变化信息，包括新增哪些文件、删除哪些文件、某个level参与compaction的最大key是什么：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//一个VersionEdit总是与一次compaction相关
class VersionEdit {
  //要删除的文件集合
  typedef std::set< std::pair<int, uint64_t> > DeletedFileSet;
  //要新增的文件集合
  std::vector< std::pair<int, FileMetaData> > new_files_;
  //记录此次compaction时，某层参与的最大key，下次compaction时会选择该key的后一个文件来进行compaction
  std::vector< std::pair<int, InternalKey> > compact_pointers_;

  void SetCompactPointer(int level, const InternalKey& key) {};

  void AddFile(int level, uint64_t file,
               uint64_t file_size,
               const InternalKey& smallest,
               const InternalKey& largest) {} ;
   
  void DeleteFile(int level, uint64_t file) {};
};

Version

LevelDB是通过version来记录数据库是有哪些sst文件组成的，每次compaction后都会生成新的version，version是LevelDB实现快照和MVCC的基础，它的主要结构如下：

1
2
3
4
5
6
7
8
9
10
11
12

class Version {
	VersionSet* vset_; 
	//更旧的版本
	Version* next_;
	//更新的版本
	Version* prev_;
	//该version的引用数，初始为1，读取或者创建快照都会增加引用数
	int refs_;

	//当前sst文件的索引信息
	std::vector<FileMetaData*> files_[config::kNumLevels];
};

其中一个很重要的成员是引用数。。在一次compaction后，需要删除的sst文件并不会立马删除，因为此时可能会有读请求或者快照仍需要查找旧的文件来获取数据，这都是通过引用计数来控制的。一个version在生成时默认引用数为1，引用数变为0的时候便可以删除，当读请求释放或者该version不是最新版本时，refs_都会减1。总的来说，LevelDB的MVCC和快照机制是由一下几个部分组成：

• sst文件是不可变的，在compaction的时候也不影响read
• 每个key在内部存储时都会带上SequenceNumber，打快照时只需记录对应的SequenceNumber即可
• version通过引用计数来保证资源的有效性，防止write影响read或者影响快照

VersionSet

VersionSet管理系统当前所有version，并负责这些元数据的持久化，其中最重要的方法就是LogAndApply，在每次version发生变化时该方法都会被调用，根据VersionEdit生成一个最新的Version，并 插入链表头部，持久化存储在manifest中，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

LogAndApply(VersionEdit* edit, port::Mutex* mu) {
	Version* v = new Version(this);
  	{
    	Builder builder(this, current_);
    	//将edit生效，记录在builder中
    	builder.Apply(edit);
    	//生成新的version
    	builder.SaveTo(v);
  	}
  	Finalize(v);

  	//创建新的manifest文件
  	if (descriptor_log_ == NULL) {
    // No reason to unlock *mu here since we only hit this path in the
    // first call to LogAndApply (when opening the database).
    assert(descriptor_file_ == NULL);
    new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
    edit->SetNextFile(next_file_number_);
    s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
    if (s.ok()) {
      descriptor_log_ = new log::Writer(descriptor_file_);
      s = WriteSnapshot(descriptor_log_);
    }
  }

  //写入manifest时候，可以释放锁，让其他写入线程能进去队列排队
  {
    mu->Unlock();

    // Write new record to MANIFEST log
    //将变化写入manifest中
    if (s.ok()) {
      std::string record;
      edit->EncodeTo(&record);
      s = descriptor_log_->AddRecord(record);
      if (s.ok()) {
        s = descriptor_file_->Sync();
      }
      if (!s.ok()) {
        Log(options_->info_log, "MANIFEST write: %s\n", s.ToString().c_str());
      }
    }

    // If we just created a new descriptor file, install it by writing a
    // new CURRENT file that points to it.
    //将current文件指向最新的manifest文件
    if (s.ok() && !new_manifest_file.empty()) {
      s = SetCurrentFile(env_, dbname_, manifest_file_number_);
    }

    mu->Lock();
  }

  if(s.ok()) {
  	//将版本v插入头部，使current_指向该版本
  	AppendVersion(v);
  }
}

触发机制

LevelDB中总共有以下几种情况会出发compaction：

• memtable达到阈值时会出发minor compaction
• 手动触发：系统提供结构供用户指定key range及level来出发compaction，默认情况下，手动触发的compaction比自动触发的高
• 文件数触发：由于level 0中的文件间key range可能存在重叠，所以需要严格控制该层的文件数，该层的文件数大于阈值的时候并发触发major compaction
• 容量触发：level 0之上的文件需要严格控制容量，提高查询效率和避免过大的数据参与compaction，所以当level 0上某层的总数据量超过阈值时，便会触发major compaction
• seek触发：系统在查找Key时会记录查找次数，由于每次查找都会消耗额外的IO，当查找次数过多时，对应的IO消耗会大于一次compaction所带来的IO，此时系统会触发compaction来降低某些key的查找次数

Reference

庖丁解LevelDB之版本控制

浅析 Bigtable 和 LevelDB 的实现

leveldb之Version VersionEdit and VersionSet

LevelDB中主要有以下几种文件：

1
2
3
4
5
6
7
8
9

enum FileType {
  kLogFile,
  kDBLockFile,
  kTableFile,
  kDescriptorFile,
  kCurrentFile,
  kTempFile,
  kInfoLogFile  // Either the current one, or an old one
};

对应的文件作用如下：

• kLogFile：WAL日志文件，文件名为[0-9]+.log
• kDBLockFile：db锁文件，文明名为LOCK，通过LOCK文件加文件锁（flock）来实现只有一个实例能操作db
• kTableFile：sstable文件，文件名为[0-9]+.sst
• kDescriptorFile：db元数据文件，存储系统中version信息，文件名为MANIFEST-[0-9]+，每当db发生compaction时，对应的versionedit会记录到descriptor文件中
• kCurrentFile：记录当前使用的descriptor文件名，文件名为CURRENT
• kTempFile：临时文件，db在修复过程中会产生临时文件，文件名为[0-9]+.dbtmp
• kInfoLogFile：db运行过程中的日志文件，文件名为LOG

下面主要来分析kLogFile文件、kTableFile。

kLogFile

kLogFile是以block为单位组织的，除了文件结尾的block外，每个block的大小为32KB。每个block由若干填入record组成，如下所示：

1
2
3
4
5
6
7
8

Each block consists of a sequence of records:

    block := record* trailer?
    record :=
      checksum: uint32     // type及data部分数据的校验值，大小为4B，用小端序存储
      length: uint16       // data部分的长度，大小为2B
      type: uint8          // FULL, FIRST, MIDDLE, LAST中的一个，大小为1B
      data: uint8[length]  //存储实际数据

block的示意图如下：

每个record的示意图如下：

一个record不会从block的最后6B的位置开始写入（因为一个record至少为7B），所以一个block可能会以trailer结尾，此部分位置会全部填0，读取该block时该部分数据会被跳过。由于每个block的大小固定，一条wal日志可能需要被切分到多个block中的record中存储，type这个字段记录的便是这个record的类型，目前只有上文所列的四种类型。FULL表示当前record存储的是一条完整的日志，FIRST、MIDDLE、LAST分别代表一条日志的头部、中部、尾部三个部分，通过多个record的拼接可还原出一条完整的日志。

log写入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

AddRecord(const Slice& slice) {
  
  Status s;
  bool begin = true;
  do {
    const int leftover = kBlockSize - block_offset_;
    assert(leftover >= 0);
    if (leftover < kHeaderSize) {
      // 如果当前block剩余空间小于7B，则在block尾部填0后切换至新的block
      if (leftover > 0) {
        // 尾部填0
        assert(kHeaderSize == 7);
        dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));
      }
      block_offset_ = 0;
    }

    const size_t avail = kBlockSize - block_offset_ - kHeaderSize;
    const size_t fragment_length = (left < avail) ? left : avail;

    //填入该record的type
    RecordType type;
    const bool end = (left == fragment_length);
    if (begin && end) {
      type = kFullType;
    } else if (begin) {
      type = kFirstType;
    } else if (end) {
      type = kLastType;
    } else {
      type = kMiddleType;
    }

    //写入record
    s = EmitPhysicalRecord(type, ptr, fragment_length);
    ptr += fragment_length;
    left -= fragment_length;
    begin = false;
  } while (s.ok() && left > 0);
  return s;
}

log读取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

ReadRecord(Slice* record, std::string* scratch) {
  Slice fragment;
  while (true) {
    const unsigned int record_type = ReadPhysicalRecord(&fragment);
    //计算该block中下个实际record的偏移值
    uint64_t physical_record_offset =
        end_of_buffer_offset_ - buffer_.size() - kHeaderSize - fragment.size();

    switch (record_type) {
      case kFullType:
        //如果读取的record是完整的一条记录，则直接返回读取到的数据
        scratch->clear();
        *record = fragment;
        return true;

      case kFirstType:
       
        //读取到的是第一个record，存储在scratch中，继续读取
        scratch->assign(fragment.data(), fragment.size());
        in_fragmented_record = true;
        break;

      case kMiddleType:
        //读取到中间record，拼接数据，继续读取
        scratch->append(fragment.data(), fragment.size());
        break;

      case kLastType:
       //读取到最后一个record，拼接数据，继续读取
        if (!in_fragmented_record) {
          ReportCorruption(fragment.size(),
                           "missing start of fragmented record(2)");
        } else {
          scratch->append(fragment.data(), fragment.size());
          *record = Slice(*scratch);
          last_record_offset_ = prospective_record_offset;
          return true;
        }
        break;
    }
  }
  return false;
}

kTableFile

kTableFile是db中持久化存储数据的文件，它也是以block的形式来组成文件，整体上看，它主要有数据block、元数据block组成，由于kTableFile文件尺寸可能较大，读取时如果从头扫描这个文件会造成读取效率低下，所以kTableFile文件中也存储data block及meta block的索引信息来加速读取，整体格式如下：

1
2
3
4
5
6
7
8
9
10
11
12

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer]        (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

整体示意图如下：

其中，data_block存储的实际kv数据，index block中保存的是每个data block的last key及其在文件中的索引（偏移量，大小），当前版本中，meta block及metaindex block均未实现。Footer是文件尾部固定长度的块，存储的是metaindex block及index block的索引信息。
每个data block在生成时，会在其尾部存储1B的type和4B的crc，分别记录该block的压缩类型及数据校验值。Block中的每个record（rentry）存储了一条kv数据，由于key是连续的，系统会key采用前缀压缩的方式来减少所需存储空间，只需存储当前key的不同部分，前缀可以从之前的key中获取出来。Block的结构如下:

1
2
3
4
5
6
7
8
9
10

Block := entry* 
		 trailer 
		 type //压缩类型，1B
		 crc // 数据校验值，4B
entry := 
		shared_bytes // key中共享前缀的长度
		unshared_bytes // key中非共享前缀的长度
		value_length // value的长度
		key_dalta // key非共享部分内容
		value // value数据

例如第一个key为sam，第二个key为samon，则第二条记录只需存储on这部分数据，前缀可以根据前一个key获取出来，此时该entry对应的各部分如下：

1
2
3

shared_bytes: 3
unshared_bytes: 2
key_dalta: on

通过这种前缀压缩的方式可以降低所需存储空间。此外，如果一个block完全按照前文所述逻辑进行压缩，每次查找key的时候都要从头开始遍历，这样的查找效率可能较低。所以系统进一步细化了粒度，采用分段压缩，每个段内的key都以第一个key开始做前缀压缩，这第一个key就被称作重启点，block中所有重启点的偏移值和数量都会记录在trailer中。

References

• 淘宝leveldb的实现
• 庖丁解LevelDB之数据存储

在本文中，我们来看在调查某个主机的性能问题时，前60S内应该首先查看哪些信息，从而快速了解整个主机的运行状况。

在前60S内，通过运行以下10个命令，我们可以对系统的资源使用情况、进程运行状况有个整体了解

1
2
3
4
5
6
7
8
9
10

uptime
dmesg
vmstat 1
mpstat -P ALL 1
pidstat 1
iostat -xz 1
free -m
sar -n DEV 1
sar -n TCP,ETCP 1
top

uptime

1
2

$ uptime 
21:43:21 up 78 days,  3:07,  2 users,  load average: 3.71, 3.08, 3.13

uptime可以使我们快速了解系统的整体负载信息，以上输出中显示的信息依次为：系统当前时间、已运行时间、 登陆用户数、平均负载，其中平均负载这里的三个数字分别表示过去1分钟、5分钟、15分钟内CPU的负载情况。对于CPU的单个核心来说，负载为1.0则说明CPU负载已经较高，没有剩余的资源了，如果长期保持在这个负载的话，则容易造成请求的积压，对于多核CPU，则该值是表示所有核的累加值。在实际定位过程中，主要是以15分钟内CPU的负载数为准，如果15分钟内CPU的负载仍然较高，那就需要注意了

dmesg

dmesg是用来显示内核环缓冲区的内容，内核将各种消息都存放在这里，内核环缓冲区的消息对于诊断系统问题很有用。例如我们可以通过dmesg查看是否有进程因为OOM被杀死、是否有TCP请求被丢弃等

vmstat

vmstat可对操作系统的虚拟内存、进程、CPU活动进行监控，如下所示：

1
2
3
4
5
6
7
8
9
10

$ vmstat 1
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
11  1 2039544 15472068   5000 2144664    0    0   757   262    0    0  5  2 90  4  0
13  1 2039328 15674144   5020 2139396 1248    0 10448    44 89482 181158 13 38 44  5  0
 7  1 2039004 16007556   5020 2122564 1760    0  7672    12 104794 213528 14 40 41  4  0
 3  2 2038660 16180976   5040 2110112 1884    0  3468    20 100660 200327 19 39 37  5  0
 6  2 2038464 16486160   5040 2094924  928    0  7688    12 90962 182643 15 38 43  5  0
 2  2 2038200 16674132   5040 2090216 1060    0 10856    12 56284 108656 14 29 51  5  0
 2  1 2037976 16817976   5052 2091832 1152    0 12184 10828 47027 85099 11 24 59  6  0

以上输出中，主要关注如下列：

• r: 运行队列中的进程数量，即占用CPU的进程数。如果CPU单核上超过3个进程，那么CPU的负载就较高了
• swap: 使用的虚拟内存大小，如果此值较高，说明内存可能不足
• free: 可用内存大小
• si,so: 每秒从交换区写入内存的大小，每秒从内存写入交换区的大小
• us,sy,id,wa,st: 用户空间时间、系统空间时间、空闲时间、等待IO时间、被强制等待CPU的时间。如果us+sy所占的比例较高的话，则说明CPU负载较高，如果wa的比例较高，则说明磁盘可能存在瓶颈

mpstat

mpstat是CPU的实时监控工具，可以检测CPU中每个核的运行状况，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

$ mpstat -P ALL 1
Linux 3.10.107-1-tlinux2-0046 (100.98.49.234) 	12/18/2018 	_x86_64_	(12 CPU)

07:52:07 PM  CPU    %usr   %nice    %sys %iowait    %irq   %soft  %steal  %guest  %gnice   %idle
07:52:08 PM  all    3.17    0.00    0.92    9.19    0.00    0.17    0.00    0.00    0.00   86.55
07:52:08 PM    0    3.03    0.00    2.02   49.49    0.00    0.00    0.00    0.00    0.00   45.45
07:52:08 PM    1    6.00    0.00    2.00   45.00    0.00    1.00    0.00    0.00    0.00   46.00
07:52:08 PM    2    2.00    0.00    1.00   13.00    0.00    0.00    0.00    0.00    0.00   84.00
07:52:08 PM    3    3.00    0.00    0.00    2.00    0.00    0.00    0.00    0.00    0.00   95.00
07:52:08 PM    4    1.98    0.00    0.99    0.99    0.00    0.00    0.00    0.00    0.00   96.04
07:52:08 PM    5   18.00    0.00    3.00    0.00    0.00    0.00    0.00    0.00    0.00   79.00
07:52:08 PM    6    3.06    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00   96.94
07:52:08 PM    7    1.01    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00   98.99
07:52:08 PM    8    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
07:52:08 PM    9    1.01    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00   98.99
07:52:08 PM   10    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  100.00
07:52:08 PM   11    1.00    0.00    1.00    0.00    0.00    0.00    0.00    0.00    0.00   98.00

通过vmstat可以获取CPU的综合使用情况，而通过mpstat可以获取每个CPU核心的使用情况，某些糟糕的程序可能会一直只使用一个CPU核心，而不是运行在所有处理器上，从而导致某个CPU核心负载很高，其他CPU资源却是空闲的。通过mpstat便可诊断这类问题

pidstat

pidstat同top命令类似，用以监控全部或者指定进程的CPU、内存等资源的占用情况，它会将这些信息滚动打印，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

$ pidstat 1
Linux 3.10.107-1-tlinux2-0046 (100.98.49.234) 	12/18/2018 	_x86_64_	(12 CPU)

07:59:50 PM   UID       PID    %usr %system  %guest    %CPU   CPU  Command
07:59:51 PM     0   1008095    0.00    0.99    0.00    0.99     9  kworker/9:2
07:59:51 PM     0   1359487    0.00    0.99    0.00    0.99    10  ceph-osd
07:59:51 PM     0   1360110    2.97    1.98    0.00    4.95     4  ceph-osd
07:59:51 PM     0   1361355    1.98    1.98    0.00    3.96    10  ceph-osd
07:59:51 PM     0   1362096    0.00    0.99    0.00    0.99     2  ceph-osd
07:59:51 PM     0   1362981    0.99    0.00    0.00    0.99     5  ceph-osd
07:59:51 PM     0   1365565    1.98    1.98    0.00    3.96     4  ceph-osd
07:59:51 PM     0   1368403    2.97    1.98    0.00    4.95     5  ceph-osd
07:59:51 PM     0   2070599    1.98    2.97    0.00    4.95     5  sap1002
07:59:51 PM     0   2070612    0.00    0.99    0.00    0.99     5  sap1008
07:59:51 PM     0   2430524    0.00    0.99    0.00    0.99     1  pidstat

07:59:51 PM   UID       PID    %usr %system  %guest    %CPU   CPU  Command
07:59:52 PM     0        21    0.00    1.00    0.00    1.00     3  rcu_sched
07:59:52 PM     0       195    0.00    1.00    0.00    1.00     0  kworker/0:1H
07:59:52 PM     0     14132    1.00    1.00    0.00    2.00     8  safe_TsysAgent.
07:59:52 PM     0   1358777    1.00    0.00    0.00    1.00     4  ceph-osd
07:59:52 PM     0   1359487    1.00    0.00    0.00    1.00    10  ceph-osd
07:59:52 PM     0   1360110    5.00    0.00    0.00    5.00     4  ceph-osd
07:59:52 PM     0   1361355    2.00    2.00    0.00    4.00    10  ceph-osd
07:59:52 PM     0   1362981    0.00    1.00    0.00    1.00     5  ceph-osd
07:59:52 PM     0   1363880    1.00    0.00    0.00    1.00     5  ceph-osd
07:59:52 PM     0   1364665    1.00    1.00    0.00    2.00    10  ceph-osd
07:59:52 PM     0   1365565    3.00    0.00    0.00    3.00     4  ceph-osd
07:59:52 PM     0   1366476    1.00    0.00    0.00    1.00     4  ceph-osd
07:59:52 PM     0   1367460    1.00    1.00    0.00    2.00     4  ceph-osd
07:59:52 PM     0   1368403    3.00    2.00    0.00    5.00     5  ceph-osd
07:59:52 PM     0   1646795    0.00    1.00    0.00    1.00    10  kworker/10:1
07:59:52 PM     0   2417476    1.00    0.00    0.00    1.00     7  fdbcli
07:59:52 PM     0   2430524    0.00    1.00    0.00    1.00     1  pidstat

iostat

iostat用以监控系统中的IO状态，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

$ iostat -xz 1
Linux 3.10.107-1-tlinux2-0046 (100.98.49.234) 	12/18/2018 	_x86_64_	(12 CPU)

avg-cpu:  %user   %nice %system %iowait  %steal   %idle
           4.84    0.00    1.81    3.57    0.00   89.78

Device:         rrqm/s   wrqm/s     r/s     w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await r_await w_await  svctm  %util
sda               0.06     3.95    0.31    9.31     6.25   190.85    40.97     0.31   31.39    0.36   32.44   3.41   3.28
sdh               0.00     0.23    6.22    1.94   700.92   228.59   227.96     0.11   13.19   11.24   19.44   9.74   7.94
sdm               0.00     0.28    7.77    2.40   875.65   284.36   228.15     0.14   13.44   11.11   20.99   9.64   9.80
sdi               0.00     0.28    6.63    2.20   750.45   242.41   224.79     0.12   13.20   11.34   18.81   9.75   8.61
sdk               0.00     0.30    7.66    2.27   871.22   276.49   231.28     0.13   13.44   11.06   21.49   9.64   9.57
sdd               0.00     0.29    5.83    2.65   646.21   216.63   203.62     0.10   12.33   11.12   15.00   9.14   7.75
sdl               0.00     0.24    5.96    1.92   676.90   220.14   227.71     0.10   12.91   10.96   18.95   9.54   7.52
sdj               0.00     0.27    7.15    2.17   805.51   261.04   228.82     0.12   13.14   11.06   20.01   9.63   8.98
sde               0.00     0.27    7.17    2.12   799.00   264.21   228.99     0.12   13.31   11.10   20.78   9.67   8.98
sdc               0.00     0.29    6.81    2.25   772.16   249.00   225.44     0.12   13.38   11.16   20.10   9.63   8.73
sdb               0.00     0.27    6.98    2.08   788.66   256.29   230.90     0.12   13.52   11.27   21.10   9.78   8.86
sdf               0.00     0.21    5.35    1.76   607.02   197.17   226.41     0.09   12.69   11.06   17.65   9.61   6.82
sdg               0.00     0.24    6.69    2.03   768.27   243.12   232.07     0.12   13.36   11.24   20.37   9.75   8.50

各列的含义如下：

• r/s, w/s,rKB/s,wKB/s: 一秒内读次数、写次数、读数据大小、写数据大小
• await: IO的平均响应时间，包括IO’的等待时间、服务时间，如果这个时间较长，则说明磁盘可能存在瓶颈。一般来说，这个时间应该小于5ms
• svctm: IO的平均服务时间，如果该值比较接近await，则说明IO几乎没有等待时间
• avgqu-sz: IO的平均队列长度，如果该值超过1，则说明排队请求较多，磁盘可能存在瓶颈
• %util: 磁盘用以IO操作的时间百分比，如果该值接近100%，则说明产生的IO请求太多，磁盘负载已经很高

free

free可以用以显示系统的内存使用状况，如下所示:

1
2
3
4
5

$ free -m
             total       used       free     shared    buffers     cached
Mem:        245998      24545     221453         83         59        541
-/+ buffers/cache:      23944     222053
Swap:            0          0          0

其中最后一行表示swap分区的使用信息，第二行是操作系统层面的内存使用情况，其中buffers是buffer缓存内存数（写缓存），cached是page cache使用的内存缓存数（读缓存），第三行是减去buffer、cache的已使用量和加上buffer、cache的空闲量，这是用户层面的统计信息，因为对于用户程序来说，buffers、cached占用的内存是可以立即重新分配，供用户程序使用的。

sar

sar是目前Linux上最为全部的系统性能分析工具之一，我们可以通过sar来查看网络吞吐状况，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

$ sar -n DEV 1
Linux 3.10.107-1-tlinux2-0046 (100.98.49.234) 	12/18/2018 	_x86_64_	(12 CPU)

08:37:57 PM     IFACE   rxpck/s   txpck/s    rxkB/s    txkB/s   rxcmp/s   txcmp/s  rxmcst/s
08:37:58 PM     bond1   2215.00   2259.00   1621.38   1712.75      0.00      0.00      2.00
08:37:58 PM      eth0   1305.00   1068.00    992.93    724.90      0.00      0.00      1.00
08:37:58 PM      eth1    910.00   1191.00    628.45    987.85      0.00      0.00      1.00
08:37:58 PM        lo      3.00      3.00      0.99      0.99      0.00      0.00      0.00

08:37:58 PM     IFACE   rxpck/s   txpck/s    rxkB/s    txkB/s   rxcmp/s   txcmp/s  rxmcst/s
08:37:59 PM     bond1   3327.00   3264.00   2411.48   2390.17      0.00      0.00      2.00
08:37:59 PM      eth0   1889.00   1508.00   1377.83   1035.24      0.00      0.00      1.00
08:37:59 PM      eth1   1438.00   1756.00   1033.66   1354.92      0.00      0.00      1.00
08:37:59 PM        lo      0.00      0.00      0.00      0.00      0.00      0.00      0.00

08:37:59 PM     IFACE   rxpck/s   txpck/s    rxkB/s    txkB/s   rxcmp/s   txcmp/s  rxmcst/s
08:38:00 PM     bond1   3025.00   3221.00   2189.47   2477.83      0.00      0.00      3.00
08:38:00 PM      eth0   1914.00   1621.00   1412.42   1133.86      0.00      0.00      1.00
08:38:00 PM      eth1   1111.00   1600.00    777.05   1343.97      0.00      0.00      2.00
08:38:00 PM        lo      0.00      0.00      0.00      0.00      0.00      0.00      0.00

每列的含义如下：

• rxpck/s, txpck/s: 每秒接收、发送的包数目
• rxkB/s, txkB/s: 每秒接收、发送的数据大小

我们也可以通过sar来查看主机上TCP连接的状况，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

$ sar -n TCP,ETCP 1
Linux 3.13.0-49-generic (titanclusters-xxxxx)  07/14/2015    _x86_64_    (32 CPU)

12:17:19 AM  active/s passive/s    iseg/s    oseg/s
12:17:20 AM      1.00      0.00  10233.00  18846.00

12:17:19 AM  atmptf/s  estres/s retrans/s isegerr/s   orsts/s
12:17:20 AM      0.00      0.00      0.00      0.00      0.00

12:17:20 AM  active/s passive/s    iseg/s    oseg/s
12:17:21 AM      1.00      0.00   8359.00   6039.00

12:17:20 AM  atmptf/s  estres/s retrans/s isegerr/s   orsts/s
12:17:21 AM      0.00      0.00      0.00      0.00      0.00

每列的含义如下：

• active/s: 本地每秒初始化的TCP连接数（通过connect（）连接远程服务器）
• passive/s: 每秒远程连接的TCP数（通过accept（）接收远程连接）
• retrans/s: 每秒TCP包重发次数，它通常是网络服务出现问题的标志（如出现丢包、网络负载太高等）

top

top命令可以简单快捷地统计系统中的资源使用情况、进程运行状况等，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

$ top
top - 20:47:16 up 79 days,  2:11, 10 users,  load average: 1.46, 2.02, 2.47
Tasks: 325 total,   1 running, 324 sleeping,   0 stopped,   0 zombie
%Cpu(s):  1.0 us,  0.5 sy,  0.0 ni, 98.4 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
KiB Mem : 32281840 total,   393664 free, 19142128 used, 12746048 buff/cache
KiB Swap:  2088956 total,   651716 free,  1437240 used.  8835108 avail Mem 

    PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                                                                                                               
1362981 root      20   0 1764960 693536   3476 S   6.7  2.1   1174:25 ceph-osd                                                                                                              
2070599 root      20   0   20920  19808    680 S   6.7  0.1 814:04.35 sap1002                                                                                                               
      1 root      20   0  193084   3432   1264 S   0.0  0.0  12:52.37 systemd                                                                                                               
      2 root      20   0       0      0      0 S   0.0  0.0   0:03.77 kthreadd                                                                                                              
      3 root      20   0       0      0      0 S   0.0  0.0   8:08.06 ksoftirqd/0                                                                                                           
      5 root       0 -20       0      0      0 S   0.0  0.0   0:00.00 kworker/0:0H                                                                                                          
      7 root      rt   0       0      0      0 S   0.0  0.0   0:53.07 migration/0                                                                                                           
      8 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcu_bh                                                                                                                
      9 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/0                                                                                                               
     10 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/1                                                                                                               
     11 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/2                                                                                                               
     12 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/3                                                                                                               
     13 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/4                                                                                                               
     14 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/5                                                                                                               
     15 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/6                                                                                                               
     16 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/7                                                                                                       
     17 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/8                                                                                                               
     18 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/9                                                                                                               
     19 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/10                                                                                                              
     20 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcuob/11                                                                                                              
     21 root      20   0       0      0      0 S   0.0  0.0  94:17.16 rcu_sched

通过此命令可一目了然得看出系统资源的负载是否较高，哪些进程占用了较多资源等，以便进一步分析

References

• Linux Performance Analysis in 60,000 Milliseconds

rgw-multisite主要涉及涉及到三种日志：

• metadata log
• data log
• bucket index log

基本概念

• zone：每个zone都是独立的ceph集群，包含osd、mon、rgw等，不会跨集群，A zone in the RGW multisite system is a set of radosgw daemons serving the same data, backed by the same set of RADOS pools in Ceph（由一组rgw提供服务，对应一组后台的pool）
• zonegroup：可以包含多个zone，zone之间同步元数据和数据，其中只有master zone能修改元数据
• realm：独立命名空间，可以包含zonegroup，zonegroup之间同步元数据，只有master zonegroup能修改元数据，用以支持在同一组集群中运行不同配置
• period：拥有唯一id和epoch，用以保持当前realm的状态，每个realm都有当前关联的period以及一组按照时间顺序排列的period
• user：user在realm里是全局唯一的
• bucket：在realm里是全局唯一的，且只属于一个zonegroup
• A sync module is a set of callbacks that are called for each change that happens in data (and potentially in metadata, e.g., bucket creation, new user, etc.; note: object’s metadata change is regaded as change in data) in a single zone-group. sync module是针对底层数据变化实现的一系列回调，每个zone都有一个对应的sync module，这个sync module决定了这个对应的zone能否导出数据

日志格式

核心机制

集群配置同步（realm sync）

• 变更极致类似于git，需要update后再提交才能被其他节点感知，首次使用时需要通过pull命令来获取更新，之后的推送是主动的（RGWPeriodPusher实现了RGWRealmWatcher接口）
• RGWPeriodPusher：与其他节点一起通过realm watcher 来推送period的更新

元数据同步 （meta sync）

• 元数据同步和数据同步分为全局同步和增量同步，元数据的修改只能发生在master zone上，更新的过程就是通过radosgw admin api来获取metadata log，并更新对应marker

数据同步（data sync）

• 更新的过程就是通过RGW Admin API来获取bilog，并更新对应的marker，从日志处获取信息差异后请求对方zone已变化数据的元数据信息，并调用底层module的相关接口
• zone_data sync status ：init 、 full_sync 、 incremental
  • bucket_instance_state: full_sync 、 incremental
• 执行流程（RGWDataSyncCR）：
  • RGWReadDataSyncStatusCoroutine：获取对应zone的同步状态
    • 从log-pool中获取datalog.sync-status.{source-zone-id}，该obejct存储了同步状态(State)以及日志分片数（state、num_shards）
    • 处理每个日志分片，从log-pool中获取datalog.sync-status.shard.{source-zone-id}.X，该object存储了同步阶段，以及同步的marker
  • 若State 为StateInit，RGWInitDataSyncStatusCoroutine
    • 锁住datalog.sync-status.{source-zone-id}，并创建一个新的object，创建完成之后再锁住
    • 处理每个日志分片，读取remote pool（rgw.log），remote-obj（data_logX）并保存shards_info[X]
    • 对上步获取到的信息shards_info，存入本地集群中local pool(rgw.log)，local obj（datalog.sync-status.shard.{source-zone-id}.X）
    • 将状态改变为StateBuildingFullSyncMaps（修改前文锁住的object并解锁）
  • 若State 为StateBuildingFullSyncMaps，RGWListBucketIndexesCR
    • 创建entries_index（RGWShardedOmapCRManager），local pool(rgw.log), objects( data.full-sync.index.{source-zone-id}.0，。。)obj数等于bucket分片数
    • 从remote zone处获取bucket instances（RGWReadRESTResourceCR）
    • 对于上步获取的每个bucket instance，获取详细信息（RGWReadRESTResourceCR ），详细信息包括：num_shards、name of bucket、index pool、data pool。。，对于每个bucket分片
      • 将key（ {bucket-name-A}:{source-zone-id}.4133.1），value（empty）写入前文entries_index obj 处
    • 对于每个日志分片X，有[bucket，shard]对应与X，该对应关系被写入日志中
  • 若State 为StateSync，对每个日志分片X分别处理（ RGWDataSyncShardControlCR-》RGWDataSyncShardCR）
    • ​

插件机制

sync plugin

• data sync module：获取数据并写入本地，支持数据导出
• log sync module：获取数据的扩展属性，不支持数据导出
• elasticsearch module：获取同步数据的元数据信息

公有云同步

数据同步机制(data sync)

Multi-site 同步示例

本文环境中分为source site 和 secondarysite两个集群，在source site上修改bucket中的数据，在secondary site上观察数据同步状态

数据机制浅析

/** remote site ***/

涉及到的存储池：

• {source-zone}.rgw.data.root：存储bucket instances
• {source-zone}.rgw.buckets.data：存储Objects
• {source-zone}.rgw.buckets.index：存储bucket对应的index objcet（与bucket index 的分片数有关）
• {source-zone}.rgw.log：存储修改日志（与日志分片数有关）

注意：总共有两种分片，分别为bucket shard ， log shard

将bucket 分片与日志分片做映射，假设测试环境中有3个bucket（bucket-0,bucket-1,bucket-2），bucket的分片数为3（rgw_override_bucket_index_max_shards=3），日志分片数为4（rgw_data_log_num_shards=4），那么需要将9个bucket shard 与4个log shard 做映射，之后针对每个bucket shard 的修改都会记录到对应的log shard 之上，下面以objcet的写入为例来分析数据同步流程：

假设将OBJ_test 写入bucket-0 shardS中，该bucket shard 对应与 log shardX，则流程如下:

1) 将OBJ_test写入pool（{source-zone}.rgw.buckets.data）中

2) 将修改信息写入pool（{source-zone}.rgw.buckets.index）的obj（.dir.{key-of-bucket-0}.S）的omap属性中：

​ <OBJ_test， 基本元信息>，<.0_00000000001.4.2，_ write OBJ_444 state=CLS_RGW_STATE_PENDING_MODIFY_>，<.0_00000000002.5.3，write OBJ_444 state=CLS_RGW_STATE_COMPLETE>

之后在omap的header中记录值 0_00000000002.5.3

3) 将修改信息写入pool （{source-zone}.rgw.log）的obj（data_log.X）的omap属性中：

1_1489979397.374156_23.1 =》some info like bucket-B shardS has modification, timestamp

之后再omap的header中记录值1_1489979397.374156_23.1

总结来说，当在某个bucket做了数据修改时，所做的修改都会以kv的形式记录在对应的obj的omap中，其中k为系统生成的有序的marker，v为对应的一些元数据信息，同时在omap的header中会记录最近的一个marker

实例

代码分析

本文接上文，对multi-site中数据同步的部分代码做分析，环境还是分为source-zone和 secondary-zone两个zone分别对应两个seal集群，实验过程中在source-zone上写入object，在secondary-zone上观察数据同步状态 。

RGWDataSyncCR为实际执行数据同步的入口协程，因为本文主要以该类为起点来分析multi-site中数据增量同步（inc_sync）的过程。multi-site的实现中在boost::asio::coroutine的基础之上封装了一个协程库，在该库之上使用了大量协程来完成数据的同步。下面以secondary-zone为视角来分析数据同步过程。

RGWDataSyncCR:

1. RGWReadDataSyncStatusCoroutine：

   从本地集群中获取远端集群数据同步状态（“state”）和日志分片数（“num_shards”），并存入到sync_status.sync_info中，对于远端集群的每个日志分片data-log-shard X，从本地集群中读取该分片同步状态(full-sync inc-sync)、marker、next_step_marker、timestamp这些信息，并存入sync_status->sync_markers[X]中:

   1 2	local-pool: {secondary-zone}.rgw.log local-obj: datalog.sync-status.{remote-zone-id}

2. 如果1中获取的”state”为”StateInit“，RGWInitDataSyncStatusCoroutine：

   2.1 锁住 datalog.sync-status.{remote-zone-id} 这个object

   2.2 重新创建这个object（ datalog.sync-status.{remote-zone-id}）

   2.3 再次锁住这个object

   2.4 对于每个日志分片data-log-shard X，从远程集群中

   1 2	remote-pool: {source-zone}.rgw.log remote-obj: data-log.X

   获取该日志分片的信息，写入shards_info[x]，之后将shards_info[x]写入本地集群中

   1 2	local-pool : {secondary-zone}.rgw.log local-obj : datalog.sync-status.shard.{source-zone-id}.X

   经过这步之后，日志分片的映射情况如下：

   1 2 3 4

   source-zone secondary-zone data_log.0 ======> datalog.sync-status.shard.{source-zone-id}.0 ...... data_log.X ======> datalog.sync-status.shard.{source-zone-id}.X

   2. 5 将数据同步状态设置为”StateBuildingFullSyncMaps”，同时写入本地集群 datalog.sync-status.{remote-zone-id} 这个object中，并将该object解锁

3. 如果1.1中获取的”state”为“StateBuildingFullSyncMaps”，RGWListBucketIndexesCR：

   注：如果是在source-zone和secondary-zone都为空的时候配置multi-site，步骤3不做任何事，因为在build full sync map的时候没有任何数据

   3.1 创建entries_index（ RGWShardedOmapCRManage），用于管理建立full sync map过程中本地的一些obj

   1 2 3 4 5

   local-pool: {secondary-zone}.rgw.log local-obj: data.full-sync.index.{remote-zone-id}.0 data.full-sync.index.{remote-zone-id}.1 ... data.full-sync.index.{remote-zone-id}.N, N = rgw_data_log_num_shards

   由上可知，每个本地的data.full-sync.index object对应于远端集群的一个data_log，下面则需要同步远端bucket的信息，并将bucket分片与本地的data.full-sync.index object建立对应关系

   3.2 调用RGWReadRESTResourceCR从source zone处获取所有bucket instance

   1 2 3 4 5

   remote-pool : {source-zone}.rgw.data.root remote-obj: .bucket.meta.{bucket-name-A}:{remote-zone-id}.4133.1 .bucket.meta.{bucket-name-B}:{remote-zone-id}.4139.2 .bucket.meta.{bucket-name-C}:{remote-zone-id}.4138.3 ....

   3.3 对于3.2步中获取的每个bucket instance（例如 {bucket-name-A}:{remote-zone-id}.4133.1）调用RGWReadRESTResourceCR 获取该bucket的详细信息，包括：bucket分片数（即该bucket的index分片数）、bucket的名字、index pool、data pool等，对于每个bucket分片，做如下处理（以分片i为例）：

   1 2 3

   # 假设分片i映射到了日志分片data_log.X上 set omap (key:{bucket-name-A}:{source-zone_id}.4133.1 val:empty) to local obj(local-pool: {secondary-zone}.rgw.log, local-obj:data.full-sync.index.{remote-zone-id}.X)

   最后，data.full-sync.index.{remote-zone-id}.X上记录了对应的remote-zone上的bucket 分片，例如：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   # rados -p {zone}.rgw.log listomapkeys data.full-sync.index.{remote-zone-id}.3 testbuckAAA:900d449b-3c56-4949-8b88-bc8a6d4ee3b1.4122.1:1 testbuckAAA:900d449b-3c56-4949-8b88-bc8a6d4ee3b1.4122.1:5 testbuckBBB:900d449b-3c56-4949-8b88-bc8a6d4ee3b1.4123.2:1 testbuckBBB:900d449b-3c56-4949-8b88-bc8a6d4ee3b1.4123.2:5 testbuckCCC:900d449b-3c56-4949-8b88-bc8a6d4ee3b1.4124.3:1 testbuckCCC:900d449b-3c56-4949-8b88-bc8a6d4ee3b1.4124.3:5 这就是说： testbuckAAA, shard1 testbuckAAA, shard5 testbuckBBB, shard1 testbuckBBB, shard5 testbuckCCC, shard1 testbuckCCC, shard5 这几个bucket分片被映射到data_log.X这个分片上

   3.4 对于每个日志分片data_log.X，记录被映射到这个日志分片上的bucket 分片数量：

   1 2	local-pool : {secondary-zone}.rgw.log local-obj : datalog.sync-status.shard.{remote-zone-id}.X

   ​

4. 如果1中获取的”state”为“StateSync”，对于每个日志分片 data-log-shard X，调用RGWDataSyncShardCR::incremental_sync来进行增量同步：

   4.2 创建set_marker_tracker（RGWDataSyncShardMarkerTrack），用来记录一个bucket shard是否在流程中和更新一个marker

   5. 5 读取远端集群中data-log.X这个object的omap header，header中包含的信息由max_marker，max_time， 如果读取的max_marker比本地记录的marker更旧的话，那么此次增量同步结束

      4.6 如果读取的max_marker比本地记录的marker更新的话，从远端集群中的data-log.X中读取这个object的omap kv对（每个kv对为一个entry），从RGWDataChangesLog::add_entry方法中可以看出这些kv对是如何组成的：

   1 2	1_1489653363.684562_381.1 => some info including bucke-tname, bucked-id, bucket-shard, modification timestamp 1_1489653363.684562_381.1这个key是在 cls/log/cls_log.cc:cls_log_add中根据时间戳生成的

   对于一个bucket的任何修改都会生成一个这样的kv对存储在对应的日志分片上，因此扫描一个日志分片data_log.X的话，结果如下：

   1 2 3 4 5 6

   # rados -p {source-zone}.rgw.log listomapkeys data_log.X 1_1490768507.881727_3.1 => some info like bucket-2 shard3 has modification timestamp1 1_1490768519.257779_4.1 => some info like bucket-5 shard1 has modification timestamp2 1_1490768527.759371_5.1 => some info like bucket-1 shard4 has modification timestamp3 1_1490768541.378290_6.1 => some info like bucket-6 shard0 has modification timestamp4 ......

   4.7 对于4.6中返回的每个entry，如果它还没有在处理流程中（由4.2中创建的marker_tracker判断），则通过协程RGWDataSyncSingleEntryCR来处理每个entry：

   • 解析该entry从而获取bucket_name和bucket_shard_id

   • 调用协程RGWRunBucketSyncCoroutine来处理该bucket shard的数据同步：

     • a) 调用协程RGWReadBucketSyncStatusCoroutine从本地集群中读取对应object的xattrs（包含的信息有：full_marker、inc_marker、lock.sync_lock、lock.sync_lock.incremental、state等）

       1 2	local-pool : {secondary-zone}.rgw.log local-obj : bucket.sync-status.{remote-zone-id}:{bucketname}:{bucket_id}:{shard_id}

     • b) 调用协程RGWGetBucketInstanceInfoCR从本地集群中读取bucket instance的信息

     • c) 如果步骤a中获取的state为rgw_bucket_shard_sync_info::StateInit（与步骤1中获取的状态不同，步骤一种状态为rgw_data_sync_info::StatInit），调用协程 RGWInitBucketShardSyncStatusCoroutine从远端集群中读取对应的bucket index log 的相关信息写入本地集群中，同时将状态置为”StateFullSync”

       1 2 3 4 5

       remote-pool : {source-zone}.rgw.buckets.index remote-obj : .dir.{key-of-bucket-B}.S local-pool : {secondary-zone}.rgw.log local-obj : bucket.sync-status.{remote-zone-id}:{bucketname}:{bucket_id}:{shard_id}

     • d) 如果步骤a中获取的state为StateFullSync，调用协程RGWBucketShardFullSyncCR将状态置为“ StateIncrementalSync”

     • e)如果步骤a中获取的状态为StateIncrementalSync，调用RGWBucketShardIncrementalSyncCR：

       • 调用RGWListBucketIndexLogCR从远端集群中获取bucket分片的相关信息（omap kv对)：

         1 2	remote-pool: {source_zone}.rgw.buckets.index remote-obj : .dir.{key-of-bucket-B}.S

         对于每个kv对，调用RGWBucketSyncSingleEntryCR来对对应的object进行同步：

         • 若这个kv对应的操作没有完成（op_state != CLS_RGW_STATE_COMPLETE），则跳过

         • 若对应的操作已完成（op_state == CLS_RGW_STATE_COMPLETE），则根据具体的操作类型调用RGWDefaultDataSyncModule中的具体方法来实现对该object的操作，具体的方法包括：

           1 2 3

           sync_object: 将远端object同步到本地集群中 remove_object: 将objcet从本地集群中删除 create_delete_marker: 对于开启了version功能的bucket，给对应的object创建一个删除标记，而不是直接删除该object

           ​

rgw_admin.cc::get_data_sync_status分析

• RGWDataSyncStatusManager::init():
  • source_log.init ： 初始化source zone的data_log
  • source_log.read_log_info：获取source zone的data_log数目
• RGWRemoteDataLog::read_sync_status()，将读取结果存储到sync_status中
  • RGWReadDataSyncStatusCoroutine
    • RGWSimpleRadosReadCR<rgw_data_sync_info>：获取sync info
    • RGWReadDataSyncStatusMarkersCR：获取日志分片的marker
• 从sync_status中读取同步状态（init、preparing for full sync 、syncing），计算full sync、inc sync的分片数目
• RGWRemoteDataLog::read_source_log_shards_info()：统计尚未同步的分片数，获取最近的已同步的修改点

推导过程

对于一致性算法来说，安全性要求如下：

• 只有被提出的方案才能被选定（chosen）
• 只有一个值能被选定
• 进程不会学习某个方案，除非这个方案真正被选定了

Paxos就是一个满足上述需求的一致性算法，它的目标是确保最终有一个方案能被选定，然后被所有进程学习，Paxos中有三种角色：proposers , acceptors, learners，所有的角色都能互通信，并由如下前提：

• agent以不固定速度运行，可能会停止或者重启。因为即使一个提案被选定了，agent也可能重启，因此被选定的提案能持久化存储，否则无法确定最终的值
• 消息在传输过程中可能会丢失、重复，等内容不会被篡改

首先，即使只有一个提案被提出，我们仍要确保最终有一个方案会被选定，这就暗示这如下需求：

1

P1: 一个Acceptor必须批准它接收到的第一个提案

但是这个需求会引出新的问题：如果有多个提案被多个Proposer同时提出，会导致每个Acceptor都批准了一个提案，但没有哪个提案被多数派批准。因此在P1基础上，为了确保最终有提案能被多数派批准，这就意味着一个Acceptor必须能批准不止一个提案，我们使用一个全局唯一的编号来唯一标识每一个被Acceptor批准的提案，此时可以用[编号，value]来表示一个提案，当一个提案被多数派批准之后，我们就说这个提案被选定了（chosen）。我们可以允许多个提案被选定，但是我们必须确保被选定的提案都具有相同的值，即有如下需求：

1

P2: 如果一个值为V的提案被选定了，那么被选定(chosen)的更高编号的提案的值也必须为V

因为编号是全局有序递增的，这样才能确保最终只有一个值能被选定。一个提案被选定意味它至少被一个Acceptor批准，因此我们可以满足如下条件来满足P2：

1

P2a: 如果一个值为V的提案被选定了，那么被批准(accept)的更高编号的提案的值也必须为V

此时，我们仍需满足P1，但因为通信是异步的，一个提案（[M0, V0]）可能会在某个Acceptor还未收到任何提案时就被选定了，如果此时某个Proposer产生了一个编号更高，值不为V0提案（[M1, V1], M1>M0, V1 != V0）发送至该Acceptor，那么该提案就会被批准，但这会与P2a相矛盾，因此对P2a进行强化如下：

1

P2b: 如果一个值为V的提案被选定了，那么之后任何Proposer产生的编号更高的提案，其值都必须为V

因此我们满足P2b即可满足P2。接下来我们来讨论如何满足P2b，即如何满足在[M0, V0]被选定时,所有编号Mn > M0的提案，其值也为V0。只需要满足如下约束即可：

1
2
3

P2c: 如果提案[Mn, Vn]被提出，那么肯定存在一个由半数以上Acceptor组成的集合S，满足如下两个条件之一：
- S中的所有Acceptor都没有批准过编号小于Mn的提案
- S中所有Acceptor批准的最大编号的提案的值为Vn

下面我们来证明P2c成立的话，P2b也一定成立。我们可以使用第二数学归纳法来证明，即首先假设提案[M0, V0]被选定了，证明过程如下：

1. 当Mn = M0 + 1时，因为M0已经被选定了，那么肯定不存在一个多数派集合S，其中所有Acceptor都没有批准过编号小于Mn的提案，即P2c中第一个条件肯定不成立了，所以肯定存在多数派Acceptor集合S1，其批准的最大编号的提案只为Vn，因为M0被选定了，所有肯定存在多数派Acceptor集合C，C中每个Acceptor都批准了M0这个提案，因为C与S1必然有交集，所以S1中最大编号的提案一定为M0，所以此时Vn必然等于V0
2. 根据第二数学归纳法，假设编号M0+1 值Mn-1 范围内的所有提案值都为V0，那么如何证明Mn提案的值也为V0呢？根据P2c，肯定存在一个多数派集合S，S中的Acceptor批准了编号小于Mn的提案，且它批准的最大编号的提案的值肯定为Vn，假设这个最大编号落在[M0+1, Mn-1]区间内，则Vn肯定等于V0，若不在这个区间内，那最大编号肯定为M0，此时Vn也肯定等于V0

由此可证明，在P2c的约束条件下，P2b是成立的。从上可看到，从P1到P2c的过程其实是一系列条件的加强，由P2c进行反向推导就可保证P2的成立。将条件逐步加强后，就可以推导出提案的生成步骤了，下面我们来看应该如何满足P2c。

提案流程

Proposer生成提案

下面来看在P2c的基础上如何来生成提案。对于Proposer来说，学习已经被批准或即将批准的提案肯定比预测未来被批准的提案更容易，因此，Proposer在生成提案N时，它需要学习这样一个提案M，M被多数派Acceptor批准且M为小于N中提案中编号最大的提案（如果这个提案存在的话）。既然预测未来提案较难，Proposer可以采取一些方法来反正其他提案（值不相同）被批准，Paxos中采用的方法就是Proposer会要求Acceptor不再批准编号小于N的提案，这就引出了如下提案生成算法：

1.Prepare阶段
Proposer获取一个提案编号N，然后向某个多数派Acceptor集合发出请求，要求集合中的Acceptor做出如下回应：

• 不再批准任何编号小于N的提案
• 反馈已批准的编号小于N中编号最大的提案（如果有的话）

2.Accept阶段
Proposer在接收到半数以上Acceptor的回复之后，生成编号为N的提案[N, V]，V就是在Prepare阶段中所有响应中编号最大的提案的值，如果这些Acceptor都没有批准过任何值的话，V的值就由Proposer决定

在确定提案后，Proposer就会将提案再次发送个半数以上的Acceptor集合，此为Accept请求。需要注意的是，此时的多数派集合跟Prepare阶段的多数派集合并不是一定相等的。

Acceptor批准提案

下面来看Acceptor的处理逻辑，Acceptor会接收到两种请求：prepare及accept，它的处理分别如下：

• Prepare请求：可以在任何时间响应
• Accept请求：在不违背承诺的前提下课任意响应，

即Acceptor批准提案的约束条件如下：

1

P1a: 只有在没有响应过任何编号大于N的prepare请求时，它才能批准这个编号为N的提案

算法整体流程

结合前文内容，可以得到如下类似两阶段提交的Paxos算法执行流程：

阶段一

1. Proposer获取一个提案编号N，然后向一个多数派Acceptor集合发送Prepare请求
2. 如果一个Acceptor接收到一个编号为N的Prepare请求，且N大于它已经响应的所有Prepare请求的编号，它会将自己批准过的编号最大的提案值反馈给Proposer，同时该Acceptor不会再批准任何编号小于N的提案

阶段二

1. 如果Proposer收到半数以上Acceptor的Prepare响应，它就会发送提案为[N, V]的Accept请求至一个多数派Acceptor集合，其中V为响应的prepare请求中编号最大的提案值，如果这个值不存在则V会有该Proposer自行生成
2. 一个Acceptor接收到[N, V]这个提案后，只要它没有响应过编号大于N的Prepare请求，它就可以批准这个提案

在实际使运行过程中，一个proposer可能会产生多个提案，但只要遵循上述流程，就一定能得到最终的正确结果，且一个proposer可以在任意时刻丢弃一个提案。

简介

在大型分布式存储系统中，如果使用哈希分布的方式来将数据打散的话有两个问题需要考虑：

• 如果系统中有设备发生变化，如何在迁移最少数据量的情况下保持系统平衡
• 数据的多个副本之间要如何分布才能使数据有较高的可靠性

显而易见，普通哈希函数是较难解决以上两个问题的，而CRUSH（Controlled Replication Under Scalable Hashing）就是一个在普通哈希之上进行扩展用以解决以上两个问题的数据分布算法。

CRUSH具有如下特点：

• 以数据唯一标识、当前存储集群拓扑结构、数据备份策略作为输入，返回一组存储设备用以保存数据副本
• 只需保存很少元数据（cluster map），只有当设备发生变化时，才会修改这些元数据
• 用公式描述就是CRUSH(X) –> (OSD1, OSD2, OSD…)，其中输入参数包括X（pgid），cluster map，placement rule

Cluster Map

cluster map描述了ceph集群中有层级关系的静态拓扑结构，这样使得CRUSH在选择OSD时有机架感知能力，配合预先定义的placement rule（分布规则），就可以使副本分布在不同机架、机房中，提高数据的可用性。cluster map中包含如下概念：

• Device：OSD，一个OSD对应一个存储设备
• Bucket：设备容器，可以递归包含多个设备或者子类型bucket。目前有root、region、datacenter、room、rack、host等，每个device都有自己的权重，bucket的权重就是子bucket和device的权重之和

Placement rule

通过cluster map来建立集群对应的拓扑结构后，就可以通过placement rule来描述数据分布规则。每条placement rule包含多个操作，这些操作总总共有3种类型：

• take：选择每个bucket，以此为后续步骤的输入
• choose：从输入的bucket中选择指定类型和数量的items
• emit：返回最终结果

一个典型的placement rule有如下定义格式：

1
2
3
4
5
6
7
8

take a
choose 
	choose firstn {num} type {bucket-type}
	chooseleaf firstn {num} type {bucket-type}
		if {num} == 0, choose {pool-num-replicas} buckets 
		if {num} > 0 && < {pool-num-replicas}, choose {num} buckets
		if {num} < 0, choose {pool-num-replicas} - |{num}| buckets
emit

对应的流程如下：

1） take a ：选择a这个bucket，一般为root类型的bucket

2）choose操作有不通的选择方式，其输入都是上一步的输出：

• choose firstn 选出num 个类型为bucket-type类型的bucket
• chooseleaf 先选出num个类型为bucket-type类型的bucket，然后递归到叶节点，选出一个OSD设备：
  • 如果num为0，则num被设置为pool的副本数
  • 如果num大于0且小于pool的副本数，则选择num个
  • 如果num小于0，则选择pool的副本数减去|num|个

3） emit：输出结果

其中chooseleaf firstn {num} {bucket_-type}可以等价为以下两个操作：

​ a）choose firstn {num} {bucket-type}

​ b） choose first 1 osd

如下为一个集群中使用的placement rule实例，采用将3副本分布在不同主机上的容灾模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

root default {
        id -1           # do not change unnecessarily
        id -2 class hdd         # do not change unnecessarily
        # weight 305.650
        alg straw2
        hash 0  # rjenkins1
        item default-100.98.49.161 weight 43.664
        item default-100.98.46.210 weight 43.664
        item default-100.98.49.174 weight 43.664
        item default-100.98.49.234 weight 43.664
        item default-100.98.49.229 weight 43.664
        item default-100.98.49.251 weight 43.664
        item default-100.98.49.224 weight 43.664
}

rule cos_rep_default_host {
        id 7
        type replicated
        min_size 1
        max_size 10
        step take default
        step chooseleaf firstn 0 type host
        step emit
}

Bucket 选择算法

前文描述了CRUSH算法的运行流程，下面来看如何从bucket总选择子item的问题，主要来看有实际使用价值的straw即straw2算法。

顾名思义，straw算法针对特定输入，为每个元素计算一个签长，从中选择长度最长者作为结果输出。每个签长的计算跟元素自身的权重是有关系的，权重越高，被选中的概率就越高。此时，straw的算法执行结果取决于三个因素：固定输入、元素编号及元素权重，其中元素编号是起随机种子的作用，用以在选择失败后进行重试可以得出不同结果，所以针对特定输入（在ceph里就是pgid），straw的算法只受元素权重的影响。进一步来讲，如果每个元素的签长只和自身权重有关，则可以证明此事straw算法对于集群item变更的处理是最优的，以添加元素为例来说明：

1）假设当前集群中有n个元素：（e1 e2 e3 ….e_n)

2）向集群中添加新元素e_n+1，(e1 e2 … e_n, e_n+1)

3）假设在n+1加入之前，针对任意输入X，分别计算每个元素的签长为(d1 d2 … d_n)，并假定其中最大值为d_max：

4）因为新元素的签长计算只和其自身编号有关，且它的加入不会影响其他元素的签长计算，假设针对输入X，新元素的签长为d_n+1

5）因为straw算法是以最长签长元素作为输入的，如果d_n+1 > d_max，那么X将被重新映射至新元素e_n+1，否则则对X的已有映射结果无任何影响

可见，在添加一个元素时，straw会随机得将一些元素映射至新添加的元素中，删除一个元素是，会将该元素中的全部数据随机重新映射，即元素的变更不会导致数据在变更的元素之间迁移（即不会导致额外的数据迁移）。但是原始straw算法在实际使用过程中却被发现会打来额外的数据迁移，社区被迫开始低该算法进行审视，原straw算法伪代码如下：

1
2
3
4
5
6
7
8

max_x = -1
max_item = -1
for each item:
	x = hash(input, r) * item_straw
	if x > max_x :
		max_x = x
		max_item = item
return max_item

可见，算法的选择结果取决于每个元素输入（input）、随机因子（r）和item_straw（权重），但原有算法中item_straw的计算不但取决于每个元素自身的权重，也和集合中所有其他元素的权重相关，从而导致每个元素变化是会到来额外的数据迁移。新修正后的算法被称之为straw2，其伪代码如下：

1
2
3
4
5
6
7
8
9

max_x = -1
max_item = -1
for each item:
	x = hash(input, r) #输出落在[0, 65535]之间
	x = ln(x / 65536) / weight
	if x > max_x :
		max_x = x
		max_item = item
return max_item

CRUSH分析

理论上来讲，只要选择一个好的哈希函数及合理的权重分配，CRUSH算法是能够保证数据在所有磁盘之间均匀分布的，但是实际使用过程中存在如下问题：

• 集群规模较小时，输入样本不够，不一定能保证数据的均衡
• CRUSH算法本身是有缺陷的，前文描述的straw2每次选择item都是计算其独立概率的，但是在实际过程中为了考虑副本的分布策略，却变成了针对item计算条件概率，所以CRUSH也无法真正处理好多副本模式下的副本均匀分布问题
• 设备的权重一般是根据其容量计算得来的，但是容量更大的硬盘不代表性能更高。所以针对异构集群（特质存在容量不一的OSD设备），CRUSH无法较好处理这种情况

因此在实际使用过程中，是允许对CRUSH的计算结果进行人工调整的。在CEPH中，每个设备除了有一个权重之外，还有一个外的reweight，CRUSH在正常选中一个OSD后，还会基于该reweight对OSD进行测试，如果测试失败，则拒绝选择该OSD，reweight调的越高，则测试通过率就越高。weight与reweight的最大区别就是weight是表示osd在crushmap中的权重，它的值一般是固定的，目前一个osd的磁盘主要是根据它的容量来计算的。而reweight是可以在使用过程中调整的，osd的reweight调整不会影响osd之上的bucket的权重，所以对以bucket的选择不会有任何影响，而只是用以选择完osd之后进行一个测试。一般来说，reweight主要是一种临时调整方案，如集群中某些磁盘较满，我们可以在一边扩容的同时，降低这些磁盘的reweight以保持集群的正常使用。

References

• Ceph设计原理与实现 [谢型果 等]
• Ceph源码分析 [常涛 等]
• Difference Between ‘Ceph Osd Reweight’ and ‘Ceph Osd Crush Reweight’

下面以X86平台下32为机器为例来分析Linux的内存管理机制。

用户进程内存管理

在多任务操作系统上，每个进行都是运载自己的内存空间里，这就是虚拟内存，在32位机器上，这个虚拟内存空间拥有4GB的寻址能力，通过页表（page table）我们可以将虚拟内存映射成真是的物理地址。Linux默认会将高地址的1GB空间分配给内核使用，剩下的3GB作为用户空间供用户使用，整体的进程地址空间布局如下：

对应的主要区域如下：

• 内核空间：供操作系统内核使用，用户态程序不能访问

• 栈：维护函数调用的上下文，向下增长，通常有数M大小。通过系统调用expand_stack()可以将分配栈空间，如果栈空间无法增长了（通常已经到8MB）了，则会发生栈溢出
• 堆：应用程序动态分区内存区域，通过brk系统调用来向上增长
• 内存映射区：通过mmap分配，用以映射共享库或映射一个匿名空间供程序使用。mmap是一个高效、方便地操作一个文件，通过mmap将动态库映射至内存中可以实现快速加载，或者通过mmap映射出一个不跟任何文件关联的匿名空间来供用户程进程使用。在Linux中，如果你通过malloc申请一块打内存的话（通常是大于128KB），glibc通常会调用mmap系统调用来分配内存
• BSS、DATA、TEXT：存储用户程序数据段、代码段等。其中BSS、DATA存储的都是存储程序全局或静态变量，不同的是BSS存储的是为初始化的变量

如上图所示，每个段之间可能会有部分随机偏移值，即每段的开始位置并不是固定的，这样有利于降低被攻击的风险。通过/proc/{pid}/maps这个文件，可以观察进行的内存使用情况。

内核空间内存管理

如下图所示，Linux中的进程实例是通过task_struct这样一个结构来描述的，该结构中的mm这个域指向一个内存描述符mm_struct，记录了进程执行期间它的内存摘要。如图所示，它存储了进程中每个段的起始位置、物理页的数目、虚拟空间的使用情况等。

在内存描述符中(mm_struct)，我们还可以找到两个重要的结构：虚拟内存区域集合（the set of virtual memory areas ）及页表（page tables）。如下，为一个内存区域集合：

每个VMA（virtual memory area）是一段连续的、不会重叠虚拟地址，一个vm_area_struct实例完整得描述了一个内存区域，包括起始、结束地址，flags描述的访问权限及行为，以及vm_file描述的对应的映射文件（如果有的话，没有的话这段内存区域就是匿名的）。

一个进程的VMA会以两种形式存储在存储在其内存描述符中：以链表的形式存储在mmap域中，以红黑树的心事存储在mm_rb域中。红黑树的形式使得内核可以快速查找出给定虚拟地址对应的内存区域，当我们读取/proc/{pid}/maps文件时，内核可以快速恢复出其VMA链表。

Linux在通常情况下会使用4KB大小的页来映射用户空间的虚拟空间，处理器会通过页表（page tables）来将虚拟地址转换为物理地址，Linux在内存描述符的pgd域中存储了指向进程page tables的指针，每个虚拟内存页在page tables里都会有一个页表项(page table entry(PET))与之对应，通常来说，PTE在x86架构下是一个大小为4byte的记录，如下所示：

如上各个位的作用如下：

• P：标识该虚拟页是否在内存中，0表示不在内存中，访问该页会出发缺页异常
• R/W：标识是否可读/写，如果为0，则页面为只读
• U/S：标识是用户/管理员，如果为0，只能供内核使用
• D：标识是否为脏页面，脏页面表示执行过写操作
• A：标识是否被访问过

虚拟内存并不存储任何东西，仅仅是将一个进程的地址空间映射至真实的物理地址空间上。这个物理地址空间被内核切分成一个个页帧（page frames），它是物理内存管理的最小单位，32为X86架构下，Linux通常采用4KB大小的页帧，每个页帧在内核中都有一个描述符和标志位进行追踪。下面我们把VMA，PTE、page frame连起来看它们是如何工作的，如下所示为一个用户堆内存：

蓝色矩形表示VMA范围内的页，箭头表示通过PTE将虚拟页映射至page frame，没有箭头指出的虚拟页，意味着这个页的P flag为0，即这个虚拟页从来没有被访问或者刚被置换出来。VMA就是进程与内核之间的签约，进程对内核发起请求（内存分配，文件映射等），内核同意后创建或者更新对应的VMA，但它不是立即就将虚拟页映射至物理页，而是在发生缺页异常的时候才会真正映射，所以实际情况是VMA记录进程同内核达成的协议，PTE记录内核实际已经执行了哪些操作。以下为内存分配的一个例子：

当进程通过brk()申请申请内存时，内核只是更新对应VMA后便返回，并没有实际的物理页被分配，当进程访问这个页时，内核会去寻找对应的VMA，如果找到了会做前置检查（读写权限等），如果没找到，说明进程访问了不合理的位置（即之前未与内核达成合同），这就会出发段错误。找到VMA之后，内核会通过查找PTE内从及VMA的类型来解决这个缺页异常（page fault），此时PTE内容为空，之后内核便会分配一个页帧并将PTE指向分配的页帧。

Page Cache

操作系统在操作文件时有两个问题需要解决：

• 相对于内存来说，硬盘的读取速度非常慢
• 需要做到将文件加载至内存中 一次便可供多个进程共享

以上两个问题都可以通过page cache来解决，kernel用它来存储与页面大小相同的文件块。下面用一个render程序为例来描述一个文件的读取过程，render会打开scene.dat文件，每次读取512 byte的内容并将其存入堆内存中，读取流程如下：

读取挖12KB后，render的堆内存及相关页帧如下：

事实上，尽管只调用了read函数，此时也会有三个page cache的页帧中存储了部分scene.dat的部分数据，因为所有的常规文件操作都是通过page cache来进行的，在x86平台上，所有文件在内核看来都是一系列4KB大小的块。即使你只是读取1byte数据，它所在的4KB大小的块都会被复制到page cache中。

不幸的是，为了是用户态程序读取文件内容，内核还需要将page cache中的东西复制到用户内存中，这不但会消耗cpu，同时也会浪费物理内存。如上图所示，scene.dat的内容在内存中存储了两份，而且每个实例都会保存一份。至此，这种读取方式虽然解决磁盘延迟的问题，但会带来较多额外的问题，但使用memory-mapped files却可以解决这些问题，即通过内核将进程的虚拟页面直接映射至page cache中，这样能有效提高文件读写效率，同时也能节省部分物理内存，如下所示：

在使用了page cache的读写时，当进程调用write()时，数据只是被写入到page cache中，对应的页进入dirty状态，磁盘IO不会立刻发生，如果此时主机死机，数据就会丢失，因此重要的数据在写入时必须调用fsync（仍需要注意磁盘驱动缓存）。另一方面，读取操作会阻塞住，直至数据准备好，内核会通过eager loading（积极加载）来加速读取，即预读取部分数据至page cache中。最后，你可以通过O_DIRECT来绕过page cache。

一个文件映射可以是私有的，也可能是共享的，这种区别只有在更改内存中的内容时才能体现出来：私有映射时进程对内存的修改不会提交至磁盘中或者被其他进程所见，而共享映射却可以。内核通过页表项，使用copy on write来实现私有映射。如下示例中，render和render3d同时创建了scene.dat的私有映射，render修改了映射至内存中的文件：

Reference

• Anatomy of a Program in Memory
• How The Kernel Manages Your Memory
• Page Cache, the Affair Between Memory and Files