PC's Blog

前言

介绍Redis数据库的实现，解答以下几个问题：

• Redis服务器是怎么保存数据库的？客户端又是怎么切换数据库的？
• 数据库的增、删、改、查的实现
• 键的过期时间是怎么保存的，又是如何删除的？怎么判断一个键是否过期？
• 过期键的删除策略有哪些？每种策略的优缺点分析？Redis采用的是哪种策略，具体又是怎么实现的？

前言

LeetCode链表题汇总，记录解题思路，C/C++语言实现。

LeetCode链表题

• 判断链表是否有环 ：https://leetcode-cn.com/problems/linked-list-cycle/

• 输出环形链表的入环点：https://leetcode-cn.com/problems/linked-list-cycle-ii/

• 输出链表中倒数第k个节点：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

• 反转链表：https://leetcode-cn.com/problems/reverse-linked-list/

前言

Redis没有直接使用基础数据结构来实现数据库，而是基于这些数据结构创建了一个对象系统。这个系统包含字符串对象、列表对象、哈希对象、集合对象、有序集合对象。

1. Redis3.0中的6种基础数据结构

前言

跳跃表是一种以O(log N)期望时间支持查找、插入、删除操作的、有序的数据结构。

Redis使用跳跃表作为有序集合键的底层实现之一。

跳表的基本实现原理参考：《Skip lists: a probabilistic alternative to balanced trees》

Redis中的跳表实现

什么是三大范式

三大范式是数据库设计遵循的规范, 分别是：

• 第一范式(1NF)：表中每列不可再拆分
• 第二范式(2NF)：1NF基础上，要求非主键列完全依赖于主键，不能只依赖于主键的一部分(针对联合主键)
• 第三范式(3NF)：2NF基础上, 要求任何非主键列必须直接依赖于主键，不能是传递依赖

问题描述

进程收到SIGABRT信号异常退出，异常调用栈显示__stack_chk_fail

原因分析和定位思路

原因分析： __stack_chk_fail说明发生了缓冲区溢出，canary被破坏。这说明代码设置GCC编译选项fstack-protector，开启了栈保护机制canary

定位思路：

前言

Redis中，整数集合是集合键的底层之一。

当一个集合只包含整数元素，且这个集合中元素个数不多的情况下，Redis就会使用整数集合作为集合键的底层实现。

1. 整数集合的实现

跳跃表简介

跳跃表是一种以O(log N)期望时间支持查找、插入、删除操作的、有序的数据结构。其性能和红黑树相当，且跳跃表实现更为简单。

如何理解”跳跃“二字

问题描述

root进程调sem_open(XXX, O_CREAT, 0666, 1)创建信号量后，非root进程使用sem_open打开同一个信号量失败，报Permission Denied错

原因分析

非root进程调用sem_open， 以O_CREAT方式打开信号量，需要同时有对该信号量文件的读权限 + 写权限。

ll /dev/shm/sem.semname 查看信号量文件权限，发现权限为0644，缺少其他用户写权限。这个权限与sem_open中指定的权限值0666不一致。

实验简介

实现自己的动态内存分配器（malloc、free、realloc）。

预备知识

• 阅读《CSAPP原书第3版》 9.9小节 —— 动态内存分配。
• 阅读writeup的全部内容。