以太格

概括来讲，存储引擎分为两大类：针对事务处理（OLTP）优化的结构，以及针对分析型（OLAP）的优化结构。它们典型的访问模式存在很大的差异：

• OLTP系统通常面向用户，这意味着它们可能收到大量的请求。为了处理负载，应用程序通常在每个用户查询中只涉及小量的记录。应用程序基于某种键来请求记录，而存储引擎使用索引来查找所请求的数据。磁盘寻道时间往往是瓶颈。

• 由于不直接面对最终用户，数据仓库和类似的分析系统相对并不太广为人知，它们主要由业务分析师使用。处理的查询请求数目远低于OLTP系统，但每个查询通常要求非常苛刻，需要在短时间内扫描百万条记录。磁盘带宽（不是寻道时间）通常是瓶颈，而面向列的存储对于这种工作负载成为日益流行的解决方案。 在OLTP方面，有两个主要流派的存储引擎：

• 日志结构流派：它只允许追加方式更新文件和删除过时的文件，但不会修改已写入的文件。BitCask、SSTable、LST-Tree、LevelDB、Cassandra、HBase、Lucence等属于此类；

• 原地更新流派：将磁盘视为可以覆盖的一组固定大小的页。B-Tree是这个哲学的最典型代表，它已用于所有主要的关系数据库，以及大量的非关系数据库。

日志结构的存储引擎是一个相对较新的方案。其关键思想是系统地将磁盘上随机访问写入转为顺序写入，由于硬盘驱动器和SSD的性能特性，可以实现更高的写入吞吐量。下面将针对这两种存储引擎进行分析。

在大多数软件系统中，功能特性决定了系统能做什么，而非功能特性决定了系统能走多远，本篇文章专注于非功能特性中三个比较重要的特性：

• 可靠性（Reliability）：当出现意外情况如硬件、软件故障、人为失误等，系统应可以继续正常运转：虽然性能可能有所降低，但确保功能正确。
• 可扩展性（Scalability）:随着规模的增长，例如数据量、流量或复杂性，系统应以合理的方式来匹配这种增长。
• 可维护性（Maintainability）：随着时间的推移，许多新的人员参与到系统开发和运维，以维护现有功能或适配新场景等，系统都应高效运转。

NameServer 作为消息中间件 RocketMQ 的核心组件之一， 起着注册中心的作用，这篇文章主要是从整体上分析一下NameServer的实现。 NameServer可以分为三个层次（暂且这么分，方便理解），1）通信层，使用 Netty 作为底层通信组件，封装统一的网络 IO 事件处理流程，同时用户也可以自定义事件。2）服务层，封装通用的业务逻辑：a）统一请求处理流程；b）定义三种调用方式，如同步调用，异步调用及单向调用（发出请求不需要响应数据）；c）响应超时处理；d）IO事件处理。3）业务层，实现请求处理器及事件监听器注册接口，处理NameServer相关的数据，如broker地址及保活信息、topic队列信息及服务器过滤信息。

1. 概述

Java 8中的Stream是对集合（Collection）对象功能的增强，它专注于对集合对象进行各种非常便利、高效的聚合操作（Aggregate operation），或者大批量数据操作(Bulk data operation)。Stream API借助于同样新出现的Lambda表达式，极大的提高编程效率和程序可读性。同时它提供串行和并行两种模式进行汇聚操作，并发模式能够充分利用多核处理器的优势，使用fork/join并行方式来拆分任务和加速处理过程¹。

1. 概述

ForkJoinPool运用了Fork/Join原理，使用“分而治之”的思想，将大任务分拆成小任务，从而分配给多个线程并行执行，最后合并得到最终结果，加快计算。ForkJoinPool可以充分利用多cpu，多核cpu的优势，提高算法的执行效率，ForkJoinPool整体结构如下图所示：

• ForkJoinPool：框架的主体，存放了工作队列数组，对线程、工作队列及任务进行统一的管理。
• WorkQueue：工作队列，是任务存储的容器，也是实现Work-Stealing的关键数据结构。
• ForkJoinWorkerThread：工作线程，是任务的执行单元。
• ForkJoinTask：封装业务的执行逻辑，包括任务fork及join流程。

1. 解决的问题

在分布式服务中，往往有这样的场景：将某个用户或某台机器的请求负载路由到固定的某台服务器上。简单的做法直接是使用哈希算法，h = hash(key) % N ，该算法的核心思想是：将服务器编号，使用哈希算法取根据某类请求参数key（用户id或IP）计算出一个哈希值，再对该哈希值用服务器数据N进行取余（%）操作，从而得到服务器编号。使用该算法有一个问题，就是服务器数据数目（N）增加中或减少的时候，h的值都会被改变，即请求会负载到新的服务器上，有可能会导致状态数据的失效。有没有一种算法，既可以将同一请求负载到同一台服务器上，又可以在服务器增加或减少的时候将请求的变更控制在一定的范围内，所以提出了一致性哈希算法。

一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出，其原理如下：

一致性哈希算法将整个哈希值（整数）空间组织成一个0~2^32-1的虚拟哈希环，首先，服务器按照名称（或编号）取哈希，并将该哈希值放置在哈希环上，然后再对key取哈希，按照随时针方向查找离该值最近的服务器结点哈希值，从而完成key与服务器的匹配映射工作。

通过一致性哈希算法，服务器的增加或减少只会影响该服务器周围的请求，不会扩大到整个哈希环，从而保证算法的可扩展性。

一致性哈希算法也有一个问题，就是服务器较少时，可能出现服务器之间负载的请求可能不均衡，有些服务器负载的请求可能过多，而有些服务负载较少。解决这个问题的关键是增加哈希环上服务节点的数量，在物理服务器不能增加的情况下，可以将一个服务结点映射为多个虚拟结点，均匀分布在哈希环上，从而解决该问题。

1. 概述

跳跃表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃表的平均查找和插入时间复杂度都是O(logn)，优于普通队列的O(n)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止，跳跃表示意图如下所示。 从图中可以看到， 跳跃表主要由以下部分构成：

• 表头（head）：负责维护跳跃表的节点指针；
• 跳跃表节点：保存着元素值，以及多个层。
• 层：保存着指向其他元素的指针，高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
• 表尾：全部由 NULL 组成，表示跳跃表的末尾。

本篇文章将以redis中的跳跃表为例进行介绍，代码用java进行了重写，为方便看懂，简化了部分流程。

1. 概述

红黑树（Red–black tree）是一种平衡二叉查找树，它可以在 O(logn)时间内完成查找，插入和删除，这里的n是树中元素的数目，我们首先介绍下二叉查找树。

二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

在Java中，ScheduledThreadPoolExecutor主要作用是执行延时及周期性任务，这篇文章主要分析以下几个问题：1）任务是如何存储的？2）延时及周期性任务什么时候执行及如何执行？3）任务怎么进行取消？带着这些问题我们继续往下看。

这篇文章主要讲述SynchronousQueue数据结构及在线程池中的应用。