分布式系统

什么是CAP定理？

Consistency一致性：每次读取都会收到最近的写入或错误。

Availability可用性：每个请求都会收到一个（非错误）响应，但不能保证它包含最新的写入。

Partition tolerance分区容错性：每个请求都会收到一个（非错误）响应，但不能保证它包含最新的写入。

CAP 定理，指出，任何分布式数据存储只能提供以下三个保证中的两个。

在CAP定理中，一般是在哪两个之间进行选择？为什么？一般会怎么选择？

如果存在网络分区，就必须在一致性和可用性之间做出选择。

如果发生网络分区故障时，要么取消操作，减低可用性，但保证一致性，要么继续操作，从而提供可用性，但存在风险。所以基本上分区容错性是要保证的。

大多数基于微服务的场景需要可用性和高可扩展性，而不是强一致性。

CAP定理，牺牲了一致性，如何解决一致性问题？

通过使用处理弱一致性或最终一致性的技术来解决强一致性问题。这是大多数基于微服务的架构所采用的方法。

解决此问题的一个好的解决方案是在通过事件驱动通信和发布订阅系统连接的微服务之间使用最终一致性。

CAP分布式系统中如何保证C或者A或者P？

保证C（一致性）：要求分布式系统中的数据在任何时刻都是一致的。为了实现C，可以采用ACID强一致性的数据库系统，如传统的关系型数据库，或者使用分布式事务来确保数据一致性。

保证A（可用性）：要求分布式系统在面对网络故障等异常情况时，仍然能够提供服务。为了实现A，可以采用分布式缓存、负载均衡、故障转移等机制来确保系统的高可用性。

保证P（分区容忍性）：要求分布式系统在面对网络分区（网络故障导致节点之间无法通信）时，仍能够继续运行。为了实现P，可以采用复制、数据分片、分布式一致性算法等手段来保证系统的分区容忍性。

什么是故障转移机制？

故障转移机制是指在分布式系统中，当某个节点或组件发生故障时，系统能够自动或者通过手动干预，将受影响的服务迁移到其他可用节点或者恢复到正常状态，以保证系统的可用性和稳定性。

故障转移机制一般采取以下一些策略和技术？

主从备份

负载均衡: 节点健康监控，流量分配或转发

故障检测: 通过心跳检测、健康监控

什么是一致性哈希算法？

一致性哈希（Consistent Hashing）是一种用于分布式系统中数据分片和负载均衡的算法。它的主要目标是在动态增加或减少服务器节点时，尽可能地减少需要重新映射的数据量。

利用一致性哈希算法增加一个节点需要重新缓存多少的数据？

在一致性哈希算法中，当需要增加一个节点时，只有部分数据会受到影响，因此只需重新缓存少量的数据。具体来说，在一致性哈希环上，新增一个节点将会影响该节点之后直到下一个节点之间的数据映射关系。

假设原本有 n 个节点，每次新增一个节点后，需要重新映射的数据量约为总数据量的 1/n。这是因为每个节点负责的数据范围大致为整个哈希环的 1/n 部分。

由于一致性哈希算法的特性，增加节点只会影响部分数据的映射，且影响范围随着节点数量的增加而减小。这使得一致性哈希在动态扩展和收缩节点时能够提供高效的数据重新映射，保证了系统运行的平稳性和性能稳定性。

Raft算法的核心思想是什么？

Raft 算法的核心思想是设计一种易于理解和实现的分布式共识算法，用于管理复制日志的一致性问题。它可以在分布式系统中提供强一致性保证，并且相对于 Paxos 算法更容易理解和实现。

Raft 算法的核心思想包括以下几点：

  • 领导选举：Raft 将时间划分为一系列的任期（terms），在每个任期中通过选举产生一个领导者（leader）。只有领导者才能接收客户端的请求并广播日志。
  • 日志复制：领导者负责向其他节点复制日志条目。一旦大多数节点都确认了某个条目，它就会成为已提交的日志，并通知其他节点进行应用。
  • 安全性：Raft 保证若干安全特性，例如领导者独占、递增的日志复制以及不会发生冲突的日志应用。

    • 分割和重新连接：当出现网络分割或者重新连接时，Raft 能够自动地进行领导者选举，从而确保整个系统的一致性。

如何设计一个通知中心？向几千万用户推送消息？
什么是两阶段提交？

两阶段提交（Two-Phase Commit，2PC）是一种分布式系统中用于保证事务的原子性和一致性的协议。它包括准备阶段和提交阶段，用于协调多个参与者节点以确保事务在所有节点上要么全部提交，要么全部回滚。

下面是两阶段提交的基本流程：

  1. 准备阶段：协调者节点向所有参与者节点发送事务准备请求。参与者节点接收到请求后，执行事务并写入redo和undo日志，然后向协调者发送“投票”是否可以提交事务。
  2. 提交阶段：如果所有参与者节点都投票同意，协调者节点向所有参与者节点发送提交请求。参与者节点接收到提交请求后，执行事务提交操作并释放资源，并向协调者节点发送完成消息。如果任何一个参与者节点出现问题或者拒绝提交，协调者节点会向所有节点发送回滚请求。
为什么会有DDD，为什么用DDD
建造者模式是什么，什么时候会用
跟原型模式有什么区别？

Big Data Processing / 大文件

处理海量数据问题，无非是：

  • 分而治之、Hash映射、Hash统计、堆/快速/归并排序
  • 双层捅划分
  • 布隆过滤器/Bitmap
  • Tire树/数据库/倒排索引
  • 外排序
  • 分布式处理之Hadoop/Mapreduce

秒杀

秒杀项目需要考虑的主要问题？
  • 高并发和性能： 秒杀活动会引起瞬时的高并发访问，因此系统需要具备良好的承载能力和性能，包括数据库、缓存、网络等方面的优化。
  • 库存和订单处理： 需要合理处理商品库存，避免超卖和负库存情况，同时要保证订单的正确性和一致性。
  • 分布式事务： 秒杀过程中涉及到下单、扣减库存等多个操作，需要考虑如何实现分布式事务，确保数据的一致性和完整性。
  • 限流和熔断： 针对突发的请求，需要设置合理的限流策略和熔断机制，避免系统崩溃或无响应。
  • 消息队列： 可以考虑使用消息队列来削峰填谷，将请求和处理进行解耦，提高系统的吞吐量和可靠性。
  • 缓存优化： 合理利用缓存技术，例如 Redis 缓存，来减轻数据库压力，提高读写效率，降低系统响应时间。
秒杀项目如何解决超卖问题？
  • 悲观锁： 在数据库层面使用悲观锁，例如通过数据库事务的行级锁或者 select ... for update 的方式来保证在更新库存时不会出现并发读写问题。
  • 乐观锁： 使用乐观锁机制，在更新库存时先查询当前库存，然后判断是否足够，再进行更新。可以利用数据库的版本控制字段或者类似 CAS（Compare And Set）的原子操作来实现。
  • 分布式锁： 使用分布式锁，例如基于 Redis 或者 ZooKeeper 的分布式锁，确保同一时间只有一个请求能够扣减库存，避免并发导致超卖问题。
  • 预减库存： 在秒杀开始前，可以将商品库存提前加载到内存中，并在内存中进行减库存操作。这样可以避免瞬时高并发下频繁地访问数据库，提高系统吞吐量，同时能够更好地控制库存，避免超卖。
  • 限流和队列： 设置合理的请求限流策略，确保系统在高并发情况下不会受到过多请求的冲击。可以借助消息队列来对请求进行排队处理，从而平滑吞噬请求。
  • 活动规则设计： 合理设计秒杀活动规则，例如单用户限购数量、总库存数量限制等，来避免超卖情况。

本质上是做拦截请求，限流。

前端页面抢购按钮静止短时间内频繁点击，前端JS禁止短时间频繁请求。

网关拦截请求，禁止同一个IP短时间内频繁请求。

秒杀系统因为商品库存少，读取库存多，修改库存少，读多写少，所以使用redis存储库存，所以从redis层可以大量减少负载。

Redis存放库存数，先去 Redis 中扣减库存，扣减成功才能继续更新数据库。这样，最终到的数据库的请求数目和需要售卖商品的数目基本一致，数据库的压力可以大大减少。

通常情况下，我们需要在redis中保存商品信息，里面包含：商品id、商品名称、规格属性、库存等信息，同时数据库中也要有相关信息，毕竟缓存并不完全可靠。

Redis 是不支持事务的，会出现扣减为负的情况，

分布式锁： 使用分布式锁，例如基于 Redis 或者 ZooKeeper 的分布式锁，确保同一时间只有一个请求能够扣减库存，避免并发导致超卖问题。

后端异步处理，消息队列、并发控制。

经过Redis库存扣减判断后，使用MQ扣减库存并生成订单。

秒杀服务与订单服务之间要做成mq异步通信的。

使用事务发件箱防止网络问题和消息队列问题带来的消息丢失，事件处理服务进行消息重传机制。下单和发件箱表要是同一个事务，保证原子操作。

订单服务读取消息，防止网络问题带来的重复消费问题，可以类似的做事件收件箱，防止消息重复消费的问题。消费者收到消息时判断收件箱是否已存在，已存在则重复消费，不做处理。

支付服务就不用动了。

针对未支付或取消订单情况做延迟队列，延迟队列的消费者负责取消订单，并增加库存。

消息队列如何保证数据的最终一致性？

以下是一些常见的方法：

  • 事务消息： 一些消息队列系统支持事务消息，在发送消息时可以使用事务来确保消息的可靠传递和处理。只有当消息被确认处理成功后，事务才会提交，否则消息会被回滚。
  • 消息确认机制： 消费者在处理完消息后向消息队列发送确认，消息队列收到确认后才会将消息标记为已消费。如果消费者在处理消息时发生异常，可以通过重试或者死信队列来处理未确认的消息。
  • 幂等性处理： 在处理消息的业务逻辑中，要尽量保证幂等性，即同样的消息多次处理结果应该是一致的。这可以通过唯一标识符、版本号、状态机等方式来实现。
  • 补偿机制： 如果消息处理失败，可以通过补偿机制来进行处理。例如，可以将处理失败的消息移动到一个专门的死信队列中，然后定时或手动重新处理这些消息。
  • 分布式事务： 对于一些分布式事务场景，可以使用分布式事务协议（如 TCC、Saga 等）来保证消息发布和消息消费的最终一致性。
  • 监控和报警： 针对消息队列的异常情况，需要设置监控指标和报警机制，及时发现并处理异常情况。

以上方法综合使用，可以有效地保证消息队列中数据的最终一致性。在设计消息队列应用时，还需根据具体业务场景和系统需求，选择合适的技术方案和机制来保证数据一致性。

场景设计

设计一个微博的粉丝关注功能，给出数据表的设计，系统的各个功能模块设计，完整的流程

数据表设计：用户表（User）：user_id、username、email、password

数据表设计：微博表（Weibo）：weibo_id、user_id、content、create_time

数据表设计： 粉丝关系表（Follow）：follow_id、follower_id、following_id

系统功能模块设计：用户管理模块：负责用户的注册、登录、个人信息管理等功能。

系统功能模块设计：微博发布模块：允许用户发布新的微博内容。

系统功能模块设计：包括关注用户、取消关注用户、查看关注列表、查看粉丝列表等功能。

关注操作：用户在粉丝关注模块中选择关注其他用户，将相应的关注关系写入到关注关系表中。查看关注列表：用户可以查看自己已关注的用户列表。查看粉丝列表：用户可以查看关注自己的粉丝列表。取消关注：用户可以取消已关注的用户，从关注关系表中删除相应的关系记录。

在抖音直播中会有弹幕流，现在要对弹幕流中的 k 条弹幕进行抽奖，如何保证中奖概率是公平的，限制: 每条用户只能发一条弹幕；空间复杂度 O(1)；中奖概率公平

要保证中奖概率公平且限制空间复杂度为 O(1)，可以使用蓄水池抽样（Reservoir Sampling）算法。蓄水池抽样是一种用于从未知大小的数据流中随机抽样的算法，适用于限制空间复杂度的场景。

下面是如何使用蓄水池抽样算法对弹幕流中的 k 条弹幕进行抽奖：

  • 初始化一个大小为 k 的蓄水池数组（reservoir）用于存储抽样结果。
  • 依次读取弹幕流中的弹幕，对于第 i 条弹幕（i > k），以 1/i 的概率将其放入蓄水池中，同时以 k/i 的概率随机替换蓄水池中的一条弹幕。
  • 最终蓄水池中的 k 条弹幕即为抽奖的中奖弹幕。

通过蓄水池抽样算法，每条弹幕都有相同的被选中的概率，保证了中奖概率的公平性。并且蓄水池的大小是固定的，不随着数据流的增长而增加，因此满足了 O(1) 的空间复杂度限制。

高并发大数据量系统的开发与维护

规则引擎应用背景

缓存

消息队列

异步任务

负载均衡

分库分表

什么是 Raft协议？

一种分布式一致性算法（共识算法）

几个T的大文件,包含用空格分隔的字符串,确定一共有多少种不同的字符串 考虑大部分字符串都不一样的情况

高并发系统 1.redis和mysql一致性策略？先删mysql 再删redis 2.存在不一致的情况吗？存在 mysql删除成功 redis删除失败 3.怎么解决？kafka消息队列实现分布式事务 两段提交 4.并发量多少？ 5.布隆过滤器底层原理 为什么用三个哈希函数 使用场景

问有一个敏感词过滤系统，我们也有一个敏感词库，如何快速的检测一个句子里是否有敏感词

怎么保证分布式数据的一致性

举了个分布式数据库的例子，说可以用日志来记录数据库的修改，然后比对日志就知道是不是一样的

案例是让给微信的朋友圈评论功能设计后端的数据库

用一个锁实现共享锁

一个系统设计，排名系统。各种表怎么设计，应该怎么加缓存啥的。

1T文件，每一行都是一个数字，求出现次数最多的topK?

  1. 内存不限制 （我说了堆）然后问堆的插入时间复杂度是多少？
  2. 如果内存有限，比如2G内存，全部文件放入统计词频，内存可能不够用。见收藏夹 哈希→分治→归并

“大文件断点续传”

秒杀系统

会一个超复杂的dp / 树状数组 / 线段树，不如面试之前写一个三路快排有点儿印象。

现有100亿个QQ号，如何快速判断某个QQ号是否在其中，存储方式自己考虑，越快越好（运行时间），空间越小越好。

假设网络会丢失消息，进程可能意外终止，磁盘可靠（写入数据后不会丢失）； 问： 如何构建一个可靠的分布式key-value存储系统？ 答题要求如下： 1.客户端向系统发送1条写入请求(例如key=x, value=1)，系统返回'成功'，客户端一定可以正确读取到key=y的值 2.在你设计的系统中，要满足上面第1条，并有一定对故障的容错能力。 3.如果要尽可能提高写入或读写成功率，如果改进系统设计？分别会有哪些问题？

构建一个可靠的分布式 key-value 存储系统是一个复杂而且需要深思熟虑的任务。以下是一些步骤和关键概念，可以帮助你构建这样的系统：

  1. 数据分片：将数据分成多个部分（分片），并存储在不同的节点上。这有助于提高系统的扩展性。
  2. 一致性哈希：使用一致性哈希算法来确定数据应该存储在哪个节点上。这有助于在节点动态加入或离开时减少数据迁移的影响。
  3. 复制：为了提高容错能力，可以考虑在不同的节点上复制数据。这有助于防止在节点故障时数据丢失。
  4. 故障检测和恢复：实现机制来检测节点故障，并在需要时自动进行故障转移或数据恢复。
  5. 负载均衡：确保数据和负载在各个节点间均匀分布，避免出现单点过载情况。
  6. 一致性和持久性：确保系统在面对并发写操作时能够保持数据的一致性，并且对数据的写入具有持久性。
  7. API 设计：设计友好且易用的 API，以便客户端可以方便地访问和使用存储系统。
  8. 安全性：采取安全措施，如访问控制和数据加密，以确保数据在传输和存储过程中的安全性。
  9. 监控和日志：实现监控系统和日志记录，以便及时发现问题并进行故障排查。
  10. 测试：进行充分的测试，包括单元测试、集成测试和压力测试，以验证系统的可靠性和性能。

以上仅是构建分布式 key-value 存储系统的一些基本指导原则。实际上，这需要综合考虑系统设计、网络通信、存储引擎、并发控制等多个领域的知识。

模拟TCP吧 发个syn 回个ack，同时保存心跳，不回的话一定时间内重传，几个心跳不回，表示链路断开。再用deamon进程来守护工作进程

比如使用集群或者说环，对数据进行分片，用p2p协议来进行数据复制。

起一个线程，用事务来绑所有的操作，直至最后写入成功，返回成功响应给客户端，中间任何一步失败，事务回滚，返回写入失败响应报文。第二，最好保证读写不在一台机器上，因为磁盘io很耗时，一般的做法，都是前面放个缓存，比如memcache，因为热点数据都在内存，这样保证读取很快。但是这样的设计会导致两个问题，一是读库和写库同步问题。前面说过，消息会丢失，那么依靠消息来同步数据就会有问题，二是写入成功率也不咋地。

服务器端进程意外退出的解决办法可参考各daemon服务器的做法，细节很多，基本步骤一般会有： 1. 设计启动时写pid文件，正常退出时最后清除pid文件。 2. 设计控制文件确保事务完整性，将收发读写设计成一个完整的事务，对事务的每一步写控制文件日志。 3. 避免被kill意外退出：抓退出信号如0, 并将未完成的事务完成，再正常退出。 4. 如果已经意外退出：进程启动时判断是否上次意外退出（pid文件），发现意外退出，分析控制文件里是否有不完整事务，发现先进行修复过程再提供服务。

系统有 data node 和 manager node两种角色，data node 负责数据的存取，manager node 负责数据的平衡工作，保证数据能同步到多台 data node（处理 data node 宕机，集群扩容情况）。用 zookeeper 保存当前的 data node 信息和配置信息（hash规则）。client 访问 zookeeper 得到自己的数据该写到哪些机器上，然后再访问 data node 将数据写入（可以同步将数据同步到多台 data node，也可以由 manager node 异步同步）。client 读数据的流程和写入类似，比写入更简单。