sync.Map源码阅读笔记

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

阅读全文

QUIC

背景与QUIC现状 最近因为毕设需要,详细研究了一下Google的QUIC。 我主要看的是Google官方团队的一篇2017年的论文与初版的QUIC规范文档。根绝Google自己的数据,Google有30%的对外流量已经在使用QUIC,因此根据Google的用户量,可以估计互联网上有……

阅读全文

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还会在……

阅读全文

你还在这样写快排?

排序永远是数据结构里永恒的话题,快排、归并排序这样基于分治思想排序的提出,极大的优化了插入排序、冒泡排序这样的O(N^2)排序算法。对于这样基于分治思想的排序,都可以写成多线程算法,但在C/C++下,很少有人把快排写成多线程,因为就pthread线程库来说其实现是与内核线程1:1……

阅读全文