redis 底层数据结构 list的底层数据结构,redis3.2之后,使用quicklist代替ziplist redis7.0开始不再使用ziplist,使用listpack代替 对于有序集合，两种实现方式:压缩列表ziplist(listpack)、跳表skiplist. redis.conf配置中有关于zset到底使用那个数据结构两个配置项, 1) "zset-max-ziplist-value" 2) "64" 3) "zset-max-ziplist-entries" 4) "128" 也就是收当zset集合中元素个数不超过128且所有元素值大小不超过64时，使用压缩列表，否则使用跳表。同理，hash也有这两个配置项。 同样对于hash类型，也存在相似的配置 "hash-max-listpack-value" "64" "hash-max-listpack-entries" "512" 当set的value为整数且个数不多时set-max-intset-entries使用intset。 sds sds object encoding key 命令用于查看key的底层存储的数据结构。 type key返回的是基本类型。 redis 多有的key类型以及value类型/复杂结构的value元素也都是字符串。redis字符串底层实现为sds。 sds优点: O(1)时间获取字符串长度。 二进制安全,允许字符串中出现’\0’这个特殊字符，sds可以存储图像,音频等类型的编码。由于获取长度不会以’\0’为结尾，所以是二进制安全的。 相比于C字符串，减少了动态扩展中的内存再分配次数。在redis中string变化的场景比较多，所以这一特性很重要。 兼容C函数， sds->buf 本质是C字符数组 hashtable 字典 linkedlist 双向链表 ziplist 在linkedlist基础上,使用连续内存，对不同的数据类型采用不同的encoding表示。本质是可以存储整数或字符串的数组或者是说具有连续内存分配的双向链表。是为了节省内存而设计的顺序型数据结构。 zltail+entry-pre_len时为了实现逆序遍历 head 中的zlen虽然数值上只能达到2^16-1=65535,但是实际entry可以大于这个数，当zlen等于65535时，需要遍历压缩列表获取entry数量 entry的pre_len 是否扩展取决于上一个节点长度是否大于等于254(0xff位结束标志,0xfe位pre_len扩展标志) entry的encoding通过前两位来区分content是怎样的字符/整数 flag=0xff,标记结束。已经有标记entry数量的zllen,为什么还需要结束标记位?? 由上述结构可知,entry的encoding字段大小会因为增删发生改变，最坏的情况下会引起一系列连续的改动，称为连锁更新。 listpack ziplist在entry头encoding设计引起的连锁更新在高并发写操作中会降低redis性能，设计了更加紧凑的listpack。redis7.0开始，不再使用ziplist. 与ziplist的不同点: head中删除tail偏移量 entry中不再记录前一节点长度，改为记录当前节点长度，entry不会再发生连锁更新的问题 encoding规则和大小与ziplist不同 quicklist redis3.2开始,list的底层实现使用quicklist代替ziplist(listpack)。我们知道ziplist(listpack)在双端链表的基础上使用连续内存和压缩节点信息的方式达到节省内存的目的, 但是其缺点也很明显，多余较长的ziplist(listpack)，增删时存在较多的内存拷贝操作.ziplist同时由于entry中会记录前一节点长度的原因也会引起连锁更新，在元素较多时性能由影响。而quicklist 是结合了链表的方便插入删除特点和ziplist(listpack)节省内存的特点，进行的折中，将ziplist(listpack)作为quicklist节点，采用双端链表的形式串起来。 quicklist的节点定义如下: typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *entry; size_t sz; /* entry size in bytes */ unsigned int count : 16; /* count of items in listpack */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* PLAIN==1 or PACKED==2 */ unsigned int recompress : 1; /* was this node previous compressed?

Redis 入门 概述 Remote Dictionary Server 数据类型：字符串 链表 集合 有序集合 哈希表。BitMap、 Hyperlog Log(大数据量的去重)、Geospatial(地理位置相关) NoSQL Not only SQL/non relational:非关系型数据库。目的解决多重数据类型和高并发问题。 KV数据库 redis 列存储数据库 关系型数据库采用行存储在存储上是连续空间，不适用于海量数据。按列存储可以实现分布式存储，适合海量数据，如HBase. 文档型数据库 NoSQL与关系型数据库的结合。如：MongoDb 图像数据库 存储一个节点关系的数据库， 如：Neo4j 用途 数据缓存 实时同步数据：要求缓存和DB中的数据保持一致 阶段性同步数据: 没有必要与DB中的数据实时保持一致。 可以为缓存数据添加缓存时长 特点 性能极高 11w/s read; 8w/s write。 基于内存 基于C开发 源码十分精细 简单稳定 源码很少 持久化 保证数据的安全性。 RDB、AOF两种方式 高可用集群 保证系统的安全性 丰富的数据类型 强大功能 数据淘汰、发布订阅、事务、Lua扩展。 客户端语言广泛 提供了简单的TCP通信协议，方便各种变成语言开发客户端。 支持ACL权限控制 redis6之后支持ACL(Access Control List)，可以为不同用户定制不同的权限。 支持多线程IO模型 6.0之后支持多线程IO IO模型 单线程模型 不同的连接会注册多种时间到事件处理器， 当socket上有事件就绪时，任务被塞到任务队列， 等待主线程从任务队列中取出执行。 这些事件除了socket建立和关闭连接这些需要操作文件的请求外， 一旦连接建立大多数是一些redis命令的执行， 而这些命令是直接操纵内存，所以执行速度很快。 同时避免了多线程带来的指令执行顺序，数据竞争的问题。 混合线程模型

1. 排序算法 1.1 冒泡排序 冒泡排序意思就是每一次遍历，将最大/的最小元素移动到末尾. 显然对于长度为len的输入而言,最多需要遍历len -1 次. 时间复杂度O(n^2) 空间复杂度O(1) template<typename T> void bubble_sort(T arr[], size_t len){ bool swap = true; // 若是当前的遍历没有发生交换说明已经是正序的,不需要继续下去 for(size_t loop_num = 0; loop_num < len -1 && swap; ++loop_num) { swap = false; for(size_t index = 0; index < len -1 - loop_num; ++index) { if(arr[index] > arr[index+1]) { const T tmp = arr[index]; arr[index] = arr[index+1]; arr[index+1] = tmp; swap = true; } } } } 1.

1. 使用栈实现队列 // front,back两个两个栈实现一个队列的功能 // 所有的入队列操作在front中进行 // 所有的出队列操作在back中进行 // 为了从先入后出逻辑变更为陷入先出,front栈底元素就要变成栈顶元素,故出队列的时候,优先出back的栈顶元素, // 只有当back栈顶元素出完时才从front那里取数据过来 if(back.empty()){ while(!front.empty()){ back.push(front.top()); front.pop(); } } if(back.empty()) return -1; auto ret = back.top(); back.pop(); return ret; 2. 包含min函数的栈 // 记录栈中的最小元素 // 需要记录当前栈顶的最小元素,当栈顶元素弹出时，最小元素也弹出 class MinStack { public: /** initialize your data structure here. */ MinStack() { } void push(int x) { element_.push(x); if(min_.empty()){ min_.push(x); }else{ min_.push(std::min(min_.top(), x)); } } void pop() { element_.pop(); min_.pop(); } int top() { return element_.

1 常用快捷键 1.1 命令跳转 crtl + a (ahead) 跳转到命令首部 ctrl + e (end) 跳转到命令尾部 ctrl + p (previous) 上一条命令 ctrl + n (next) 下一条命令 ctrl + 左 (向左移动一个单词) ctrl + 右 (向右移动一个单词) 1.2 删除 ctrl + k 删除到行尾 ctrl + u 删除到行首 ctrl + y 撤销，实际上为粘贴操作， 上述的删除实际有复制操作的副作用 ctrl + r 快速搜索 2. 交互方式 交互式:1问1答 非交互式:脚本方式 2.1 交互式bash 全局配置 /etc/bashrc /etc/profile 一般不修改 个人配置 ~/.bashrc 仍然会索引全局配置。 个人配置的查找顺序： .bash_profile .bash_login .profile, 只生效第一个查找到的目标 指定Login shell useradd -s ${shell}