以太格

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数据结构及在线程池中的应用。

之前在讲ReentrantLock时，在Java中实现线程的同步与互斥，除了JUC中提供的各种锁，还可以使用snchronized关键字，它被用于方法及方法块中，在JDK1.6之前，synchronized是基于monitor锁对象来实现的，而moniter对象是基于操作系统的futex来实现的，相对比较重量级，这种锁也被称为“重量级锁”。所以，在JDK1.6之后，JDK对synchronized进行了种种优化，为了减少获得锁和释放锁所带来的性能消耗，提高性能，引入了“轻量级锁”和“偏向锁”。

在Java中要实现资源的互斥访问及线程间的同步，一般有两种方式，一种是通过synchronized（同步块或同步方法）结合Oject.wait()及Object.signal()来实现，另外一种是通过ReentrantLock和Condition来实现。为了解决不同条件下的并发问题，Java还引入了一些高级锁和同步机制，如Semaphore,ReentrantReadWriteLock,CountDownLatch和CyclicBarrier等等。

在项目开发中，用ReentrantLock相对较多，但对其的理解程序仅限于Java语言层面，对于JVM及操作系统的底层实现并没有了解，没有一个全局的概念，相关知识点存在断层，如ReentrantLock在JVM和操作系统中到底对应什么实体？等待队列存储在什么地方？线程的等待及唤醒对应什么样的操作？JVM及操作系统在ReentrantLock中提供了什么样的功能？正好在学习操作系统的知识，把这些知识重新梳理下，打通认知上的盲点。

Memcached是一个基于内存的缓存系统，存储的是key/value的键值对，与Redis类似。不过相对于Redis，值是无类型的字节数组（类比于Reidis中的String类型）。在Reidis中构建了一个对象系统来存储键值对，Memcached内部是如何处理的？抱着这份好奇心来分析下Memcached的内存模型。

Redis是一个key-value类型的数据库，key可以是整数或者字符串，value可以支持丰富的数据结构，如字符串、列表、哈希、集合及有序集合。在Redis中，对这些数据结构统一进行了封装，都是以redis对象(redisObject)来呈现，这篇文章主要是对redisObect内部原理及实现做一些梳理，内容主要基于《Redis设计与实现》。

Redis中有丰富的数据结构，如简单动态字符串、链表、字典、跳跃表、整数集合及压缩列表，基于这些数据结构，封装了一套对象系统，供用户使用，这篇文章主要是对这些数据结构进行了一个总结及加深理解。