本系列参考了Github上诸多开源的学习资料：

Snailclimb/JavaGuide
CyC2018/CS-Notes
taizilongxu/interview_python
zpoint/CPython-Internals
donnemartin/system-design-primer

Django

基础架构

基于Python的Web框架

WSGI

WSGI的全名是：Python Web Server Gateway Interface，它是一种用Python语言定义的Web服务器到Web应用之间的一种接口协议，这么说可能还是比较不好理解，不妨先来看一下HTTP的大致流程：

浏览器发起请求到HTTP服务器，然后服务器返回请求所对应的文本
浏览器接到请求的文本，再根据文本生成浏览器里面展示的内容

所以最简单的一个Web服务就是一个静态文件的服务器，即根据url直接找到对应的文本再返回给客户端就可以了。但是如果使用Python作为后端服务器的话，那么就会有一个将服务器的返回转化成HTTP协议的流程，WSGI就是定义这种流程的一个规范，如果没有这个规范，想要实现一个HTTP服务器可能就得花个把月去了解HTTP协议的全部内容了。

django-2

有了WSGI以后，想要实现一个基于Python的动态HTTP服务器就很简单，直接参考文档编写代码就可以了，详细内容可以参考：FullStack Python - WSGI Servers。

uwsgi和uWSGI

这两个东西的名字实在是太值得吐槽了，虽然只是大小写的区别，但却完全不同：

uWSGI是针对WSGI传输协议的一种实现，是一个Web服务器
uwsgi是uWSGI服务器包含的一种自有传输协议，与WSGI没啥关系

当红的Python-Web框架都在框架里实现了一个简单的WSGI，不需要依赖uWSGI就可以直接运行，但是Django官方文档也有说明，因为效率问题绝对不能用在生产环境，使用uWSGI进行部署可以参考官方文档：Django - 如何用 uWSGI 托管 Django。

但是一般uWSGI还会和Nginx进行混合部署，因为Nginx有非常优秀的静态文件性能，可以让静态文件由Nginx代理，动态接口再由Nginx转发到uWSGI服务器，从而让前端和后端在同一个域名中，避免了跨域问题。

ASGI

在Python3中，加入了新的关键词async和await，代替了原有协程的yield实现，形成了新的协程模型。这种新编码方式的出现，为异步服务器提供了便利，因此ASGI诞生了，它本质上就是一个支持异步服务代码的WSGI。

不过在一般情况下还是推荐使用WSGI，但如果想要使用WebSocket的话，ASGI就是一个比较好的选择了，尤其Django官方支持的WebSocket库Channels就指定了必须使用ASGI协议。但是目前ASGI还不是特别成熟，性能也容易遭遇瓶颈，因此如果要使用ASGI服务器的话还是推荐将WSGI和ASGI分开部署，再由Nginx转发请求。

处理HTTP请求的基本流程

在Django系统中处理HTTP请求时，很重要的一点是它的中间层系统，它的中间层设计类似于一个针对请求的AOP系统，许多第三方插件都是通过中间层来实现的。在最外层，Django的WSGIHandler模块会将WSGI封装的environ转化成Reqeust，之后的处理流程大致如下图：

在平时编码时，常见的中间件使用场景有：

针对登录鉴权等用户信息的额外处理，会加在Request中间件里面
报错系统可能需要把内部Exception统一转化成前端可识别的数据格式，这可以在Exception中间件中实现

系统设计

目前通常所说的系统设计都是分布式环境下的系统设计，微软有一套很好的教程，讲述了在分布式环境下构建应用需要用到的概念和技术，笔者做了搬运工，可以参考之前的博客：Architecting Distributed Cloud Applications。

对于云设计模式有兴趣的同学可以参考微软的技术博客：Azure - Cloud Design Patterns，如果通读的话应该会有一个非常好的提升，目前的大部分设计问题都可以通过一种或者多种设计模式来解决。

基本流程

绝大多数时候系统设计问题并没有标准答案，而是根据每个人对需求的理解和挖掘，在知识储备的基础上做出的。但是系统设计问题还是有迹可循的，可以参考：github - system-design-primer。可以发现里面的知识许多也在分布式的博客中有所提及，有了这些基础知识以后，再遇到设计类问题就可以利用里面的组件根据需求进行搭。

一般而言，在面试或者现实中遇到一个系统设计问题，都会经历以下几个过程：

确认需求的细节

这一步会涉及到沟通能力以及对需求的整体把控，从沟通中至少要建立几个基础信息：

该系统有哪些使用方，他们使用系统的目的都是哪些，他们长远的考虑是什么
不同的使用方可能会产生不同的读写需求，每个需求的用户量、吞吐量等等信息
建立基础的业务模型和用户故事，并与客户或者面试官二次确认

拿到一个问题没有任何沟通直接开始做是非常错误的，笔者在刚开始的时候也会犯这些错误，在项目中可能导致最后成品和客户要求有出入，在面试中可能会直接导致本轮面试失败。另外，有可能即使只有细节上的差异，最后的设计也大相径庭。

确认用户的吞吐量等信息可以知道系统中需要着重考虑扩缩容和并发的节点，避免单点故障等问题。最后二次确认并不是一个硬性要求，某些面试官可能不会把这个作为考察点，但是实际上在工作中还是需要的，这个动作意味着系统的设计目标已经建立，接下来去完成这个目标就可以了。

创建高层设计

根据之前的需求分析，就可以画出系统的大致设计图了，其中包含了各个组件和组件之间的关联。针对需要做负载均衡、故障转移的地方需要加上相应的设计，有时还可能需要加入读写分离或者一些云设计模式，这里都需要针对特定的需求进行取舍，这里也是许多设计的关键步骤。

在这一步并不会具体设计后台服务的内容，面试的时候由于时间原因，一般到这一步就差不多了，因为这一步已经可以看出候选人对于系统的理解，并且这里还会涉及到系统的可扩展性。

设计核心组件

这一步的内容是：针对某些关键的后端服务，做出更细节的设计。针对不同的子模块可能有不同的设计要求，比如：具体的数据库选型、是否加入缓存、如何利用设计模式方便地扩展功能、再细节一点可能还涉及到具体的面向对象设计等等。

Mysql

Mysql是目前最流行的关系型数据库，它最常见的数据库引擎是InnoDB，这是一种支持事务的数据库引擎。不同的数据库引擎会支持不同的功能，也有不同的优缺点，比如另一种引擎MyISAM，它的索引和查询速度更快，但是不支持事务。由于InnoDB是最常见的Mysql引擎，因此后面的内容不加说明的话默认属于InnoDB引擎。

索引

索引的目的是为了更快地找到对应的数据，其实在平时的编码中就经常会用到和索引有关的数据结构，比如：Python对象底层都是一个dict，而dict对应的实现就是哈希表；Java中的HashMap、HashSet以及TreeMap和TreeSet都是非常常用的容器，它们通过哈希表和红黑树来实现索引从而对数据的存取进行加速。

B树和B+树

B树和B+树广泛应用于各类的数据库中，它们都是树形数据结构的一种，并且都属于搜索树。

搜索树有一个非常重要的特性：它的中序遍历是有序的，由于这个特性，如果希望寻找一个 $key$，那么可以从根开始查找，根据 $key$ 和当前节点保存值的关系再递归地去查找对应子树，直到找到 $key$ 或者确认它不存在，最终查找单个值的复杂度最高就等于树的深度（当到达叶子节点时，要么已经找到对应内容，要么已经确认内容不在搜索树中）。

假设这是一个拥有 $N$ 个节点的 $M$ 叉树，那么它的平均深度应该是 $log_mN$ 的量级，除非整棵树退化成每个节点只有一个子节点，此时它的深度就是 $N$ ，因此查询单个节点的效率也会退化到 $O(N)$。为了避免这种情况，我们在维护搜索树的时候，需要对其进行平衡操作，使其深度维持在 $log_mN$ 的量级，这就引出了平衡树的概念，这种数据结构会将树的深度维持在固定的量级从而减少整体的复杂度。

平衡树的门类下面有非常多的实现，其中还有极其出名的红黑树，Java中的TreeMap底层就是这种数据结构，另外B树和B+树也都是特殊的平衡树（它们是多叉树而不是二叉树）。不过需要注意的是，维持树的平衡状态也是需要消耗额外时间的，因此每一次插入在时间上并不是等价的。

关于索引的疑问

第一个问题：为什么不使用红黑树？

早期计算机都是使用的机械硬盘，对于机械硬盘来说每次读取的寻道时间都很长，因此要尽量减少读取硬盘数据的次数从而提升效率。另外硬盘还有个4K对齐的技术，即一般情况下单次读取硬盘最少要读取4K（一个扇区）的大小。因此，最好的方法是让每个节点都刚好是4K大小，这样才可以充分利用硬盘资源，那么二叉树结构就不适用了，因为根本用不完这么大空间。

第二个问题：为什么InnoDB引擎使用了B+树作为索引？

B+树和B树的区别在于：B+树的数据全部都存储在叶子节点上，非叶子节点只存储索引信息，另外相邻的叶子节点之间还会有指针相连；但是B树则没有这种特别的限制，即所有节点都可以同时保存数据和索引。那么它们之间的区别就很明显了：B+树针对区间类型的查询会有优势（由于相邻的子节点可以直达），而B树则对随机查询单个节点更快。因此MongoDB数据库就选择使用了B树索引的结构，这里并没有孰优孰劣，只是适用的场景不同。

第三个问题：为什么推荐使用自增ID作为主键？

产品侧的原因是假设使用一个业务字段作为逐渐，那么随着产品的不断更新和迭代，可能会出现不得不更换主键或者主键有重复值的情况出现，这解决起来就非常困难。另外站在技术角度来看，主要原因还在索引的底层结构上，首先每张表都只会有一个聚簇索引（保存数据的那个索引，同时也是主键所在的索引），如果主键是个随机值，那么每次插入都可能涉及很多平衡操作，导致插入时间变长；相反如果只是递增ID的话，平衡操作就减少，因此插入效率也更高。

查询优化

由于B树的排序性质，对于多列索引和字符串索引，可以免费获得其前缀索引。但是，对于那些从中间列开始查询，或者从字符串中间开始查询的内容，就不会命中任何索引了，这也是B树索引的性质导致的，更多的Mysql查询优化建议参考：《美团技术团队-MySQL慢查询优化》和《高性能Mysql》。

哈希索引

哈希索引的底层数据结构是哈希表，这个结构在各种语言里都非常常见，就不赘述它的具体实现了。与B树索引不同的是，哈希索引只能在 $=key$ 这样的查询条件下生效，对于大于小于这一类查询则不支持；相应地，查找单个 $key$ 可以看成是 $O(1)$ 的复杂度。在Mysql中，只有MEMORY引擎支持哈希索引。

自适应哈希索引

在InnoDB引擎中，可以创建一个自适应哈希索引，这并不是一个严格意义上的索引，因为它并不会索引全部数据。它只对热点数据自动生成一个哈希索引作为缓存，同样也只在 $=key$ 这种条件下生效，具体使用方式可以参考官方文档：Mysql - Adaptive Hash Index。

事务

完美事务：ACID

并不是所有的事务都满足ACID特性的，事务本身的定义仅仅是一些数据库操作的集合，并不包含ACID的特性，ACID是四个单词的缩写：

原子性：A（atomicity），事务中的操作，要么全部执行，要么全部不执行
一致性：C（consistency），事务执行的前后，数据库完整性没有被破坏
隔离性：I（isolation），事务是相互独立的，中间状态对外不可见
持久性：D（durability），事务导致的数据修改是永久的

其中比较容易引起混淆的是原子性和一致性，其中原子性和Java中的原子性有所不同，Java中的原子性除了原子性本身以外还包含了线程之间的隔离性；而一致性也和分布式CAP理论中的一致性不是一个概念，这里的一致性包含了关系数据的完整性和业务逻辑的一致性。另外还有一个问题：为什么原子性不能保证一致性（或者说为什么要同时列出原子性和隔离性）？我们不妨假设两个事务交叉进行的场景，如果没有隔离性保障，那么其中一个就可能会覆盖另一个的结果，从而破坏一致性。

制定标准：隔离等级

由于不同的数据库事务的实现方式都不同，在并发情况下可能会发生这么几个问题：

脏读：事务A还没有提交，事务B已经读取到了A的修改（破坏隔离性）
不可重复读：事务A在事物中多次读取一个自己没有修改的值，但是结果不同（破坏一致性）
幻读：事务A在事务中进行了多次读取，中间突然出现了了在前一次没有读到的数据（破坏一致性）

为此，ISO提出了事务隔离等级的概念，这里一共有四个隔离等级，分别解决了上面的三种并发问题：

隔离级别	脏读	不可重复读	幻读
未提交读（Read Uncommitted）	可能发生	可能发生	可能发生
已提交读（Read Committed）	-	可能发生	可能发生
可重复读（Repeatable Read）	-	-	可能发生
序列化（Serializable）	-	-	-

InnoDB的锁机制

锁机制一直是一个非常复杂的主题，它不仅仅涉及具体的实现，更涉及实现之上的抽象定义。比如Java中的锁机制，其中AQS是对锁最底层的实现，在实现的基础上再进行抽象，开发出众多的工具类，形成一套完整的锁机制，方便用户使用，下面将从不同维度介绍数据库使用的锁机制。

根据锁的范围分类

只有明确指定主键或者范围才能触发InnoDB的行锁，否则会执行表锁。

无锁：

# 明确指定主键，但不存在该主键的值（没有数据，当然不会有锁）
SELECT * FROM products WHERE id=-1 FOR UPDATE;

行锁：

# 明确指定主键
SELECT * FROM products WHERE id=3 FOR UPDATE;
SELECT * FROM products WHERE id>100 FOR UPDATE;

行锁中有三种算法：

Record Lock（普通行锁）：键值在条件范围内且存在的数据行加普通行锁，对应第一行代码
Gap Lock（间隙锁）：键值再条件范围内但是数据不存在加间隙锁，对应第二行代码，假设 $id>100$ 这个条件没有命中任何数据
Next-Key Lock（混合两种锁）：综合前两种情况，加Next-Key锁，对应第二行代码，假设 $id=101$ 有一条数据，但是后面没有数据

表锁：

# 主键不明确
SELECT * FROM products WHERE name='Mouse' FOR UPDATE;
SELECT * FROM products WHERE id<>'3' FOR UPDATE;
SELECT * FROM products WHERE id LIKE '3' FOR UPDATE;

表锁又可以分为：

意向锁：一个事务在获取行锁的时候，需要先获取其操作对应的表级意向锁，从而提高效率，这么说可能有点抽象，具体可以参考：百度百科-意向锁
自增锁：在事务中插入自增类型的列时获得自增锁，这个是为了防止在事务中连续插入时产生自增列需要不连续的问题

根据锁的实现分类

共享锁和排他锁是锁具体实现的类型，对应就有行共享锁、行排他锁；意向共享锁、意向排他锁等。

共享锁：一个事务获取共享锁之后，阻止其他事务获取排他锁，类似Java的读锁
排他锁：一个事务获取排他锁之后，阻止其他事务获取任何锁，类似Java的写锁

PS：用了排他锁之后，其他事务也是可以无锁读数据的。

根据使用方式分类

根据使用场景来说，预计会出现冲突使用悲观锁（不冲突也有性能损失），预计不会出现冲突用乐观锁（出现冲突可能要多次重试，但是不冲突时对性能影响很小）

悲观锁：显示地使用事务或者行锁表锁来控制数据
乐观锁：一般会加入一个单独的version列，通过业务逻辑来进行处理，有可能需要手写回滚代码

InnoDB的事务实现

InnoDB中的事务实现包含了两个部分：锁和MVCC版本控制，其中MVCC在RR和RC两个隔离等级下生效。MVCC是一个版本控制机制，它在每个事务读取时生成一个版本的快照，从而避免了脏读，详细了解可以参考：官方文档和美团博客。本质上MVCC是一种乐观锁，有很多人说它和Next-Key锁的结合在RR的隔离级别下解决了幻读问题，笔者查阅了很多资料以后，发现并不完全是这样，正确的描述应该是：InnoDB在当前读（只读取当前事务锁定版本的数据）下解决了幻读，但是快照读（每次都读取最新版本的数据）的话还是会有幻读的。

运维

binlog

Mysql的binlog是一种二进制日志系统，它一般会用于以下两种场景：

主从复制：在这种模式下需要使用binlog文件进行数据库的状态传递
数据备份：某些恢复操作会使用到binlog文件，比如使用mysqlbinlog工具恢复数据库状态

打开数据库的binlog大概会导致1%的性能损失，但是在数据丢失的时候可能会有奇效。因为一般完整备份周期都比较长，中间发生了异常之后会导致数据有很大的回滚，即会导致RPO很糟糕，但是配合上binlog以后，理论上可以恢复到有binlog支持的任意时刻。

高可用

首先有一种最基础的高可用实现：主从复制模式，这种模式和分布式环境中的主-从比较类似，由主服务器负责读写，而从服务器只负责读，数据由主服务器向从服务器进行同步，在Mysql中数据同步的方式就是binlog同步。不需要确认机制的主从同步可能会出现一个问题：如果主从之间的连接断开，那么会破坏主从之间的数据一致性，这种方式被称为异步复制。

为了解决异步复制的问题，引入了同步复制：可以在数据写入时加入从库的确认机制，主库收到确认后再返回给客户端，但是这样就引入了大量延迟（毕竟多了额外的写库等待时间）。为了解决延迟问题引入了半同步复制：从库不需要完成写入才发送确认，而是收到binlog之后就发送确认，这大大减少了延迟问题，也是目前最常用的方式。

MMM

MMM（Master-Master replication manager for MySQL）架构使用了多个主服务器，由mmm-manager管理整个集群，每个节点都由一个mmm-agent服务向mmm-manager发送心跳包，当其中一个主库发生故障时，立刻切换到备份的主库进行写操作。但是这种方式也有诸多问题，比如：mmm-manager本身是个单点故障，mmm-agent在每个节点上也是单点，如果挂掉会导致系统误判等等。

美团对MMM这种架构进行了改进，具体可以参考：美团 - 数据库高可用架构的演进与设想。

MHA

MHA（Master High Availability）架构里有两个角色：Manager和Node，一个Manager可以管理多个Mysql集群，它会定时探测集群中的master节点，当发现master出现故障时，会自动将数据最新的slave提升为新的master，然后将剩余的slave指向新的master。

爱奇艺对MHA架构进行了改进，具体可以参考：爱奇艺技术团队 - 爱奇艺 MySQL 高可用方案概述。

MGR

MGR（MySQL Group Resplication）是在Mysql5.7中官方提出的一种插件，在普通主从模式里使用的半同步复制还是有可能导致一致性问题，因此MGR使用了Paxos算法来保证集群的一致性，它有两种模式：

单主模式，该模式下需要选举推出主节点，其他节点可以提供读服务，主节点宕机后会重新选举
多主模式，没有主节点也没有选举，任意一个节点都可以支持读写操作，节点宕机后自动切换到其他节点

在MGR中会有非常复杂的机制保证事务能在集群中正常运行，具体可以参考官网文档：Mysql - Group Replication。

基于业务的切分

当业务量增大时，一个集群是无法抗住压力的，因此必须要做一些基于业务的分库分表操作。比如订单量非常大，导致系统已经撑不住高负载时的并发量，可以对userID进行哈希计算，得到库id和表id，由于事务只在用户级别发生，因此事务可以得到保障，而库和表就可以进行动态扩展了。

可以参考大众点评的技术博客：美团 - 大众点评订单系统分库分表实践。

Redis

架构

Redis为什么这么快

Redis是一个基于内存存储、单线程执行器和IO多路复用并发模型的数据库，这种架构是其速度的来源：

单线程的执行器保证了没有线程切换的开销，也不会有并发问题
IO多路复用保证了在单线程的情况下，也有非常高的并发效率
内存存储与高效的数据结构实现，共同保证了每一步操作都非常快速，CPU不会成为性能瓶颈

某些情况下可能需要对于搭建的Redis服务有一个很好的性能估计，可以参考Redis官方的讨论：How fast is Redis?，在我的小笔记本上使用benchmark命令，如果设置pipeline为16差不多可以获得70W+的并发，如果不打开的话也有7W+的并发量。

redis-benchmark -r 1000000 -n 2000000 -t get,set,lpush,lpop -P 16 -q
SET: 755572.31 requests per second
GET: 829187.44 requests per second
LPUSH: 830909.81 requests per second
LPOP: 832292.94 requests per second

redis-benchmark -r 100000 -n 200000 -t get,set,lpush,lpop -P 1 -q
SET: 74046.65 requests per second
GET: 74183.98 requests per second
LPUSH: 73827.98 requests per second
LPOP: 73882.52 requests per second

IO多路复用

IO多路复用这种并发模型在操作系统和Java的NIO中都有涉及，在Redis中使用的IO多路复用器的基本原理都和它们类似，Redis为每个IO多路复用函数库（比如select、epoll、evport等）都实现了相同的API，Redis会在编译时自动选择系统中性能最高的IO多路复用函数。

事件处理器

在IO多路复用器的背后是文件事件分派器，分派器连接了各种处理器，整个系统架构是一个单线程处理结构，因此也不需要考虑线程切换和锁的问题，事件处理器整体分为三种类型：

连接应答处理器，它对客户端来的socket进行应答
命令请求处理器，当客户端socket可读的时候，读取客户端的命令，并且交给命令执行器执行，这一步会修改数据库里的数据内容
命令回复处理器，当有命令回复需要传达给客户端的时候，该处理器运作，并对socket执行写操作

时间事件：除了文件事件外，Redis还有一些时间事件需要处理，比如：更新服务器统计信息、尝试执行AOF和RDB等，对于这些事件会放在一个链表中，周期性地扫描该链表进行执行。

利用多核CPU

显然，Redis的单线程架构是没有办法利用多核CPU的，但是一般情况下CPU并不会成为Redis运行的瓶颈。如果想要利用多核心CPU的话，官方推荐的方案是直接创建多个Redis实例来构建一个集群：Redis - exploit multiple CPU / cores。

其实Redis早就不是曾经的单线程了，有许多操作也是在多线程下执行的，比如：

惰性删除：如果删除的对象非常大，那么会引起主线程的卡顿，因此引入了惰性删除会在另一个线程中对对象进行删除操作
AOF Sync：如果开了AOF的话Redis会定期同步日志到磁盘，这个操作也很慢，也单独起了一个异步线程来处理

Redis6的多线程

Redis6中新增了IO线程，让Redis是不是单线程的这个问题变得更加迷惑了。之前版本的Redis中最耗时的任务都运行在一个线程中，虽然CPU并不是瓶颈，但是对于系统IO的操作，还是占用了很大的时间，因为读写socket这个系统调用依旧是一个同步调用。

因此，在Redis6中加入了多个IO线程来处理读取和写入的问题，但是本质上worker线程还是一个，因此说Redis是单线程的还是没有毛病的。在性能提升方面，开启多个IO线程差不多可以让单机的Redis吞吐量翻倍：博客 - redis io thread多线程的性能瓶颈。

不过经过笔者研究，得到结论是：官方并不推荐开启IO多线程，还是更推荐使用集群方案来使用多核CPU，原因在于开启集群模式的吞吐量提升要比IO多线程更多，同时也更容易扩展，虽然运维难度增加了，但是是值得的。

数据类型

在Redis中实现的基本类型有五种：

String，可以是任意字符串，也可以是数字，也可以支持自增等操作
Hash，与Java中的HashMap类似，即哈希表
List，双向链表，支持头尾插入和删除操作，也可以用作简单的消息队列
Set，集合，并且支持交集、并集、差集等操作
SortedSet，有序集合，与集合类似，但是每个元素都会关联一个分数，元素会按照分数从小到大排序

Redis中，除了这五种基本类型以外实际上没有其它类型了，这五种类型根据数据量的大小又可能对应多种底层实现，之后Redis对于它们又做了更多的封装，从而实现了Geo、消息队列、HyperLogLog等功能。

类型实现

大多数类型细节都和常见的数据结构保持一致，不同的是Redis在底层加入了许多减少空间复杂度和单次操作时间复杂度的算法（这也是因为Redis基于内存存储和单线程的特性），下面仅列举与常见数据结构有差别的实现。

渐进式rehash

在Redis中的Hash结构和各种语言中的哈希表容器一样也会有扩容的需求，不同的是由于Redis是单线程系统，如果需要扩容的数据本身已经很大了，那么在扩容的时候一次性移动全部数据就会导致这次请求时间过长，从而卡住其他请求。

因此Redis在扩容以后并不会一次性迁移全部数据，它会保留新旧两张哈希表，每次查找时迁移一部分数据到新哈希表中，直到剩余的数据足够少了，才会一次性将剩下的数据全部迁移走并销毁旧哈希表。

跳表

常见的数据结构中与跳表对应的是红黑树，跳表这种结构只在SortedSet中使用到了，它可能对很多人来说比较陌生，详细的描述可以参考：wiki - 跳表。相比红黑树来说，跳表有一样的渐进复杂度，并且优势在于针对区间查找的效率更高，但是跳表查找单个值的复杂度并不稳定，最差可能退化到 $O(n)$。

压缩列表

压缩列表（ziplist）是一种经过特殊编码的双向链表，它支持 $O(1)$ 的时间在头尾进行push和pop操作，与普通链表不同的是，它直接使用了一整块内存来保存数据，同时每个节点的长度是由存储内容决定的，这样的好处是最大程度地利用了空间。在Hash和SortedSet这两种结构中，如果数据量很小，那么底层就会用压缩列表来实现，具体内容可以参考：Redis设计与实现 - 压缩列表。

节约内存

其实节约内存的方式就是利用好Redis提供的五种基础类型，尽量减少直接使用Key-Value，另外尽量缩短Key和Value的长度，比如：保存一个图片ID和发布人的键值对，如果能将图片ID进行分组，每个组1000个再保存成一个Hash，就可以大大减少内存占用。

应用

使用布隆过滤器

在编写爬虫代码的时候，经常会遇到一个问题：如何判断一个url到底有没有爬取过，这里引入布隆过滤器（Bloom Filter），即一个不需要执行删除操作的Set结构，在Redis中对应的结构为Bitmap，这种结构由基础的String封装而来，相比Set大大减少了内存的占用，如果担心碰撞，还可以使用多个哈希函数的方式来减少碰撞几率。

分布式锁

分布式锁是目前项目中使用Redis比较多的一个场景，主要是启动了多个定时任务时，防止多个任务同时执行同一段逻辑。它的基本实现是多个进程使用setnx命令争抢一个key（可能需要同时设置key的超时时间），由争抢到的进程去执行脚本，在执行完之后删除key。

Redlock是一个基于Redis集群的分布式锁，它会对集群中的机器都进行拿锁操作，获取到一半以上的锁才算成功拿到锁，另外考虑到锁的超时、释放和重试等问题，推荐直接参考官方文档进行实现或者使用第三方库。

运维

持久化

RDB

RDB（Redis Database）可以将某个时刻Redis的所有数据以快照的形式保存到一个文件中。

Redis使用了子进程来实现RDB备份，这里又涉及到了操作系统中父子进程的概念。当从父进程fork出子进程之后，子进程虚拟内存空间里保存的内容与父进程一致，并且操作系统还提供了写时复制的功能，这保证了RDB操作的安全性和执行效率。

AOF

AOF（Append Only File）将每一个Redis执行过的写入操作保存到日志中，当数据库重启的时候，可以通过AOF恢复到最新状态。

高可用

主从复制

通过执行slaveof命令或者提前写入相关设置，可以让一个Redis实例去复制另外一个Redis实例的数据，从而实现一个基本的主从模式（当然也可以复制从服务器），复制操作可以分为两个步骤：

从服务器向主服务器发送SYNC命令，主服务器收到后执行BGSAVE命令，生成RDB文件后发送给从服务器，从服务器将同步到RDB文件生成时的状态
之后主从服务器都会维持传递数据的offset来记录当前发送的数据位置和接收到的数据位置，当经历断线重连之后，主从服务器的offset不相等，此时会进行部分复制：主服务器向从服务器传递offset偏差对应的数据，而不需要同步整个RDB文件

当完成复制操作之后，主从之间会通过心跳维持连接状态，并且主服务器会广播所有的操作给从服务器，用这种方式实现主从模式。同时可以让从服务器处理读取请求，从而减轻主服务器的压力，但是这种主从模式是异步复制的，因此没有强一致性保障。

哨兵

光有主从是不能解决高可用问题的，当一个主服务器宕机时，需要自动选择一个从服务器替换，才可以保证写服务不中断。哨兵就提供了故障转移的功能，另外哨兵还提供了监控和通知的功能。但是至少需要三个哨兵实例，才可以保证哨兵系统的健壮性，哨兵系统本身使用了Raft算法来进行领导选举。

PS：主从和哨兵是不能保证数据不丢失的，它们的组合只能保证系统的可用性。

集群

Redis集群模式是官方提供的另一种高可用方案，包含了：槽指派、重新分片、动态扩缩容、故障转移等功能。

槽指派：Redis集群将所有的key分配到16384（原因：与心跳包的大小有关）个槽位上，然后将这些槽位分配到Redis实例上，所有的槽必须分配完毕集群才处于可用状态，任意槽没有对应的实例都会导致集群宕机

重新分片：当集群写压力增大时，可能需要新增节点，并且将槽重新指派，从而实现动态扩容，重新分片就是实现动态扩缩容的操作，在重新分片的过程中集群不需要下线，之后集群会自动迁移槽对应的数据

故障转移：集群中的节点分为主节点和从节点（与主从模式类似，但是从节点支持动态分配），当某个主节点进入下线状态时，它的从节点进行自动替换，从而实现故障转移功能

一致性哈希

一致性哈希是一种环形哈希算法，它与Redis集群本身并没有太大关系，但是经常与Redis的槽分配方案进行比较。如果不需要持久化数据，那么可以使用多个Redis实例与一致性哈希结合的方案，当有实例宕机时，一致性哈希可以保障系统的可用性。对比Redis提供的集群方案，一致性哈希不需要从服务器就可以实现动态扩缩容和故障转移的功能，不过这也是在可以接受数据丢失的前提下，因此一般只用在缓存系统里。

另外，一致性哈希经常用在这样的场景下：需要将带有相同编号的请求每次都放到同一个服务器上执行，并且还需要支持扩缩容操作。至于为什么Redis没有采用一致性哈希的方案，笔者找了半天并没有什么收获，后来看到有人提了个issue，下面最新的回答是因为槽分配实现起来简单啊，咋说呢，听着也挺合理的。

ElasticSearch

基础概念

索引、类型和文档

索引（index）：可以类比Mysql中的库，ES中的索引也是用于存放具体数据的
类型（type）：可以类比Mysql中的表，用于对文档进行定义
文档（document）：可以类比Mysql中的每一列数据

其实每次看到这种解释都会有一种比较奇怪的感觉，理由是ES是一种NoSql数据库，这种类比成Sql数据库的方式并不恰当，另外在使用的过程中也没有发生过在一个index里面放多种不同的类型情况，这可能导致整个index都难以维护，另外在多个类型有同名但不同类型字段的时候是没有办法放到同一个index里的。因此在ES的新版本中，彻底将type这种抽象移除了（官方文档传送门：ES - Removal of mapping types）。同时官方推荐了两种替代方案：一个是为每一种类型创建一个index，另一种是在index中新增一个type字段，用来标识到底是哪种类型的文档。

保存关联属性

既然是NoSql数据库，就不得不提对关系的处理，这在Redis中是完全没有相关支持的（必须由客户端通过多次请求来实现），在ES里一般有三种不同的方案可以处理数据之间的关联关系：

扁平化，直接将需要关联的对象放在文档的内部，这么做会引发一个问题：由于倒排索引的特殊性，在ES中的数组其实是不关心顺序的，在查询的时候会导致出现非常奇怪的bug
内嵌文档，新建一个内嵌文档的类型，可以解决上面提到的查询问题，但是内嵌文档会有很大的性能损失，因为ES在系统里会将内嵌文档和原文档拆开保存，再使用关联操作将它们同时返回
父子文档，存在多对多关系的时候就需要使用到父子文档，这种方式比内嵌文档更彻底，就完全是分开的文档，通过关联关系连接在一起，这种方案也有更严重的性能损失，官方推荐只有在可以节约大量存储空间的时候使用这种模式

当然除了官方推荐的三种方式以外，还可以自己用一些反模式的骚操作，比如保存多份文档等冗余方案，不过最终都是要在查询效率和存储空间之间进行权衡。

结果分页

有很多基于列表的内容，前端都需要进行页码统计和翻页操作，还可能会额外支持直接跳转到某一页这样的操作。对于Mysql来说可以使用count和limit命令来实现这两个操作，在ES中对应的是from和size命令，不过在ES中这个命令可能遇到一个常见的报错：返回的文档数量超过分页窗口的限制，默认ES最大支持的分页深度是10000，这个值可以通过配置增大，但是增大也会导致查询请求时间大大增加（其实这在Mysql中也一样）。

原因在于假如要返回第9900条到10000条之间的数据，那么数据库就必须将前面的内容都拿到，否则的话无法精确统计到第9900条到10000条，这个问题在天生集群化的ES上会更严重，为了精确找到9900条到10000条之间的数据，必须让每个shard都返回至少10000条数据再重新排序。因此在大数据分页的场景不建议采用上述方案，可选的替代方案有：

search_after，只能处理下一页这种需求，必须提供上一页最后一个项目的具体字段，并且这个组合字段不能重复，否则可能会漏掉一些结果，这种方案会影响产品设计
scroll，这种方案会让ES提供一个结果的快照，避免分页的时候多次进行查询，但是快照也就意味着不适用于高实时性的场景

索引

倒排索引

索引本质是建立一种数据结构，方便通过Key查询到对应的Value。倒排索引可能在一般的数据库中不常见，但是它是搜索引擎中最常见的底层数据结构，如果把文章ID看作Key，文章内容看作Value的话，倒排索引就是需要建立一个Value到Key的反查关系，方便通过文章的内容来查找文章的ID。

上图是一个倒排索引的样例，这里涉及了一个非常重要的步骤：分词，在分词之后对每个词和文章ID建立一个映射关系，就形成一个倒排索引的结构了，此时需要查询包含一些关键词的文章，只要去倒排索引里找关键词对应的文章ID即可。

FST数据结构

倒排索引最简单的实现可以用一个：Key是String类型，Value是Set类型的哈希表。不过哈希表的结构会使用大量的存储空间，因此在具体实现上，ES采用了FST的数据结构来节约空间。

FST是一种比较复杂的数据结构，它可以看作是一个字典树的变种，字典树如果只保存小写英文单词的话是一棵26叉树，每个节点存放一个字符，对应的子节点存放下一个字符，这样就可以共享非常多的中间节点，但是查找时间相对于哈希表也有所增加。FST则在字典树的基础之上，对每个路径增加了权重，使得结果可以进行排序，如果说字典树对应Dict的话，FST就对应OrderedDict，详细内容可以参考博客：申艳超 - 关于Lucene的词典FST深入剖析。

分布式架构

备份工具

ES官方提供了一种基于快照的备份工具，这种方式类似于Docker的镜像仓库，需要提前创建一个快照仓库，然后就可以向仓库推送快照，仓库可以建立在本地也可以建立在远程，并且快照是增量更新的，不用担心备份多了的容量问题。

不过官方没有提供和Mysql的binlog和Redis的AOF类似的工具，进行一次快照时，最终快照保存的内容会是基于开始时间到结束时间中间的某个状态，所以也不是稳定的，相比较其他数据库来说，ES的备份工具还是有待加强，不过ES集群本身的可靠性已经很高了，另外可能也是考虑到很少有用ES作为主数据库的。

Translog功能

在之前有说过，由于数据并不是实时存储到磁盘中的，因此ES引入了Translog防止意外断电导致的数据丢失问题。这种方式比较类似Mysql的binlog和Redis的AOF，不过笔者暂时没有搜到利用这种文件进行恢复的相关文章，官方文档：ES - Translog。与Mysql分布式方案相似的是，在ES的集群中各个分片与副本进行同步的时候，也是通过复制Translog并重放Translog中所有的操作来进行的。

高可用：集群、节点和分片

分片（Shard）是ES分布式中最基础也是最重要的概念，在ES中的index在物理机上就表示为多个分片的集合，这些分片相互独立并且每个都拥有自己的索引。另外，每个索引都可以设置副本数量（replica）来满足高可用的需求。每个index的主分片数量必须在index创建的时候就设置好，但是分片副本数量是随时可以修改的。

一个集群会由多个工作节点构成，ES会对分片在集群中的节点分布进行管理，用户并不需要关心，当集群进行扩缩容的时候，分片会在节点上自动进行流转，具体可以参考官方文档：ES - Clusters, nodes, and shards。

节点角色

在ES中的节点有非常多的角色，在启动ES时是可以配置节点的角色的，当然也可以不配置，由ES集群自己决定，具体各种角色的介绍可以查看官方文档：ES - Node roles，其中最常用的两种节点是：

Master-eligible node（候选主节点），这种角色并不是每个节点都是主节点，而是其中一个节点为主节点，当主节点宕机时，可以立刻进行选举从Master-eligible的节点中再选出一个节点作为新的主节点
Data node（数据节点），这种节点保存着分片的数据内容，另外客户端也可以对任意一个数据节点发起请求，并不需要经过主节点

主节点和数据写入

在ES中，主节点的任务其实是相对轻松的，它只负责管理索引、分配分片和确保子节点状态的工作。前面一节已经介绍了在集群中每个Shard都被分配到不同的节点上，对于客户端来说，每次的新增、查询和聚合等请求，连接到集群的任意一个数据节点都可以完成。

写入一条数据

当一条数据需要写入ES集群时，第一件事情就是需要直到它应该写到哪个分片中，ES中根据以下公式来计算：

shard = hash(routing) % number_of_primary_shards

其中routing是一个可变值，默认时文档的_id字段，number_of_primary_shards是等待写入index的分片数量。还记得之前提到的index的分片数量不允许修改么，从这里就可以看出不能修改的原因。另外这里的计算并没有使用一致性哈希，是因为分片最终是落到硬盘上的，新增分片后导致的数据迁移量会非常巨大，很可能拖垮整个集群，还不如让用户手动迁移数据了。

知道需要写入哪个分片后，找到分片所在的节点写入就可以了，在集群中的每个节点内都保存了Cluster State信息，该信息只能由主节点进行修改，其中就包含了每个index的分片所在的位置，然后这条数据就可以找到对应的节点写入就可以了。这种方案比较像HDFS文件系统的分布式方案，区别在于ES集群写入操作也完全不用主节点参与了。

近实时搜索

向一个ES集群写入一条数据并不是实时的，这是由底层框架Lucene决定的，它并不是传统意义上的数据库，而是一个搜索引擎。不过ES对Lucene做了诸多优化，在官方的介绍中，把它称为近实时搜索：ES - Near Real Time Search。写入数据会先写入到文件缓存中，ES会有一个周期任务定时刷新缓存（默认周期是1秒），但即使刷新缓存也不是立刻写入硬盘，因此断电有可能导致ES损失分钟级别的数据，ES通过Translog来防止这种情况。

领导选举

Bully算法

旧版本（7.0以前）的ES采用的是类Bully算法，它的基本说明如下：

每个节点都有一个唯一ID，任何时刻当前的Leader都是ID最大的那个节点
当Leader进入宕机状态时，进行选举，从候选人中选出新Leader

Bully算法的基本选举流程：

假设当前节点发现主节点已经宕机，那么向所有比自己ID更大的节点发送选举消息
如果一个节点接收到了比自己ID更小节点的选举消息，那么需要进行回复，否则无需回复
如果当前节点没有收到任何回复，那么它自己成为主节点，并向所有节点宣布，开始接收其他节点的状态并更新Cluster State信息
如果当前节点收到任何回复，那么它将等待新的主节点发送的消息，如果等待超时则发起一轮新的选举

假死和脑裂问题

单纯的Bully算法有两个核心问题很难解决：

假死：如果主节点并不是宕机而只是网络问题，也会导致其他节点开始选举，如果选举完成后主节点再次加入，那么会导致主节点反复变更
脑裂：假设一种特殊的网络故障出现，将整个集群完整的分为两个子网，那么它们会分别进行选举，从而产生两个互不相干的主节点

ES集群在Bully算法上做出了一点改进，从而避免了这两种问题的产生：

延迟选举：选举并不会在检测到主节点宕机后第一时间进行，而是会先询问其他节点是否也发现主节点宕机，如果超过半数以上的节点都发现主节点宕机，才会进行选举，这种方式也间接导致了旧版ES的故障转移时间可能会比较长
多数票选：针对脑裂问题，ES要求一个节点想要成为主节点，必须获得一定数量的票数，默认为必须大于节点总数的一半（可以通过参数自行设置），但是这种方式也意味着一个集群的节点数量至少要三个，否则就无法进行故障转移了

新版本的选举

在7.0以后的版本，ES修改了领导选举算法，并抛弃了以前被称为Zen Discovery的集群协调子系统，与之相关的配置和功能也就都被改变了。新版本的算法并不是简单的使用了某种共识算法（比如Paxos、Raft等），而是对ES的情况进行了综合考量（比如需要平滑升级、融入ES的健康检查、方便的扩缩容等）。

官方也有介绍新选举算法的博客：ES - A new era for cluster coordination，不过里面也没有介绍具体实现的细节，因此要想再深入研究的话估计只有阅读源码了，在这里就点到为止了。

MongoDB

基础概念

数据库、集合与文档

这三个内容看起来非常眼熟，和ES中索引、类型和文档的结构几乎如出一辙，这也是因为它们都属于基于文档的Nosql数据库，它们存储的最低层抽象都是以文档为单位的，之上再建立其他的抽象，同时也都对应了Mysql中的库、表和行。除了基于文档的数据库以外，常见的还有：

基于Key-Value的数据库，代表为Redis，存储结构以哈希为主
基于列的数据库，代表为Hbase，有别于传统的行式存储（Mysql），列式存储将每一列的数据存储在一起
基于图的数据库，目前笔者还没有用到，这种数据库对图结构会有额外的优化

还有其他的存储方式，具体可以参考：Wiki - NoSQL，不过这些存储方式本质上和是不是SQL数据库没有直接联系，只不过目前这些存储方式在NoSql数据库中更常见。

原子操作

在旧版本的MongoDB中是没有事务支持的，因此不能要求它保证ACID，但是针对文档的不少基础操作都是原子的，比如：创建、删除等。另外，MongoDB中还提供了针对修改的原子操作：findAndModify，并且提供了重命名、自增等各种子操作，官方文档：MongoDB - findAndModify()。

保存关联属性

在MongoDB中保存关联属性和ES中保存的方式有很多相似点，当保存一个关联关系时，有以下方案可以选择：

嵌入式关系，类似于ES中的扁平化，直接将另一个文档嵌入到当前文档中，实现一对多关系
引用式关系，用ObjectID代替嵌入内容，需要手动拉取两次才可以获得相应的文档内容

数据文件

BSON格式

BSON格式文件其实是一种二进制JSON格式（Binary JSON）文件，它的名字本身就是英文名的缩写，不过因为要适配MongoDB，它支持的字段类型和JSON略有不同，同时编码/解码效率要比JSON高很多，具体支持的类型可以参考官方文档：MongoDB - BSON types。

命名空间

在数据保存到具体的文件之后，它们是以命名空间（Namespace）为单位来组织的，在MongoDB里，每个集合或者索引都拥有自己的命名空间。命名空间通常是一个对使用者透明的抽象概念，但是在把数据保存到系统中时，它又是一个非常具体的概念。MongoDB也设计了不同的存储引擎来保存命名空间（和Mysql有不同的引擎类似），最后会将命名空间以特定的格式保存到硬盘和内存空间内。

在旧版本的MongoDB中普遍使用MMAP引擎，这种引擎每个命名空间会被切割成好多个数据文件，被称为区段（extent），区段可以保存在不同的地方，在磁盘上不一定是连续的，但是要尽量保证连续从而提升性能。并且最后一块区段会有一部分预分配的额外空间，区段整体的设计和操作系统中的内存管理很类似（它们需要解决的问题也是相似的）。

新版本的MongoDB开发了更高效的引擎，可以参考官方文档：MongoDB - Storage engines。

索引

B树索引

在前面Mysql的章节中，已经提到了有关B树和B+树索引的一些知识。对于MongoDB来说，使用的都是B树索引，其实不管使用什么类型的索引，其目的都是尽量减少磁盘IO从而加快数据检索。这里与Mysql的不同选择主要是由于MongoDB不同的应用场景导致，最主要的区别在于Mysql中会有大量的区间遍历，而MongoDB中很少有区间访问的需求。

就像系统设计章节中所描述的那样，一切的技术选择都需要基于用户的需求，技术在实现需求的层面并没有高级与低级之分，只有适应和不适应需求的区别。

额外支持的索引

使用B树索引可以满足绝大多数情况，但是MongoDB也提供了其它类型的索引以应对各种场景，官方文档：MongoDB - Indexes。

哈希索引

哈希索引是一种基于Hash计算的索引，这种索引可以设置成shard key用来支持sharding模式的集群。当设置完成之后，客户端不需要自己计算字段对应的Hash值，这种索引会将内嵌文档拍平来计算，但是它不能支持多值字段（比如array类型的字段）。

地理位置索引

MongoDB在位置索引上支持了两种不同的情况：基于球面的索引和基于平面的索引，一般来说通常的经纬度都是基于球面的索引，但是也有可能某些场景下使用的是用户自定义的坐标系，这种情况通常是基于平面的索引。

基于球面的索引支持GeoJson或者是格式化好的经纬度字段，而基于平面的索引支持平面上的坐标点字段，另外球面索引可以作为分片集群的shard key，但是平面索引不可以。

文本索引

文本索引支持所有的文本类型，与使用B树索引和哈希索引不同，这种索引主要目的是支持全文检索，也就是关键词搜索功能。另外Mongo的文本索引还可以支持设置语言、字段权重等。

不过MongoDB的文本索引还是按照标点符号进行分词的，最后会对结果做一个or的操作，这对中文来说就很尴尬了，需要复杂的搜索的话还是需要上ES或者Lucene。

分布式架构

三种集群方案

主从（Master-Slaver）

MongoDB的主从和其他的主从含义基本相同，在这种模式下，每个从节点需要知道主节点的地址，并且可以自动同步主节点产生的oplog（操作日志）文件，从而让主从节点都保持同样的状态。对于客户端来说，需要使用主节点进行写操作，同时可以通过任意节点进行读操作。

不过这种模式没有默认的故障转移方案，一般都是由客户端来操作（发现主节点失效后切换到从节点进行读写），因此MongoDB官方不推荐基础的主从架构，而是推荐使用副本集方案。

副本集（Replica Set）

副本集与主从模式类似，都是由一个主服务器和一个或多个副本构成，但是和传统主从架构不同的是，副本集提供了故障转移功能。也就是说传统的主从架构当主服务器宕机，一般都是手动切换某一个从服务器成为新的主服务器，而副本集则可以自动选举一个新的主服务器，整个过程对于客户端来说是透明的。

数据同步

在MongoDB中使用的同步文件是oplog，相比较于Mysql的binlog，MongoDB的oplog可以保证操作是幂等的，这是相对于binlog的优势，其他的内容则类似。因此，在主从模式或者副本集模式下，也会存在Mysql中类似的一致性问题，也就是可能存在短暂的主从状态不同步，比如客户端刚添加的数据并没有在列表中展示等问题。

在MongoDB中的同步会有完全同步和部分同步两种（也可以类比Redis中的同步机制）：

初始化（initial sync），这是一种完全同步的操作，在子节点首次加入副本集或者落后超过oplog记录的范围时发生，这种同步会产生大量的网络IO操作，时间也相对更长
复制（replication），这种模式是在进行了初始化同步之后，会在主节点和从节点之间产生心跳包，用来不停地同步oplog，并且子节点会重放oplog中的操作，使得它们处于同样的状态

故障转移

故障转移在从节点发现主节点掉线一段时间后发生，这里涉及到一个领导选举的问题，这里除了主节点、从节点以外还引入了仲裁节点，这种节点不会复制数据，仅参与投票过程，这样可以调整从节点的数量为奇数。

官方推荐MongoDB副本节点最少为3台，并且数量为奇数，和ES一样在MongoDB中执行故障转移时也可能会出现脑裂问题，可以通过设置副本数量为奇数+半数票通过来避免这个问题。

读写分离

在副本集模式下可以配置读写分离来提高读取性能，此时最好关闭主节点的读取功能来减少主节点的压力，另外别忘了主节点和副本之间的数据可能存在一定的延迟，需要额外的操作来减少这种延迟造成的影响。

分片（Sharding）

分片和主从、副本集属于不同方向上的高并发方案，可以类比ES的分片和Redis Cluster的方案，MongoDB的分片将数据进行拆分，并且分散到不同的机器上，从而让整个数据库可以横向扩展，并且使用一个均衡器来对各个分片进行数据平衡和迁移，但是对于写入可能效率会比其他方案更差，查询则需要尽量避免跨分片查询。

一般来说，遇到以下情况时可以考虑使用分片：

单机磁盘已经不够用了，需要分片来解决磁盘空间问题
单机不能满足写入速度的要求，需要分片将写入压力分散到不同的机器上
希望将大量数据放到内存中来提高效率，和上面两点一样，使用分片来扩展资源

分片的实现

一个MongoDB分片集群包含三种组件：

shard：每个shard包含了数据集的一部分数据，并且每个shard也可以被部署成副本集从而提高可用性
mongos：该组件作为请求的路由器，为客户端提供服务，它是分片集群的访问入口
config server：存储了所有的元数据和集群的配置信息

在真正存储数据时，数据会被分配到chunk上，每个shard可以存储很多个chunk，这部分存储的信息会保存在config server中，由mongos来负责在shard之间复制和移动chunk来进行负载均衡。

数据分布策略

在命名空间中的数据具体需要分配到哪个chunk中，是由shard key决定的，它可以在配置中被指定。根据shard key来分配chunk，有两种策略：

根据范围进行分片：这种方案可以将相近的key放到同一个shard中，好处是区间查询时效率较高，问题在于出现大量新增数据的时，很容易写入到同一个shard中，没有很好地扩展写能力
根据Hash值进行分片：这种方案将shard key计算Hash值再按照范围进行分片，这样可以将写新数据的压力均匀地分配到每个shard上，因此可以很好地扩展写性能，但是牺牲了区间查询的效率

横向扩展与高可用

在分片集群的方案下，可以非常容易地对数据库进行横向扩展，直接向集群中新增shard节点就可以扩展集群的读写性能，同时还可以扩展集群的最大容量。

高可用方案则基于副本集的高可用实现，集群中的shard节点和config server节点都可以通过副本集来部署，即通过保证每个节点的高可用来保证集群的高可用。另外，即使有一部分shard节点已经宕机，集群依旧可以对还没宕机的shard进行读取和写入，整个集群仍然保留着一部分的可用性。