IEEE754 换算和代码实现

问题

有没有想过为什么在很多语言里面简单的浮点数计算会丢失掉精度,这个精度又是如何丢失和保证的,在计算机里面怎么用有限的空间去保存无限的数

PHP

1
2
3
4
<?php
echo (float)(0.1+0.2).PHP_EOL;
var_dump(0.1+0.2);
var_dump((0.1 + 0.2 ) == 0.3);

结果

1
2
3
0.3
float(0.3)
bool(false)

JS

1
2
0.1+0.2
0.30000000000000004

抄一段维基百科对IEEE754上的解释

IEEE二进制浮点数算术标准(IEEE 754)是20世纪80年代以来最广泛使用的浮点数运算标准,为许多CPU与浮点运算器所采用。这个标准定义了表示浮点数的格式(包括负零-0)与反常值(denormal number),一些特殊数值((无穷(Inf)与非数值(NaN)),以及这些数值的“浮点数运算符”;它也指明了四种数值舍入规则和五种例外状况(包括例外发生的时机与处理方式)。

IEEE 754规定了四种表示浮点数值的方式:单精确度(32位)、双精确度(64位)、延伸单精确度(43比特以上,很少使用)与延伸双精确度(79比特以上,通常以80位实现)。只有32位模式有强制要求,其他都是选择性的。大部分编程语言都提供了IEEE浮点数格式与算术,但有些将其列为非必需的。例如,IEEE 754问世之前就有的C语言,现在包括了IEEE算术,但不算作强制要求(C语言的float通常是指IEEE单精确度,而double是指双精确度)。

定义

浮点类型 符号位 阶码 接码偏移值 尾数
单精度(float32) 1 8 127 23
双精度(float64) 1 11 1023 52

演算

其实网上有很多讲解IEEE754的文章,但是至少我没找到一个比较详细的计算过程。

  • 整数位除二取余
  • 小数位乘二取整

我们先换算 0.1转换为二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 1 0.1 X 2 = 0.2
2 0.2 X 2 = 0.4
3 0.4 x 2 = 0.8
4 0.8 x 2 = 1.6
5 0.6 x 2 = 1.2
6 0.2 x 2 = 0.4
7 0.4 x 2 = 0.8
8 0.8 x 2 = 1.6
9 0.6 x 2 = 1.2
10 0.2 x 2 = 0.4
11 0.4 x 2 = 0.8
12 0.8 x 2 = 1.6
...

可以看出进入了一个 0.4 0.8 1.6 1.2 的死循环

用科学计数法即保留一位有效整数位,往后取23位为位数,往后移动的位数是加上偏移量是阶码

  • 尾数 = 0001.10011001100110011001101

  • 阶码 = (-4 + 127) = 123 = 01111011 (2022年11月16日补充:阶码为保留1个整数位小数点左右移动的位数 公式为 (位数+127) )

  • 符号位 = 0

0.1用二进制表示为

符号位 + 阶码 + 尾数

0_01111011_10011001100110011001101

GO实现

float32转换为IEEE754

1
2
3
4
5
6
7
8

bits := math.Float32bits(0.1) //依靠库
binary := fmt.Sprintf("%.32b", bits)


fmt.Printf("binary: %s \n",binary)
fmt.Printf("IEEE754:%s_%s_%s \n", binary[0:1], binary[1:9], binary[9:])//按协议输出

输出

1
2
binary: 00111101110011001100110011001101 
IEEE754:0_01111011_10011001100110011001101

IEEE754 转换为float32

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func ieeeToFloat (bits uint32) {

bias := 127
binary := fmt.Sprintf("%.32b", bits)
sign := bits & (1<<31)

exponentRaw := int( bits >> 23 )

var exponent int

if sign != 0 {
exponent = exponentRaw - bias - 256 //减去高位符号位
} else {
exponent = exponentRaw - bias
}


var mantissa float64
for index, bit := range binary[9:32]{
if bit == 49 {
position := index + 1
bitValue := math.Pow(2, float64(position))
fractional := 1/bitValue
mantissa = mantissa + fractional
}
}

value := (1+mantissa) * math.Pow(2, float64(exponent))

fmt.Printf("exponent:%d\nmantissa:%.32f\nvalue:%.32f\nsign:%b\n",exponent,mantissa, value, sign)
}

输出

1
2
3
mantissa:0.60000002384185791015625000000000
value:0.10000000149011611938476562500000
sign:0

精度丢失

浮点数的精度丢失主要发生在两个地方

进制转换时的精度损失

我们可以看出在采取IEEE754存储浮点数时小数会出现无限循环的情况而我们定义的存储长度是有限的,这样就会产生进度误差,比如之前提到的

0.1 -> 0_01111011_10011001100110011001101 -> 0.10000000149011611938476562500000

0.2 -> 0_01111100_10011001100110011001101->0.20000000298023223876953125000000

0.10000000149011611938476562500000 + 0.20000000298023223876953125000000 = 0.300000004470348

运算过程中的精度丢失

0.5*0.75

0.5 = 0_01111110_00000000000000000000000
0.75 = 0_01111110_10000000000000000000000

尾数部分直接相乘 = 10000000000000000000000
指数相加-127 = 01111110 + 01111110 - 127 = 126+126-127 = 125
最终
0_01111101_10000000000000000000000

1
2
c,_ := strconv.ParseUint("00111110110000000000000000000000", 2, 64)
btod(ieeeToFloat(uint32(c)))

用上面的 ieeeToFloat 测试下可以得到 0.375

对于加减法需要先调整指数大小一致,再进行小数部分的相加。
列如 1.23x10^28 + 1.00x20^25
转换为 1.23x10^28 + 0.001x10^28
小数求和 1.231x10^28
如果浮点数只能精确表示 1.23 那么这个操作就会被舍弃丢失精度

参考

https://time.geekbang.org/column/article/439782

https://www.h-schmidt.net/FloatConverter/IEEE754.html

《GO语言底层原理剖析》

缓存更新军体拳

前言

在日常工作中说实话我没细想过缓存更新会有这么多的细节,一个原因是因为我本身所在平台的量级并发量被不大,二是对自己要求还是不够严谨。

会出现什么样的问题

缓存更新出现问题其实归根揭底是因为维护了 redis 和 mysql 两份数据,出现问题也是他们一致性的问题。常见的场景如下

场景一

一般DataStore更新或者删除会删掉cache而不是去更新它,但是在一些高并发场景这样做会让大量请求打到DataStore上,一种做法还是去更新这个缓存。

如图,当redis缓存过期重新从mysql取值得当前值cache=A1,同一时间运营修改了数据cache的值应该变为A2,脚本获得需要更新的值cache=A2。这样问题就来了 set cache = A1set cache = A2 的执行顺序会影响最终的结果。

场景二

先删除缓存再修改数据库,而后续的操作会把数据再装载的缓存中。这种操作本身就是有问题的。

场景三

先更新数据库,再删除缓存,而后续的操作会把数据再装载的缓存中。这种场景如图

session-1 session-2
update cache=A2 where cache=A1 缓存过期
transaction ing get cache=A1
commit
delete cache=A1
set cache=A1

依然会缓存脏数据,如果感觉例子中的update不是很好理解可以也可以想象成类似主从延时等其他情况。

常见解决方法

Cache Aside

这种方式是通用型的解决方案遵循

  • 读请求

先读chache 如果 miss 用 DataStore 数据回填chache。

  • 写请求

先删除/更新 数据库,再删除cache

主要要点是
 
 1. 读的顺序
 2. 删除cache而不是update(为了避免并发写产生脏数据

Read Through

Cache Aside 是调用方去解决缓存miss的情况, Read Through会依赖其它操作把需要的数据写入cache, 比如异步服务或者依靠运营手动更新缓存。

Write Through

有修改或者删除操作,先操作cache然后cache去更新DataStore,如果miss就直接操作DataStore

Write Behind Caching

page cache 更新策略,操作全部放入cache 按策略后台异步去写DataStore。(参考mysql rodolog 或者 redis AOF)

场景解决方案

场景一

这个场景是违反了Cache Aside 的只删不更新原则,是一个反范式的设计。目的是在高并发下不想缓存miss增加数据库的压力,毛老师在redis中的解决感觉很精巧所以特地记录下来了。

  1. 数据库同步到缓存的脚本用 setex 覆盖写,读缓存失效用 setnx 存在就不写。 setex > setnx, 用类似写优先级的方案解决了这种问题。
  2. Read Through, 把写缓存的操作交给运营手动去执行或者订阅binlog用脚本去更新,程序只用去关心读场景miss了返回空即可。

场景二

先删缓存再更新数据库这种方式尽量避免

场景三

session-1 session-2
update cache=A2 where cache=A1 缓存过期
transaction ing get cache=A1
commit
delete cache=A1
set cache=A1

延时双删,在第一次删除缓存后延时一定时间,再删一次。

session-1 session-2
update cache=A2 where cache=A1 缓存过期
transaction ing get cache=A1
commit
delete cache=A
set cache=A1
sleep(2s)
delete cache=A1

延时删除的时间根据业务场景决定是一种减少概率的规避做法

参考

  1. 极客时间毛老师第4期缓存策略分享
  2. https://coolshell.cn/articles/17416.html

《PHP 7底层设计与源码实现》

感受

读完这本书马上来写评论,在不翻看的情况下回忆它给我带来的好处有如下几点

  1. zval 结构体的巧妙
  2. opcode 与 opcache的关系
  3. PHP zend 运行机制 (词法解析->语法解析-> AST->opline->opcode->汇编)
  4. php array 5.6 与 7的区别
  5. GC
    很多C实现的宏表达因为功力有限没法一次看懂应该会再看一遍,总的来说值回书价

《富爸爸穷爸爸》

感受

醍醐灌顶甚至感到了羞愧,书中的穷爸爸的很多观念感觉都是在描述我自己,代入感太强了。这本书用穷富爸爸思维方式来产生强烈的对比,书中印象最深的一句话是“很多人一辈子都在为别人打工,帮别人赚钱”。它给我的启发就是合理的财务分配,平时求知若渴的经验积累,机会到来时能有足够能力识别和抓住

《西点军校送给男孩的最好礼物》

感受

西点军校是一所非常有名的学校,出了很多优秀的历史人物,全书描述了这些成功的历史人物身上具备的优秀品质在人生中都起到了什么样的·作用,它没有告诉我们学校教授了什么样的知识而是告诉了读者学校培养和看重的那些品质这是他们培养总统的标准。全是读起来比较有意思由一个个小故事来组成

《稻盛和夫-给年轻人的忠告》

感受

读了50页就读不下去了,一本读目录就知全文的书。作者并非稻盛和夫本人是一个叫德群的家伙写的感觉是蹭稻盛的热度。全文比较臃肿反复说明一个事“磨炼灵魂“,讲了很多正确的废话文中博士钓鱼的例子我甚至在以前看故事会的时候看过。书是送的感觉稻盛比较有名想拜读一番,没注意看出版社和作者也算失策的浪费了宝贵的时间。

redis底层结构与对象

数据结构

SDS

SDS(simple dynamic string 动态简单字符串 )

结构体

1
2
3
4
5
6
7
struct sdshdr { 
//buf占用长度
int len;
//buf可用空间长度
int free;
char buf[];
}

图解

优点

  1. o(1)获取字符串长度
    C语言在获取字符串长度时会遍历整个字符串,遍历到’\0’为止,SDS直接读free属性

C的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int cont_str(char *s)
{
int i = 0;
while (s[i++] != '\0');
return i;
}

int main()
{
char string[] = "test";
int c = cont_str(string);
printf("%d", c);
return 0;
}

=========
输出5(test+'\0'
  1. 杜绝缓冲区溢出
    标准C语言函数提供了一些没有边界检查的字符串处理函数 strcat()、strcpy()、 sprintf() 、vsprintf() 并不会检测溢出情况

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     #include <stdio.h>
    #include <string.h>

    int main()
    {
    char str[14];
    strcpy(str, "www.");
    strcat(str, "phpzjj.");
    strcat(str, "com");
    printf("%s",str);
    return 0;
    }

    ======
    www.phpzjj.com + '\0' 长度为15字符,我们申请14字符就会存在缓冲区溢出报错的情况

    SDS在遇见buf空间不够时会动态扩容(1M以下空间X2,1M以上按1M递增)
    代码实现

  2. 减少内存分配次数

    • 空间预分配
      sdscat()函数每次执行的时候会调用 sdsMakeRoomFor,空间够的时候就返回不够进行动态扩容并预留了充分的空间。
    • 惰性空间释放
      SDS直接修改 int len; int free; 2个属性不会真正的去释放
  3. 二进制安全
    C语言在处理字符串的时候会把'\0'作为结尾符,如果字符串中包含这个关键字会出现问题,SDS会主要读 int len 然后取固定长度。

  4. 兼容C字符串函数
    SDS维护了'\0'结尾符,兼容了C原生的类库

链表

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

typedef struct list {
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表节点数
unsigned long len;
//节点复制函数
void *(*dup)(void *ptr);
//节点释放函数
void (*free)(void *ptr);
//节点值对比函数
int (*match)(void *ptr, void *key);
}

typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode * next;
//节点值
void *value
}

图解

优点

  1. 双端:获取某个节点的前后节点时间复杂度为o(1)
  2. 无环:头尾节点都指向null
  3. 带表头和表尾指针:通过list结构体可以o(1)找到表头和表尾
  4. 带表头指针和表尾指针获取链表头尾复杂度o(1)
  5. 带链表长度技术器获取链表节点数量复杂度o(1)
  6. 多态:void指针保存节点值,dup,free,match设置指定类型函数,可以保存不同类型的值

字典

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
/*
* 字典
*/

typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;


/*
* 哈希表
*
* 每个字典都使用两个哈希表,
* 从而实现渐进式 rehash 。
*/
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;

/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;

图解

dict

写入

1
2
3
4
5
// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)

// 计算新哈希表的哈希值,以及节点插入的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;

键冲突

在hash键计算冲突的情况下,会以链表的方式把冲突数据写入链表头部(单项链表,放尾部o(n),头部则是o(1)redis的优化就很细) dictEntry

rehash

装载因子: load_factor = ht[0].used/ht[0].size

rehash策略: 当load_factor超过合理范围区间哈希表会进行扩张(used*2)或者收缩 (used/2)

load_factor 大于等于1 大于等于5
BGSAVE/BGREWRITEAOF 等待结束 不用等待结束

渐进式rehash

  1. ht[1]分配空间,同时持有ht[0]和ht[1]两个哈希表
  2. dict结构中的rehashidx设置为0表示开始渐进加载
  3. 期间每次crud都会进行一次对应操作一次顺带迁移,并且rehashidx会加一
  4. 迁移完成后rehashidx设置为-1表示完成

crud操作时会同时查找2个哈希表,期间新增加的键值对会保持到ht[1]。

跳跃表

跳跃表性能媲美平衡树并且实现比它简单,平均O(logN),最坏O(N),是有序集合的底层实现之一。跳表的实现是链表加上多级索引的结构

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 跳跃表
*/
typedef struct zskiplist {

// 表头节点和表尾节点
struct zskiplistNode *header, *tail;

// 表中节点的数量
unsigned long length;

// 表中层数最大的节点的层数
int level;

} zskiplist;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* ZSETs use a specialized version of Skiplists */
/*
* 跳跃表节点
*/
typedef struct zskiplistNode {

// 成员对象
robj *obj;

// 分值
double score;

// 后退指针
struct zskiplistNode *backward;

// 层
struct zskiplistLevel {

// 前进指针
struct zskiplistNode *forward;

// 跨度
unsigned int span;

} level[];

} zskiplistNode;

实现思路

最直观的是下面这种表现方式,原始链表上衍生出了多级索引加快定位数据的速度。

极客时间插图

《redis设计与实现》中插图是这样表示的

redis设计与实现-跳表

两者从直观感受上来说还是有一定的差别的,我尝试用图形来表示但是发现它是一种错误的理解表示形式

错误的理解

他们的区别是极客时间中跳表的表示是一类更为宏观的理解,既跳表是链表+多级索引
redis书上更偏向于代码实现,既生成当前zskiplistNode 用代码逻辑来达到宏观上的链表+多级索引,最后发现了一种比较贴合两者之前的画法。

每插入一个数据,redis跳表的实现会抛硬币即50%的几率来决定层数(最大32层)这样可以解决跳表数据过于集中退化成链表的情况,一个数据会包含多层,每层指针会指向本层的下一个数据

多个zskiplistNode可以组成一个跳表,zskiplist更好的提供了定位头尾节点的能力并且在o(1)复杂度获取相关的长度和层数信息

整数集合

结构体

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {

// 编码方式
uint32_t encoding;

// 集合包含的元素数量
uint32_t length;

// 保存元素的数组
int8_t contents[];

} intset;

整数集合会根据encoding值来确定contents[]中的数据类型,它包含int16_t int32_t int64_t

升级

整数集合是可以提供动态向上升级的,但是不能降级这要做的好处能有效节省内存空间,做到有需要再升级。

压缩列表

列表键和哈希键的底层实现之一,当列表键只包含少量列表项,并且列表项是小整数值或者比较短的字符串,就会采用压缩列表。压缩列表是一种为了节约内存而设计的顺序型数据结构。

zlbytes|zltail|zllen|entry1| entry2 |…| entryN | zlend
:-:|

属性|类型|长度|用途|
:-:|:-:|:-:|:-:|:-:
zlbytes|uint32_t|4字节|整个压缩列表占用内存字节数
zltail|uint32_t|4字节|压缩列表尾节点到起始地址多少字节
zllen|uint16_t|2字节|包含节点数,小于65535是真实数据,等于需要遍历技术得出
entryx|列表节点|不定|压缩列表的各个节点
zlend|uint8_t|1字节|特殊值0XFF标识末端

压缩列表节点

previous_entry_length encoding content
  • previous_entry_length

    小于254为1字节,大于等于254会扩展为5字节(5字节高位表示254,后4字节表示实际长度)

    高位表示大于254

    实际大小

previous_entry_length encoding content
0X05
previous_entry_length encoding content
0XFE00002766
1
通过当前节点  p- previous_entry_length 可以得到上一个节点
  • encoding

    记录了content的长度用约定好的二进制结构表示

  • content

    节点数据

连锁更新

压缩列表会存在连锁更新的情况O(n)的时间复杂度,但是它所储存的数据量级不会太大这种情况是设计内可以接受的

embstr

专门用于保存短字符串的一种优化编码方式REDIS_ENCODING_RAW 会调用两次内存分配函数分别创建redisObject和结构sds, embstr通过一次内存分配函数给到redisObject和sds的连续空间。

优点

  • REDIS_ENCODING_RAW 内存分配两次降为一次
  • 释放同理降为一次
  • 放在连续内存中更友好的利用缓存优势

注:1.redis会把long double也当成字符串保存哎需要的时候转回long double过后再变成字符串保存起来
2. embstr是只读的做修改操作会转换为SDS

对象

每当我们新建一个键值对时至少会建立两个对象,一个是键值对的键一个是值。对象的值不会固定是某一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct redisObject {

// 类型
unsigned type:4;

// 编码
unsigned encoding:4;

// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

// 引用计数
int refcount;

// 指向实际值的指针
void *ptr;

} robj;

对象编码

1
2
3
4
5
6
7
8
9
#define REDIS_ENCODING_RAW 0     /* Raw representation  简单字符串sds*/ 
#define REDIS_ENCODING_INT 1 /* Encoded as integer */
#define REDIS_ENCODING_HT 2 /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6 /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8 /* EMBSTR 简单动态字符串*/

对象对应关系

类型 编码 对象
string REDIS_ENCODING_INT 整数字符串对象
string REDIS_ENCODING_EMBSTR EMBSTR简单动态字符串
string REDIS_ENCODING_RAW 简单字符串SDS
list REDIS_ENCODING_ZIPLIST 压缩列表
list REDIS_ENCODING_LINKEDLIST 双端链表
hash REDIS_ENCODING_ZIPLIST 压缩列表
hash REDIS_ENCODING_HT 字典
set REDIS_ENCODING_INTSET 整数集合
set REDIS_ENCODING_HT 字典
zset REDIS_ENCODING_ZIPLIST 压缩列表
zset REDIS_ENCODING_SKIPLIST 跳表

字符串对象

REDIS_ENCODING_INT

long int

REDIS_ENCODING_RAW SDS

string leng > 32

REDIS_ENCODING_EMBSTR

string leng <= 32

列表对象

REDIS_ENCODING_ZIPLIST

  • 列表所有对象保存的字符串元素长度都小于64字节
  • 列表对象保存元素量小于512个

REDIS_ENCODING_LINKEDLIST

不满足上述2个条件会转换

哈希对象

REDIS_ENCODING_ZIPLIST

  • 哈希对象保存所有键值对键和值的字符串长度都小于64字节
  • 哈希对象数量小于512个

哈希对象在压缩列表中的存储是紧凑的先键后值

zlbytes zltail zllen key vlen key1 vlen1 zlend

REDIS_ENCODING_HT

不满足上述2个条件会转换

集合对象

REDIS_ENCODING_INTSET

  • 保留所有对象都是整数
  • 集合元素不超过512个

REDIS_ENCODING_HT

  • 不满足上述2个条件会转换

如果我没理解错,集合在使用字典作为底层实现的时候是没有值的,只会用到键

有序集合对象

REDIS_ENCODING_ZIPLIST

每个集合元素两个紧挨一起进行保存,第一个节点保存元素成员第二个元素保存元素分值,按分值从小到大进行排序。

  • 有序集合保存元素小于 128个
  • 所有元素成员长度都小于 64字节

REDIS_ENCODING_SKIPLIST

不满足上面2个要求会转换成跳表

有序集合使用跳表时会用到zset对象,同时用到了map和zskiplist。他们需要交叉服用功率大增,map能保证单个查询O(1)的查询效率,zskiplist能保证区间查询O(logN)的效率。指针指向同一份内存地址也不会有空间浪费的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 有序集合
*/
typedef struct zset {

// 字典,键为成员,值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;

// 跳跃表,按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;

} zset;

注: redis会共享整数对象

参考文档

极客时间-跳表
segmentfault-跳表

《Redis设计与实现》

感受

图文并茂清晰易懂没有多余的废话,全是知识点和考点,部分地方需要额外查下质料。黄老师还在GitHub上提供了中文注释的C项目。发现一个大佬写好Makefile的项目直接CLion调断点效率翻倍方便理解,https://github.com/htw0056/redis-3.0-annotated-cmake-in-clion。建议做一个详细的笔记记录下书中所讲的知识点隔段时间翻翻会有不一样的感受。

笔记

redis底层结构与对象

《数据库系统内幕》

感受

一本讲底层原理的书,从磁盘型和内存型的底层数据结构介绍优劣势分析和选择到具体的案例,再到后面的分布式一致性算法都涉及。书不算厚里面的知识点比较密集,读它本身不会花太多的时间但是结合着相关质料真的一张一张读懂还是需要花一些功夫的。

《关键对话》

这是我读过众多情绪管理和沟通技巧中最有用的, 它分析了我们遇见问题时候的心里和生理特征,并且总结归纳出了一套实用的沟通模型。遇见关键对话时我们很容易陷入傻瓜选择(打或者逃),它从人类进化学的角度解释了这种原因并且分析出了一系列的行为表现和特征,主张培养双路对话处理能力并且列举出来了一系列让对话可以达到我们目标的实施路数。这套沟通模型我也花了时间记了下来用在了平时生活中,感触颇深。

关键对话

文档链接: https://share.mubu.com/doc/4PX1d5k11uQ 密码: k9s4

请我喝杯咖啡吧~