manout's blog

Something about me

之前和一个朋友吃饭,讨论到了工作的事情,他说工作大部分都是被资本家剥削,和之前的黑奴给奴隶主打工没有什么不同。

我倒不这么想,也激起了我的一些想法。
关于剥削大概是工作的劳动所得小于自己的工作产出,所以富者越富,穷者越穷,这里资本收益大于劳动收益。我觉得这里工作产出是很难量化的事情。一个制度完善的现代化公司,本质上都是一群人聚集在一起,共享资源,做一件或者一些事情。一个人的工作无一不是基于他人的劳动之上。一个接触上层业务的人可能能直观感觉到业务的发展情况,但是其提供的服务也都依赖于基础架构部门提供的技术支持。至于的公司的盈亏,并不是由人们想的全归老板和上层领导所得,一个公司发展初期当然要有投资的帮助,这里会有投资人的资本收益。

说到资本,资本收益确实大于劳动收益,这里合情合理,问题不在于剥削,而在于私有,一个人劳动所得归自己所有,这样的道理合情合理,拿劳动所得去换取收益,又或者资本。在此之上又获取收益,都合情合理。资本的原始积累也是在建立在劳动之上。劳动产生的价值从来都不是可以量化的,选择的重要性永远大于自我感动式的努力。努力只不过是形式上的东西。

啊,我要毕不了业了。/(ㄒoㄒ)/~~

今天 montor 提了一个问题,当任务分发后负责该任务的实例宕机怎么办。(我这么蠢当然不知道该怎么办)

忽然想起前段时间一直在学习 kafka, 发现这里的任务分发可以改为 producer-consumer 模式。

由 producer 向 kafka 发送要消费的消息,在这里是要比对的 key. 然后由多个消费者从 kafka 拉取 key 进行消费。这样一个实例宕机就只会影响一个 key 的消费状态,并且一个消费者宕机其负责的 partition 会自动被另一个消费者接管。

之前这里的问题在于一个实例是有状态的,并且其任务完全无法保证原子性。一个实例要完成的任务粒度很大,所以中间的状态无法保证。

问题

现在遇到一个问题,在一个函数中向文件写内容并返回该文件句柄, 在上游函数从该文件句柄中读取,读不到内容,原来猜测是没有 flush 到 disk 导致的。

可是调用 file.Sync 显式 flush 到 disk 仍然没有作用。

原因

意识到文件在写操作完成后 file cursor 已经定位到文件末尾,所以直接读取只会得到 eof.

解决办法

将 file cursor 重新定位到文件开头

1
2
3
4
5
offset, err := file.Seek(0, 0)
if offset != 0 || err != nil {
// seek to file begin failed.
// handle error
}

  • 业余时间做下毕设,毕业要紧
  • 完成数据一致性检测工具
  • 学习工作中用到的但是没有接触过的东西 (hive, hdfs, spark, etc…)
  • 办护照和港澳通行证
  • 攒钱去旅行
  • 控制消费,控制业余时间的消费(比如一个月看电影还是不要超过四次…)
  • 控制饮食,公司食堂虽然免费好吃但还是要节制下
  • 保持运动的习惯,跑步时间改到早上上班前,多去健身房
  • 晚上早点睡

原文出自深度开源论坛,链接

LSM(Log Structured-Merge Tree) 出自 2006 年谷歌发表的论文 big table. LSM 被用在许多产品的文件结构策略: HBase, Cassandra, LevelDB, SQLite, 在 mangodb3.0 中也附带一个可选的 LSM 引擎.

背景

LSM 的设计目的来提供比传统的 B+ 树 或者 ISAM 更好的写操作吞吐量,通过消去随机的本地更新操作来达到目标。
根本原因在于硬盘随机读写操作慢,顺序操作快的问题。两种操作方式存在巨大的差距,无论是机械硬盘还是 SSD.

LSM_random_sequence_op

上图显式顺序读写磁盘快于随机读写内存,而且至少快三个数量级。

所以应用对写操作敏感,为了避免性能瓶颈,简单的办法是将数据追加到末尾。该策略常用于日志或者堆文件,因为该文件内容是完全顺序的,所以可以提供很好的写操作性能。
因为简单和高效,基于日志的策略在大数据之间越来越流行,同时也有一些缺点,从日志文件中读特定数据将比写操作需要更多的查找时间,需要倒序扫描,直到找到所需的内容。
这样的特性说明日志仅仅适用于一些简单的场景

  • 数据是被整体访问,如大部分数据库的 WAL
  • 知道明确的 offset, 比如 kafka

所以为了提供良好的读性能(比如按 key 或者 range), 有以下四种方法

  • 二分查找: 将数据有序保存,使用二分查找来完成特定 key 的查找
  • 哈希: 用哈希将数据分割成不同的 bucket
  • B+ 树: 使用 B+ 树或者 ISAM 等方法,可以减少外部文件的读取
  • 外部文件: 将数据保存为日志,并创建一个 hash 或者查找树映射相应的文件

以上的方法都提供了良好的读性能(最低为(log(n))), 但是丢失了日志文件超好的写性能。上面这些方法都强加了总体的结构信息在数据上,数据被按照特定的方式放置,所以可以很快的找到特定的数据,但是却对写操作不友善。

LSM 发明就是为了解决上述问题,保持了日志文件写性能,以及微小的读性能损失。本质上就是让所有的操作顺序化。

很多树结构可以不用 update-in-place, 最流行的就是 append-only-tree, 也称为 copy-on-write tree. 他们通过顺序的在文件末尾重复写对结构来实现写操作,之前的树结构的相关部分,包括最顶层节点都会变成孤节点。尽管这种办法避免了本地更新,但是因为每个写结构都要重写树结构,放大了写操作,降低了写性能。

Base LSM Algorithm

基本的 LSM 是将之前使用一个大的查找结构(造成随机读写,影响写性能), 变换为将写操作顺序的保存到一些相似的有序文件(也就是 sstable[sort-string-table])中。所有每个文件包含短时间内的一些改动。因为文件是有序的,所以之后查找也会很快,文件是不可修改的,永远不会更新,新的更新操作只会写到新的文件中。读操作检查现有的文件,通过周期性的合并这些文件来减少文件个数。

LSM_file

当一些更新操作到达时,他们会被写到内存缓存(memtable)中,memtable 使用树结构来保持 key 的有序,在大部分的实现中,memtable 会通过写 WAL 的方式备份到磁盘,用来恢复数据,防止数据丢失。当 memtable 达到一定规模时会被刷新到磁盘上的一个新文件,重要的是系统只做了顺序磁盘读写,因为没有文件被编辑,新的内容或者修改只用简单的生成新的文件。

因为比较旧的文件不会被更新,重复的记录只会通过创建新的记录来覆盖,也就产生了一些冗余的数据。所以系统会周期性的执行合并操作。合并操作选择一些文件,并把他们合并到一起,移除重复的更新或者删除记录,同时也会删除上述的冗余。更重要的是,通过减少文件个数的增长,保证读操作的性能。因为 sstable 文件都是有序结构的,所以合并操作也是非常高效的。

读操作

当一个读操作请求时,系统首先检查内存数据,如果没有找到一个 key, 就会逆向检查 sstable 文件,直到 key 被找到。因为每个 sstable 都是有序的,所以查找比较高效(O(logN)), 但是读操作会变的越来越慢随着 sstable 的个数的增加,因为每一个 sstable 都要被检查。

为了提高读操作的性能,最基本的方法就是页缓存(leveldb 的 TableCache, 将 sstable 按照 LRU 缓存在内存中),减少二分查找的小号。LevelDB 和 BigTable 是将 block-index 保存在文件尾部,这样查找就只要一次 I/O 操作,如果 block-index 在内存中。

即使有每个文件的索引,随着文件个数的增多,读操作仍然很慢。通过周期的合并文件,来保持文件的个数。即使有了合并操作,读操作仍然会访问大量文件,大部分的实现通过布隆过滤器来避免大量的读文件操作,布隆过滤器一种高效的方法来判断一个 sstable 中是够包含一个特定的 key.(如果 bloom 判定一个 key 不存在,就一定不存在,而当 bloom 判定一个 key 存在,则有不存在的可能,只是通过概率保证)。

LSM_write_op

写操作

所有的写操作都被分批处理,只写到顺序块上。另外,周期性的合并操作会对 I/O 有影响,读操作有可能会访问大量的文件(散乱的读). 这就简化了算法工作的方法,LSM 交换了读和写的随机 I/O. 通过软件实现的技巧像布隆过滤器或者硬件(大文件 cache) 来优化读性能。

合并操作

当一定数量的 sstable 文件被创建,例如有 5 个 sstable, 每一个有 10 行,他们被合并为一个 50 行的文件(或者更少的行数). 这个过程一直持续着,当更多的有 10 行的 sstable 文件被创建,当产生 5 个文件,他们就会合并到 50 行的文件。最终会有 5 个 50 行的文件,这是会将这 5 个 50 行的文件合并成一个 250 行的文件。这个过程不停地创建更大的文件。

LSM_combine_op

上述的方案有一个问题,大量的文件被创建,最坏的情况下,所有的文件都要搜索

分层合并

levelDB 和 Cassandra 解决这个问题的方法是: 实现一个分层的,而不是根据文件大小执行合并操作。这个方法可以减少在最坏情况下需要检索的文件个数,同时也减少了一次合并操作的影响。

按层合并的策略相对于上述的按文件大小合并的策略有两个关键的不同:

  • 每一层可以维护指定的文件个数,同时保证不让 key 重叠。也就是将 key 分区到不同的文件。因此在一层查找一个 key, 只用查找一个文件。第一层是特殊情况,不满足上述条件,key 可以分布在多个文件中
  • 每次,文件只会合并到上一层的一个文件。当一层的文件满足特定个数时,一个文件会被选出并合并到上一层。这明显不同与另一种合并方式,一些相近大小的文件被合并为一个大文件

这些改变表明按层合并的策略减小了合并操作的影响,同时减少了空间需求。

总结

所以,LSM 是日志和传统的单文件索引(B+ tree, Hash Index) 的中立,他提供了一个机制来管理更小的独立的索引文件(sstable).

通过管理一组索引文件而不是单一的索引文件,LSM 将 B+ 树等结构昂贵的随机 I/O 变的更快,而代价就是读操作要处理大量的索引文件(sstable)而不是一个,另外还是一些 I/O 被合并操作消耗。

之前记得看到有些博客背景有可以用鼠标吸引的几何线条,很是喜欢,一直想加到自己博客里面。

theme 是 nexT, 在 themes/next/layout/_layout.swig 的 body 块中添加如下内容即可

1
<script type="text/javascript" color="0,0,0" opacity='0.5' zIndex="-1" count="99" src="//cdn.bootcss.com/canvas-nest.js/1.0.0/canvas-nest.min.js"></script>

当然也可以 npm install --save canvas-nest.js, 只是不太可控

redis 大体上可以分为两部分: 服务端和客户端。观察下服务端启动时都做了下哪些事。

Redis 全部由 C 语言编写,main 函数写在 server.c 中,启动主要分为以下几步

  • 初始化全局服务器状态:
  • 设置 commend table
  • 初始化哨兵模式
  • 修复持久化文件
  • 处理参数
  • initServer
  • Shared object
  • Shared integers
  • 新增循环事件
  • 分配数据库
  • 监听 TCP 端口
  • 初始化 LRU 键池
  • Server Cron
  • 打开 AOF 文件
  • 最大内存限制
  • Redis Server 启动
  • 从磁盘加载数据
  • 最后设置
  • 进入循环主事件

初始化全局服务器状态

如果 redis-server 命令启动时使用了 test 参数,那么就会先进行指定的测试。接下来调用了 initServerConfig 函数,这个函数初始化了一个类型为 redisServer 的全局变量 Server.
redisServer 这个结构包含了非常多的字段,按类别划分,可以分为以下类别。

  • General
  • Modules
  • NetWorking
  • RDB / AOF load information
  • Faster Pointers to offten lookup command
  • Fields used only for stats
  • Configuration
  • AOF / RDB persistence
  • Loggin
  • Replicaion
  • Synchronous replication
  • Limits
  • Blocked clients
  • Sort parameter
  • Zip structure config
  • time cache
  • Pubsub
  • Cluster
  • Scripting
  • Lazy free
  • Assert & bug reporting
  • System hardware info

initServerConfig 的主要工作是给可以在配置文件中(redis.conf)中配置的变量初始化一个默认值。比较常用的变量有服务器端口号,日志等级等。

设置 command table

initServerConfig 函数,会调用 populateCommandTable 函数来设置服务器的命令表,命令表的结构如下

1
2
3
4
5
6
7
struct redisCommand redisCommandTable[] = {
{"module", moduleCommand, -2, 0, NULL, 0, 0, 0, 0, 0},
{"get", getCommand, 2, "rF", 0, NULL, 1, 1, 1, 0, 0},
{"set", setCommand, -3, "wm", 0, NULL, 1, 1, 1, 0, 0},
{"set", setCommand, -3, "wm", 0, NULL, 1, 1, 1, 0, 0},
{"setnx", setnxCommand, 3, "wmF", 0, NULL, 1, 1, 1, 0, 0}
}

每一项分别代表

  • name: 命令的名称
  • function: 命令对应的函数句柄
  • arity: 命令的参数个数, 如果为 -N 表示大于等于 N
  • sflags: 命令标志, 标识命令的类型(read/write/admin)
  • flags: 位掩码,可由 Redis 根据 sflags 计算
  • get_keys_proc: 可选函数,当下面三个不能哪些参数是 key 时使用
  • first_key_index: 第一个是 key 的参数
  • last_key_index: 最后一个是 key 的参数
  • key_step: key 的步长,比如 MSET 的 key_step 是 2, 因为某些命令的参数是 key,val,key,val 这样的形式
  • microseconds: 执行命令需要的微秒数
  • calls: 该命令被调用总次数

设置好命令表后,redis-server 还会对一些常用的命令设置快速查找方式,直接赋予 server 的成员指针。

1
2
server.delCommand = lookupCommandByCstring("del");
server.multiCommand = lookupCommandByCString("multi")

初始化哨兵模式

变量初始化后,就会将启动命令的路径和参数保存起来,方便下次重启的时候使用。如果启动的服务是哨兵模式,那么就会调用 initSentinelConfiginitSentinel 初始化哨兵模式。关于哨兵模式会在另一篇博文里介绍。
initSentinelConfiginitSentinel 都在 sentinel.c 文件中。initSentinelConfig 函数负责初始化 sentinal 的端口号,以及解除服务器的保护模式。
initSentinel 函数负责将 command table 设置为只支持 sentinal 命令,以及初始化 sentinalState 数据格式。

修复持久化文件

启动模式如果是 redis-check-rdb/aof, 那么就会执行 redis_check_rdb_mainredis_check_aof_main 这两个函数来修复持久化文件,不过 redis_check_rdb_main 函数所做的事情在 Redis 启动过程中已经做了,所以这里不需要做,直接使用这个函数就可以。

处理参数

如果是简单的参数例如 -v--version, -h--help, 就会直接调用响应的方法,打印信息。如果是使用其他配置文件,则修改 server.exec_argv. 对于其他信息,会将其转换为字符串,然后添加进配置文件,例如 --port 6380 就会转换成 port 6380\n 加进配置文件。此时,redis 就会调用 loadServerConfig 函数来加载配置文件,这个过程会覆盖前面初始化默认配置文件的变量的值。

initServer

initServer 函数负责结束 server 变量初始化工作。首先设置处理信号(SIGHUPSIGPIPE 除外), 接着会创建一些双向列表用来跟踪客户端,从节点等.

1
2
3
4
5
6
7
8
9
10
11
server.current_client = NULL;
server.clients = listCreate();
server.client_index = raxNew();
server.client_to_close = listCreate();
server.slaves = listCreate();
server.monitors = listCreate();
server.client_pending_write = listCreate();
server.slaveseldb = -1;
server.unblocked_clients = listCreate();
server.ready_keys = listCreate();
server.client_waiting_acks = listCreate();

Shared object

createSharedObject 函数会创建一些 shared 对象保存在全局的 shared 变量中,对于不同的命令,可能会有相同的返回值。这样返回时就不需要新增对象,保存到内存中。
这样设计以启动 Redis 时多消耗一些时间为代价,换取运行的更小的延迟

1
2
3
4
5
shared.crlf = createObject(OBJ_STRING, sdsnew("\r\n"));
shared.ok = createObject(OBJ_STRING, sdsnew("+OK\r\n"));
shared.err = createObject(OBJ_STRING, sdsnew("-ERR\r\n"));
shared.emptybulk = createObject(OBJ_STRING, sdsnew("$0\r\n\r\n"));
shared.czero = createObject(OBJ_STRING, sdsnew(":0\r\n"));

shared integers

除了上述的一些返回值以外,createSharedObject 函数还会创建一些共享的整数对象。对 Redis 来说,有许多类型 (比如 lists 或者 sets) 都需要一些整数 (比如数量), 这是就可以复用这些已经创建好的整数对象,而不需要重新分配内存并创建。这同样是牺牲了启动时间来换取运行时间。

新增循环事件

initServer 函数调用 aeCreateEventLoop 函数 (ae.c 文件)来增加循环事件,并将结果返回给 server 的 el 成员。Redis 使用不同的函数来兼容各个平台,在 Linux 平台使用 epoll, 在 BSD 使用 kqueue, 都不是的话,最终会使用 select. Redis 轮询新的连接以及 I/O 事件,有新的事件到来时就会及时作出响应。

分配数据库

Redis 初始化需要的数据库,并将结果赋予 server 的 db 成员。

1
server.db = zmalloc(sizeof(redisDb) * server.dbnum);

监听 TCP 端口

listenToPort 用来初始化一些文件描述符,从而监听 server 配置的地址和端口。listenToPort 函数会根据参数中的地址判断要监听的是 IPv4 还是 IPv6, 对应的调用 anetTcpServer 或者 anetTcp6Server 函数,如果参数中未指明地址,最会强行绑定 0.0.0.0

初始化 LRU 键池

evictionPoolAlloc (evict.c 文件中) 用于初始化 LRU 的键池,Redis 的 key 过期策略是近似 LRU 算法.

1
2
3
4
5
6
7
8
9
10
11
12
13
void evictionPoolAlloc() {
struct evictionPoolEntry *ep;
int j;

ep = zmalloc(sizeof(*ep)*EVPOOL_SIZE);
for (j = 0; j < EVPOOL_SIZE; j++) {
ep[j].idle = 0;
ep[j].key = NULL;
ep[j].cached = sdsnewlen(NULL, EVPOOL_CACHED_SDS_SIZE);
ep[j].dbid = 0;
}
EvictionPoolLRU = rp;
}

server cron

initServer 函数接下会为数据库和 pub/sub 再生成一些列表和字段,重置一些状态,标记系统启动时间。在这之后,Redis 会执行 aeCreateTimeEvent (在 ae.c 文件中) 函数,用来新建一个循环执行 serverCron 函数的事件。serverCron 默认每 100 毫秒执行一次.

1
2
3
4
if (aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL) == AE_ERR) {
serverPanic("Can't create event loop timers.");
exit(1);
}

可以看到,代码中创建循环事件时指定每毫秒执行一次 serverCron 函数,这是为了使循环马上启动,但是 serverCron 函数的返回值又会被作为下次执行的时间间隔。默认为 1000/server.hz.
server.hz 随着客户端数量的增加而增加。

serverCron 函数做了许多定时执行的任务,包括 rehash, 后台持久化,AOF 重新与清理,清理过期 key, 交换虚拟内存,同步主从节点等等。总之能想到的 Redis 的定时任务几乎都在 serverCron 函数中处理。

打开 AOF 文件

1
2
3
4
5
6
7
8
9
if (server.aof_state == AOF_ON) {
server.aof_fd = open(server.aof_filename,
O_WRONLY | O_APPEND| O_CREAT, 0644);
if (server.aof_fd == -1) {
serverLog(LL_WARNING, "Can't open the append-only file:%s",
strerror(errno));
exit(1);
}
}

最大内存限制

对于 32 位系统,最大内存是 4GB, 如果用户没有明确指出 Redis 可使用的最大内存,那么这里默认限制为 3GB.

1
2
3
4
5
if (server.arch_bits == 32 && server.maxmemory == 0) {
serverLog(LL_WARNING, "WARNING: 32 bit instance detected but no memory set. Setting 3 GB maxmemory limit with 'noeviction' policy now.");
server.maxmemory = 3072L * (1024 * 1024);
server.maxmemory_policy = MAXMEMORY_NO_EVICTION;
}

Redis Server 启动

如果 Redis 被设置为后台运行,此时 Redis 会尝试写 pid 文件,默认路径是 /var/run/redis.pid. 这时,Redis 服务器已经启动。

从磁盘加载数据

如果存在 AOF 文件或者 dump 文件 (都有的话 AOF 文件的优先级高), loadDataFromDisk 函数负责将数据从磁盘加载到内存

最后的设置

每次进入循环事件时,要调用 beforeSleep 函数,主要做如下工作

  • 如果 server 时 cluster 中的一个节点,调用 clusterBeforeSleep 函数
  • 执行一个快速的周期
  • 如果有客户端在前一个循环事件被阻塞了,向所有的从节点发送 ACK 请求
  • 取消在同步备份过程中被阻塞的客户端的阻塞状态
  • 检查是否有因为阻塞命令而被阻塞的客户端,如果有,解除
  • 把 AOF 缓冲区写入磁盘
  • 线程释放 GIL

进入主循环事件

程序调用 aemain 函数,进入主循环,这是其他的一些循环事件也会分别被调用

1
2
3
4
5
6
7
8
void aemain(aeEventLoop *eventLoop) {
eventLoop -> stop = 0;
while (!eventLoop -> stop) {
if (eventLoop -> beforesleep != NULL)
eventLoop -> beforesleep(eventLoop);
aeProcessEvents(eventLoop, AE_ALL_EVENTS | AE_CALL_AFTER_SLEEP);
}
}

执行到这里,Redis server 已经准备好处理各种时间了。

0%