网格系统(Grid System)对于分析海量空间数据集，将地球空间划分为可识别的网格单元(cell)至关重要。

考虑到这一点，Uber开发了 H3 ，这是我们的网格系统，它可以用来有效优化乘车价格和调度、地图空间数据的可视化和挖掘。 H3使我们能够分析地理信息以设置动态价格并在整个城市范围内做出决策。 我们将H3作为网格系统用于整个市场的分析和优化。 H3就是为此目的而设计的，它使我们可以使用六边形层次索引。

今年早些时候，我们在Github上 开源了H3 ，大家都可以使用此强大的解决方案，上周，我们开源了 H3 JavaScript 版本。 在本文中，我们讨论了为什么我们使用网格系统，H3的某些独特属性以及如何开始使用H3。

图1. H3把地球分成很多六边形，使用户可以进行更精准的分析。

缘起

公司业务由于广告以及导流的影响，对搜索服务的稳定以及性能提出了更苛刻的要求，为了应对可能的流量突增，特进行了大规模，全方位的性能测试。摸清线上服务的能力，以及定位瓶颈所在。

搜索服务采用了Master-Slave的Redis服务来缓存用户的搜索结果，过期时间在5~10分钟，通过缓存来提升响应时间和并发。key是用户的请求实体json字符串，value自然是搜索结果json串，并没有使用set,hash等类型。

Redis瓶颈

经过一轮的性能测试，最终的瓶颈点落在了Redis上，如下图Grafana监控所示：

在请求和并发上去之后，redis item迅速增长到300W左右，每秒command数达到近10W。由于redis存储做了限制20G，图中可以看到内存已经满了，item肯定会被频繁置换出去，总数提升不上去。从network上看，output已经达到了近200MB/s，远超运维的限制的100MB/s(千兆网卡极限约100MB,万兆约1000MB)。

核心瓶颈点：

• 存储
• 网络IO

Lucene Field本身并不支持嵌套类型，最多也就支持多值类型。ElasticSearch进行了扩展，使得Field可以是object对象类型或者nested嵌套类型。

object类型，本质上是把字段路径打平，最终在索引里还是一个正常的Field字段，object类型转化后，并不会保留对象内的属性对应关系，这在查询中可能需要特别注意。然后nested嵌套类型却实现的对应关系。

使用上的区别，可以参考官方Nested Data Type。

本文，我们主要关注的是elasticsearch内部是如何实现的？

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，它的底层实现/编码方式也是不一样的。枚举类型如下：