跳转至

SimpleRedis

实习这么长时间，学习了这么关于项目的，对于一个项目来说，现在我应该注意什么，要参考什么

项目需求

  1. 完成各种数据结构，使用C++去实现
  2. 进行单元测试，对各个数据结构进行单元测试的使用，并且尽量能够总结一个qps，并发量测试出来
  3. 代码能否编译成对应的lib文件或者说是动态库的形势，提供给其他人使用？

侵入式数据结构

优点

  • 对于非侵入式数据结构来说，数据结构存储的是用户传递的副本（会发生拷贝），但是侵入式数据结构存储的不是数据结构的副本，而是存储对象的本身，对象插入数据容器的数据需要由对象本身来提供
    • 根本不会出现调用任何内存分配相关的问题（因为侵入式数据结构的数据由外部进行管理，压根没有析构函数）
    • 提供可预见性，不会进行内存管理（内存管理是不可预见的操作），管理起来要比非侵入式数据结构要好
  • 更快的访问速度，完全没有内存分配，内存访问要快得多
  • 存储对象如果不能copy的情况下也能使用侵入式数据结构，（因为非侵入式数据结构需要copy）

缺点

  • 存储的是对象本身，对象本身需要改动，需要改动对象的内存布局，插入两个指针，sizeof的数据肯定要大
  • 数据结构不会进行内存管理，用户要独立于容器之外要管理对象的生命周期
  • 编写难度要不非侵入式数据结构要大

container_of

侵入式数据结构中一个数据是包含两个部分的，一个是数据本身，另一个是数据的前后指针，这里就需要偏移列表节点来获取真正的容器数据

Node* my_node = lookup_function();
MyRealData* my_data = container_of(my_node, MyData, node);
//                                 ^ptr     ^type   ^member

#define container_of(ptr, T, member) ({                  \
    const typeof( ((T *)0)->member ) *__mptr = (ptr);    \
    (T *)( (char *)__mptr - offsetof(T, member) );})

数据结构

HashTable 哈希表

对于一个KV存储的数据结构，哈希表的查询，查找的时间复杂度都是\(O(1)\)的，但是实现方式有两种

  1. 开放寻址法
    1. 很显然，如果负载因子很多的话，那么其时间复杂度就会直接变大
  2. 链式法：
    1. 时间复杂度非常均匀，实现也非常简单
  • 数组大小通常是2的次幂，
  • 均摊成本是\(O(1)\)，但是调整大小依旧是\(O(n)\),因为调整的时候是将其移动到另一个新表上

AVL树

  • 为什么选择这个数据结构？
    • 自平衡，而且是二叉树，好实现
  • 对于排序来说，是能够自动保持平衡的树，左旋右旋，完全不会旋
    • 其实这个旋转还是比较好实现的，左旋和右旋其实是一样的，其实就是将两个相关节点的左儿子，右儿子，父亲搞清楚，然后更新一下对应的树的相关信息就好了
    • 最后旋转出来的节点是新节点，就是最后挂出来的节点， 这里使用面向过程的思想比较好，因为对于树来说，很多节点可能是空的，换算成面向过程比较好操作

AVL排序

真正实现的是如何进行排序，这个还是比较关键的

测试

  • gtest文件中进行测试
  • 之后可以使用google benchmark进行测试，这个还是比较好的
  • 使用工具：valgrind进行测试: valgrind --tool=memcheck --leak-check=full ./测试文件

TTL

  • redis中很多数据都是缓存的，缓存都有有一个时间的，所以这里要用一个堆来维护这个数据。
  • 这里使用的是小根堆，也就是堆的root是比较小的元素
  • 很显然，插入，删除的时间复杂度是\(O(logn)\)

资料