theme: orange
富途，向梦奔FU，星海为TU。
接受成长，也接受所有的不欢而散。
一、服务本地缓存如何实现DB和缓存内的数据一致性？
当后台数据有更新时，通过Redis的Pub/Sub机制通知所有在本地缓存该缓存的Pod，Pod接受到通知后清空本地缓存，然后下次缓存命中的时候，重新从DB中获取内容，此时完全可以避免脏数据的问题产生，因为本地缓存为了避免瞬时流量时，当缓存都不存在时去同时查看DB，导致DB压力很大的情况下，本地缓存组件一般都是会进行Lock的。这样单个Pod内同一个缓存同一个时刻只会有一个请求打入到DB，其他请求会因为被Lock住而无法打到DB，当去请求DB的请求写入缓存后释放锁，此时其他所有请求都直接从缓存中获取，可以避免大量的请求直接打到DB上。
对于Redis这类内存分布式中间件作为缓存的话，当我们某个请求导致缓存变更时，此时，为了解决缓存中出现脏数据，我们一般可以通过添加缓存过期时间作为兜底策略的同时进行双删策略来保证缓存和数据库DB的数据一致性。而用双删的原因就是不需要添加分布式锁就能实现缓存一致性，我们考虑一种场景（只有一个删）：
- A请求去请求缓存的时候，B已经删了缓存（B先删缓存，在更新DB），此时A发现缓存不存在，则会去DB请求数据然后缓存到DB中，此时如果B请求还没有将数据写入到DB中，那么A缓存的数据则时脏数据，此时如果有缓存时间，那么就一定会存在缓存未过期的时间段内的缓存是脏数据。
- A请求去请求缓存的时候，B正在更新DB（B先更新DB在删除），假设此时缓存为空，那么A请求的DB如果发现没有缓存命中，此时会去查询DB，那么查询到的BD则可能是B还没有更新结束的旧的数据，此时A将数据更新到缓存内，那么在缓存有效期内，仍然是脏数据。
基于以上两种只删一个的情况下，我们只需要B在更新DB时，在更新DB前删缓存，在更新DB后再删缓存就可以完全避免两种情况。同时我们还可以使用延迟双删，当我们更新DB后，先删除缓存，然后在间隔一段时间在删除缓存。
二、用Redis实现缓存同步，Redis本身并不是可靠的，缓存可以容忍一段时间的脏数据吗？
对于这种用Redis实现的Pub/Sub监听机制的场景，本身就不是要求数据严格一致的场景，因为本身Redis会出现数据丢失的情况（master收到命令后，宕机，此时客户端认为OK，但是新的master不会有该新数据，就会导致数据丢失，如果是分布式锁，那么在锁未过期的情况下，该锁的流程所有Pod都是阻塞的。）。而同时本地缓存又有缓存的过期时间，所以一般来说如果本地缓存数据可容忍一段时间的脏数据，那么是可以用Redis来实现的，因为毕竟缓存时间过期了就会重新Load数据到缓存内，此时Load的数据一定是最新的。
其实放入本地缓存内的数据本身就已经说明了这些缓存数据时可以容忍一定时间的脏数据。如果我们要尽量去避免这种情况的话，我们可以采用可靠的中间件来进行实现，比如Kafka，我们可以专门建立一个Topic为缓存更新通知Key，然后不同的缓存通过定义不同的Event来进行实现，当监听到某个Event的时候，我们就去更新对应的本地缓存中的内容，这种在一定程度上是要比Redis可靠的。缓存实例在所有服务内都应该是单实例缓存，所以一个服务只要监听Topic,然后根据不同的Event找到不同的缓存实例，进行清除更新即可。
三、为什么用Redis而不用Kafka？
Redis适用场景为缓存或者分布式锁等需要在多个进程之间共享内存来实现分布式缓存或者互斥的作用。其中Redis的数据结构比较丰富，比如哈希、跳表、压缩链表等，有查询时间复杂度高的数据结构，也有排序性能高的数据结构，也有内存紧凑型的压缩链表，提供丰富算法来供业务使用，由于其存在数据丢失的可能性，所以在设计方案的时候，如果考虑到Redis则要考虑数据丢失的风险。所以Redis一般都是用于进行缓存的，如果缓存没有命中则去DB中重新加载。
Kafka提供可靠的数据持久化能力，和高效的吞吐能力，其每个Topic内的分区都有一定的副本来保证数据持久化的可靠性，并且分区的Leader和Flower分配在不同的Broker上，当一个Broker挂掉后，会选择其其他Broker的Flower作为Leader分区提供服务。同时在这个基础上，提供了生产者ACK机制，如果设置ACK为2，那么只有当Broker上的Leader分区和Flower分区全部持久化成功后才会返回给生产者成功的ACK，否则则返回失败的ACK。其中Broker返回ACK机制是异步的逻辑，内部维护了时间轮算法来进行异步返回ACK操作。这两个步骤基本上就可以保证Kafka的持久化是可靠的。而Kafka一般用在异步解耦和流量削峰等场景上。同时，Kafka消费者是基于消费者组来实现的，也就是说Kafka在消费的时候，是一个组内的消费者只会监听不同的分区，默认按照消费者数量进行轮转分配。所以Kafka在消费者从分区内获取消息时分布式获取的，是多个消费者并行消费的，如果要考虑获取消息时的延迟、消息传输的延迟、消息处理的延迟，那么Kafka这种分区特性能够很大程度上提高吞吐量。同时Kafka增加消费者也很容易，只需要扩容Pod就可以了。
四、Kafka在一个Topic内，如何实现高优先级的消息优先消费？
我们知道Kafka消费者在消息消费时是消费均等的概念，也就是说一个消费者在处理一个消息时的时间平均的话是相等的。在这个前提下，假设我们现在有10个消费者，此时如果我们有10个分区，同时我们固定优先级的概念，整个中心有3档任务，1-6分区高优先级，7-9中优先级，10低优先级。这样的话高优先级则会有6个消费者进行消费，中优先级有2个消费者进行消费，低优先级则只有1个小希进行消费，此时如果高、中、低优先级的消息数量都有100w，那么我们可以明显的感知到，这100w的消息数量一定是高优先级的分区优先执行完毕。在消费者消费均等逻辑上增加高优先级的消费者的数量来实现Kafka优先的一个概念。但是这种情况在扩容时可以在有消息没有被消费时进行扩容，但是如果要缩容的话必须要保证没有消息消费才能进行缩容。因为要避免消费者rebalance时将高优先级的分区上的消息消费速度降低。
五、消息队列在进行消息消费时，如果还未进行ACK，此时消费者挂掉了会有什么影响？
如果我们在一个消息还没有消费完毕时，如果消费者挂掉了此时是没有什么影响的，因为我们会在消费者哪里进行消息幂等（对于同一个请求，处理多次的结果和处理一次的结果是一样的）处理。具体实现是：我们维护一个唯一Key的数据表结构，这个唯一Key是针对消息来说的，因为我们总时能够从消息上抽象出一个唯一的消息Key，我们在消费消息前将该唯一Key存入到数据表中，并设置状态为未消费（status=0）。我们消费逻辑内进行RPC处理或者其他处理本身都是幂等的，因为下游服务设计时就会设计成幂等的。所以在消费处理过程中如果处理成功了，那么我们将数据表状态修改为status=1表示成功，然后ACK掉该数据。如果RPC失败或者消费者挂机了，此时也无影响，因为该消息状态为0，那么当消费者进行Rebalance时，重新开始消费该消息，那么会判断状态是否为1，如果是1则直接ACK，否则执行业务逻辑，因为其本身下游服务都是幂等的，所以可以进行重试操作。当所有操作成功时修改状态为1，然后ACK掉即可。
六、如何让项目更加稳定、可靠、高吞吐，能够抗住瞬时的流量？
对于稳定和可靠这方面来说，我们在选用的第三方组件上选择高可靠的组件的同时，在我们业务逻辑上尽可能的有兜底策略那么整体上项目时可靠的。兜底策略可以是当失败时我们进行幂等重试、或者写入失败记录表然后后台线程定时重试等也就是有一定的重试机制。同时我们也可以在某些关键路径上，对于一些不影响核心功能点上进行降级或者限流，来保证服务整体的稳定性。同时对于下游服务我们尽可能采用一定的负载均衡策略机制来去避免将请求打在同一个Pod上。同时在关键路径上添加适当的监控或者Error日志，并通过第三方组件来实现告警通知能力。当发现问题时能够及时发现服务内的问题而从而进行修正。为了保证功能的稳定性，我们必须假设某些场景下DB出现问题的时候，我们能够及时恢复数据的能力，所以我们要堆数据进行冷备处理，也就是备份处理。
高吞吐量和瞬时并发流量的服务我们要尽可能避免同步排队去做某些事情，利用现代多核CPU能力去并发做某些事情。那么问题就落在了如何避免同步的问题上。避免同步的问题上其实就是去异步做业务逻辑，而异步一定要保证异步的是可靠的，而可靠的异步组件就是Kafka了，所以我们可以利用Kafka的可靠的持久化能力、和Topic分区能力来实现分布式异步能力，和流量入口哪里进行解耦，快速释放入口资源，能够顶住瞬时高流量，尽快将结果返回给客户端，同时异步去做业务逻辑。这样就能够保证相同的资源去接纳更多的请求来处理业务逻辑。
七、如果使用中间件挂掉了如何处理？
如果我们在要求服务严格可靠的情况下，我们可以进行多路处理，一个快速处理，一个可以慢速处理，但是慢速处理也要能够进行处理。具体点就是我们在向Redis或者Kafka写入数据的同时，我们也写入到MySQL类似的备份表中，消息队列的消费者为主逻辑业务处理，当消息队列挂掉后，我们后台仍然有进程在处理消息，那就是后台线程去扫描备份表，然后进行处理，由于消息时幂等的，并且下游服务也是幂等的，所以可以并行的进行消费，当后台线程消费之后，同步到记录表，之后当消息队列恢复后，假设消费到已经消费的消息，此时发现该消息已经成功处理了，那么此时只需要进行ACK掉该消息就行了，从而保证服务的整体可用。
八、Redis持久化的实现原理以及主从同步原理
Redis持久化分为RDB快照持久化以及AOF日志文件追加命令方式去实现持久化的能力。
RDB持久化支持save和bgsave两种模式，效率上bgsave要更加高效一点，因为其实通过fork一个子进程来实现异步操作的，其不会阻塞主进程的执行客户端命令的过程。假设我们开启了bgsave的配置，在50S内如果有10次命令发生，那么我们就执行bgsave，此时主进程内核会将内存修改为 ReadOnly状态，此时子进程开发进行RDB备份，之后当主进程接收到新的写的命令时，其发现内存只支持读，不可写，此时其会重新加载Page到内存上，然后在将数据写入，而由于子进程和主进程内存共享，且子进程内存指向了主进程的内存，所以说当有新的命令时其只需要执行纳秒级别的寻址就可以了，也就是大名鼎鼎的CopyOnWrite。
AOF持久化可以通过配置AOF持久化的能力来支持Redis AOF持久化。其通过RESD协议明文写入到AOF文件中，来进行持久化。如果开启的是每秒AOF持久化，则可能会丢失一秒内的数据，如果每个命令都AOF持久化，那么整体性能则会降低。如果操作系统随机异步刷盘，那么可能会丢失数据。
**主从同步机制：**从节点在进行数据同步时，会先进行全量同步，然后在不断地进行增量同步。而全量同步时通过传输RDF文件之后，从节点开始解析RDB文件来实现阶段性的数据一致性。之后开始通过增量同步来进行数据一致性。主节点内部维护了一个缓冲区（默认2M），当全量同步时，会将命令也追加到这个缓冲区内，同时主节点维护了一个从节点同步的offset偏移量，当从节点开始增量同步时带来的offset在缓冲区内，此时则增量同步缓冲区内的内容，如果缓存区移除，offset不在缓冲区内，此时，从节点继续全量同步。以此类推。
如果我们发现从节点一致在全量同步，那么此时我们就需要条件这个缓冲区的大小，适当的调大一些，当数据一致性后，降低该数值，之后观察全量同步情况，在适当调节该缓冲区的大小。
九、Redis的集群模式和哨兵机制
Redis集群是通过哈希槽来进行数据分片，Redis将集群内分成16384个哈希槽，每一个Master节点都可以指定分配XXX-XXX哈希槽，同时每一个Master内部都维护了其他Master占用的哈希槽。当我们新增或者删除某一个Master时，其会平衡集群内的每一个Master节点的哈希槽，然后将结果同步到每一个Master上。之后客户端通过命令去在集群内操作时，如果链接的Master不包含本次请求的Key所在的哈希槽，此时会查找该哈希槽位于那个Master，之后会返回给客户端具体Master的信息，让客户端重新请求执行命令。
Redis的哨兵机制就是预防当Master节点挂掉之后，可以从其从节点中选择一个可用的节点作为Master节点对外提供服务。每一个Sentine都会监听所有的Master，同时所有的Sentinel内部会通过Pub/Sub组件一个Sentinel消息圈，用于信息同步。当某个Sentinel率先发现某个Master不通时，其会询问其他Sentinel，当其他Sentinel恢复也不通时，此时第一个发现的Sentinel作为本次选举的Leader Sentinel，其来推荐一个合适的从节点作为主节点继续对外服务。其优先选举最近刚刚通信的从节点来作为主节点。
十、Redis的过期Key实现原理
Redis的每一个DB其实都是一个字典，同理Redis针对每一个DB都维护了一个过期Key的字典，Key为带有过期时间的Key，Value为TTL。Redis的删除策略如下：
- 惰性删除：Redis在操作某个Key时，如果其发现是带有过期时间的，其会从过期时间的字典中找到过期时间，并判断是否过期，如果过期则会在本次访问中进行删除。存在一个弊端就是如果有大量的数据都没有进行访问，那么就会保存大量的不需要访问的数据在内存中。
- 随机删除：Redis支持针对某个DB进行随机删除一些已经过期的Key，由于其是单线程的，所以在删除时不能占用过长的时间去阻塞进程接受客户端的命令，所以其会随机删除某个DB中的一些过期Key。
当我们结合两种去删除过期时间的Key时，我们就可以在保证Reids吞吐能力的情况小去尽量减少过期数据的内存占用情况。
十一、如何理解MySQL用B+树作为索引的实现结构？
在大多数文件系统上，大部分都是采用的B+树来进行文件索引，这是由于其数据结构来定义的，其可以支持海量数据的情况下还能够降低磁盘IO的次数，所以说运用在大部分的文件系统上，而MySQL也是运用了这个特性。
B+树是B树的一种延伸数据结构，B树不仅仅只有叶子节点存储非索引相关的数据，其非叶子节点也会存储非索引相关的数据，这就会导致其树的高度增加，因为一个节点内存大小时固定的，当你存储了非索引相关的数据，那么存储的索引就会少，从而继续增加叶子节点，增加树的高度，而增加树的高度带来的反面效果就是增加磁盘IO次数。同理其在范围查找上的性能也是低于B+树的，在B树上进行范围查找的话，不仅仅要在当前命中的节点上进行比较，还要去查看所有该节点的子节点来继续进行范围比较，这不仅仅是增加了磁盘IO消耗，还增加了范围搜索的时间。
B+树在B树的基础上进行优化，其保证只在叶子节点上存储数据，而非叶子节点上只存储索引和下一个Page指针相关的数据，同时，在叶子节点上其增加了指向前一个节点和后一个节点的指针，也就是双链表，其在进行范围查询时是要比B树的性能高的。
MySQL中其数据都默认存储在主键索引上（如果行数据大于16K，那么就会存入到溢出页上。），叶子节点上的数据就是这一行的数据，既能够利用索引加速访问，也能避免回表进行多次IO。这个概念也称作聚簇索引。而非聚簇索引就是叶子节点不存储数据，而是存储指针，然后在通过指针去查行的数据。
如果我们本次要进行的Select命中了索引，但是要查询的字段刚好是索引字段，那么就可以直接返回给MySQL Server，从而返回给客户端，这个概念被称作索引覆盖。如果查询的字段不是命中的索引字段，那么就需要根据索引来去主键索引中回表找到对应的字段，这个概念被称作回表。
十二、MySQL的间隙锁
MySQL中支持间隙锁，也就是Gap Lock。我们尝试看看如下命令：select * from t where id >10 and id <20 for update; 当我们执行该命令时，MySQL会对 (10,20)加一个范围锁，也就是Gap Lock，此时当另外的事务执行 update t set id = 111 where id = 12;的时候，则会阻塞住，这个就是间隙锁生效。
如果当我们使用到了唯一索引时，间隙锁就会退化到行锁 Record Lock。如果索引时非唯一索引，那么我们可以很好的用间隙锁锁定一个范围，避免重复添加。如果是唯一索引，那么我们直接加Record Lock就好了。
十三、MVCC基本工作原理
MySQL针对每一行默认都增加了一个rtx_id字段，表示该行数据是被那个事务ID修改的，同时InnoDB维护了事务自增长的ID，每次当有事务时，通过该字段获取到事务ID。当我们在可重复读的隔离界别下，我们去执行快照读：select * from t where id > 10 and id <20;此时对于这个事务来说，其只能看到id在(10,20)范围内的数据，并且事务ID小于当前事务ID的数据，如果看不到 则根据roll_ptr回滚指针从undo log中找到历史的版本数据来进行查找，这个也就是所谓的快照读。其仍然存在幻读的情况：在一个事务中，我们先用快照读读取 (10,20) 范围内的数据，之后在修改 update t set id = 111 where id = 12;，之后在用当前读取读取（同一个事物），则将会读取不到id=12行数据，这个场景就是幻读。
而解决幻读就是通过针对事务内的操作添加排它锁或者共享锁来去解决幻读。
十四、Epoll、Poll、Select基本工作原理，如果自己封装Epoll客户端？自己封装Epoll客户端需要监听什么事件？
Select和Poll基本上都是类似的，其本质上都需要用户态将文件句柄拷贝到内核态，当内核态有时间到来时，在将文件句柄返回到用户态，用户态获取到之后，遍历有事件发生的文件句柄，然后开始执行。期间存在用户态到内核态的大量的文件句柄的拷贝以及需要在用户态循环遍历有事件发生的文件句柄。这在海量请求时资源有限的情况下是很浪费资源的。同时select只支持最大1024个文件句柄，而Poll可以支持无限个。
Epoll其避免了内核态到用户态的拷贝以及支持无限个文件句柄，其实现过程时：Epoll内部维护了一个红黑树存储文件句柄来管理交给Epoll的事件，当网卡收到数据包后发送硬中断通知CPU，CPU收到硬中断后触发软中断，避免占用过长的CPU。软中断会从RingBuffer中取出数据放入对应的Socket数据缓冲区，然后通过Epoll管理的红黑树找到对应的EpollItem来唤醒其等待的进程。之后用户态在EPOLL_WAIT阶段就能够获取到要本次时间，然后用户态执行数据的解包逻辑处理。
当我们自己封装Epoll客户端时，我们先创建Epoll实例，然后链接Server端，监听该Socket的读写事件之后，放入到Epoll实例中。之后我们进行Send的内容大于Socket缓冲区，之后我们进行EPOLL_WAIT，当我们发送的数据大于Socket缓冲区的话，内核会将多余的数据通过EPOLL_OUT事件通知给用户态，而在用户态我们就可以收到EPOLL_OUT的通知，之后当我们监听到该通知后，重新Send即可。
十五、为什么要三次握手？TIME_WAIT的含义？半链接队列和全连接队列什么时候会丢掉已经创建好的链接？
假设我们只需要二次握手就能够建立连接（缺少建立链接撤销机制），此时我们有一个场景客户端向服务端建立连接，由于网络原因，建立了2次，先后到达，此时第一次建立连接的请求由于网络抖动比第二次要慢，但是第二次已经先到服务端了，服务端认为链接OK，此时Seq都已经初始化了，如果2次就认为建立成功了，那么之后第一次到达服务端后，对比Seq发现不一致，那么链接会被销毁掉，如果该链接已经发送过数据此时不就乱了吗？ 所以在增加个第三次握手来进行确认机制来避免该情况。
当在连接断开时，主动断开的一方，在发送完最后一次挥手的信息后，将会进入TIME_WAIT状态，该状态会持续 2MSL，因为其为了避免最后一次ACK的消息和重发的消息都没有被被动关闭一方接受的话，此时数据包还在网络上传输，假设链接关闭，此时客户端和服务端针对同一个IP和端口建立了同一个链接之后，之前挥手的链接重新被新的链接复用，此时由于Seq不一致，将会导致SEQ乱序等。所以需要等待TIME_WAIT。而为了解决这个状态，我们可以支持端口服用或者降低MSL的时间，默认是60S，我们可以降低到30S，那么TIME_WAIT就是60S。
第一次握手成功，会在服务端创建文件句柄，并且进行初始化，之后放入到半链接队列中，当服务端收到第三次握手成功的信息后，会将该Socket从半链接队列中取出来存入到全连接队列，而全连接队列中的文件句柄已经是三次握手好的链接，已经是可以进行通信的链接了。之后我们执行accept()函数，将会从全连接队列中取出对应的文件句柄进行数据传输。
而当我们的半链接队列和全连接队列满了之后，新来的链接将会溢出，也就是被丢弃。我们通过如下命令查看半链接和全连接大小：参考文档：https://developer.aliyun.com/article/804896
# -n 不解析服务名称
# -t 只显示 tcp sockets
# -l 显示正在监听(LISTEN)的 sockets
[root@VM-12-2-centos ~]# ss -lnt
State Recv-Q Send-Q Local Address:Port Peer Address:Port
LISTEN 0 128 127.0.0.1:32772 *:*
LISTEN 0 128 *:3306
# 解释：
# Recv-Q：当前全连接里面等待被accept接受的大小
# Send-Q： 当前全连接队列大小
我们查看当前已经被丢弃掉的数据信息：
$ netstat -s | grep -i "listen"
189088 times the listen queue of a socket overflowed # 半链接溢出
30140232 SYNs to LISTEN sockets dropped # 全链接溢出
十六、LRU算法、八皇后
LRU算法参考自己实现的LRU本地缓存库：https://github.com/xmopen/golib/tree/master/pkg/localcache
八皇后：
// 面试题
func solveNQueens(n int) [][]string {
boards := make([][]int, n)
for i := 0; i < n; i++ {
boards[i] = make([]int, n)
}
var result = make([][]string, 0)
var dfs func(n, row int, boards [][]int)
dfs = func(n, row int, boards [][]int) {
if row == n {
// 当前深度结束,将当前站位记录标识下。
// 将当前boards规约成最终结果。
result = append(result, convertBoardToStringList(boards))
return
}
for col := 0; col < n; col++ {
if isValid(n, row, col, boards) {
//fmt.Printf("row:%v col:%v\n", row, col)
boards[row][col] = 1
temp := row + 1
dfs(n, temp, boards)
// 回溯，撤销皇后。
boards[row][col] = 0
}
}
}
dfs(n, 0, boards)
return result
}
// isValid 当前row、当前col是否
// n 表示是多少个皇后
// row 当前是多少行
// boards 当前棋盘。
func isValid(n, row, col int, boards [][]int) bool {
// 1、查看当前列是否存在皇后
for i := 0; i < row; i++ {
if boards[i][col] == 1 {
return false
}
}
// 2、查看45度是否有皇后
left, right := row-1, col-1
for left >= 0 && right >= 0 {
if boards[left][right] == 1 {
return false
}
left--
right--
}
// 3、查看135度是否有皇后
left, right = row-1, col+1
for left >= 0 && right < n {
if boards[left][right] == 1 {
return false
}
left--
right++
}
return true
}
// 1表示有皇后，置为Q,否则为.
func convertBoardToStringList(boards [][]int) []string {
tempResult := make([]string, len(boards))
for idx, board := range boards {
list := make([]string, len(board))
for index, value := range board {
if value == 1 {
list[index] = "Q"
continue
}
list[index] = "."
}
tempResult[idx] = strings.Join(list, "")
}
return tempResult
}
所有面经、后端开发文章会第一时间同步到个人博客以及公众号上。
个人博客：openxm.cn
个人公众号：社恐的小马同学