leveldb注释8–snapshot机制

snapshot,也就是快照机制的作用,就是使得读操作不受写操作影响。其巧妙的使用了SequenceNumber来实现这一机制。

上一节中,我们知道,SequenceNumber使得对写入的任何key在内部存储时都会附加一个递增的SequenceNumber。而在leveldb内部,一次snapshot也对应一个全局唯一的SequenceNumber。因此,在调用GetSnapshot获取snapshot时,leveldb所做的仅仅是生成一个SequenceNumber。db内部使用双向循环链表保存先后生成的snapshot。 继续阅读

发表在 leveldb | 标签为 , , , | 4 条评论

leveldb注释7–key与value

作为一个kv的系统,key的存储至关重要。在leveldb中,主要涉及到如下几个key,user_key、InternalKey与LookupKey(memtable_key)。
其关系构成如下图。user_key就是用户输入的key,而InternalKey在user_key的基础上封装了sequence_num+type。sequence_num是一个全局递增的序列号,每一次Put操作都会递增。这样,不同时间的写入操作会得到不一样的sequence_num。前面章节中提到的sstable单条record中的key,其内部其实就是一个InternalKey。sequence_num主要跟snapshot机制与version机制相关,对压缩会产生一定影响。这些我们在后续章节分析。根据type字段,可以获知本次写入操作是写还是删除(也就是说删除是一种特殊的写)。而LookupKey/memtable_key用于在memtable中,多了一个长度字段。代码主要在dbformat.cc/.h中。 继续阅读

发表在 leveldb | 标签为 , , , | 留下评论

leveldb注释6–log文件

在leveldb中,除了sstable文件格式,还有log文件格式。该文件格式用于存储写操作的日志与manifest文件(不同的文件名)。前者用于异常回滚。后者用于记录sstable文件的元数据。整体架构中提到过,leveldb在将记录写入内存中的memtable之前,会先写入log文件,memtable会延后持久化。在这个过程中进程可能down掉。有了log写操作文件后,即使系统发生故障,levelDB也可以根据log写操作日志文件恢复内存的memtable内容,不会造成丢失数据。而manifest文件用于记录所有的sstable文件的元数据,比如sstable文件的编号,key范围。 继续阅读

发表在 leveldb | 标签为 , , , | 留下评论

leveldb注释5–sstable文件

本节主要介绍sstable文件的格式及单个sstable文件的get/put。sstable文件全称是sorted string table,是一个有序且带索引的文件。

从前面的分析可知,level 0级的sstable文件是由内存中的immunable memtable经过minor compact形成的(也就是直接dump),而level>0级的文件是由level-1级别的文件经过major compact形成的。关于compact过程,我们在后续章节分析。这里着重于分析单个sstable文件的相关接口,代码在table/目录。 继续阅读

发表在 leveldb | 标签为 , , , | 留下评论

leveldb注释4–平台相关

0 编译
leveldb没有使用autoconf/automake来生成Makefile,而是自己编写了Makefile以及平台检测脚本。Makefile中会先调用检测脚本build_detect_platform,并将设置的环境变量保存在build_config.mk文件里。随后Makefile会include build_config.mk文件以进行编译,相关Makefile代码如下,其中的PLATFORM_CCFLAGS等参数将在build_detect_platform中设置并输出给build_config.mk文件: 继续阅读

发表在 leveldb | 标签为 , , , , | 留下评论

leveldb注释3–基础类

这一节主要分析下util目录下的代码。这部分代码相对独立,功能明确,很容易看明白。可先尝试理解这部分代码,以为进一步理解leveldb代码打下基础。

1 内存管理(arena.cc/.h) 继续阅读

发表在 leveldb | 标签为 , , , , , , , , , , | 留下评论

leveldb注释1–整体介绍

概括的说,leveldb是一个kv型的存储库。主要特点如下:
> 单机嵌入式接口
> 持久化存储
> KV系统,提供读写删除操作(kv都是字节序列)
> 支持快照功能,使得读操作不受写操作影响
> 磁盘上的数据是有序的,且分级存储,同时在文件保存相应的索引以加速读操作
> 删除是一种特殊类型的写操作
> 提供压缩操作以减少存储空间
> 写入,延迟写入,通过log保证数据不丢失

整体架构如下图所示: 继续阅读

发表在 leveldb | 标签为 , , | 一条评论

leveldb注释0–start

因为工作需要,曾对leveldb进行过测试与实际使用,而对leveldb的源代码进行学习,则纯粹是出于一个码农对美好世界进行探究的好奇。接下来将尽可能从源代码上给出leveldb代码的详尽注释,这里先列出自己在阅读前后的主要参考。 继续阅读

发表在 leveldb | 标签为 , , | 留下评论

网页spam相关论文了解

最近对网页spam有兴趣,找了些论文看看,部分还没看完,做个小结吧,后续再慢慢看,慢慢补充了。
主要内容都是参考里的论文里的。

1 spam基础
那些误导搜索引擎排名的行为或者从搜索引擎中获得不应有的利益的行为都可以称为spam,具体是否为spam取决于搜索引擎的判断标准。

简单来说,那些搜索引擎明文允许进行的或者即使搜索引擎不存在但仍存在的“优化”行为可以认为不是spam。比如一些针对特定client、终端的优化行为不能认为是spam。再比如垃圾网站里贴出的链接,这些链接不应该作为spam,因为这些链接的存在超出了链接目的地的owner的控制,惩罚的应该是垃圾网站本身而不是它指向的链接。 继续阅读

发表在 搜索引擎 | 标签为 , , | 评论关闭

redis源代码分析25–VM(下)

这一节介绍下redis中的多线程机制。

先看看多线程换出的机制。

serverCron函数中调用 vmSwapOneObjectThreaded开始多线程方式换出value,vmSwapOneObjectThreaded会调用 vmSwapOneObject(参看上一节的解释),而vmSwapOneObject最终会调用vmSwapObjectThreaded。 继续阅读

发表在 redis | 留下评论