数据存储方式 B树：B树的每个节点既存储数据也存储索引。这意味着B树的非叶子节点既包含索引键也包含对应的数据。 B+树：B+树的非叶子节点仅存储索引键，而数据全部存储在叶子节点。B+树的所有叶子节点通过指针连接成一个有序链表，便于范围查询。 叶子节点关联性 B树：B树的叶子节点和非叶子节点没有直接关联，各自独立存在。 B+树：B+树的叶子节点之间通过链表相连，形成了一个有序的链表。这有助于范围查询，因为数据按顺序排列。 范围查询效率 B树：在B树上进行范围查询相对较慢，因为需要访问非叶子节点和叶子节点。 B+树：B+树在范围查询时非常高效，因为只需遍历叶子节点的链表。 非叶子节点的索引键 B树：非叶子节点的索引键可以是重复的，可能导致不必要的冗余数据。 B+树：B+树的非叶子节点的索引键一般是不重复的，确保了索引的唯一性。 叶子节点个数 B树：B树的叶子节点数量和数据记录数量相等。 B+树：B+树的叶子节点数量比数据记录数量多，因为叶子节点主要用于存储数据和维护链表，而非叶子节点用于索引。 B+树 B树 ...

众所周知，一个数据库系统想要实现高可用，主要从以下两个方面来考虑： 保证数据安全不丢失 系统可以正常提供服务 而 Redis 作为一个提供高效缓存服务的数据库，也不例外。 上期我们提到的 Redis 持久化策略，其实就是为了减少服务宕机后数据丢失，以及快速恢复数据，也算是支持高可用的一种实现。 除此之外，Redis 还提供了其它几种方式来保证系统高可用，业务中最常用的莫过于主从同步（也称作主从复制）、Sentinel 哨兵机制以及 Cluster 集群。 同时，这也是面试中出现频率最高的几个主题，这期我们先来讲讲 Redis 的主从复制。 2. 主从复制简介 Redis 同时支持主从复制和读写分离：一个 Redis 实例作为主节点 Master，负责写操作。 其它实例（可能有 1 或多个）作为从节点 Slave，负责复制主节点的数据。 2.1 架构组件 主节点Master 数据更新：Master 负责处理所有的写操作，包括写入、更新和删除等。 数据同步：写操作在 Master 上执行，然后 Master 将写操作的结果同步到所有从节点 Slave 上。 从节点Slave 数据读取：Slave 负责处理读操作，例如获取数据、查询等。 数据同步：Slave 从 Master 复制数据，并在本地保存一份与主节点相同的数据副本。 2.2 为什么要读写分离 1）防止并发 从上图我们可以看出，数据是由主节点向从节点单向复制的，如果主、从节点都可以写入数据的话，那么数据的一致性如何保证呢？ 有聪明的小伙伴可能已经想到了，那就是加锁！ 但是主、从节点分布在不同的服务器上，数据跨节点同步时又会出现分布式一致性的问题。而在高频并发的场景下，解决加锁后往往又会带来其它的分布式问题，例如写入效率低、吞吐量大幅下降等。 而对于 Redis 这样一个高效缓存数据库来说，性能降低是难以忍受的，所以加锁不是一个优秀的方案。 那如果不加锁，使用最终一致性方式呢？ 这样 Redis 在主、从库读到的数据又可能会不一致，带来业务上的挑战，用户也是难以接受的。 业务为用户服务，技术为业务服务。 所以，为了权衡数据的并发问题和用户体验，我们只允许在主节点上写入数据，从节点上读取数据。 2）易于扩展 我们都知道，大部分使用 Redis 的业务都是读多写少的。所以，我们可以根据业务量的规模来确定挂载几个从节点 Slave，当缓存数据增大时，我们可以很方便的扩展从节点的数量，实现弹性扩展。 同时，读写分离还可以实现数据备份和负载均衡，从而提高可靠性和性能。 3）高可用保障 不仅如此，Redis 还可以手动切换主从节点，来做故障隔离和恢复。这样，无论主节点或者从节点宕机，其他节点依然可以保证服务的正常运行。 3. 主从复制实现 3.1 开启主从复制 要开启主从复制，我们需要用到 replicaof 命令。 当我们确定好主节点的 IP 地址和端口号，在从库执行 replicaof <masterIP> <masterPort> 这个命令，就可以开启主从复制。 注意，在 Redis5.0 之前，该命令为 slaveof 开启主从复制后，应用层采用读写分离，所有的写操作在主节点进行，所有读操作在从节点进行。 主从节点会保持数据的最终一致性：主库更新数据后，会同步给从库。 3.2 主从复制过程 那主从库同步什么时候开始和结束呢？ 是一次性传输还是分批次写入？Redis 主从节点在同步过程中网络中断了，没传输完成的怎么办？ 带着这些疑问我们来分析下，首先，Redis 第一次数据同步时分 3 个阶段。 1）建立连接，请求数据同步 主从节点建立连接，从库请求数据同步。 从服务器从 replicaof 配置项中获取主节点的 IP 和 Port，然后进行连接。 连接成功后，从服务器会向主服务器发送 PSYNC 命令，表示要进行同步。同时，命令中包含 runID 和 offset 两个关键字段。 runID：每个 Redis 实例的唯一标识，当主从复制进行时，该值为 Redis 主节点实例的ID。由于首次同步时还不知道主库的实例ID，所以该值第一次为 ? offset：从库数据同步的偏移量，当第一次复制时，该值为 -1，表示全量复制 主服务器收到 PSYNC 命令后，会创建一个专门用于复制的后台线程（replication thread），然后记录从节点的 offset 参数并开始进行 RDB 同步。 2）RDB 同步 主库生成 RDB 文件，同步给从库。 当从服务器连接到主服务器后，主服务器会将自己的数据发送给从服务器，这个过程叫做全量复制。主服务器会执行 bgsave 命令，然后 fork 出一个子进程来遍历自己的数据集并生成一个 RDB 文件，将这个文件发送给从服务器。 在这期间，为了保证 Redis 的高性能，主节点的主进程不会被阻塞，依旧对外提供服务并接收数据写入缓冲区中。 从服务器接收到 RDB 文件后，会清空自身数据，然后加载这个文件，将自己的数据集替换成主服务器的数据集。 3）命令同步 在第一次同步过程中，由于是全量同步，所以用时可能比较长，这期间主库依旧会写入新数据。 但是，在数据同步一开始就生成的 RDB 文件中显然是没有这部分新增数据的，所以第一次数据同步后需要再发送一次这部分新增数据。 这样，主服务器需要在发送完 RDB 文件后，将期间的写操作重新发送给从服务器，以保证从服务器的数据集与主服务器保持一致。 3.3 增量同步 1）命令传播 在完成全量复制后，主从服务器之间会保持一个 TCP 连接，主服务器会将自己的写操作发送给从服务器，从服务器执行这些写操作，从而保持数据一致性，这个过程也称为基于长连接的命令传播（command propagation）。 增量复制的数据是异步复制的，但通过记录写操作，主从服务器之间的数据最终会达到一致状态。 2）网络断开后数据同步 命令传播的过程中，由于网络抖动或故障导致连接断开，此时主节点上新的写命令将无法同步到从库。 即便是抖动瞬间又恢复网络连接，但 TCP 连接已经断开，所以数据需要重新同步。 从 Redis 2.8 开始，从库已支持增量同步，只会把断开的时候没有发生的写命令，同步给从库。 详细过程如下： 网络恢复后，从库携带之前主库返回的 runid，还有复制的偏移量 offset 发送 psync runid offset 命令给主库，请求数据同步； 主库收到命令后，核查 runid 和 offset，确认没问题将响应 continue 命令； 主库发送网络断开期间的写命令，从库接收命令并执行。 这时，有细心的小伙伴可能要问了，网络断开后，主库怎么知道哪些数据是新写入的呢？ 这是个好问题，接下来我们详细说明一下。 3）增量复制的关键 Master 在执行写操作时，会将这些命令记录在 repl_backlog_buffer （复制积压缓冲区）里面，并使用 master_repl_offset 记录写入的位置偏移量。 而从库在执行同步的写命令后，也会用 slave_repl_offset 记录写入的位置偏移量。正常情况下，从库会和主库的偏移量保持一致。 但是，当网络断开后，主库继续写入，而从库没有收到新的同步命令，所以偏移量就停止了。所以，master_repl_offset 会大于 slave_repl_offset。 注意：主从库实现增量复制时，都是在 repl_backlog_buffer 缓冲区上进行。 网络断开前后，主从库的同步图如下：   repl_backlog_buffer 复制积压缓冲区是一个环形缓冲区，如果缓冲区慢了（比如超过 1024），则会从头覆盖掉前面的内容。 所以，当网络恢复以后，主节点只需将 master_repl_offset 和 slave_repl_offset 之间的内容同步给从库即可（图中 256~512 这部分数据）。 需要注意的是，主库的积压缓冲区默认为 1M，如果从库网络断开太久，缓冲区之前的内容已经被覆盖，这时主从的数据复制就只能采取全量同步了。 所以我们需要根据业务量和实际情况来设置 repl_backlog_buffer 的值。 4. 小结 面让架构易于扩展，另一方面防止单体故障：当主库挂了，可以立即拉起从库，不至于让业务停滞太久。 而首次主从复制包括建立连接，RDB 同步和命令同步三个阶段。 为了保证同步的效率，除了第一次需要全量同步以外，例如当主从节点断连后，则只需要增量同步，这是由主从库的复制偏移量以及主库的 repl_backlog_buffer 复制积压缓冲区来控制的。 好了，以上就是本文的所有内容了，希望今天的文章能让大家更深入地了解 Redis 主从复制，并在面试或者实际工作中学以致用，探索更多的细节。 ...

红黑树（Red Black Tree）是一种平衡的排序二叉树，如图： 所有的红黑树都满足如下性质： 每个节点要么是红色，要么是黑色的； 根节点和叶子节点（即 NIL 空节点）一定是黑色； 红色节点的父节点，或者子节点一定为黑色； 对每个节点，从该节点到叶子节点的所有路径上，包含的黑节点数目相同。 根据性质4，我们可以得出：从根节点到叶子节点的可能路径，最长不超过最短路径的两倍。 红黑树的主要应用场景： java8 hashmap 中链表转红黑树优势：时间复杂度从O(n) –> O(logn)，且自旋开销较其他树较低（不用整体平衡）。 epoll 在内核中的实现，用红黑树管理 fd 文件描述符 优势： 因为内核态需要维护一个长久存放 fd 的数据结构，而 fd 的变动十分频繁，且需要支持快速查询，所以红黑树很适合 红黑树可以判断是否是重复的 fd 3.Linux 进程调度 Completely Fair Scheduler，用红黑树管理进程控制块；nginx 中，用红黑树管理 timer 等 。 ...

ZK的数据模型是一种树形结构，具有一个固定的根节点（/），可以在根节点下创建子节点，并在子节点下继续创建下一级节点。 每一层级用/隔开，且只能用绝对路径（get/work/task1）的方式查询ZK节点，而不能用相对路径。 持久节点 将节点创建为持久节点，该数据节点会一直存储在ZK服务器上，即使创建该节点的客户端与服务端的会话关闭了，该节点依然不会被删除，除非显式调用delete函数进行删除操作。 临时节点 如果将节点创建为临时节点，那么该节点数据不会一直存储在ZK服务器上。当创建该临时节点的客户端会话因超时或发生异常而关闭时，该节点也相应在ZK服务器上被删除。也可以主动调用delete删除。 有序节点 有序节点并不算一种单独种类的节点，而是在持久节点和临时节点的基础上，增加一个节点有序的性质。创建有序节点的时候，ZK服务器会自动使用一个单调递增的数字作为后缀，追加到创建的节点后边。例如一个客户端创建了一个路径为works/task-的有序节点，那么ZooKeeper将会生成一个序号并追加到该节点的路径后，最后该节点的路径为works/task-1。 节点内容 一个二进制数组（byte data[]），用来存储节点的数据、ACL访问控制、子节点数据（因为 临时节点不允许有子节点，所以其子节点字段为null），记录自身状态信息的stat。 stat +节点路径可以查看状态信息 czxid：创建节点的事务id mzxid：最后一次被更新的事务id pzxid：子节点最后一次被修改的事务id ctime：创建时间 mtime：最后更新时间 version：版本号、表示的是对节点数据内容，子节点信息或ACL信息的修改次数可以避免并发更新问题，使用之前获取的版本进行CAS操作更新 cversion：子节点版本号 aversion：acl的版本号 ephemeralOwner：创建节点的sessionId，如果是持久节点、值为0 dataLenght：数据内容长度 numChildren：子节点个数 ...

Zookeeper是一个分布式协调服务，可以用来实现分布式锁的功能。 分布式锁是一种控制多个分布式系统之间同步访问共享资源的机制。 Zookeeper实现分布式锁的原理如下：   首先，需要在 Zookeeper 中创建一个持久节点作为锁的根节点，例如 /lock。 然后，每个需要获取锁的客户端都在 /lock 节点下创建一个临时顺序节点，例如 /lock/seq-0000000001。这样可以利用 Zookeeper 的节点唯一性和顺序性特性。 接着，每个客户端都获取 /lock 节点下的所有子节点，并按照序号排序，判断自己创建的节点是否是最小的。如果是，说明获取到了锁，可以执行相关操作。 如果不是最小的，说明没有获取到锁，需要等待。此时，客户端可以监听自己前一个节点的变化（例如删除），一旦监听到事件发生，就重新判断自己是否是最小的节点。 最后，当客户端执行完操作后，需要释放锁，即删除自己创建的临时顺序节点。这样，后面等待的客户端就可以收到通知，继续尝试获取锁。 以上就是 Zookeeper 实现分布式锁的基本原理。 实现方式： 实际开发过程中，可以 curator 工具包封装的API帮助我们实现分布式锁。 <dependency> <groupId>org.apache.curator</groupId> <artifactId>curator-recipes</artifactId> </dependency> 1、客户端想要获取锁，就在 Zookeeper 上创建一个临时的、有序的节点，这个节点相当于一把锁。  2、客户端查看 Zookeeper 上所有的节点，按照顺序排列，看看自己创建的节点是不是最小的。  3、判断是否获得锁，如果是读操作，只要自己前面没有写操作的节点，就可以获取锁，然后开始执行读逻辑。如果是写操作，只有自己是最小的节点，才可以获取锁，然后开始执行写逻辑。  4、如果没有获取到锁，就要等待。如果是读操作，就监听自己前面最近的一个写操作的节点。如果是写操作，就监听自己前面最近的一个节点。一旦监听到这个节点被删除了，就重新判断是否可以获取锁。 Curator 的几种锁方案 ： 1、InterProcessMutex：分布式可重入排它锁2、InterProcessSemaphoreMutex：分布式排它锁3、InterProcessReadWriteLock：分布式读写锁下面例子模拟 50 个线程使用重入排它锁 InterProcessMutex 同时争抢锁： 实例: public class InterprocessLock { public static void main(String[] args) { CuratorFramework zkClient = getZkClient(); String lockPath = "/lock"; //通过InterProcessMutex创建分布式锁 InterProcessMutex lock = new InterProcessMutex(zkClient, lockPath); //模拟50个线程抢锁 for (int i = 0; i < 50; i++) { new Thread(new TestThread(i, lock)).start(); } } static class TestThread implements Runnable { private Integer threadFlag; private InterProcessMutex lock; public TestThread(Integer threadFlag, InterProcessMutex lock) { this.threadFlag = threadFlag; this.lock = lock; } @Override public void run() { try { lock.acquire(); System.out.println("第"+threadFlag+"线程获取到了锁"); //等到1秒后释放锁 Thread.sleep(1000); } catch (Exception e) { e.printStackTrace(); }finally { try { lock.release(); } catch (Exception e) { e.printStackTrace(); } } } } private static CuratorFramework getZkClient() { String zkServerAddress = "127.0.0.1:2181"; ExponentialBackoffRetry retryPolicy = new ExponentialBackoffRetry(1000, 3, 5000); CuratorFramework zkClient = CuratorFrameworkFactory.builder() .connectString(zkServerAddress) .sessionTimeoutMs(5000) .connectionTimeoutMs(5000) .retryPolicy(retryPolicy) .build(); zkClient.start(); return zkClient; } } </div> ...