分类 源码阅读 中的文章

sync.Map源码阅读笔记

写在前面的碎碎念 Go的原生map不是并发安全的,多个协程并发读写map被竞态检测到时会直接panic掉整个进程,recover都不能cover住…因此在写代码时,只要关于并发读写map都要谨记并发安全,印象中之前组里有出过这样的bug,凌晨左右发现服务莫名其妙挂掉。……

阅读全文

Redis源码剖析——dict(二)

下面要探究的核心问题是dict中为何要用两个哈希表,这两个哈希表给Redis的dict带来了什么好处?我们从dict最开始的创建、插入、迭代器、以及删除等全过程来剖析 (ps: 下面有时候会把dict和字典混说) 哈希函数 我们不妨先看看Redis中哈希用的哈希函数 1555486330514822.png 这是比较常用的Mur……

阅读全文

Redis源码剖析——dict(一)

dict结构根本上是为了提供高效的搜索映射,因此红黑树、AVL树、哈希表都可以用来实现字典结构,不过树形结构怎么都不可能达到常数级别的时间复杂度,因此用树形结构来实现dict已经比较少见了,不过C++STL库中map的实现仍然是红黑树,红黑树也自有优点,在实现字典结构的同时还可以……

阅读全文

Redis源码剖析——intset

intset是Redis源码里一个比较基础的组件,和非常多的部分有耦合,因此也就不单独谈其所关联的部分了。总的来说intset实现了这样一个东西:一个多编码的顺序整型数据存储结构。(以下代码位于intset.c与intset.h) 其基本结构非常简单 1560263505996778.png encoding字段支持的整型……

阅读全文

Redis源码剖析——HyperLogLog

HyperLogLog算法核心原理 写在前面… 阅读Redis的源码你会发现,里面有个略微奇怪的结构,叫做HyperLogLog。大多数人第一反应这个可能是个日志相关的东西?实际上是Redis里相对复杂的一个非传统算法,其可被用于海量数据的统计。 上次写这篇文章是两年前了……

阅读全文

Redis源码剖析——跳表(三)

Redis跳表中每个节点的span实际上是个非常巧妙的设计,但是关于span的部分阅读起来不是很容易,因为这种在数据结构上做的创新行为往往不能第一眼就理解。在跳表的插入删除操作,可以看到有很多部分都在对span进行调整,span是一个重要且不能绕过的东西,那么span到底是用来干……

阅读全文

Redis源码剖析——跳表(二)

下面进入跳表的具体实现,以下代码位于z_set.c 先忽略插入与删除中对span相关的调整操作,下一篇会专门对span进行解释后再继续跳表的后续剖析 以下是两个基本的创建函数 1557066756673388.png 创建一个跳表节点,不多说 1557066868184478.png 创建整个跳表。设置跳表的初始最大层高为1,长度为0。创建一个score为0,sds……

阅读全文

Redis源码剖析——跳表(一)

前言 从跳表(SkipList)开始,离Redis用户层面就比较近了,Redis用户层面的五个基本数据类型中有序集合zset的实现主要基于三个部分:跳表、dict、ziplist。三者搭配的很完美,其中dict我们已经研究过,至于ziplist则是压缩列表,关于ziplist还会在……

阅读全文

Redis源码剖析——SDS库(二)

上一篇我们熟悉了SDS字符串的基本结构以及一些基本方法,我们接下来继续深入看一些方法比较重要的方法,别忘了我们的目的是为了找出SDS到底比glibc的字符串好在哪儿。 具体实现 以下代码位于sds.c 1555073913731569.png 首先说明一下这个工具函数,该函数会根据参数string_size来判断该strin……

阅读全文

Redis源码剖析——SDS库(一)

SDS是一个C的动态字符串库,即1554909660672013.png redis抛弃了glibc的字符串库,自己实现了一个更好的字符串库,为什么要造这个轮子,SDS比起glibc的一套更好在哪儿?这就是我们要探究的核心问题。(以下代码位于sds.h) SDS字符串的类型很简单 1554909827468057.png 当……

阅读全文