redis与mysql差缺补漏-面试版持续更新

目录1. 压缩列表介绍2. 跳表介绍2.1 核心原因范围查询的实现难度决定性因素2.2 实现复杂度Lock-Free无锁与易维护性3. Redis 数据同步解释一下4. 布隆过滤器原理1. 压缩列表介绍答本质是使用一段连续的内存区域对数据进行编码减少开销zlbyte整个压缩列表的占用字节数- zltail最尾部的数据距离开头的偏移量- zllen数据实际占用长度- entryX具体数据节点- zlend尾部结束标识使用如果有序集合的元素个数小于 128 个并且每个元素的值小于 64 字节时Redis 会使用压缩列表作为底层数据结构。hash 的元素个数则为 512 个。追问现在压缩列表被 listpack 替代原因是答原来的压缩列表存储的格式为previous_entry_len前一个元素的长度- encoding元素类型- content实际内容当增加、删除、修改都会导致 previous_entry_len 的改动导致形成多米诺骨牌效应。listpack 目前的存储格式为total-byte整个 listpack 占用字节- num-element元素总数- 实际节点 - end-byte实际结束节点节点设计为 encoding类型- data数据- len长度避免元素修改对别的元素产生影响。2. 跳表介绍答跳表如图当要查找节点 5 时候会直接来到 level 2 定位从 1 找到 5 只查询了两次整体速度为 log n。实现过程当一个节点Redis 会随机生成 0-1 之间的小数若小于 0.25 则会升阶并且重复直至大于 0.25 为止。如节点 1, 2, 3, 4, 5, 6这时候对 1第一次生成为 0.4 则 1 就在 level 0 中对 2 第一次为 0.1第二次为 0.2第三次为 0.9 则他为 level 2 中。本质有序链表但是随机层高。追问为什么不使用红黑树呢要使用跳表答1. 核心原因范围查询的实现难度决定性因素这是 Redis 选择跳表最重要的原因。对于有序集合ZSet而言范围查询如ZRANGE、ZRANK、ZREVRANGE是最高频的操作之一。在跳表中一旦你通过索引找到了范围起始的节点你只需要顺着最底层的链表Level 0向后遍历即可。因为底层链表本身就是一个有序的、包含所有元素的序列。时间复杂度为O(log N M)M 为返回的元素数量。在红黑树中虽然红黑树也是有序的但它的结构是树形的。想要输出一个范围内的所有元素你必须进行中序遍历In-order Traversal。这需要维护一个栈或父节点指针来记录回溯路径代码实现复杂得多且缓存局部性Cache Locality远不如链表连续遍历好。2. 实现复杂度Lock-Free无锁与易维护性跳表跳表的插入和删除逻辑非常直观只需要修改相邻节点的指针。即使需要调整层高随机生成也是局部修改。整个数据结构仅需约 400 行 C 语言代码即可实现所有功能。红黑树红黑树的插入和删除涉及复杂的旋转Rotate和颜色翻转Color Flip操作需要处理多种边界情况插入时的 3 种情况删除时的 6 种情况。代码量通常是跳表的数倍约 1500-2000 行。重要引申Redis 是单线程指主事件循环模型但跳表简单的结构使得更容易在将来进行无锁Lock-Free并发改造且当前代码便于维护和 Debug。antirez 曾直言维护红黑树在长时间运行中极易出现难以复现的指针问题。追问为什么不使用 B 树呢答B 树适合磁盘 IO场景因为它将数据聚合在页Page中降低磁盘寻道次数。Redis 是纯内存数据库数据都在内存中不存在磁盘寻道开销。使用 B 树在内存中反而会因为复杂的页管理而浪费内存且增加代码复杂度。跳表在内存中的表现更优。追问跳表为什么要随机层高而不是连续有规律的层高呢答使用连续层高如严格 1/2 比例假设你维护一个完美的跳表第 1 层有 N/2 个节点第 2 层有 N/4 个节点……当你插入一个新节点时为了维持这个严格的“1/2”比例你可能需要把大量后续节点从底层提升到上一层或者调整已有的索引关系。这会导致连锁反应最坏情况下单次插入的时间复杂度会退化为O(N)。这就像维护一个完全平衡的二叉搜索树如 AVL 树一样插入后必须进行复杂的旋转操作。使用随机层高跳表通过抛硬币随机数决定新节点的层高完全不依赖现有节点的数量和分布。插入新节点时只需要ol li p在底层链表中插入节点。/p /li li p根据随机值决定这个节点出现在哪几层索引中。/p /li li p将新节点“链入”这几层索引的对应位置只修改前后指针。br / 整个过程是strong纯局部操作/strong时间复杂度稳定在 strongO(log N)/strong 的期望值且strong无需移动或调整任何其他节点的层高/strong。/p /li /ol /li3. Redis 数据同步解释一下答前置了解AOF 以及 RDB 快照。AOF 日志是增量每次记录 Redis 的执行操作一般有 everysec、always、no 三种模式常用的是 everysec 每秒记录一次若宕机只会损失一秒的数据。RDB 快照顾名思义对当时情况进行拍照可以通过 save() 或者 bgsave() 调用。自服务会在1. 初始化2. 缺少较多数据即偏移量过旧。触发全量增长。Redis 有一个环形缓冲区环形缓冲区存放 Redis 执行命令当偏移量不存在于环形缓冲区则会触发全量复制。一般流程为数据执行 - AOF 缓存 - replication backlog - 根据策略 AOF 刷盘。4. 布隆过滤器原理答1. 添加元素存指纹假设我们有一个 16 位的空数组以及 3 个哈希函数hash1、hash2、hash3。当要添加字符串apple时分别计算三个哈希值得到三个位置比如2、8、13。将数组中这些位置都设为 1。2. 查询元素查指纹当要检查banana是否存在时同样计算它的三个哈希值得到位置2、7、13。检查这些位置位置 2 和 13 都是 1但位置 7 是 0。结论只要有任意一个位置为 0就说明banana绝对不存在。3. 误判指纹冲突当要检查grape时计算位置为2、8、13。检查这些位置全部都是 1。结论布隆过滤器会告诉你grape可能存在。但真相可能是这些 1 是apple和其他元素留下的grape根本没存过。这就是误判。5.redis使用set nx实现分布式锁答:set nx本质就是如果key 存在则无法创建达到锁的效果,但是只用这一句话来实现分布式锁依旧有问题:1.会意外释放到别的人创建的锁---创建特定id2.会导致多个线程同时认为自己拿到锁---加锁原子性3.执行到一半锁过期---看门狗所以目前常用直接使用redission 或者是lua脚本Mysql相关内容:1.