Posted on

Minix

Linux内核在最早发现的时候并没有实现自己的文件系统，而是直接引入了Minix中的文件系统，它的主要结构如下：

  • 一个boot sector位于磁盘的第一个扇区内，里面存储的是Minix系统的启动信息和分区表
  • 每个分区的第一个block中存储的是superblock，里面记录了磁盘上其他分区的结构和对应物理磁盘上的位置
  • inode bitmap：里面记录了inode的使用情况
  • inode信息：一个inode对应一个文件，inode中记录了文件的元数据
  • zone bitmap：记录磁盘块的使用情况
  • data zone：实际存储文件数据的地方
    其中，inode存储的是文件的元数据，包括文件大小、文件所属、修改时间等，但是inode中并没有存储文件名。inode中同时存储了文件所占用的block位置，在Minix和EXT1~3文件系统里，inode中是包含9个直接指针、7个1级指针、2个2级指针用以指向对应的data block

EXT

最初的EXT文件系统是为了克服Minix文件系统的大小限制而开发的，它是基于Unix文件系统而来，但是目前能获取的关于EXT文件系统的信息较少，因为它也存在较多问题并 很快被EXT2文件系统所替代

EXT2

EXT2的元数据结构跟EXT是一样的，但是它更具前瞻性，因为它预留了较多空间供元数据使用。和Minix一样，EXT的第一个扇区也是boot sector。一个EXT2上的空间会被切分成多个块组进行管理（一个块组通常是8MB，块组也叫柱面组，基于柱面做分组能有效降低旋转时间），如下所示为一个块组的基本结构，其中数据分配的基本单元为块，一个块的大小通常为4K：

一个块组的第一个块为superblock，其中存储的都是整个文件系统的元数据，如果元数据损坏，可以通过dd将备份超级快复制过来进行修复。通常这部分元数据都会备份存储在多个块组上用以提高系统可用性。ext4的驱动在工作时都是查询和修改第一个块组内存储的元数据，dumpe2fs可以查看superblock中的元数据：

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
# dumpe2fs /dev/sda1
Filesystem volume name:   boot 
Last mounted on:          /boot 
Filesystem UUID:          79fc5ed8-5bbc-4dfe-8359-b7b36be6eed3 
Filesystem magic number:  0xEF53 
Filesystem revision #:    1 (dynamic) 
Filesystem features:      has_journal ext_attr resize_inode dir_index filetype needs_recovery extent 64bit flex_bg sparse_super large_file huge_file dir nlink extra_isize 
Filesystem flags:         signed_directory_hash 
Default mount options:    user_xattr acl 
Filesystem state:         clean 
Errors behavior:          Continue 
Filesystem OS type:       Linux 
Inode count:              122160 
Block count:              488192 
Reserved block count:     24409 
Free blocks:              376512 
Free inodes:              121690 
First block:              0 
Block size:               4096 
Fragment size:            4096 
Group descriptor size:    64 
Reserved GDT blocks:      238 
Blocks per group:         32768 
Fragments per group:      32768 
Inodes per group:         8144 
Inode blocks per group:   509 
Flex block group size:    16 
Filesystem created:       Tue Feb  7 09:33:34 2017 
Last mount time:          Sat Apr 29 21:42:01 2017 
Last write time:          Sat Apr 29 21:42:01 2017 
Mount count:              25 
Maximum mount count:      -1 
Last checked:             Tue Feb  7 09:33:34 2017 
Check interval:           0 (<none>) 
Lifetime writes:          594 MB 
Reserved blocks uid:      0 (user root) 
Reserved blocks gid:      0 (group root) 
First inode:              11 
Inode size:               256 
Required extra isize:     32 
Desired extra isize:      32 
Journal inode:            8 
Default directory hash:   half_md4 
Directory Hash Seed:      c780bac9-d4bf-4f35-b695-0fe35e8d2d60 
Journal backup:           inode blocks 
Journal features:         journal_64bit 
Journal size:             32M 
Journal length:           8192 
Journal sequence:         0x00000213 
Journal start:            0 


Group 0: (Blocks 0-32767) 
 Primary superblock at 0, Group descriptors at 1-1 
 Reserved GDT blocks at 2-239 
 Block bitmap at 240 (+240) 
 Inode bitmap at 255 (+255) 
 Inode table at 270-778 (+270) 
 24839 free blocks, 7676 free inodes, 16 directories 
 Free blocks: 7929-32767 
 Free inodes: 440, 470-8144 
Group 1: (Blocks 32768-65535) 
 Backup superblock at 32768, Group descriptors at 32769-32769 
 Reserved GDT blocks at 32770-33007 
 Block bitmap at 241 (bg #0 + 241) 
 Inode bitmap at 256 (bg #0 + 256)
 Inode table at 779-1287 (bg #0 + 779) 
 8668 free blocks, 8142 free inodes, 2 directories 
 Free blocks: 33008-33283, 33332-33791, 33974-33975, 34023-34092, 34094-34104, 34526-34687, 34706-34723, 34817-35374, 35421-35844, 35935-36355, 36357-36863, 38912-39935, 39940-40570, 42620-42623, 42655, 42674-42687, 42721-42751, 42798-42815, 42847, 42875-42879, 42918-42943, 42975, 43000-43007, 43519, 43559-44031, 44042-44543, 44545-45055, 45116-45567, 45601-45631, 45658-45663, 45689-45695, 45736-45759, 45802-45823, 45857-45887, 45919, 45950-45951, 45972-45983, 46014-46015, 46057-46079, 46112-46591, 46921-47103, 49152-49395, 50027-50355, 52237-52255, 52285-52287, 52323-52351, 52383, 52450-52479, 52518-52543, 52584-52607, 52652-52671, 52734-52735, 52743-53247 
 Free inodes: 8147-16288 
Group 2: (Blocks 65536-98303) 
 Block bitmap at 242 (bg #0 + 242) 
 Inode bitmap at 257 (bg #0 + 257) 
 Inode table at 1288-1796 (bg #0 + 1288) 
 6326 free blocks, 8144 free inodes, 0 directories 
 Free blocks: 67042-67583, 72201-72994, 80185-80349, 81191-81919, 90112-94207 
 Free inodes: 16289-24432 
Group 3: (Blocks 98304-131071)

<snip>

此外每个块组可能会有一小段的预留空间用来存组描述符（GDT），每个块组有自己的inode和block位图用以管理自身的inode和block，所以一个EXT2的磁盘结构如下所示：

EXT2的最大问题就是在发生奔溃后需要花费较长时间才能恢复，因为fsck需要花费很长时间修复文件系统中的不一致问题。

EXT3

ETX3最终要的修改就是引入了日志来解决ETX2恢复时间较长的问题，日志里记录了文件系统上最近的修改。此时，数据不是直接写入磁盘数据区，而是先写入日志中，当数据正在持久化后，就可以回收日志。当文件系统奔溃后，通过回放日志就可以恢复文件系统，避免数据丢失。显而易见的是，引入日志虽然提高了数据的可靠性，但是会带来性能的下降，所以EXT3也提供了选项供用户在数据可靠性和性能之间做平衡。

EXT4

EXT4主要是提升了文件系统整体的性能、可靠性及容量。为了提高可靠性，加入了元数据和日志的校验。此外，ext4在提升文件的连续性上也做了非常多的工作，如extent的引入、更加合理的block、inode分配策略等。数据分配的基本单元由block变为extent了，一个extent是磁盘上的一段连续空间，extent的引入使得一个inode能使用更少的数据指针描述一个物理上连续的大文件，在有效提升单个文件的最大尺寸的同时有效减少文件元数据的大小。
此外，EXT4也引入了一些其他分配策略来提升文件的连续性，降低文件内部的碎片，主要如下：

  • 将新创建的文件分散到磁盘上来减少磁盘碎片，而不是将文件都集中在磁盘开头部分
  • 文件分配算法会尽量将文件随机分布到块组上，同时尽量保持同一文件的extent处以同一块组，extents间尽可能靠近，从而缩短寻道和旋转时间
  • 采用预分配策略来创建新文件，同时新文件不会紧跟现有文件，防止现有文件的碎片较多
    需要注意的是，文件内部碎片的这么优化可能会导致整体磁盘空间碎片的增加，这也需要做一个权衡。

下面来详细看看EXT4的主要结构。

Super Block

SuperBlock中记录了整个文件系统的元数据，如block数目、inode数目、block group的情况等，superblock如果彻底损坏会导致整个文件系统不可用，在初始化的时候我们可以指定是否需要将superblock备份到每个block group上。

Block Group Descriptor

每个block group都有一个描述符与之对应，一般情况下每个block group内都会存储GDT的备份，但是在初始化的时候也可以指定是否需要将superblock和GDT备份到全部block group上，如果一个block group不含有这部分元数据，则该group一般就是从bitmap开始存储。一个block group descriptor记录该group中bitmap和inode table的位置信息，需要注意的是，一个group内位置固定的只有它的元数据（superblock和GDT），bitmap和inode的位置都部署固定的，这样便于将多个block group和成一个logic block group使用。

Block and inode Bitmaps

block bitmap记录了group内block的使用情况，inode记录了group内inode的使用情况。

Inode Table

Inode table会占用多个block来存储inode实例，每个inode实例对应系统上的一个文件。每个inode的id是全局唯一的，从1开始分配，同时每个group内inode的数目都是固定的（sb->s_inodes_per_group），所以通过(inode_num-1/ sb->s_inodes_per_group)就知道 一个inode位于哪个group之内。

Inode

如前文所述，一个inode对应于一个文件，每个inode都有个局部唯一性ID，用以存储该文件的元数据以及数据块指针，它的结构如下所示：

通常情况下，文件的碎片率不会不会很高，所以通常以及直接指针就够用了。在ext4中，inode的size是可以在初始化的时候指定的，我们可以利用更大的inode size来存储部分额外的用户元数据，这样能有效提升用户元数据的存储效率。

需要特别注意的是，一个inode是不包含文件名的，文件的访问需要通过directory entry来进行，下面来看目录项的具体内容。

Directory Entries

在ext4中，一个目录也是作为一个文件来管理，它的文件内容就是该目录下文件和其inode的对应关系，所以我们在访问一个文件时，都要先通过该文件所在目录的directory entry来获取到该文件的inode，这样才能访问该文件。。

通常情况下，一个目录项是以一种线性的方式来list它的所有entry的，当一个目录下存储的文件数过多的话，对应的directory entry就会非常大，这也是为什么ls一个大目录的时候需要很久才能返回结果。基于此考虑，ext3还引入hash tree的结构来存储一个目录的所有entry，如果EXT4_INDEX_FL这个flag在inode中设置了的话，对应的目录就是用这种hash tree的结构来组织和查找它的entries。

Journal

journal是在ext3引入的，用以提升文件系统的可靠性，防止系统奔溃导致文件系统的损坏。在修改系统内的重要数据之前，会先写入日志，待写入的数据持久化存储后，可以将对应的记录从日志中删除，当系统发生奔溃时，通过重放日志即可恢复数据。基于性能方面的考虑，默认情况下，ext4只有在修改元数据的时候才会写入日志，用户数据的修改是不会写入日志的，这个行为在挂载时也可以修改。如果默认的保护级别(data=ordered)不足，通过data=journal可以使所有数据在修改时都要写入日志中，这种方式虽然更安全，但是性能也会下降。

Reference

Posted on

本文从共识问题开始讲起，一步步演化出basic paxos，然后分析部分基于paxos的共识算法，包括multi-paxos、raft

共识问题

所谓共识问题就是要在多个参与者之间确定一个不可变变量的值，所谓不可变变量就是这个值一旦确定之后就不可再变了。看到这里，大部分人的疑惑就是，我要做的是一个分布式存储系统或者是数据库，你给我确定一个值有什么用呢？其实这里的不可变变量只是实际应用场景的一个抽象，在日常中通常是要配合状态机进行使用的，所谓状态机就是对于一系列相同的输入，它的最终输出结果总是一样的。所以我们可以用这个不可变变量作为多个状态机的输入，来确保所有状态机下的输出结果是一致的。例如对于一个存储系统来说，这个不可变变量可以是一条日志记录，一条日志记录确定以后，它是永远不会再变的，之后通过在多个数据副本上应用这条日志记录就可以确保副本之间保持一致。

basic paxos演进

通常我们说的paxos算法是指basic paxos，它是共识领域里最经典的算法，本文不讲它的证明，而是从实际应用角度来看它是如何一步步演进而来的。
首先，paxos要解决的是如何设计有一个系统来确定一个不可变变量的值（var），同时它应满足如下特性：

  • 系统需要满足正确性，一旦某个提案被选定后，var的值就不可再变了
  • 系统需要具有容错性

在paxos算法中，主要有两类角色，分别是proposer和acceptor，其中proposer负责生成提案，acceptor负责对提案进行投票，两类角色是可以重合的。为了演进出最终的解决方案，我们可以先将问题简化，先生存简单方案，一步步改进直至演化成最终的方案。

方案1

首先假设系统中只有一个acceptor和多个proposer，在这种情况下，最有效的方式就是加锁，即proposer在生成提案之前，首先需要向acceptor取申请锁，谁先获得锁就获得提案权，所以最终只有一个proposer会获得提案权，这样就可以确保系统的正确性，因为acceptor只会收到一个提案，这个提案会最终被选定。此时方案一就类似一个两阶段提交协议，它的整体流程如下：

  • proposer向acceptor申请锁，acceptor若还未发放锁，则将锁发放给请求锁的proposer
  • proposer获取到锁之后便可发起提案，acceptor则会通过该提案

但是这种方式又一个问题就是容错性很低，acceptor异常退出或者抢到锁的proposer在发出提案之前异常退出都会导致这个系统的不可用，下面来看改进方案2。

方案2

方案1中假设一个acceptor在抢到锁后还没来得及发出提案就异常退出了，此时整个系统就不可用了，为了解决这个问题，这里的锁可以变为抢占式的锁，即acceptor可以向多个proposer发放锁，只有最新的锁才是有效的。所以此时需要给每个锁赋予一个唯一性id来标记锁的新旧程度，这就是paxos中proposal number的意义，proposal number越大，锁就越新。这样当一个proposer异常退出之后，其他的proposer仍旧可以获得提案权。当一个proposer获得锁之后就可以发送提案给acceptor，如果此时没有发放更新的锁，那么该提案就可以被选定，如果已经发放了更新的锁，该提案就会被拒绝。该方案的整体流程如下：

  • proposer向acceptor申请锁，acceptor若还未选定提案，则总是发放锁该proposer，同时记录下当前最新的锁序号
  • proposer获取到锁后，需要生成提案发送给acceptor，同时提案总要带上自身的锁序号
  • acceptor收到提案之后，若该提案对应的锁是最新的，则选定该提案，否则拒绝

方案3

上述方案还有一个明显问题就是acceptor挂掉后整个系统就不可用了，所以在这个方案基础之上我们需要引入多个acceptor，此时仍旧采用可抢占式锁方案，这也是basic paxos的基本流程：

  • proposer在提案之前需要先从acceptor处申请锁，只有获取到半数有以上acceptor发放的锁后才能发起提案
  • 在接收到获取锁的请求后，如果acceptor还未同意提案，则将锁发放给proposer，同时记录下自身当前最新的锁，若已经同意提案，咋需要将提案及对应的锁编号返回给proposer
  • 在获取到半数以上aceptor发放的锁之后，proposer才可以发起提案。若有acceptor已经同意了提案，则acceptor需要从中选出编号最大的提案作为自身的提案发送给acceptor，否则的话可以生成新的提案
  • 一个acceptor收到提案之后，若该提案对应的锁对于自身来说值最新的，则同意该提案
  • 一个提案被半数以上acceptor同意后就表示该提案已经被选定了

上面就是basic paxos的整体流程，大部分描述中，proposal number即是对应上文的锁编号，大部分资料描述中都是proposer自己生成proposal number，proposer需要带上proposal number去请求acceptor，这种描述的整体流程和效果也是一样的。另外proposer采用当前最大编号的提案作为自身提案的原因如下：

  • 为了确保paxos的正确性，即提案被选定后就不能修改了，因为一个提案被选定后一定会被某些acceptor返回给proposer，proposer采用该提案作为自身的提案值就可确保最终的提案值不会被修改了

以上就是basic paxos的基本流程，在实际使用过程中通常proposer和acceptor两种角色都是会重合的，同时也可能会增加learner的角色来学习提案，用它来分担读请求压力。另外上述basic paxos在实际使用过程中可能存在一个活性的问题(liveness)，即有可能无法选出最终提案或花费较长时间才选出，因为锁是抢占式的，所以可能存在一个proposer还来不及生成提案锁又被抢走了，循环反复下系统一直处以抢锁状态而无法生成提案，所以在实际过程中一般会先选定一个proposer leader,只有该leader拥有提案权，这样可能有效解决这个问题，同时降低网络流量。

multi-paxos

前文说到，basic paxos是用来确定一个变量，而multi-paxos则是就一批提案达成一致，这也是日常应用中使用的paxos。最简单粗暴的方法就是对于每个提案都运行basic paxos的完整流程，先抢锁然后再生成提案，这样显然效率不是很高。所以日常使用的multi-paxos在basic paxos基础上做了如下优化：

  • 选取一个proposer leader，只有该leader具有生产提案的权利，通过basic paxos的抢锁流程即可选出leader
  • leader是有任期的，leader需要跟系统中的其他角色保持心跳联系来维持自身的任期
  • 在一个leader的任期内，它可以直接跳过抢锁阶段，直接生成提案，这样能减少网络交互，提高效率

实际应用

raft

基本问题

原始的paxos较难理解同时更多的是停留在理论证明层面，而raft就是以paxos为基础，提出的更加具体、更易懂、更加工程化的一种共识算法。它将paxos拆分成以下三个子问题：

  • 选主
  • 日志复制
  • 安全性

选主

raft限制一个时刻只有一个节点可以发起提案，这样能极大简化算法的实现，这个节点就是leader节点。因为raft需要解决的第一个问题就是：

  • 如何保证一个时刻最多只有一个leader节点
  • 在一个leader节点异常后如何尽快选出新的leader

在raft协议中，存在三种角色，分别是leader,follower,candidate，状态转换图如下所示：

整体流程如下：

  • 所有节点以follower角色启动
  • leader周期性发送心跳给所有follower
  • 在超时时间内未收到心跳包的follower会变为candidate，将自身term增加1，然后发起选主
  • 选举结束：
    • 若收到大多数节点的投票，则该candidate变成leader，并向其他节点发送一个空的AppendEntry请求
    • 若收到相同或更大term的AppendEntry请求，则承认对方为leader，自身变成follower
    • 若超时则重新选主

这里的term及对应paxos中的proposal number，一个term最多只有一个leader与之对应。其中follower节点对于选主的投票规则是对方的日志比自身新，确保最后选出的leader拥有最新最全的日志，从容简化之后的恢复流程，这部分会在第三个子问题中详细阐述。

日志复制

日志复制是为了保证节点的一致性，所有的日志都是先提交到leader节点，再由leader节点follower节点，正常情况下follower节点跟leader节点是一致的，但是在发生节点加入或者leader重新选举之后，follower节点可能落后较多，日志复制需要保证节点的一致性。

raft为了算法实现，要确保日志是连续的，即节点的日志序列不能存在空洞，它的日志复制示意图如下所示：

整体流程如下：

  • leader接收client的请求，先将日志写入本地，之后向所有follower发送AppendEntry请求
  • follower对收到的Entry验证，若该entry对应的前一个位置上，follower对应的日志和leader对应的日志term是相同的，则写入该Entry并返回成功
  • 若对应的term不相等或者是folloer的日志落后，则拒绝该请求，同时回复自身的日之前情况，leader接收到后会发送缺失部分的日志
  • leader在收到半数节点的成功应答后，则认为该日志已经被选定（commit），可以回复成功给客户端
  • 后续的AppendEntry和HeartBeat请求中都会带上leader的commit信息，follower便可以更新自身的commit信息

利用日志连续这个特性可以大大简化raft的整体恢复、选主、应用流程，通过以上日志复制机制可以确保如果两个节点相同位置上的日志项的term是相等的，那么该条日志就一定是相等的（因为一个term只会有一个leader），而该日志是相等的，则可以确认前面所有的日志都是相等的（在AppendEntry前会先比较前一条日志是否相等）。

部分疑问

提交日志回复

最初看论文时，我产生过这样的疑问，就是一个client在想leader节点提交日志之后，该leader节点挂掉了，那么client节点最后会收到什么回复呢？如果回复是超时的话，那么客户端是否需要重试后者怎样才能获取到提交结果呢？如果回复是失败的话，如果该leader节点之后又恢复了，那么此条日志也是有可能会commit的，这样显然也不不行的。
其实这个问题根分布式系统的原则有关，如果server端返回的timeout，那么结果就是不确定的，系统设计者对使用者的期望就是retry，同时系统设计者或者使用者需要确保这种retry操作是幂等的。其次，对于raft来说，如果一个日志在提交时失败了，那么只能给你返回timeout。这是因为，即使只有少数派node接受了这条日志，这条日志还是有可能被后续的选举出来的leader分发给其他的node，从而变成多数派，然后提交。当然也有可能不包含这条日志的node被选为leader，导致这条日志被truncate掉，从而从系统中消失掉。综合以上两种情况，只能给你返回timeout来代表undefined。
最后，raft返回给你成功就是达成了多数派；返回给你失败时就是拒绝你提交，但是这种失败一般不代表日志commit失败，而是因为当前node不是leader或者当前node只读等原因拒绝你；如果返给你timeout，那么结果就是undefined，需要你去查询leader或者干脆重试，而重试的话要求你的操作在你的应用中是幂等的

工程优化

  • 预选举：candidate每次在发起选举的时候都会提升自己的term，如果某些candidate因为日志原因肯定无法成为leader，但是它却不断参与选举导致系统的term增加，使真正能当选的candidate要花费一段时间将自身的term跟上之后才能选出leader，容易导致选举周期过长。所以在实际实现过程中，可以增加pre-vote阶段，先发去预投票而不增加自身的term，只有确认可以当选为leader后才会增加自身的term
  • 乱序提交：raft为了简单性，采用了高度串行化设计，在实际使用中可能会存在性能问题，因此PolarFS因为实现了ParallelRaft，即raft的乱序提交版本。简单来说，就是对于无冲突的log之间可以乱序提交，而由冲突的log之间则需要顺序提交，然后在选主阶段引入额外的流程来填补leader中的log空洞，具体可参考PolarFS

一致性达成

在讨论分布式系统的时候，很容易混淆共识算法和一致性这两个概念，或者混为一谈，认为paxos和raft是一种强一致性算法，这其实是错误的。raft和paxos只是一种共识算法，共识达成之后如何达到所要求的一致性（线性一致、最终一致等），仍需要其他的实现手段，具体可参考线性一致性和 Raft

安全性

所谓安全性就是在前两个问题的基础之上如何确保日志不会丢失，以下是它的具体方案：

  • 为了简化数据同步和恢复流程，raft中的日志总是从leader流向follower节点的，所以选出来的leader一定要确人是拥有最多以选定日志的节点，这样才不会造成日志的丢失。因此follower向candidate的投票原则是：candidate的最后一条日志的term比follower大，或者在term一样大的情况下，candidate的日志更长，这样就可以确保最终选择的leader包含了大多数节点的日志
  • 此外论文中还描述了一种情况是一条日志被commit之后又被否定了，其核心原因是根据多数派判断当前日志是否可以commit只适用于当前term，所以一个leader在当选之后会提交一个空的AppendEntry，通过日志的连续性来确保提交该日志的同时也提交之前任期的日志

与paxos的对比

这里说的paxos是指multi-paxos，raft比paxos更容易理解和实现，可以视为paxos的加强限制版，它也paxos的主要区别是：

  • raft强化了leader的地位，leader一定是拥有最全的日志，日志只会从leader流向follower
  • raft节点中日志是连续的，日志之间是不会存在空洞的

multi-paxos中可以不存在leader，这样的话就退化成了经典的basic paxos实现，raft正是通过这两个限制来简化paxos的工程实现。而paxos和raft都是一旦一个entry（raft叫日志，paxos叫提案）被多数派同意，该提案计算被选定了，被选定的提案就不会丢失也不会更改。事实上，paxos和raft都是用一个唯一性id来标识leader的合法性（proposal-number和term），id最大的leader才是有效的leader，对于paxos和raft来说，同一时刻是可能存在两个leader的，但只有一个是合法的，即同一个term期间只会有一个leader。

此外，raft中强调了leader拥有最新的日志，而multi-paxos没有强调这点，所以在paxos中一个节点当选为leader之后需要额外的流程从其它acceptor处来补全自身的日志，而raft的恢复流程则简单得多，日志只会从leader流向follower。此外需要注意的是，leader此时恢复的日志可能还不是已经选定的日志，所以paxos和raft中，leader节点在当选之后都需要重新走一遍流程来提交自身的日志。

raft还有一个很重要的点就是日志的连续性保证，所谓连续性就是说不同节点上相同位置的日志只要他们的term是相同的，这两条日志就一定是相同的，且它们之前的日志也都是相同的，这是通过前文所述的日志复制策略来保证的。这样leader只需对比下follower的日志id和term就知道该节点的日志情况，这样能极大简化日志恢复、选主过程。

从根本上来说，raft更加易懂、易实现，而paxos侧重于理论描述，两种协议之间不存在绝对的优劣。但是只要有leader角色的存在，选主就一定需要花费一点时间，而paxos中没有强调leader的存在，所以对于极端可用性要求的场景，可以选用paxos。存在此外有资料说raft要求日志是连续的这点会导致系统在网络环境较差的环境里性能较差，个人认为不是这样的，除非是这个环境里慢节点是会不断变化的，才会带来raft性能的明显下降。但是这里也跟具体的日志存储实现有关，当有大量并发写请求执行时，要求所有的日志写入是按顺序写入，那么处于尾部的请求，必须等待之前所有的请求都被处理后才能被提交和返回，这个对性能也是会有影响的。此外，在并发较大的场景下，日志请求的到达可能是乱序的，这对于写入也会造成一定影响。

Reference

Posted on

简介

Monitor是Ceph集群中的元数据管理组件，负责整个集群的元信息的维护，这里的元信息主要是几张抽象的map，包括osdmap、pgmap、monmap、mdsmap等。在Ceph集群中，OSD的设计原型为INTELLIGENT STORAGE DEVICES，通过这种智能的OSD可以减少Monitor作为中心节点的负担。在实际运行过程中，真正需要Monitor介入的主要是以下几种场景：

  • Client在首次访问时需要从Monitor处获取集群crush map信息
  • OSD节点会向Monitor节点汇报故障OSD的信息，Monitor需要修改对应map
  • OSD在加入集群时，会向Monitor发送信息，Monitor需要修改对应map

整体来说，Monitor是基于改进的Paxos算法，对外提供一致的元信息访问及更新服务。

PAXOS

Monitor的整体架构如上图所示，整体分为4层，分别是DB层、Paxos层、PaxosService层及应用层。DB层用于提供单机KV存储服务，而PaxosService将应用层的不同元信息操作层封装成KV操作下发至Paxos层，Paxos层对上层提供一致性的KV存储服务，上层的不同PaxosService都共用一个Paxos实例。下面来看Paxos层是如何基于改进的Paxos算法来对外提供服务的。

Monitor中主要有两个角色，分别是leader及peon，其中只有leader能发提案，即leader对应于paxos中的proposer，peon及leader都是作为paxos中的acceptor存在，只要Monitor集群中半数以上
的节点存活，Monitor就能正常对外提供服务。下面先不看leader选举及异常恢复机制，
下面通过源码来看一个正常运行Monitor集群中paxos层是如何工作的。

一个paxos实例存在如下可能的状态：

  • recovering：恢复状态，用于选主后各个实例之间的数据同步
  • active：空闲状态，可以进入新的paxos流程
  • updating：处于提案commit阶段
  • updating-previous：恢复数据期间，实例处于提案commit阶段
  • writing：提案正在写入
  • writing-previous：恢复数据期间，实例正在写入提案
  • refresh：等待刷新状态，获取lease后就可进入active状态
  • shutdown：异常状态

一个Paxos实例的正常运行过程主要涉及到如下数据：

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
private:
  //当前实例上保存的最低版本已commit记录
  version_t first_committed;
  
  //上次提案的proposal number，一个leader在任期间pn是不会变的
  version_t last_pn;
  
  //当前实例上保存的最高版本已commit记录
  version_t last_committed;
  
  //已accept的最新proposal number
  version_t accepted_pn;

   //paxos会将提案的值以Transaction的方式记录在pendping_proposal中，一个Transaction
   记录了一系列此次提案对应的操作。从这种形式也能看出来，paxos层一次只能对一个提案进行决议。
  /**
   * Pending proposal transaction
   *
   * This is the transaction that is under construction and pending
   * proposal.  We will add operations to it until we decide it is
   * time to start a paxos round.
   */
  MonitorDBStore::TransactionRef pending_proposal;

  //pending_finishers中暂时存放提案被accept后的回调函数
  /**
   * Finishers for pending transaction
   *
   * These are waiting for updates in the pending proposal/transaction
   * to be committed.
   */
  list<Context*> pending_finishers;

  //paxos流程开始后，committing_finishers中存放的是提案被选定后的回调函数
  /**
   * Finishers for committing transaction
   *
   * When the pending_proposal is submitted, pending_finishers move to
   * this list.  When it commits, these finishers are notified.
   */
  list<Context*> committing_finishers;

Paxos的提案入口是在trigger_propose，如下：

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
  bool Paxos::trigger_propose()
{
  if (plugged) {
    dout(10) << __func__ << " plugged, not proposing now" << dendl;
    return false;
  } else if (is_active()) {
    dout(10) << __func__ << " active, proposing now" << dendl;
    propose_pending();
    return true;
  } else {
    dout(10) << __func__ << " not active, will propose later" << dendl;
    return false;
  }
}

void Paxos::propose_pending()
{
  assert(is_active());
  assert(pending_proposal);

  cancel_events();

  bufferlist bl;
  pending_proposal->encode(bl);

  dout(10) << __func__ << " " << (last_committed + 1)
	   << " " << bl.length() << " bytes" << dendl;
  dout(30) << __func__ << " transaction dump:\n";
  JSONFormatter f(true);
  pending_proposal->dump(&f);
  f.flush(*_dout);
  *_dout << dendl;

  pending_proposal.reset();

  committing_finishers.swap(pending_finishers);
  state = STATE_UPDATING;
  begin(bl);
}

从以上源码也可以看出来，一个提案首先是被持久存储在DB中的，这样可以保证提案被被提出后，即使paxos实例异常退出，提案数据也不会丢失。当一个paxos流程开始后，对应的提案会被从DB中取出，并开始决议过程。

begin(leader)

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// leader
void Paxos::begin(bufferlist& v)
{
  dout(10) << "begin for " << last_committed+1 << " " 
	   << v.length() << " bytes"
	   << dendl;

  //只有leader才能发起提案，并且一次只能由一个提案被决议	   
  assert(mon->is_leader());
  assert(is_updating() || is_updating_previous());

  // we must already have a majority for this to work.
  assert(mon->get_quorum().size() == 1 ||
	 num_last > (unsigned)mon->monmap->size()/2);
  
  // and no value, yet.
  assert(new_value.length() == 0);

  // accept it ourselves
  accepted.clear();
  //accepted列表中插入自身的rank值，因为自己的提案自己是不会拒绝的
  accepted.insert(mon->rank);
  new_value = v;

  //本次提案为第一个提案
  if (last_committed == 0) {
    auto t(std::make_shared<MonitorDBStore::Transaction>());
    // initial base case; set first_committed too
    t->put(get_name(), "first_committed", 1);
    decode_append_transaction(t, new_value);

    bufferlist tx_bl;
    t->encode(tx_bl);

    new_value = tx_bl;
  }

  // store the proposed value in the store. IF it is accepted, we will then
  // have to decode it into a transaction and apply it.
  //将本次提案存入数据库中，其中key为本次提案版本号，value为提案的值，在提案被选定后，
  //Paxos会将提案读出并使其生效
  auto t(std::make_shared<MonitorDBStore::Transaction>());
  t->put(get_name(), last_committed+1, new_value);

  // note which pn this pending value is for.
  //更新当前决议过程中的提案的信息
  t->put(get_name(), "pending_v", last_committed + 1);
  t->put(get_name(), "pending_pn", accepted_pn);

  dout(30) << __func__ << " transaction dump:\n";
  JSONFormatter f(true);
  t->dump(&f);
  f.flush(*_dout);
  auto debug_tx(std::make_shared<MonitorDBStore::Transaction>());
  bufferlist::iterator new_value_it = new_value.begin();
  debug_tx->decode(new_value_it);
  debug_tx->dump(&f);
  *_dout << "\nbl dump:\n";
  f.flush(*_dout);
  *_dout << dendl;

  logger->inc(l_paxos_begin);
  logger->inc(l_paxos_begin_keys, t->get_keys());
  logger->inc(l_paxos_begin_bytes, t->get_bytes());
  utime_t start = ceph_clock_now();

  //将提案持久化存储在DB中
  get_store()->apply_transaction(t);

  utime_t end = ceph_clock_now();
  logger->tinc(l_paxos_begin_latency, end - start);

  assert(g_conf->paxos_kill_at != 3);

  if (mon->get_quorum().size() == 1) {
    // we're alone, take it easy
    //如果当前quorum中只有一个monitor实例，则提案直接被选定，开始将提案进行commit
    commit_start();
    return;
  }

  // ask others to accept it too!
  //将天发送至quorum中的所有其他成员（peon），
  for (set<int>::const_iterator p = mon->get_quorum().begin();
       p != mon->get_quorum().end();
       ++p) {
    if (*p == mon->rank) continue; //该成员为实例本身
    
    dout(10) << " sending begin to mon." << *p << dendl;
    MMonPaxos *begin = new MMonPaxos(mon->get_epoch(), MMonPaxos::OP_BEGIN,
				     ceph_clock_now());
    begin->values[last_committed+1] = new_value;
    begin->last_committed = last_committed;
    begin->pn = accepted_pn;
    //将last_committed及accepted_pn一并发送给peon，供peon判断是否接受本次提案
    //一个leader在任期间内pn都是不会变的
    mon->messenger->send_message(begin, mon->monmap->get_inst(*p));
  }

  // set timeout event
  //设置提案超时的回调
  accept_timeout_event = mon->timer.add_event_after(
    g_conf->mon_accept_timeout_factor * g_conf->mon_lease,
    new C_MonContext(mon, [this](int r) {
	if (r == -ECANCELED)
	  return;
	accept_timeout();
      }));
}

handle_begin(peon)

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
// peon，处理leader发送过来的begin消息
void Paxos::handle_begin(MonOpRequestRef op)
{
  op->mark_paxos_event("handle_begin");
  MMonPaxos *begin = static_cast<MMonPaxos*>(op->get_req());
  dout(10) << "handle_begin " << *begin << dendl;

  // can we accept this?
  //如果已经acceptle版本更高的提案，则拒绝此提案，因为一个leader在任期间，pn是不会变的
  //发送此情况多半是leader已经发生了切换
  if (begin->pn < accepted_pn) {
    dout(10) << " we accepted a higher pn " << accepted_pn << ", ignoring" << dendl;
    op->mark_paxos_event("have higher pn, ignore");
    return;
  }
  assert(begin->pn == accepted_pn);
  assert(begin->last_committed == last_committed);
  
  assert(g_conf->paxos_kill_at != 4);

  logger->inc(l_paxos_begin);

  // set state.
  //设置该paxos实例的状态，进入提案决议流程
  state = STATE_UPDATING;
  lease_expire = utime_t();  // cancel lease

  // 接受此次提案
  version_t v = last_committed+1;
  dout(10) << "accepting value for " << v << " pn " << accepted_pn << dendl;
  // store the accepted value onto our store. We will have to decode it and
  // apply its transaction once we receive permission to commit.
  auto t(std::make_shared<MonitorDBStore::Transaction>());
  t->put(get_name(), v, begin->values[v]);

  // note which pn this pending value is for.
  //更新此次提案的版本号、proposal number等
  t->put(get_name(), "pending_v", v);
  t->put(get_name(), "pending_pn", accepted_pn);

  dout(30) << __func__ << " transaction dump:\n";
  JSONFormatter f(true);
  t->dump(&f);
  f.flush(*_dout);
  *_dout << dendl;

  logger->inc(l_paxos_begin_bytes, t->get_bytes());
  utime_t start = ceph_clock_now();

  //在peon上存储此次提案的值
  get_store()->apply_transaction(t);

  utime_t end = ceph_clock_now();
  logger->tinc(l_paxos_begin_latency, end - start);

  assert(g_conf->paxos_kill_at != 5);

  // reply
  //将accept消息回复给leader
  MMonPaxos *accept = new MMonPaxos(mon->get_epoch(), MMonPaxos::OP_ACCEPT,
				    ceph_clock_now());
  accept->pn = accepted_pn;
  accept->last_committed = last_committed;
  begin->get_connection()->send_message(accept);
}

handle_accept(leader)

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
// leader，处理peon发送回来的accept消息
void Paxos::handle_accept(MonOpRequestRef op)
{
  op->mark_paxos_event("handle_accept");
  MMonPaxos *accept = static_cast<MMonPaxos*>(op->get_req());
  dout(10) << "handle_accept " << *accept << dendl;
  int from = accept->get_source().num();

  //此消息为前任leader期间的消息，忽略
  if (accept->pn != accepted_pn) {
    // we accepted a higher pn, from some other leader
    dout(10) << " we accepted a higher pn " << accepted_pn << ", ignoring" << dendl;
    op->mark_paxos_event("have higher pn, ignore");
    return;
  }
  //此消息为过时消息，忽略
  if (last_committed > 0 &&
      accept->last_committed < last_committed-1) {
    dout(10) << " this is from an old round, ignoring" << dendl;
    op->mark_paxos_event("old round, ignore");
    return;
  }

  // to do ??不明白
  assert(accept->last_committed == last_committed ||   // not committed
	 accept->last_committed == last_committed-1);  // committed

   //一次只能由一个提案处以决议中
  assert(is_updating() || is_updating_previous());
  assert(accepted.count(from) == 0);
  //from这个peon已经同意此提案
  accepted.insert(from);
  dout(10) << " now " << accepted << " have accepted" << dendl;

  assert(g_conf->paxos_kill_at != 6);

  // only commit (and expose committed state) when we get *all* quorum
  // members to accept.  otherwise, they may still be sharing the now
  // stale state.
  // FIXME: we can improve this with an additional lease revocation message
  // that doesn't block for the persist.
  //与标准paxos不同的是，Monitor总要quorum的所有成员全部accept一个提案，这个提案才算被选定，
  //这样能简化paoxs的实现，但是在mon节点发生故障时，paxos服务会短暂不可用，直至形成新的quorum
  //由于一次只有一个提案处于决议中，形成新的quorum过程也较快
  //如果提案被选定了，就开始进入commit阶段
  if (accepted == mon->get_quorum()) {
    // yay, commit!
    dout(10) << " got majority, committing, done with update" << dendl;
    op->mark_paxos_event("commit_start");
    commit_start();
  }
}

commit_start(leader)

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
//leader，开始提案commit流程
void Paxos::commit_start()
{
  dout(10) << __func__ << " " << (last_committed+1) << dendl;

  assert(g_conf->paxos_kill_at != 7);

  auto t(std::make_shared<MonitorDBStore::Transaction>());

  // commit locally
  //更新本地last_commited的值为最新提案的版本号
  t->put(get_name(), "last_committed", last_committed + 1);

  // decode the value and apply its transaction to the store.
  // this value can now be read from last_committed.
  decode_append_transaction(t, new_value);

  dout(30) << __func__ << " transaction dump:\n";
  JSONFormatter f(true);
  t->dump(&f);
  f.flush(*_dout);
  *_dout << dendl;

  logger->inc(l_paxos_commit);
  logger->inc(l_paxos_commit_keys, t->get_keys());
  logger->inc(l_paxos_commit_bytes, t->get_bytes());
  commit_start_stamp = ceph_clock_now();

  //将提案对应的事务在本地DB中生效
  //本地提交后,会调用C_Committed中的回调函数commit_finish
  get_store()->queue_transaction(t, new C_Committed(this));

  //更新leader状态为STATE_WRITING_PREVIOUS或者STATE_WRITING
  if (is_updating_previous())
    state = STATE_WRITING_PREVIOUS或者;
  else if (is_updating())
    state = STATE_WRITING;
  else
    ceph_abort();
  ++commits_started;

  if (mon->get_quorum().size() > 1) {
    // cancel timeout event
    mon->timer.cancel_event(accept_timeout_event);
    accept_timeout_event = 0;
  }
}

commit_finish(leader)

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
//leader，将commit操作下发至peon，刷写leader的状态
void Paxos::commit_finish()
{
  dout(20) << __func__ << " " << (last_committed+1) << dendl;
  utime_t end = ceph_clock_now();
  logger->tinc(l_paxos_commit_latency, end - commit_start_stamp);

  assert(g_conf->paxos_kill_at != 8);

  // cancel lease - it was for the old value.
  //  (this would only happen if message layer lost the 'begin', but
  //   leader still got a majority and committed with out us.)
  lease_expire = utime_t();  // cancel lease

  last_committed++;
  last_commit_time = ceph_clock_now();

  // refresh first_committed; this txn may have trimmed.
  first_committed = get_store()->get(get_name(), "first_committed");

  _sanity_check_store();

  // tell everyone
  //给quorum中的所有peon发送commit信息
  for (set<int>::const_iterator p = mon->get_quorum().begin();
       p != mon->get_quorum().end();
       ++p) {
    if (*p == mon->rank) continue;

    dout(10) << " sending commit to mon." << *p << dendl;
    MMonPaxos *commit = new MMonPaxos(mon->get_epoch(), MMonPaxos::OP_COMMIT,
				      ceph_clock_now());
    commit->values[last_committed] = new_value;
    commit->pn = accepted_pn;
    commit->last_committed = last_committed;

    mon->messenger->send_message(commit, mon->monmap->get_inst(*p));
  }

  assert(g_conf->paxos_kill_at != 9);

  // get ready for a new round.
  new_value.clear();

  // WRITING -> REFRESH
  // among other things, this lets do_refresh() -> mon->bootstrap() know
  // it doesn't need to flush the store queue
  //更新状态为STATE_REFRESH
  assert(is_writing() || is_writing_previous());
  state = STATE_REFRESH;
  assert(commits_started > 0);
  --commits_started;

  //其中，do_refresh是让上层服务刷新状态，获取最新的commit信息等
  if (do_refresh()) {
    commit_proposal();
    if (mon->get_quorum().size() > 1) {
      extend_lease();
    }

    finish_contexts(g_ceph_context, waiting_for_commit);

    assert(g_conf->paxos_kill_at != 10);

    finish_round();
  }
}

handle_commit(peon)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//peon，处理leader发送过来的commit消息
void Paxos::handle_commit(MonOpRequestRef op)
{
  op->mark_paxos_event("handle_commit");
  MMonPaxos *commit = static_cast<MMonPaxos*>(op->get_req());
  dout(10) << "handle_commit on " << commit->last_committed << dendl;

  logger->inc(l_paxos_commit);

  if (!mon->is_peon()) {
    dout(10) << "not a peon, dropping" << dendl;
    ceph_abort();
    return;
  }

  //to do?? 不知道啊
  op->mark_paxos_event("store_state");
  store_state(commit);

  if (do_refresh()) {
  	//唤醒等待中的回调函数
    finish_contexts(g_ceph_context, waiting_for_commit);
  }
}

至此，一轮提案决议过程就算完成了，monitor会发送ack信息给客户端,各个paxos实例便算完成了数据恢复和同步，leader的状态转换图如下所示：

对应的转换操作如下:

  • active-updating：接收到提案请求，将提案持久化存储，进入提案状态
  • updating-writing：quorum的全部成员都同意此提案，开始提交提案
  • writing-refresh：leader commit成功，并通知其他节点提交，开始刷新上层服务，通知上层可读
  • refresh-active：刷新完成，一轮提案完成

peon的状态转换图如下所示：

peon在接收到提案后就进入updating状态，此状态期间是不提供读服务的，提案完成后接收到leader的lease后会重新进入active状态

异常恢复

下面分别以leader异常退出和peon异常退出为例来看数据是如何恢复的。
在看具体恢复例子时，要先清除整个paxos实例的一个状态转换图，清楚在每个状态异常退出时，数据是如何来恢复的，如下：

leader节点在选举成功之后会进入recovering状态用以尝试恢复数据，如果发现有未提交的数据，则会进入updating_previous状态，开始恢复数据，下面通过两种情况来分析monitor中paxos的恢复逻辑。

Peon down

peon节点down掉之后会触发选主流程，由于monitor是根据ip来选主的，原先的leader节点必定还会当选，且它的数据一定是最新的，leader节点只需进入数据恢复流程，尝试提交尚未commit的数据即可。

down的节点在之后加入集群后通过probing阶段便可同步数据，之后正常加入集群，leader节点不会变化

Leader down

leader节点可能down在任意状态，下面分别从leader down、leader up后集群如何恢复正常来看整个数据恢复流程。

down

leader down了之后，有新的peon节点当选为leader，leader节点可能down在以下几种状态：

  • down在active状态，无需恢复数据
  • down在updating状态，如果没有peon accept提案，则无需恢复数据。如果有的话，peon只需学习该提案即可
  • down在writing状态，说明所有peon已经accept提案，新的leader会从新propose该提案
  • down在refresh状态，说明老的leader已经成功提交提案，如果peon已经收到commit消息，则该提案会被学习到，若未收到的话，会重新propose该提案

up

leader节点在重新up后，会通过probing阶段做数据同步，当选为leader之后会进入数据恢复流程。

节点异常恢复分析需要重点关注下是否会存在数据丢失或者不一致的情况，peon节点down掉肯定不会造成数据丢失和不一致。唯一需要注意的是leader点down掉，如果数据已经commit了的话，peon处肯定是会持久存储的，所以不会有数据丢失，如果还有uncommited的数据的话，如果有peon已经接收的话，是会被重新学习的，所以不会造成数据丢失和不一致。

一致性达成

要保证强一致性的读取，有以下两个点需要注意：

  • 如果防止读到过期的数据
  • 如何防止读到尚未commit的数据

ceph-monitor中是通过租约机制来保证读的，持有lease的节点才能被读取数据，在提案过程之中所有节点的租约是会回收的，即提案过程中，paxos层是不可读的，这对于monitor这种典型的读多写少的场景也是一种合理的取舍。
同时通过以上的分析可知，每个提案是有一个版本号的，上层应用层在读取数据的时候需要带上版本号来读取数据，对于尚未commit的提案，是不可能会被读取到的，反应在应用层就是读请求会阻塞住，直至该提案可读。

定制化实现

与标准的multi-paxos或者其他paxos工程化实现，ceph-monitor中的paxos做了如下实现：

  • quorum：与其他共识算法实现很不同的是，ceph-paxos中quorum成员在选主之后就是固定的，之后所有的决议都要全部quorum成员的同意，任何一个quorum成员的变化都会触发重新选主。这样能简化paxos的实现，但是如果quorum成员变化频繁的话，ceph-paxos的可用性和性能就会受到很大影响。考虑到Monitor的节点数较少，这种取舍也是合理的

  • 一次决议一个值：ceph-paxos一次只能决议一个值，同时对于决议值要求所有的quorum成员都应答，即不允许参与决议的节点存在日志空洞，前一条日志commit之后才能发起下个提案，这样能非常有效简化数据恢复流程。对于决议过程中的新提案请求，ceph-paxos层及上层的应用层都会进行聚合，这样能有效降低monitor的写入压力

  • 读取：leader节点会给peon节点发放lease，持有lease的节点可以接收读请求，如果有提案在决议过程中，则取消peon的lease，防止读到旧的数据，提案commit之后peon节点会重新获得lease。通过每个提案会有个版本号，应用层读取数据时会带上此版本号用以读取最新的数据，通过这样的机制可以保证强一致性读，lease的引入对于monitor这种典型的读多写少的应用也是非常有效的

Reference

Posted on

FBString是folly中关于std::string的实现，它更加精细地控制了内存的使用，在64位X86平台上，它的实现方式如下：

  • 对于小字符串（0~23字节），直接将数据存储在栈内，不需在对上开辟空间，因为栈的访问效率较高
  • 中等长度的字符串（24~254字节），在堆上开辟空间，发生拷贝时直接复制整个字符串
  • 大长度的字符串（大于254字节），在堆上开辟空间，采用COW机制

定义

fbstring的定义如下：

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
typedef basic_fbstring<char> fbstring;

template <typename E, class T, class A, class Storage>
#else
template <
    typename E,
    class T = std::char_traits<E>,
    class A = std::allocator<E>,
    class Storage = fbstring_core<E>>
class basic_fbstring {}
class fbstring_core() {
  struct MediumLarge {
    Char* data_;
    size_t size_;
    size_t capacity_;

    size_t capacity() const {
      return kIsLittleEndian ? capacity_ & capacityExtractMask : capacity_ >> 2;
    }

    //
    void setCapacity(size_t cap, Category cat) {
      capacity_ = kIsLittleEndian
          ? cap | (static_cast<size_t>(cat) << kCategoryShift)
          : (cap << 2) | static_cast<size_t>(cat);
    }
  };

  //将短字符串存储在栈区，用union存储，可以有效节省内存
  union {
    uint8_t bytes_[sizeof(MediumLarge)]; // 存储所有字节
    Char small_[sizeof(MediumLarge) / sizeof(Char)];
    MediumLarge ml_;
  };
  
  constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
  constexpr static size_t maxSmallSize = lastChar / sizeof(Char);//64为x86平台为23个（宽）字节
  constexpr static size_t maxMediumSize = 254 / sizeof(Char);
  constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
  constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
  constexpr static size_t capacityExtractMask = kIsLittleEndian
      ? ~(size_t(categoryExtractMask) << kCategoryShift)
      : 0x0 /* unused */;
}

下面来看fbstring_core的实现。

构造

还是以最常见的std::string(“xxx”)这种构造方式为例来看它对应的构造函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fbstring_core(
    const Char* const data,
    const size_t size,
    bool disableSSO = FBSTRING_DISABLE_SSO) {
  if (!disableSSO && size <= maxSmallSize) {
    //SSO（Small String Optiomition），即短字符串优化
    initSmall(data, size);
  } else if (size <= maxMediumSize) {
    initMedium(data, size);
  } else {
    initLarge(data, size);
  }
  FBSTRING_ASSERT(this->size() == size);
  FBSTRING_ASSERT(
      size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
}

如前文所述，对不不同的size，它的实现方式是不一样的，下面来逐个分析。

  • Small
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
template <class Char>
inline void fbstring_core<Char>::initSmall(
    const Char* const data,
    const size_t size) {
  // Layout is: Char* data_, size_t size_, size_t capacity_
  
 //如果数据是内存对齐的，则用字长快速复制，否则的话就用保守的memcpy
#ifndef FBSTRING_SANITIZE_ADDRESS
  if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
    const size_t byteSize = size * sizeof(Char);
    constexpr size_t wordWidth = sizeof(size_t);
    switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
      case 3:
        ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
        FOLLY_FALLTHROUGH;
      case 2:
        ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
        FOLLY_FALLTHROUGH;
      case 1:
        ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
        FOLLY_FALLTHROUGH;
      case 0:
        break;
    }
  } else
#endif
  {
    if (size != 0) {
      //调用memcpy将data复制至small_
      fbstring_detail::podCopy(data, data + size, small_);
    }
  }
  setSmallSize(size);
}

  void setSmallSize(size_t s) {
    // Warning: this should work with uninitialized strings too,
    // so don't assume anything about the previous value of
    // small_[maxSmallSize].
    //string未经初始化时也要能调用，此时small_中可能没有数据
    FBSTRING_ASSERT(s <= maxSmallSize);
    constexpr auto shift = kIsLittleEndian ? 0 : 2;
    //用small_中的最后一个字节来存储字符串大小的信息
    small_[maxSmallSize] = char((maxSmallSize - s) << shift);
    small_[s] = '\0';
    FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
  }

由此可见，短字符串的内存结构如下所示：

由于需要一个字节存储size，另外需要一个字节存储结束符，所以small_中最多能存22个字节。

另外还有个问题就是字符串的类型（small、medium、large）是存储在哪的？答案就是同上图的size存在一起，即存在bytes_的最后一个字节中，如下所示：

1
2


因为前面也说到，短字符串的长度最多只有22个字节，存储这个长度不需要占用整个字节，所以可以用最后一个字节的高两位来存储字符串的类型，由此可见FBString对内存控制的精细度。

  • Medium
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
    const Char* const data,
    const size_t size) {
  // 多分配一个字符用以存储结束符，将data指向分配的首地址
  auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
  ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
  //调用memcpy
  if (FBSTRING_LIKELY(size > 0)) {
    fbstring_detail::podCopy(data, data + size, ml_.data_);
  }
  ml_.size_ = size;
  //设置容量及存储类别
  ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
  ml_.data_[size] = '\0';
}

由此可见，中型字符串的内存结构如下所示：

  • Large
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
template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
    const Char* const data,
    const size_t size) {
  // 大字符串启用COW
  size_t effectiveCapacity = size;
  auto const newRC = RefCounted::create(data, &effectiveCapacity);
  ml_.data_ = newRC->data_;
  ml_.size_ = size;
  ml_.setCapacity(effectiveCapacity, Category::isLarge);
  ml_.data_[size] = '\0';
}

  struct RefCounted {
    //使用atomic存储引用计数，data存在随后的连续内存中，提高内存使用效率
    std::atomic<size_t> refCount_;
    Char data_[1];

   static RefCounted* create(size_t* size) {
     //通过goodMallocSize将size对齐，提高内存分配效率
      const size_t allocSize =
          goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
      auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
      result->refCount_.store(1, std::memory_order_release);
      *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
      return result;
    }

    static RefCounted* create(const Char* data, size_t* size) {
      const size_t effectiveSize = *size;
      auto result = create(size);
      if (FBSTRING_LIKELY(effectiveSize > 0)) {
        //调用memcpy
        fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
      }
      return result;
    }
  };

大型字符串的内存分布同中型字符串基本相同，仅仅多了个引用计数需要存储，如下所示：

到此，还有个问题就是字符串的类别是如何存储的，代码如下所示：

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
typedef uint8_t category_type;
enum class Category : category_type {
  isSmall = 0,
  isMedium = kIsLittleEndian ? 0x80 : 0x2,
  isLarge = kIsLittleEndian ? 0x40 : 0x1,
};

//categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
Category category() const {
    // works for both big-endian and little-endian
    return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
  }

  struct MediumLarge {
    Char* data_;
    size_t size_;
    size_t capacity_;

 // 小端序情况下，capacityExtractMask = ~(size_t(categoryExtractMask) << kCategoryShift)
    size_t capacity() const {
      return kIsLittleEndian ? capacity_ & capacityExtractMask : capacity_ >> 2;
    }
// kCategoryShift = (sizeof(size_t) - 1) * 8;
    void setCapacity(size_t cap, Category cat) {
      capacity_ = kIsLittleEndian
          ? cap | (static_cast<size_t>(cat) << kCategoryShift)
          : (cap << 2) | static_cast<size_t>(cat);
    }
  };

由此可见，basic_string栈中最后一个字节的高两位被用来存储字符串类型，在短字符串中，该字节存储的是字符串的size，由于此时size最多为22，所以高两位是不需要的，所以可以用来存类别，而在中大型字符串中，这两位对应于capacity中的最高两位，现有主机的内存没有这么大，所以这高两位也不可能用到，因此可以用来存储字符串类型。由此可见，FBString对内存的利用控制得多精细。

拷贝

看完了构造函数，下面来看拷贝构造函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fbstring_core(const fbstring_core& rhs) {
  FBSTRING_ASSERT(&rhs != this);
  switch (rhs.category()) {
    case Category::isSmall:
      copySmall(rhs);
      break;
    case Category::isMedium:
      copyMedium(rhs);
      break;
    case Category::isLarge:
      copyLarge(rhs);
      break;
    default:
      folly::assume_unreachable();
  }
  FBSTRING_ASSERT(size() == rhs.size());
  FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
}

下面来分别看不同尺寸下的拷贝构造函数是如何实现的。

  • Small
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class Char>
inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
  static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
  static_assert(
      offsetof(MediumLarge, size_) == sizeof(ml_.data_),
      "fbstring layout failure");
  static_assert(
      offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
      "fbstring layout failure");
  // Just write the whole thing, don't look at details. In
  // particular we need to copy capacity anyway because we want
  // to set the size (don't forget that the last character,
  // which stores a short string's length, is shared with the
  // ml_.capacity field).
  ml_ = rhs.ml_;
  FBSTRING_ASSERT(
      category() == Category::isSmall && this->size() == rhs.size());
}
  • Medium
1
2
3
4
5
6
7
8
9
10
11
12
template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
    const fbstring_core& rhs) {
  //中型字符串总是采用eager-copy的方式，即字符串的拷贝总会重新分配内存并拷贝内容
  auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
  ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
  fbstring_detail::podCopy(
      rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
  ml_.size_ = rhs.ml_.size_;
  ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
  FBSTRING_ASSERT(category() == Category::isMedium);
}
  • Large
1
2
3
4
5
6
7
8
template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
    const fbstring_core& rhs) {
  //大型字符串采用COW
  ml_ = rhs.ml_;
  RefCounted::incrementRefs(ml_.data_);
  FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
}

下面来看字符串的修改是如何实现的，显而易见的是，Large的修改会导致内存的重新分配，Small及Medium字符串由于是采用的eager-copy的方式，修改的时候直接返回对应的内存地址即可，以basic_string为例来看：

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
//basic_string
reference operator[](size_type pos) {
  return *(begin() + pos);
}

iterator begin() {
  //此处store即是fbstring_core
  return store_.mutableData();
}

//fbstring_core
Char* mutableData() {
  switch (category()) {
    case Category::isSmall:
      return small_;
    case Category::isMedium:
      return ml_.data_;
    case Category::isLarge:
      return mutableDataLarge();
  }
  folly::assume_unreachable();
}

template <class Char>
inline Char* fbstring_core<Char>::mutableDataLarge() {
  FBSTRING_ASSERT(category() == Category::isLarge);
  if (RefCounted::refs(ml_.data_) > 1) { //如果无其他字符串引用，则直接返回即可，否则需要重新分配内存
    unshare();
  }
  return ml_.data_;
}

template <class Char>
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
    size_t minCapacity) {
  FBSTRING_ASSERT(category() == Category::isLarge);
  size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
  //重新分配内存
  auto const newRC = RefCounted::create(&effectiveCapacity);
  FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
  //拷贝数据
  fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
  RefCounted::decrementRefs(ml_.data_);
  ml_.data_ = newRC->data_;
  ml_.setCapacity(effectiveCapacity, Category::isLarge);
}

总结

  • fbstring在std::string的基础上对于不同尺寸的string采用了不同类型的实现方式，对内存的使用控制非常精细。
  • 短字符串直接存储在栈中从而避免内存分配
  • 中型字符串采用了eager copy的实现方式，因为folly鼓励使用jemalloc来替代glibc下默认的ptmalloc，内存使用使用很高效，开辟这样尺寸的内存可以认为是非常高效的
  • 长字符串则采用了COW的实现，减少内存拷贝

Reference

Posted on

Overview

在c++的函数调用中传递字符串引用时非常常见的，但是通常被调函数通常不关心所传参数的实际实际类型，从而可能会发生以下状况：

  • 被调函数以std::string(包括std::string&)作为参数，如果调用者传入的是非std::string的数据类型的话，必然会发生数据拷贝
  • 被调函数以char*及length作为参数，则会降低代码可读性和安全性，同时还无法使用标准库提供的一些函数
  • 被调函数是以模板实现的用以支持各种参数，但这通常会增加代码的复杂度和编译时间
  • 被调函数之间需要传递字符串的一部分（substr）时，也必然会发生数据拷贝

来看一个具体的例子：

1
2
3
4
5
std::string extract_part ( const std::string &bar ) {
    return bar.substr ( 2, 3 );
    }

if ( extract_part ( "ABCDEFG" ).front() == 'C' ) { /* do something */ }

在上述例子中，一个临时的string变量会被创建出来，然后通过引用传递的方式传入extract_part中，然后第二个临时string变量在调用substr之后会被创建出来，然后返回给调用者的时候也可能会产生数据拷贝（通过RVO可消除）。其实这两个临时变量不是必须要产生的，这说明在以string做为参数传递时经常容易产生不必要的拷贝，特别是对于大字符串来说，避免数据拷贝是很有必要的，但是标准库的COW实现也有问题，参见std::string的Copy-on-Write：不如想象中美好,所以很多大型项目或基础库都提供了StringReference的实现，如Boost::StringRef,LLVM的StringRef, Chromium的base::StringPiece等，在c++17中也新增了std::string_view来支持字符串引用。

Chrome StringPiece

Chrome中的StringPiece实现在string/string_piece.h中，它可以作为函数参数和返回值使用，一个StringPiece参数也可以接受std::string、const char*、常量字符串作为输入，这些输入都不会产生数据拷贝。
StringPiece的定义如下：

1
2
3
//strings/string_piece_forward.h
class BasicStringPiece;
typedef BasicStringPiece<std::string> StringPiece;

可以看到，StringPiece是BasicStringPiece关于std::string的实现，下面来看BasicStringPiece的实现。

1
2
3
4
5
6
7
8
9
10
11
12
//构造函数
constexpr BasicStringPiece(const value_type* str)
    : ptr_(str), length_(!str ? 0 : CharTraits<value_type>::length(str)) {}
BasicStringPiece(const STRING_TYPE& str)
    : ptr_(str.data()), length_(str.size()) {}
constexpr BasicStringPiece(const value_type* offset, size_type len)
    : ptr_(offset), length_(len) {}
BasicStringPiece(const typename STRING_TYPE::const_iterator& begin,
                 const typename STRING_TYPE::const_iterator& end) {}
//成员变量
const value_type* ptr_;
size_type length_;

可以看到，它有两个成员变量，分别是指向的数据以及数据的长度，所以它的传递和拷贝值需要拷贝相应的指针，而不需要拷贝指向的数据，这种实现方式也要求调用者要确保指向数据的有效性。如前文所说，它可以接收const char*、const std::string&作为参数。
下面来看它的部分成员函数实现，首先是substr:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  // substr.
  BasicStringPiece substr(size_type pos,
                          size_type n = BasicStringPiece::npos) const {
    return internal::substr(*this, pos, n);
  }

  //最终调用函数
  template<typename STR>
BasicStringPiece<STR> substrT(const BasicStringPiece<STR>& self,
                              size_t pos,
                              size_t n) {
  if (pos > self.size()) pos = self.size();
  if (n > self.size() - pos) n = self.size() - pos;
  return BasicStringPiece<STR>(self.data() + pos, n);
}

BasicStringPiece::substr最终调用的是substrT这个函数，可以看到的是，它不会产生额外的数据拷贝，只会拷贝指向数据的指针。

References

Posted on

从实际使用上来说，std::string跟应该叫做std::string_buffer，因为它的特性更像std::vector而不是std::array，在很多情况下都容易引起数据拷贝。在实际项目中，拷贝std::vector并不是一个好的行为，他们更想要的是copy-on-write string、不可变string、基于引用计数的string等。在实际使用的过程中，std::string的最大问题就是它不适用于作为参数传递，因为它非常容易导致不必要的数据拷贝。此外，由于各个标注库实现的方式不同，会给跨平台一直带来风险，所以现在不少大型项目都会自己实现相关的string类。在实际使用过程中一般有以下替代品：

  • boost::string_ref（chrome:StringPiece）
  • std::string_view(c++17后才可用)
  • 不直接传递一个string，而是传递它的迭代器

本文主要来分析GNU STL中std::string的实现，string_ref的实现可参考string_ref的实现，folly::FBString的实现可参考FBString的实现

定义

以gcc-stl 4.4.0为例std::string的实现方式，gnu-stl中string的定义如下：

1
2
3
4
5

template<typename _CharT, typename _Traits = char_traits<_CharT>,
         typename _Alloc = allocator<_CharT> >
  class basic_string;
typedef basic_string<char>    string;

可以看到，std::string是basic_string关于char的实现，下面来看basic_string的实现，如下为关于basic_string的部分说明：

1
2
3
4
5
6
7
8
9
*  A string looks like this:
*
*  @code
*                                        [_Rep]
*                                        _M_length //长度
*   [basic_string<char_type>]            _M_capacity //容量
*   _M_dataplus                          _M_refcount //引用计数，使用了cow
*   _M_p ---------------->               unnamed array of char_type //指向实际的数据
*  @endcode

构造

首先来看basic_string的构造函数，以最常见的std::string(“xxx”)这种构造方式为例来看它对应的构造函数：

1
2
3
4
5
template<typename _CharT, typename _Traits, typename _Alloc>
   basic_string<_CharT, _Traits, _Alloc>::
   basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
   : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
   { }

它调用_S_construct这个函数对_M_dataplus这个成员变量来进行初始化，_M_dataplus的定义为：

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

     // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
     struct _Alloc_hider : _Alloc
     {
_Alloc_hider(_CharT* __dat, const _Alloc& __a)
: _Alloc(__a), _M_p(__dat) { }

_CharT* _M_p; // The actual data.
     };

    private:
     // Data Members (private):
     mutable _Alloc_hider	_M_dataplus;

由此可见，_M_dataplus中包含指向实际数据的指针，前文也说到，basic_string中应该还包含有大小、容量等数据成员的，这部分数据成员是存在_Rep中的，basic_string只存储指向它的指针，从而将减少内存占用和避免额外的内存拷贝，它的定义如下所示：

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

     struct _Rep_base
     {
size_type		_M_length;
size_type		_M_capacity;
_Atomic_word		_M_refcount;
     };

     struct _Rep : _Rep_base
     {
       _CharT*
         _M_refdata() throw()
         { return reinterpret_cast<_CharT*>(this + 1); }//获取指向的实际数据
     }

_S_construct根据输入参数初始化_M_dataplus,定义如下：

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
  template<typename _CharT, typename _Traits, typename _Alloc>
    template<typename _InIterator>
      _CharT*
      basic_string<_CharT, _Traits, _Alloc>::
      _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
		   input_iterator_tag)
      {
#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING //是否开启动态字符串，默认是开启的，即使用引用计数
	if (__beg == __end && __a == _Alloc())
	  return _S_empty_rep()._M_refdata();
#endif
	// Avoid reallocation for common case.
     //当字符串较短时，直接将数据存在栈中，避免去申请动态内存空间
	_CharT __buf[128];
	size_type __len = 0;
	while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
	  {
	    __buf[__len++] = *__beg;
	    ++__beg;
	  }
     //根据__len分配空间，初始化__r
	_Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
     //将数据拷贝纸__r的指向位置
	_M_copy(__r->_M_refdata(), __buf, __len);
	__try
	  {
	    while (__beg != __end)
	      {
		if (__len == __r->_M_capacity)
		  {
		    // Allocate more space.
            //分配更多内存，销毁老的指针
		    _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
		    _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
		    __r->_M_destroy(__a);
		    __r = __another;
		  }
		__r->_M_refdata()[__len++] = *__beg;
		++__beg;
	      }
	  }
	__catch(...)
	  {
	    __r->_M_destroy(__a);
	    __throw_exception_again;
	  }
    // 返回指向的数据，及最终M_dataplus指向实际存储的数据
	__r->_M_set_length_and_sharable(__len);
	return __r->_M_refdata();
   }

其中，_Rep::_S_create的定义如下：

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
 template<typename _CharT, typename _Traits, typename _Alloc>
   typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
   basic_string<_CharT, _Traits, _Alloc>::_Rep::
   _S_create(size_type __capacity, size_type __old_capacity,
      const _Alloc& __alloc)
   {
    if (__capacity > _S_max_size)
__throw_length_error(__N("basic_string::_S_create"));

     //对齐页面大小及头部大小，其中头部带下是malloc分配时内存页面对齐时所需要使用的
     const size_type __pagesize = 4096;
     const size_type __malloc_header_size = 4 * sizeof(void*);
    
     //一次扩大至少两倍容量，避免频繁的内存分配
     if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
__capacity = 2 * __old_capacity;

     //多申请一个字节用以存储'\0'
    size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);

     //进行内存对齐的实际长度，需要加上头部长度
    const size_type __adj_size = __size + __malloc_header_size;
     if (__adj_size > __pagesize && __capacity > __old_capacity)
{
     //进行页面对齐
  const size_type __extra = __pagesize - __adj_size % __pagesize;
  __capacity += __extra / sizeof(_CharT);

  if (__capacity > _S_max_size)
    __capacity = _S_max_size;
  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
}

     //开辟内存
     void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
     _Rep *__p = new (__place) _Rep;
     __p->_M_capacity = __capacity;
   
     //启用引用计数
     __p->_M_set_sharable();
     return __p;
   }

到现在可以明白的是，_Rep中存储了前文说到的字符串长度、容量、引用计数等信息，同时会申请__capacity + 1大小的内存用以存储实际字符串内容。至此，整个basic_string的初始化机制就比较明朗了。

内存布局

一个std::string的内存布局如下：

拷贝

在gcc4.*版本中，basic_string的拷贝采用了COW机制，通过如下代码可以来验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;

int main() {
  string s1 = "s1";
 
  string s2 = s1;
  cout << ((void*)(s1.data()) == (void*)(s2.data())) << endl;

  s2[0] = 'x';
  cout << ((void*)(s1.data()) == (void*)(s2.data())) << endl;

  return 0;
}

在GCC 4.8.5上编译后的运行结果如下所示：

1
2
1
0

由此可验证字符串拷贝默认是采用了COW机制，下面来看字符串拷贝的具体实现，它的拷贝构造函数为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
basic_string(const basic_string& __str)
    : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
					  __str.get_allocator()),
		  __str.get_allocator())
      
 _CharT* _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
{
    return (! _M_is_leaked() && __alloc1 == __alloc2)
        ? _M_refcopy() : _M_clone (__alloc1);
}

_CharT*_M_refcopy() throw ()
{
#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
    if ( __builtin_expect(this != &_S_empty_rep(), false))
#endif
        __gnu_cxx::__atomic_add_dispatch (&this-> _M_refcount, 1);
    return _M_refdata();
}

可以看到，最终调用的_M_refcopy这个函数，将引用计数加1，然后将指针指向_Rep，下面来看实际的修改的行为。

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
reference operator []( size_type __pos )
{
    _M_leak();
    return _M_data ()[__pos ];//其中,_M_data()用以获取_M_p
}

void _M_leak ()  // for use in begin() & non-const op[]
{
    //拷贝构造时_M_is_leaked都是为false，即是通过COW生成的，所以会调用_M_leak_hard
    if (! _M_rep ()->_M_is_leaked ())
        _M_leak_hard ();
}

void _M_leak_hard ()
{
    if ( _M_rep ()->_M_is_shared ())
        _M_mutate (0, 0, 0);
    _M_rep()-> _M_set_leaked ();
}

void _M_mutate ( size_type __pos , size_type __len1, size_type __len2 )
{
    const size_type __old_size = this-> size ();
    const size_type __new_size = __old_size + __len2 - __len1 ;
    const size_type __how_much = __old_size - __pos - __len1 ;

	//重新生成_Rep,拷贝数据，引用数减1
    if ( __new_size > this -> capacity() || _M_rep ()->_M_is_shared ())
    {
      
        const allocator_type __a = get_allocator ();
        _Rep * __r = _Rep:: _S_create (__new_size , this-> capacity (), __a );

        if (__pos )
            _M_copy (__r -> _M_refdata(), _M_data (), __pos );
        if (__how_much )
            _M_copy (__r -> _M_refdata() + __pos + __len2 ,
            _M_data () + __pos + __len1, __how_much );

        //引用计数减1
        _M_rep ()->_M_dispose ( __a);

        //指向新的_Rep
        _M_data (__r -> _M_refdata());
    }
    else if (__how_much && __len1 != __len2 )
    {
        // Work in-place.
        _M_move (_M_data () + __pos + __len2 ,
            _M_data () + __pos + __len1, __how_much );
    }

    //设置自身的引用计数
    _M_rep()-> _M_set_length_and_sharable (__new_size );
}

所以数据拷贝的发生在数据实际修改的时候。

总结

  • basic_string仅仅包含一个成员_M_dataplus，它会指向一个_Rep的结构，_Rep中才会实际存放字符串的内容和长度等信息。初始化过程中，对于短字符串，会先存放在栈中，待生成_Rep指针后才会将数据拷贝至_Rep中，这样可以避免初始化短字符串的时候去申请动态内存空间
  • _Rep中记录了basic_string的引用计数，在GCC4.*版本中，引用计数是默认开启的，所以对象的拷贝构造很快
  • 因为basic_string中仅包含指向_Rep的指针这一个数据成员，所以sizeof(std::string)等于8，但是由于它还要为它分配_Rep，一个空_Rep的大小为25，所以在GCC4.*中一个空string的大小也为33个字节
  • COW能有效减少内存拷贝，但是其实现较为复杂，也存在一些其他问题，具体可参考[std::string的Copy-on-Write：不如想象中美好)，加上新的标准库中std::move的引入导致COW的这种优化不再有不要，所以从GCC5开始已经废弃了COW机制

Reference

Posted on

本文主要讲述Linux下SO_REUSEADDR及SO_REUSEPORT这两个socket选项的用法及区别，不同平台下的实现可能不同

众所周知，一个TCP/UDP连接是有如下一个五元组来确定的，没有两个连接是具有完全相同的五元组的。

1
[协议，源地址，源端口，目的地址，目的端口]

其中，协议部分是在创建socket指定的，源地址及源端口是服务端在bind时指定的，目的地址及目的端口是客户端通过connect时指定的。因为UDP是无连接的通信协议，一个UDP无需connect就使用，这种无连接的socket

在第一次发送数据的时候会有系统自动绑定一个五元组，否则的话该socket将无法接收任何数据。对于TCP连接同样是如此，系统会在连接建立之前隐式绑定一个五元组。

SO_REUSEADDDR

无法将一个socket绑定值相同的五元组容易带来如下问题：

  • TIME_WAIT状态时间过长，造成期间socket的某个端口无法复用，这个问题在tcp server重启的时候尤其严重
  • 通过0.0.0.0将socket绑定至本地任意一个地址后，其他本地地址将无法再使用

在Linux中，SO_REUSERADDR就是用以解决这个问题的。假设某个主机有两个本地地址分别是192.168.0.1及10.0.0.1，对SocketA及SocketB通过不同方式绑定有如下结果：

SO_REUSEADDR SocketA SocketB Result
ON/OFF 192.168.0.1:21 192.168.0.1:21 Error(EADDRINUSE)
ON/OFF 192.168.0.1:21 10.0.0.1:21 Ok
ON/OFF 10.0.0.1:21 192.168.0.1:21 Ok
OFF 0.0.0.1:21 192.168.0.1:21 Error(EADDRINUSE)
OFF 192.168.0.1:21 0.0.0.1:21 Error(EADDRINUSE)
ON 0.0.0.1:21 192.168.0.1:21 Ok
ON 192.168.0.1:21 0.0.0.1:21 Ok
ON/OFF 0.0.0.1:21 0.0.0.1:21 Error(EADDRINUSE)

SO_REUSEPORT

如上文所述，SO_REUSEADDR选项并不是用以将socket真正绑定至同一五元组的，Linux在3.9版本之后添加了新选项SO_REUSEPORT，通过该选项，不同线程或者进程就可以绑定至同一端口。其中需要注意的是，所以绑定至该端口的socket都需设置SO_REUSEPORT选项，否则将会绑定失败。同时基于安全性考虑，第一个进程绑定后，后续需要板顶至该端口的进程所属用户要么是root用户，要么是跟第一个进程归属于同一用户。

网络服务中一种常见的模式是用一个listen线程来接收连接后将分配工作线程来处理新连接，这种模式下listen线程容易存在瓶颈。为了解决这种问题，第二种常见模式是运行多个进程来对循环监听一个端口。在没有SO_REUSEPORT选项之前，是通过fork来实现的，父进程绑定至一个端口后，fork出多个子进程来循环监听这个socket。但是这种模式存在一个问题，当有新连接到来时，那个进程能成功获取到这个连接呢？在Linux 2.6.18之前，所有监听的进程都会被唤醒，但只有一个进程能成功获取到这个连接，这既是accept惊群问题，在Linux2.6.18之后的版本已经修复了这个问题。但是如果使用epoll去监听accept socket上的可读事件，仍会存在惊群问题。

有了SO_REUSEPORT选项，我们就可以不通过fork的方式来让多个进程监听统一端口，这样每个进程中的socket fd是不一样的，自然也就不会存在惊群问题。

Reference

Posted on

函数压栈过程

以如下代码为例来分析C++中函数调用过程中，栈是如何变化的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;

int foo(int sp1, int sp2) {
  int res = sp1 + sp2;
  return res;
}

int main() {
  int res =  foo(1, 2);

  cout << res << endl;

  return 0;
}

在Linux进程的地址空间中，栈是位于进程的高地址位置，且栈顶是向下增长的，每次的函数调用都有它自己独立的一个栈帧，用以记录这个函数调用过程中所需的信息，包括函数返回地址、参数、临时变量、保存的上下文等。其中有两个寄存器非常重要，分别esp和ebp，分别记录当前栈帧的栈顶位置和栈底位置，（对于X86-64平台上来说，对应的寄存器则为rsp及rbp），压栈使esp变小。一个典型的栈帧如下所示：

从参数开始的数据即是当前函数的栈帧，ebp的位置在运行过程中是固定的，而esp始终指向栈顶，在运行过程中是会发生变化的，而参数及返回地址之所以在ebp之上是因为这个两项是由该函数的调用者进行压栈的。ebp指向的old ebp是函数调用者的ebp值，这样该函数退出后通过old ebp即可恢复调用者的栈帧。

将示例代码编译后，通过gdb进行反汇编，首先来看main函数，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(gdb) disassemble main
Dump of assembler code for function main():
   0x0000000000400830 <+0>:	push   %rbp 
   0x0000000000400831 <+1>:	mov    %rsp,%rbp
   0x0000000000400834 <+4>:	sub    $0x10,%rsp
   0x0000000000400838 <+8>:	mov    $0x2,%esi #将foo第二个参数存入寄存器中
   0x000000000040083d <+13>:	mov    $0x1,%edi #将foo的第一个参数存入寄存器中
   0x0000000000400842 <+18>:	callq  0x400816 <foo(int, int)> # 调用foo
   0x0000000000400847 <+23>:	mov    %eax,-0x4(%rbp)
   0x000000000040084a <+26>:	mov    -0x4(%rbp),%eax
   0x000000000040084d <+29>:	mov    %eax,%esi
   0x000000000040084f <+31>:	mov    $0x601060,%edi
   0x0000000000400854 <+36>:	callq  0x4006a0 <_ZNSolsEi@plt>
   0x0000000000400859 <+41>:	mov    $0x400700,%esi
   0x000000000040085e <+46>:	mov    %rax,%rdi
   0x0000000000400861 <+49>:	callq  0x4006f0 <_ZNSolsEPFRSoS_E@plt>
   0x0000000000400866 <+54>:	mov    $0x0,%eax
   0x000000000040086b <+59>:	leaveq 
   0x000000000040086c <+60>:	retq

可以看到，参数是在调用foo之前传入的，参数可能是通过压栈的方式传入，也可能是通过寄存器传递，其中call指令用以调用foo函数，该指令也会将函数的返回地址进行压栈。下面来对foo进行反汇编，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
(gdb) disassemble foo
Dump of assembler code for function foo(int, int):
   0x0000000000400816 <+0>:	push   %rbp #将老的rbp压栈
   0x0000000000400817 <+1>:	mov    %rsp,%rbp # 将rbp指向rsp
   0x000000000040081a <+4>:	mov    %edi,-0x14(%rbp) #参数1入栈
   0x000000000040081d <+7>:	mov    %esi,-0x18(%rbp) #参数2入栈
   0x0000000000400820 <+10>:	mov    -0x14(%rbp),%edx #参数1存入edx
   0x0000000000400823 <+13>:	mov    -0x18(%rbp),%eax #参数存2入eax
   0x0000000000400826 <+16>:	add    %edx,%eax #执行加法运算，结果存储在eax中
   0x0000000000400828 <+18>:	mov    %eax,-0x4(%rbp) #将运算结果赋值给result,它的位置为rbp-4
   0x000000000040082b <+21>:	mov    -0x4(%rbp),%eax #将result赋值给eax，eax为函数返回值
   0x000000000040082e <+24>:	pop    %rbp #从栈中恢复保存的rbp,即恢复函数调用者的栈帧
   0x000000000040082f <+25>:	retq  #从栈中取到返回地址，并跳转到该位置

从上述代码也可总结出，c++中一个函数调用(foo)过程是这样的：

  1. 把该函数的所有或者部分参数入栈，或者将参数存入寄存器中
  2. 把当前指令的下一条指令压如栈中
  3. 跳转到函数foo内部执行
  4. 将调用者的ebp值压栈保存(push ebp)
  5. 重置foo函数的栈帧(mov ebp esp)
  6. 执行相关操作
  7. 执行完函数foo之后，恢复调用者的栈帧（pop ebp)
  8. 跳转到下一指令继续执行

函数返回值传递

通过前文的发汇编代码也可看到，函数的返回值是通过eax来返回的，但是eax只能存储4个字节，那么对于大于4个字节的返回值是如何传递的呢，以如下代码为例来看:

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
#include <iostream>
using namespace std;

int test4Bytes() {
  return 1;
}

long test8Bytes() {
  return 12345678901l;
}

struct node {
  long l1;
  long l2;
};

node testMoreBytes() {
  node n1;
  n1.l1 = 1234567889l;
  n1.l2 = 1234567889l;
  return n1;
}

int main() {
   int s1 = test4Bytes();

   long s2 = test8Bytes();

   node s3 = testMoreBytes();

  return 0;
}

main函数的反汇编结果如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(gdb) disassemble main
Dump of assembler code for function main():
   0x000000000040077e <+0>:	push   %rbp
   0x000000000040077f <+1>:	mov    %rsp,%rbp
   0x0000000000400782 <+4>:	sub    $0xa0,%rsp
   0x0000000000400789 <+11>:	mov    %fs:0x28,%rax
   0x0000000000400792 <+20>:	mov    %rax,-0x8(%rbp)
   0x0000000000400796 <+24>:	xor    %eax,%eax
   0x0000000000400798 <+26>:	callq  0x400726 <test4Bytes()>
   0x000000000040079d <+31>:	mov    %eax,-0x9c(%rbp)
   0x00000000004007a3 <+37>:	callq  0x400731 <test8Bytes()>
   0x00000000004007a8 <+42>:	mov    %rax,-0x98(%rbp)
   0x00000000004007af <+49>:	lea    -0x90(%rbp),%rax
   0x00000000004007b6 <+56>:	mov    %rax,%rdi
   0x00000000004007b9 <+59>:	callq  0x400741 <testMoreBytes()>
   0x00000000004007be <+64>:	mov    $0x0,%eax
   0x00000000004007c3 <+69>:	mov    -0x8(%rbp),%rdx
   0x00000000004007c7 <+73>:	xor    %fs:0x28,%rdx
   0x00000000004007d0 <+82>:	je     0x4007d7 <main()+89>
   0x00000000004007d2 <+84>:	callq  0x400610 <__stack_chk_fail@plt>
   0x00000000004007d7 <+89>:	leaveq 
   0x00000000004007d8 <+90>:	retq

从main函数的反汇编结果也可看出，前两个函数是分别是通过eax及rax来返回的。首先来看test4Bytes，如下所示：

1
2
3
4
5
6
7
(gdb) disassemble test4Bytes
Dump of assembler code for function test4Bytes():
   0x0000000000400726 <+0>:	push   %rbp
   0x0000000000400727 <+1>:	mov    %rsp,%rbp
   0x000000000040072a <+4>:	mov    $0x1,%eax
   0x000000000040072f <+9>:	pop    %rbp
   0x0000000000400730 <+10>:	retq

如前文所述，4个字节的函数返回值是通过eax来传递的。而test8Bytes的反汇编结果如下:

1
2
3
4
5
6
7
(gdb) disassemble test8Bytes
Dump of assembler code for function test8Bytes():
   0x0000000000400731 <+0>:	push   %rbp
   0x0000000000400732 <+1>:	mov    %rsp,%rbp
   0x0000000000400735 <+4>:	movabs $0x2dfdc1c35,%rax
   0x000000000040073f <+14>:	pop    %rbp
   0x0000000000400740 <+15>:	retq

可以看出，此时8个字节的返回值是通过rax来返回的，这个对于不同平台的实现来说可能是不一样的，例如在32位的机器上，一般是通过eax和edx组合来返回8个字节的返回值。上述main函数的反汇编代码中有段保护机制，为了简化无关代码的干绕，关闭端保护机制编译如下代码(g++ -fno-stack-protector )：

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
#include <iostream>
using namespace std;

struct node {
  char buf[64];
};

node testMoreBytes() {
  node n1;
  n1.buf[0] = 'c';
  return n1;
}

int main() {
   node s3 = testMoreBytes();

   s3.buf[0] = 'a';

  return 0;
}

# 相应的反汇编结果分别为：
(gdb) disassemble  main
Dump of assembler code for function main:
   0x00000000004006e7 <+0>:	push   %rbp
   0x00000000004006e8 <+1>:	mov    %rsp,%rbp
   0x00000000004006eb <+4>:	sub    $0x40,%rsp
   0x00000000004006ef <+8>:	lea    -0x40(%rbp),%rax
   0x00000000004006f3 <+12>:	mov    %rax,%rdi
   0x00000000004006f6 <+15>:	callq  0x4006d1 <_Z13testMoreBytesv>
   0x00000000004006fb <+20>:	movb   $0x61,-0x40(%rbp)
   0x00000000004006ff <+24>:	mov    $0x0,%eax
   0x0000000000400704 <+29>:	leaveq 
   0x0000000000400705 <+30>:	retq  
End of assembler dump.
(gdb) disassemble testMoreBytes
Dump of assembler code for function _Z13testMoreBytesv:
   0x00000000004006d1 <+0>:	push   %rbp
   0x00000000004006d2 <+1>:	mov    %rsp,%rbp
   0x00000000004006d5 <+4>:	mov    %rdi,-0x8(%rbp)
   0x00000000004006d9 <+8>:	mov    -0x8(%rbp),%rax
   0x00000000004006dd <+12>:	movb   $0x63,(%rax)
   0x00000000004006e0 <+15>:	nop
   0x00000000004006e1 <+16>:	mov    -0x8(%rbp),%rax
   0x00000000004006e5 <+20>:	pop    %rbp
   0x00000000004006e6 <+21>:	retq    
End of assembler dump.

从main的反汇编结果可以看出，它先是分配了64字节的一个堆栈空间，然后将该地址空间保存在rax中，然后将rax的值传入rdi中，紧接着便调用testMoreBytes函数，显而易见的是它是要将分配的这一段空间传递给testMoreBytes函数。而通过testMoreBytes的反汇编结果可以看出，它显示从rdi中取出这段地址，并将地址赋值给rax，最后再将值拷贝到这段地址空间处，所以此时函数返回值的传递过程是：

  1. main函数会在堆栈中额外开辟一段空间，用以存储返回值
  2. 将上述空间的地址传递给testMoreBytes函数，函数内部将值拷贝到该空间处
  3. main函数通过该端空间来读取返回值

Posted on

本文主要参照MSDN文档，以windows为例，讲述TCP连接的优雅关闭，Linux也是同理

本文主要讨论TCP连接中socket的优雅关闭，在实际使用时，明白关闭一个socket连接(socket connection)及关闭一个socket自身的区别是很重要的。

关闭一个socket连接(shutdown a socket connection)需要连接双方进行信息交互，这个交互即是关闭序列shutdown sequence，这中序列主要分为两种：优雅退出及强制退出。在优雅关闭中，任何已经在队列中但尚未发出的数据可以在连接被真正关闭之前被发出，而在强制退出中，任何未被发送的数据都会被丢弃。同时关闭序列也可以用来给相关应用程序发送FD_CLOSE指令，用以表示正在进行关闭连接操作。

而关闭一个socket本身(close a socket)是将这个socket删除，使得之后没有任何应用可以再使用该socket。

在Windows编程中，shutdown及WSASendDisconnect这两个函数都可以用来初始化一个关闭序列，而closesocket这个函数用以释放一个socket句柄并回收对应的资源。然而容易造成疑惑的是，再调用closesocket时，如果还没有关闭序列产生，该函数也会隐式生成一个关闭序列。事实上，依赖此特性来使用closesocket来生成一个关闭序列和回收句柄已经成为一个非常常见的用法。为了简化使用，socket编程接口会提供相应机制供使用者指定是产生优雅关闭序列还是强制关闭序列，以及closesocket函数是否应等待（linger，不是立即关闭）优雅关闭的完成。

通过为SO_LINGER及SO_DONTLINGER这两个选项设置合适的值，closesocket可以具有以下行为：

  • 生成强制关闭序列，closesocket函数立即返回
  • 优雅关闭，closesocket函数会等待优雅关闭完成或者直到超时时间，如果超时后优雅关闭还未完成，就会产生一个强制关闭序列，此后函数会返回
  • 优雅关闭，但是函数立即返回，在后台执行优雅关闭任务，这也是windows及Linux中的默认行为，然而这种模式下，应用程序是无法知道优雅关闭是否完成了

其中，linger的使用方式及具体含义可参考SO_LINGER选项使用方式

为了减少关闭TCP连接过程中可能产生的问题，我们应该尽量避免依赖closesocket来隐式调用shutdown，而是现实调用shutdown或者WSASendDisconnect来关闭连接。这样可以是对端应用程序收到FD_CLOSE指令，标识所有数据都已发送。

总体来说，如下表所示展示了应该如何优雅关闭一个TCP连接：

客户端侧 服务端侧
1. 调用shutdown(s, SD_SEND)来关闭一个连接，同时表明自身再无数据需要发送
2. 接收到FD_CLOSE事件，表示有优雅关闭正在进行，同时所有数据都已经达到
3. 将服务端待发送数据都发送给客户端
(时间上同右侧无必然联系)获取到FD_READ事件 4. 调用shutdown(s, SD_SEND)，表明服务端以无数据需要发送
5. 收到FD_CLOSE事件 调用closesocket（时间上同左侧无必然联系）
调用closesocket

Reference

Posted on

本文主要参照MSDN文档，以windows为例，讲述socket编程中SO_LINGER选项的使用

SO_LINGER选项用以用以设定一个socket在关闭时队列中的待发送数据如何处理以及closesocket函数，该结构定义如下：

1
2
3
4
typedef struct linger {
  u_short l_onoff;
  u_short l_linger;
} LINGER, *PLINGER, *LPLINGER;

成员

l_onoff

标识在调用closesocket后该socket是否仍停留一段时间从而使得队列中的数据发送出去，这个成员可以有如下取值:

取值 含义
0 close函数立即返回，socket关闭，数据由后台发送，应用层不再知晓
非0 socket会停留一段时间

l_linger

取值 含义
0 close函数立即返回，数据丢弃，发送RST报文该服务端，服务端收到后立即管理连接，这样可以不经过四次挥手来关闭连接
非0 close函数阻塞到超时时间，若为发送完成则发送RST报文