Mimalloc

这篇文章中我们会介绍一下mimalloc的实现。首先我们需要了解的是其整体结构，mimalloc的结构如下图所示

mimalloc整体结构

mimalloc

mimalloc是微软最近开源的一个malloc实现，其实验数据表明相比于jemalloc、tcmalloc等实现大约快了10%。其通过将空闲块列表(Free List)进行分片(Sharding)来获取更好的分配的内存的局部性，从而提升性能。在mimalloc中一共进行了4次Free List的Sharding。接下来我们会分别介绍这4个Free List的Sharding的位置以及其为什么要进行Free List的Sharding。

在Mimalloc页中进行的Free List的Sharding

在其他的内存分配器的实现中，一般会为每一类大小的对象保留一个Free List，随着内存的不断分配与释放，这个列表中的对象可能散布在整个地址空间中，因此内存分配的局部性较差。而在mimalloc中，其通过将内存分页，每个页负责一个特定大小的内存的分配，每个页有一个Free List，因此内存分配的空间局部性较好。

简介

Dynamo是亚马逊的一个高可用的分布式KV数据库，其需要为用户提供一种一直在线的状态。同时由于该数据库需要适应不同的场景，因此需要允许用户通过对Dynamo进行配置来决定其高可用性与性能之间的平衡。为了保证Dynamo为达成高可用性和可扩展性使用了一系列技术，包括：使用一致性哈希来对数据进行分割和复制，使用版本来保证存储对象的一致性，使用一个大多数(quorum-like)的技术及无中心化的副本同步协议来保证副本更新时的一致性，基于Gossip的分布式错误监测及成员变更协议。

简介

Google File System是谷歌开发的分布式文件系统，GFS虽然也像之前的分布式文件系统一样希望能够达到较好的性能、扩展性、可靠性、可用性，但是其设计主要是从各种使用GFS的应用的工作负载以及环境来出发的。设计GFS时，开发者对GFS的实际使用环境做出了一系列的假设，包括：

• 系统构建在很多较为偏移的商业机器上，这些机器很有可能出现错误
• GFS存储的文件一般都较大
• 应用的工作负载主要为大量的顺序读取和少量的随机读
• 应用的工作负载有大量的顺序写，文件在写入后很少会进行修改
• 系统需要有效的处理多个客户端并行向同一个文件尾追加内容的操作，这是由于GFS中很多文件被用作构建生产者消费者队列或多路归并
• 保证高的可持续的带宽利用率比保证请求的低延迟更重要

网络

网络体系结构

对网络层次的划分有多种，例如OSI的七层网络模型，TCP/IP的四层网络模型以及部分书籍中的五层网络模型。我们接下来分别介绍这几种网络模型，看看每层的功能，之后会分别对每层进行更详细的介绍。

五层网络模型

五层网络模型中，网络由下至上分别为物理层、数据链路层、网络层、传输层、应用层。其每层的功能如下：

• 物理层： 保证计算机能够在连接不同计算机的传输介质上传输数据比特流，也就是说物理层需要尽可能的屏蔽掉计算机网络中的硬件设备和传输媒体的差异，确保原始的数据可以在各种物理媒体上传输。
• 数据链路层：数据链路层在物理层提供的服务的基础上向网络层提供服务。由于主机之间可能有多条链路，该层为同一链路的主机提供数据传输服务。该层将网络层传递的分组拆分为帧。数据链路层还会处理对共享信道的访问控制及防止高速发送方淹没接收方。
• 网络层：为主机提供数据传输服务，利用数据链路层提供的相邻端点之间的数据帧的传送功能，将数据设法从源端点经过若干个中间节点传送到目的端。该层将传输层传递的报文段或用户数据段封装为分组。
• 传输层：为进程提供数据传输服务。
• 应用层：为特定应用程序提供数据传输服务，如HTTP、DNS等。传输单位为报文。

IO模型

简介

一个IO输入操作通常包括两部分，一部分是等待数据准备好，另一部分是从内核向进程复制数据。Unix的IO模型有五种：

• 阻塞式IO
• 非阻塞式IO
• IO复用(select/poll)
• 信号驱动式IO(SIGIO)
• 异步IO(AIO)

内存对齐

简介

C++中一个对象所占的内存大小取决于三点：所有非静态成员变量大小总和、编译器所进行的数据对齐而添加的填充的大小、为支持虚函数、虚继承所产生的额外负担。其中编译器会为结构体进行对齐，从而往其中加上一些并不会使用的空间，那么我们为什么需要进行内存对齐呢，其原因大致有两个，一个是平台原因，因为并不是所有的硬件平台都能访问任意地址上的任意数据的，某些硬件平台只能在某些地址处取出某些特定类型的数据，否则会抛出硬件异常；另一个是性能原因，因为为访问未对齐的内存时，CPU可能为了取出数据进行多次内存的读取操作，效率较低。

死锁

简介

死锁是指两个或者两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信造成的一种阻塞现象，如果没有外力的作用，这些进程无法进行继续的工作，此时称系统产生了死锁，这些永远在互相等待的进程被称为死锁进程。

必要条件

• 互斥：每个资源要么已经分配给了一个进程要么是可用的
• 占有和等待：已经得到某种资源的进程可以继续请求其他资源
• 不可抢占：已经分配给某个进程的资源不能够被强制的剥夺，仅能等待拥有该资源的进程主动释放资源
• 环路等待：由两个或两个以上的进程形成一个环路，环路中每个进程都在等待下一个进程所拥有的资源

存储管理

存储器抽象

操作系统需要为底层的硬件资源提供一种抽象，从而向上层隐藏底层实现细节，并便于上层软件的开发。

不抽象

而对存储器的最简单的抽象就是不进行抽象，每个程序可以直接访问内存，不同进程由于使用的是同一个地址空间，因此可以访问和修改其他进程甚至操作系统的数据。在这种抽象的情况下，如果需要运行多个进程可以利用交换技术，每次需要运行其他进程时会先将当前进程的数据保存到磁盘，然后调入其他进程；或者可以将地址空间进行划分，每个进程使用不同的地址空间来支持多个进程的运行。

地址空间

由于直接使用物理内存空间作为存储器抽象没有为上层软件开发提供一个足够好的环境，因此人们开始将物理内存抽象为地址空间。由于地址空间是每个内存可用于寻址的一系列地址的集合，因此需要将为每个进程划分一个自己的地址空间，一个方法是使用基址寄存器和界限寄存器，其中基址寄存器用于保存该进程地址空间的0地址在物理地址空间的位置，而界限寄存器用于保留程序的长度。因此程序需要装载到内存中连续的地址中，而每次进程访问内存、取指或者读写数据时CPU会在将地址发送到内存的总线前加上基址，同时监测偏移是否超过了界限寄存器。使用基址寄存器和界限寄存器可以非常方便的为每个进程提供私有的地址空间，但是由于每次访问内存都需要进行加法和比较运算因此会带来一定的额外负担，而且要求每次将程序装载到连续的内存空间中。

进程调度

简介

由于可能有多个进程或线程在竞争CPU，因此需要从所有就绪的线程或进程中选择下一个运行的，完成该工作的程序即为调度程序。总的来说，调度算法应当满足以下目标：

• 所有系统
  • 公平：给每个进程公平的CPU份额
  • 策略强制执行：满足不同系统的实际需求的策略
  • 平衡：保持系统的不同部分忙碌
• 批处理系统
  • 吞吐量：单位时间作业数
  • 周转时间：从提交到完成所花费的时间数
  • CPU利用率：保持CPU始终忙碌
• 交互式系统
  • 响应时间：快速的响应请求
  • 均衡性：满足用户需求
• 实时系统
  • 满足截至时间
  • 可预测性