本文耗时60分钟，阅读需要10分钟。

今天要跟大家剖析的是 redis client in golang gopkg.in/redis.v3

前文回顾

其实在此之前，我已经对这个库的源码进行过初步介绍和分析了。

Golang redis.v3源代码分析 Golang redis.v3 源代码再分析

为什么还要来分析呢？

主要是最近我们线上环境使用到redis的一个服务出现了这样的错误信息:

1
2
3

redis: connection pool timeout
...
redis: you open connections too fast (last error: xxx)

错误信息提示的很清楚，超时之后又是打开连接太快了。

应该不难理解，其实就是当连接池里面的连接超时不可用了之后，再重新创建，但是因为业务量对于redis连接数的诉求比较大，所以短时间内就出现了超过设定的连接池大小了，而这个错误是超过其预设连接池的2倍就会触发。

为什么是2倍呢？带着这样的问题，我就开始查看错误信息的来源[源码 gopkg.in/redis.v3/pool.go#L199]

注意我这里提供的源码项目版本是:

1
2
3
4
5

{
			"ImportPath": "gopkg.in/redis.v3",
			"Comment": "v3.1.4-1-g5f975ec",
			"Rev": "5f975ec92c05174cbde7254f204219ab6966c15e"
}

备注:GitHub 上已经没有3.1.4.1的分支了，那我直接给大家贴源码吧。

本文耗时60分钟，阅读需要5分钟。

今天给大家介绍一下跳跃链表。

跳跃列表由 William Pugh 发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。参见 引用并下载文档。

引用发明者的话：

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。

在计算机科学领域，跳跃链表是一种数据结构，允许快速查询一个有序连续元素的数据链表。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。 

基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。

基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表，因此得名。所有操作都以对数随机化的时间进行。

跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”，这里在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1 中。平均起来，每个元素都在 1/(1-p) 个列表中出现，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在 O(log1/p n) 个列表中出现。

本文耗时60分钟，阅读需要20分钟。

leveldb 介绍

LevelDB 是 Google 开源的持久化KV单机数据库，具有很高的随机写，顺序读/写性能，但是随机读的性能很一般，也就是说，LevelDB很适合应用在查询较少，而写很多的场景。 LevelDB 应用了LSM (Log Structured Merge) 策略，lsm_tree 对索引变更进行延迟及批量处理，并通过一种类似于归并排序的方式高效地将更新迁移到磁盘，降低索引插入开销，关于LSM，本文在后面也会简单提及。

根据Leveldb官方网站的描述，LevelDB的特点和限制如下：

特点： 1、key和value都是任意长度的字节数组； 2、entry（即一条K-V记录）默认是按照key的字典顺序存储的，当然开发者也可以重载这个排序函数； 3、提供的基本操作接口：Put()、Delete()、Get()、Batch()； 4、支持批量操作以原子操作进行； 5、可以创建数据全景的snapshot(快照)，并允许在快照中查找数据； 6、可以通过前向（或后向）迭代器遍历数据（迭代器会隐含的创建一个snapshot）； 7、自动使用Snappy压缩数据； 8、可移植性；

限制： 1、非关系型数据模型（NoSQL），不支持sql语句，也不支持索引； 2、一次只允许一个进程访问一个特定的数据库； 3、没有内置的C/S架构，但开发者可以使用LevelDB库自己封装一个server；

LevelDB本身只是一个lib库，在源码目录make编译即可，然后在我们的应用程序里面可以直接include leveldb/include/db.h头文件，该头文件有几个基本的数据库操作接口。

存储流程简述

存储流程如下所示：

• 当插入一条key-value数据时,leveldb先将数据插入到log文件(追加)中，成功后写入memtable中，既保证了高效写入,也保证了数据的稳定性
• 当memtable插入的数据到了一个界限之后，会转为Immutable memtable, 由新的memtable支持写入操作.同时，leveldb在后台会通过调度程序将 Immutable memtable dump到磁盘上的sstable文件中。
• sstable内部的数据是key有序的。由Immutable memtable不断dump出来的 sstable文件越来越多，会进行compact操作，形成新的level的sstable文 件。

本文耗时60分钟，阅读需要5分钟。