2020年7月

平衡二叉树

二叉树的查找的时间复杂度是O(log2N)，其查找效率与深度有关，而普通的二叉树可能由于内部节点排列问题退化成链表，这样查找效率就会很低。因此平衡二叉树是更好的选择，因为它保持平衡，即通过旋转调整结构保持最小的深度。其查找的时间复杂度也是O(log2N)。

但实际上，数据库中索引的结构也并非AVL树或更优秀的红黑树，尽管它的查询的时间复杂度很低。

- 阅读剩余部分 -

流量控制

一般来说，我们希望数据传输的更快一些。但是如果发送方传的过快，接收方来不及接收，这就会造成数据的丢失。所谓流量控制(flow control)就是让发送方的发送速率不要太快，要让接收方来的及接收。

滑动窗口

流量控制利用滑动窗口机制来实现。
tcp报文结构中有4字节表示接收方窗口大小。发送方的发送窗口不能超过接收方的接收窗口大小。

拥塞控制

网络资源、带宽、交换机，传输需求超过了资源所能提供的可用部分，网络性能就会变坏。这就叫拥塞。

拥塞控制和流量控制的一丝差别：
拥塞控制就是防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不至过载。
拥塞控制是一个全局性的过程，涉及所有主机、路由器，所以即使tcp端点迟迟不能接收对方的消息，也无法知道拥塞到底发生在网络的何处以及发生的原因。
而流量控制往往指点对点通信量的控制。是端到端的问题。

从控制理论的角度看拥塞控制，可以分为开环控制和闭环控制。

开环控制

开环控制是在设计网络时事先将有关发生拥塞的因素考虑周到，力求网络工作时不拥塞。运行过程中不再改正。

闭环控制

闭环控制是基于反馈链路的概念。

  1. 监测网络系统一遍检测拥塞在哪里发生。
  2. 把拥塞发生的信息传送到可采取行动的地方。
  3. 调整网络系统的运行来解决出现的问题。

检测网络拥塞的主要指标：由于缺少缓存空间而被丢弃的分组的百分数、平均队列长度、超时重传的分组数、平均分租延时、分组时延的标准差等。

RFC2581定义了拥塞控制的四中算法：慢开始、拥塞避免、快重传、快恢复。

  1. 链地址法，将冲突键以链表结构存储
  2. 开放寻址法。其中包括三种方式：线性探测再散列、二次探测再散列、伪随机再散列
  3. 再散列法。对冲突键不断散列，直到不冲突为止。消耗计算时间。

字典

字典又称符号表、关联数组、映射，是保存k-v结构的抽象数据结构。

redis中字典是常用数据结构，数据库命令就是字典结构，还有哈希对象，底层也是字典，但是有条件。

- 阅读剩余部分 -

跳跃表

跳跃表skiplist 是一种有序数据结构，通过在每个节点维持多个指向其他节点的指针，从而达到快速访问的目的。

跳跃表可以在O(logn)、最坏O(N)时间复杂度下查找节点，还有顺序性操作批量处理节点。

- 阅读剩余部分 -

压缩列表ziplist是列表、哈希和有序集合的底层实现，当数据量比较小时会使用ziplist。
数据类型与数据结构对应关系.png

  1. 列表类型ziplist条件：

    • 列表对象保存的所有字符串元素都小于64字节；
    • 列表对象保存的元素个数小于512个。
      在配置文件中 list-max-ziplsit-entries和list-max-ziplist-value。

  2. 哈希类型ziplist条件：

    • 哈希对象保存的所有字符串元素都小于64字节；
    • 哈希对象保存的元素个数小于512个。
      在配置文件中hash-max-ziplsit-entries和hash-max-ziplist-value。

  3. 有序集合ziplist条件：

    • 有序集合保存的元素小于128个
    • 所有元素长度小于64字节
      在配置文件中zset-max-ziplsit-entries和zset-max-ziplist-value。




- 阅读剩余部分 -

zset对象的结构可以是ziplist或skiplist

当同时满足以下两个条件时使用ziplist：

  1. 有序集合保存的元素小于128个
  2. 所有元素长度小于64字节
    注，以上条件上限值可修改。在配置文件中zset-max-ziplsit-entries和zset-max-ziplist-value。

当ziplist作为zset的底层存储结构时候，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值。集合元素按分值从小到大排序，小的在表头，大的在表尾。

zadd price 8.5 apple 8.1 banana

键price的值对象使用的是ziplist，对象如图所示。
ziplist编码的有序集合对象.png

对象使用的压缩列表如图所示：
有序集合压缩列表中从小到大排序.png

当skiplist作为zset的底层存储结构的时候，使用skiplist按序保存元素及分值，使用dict来保存元素和分值的映射关系。




- 阅读剩余部分 -

sds定义

sds.h/sdshdr 结构定义了sds的结构：

struct sdshdr {
//记录buf数组使用字节数量，即字符串长度
int len;

//记录buf数组未使用字节数量
int free;

//字节数组，保存字符串
char buf[];

len： 字符串长度

- 阅读剩余部分 -

哨兵系统会监控主从服务器，当检测到下线时长超过用户设定时长上限时，会进行故障转移操作：

  • 选择一个从服务器作为主服务器
  • 然后对其他所有从服务器发送新的复制指令，让它们成为新的主服务器的从服务器，当所有从服务器都开始复制新的主服务器时，故障转移操作完毕
  • 另外，哨兵还会继续监视已下线的服务器，并在它重新上线时，将它设置为新的主服务器的从服务器。

- 阅读剩余部分 -

2.8版本前后复制原理有所不同，2.8之前称为旧版，2.8后称为新版。

旧版复制实现原理

redis的复制操作分为同步(sync)和命令传播(command propagate) 两个操作：

  • 同步操作用于将从服务器状态更新为主服务器当前所处的服务器状态
  • 命令传播操作则用于当主服务器状态被修改，导致主从状态不一致时，让主从状态恢复到一致状态。

- 阅读剩余部分 -

  1. 1
  2. 2
  3. 3
  4. 4