NrOS: Effective Replication and Sharing in an Operating System
源自osdi2021
整体总结：
第一张图是关于节点复制的，层次关系是每个NRkernel放在不同的NUMA节点上，每个NRkernel下又有多个cpu，这些cpu之间共享内存。不同的NRkernel之间因为在不同的NUMA节点上，所以内核之间的同步用NRLog来实现（主要减少了跨内核以及跨NUMA之间的消息交互）。
第二张图是关于NROS设计，主要关注三个方面：虚拟内存、文件系统、进程调度
虚拟内存核心问题在1.修改内存映射时已有其他进程访问了改内存映射，这一问题使用resolve操作来解决。2.对映射的修改会造成TLB表项不一致，这一点通过修改后发送IPI让每个节点更新从而放弃失效的TLB来完成。
文件系统的核心问题在处理1.文件描述符问题（放入用户空间，内核空间之间进行对地址的读写）2.大文件与日志大小的冲突（较大的文件在日志中进行索引）3.用户空间缓冲区可能在所有内核同步之前被修改的问题（将缓冲区复制入内核）4.读写冲突和增加并发性（使用CNR）
进程调度主要涉及1.NR将线程分配给cpu内核层面只保留对应的映射表进行粗粒度操作2.需要写的进程写入部分内存分配问题（在创建进程前先分配好读写的内存，在使用时直接映射到预先分配好的内存即可）
这篇文章针对的主要问题是在多核状态下，针对NUMA架构的内核设计问题。在多核并发的情况下，并且为了减少多核对总线资源的抢夺，便产生了NUMA架构。与此同时，不同内核之间的一致性问题以及内存读写锁问题一直备受关注，目前针对NUMA架构设计的内核主要有两种：一是单内核架构，核心思路是多个cpu使用同一个内核，例如linux，采用的思路是使用极其复杂的数据结构和读写锁来提高整个系统的并发性，但是随着内核的增多这使得整个系统的拓展性降低——增加cpu的代价是整个系统的冗杂和沉重的负载问题。二是多内核结构，对每个NUMA节点分配一个内核，这样操作的结果是方便了整个系统的可拓展性但是使得不同的NUMA节点之间交流的效率变低使得整个系统的消息传递变得十分复杂。为了解决可拓展性和复杂性的矛盾，文章参考了分布式系统节点复制的想法，提出了NUMA节点之间进行内核复制的方法来同时满足可拓展性和简洁性，并设计了NROS被证明各种性能上优于linux。
核心思路
核心架构如图，在此前多核设计的模式中，为了方便可扩展性，大多避免了共享内存的设计，但是NROS采用了共享内存的设计（其可扩展性将在内核复制中解决），NROS的每个内核是对内核节点复制，这减少了读取内核状态时复杂的消息传递。同时为了保持节点之间的一致性，所有NRkernel共享一个NRLog数据结构，每个节点对NRLog不采用实时更新的方式，只在必要时对其进行同步，并且对整体来说，整个系统的读写都采用单线程的数据结构，从而避免出现一致性错误。
整体来说，NROS的设计有以下特征和有点：
- 相对多内核来说，采用了内核复制的模式，简化了NUMA节点之间消息传递的方式
- 在整体层面上使用单线程读写的数据结构，使得一致性模型简单并且易于扩展
- 相对单内核来说，简化了并行模型的复杂性，同时也提高了系统的扩展性
NR（Node Replication）
本文核心设计思路即为节点复制（Node Replication），即在宏观层面上使得在同一时刻不同NUMA节点上的内核状态是一致的，从而减少因内核状态读取造成的开销。并且在此之上使用单线程的读写数据结构来保持一致性以及用共享内存来减少节点之间交换数据所造成的系统开销。
一些核心概念：
NRLog：一个被各个内核节点共享的循环数据结构，其每一个条目为每个节点对内核的一次修改，并且NRLog保证操作的顺序性。NRLog自身维护一个指针指向尾部，即最新的操作位置，每个NR节点维持一个自身指针指向NRLog的条目，表示本节点目前执行到日志的位置。每一个节点再写入NRLog的内容后，其写入的内容在所有节点都执行之前无法被重复使用（为了保证一致性），所以为了防止NRLog被条目占满，每个节点都会有线程（进程）定期对自身进行更新从而保证与其他节点的一致性。
Flat combing：在NrOS中，flatcombing使得每个NUMA节点的多核中可以共享同一个NR节点（replic），这样的好处在于同一个NUMA节点中的核可以共享最后一级的内核，同时也为日志的读写提供了方便。
日志更新（写入）过程：当一个本地副本节点需要对NRLog进行修改时，向NRLog申请combiner，这个combiner有两个作用：一是在Flat combing中所提到的对本地的线程进行加锁，保证NR节点本地的一致性，二是作为对NRLog的一个访问锁，在将自己对NRLog写入的条目更新完毕后，讲NRLog指针放到尾部，并且将自己的指针也更新到尾部。这种对唯一NRLog加锁的方式即上文提到的“单线程数据结构”，这种方法的好处是使用一个十分简单可控并且可拓展的方法使各个节点之间保证一致性，但同时在某些极端情况下，这种方法会成为整个系统吞吐量的瓶颈，解决这一问题文章提出了CNR（Concurrent Node Replication，一致性节点复制）讲在介绍完NR后详细介绍。
日志更新（读取）过程：对日志读取的操作不需要新添NRLog条目，为了保证更新数据的实时性，读取过程先回对比此时本地指针和NRLog维持指针的位置，并等待combiner，当所有需要写入的NRNode使用完combiner后，需要读取的NRNode获得combiner讲自身副本数据进行更新，讲指针更新到NRLog尾部，返还combiner。这里特别需要注意一点，NRLog中日志的条目必然是线性顺序的，并且在所有节点更新完之前，写入的数据是不可重复使用的，这在保持各个节点之间的一致性过程中十分重要。
具体的读写过程以下图为例：
初始过程：每个内核维持自己的对NRLog的指针，并且NRLog本身维持一个自身的尾部指针作为日志的最新状态。
申请combiner：假设节点1的T2进程需要对内核更新，此时节点1申请到了combiner，节点1中T2执行写入NRLog操作，其他进程阻塞。
写入NRLog：节点1申请到combiner后，讲需要写入的内容加入NRLog中，并将自己维持的指针更新到日志尾部。
读入操作：当节点二读取到日志尾部在自己维持的指针之后时，申请combiner，并使自己内核的状态更新到日志的最新位置。
关于NR内核的具体数据结构、文件系统、虚拟内核等放到下周说吧，接下来讲一下CNR（Concurrent Node Replication，一致性节点复制）。
CNR（Concurrent Node Replication，一致性节点复制）
首先说明一下CNR出现的原因，因为在NR中，存在一个很大的问题：即所有节点都要共享一个NRLog，并且写入日志的过程中单个combiner对日志操作减少了并行性。
为了解决这一问题，文章提出了CNR（Concurrent Node Replication，一致性节点复制）。
核心思路：
明确两个概念：commutative & conflicting（可交换的和冲突的），我们可以将内核的操作指令分为可交换的以及冲突的，这里可交换指可线性化的，即两条或多条指令并发执行时和其线性执行的结果一致，相反，互相冲突的指令是指交换其执行顺序后可能造成其结果不一致的两条或多条指令。
之后进入正题，CNR和NR的最大区别在于CNR将所有的操作指令根据其可交换性分组，每组指令对应一个NRLog，而CNR中每一个核都映射一个NRLog，并且将自己对内核的更新只记录在自身的NRLog中。这就解决了以下的一致性问题：例如对内存的读写操作，当Node1执行Get（k）而Node2执行Write（k，buff）的时候，我们无法决定Node1和Node2谁先执行指令，从而造成的结果是我们无法确定从地址k读出的数据是不是写入的buff，而由于每个NRLog之间的指令是可交换的，所以并发执行时不会出现这样的问题。
当然，如果放在线程层面来看，更准确的说法应该是相互冲突的指令被放在同一个combiner中来执行（在CNR中，combiner变成了保证线程与自己的本地log一致性的锁）。这是一个很聪明的做法，将本应该立即保持一致的不同节点所需要保持一致性的时间要求推迟（总之就是虽然都是顺序一致性但是CNR的要求要低一点该怎么表达我暂时也想不到）。但与此同时，当所有节点需要同步时，整个同步过程将会变得较为复杂。
有关多节点同步的问题：
首先考虑一些必须涉及到全局的操作：例如对整个文件系统或内存的扫描，抑或是文件改名等操作，这需要对整个内核进行扫描操作，这个时候我们将面临两个问题：1.我们需要保证对整个内核扫描的时候没有正在更新的combiner 2.我们需要保证我们对内核的扫描均是最新的数据。
为了解决这个问题，文章巧妙设计了一种简单的操作方法：当扫描开始时，对每个NRNode中加入扫描指令，并且加上scan-lock，保证此时只有扫描操作执行（这样也避免争夺log资源造成死锁）即每一个需要更新的线程都等待扫描线程释放scan-lock。关于节点更新问题，类似于全局操作，不过依旧需要说明一点的是，扫描操作有读取和更新两种操作，读取操作只影响一个副本，而更新操作需要影响多个副本，这在设置读写锁的问题上比较重要。
NROS具体设计
这周算是整体看完了NrOS的论文，首先是发现上周对作者的整体行文过程没有搞清楚，以至于上周的一些地方（如CNR部分）是完全靠自己臆想推测出来的。在阅读全文时发现了自己的问题，这里不再一一列举，涉及到的问题会在下文遇到时提出来。
总体设计概要
NrOS的设计主要涉及以下几个方面：
- 物理内存设计
- 虚拟内存设计
- 文件系统设计
- 进程分配管理
- 日志同步问题
这里先对NUMA节点和内核复制做一点简单的说明，传统的多核并发的架构需要不同内核以及不同NUMA节点之间进行消息传递，这使得高代价的消息传递（不同核之间以及不同NUMA之间）的时间复杂度与内核的数量之间是n方的关系。针对这件事，NrOS采用了不同的方法：对于同一个NUMA节点之间的不同内核采用共享内存的方式进行信息交互，并且根据NrLog进行节点之间的同步，这就减少了内存之间消息交换的频率，并且使得消息交互的复杂度与NUMA数量相关而不是与内核数量相关。
说完了总体的内存设计架构之后，我们再来对上面几点进行详细的说明。
物理内存设计
物理内存设计主要考虑两个方面的问题：物理框架（页表）的设计以及动态内存分配的问题。
先说页表，在NrOS中，物理页表是独立于节点复制的，因为如果将初始化物理页表这一行为也下放给每个节点，会造成页表不一致的问题。所以在内核复制之前会先生成一个整体的页表，之后会将页表的指针作为参数传入内核复制的过程中，从而保证每个内核都拥有相同的页表。
关于缓存：每个NUMA将自己内存分为4KiB和2MiB的块，分配给每个核（类似于slap allocation的分法，这里不在细说）。
关于动态分配内存问题，与常规的多核系统将自己动态内存分配放在用户空间不一样的是，NrOS将动态内存分配放在内核空间，将4KiB和2MiB的块组成链表自动为程序动态分配内存。如此设计有一个很大的问题是在自动内存分配的地方很难做到完美，可能会使后期出现大量的bug。为了解决这一问题，NrOS的内核部分使用Rust编写，不同于C++，Rust的特点是安全性，即从语言设计层面避免了内存泄漏或溢出等问题的出现，这样以编译器为系统安全性做出保证，这使得NrOS将动态内存分配放入内核空间得以实现。
同时，动态内存分配仍需考虑一个问题——当内存不够时，对内核的状态复制导致不同节点不一致的问题。举个例子，不同内核进行同步的时候，由于每个内核对log进行同步不是同时进行的，所以无法确定每个内核进行同步的时候有足够的内存空间，这就会造成我们无法确定一个同步过程在每个节点中都同步成功。为了解决这一问题，我们在内核中设计了一个决定性内存分配器，在同步时，这个分配器会暂存每一个节点的内存分配结果，如果遇见分配出现错误的节点则向之前复制成功的节点返回错误。
虚拟内存
NrOS也使用虚拟内存来实现地址的独立性与一致性，其物理地址的映射表为一个B树，并且对于每一个节点，都拥有一个物理页表（上面已经提过），以及一个地址映射表。在虚拟内存系统中，NrOS提供了四个操作：MapFrame（插入表项），Unmap（删除表项），Adjust（调整表项权限）和Resolve（推进副本查询地址空间状态）。
考虑一个冲突问题：如果一个进程在复制体A的核心X上映射了一个页面，而复制体B的核心Y在复制体B应用更新之前就在用户空间访问了该映射，这个时候就会产生冲突（主要原因在于硬件页表不像日志那样只涉及内核空间）。为了处理这一问题，便有了Resolve，一旦出现了页面映射问题，便推动Resolve过程寻找冲突的映射，若找到冲突的映射则恢复进程此前的操作，若没有找到，便认为此映射为此前进程无效的读写所遗留的映射。
对于Unmap和Adjust操作来说，有一个需要注意的地方，即在处理完映射表上的操作之后，不同节点之间映射表通过log来同步这一过程本身没有问题，不过却难以处理TLB中内存映射的同步。为了处理这一问题，文章通过发送处理器内部通断来同步所有和修改块相关的进程，使之与日志同步。例如，当一个进程对映射表已有的条目进行修改后，他会发送处理器内部中断（IPI）使所有节点对日志进行同步，接着对每个核进行遍历获得其需要刷新TLB的区域，最后再使对应的TLB条目无效。
文件系统
有关文件系统的实现主要面临三个问题，接下来一一说明。
首先，文件描述符问题，通常情况下，用户空间使用文件描述符对文件进行读取的过程会对内核产生修改（例如文件描述符的偏移），这回大幅度降低整个系统的并行性。为了解决这一问题，NrOS将文件描述符放在了用户空间，并且在内核状态下，只进行针对地址的读写，这样保证了内核不必记录每个文件描述符的偏移位置。
其次，大型文件的读写问题，我们的日志是一个循环的数据结构，当系统进行改变大型文件的时候，如果将所改变的内容全部放在日志条目里，可能会产生日志的内存不够用的情况。为了解决这一问题，NrOS为大的文件在内存中分配缓冲区，并且将其索引放入日志中方便其他节点进行同步。
最后，仍需要考虑一个问题，即在用户区的读写缓冲区在未被其他节点复制之前就被改变造成节点之间读写不一致问题。为了解决这一问题，NrOS将所有的读写缓冲区事先复制进入内核内存中，这样便可以在同步的过程中进行固定地址的读写。
文件系统读写一致性问题
NrOS使用CNR来保证每个节点的读写一致性，CNR中有多个日志，根据冲突性对操作进行分组，把每组映射到不同的日志中（具体前面已经说过了）。之后针对文件改名等需要对整个文件系统进行扫描的，对整个系统进行操作（见第二节）。
进程分配管理
NrOS在内核分配层面采用粗粒度的方式为进程分配资源——NR调度器把cpu分配给进程的方式，进程通过系统调用来向内核申请cpu或释放cpu。而一个cpu被分配给一个进程之后，就会生成一个执行器对象（相当于通常意义上的内核线程），来负责进程的系统调用，以及分配用户空间和保存寄存器状态，进程会将执行器保存起来以便重复使用。
NR调度器中维持一个hash表用来把内核进程映射在对应的分配器和对应的cpu，在这个表中用来生成、删除进程以及分配调度器。
还需要注意一个问题即对进程内存分配的问题，当处理一个需要写操作分配内存的进程时会造成冲突，同时也需要每个进程统一的虚拟地址。为了解决这一问题，在内存创建前，读取程序，预先找到其需要写的位置，为其分配好内存，随后再创建进程，当需要分配需要写的内存的时候，直接映射到预先分配好的内存，从而解决冲突问题。
日志同步
这个其实是从一开始就困扰的问题然后到最后文章才说明白，，，
NrOS日志是一个循环的数据结构造成的一个可能出现的问题是，当一个节点因为某些原因一直没有和日志同步，以至于别的节点无法更新日志。为了解决这个问题，文章提出了两个解决办法：首先是无法进行更新的节点对没有更新的节点发送IPI，使对应节点对日志进行同步，从而使自己可以更新日志。然而这种使用IPI的方法代价十分昂贵，于是大多数情况下采用另一种办法：即当节点处于空闲状态时，主动对日志进行同步，从而避免频繁的IPI。
循环的数据结构还会造成一个问题，即日志中的表项只有在被覆盖时才会销毁掉，而一些表现可能有外部的数据引用，倘若在表项被覆盖时才释放这些引用就会造成大量的内存浪费。解决办法则是对每个引用根据未被同步的节点数量设置一个计数器，当计数器清零的时候则释放对应的资源。