Martin Kleppmann 的质疑

Martin上来就问，我们要锁来干啥呢？2个原因：

1. 提升效率，用锁来保证一个任务没有必要被执行两次。比如（很昂贵的计算）
2. 保证正确，使用锁来保证任务按照正常的步骤执行，防止两个节点同时操作一份数据，造成文件冲突，数据丢失。

对于第1种原因，我们对锁是有一定宽容度的，就算发生了两个节点同时工作，对系统的影响也仅仅是多付出了一些计算的成本，没什么额外的影响。这个时候 使用单点的 Redis 就能很好的解决问题，没有必要使用RedLock，维护那么多的Redis实例，提升系统的维护成本。

分布式锁是一个在很多环境中非常有用的原语，它是不同进程互斥操作共享资源的唯一方法。有很多的开发库和博客描述如何使用Redis实现DLM（Distributed Lock Manager），但是每个开发库使用不同的方式，而且相比更复杂的设计与实现，很多库使用一些简单低可靠的方式来实现。

这篇文章尝试提供更标准的算法来使用Redis实现分布式锁。我们提出一种算法，叫做Relock，它实现了我们认为比vanilla单一实例方式更安全的DLM（分布式锁管理）。我们希望社区分析它并提供反馈，以做为更加复杂或替代设计的一个实现。

翻译自《In Search of an Understandable Consensus Algorithm(Extended Version)》论文

摘要

Raft 是一种为了管理日志复制的一致性算法。它提供了和 Paxos 算法相同的功能和性能，但是它的算法结构和 Paxos 不同，使得 Raft 算法更加容易理解并且能更好的构建实际系统。为了提升可理解性，Raft 将一致性算法分解成了几个关键模块，例如Leader选举、日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态的数量。用户研究证明，对于学生而言，Raft 算法比 Paxos 算法更加容易学习。Raft 算法还包括一个新的机制来允许集群成员的动态改变，它利用重叠的大多数来保证安全性。

Redis 是一个事件驱动的内存数据库，服务器需要处理两种类型的事件。

• 文件事件
• 时间事件

文件事件(FileEvent)

Redis 服务器通过 socket 实现与客户端（或其他redis服务器）的交互,文件事件就是服务器对 socket 操作的抽象。 Redis 服务器，通过监听这些 socket 产生的文件事件并处理这些事件，实现对客户端调用的响应。

Reactor

Redis 基于 Reactor 模式开发了自己的事件处理器。

这里就先展开讲一讲 Reactor 模式。看下图：

“I/O 多路复用模块”会监听多个 FD ，当这些FD产生，accept，read，write 或 close 的文件事件。会向“文件事件分发器（dispatcher）”传送事件。

文件事件分发器（dispatcher）在收到事件之后，会根据事件的类型将事件分发给对应的 handler。

我们顺着图，从上到下的逐一讲解 Redis 是怎么实现这个 Reactor 模型的。

Redis内存限制

Redis作为一个高性能的内存NoSQL数据库，其容量受到最大内存限制的限制。

在使用Redis时，除了对性能，稳定性有很高的要求外，对内存占用也比较敏感。在使用过程中，有些用户会觉得自己的线上实例内存占用比自己预想的要大。

事实上，实例中的内存除了保存原始的键值对所需的开销外，还有一些运行时产生的额外内存，包括：

1. 垃圾数据和过期Key所占空间
2. 字典dict渐进式rehash导致未及时删除的空间
3. Redis管理数据, 包括底层数据结构开销，客户端信息，读写缓冲区等
4. 主从复制，bgsave时的额外开销
5. 其它

同步IO和异步IO，阻塞IO和非阻塞IO分别是什么，到底有什么区别？不同的人在不同的上下文下给出的答案是不同的。

这里主要讨论Linux环境下的network IO。

一 概念说明

在进行解释之前，首先要说明几个概念：

• 用户空间和内核空间
• 进程切换
• 进程的阻塞
• 文件描述符
• 缓存 I/O

用户空间与内核空间

现在操作系统都是采用虚拟存储器，那么对32位操作系统而言，它的寻址空间（虚拟存储空间）为4G（2的32次方）。操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间，也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核（kernel），保证内核的安全，操心系统将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。

针对linux操作系统而言，将最高的1G字节（从虚拟地址0xC0000000到0xFFFFFFFF），供内核使用，称为内核空间。

而将较低的3G字节（从虚拟地址0x00000000到0xBFFFFFFF），供各个进程使用，称为用户空间。

Redis对象

在Redis的世界里，存储的所有值都是这个RedisObject对象。

源码定义如下：

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

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // 引用计数
    int refcount;
    // 指向实际值的指针
    void *ptr;
} robj;

其中type可以取值枚举如下：

不同类型Type，它的底层实现/编码方式也是不一样的。枚举类型如下：

现象

ES集群，状态持续Yellow。出现部分replica一直在追primary的索引数据，追不上。线上提供服务出现慢查询，导致499量增大。

固定的几个ES节点（10.10.24.X网段），出现间歇性被踢出Cluster，随后又加入Cluster。这是导致出现yellow原因，并且一直不能恢复到Green状态。由于Master节点在10.10.19.X网段, 感觉起来就是2个网段之间不通了。

当我对遇到的问题找一个解决方案的时候，我遇到了BKD树这个难题。从来没有听过吗？这种情况可能不只是你自己。从google上搜索”bkd tree”，通常会把你引导到original research paper和Lucene中用来解决一些空间搜索的patch 网页，然后就没有其他的了。实际上，在写这篇文章的时候，google的第2篇文章推过来的是wikipedia上与这个比较相似名称的 K-D-B Tree。BKD树太冷门了，google都以为你是想找其他的。

BKD树作为一个这么伟大的发明，google这样对待它，这是相当不幸的。

BKD树是用来搜索多维数据的一种树。多维数据可以是物理空间中的一些点，也可以是一个很大调色板上的一些点。BKD树相当善于做其他数的工作。相比和BKD同类型的树，BKD树通常比K-D-B树以及更简单的 R-Trees更快，更节省空间。

本篇文章不是一个对BKD树简单的罗列或者详细描述的wikipedia。我尝试用大白话来讲解BKD树是怎么运作的，有哪些特性。

最近2年，整个开源搜索引擎领域，发展迅速，版本迭代很快。 Lucene最近两年从4.0版本已经发布到最新的7.5.0版本，Solr和Elasticsearch也不断跟进升级。Lucene作为核心包，互联网上或者是书籍上关于它的介绍和分析都比较陈旧了，很多都是基于Lucene3.x来。是时候，从底层来分析下最新的Lucene发展情况了。

本文，依Lucene 7.5.0（当时最新）版本描述。

Lucene索引文件的表现

Lucene索引在硬盘上的表现就是一系列的文件，后缀名不同，下面是一个样例：

通常，看到这些文件，我们就想打开看看，发现根本无法直接查看。这里存的到底是什么，都有什么作用。很多时候是一脸的懵。为了更好的理解这些文件，下面将一步步进行细致的分析。