每日十题八股-2025年1月23日

1.快排为什么时间复杂度最差是O（n^2）
2.快排这么强，那冒泡排序还有必要吗？
3.如果要对一个很大的数据集，进行排序，而没办法一次性在内存排序，这时候怎么办？
4.面试官：你的项目为什么要用消息队列？
5.面试官：消息队列是怎么演进的？
6.面试官：Kafka架构长什么样的？
7.面试官：你说说 Kafka 为什么是高性能的？
8.面试官：RocketMQ 和 Kafka 有什么区别？
9.面试官：RocketMQ 为什么性能不如 Kafka？
10.面试官：Kafka 会丢消息吗？

1.快排为什么时间复杂度最差是O（n^2）

2.快排这么强，那冒泡排序还有必要吗？

对于小规模数据或基本有序的数据（冒泡可以通过判断本次遍历有没有交换元素来确定数组是否已经有序），冒泡排序可能比快速排序更简单、更直观。
稳定性。对于需要稳定性的场景，冒泡排序更适合。

3.如果要对一个很大的数据集，进行排序，而没办法一次性在内存排序，这时候怎么办？

大数据集划分成内存可实现内部排序（快排等，时间复杂度可以控制在O(nlogn)）的小数据集，然后归并排序（两两归并，每次读取两个小数据集的一部分，边排序变输出磁盘）。
败者树：归并阶段有个非常大的时间消耗就是 IO，也就是输入输出。最好就是让归并的层数越低越好，为了降低降低归并层数，可以使用败者树。

败者树是一种特殊的二叉树结构，用于归并排序中的多路归并。它通过比较多个数据源的当前最小值，逐步挑选出全局的最小值进行归并。败者树在归并排序中非常高效，尤其适用于多路归并。与逐一比较所有数据源的当前最小值相比，它的复杂度降低为 O(logk) (k 为数据源个数），因为树的高度为logk。

4.面试官：你的项目为什么要用消息队列？

在我们的项目中，使用消息队列主要是出于以下几个考虑：

第一，解耦。 项目中，模块之间原本耦合度较高，比如订单系统和库存系统的直接调用会导致双方改动时互相影响。引入消息队列后，订单系统只负责发送消息，库存系统只负责订阅消息，彼此独立，降低了耦合性，提高了系统的扩展性和维护性。

第二，异步处理。 有些操作不是必须实时完成，比如订单完成后发送通知短信或邮件。如果直接调用短信服务会导致用户等待时间变长，而通过消息队列将任务异步处理，订单接口的响应速度显著提升，提升了用户体验。

第三，削峰填谷。 在流量高峰期，比如秒杀活动，订单量会剧增。如果直接对后端系统施加压力，可能导致数据库崩溃。消息队列可以将请求暂存并按能力逐步消费，保护了后端系统的稳定性。

第四，可靠性保障。 消息队列支持消息持久化，即使消费者宕机，消息也不会丢失，保证了数据传递的可靠性。

总的来说，消息队列帮助我们实现了解耦、异步处理、流量削峰和可靠性保障，显著提高了系统的性能和稳定性，是项目中不可或缺的技术组件。

5.面试官：消息队列是怎么演进的？

消息队列的演进可以结合市面上的产品分为以下几个阶段：

第一阶段：初步引入消息队列（如 RabbitMQ）。
为了实现模块解耦和异步处理，项目开始使用消息队列。比如订单系统在完成订单后，将消息发送到 RabbitMQ 队列，通知短信或库存系统进行处理。这种方式显著降低了模块之间的耦合性，并提升了接口的响应速度。不过在初期，系统规模较小，RabbitMQ 的单机部署已经可以满足需求。

第二阶段：优化可靠性与高可用性（如 Kafka）。
随着业务增长，消息量激增，对高可用性和性能提出了更高要求。我们采用 Kafka 替代 RabbitMQ，因为 Kafka 支持消息持久化和分区机制，可以保证消息不会因为系统宕机丢失，同时支持大规模并发消费。比如在电商秒杀场景中，Kafka 可以通过削峰填谷机制，将瞬间的高并发流量缓冲下来，避免后端服务过载。

第三阶段：分布式消息队列（如 RocketMQ 和 Pulsar）。
当系统进一步扩展到分布式架构后，需要支持多数据中心和更低延迟的消息传递。例如，RocketMQ 支持灵活的消息重试机制和事务消息，适用于金融类场景，保证系统的最终一致性。而 Pulsar 支持多租户和分层存储，帮助降低存储成本的同时实现更高的性能。

第四阶段：云原生消息队列（如 Kafka on Confluent 和阿里云的 MNS）。
随着云计算的发展，越来越多的项目选择使用云原生的消息队列服务，比如 Kafka on Confluent 或阿里云的 MNS，这些服务提供了开箱即用的高可用性和自动扩展能力，大幅降低了运维成本，让开发者专注于业务逻辑实现。

总结： 从 RabbitMQ 到 Kafka，再到 RocketMQ、Pulsar，以及云原生服务，消息队列的演进不断解决性能、可靠性和分布式场景的挑战，为系统提供了解耦、异步处理和削峰填谷等能力，是现代分布式系统的重要支撑工具。

在 RabbitMQ 之前，确实存在一些早期的消息队列产品或概念，只是这些方案没有达到现代分布式消息队列的成熟度和广泛应用，以下是一些典型代表：

1. IBM MQ（前身是 MQSeries，1993年推出）：
   IBM MQ 是较早的企业级消息中间件，主要用于企业系统之间的消息传递和事务处理。它以强大的可靠性和事务支持著称，但价格昂贵，配置复杂，更适合大型企业的传统系统。

2. JMS（Java Message Service，1999年推出）：
   JMS 是 Java 平台的消息传递标准，支持点对点和发布订阅两种模式。像 ActiveMQ 是基于 JMS 的开源实现，适合早期小型分布式系统。但它在高并发场景下的性能和扩展性有限。

3. ActiveMQ（2004年推出）：
   ActiveMQ 是早期开源消息队列的代表之一，支持多种协议，兼容 JMS，易于部署。然而，ActiveMQ 在处理高并发和大规模场景时存在性能瓶颈，逐渐被更现代的产品（如 RabbitMQ 和 Kafka）取代。

4. RabbitMQ（2007年推出）：
   RabbitMQ 是消息队列发展的一个重要节点，它基于 AMQP 协议，专注于可靠消息传递和易用性，是现代轻量级消息队列的标杆产品。相比之前的方案，RabbitMQ 提供了更灵活的路由和更简单的管理。

总结： 在 RabbitMQ 之前，像 IBM MQ 和 ActiveMQ 等产品已经为消息队列打下了基础，但它们更偏向于传统的企业系统。而 RabbitMQ 开创了现代轻量级消息队列的先河，更适合互联网业务和微服务架构。

6.面试官：Kafka架构长什么样的？

生产者（Producer） 发送消息。
主题（Topic）和分区（Partition） 分类和分散存储消息。
Broker存储消息，支持高并发和高可用。
消费者（Consumer） 取出消息，完成业务逻辑。
Zookeeper 或元数据管理负责协调整个系统。
主分区和副本保证消息传递的可靠性和稳定性。
Kafka 就是靠这些部分紧密配合，高效地处理海量数据流动的！

1. Producer（生产者）：
   生产者就像“寄信人”，负责把消息（信件）发送到 Kafka 中的“主题”（类似于信箱）。比如一个电商系统，订单模块把“新订单消息”发到 Kafka 的订单主题里。

2. Topic 和 Partition（主题和分区）：
   主题（Topic）： 是消息的分类，比如订单消息会发到“订单主题”，日志消息会发到“日志主题”。
   分区（Partition）： 是为了“分开存放邮件”的格子。每个主题可以分成多个分区，分区让 Kafka 可以分散存储数据到不同的服务器上，从而支持高并发处理。
   作用：主题保证了消息的分类和管理。
   分区则通过分散存储，解决了“信件太多放不下”的问题，提升了处理速度。

3. Broker（代理）：
   Broker 是 Kafka 中的“邮递员”，它负责存储这些分区里的消息。Kafka 集群由多个 Broker 组成，每个 Broker 管理一部分分区。比如有 3 个 Broker，分区可能会分别分布在不同的 Broker 上，这样即使一个 Broker 坏了，其他的 Broker 还能继续工作。

4. Consumer（消费者）：
   消费者就是“收信人”，从主题中读取消息。比如“发货系统”作为消费者，会从“订单主题”里取出新订单，执行发货操作。
   如果有多个消费者组成消费组（Consumer Group），每个消费者会负责处理主题里的不同分区，避免重复处理。

5. Zookeeper（管理员）：
   可以把 Zookeeper 想象成 Kafka 的“协调员”，负责管理所有 Broker，比如监控哪个 Broker 存在哪些分区、哪个分区是主分区（Leader）等。新版本的 Kafka 开始使用内置的元数据管理，逐步替代 Zookeeper。

6. Leader 和 Replica（主分区和副本）：
   Kafka 里的每个分区都有一个主分区（Leader）和多个副本（Replica）。
   Leader 是负责读写的核心分区，比如“邮局的窗口”。
   副本是备份，当 Leader 坏了，Kafka 会从副本中选一个新 Leader，保证消息不会丢失。

7.面试官：你说说 Kafka 为什么是高性能的？

1. 高吞吐量的消息存储： 顺序写入
Kafka 将消息以日志的形式存储在磁盘中，每条消息都附带一个偏移量，Kafka 是通过顺序写入磁盘来实现高吞吐量的。这种顺序写入比随机写入要快得多，因为磁盘顺序写入比随机写入更高效，尤其是对于大数据量的处理。

2. 分区和并行处理：
   Kafka 的每个主题（Topic）可以划分成多个分区（Partition）。每个分区可以分布在不同的机器上，意味着多个生产者和消费者可以并行工作，提高了系统的吞吐量。分区是实现水平扩展的关键，通过分区 Kafka 能够分散负载，避免单点瓶颈。

3. 零拷贝：网络传输，数据不进入用户空间了sendfile
   

4. 高效的网络传输： 批量发送和消费，并且可以消息压缩。
Kafka 在传输数据时，采用批量处理方式。生产者会先将多条消息积攒成一个大的批次，然后一次性发送到 Kafka 集群。这样可以减少网络请求的频率，减少网络延迟，提高数据传输效率。同时，消费者也可以批量拉取消息，进一步提升性能。

5. 消息持久化和日志压缩：
   Kafka 默认将消息持久化到磁盘，并且支持高效的日志压缩。持久化机制使得即使系统崩溃，也能保证数据不会丢失。而日志压缩和保留策略保证了长期存储的消息在不占用过多空间的情况下依然能高效存储。

6. mmap
   Kafka 的日志文件分为数据文件(.log)和索引文件(.index)，Kafka 为了提高索引文件的读取性能，对索引文件采用了 mmap 内存映射，将索引文件映射到进程的内存空间，这样读取索引文件就不需要从磁盘进行读取。？（后面的回答又说是sendfile，RocketMQ用得是mmap）

7. 扩展性：
   Kafka 支持水平扩展，添加更多的 Broker 以增加集群的存储容量和处理能力。每个分区可以分布到不同的 Broker 上，这使得 Kafka 可以非常灵活地适应不断增长的负载。

总结：
Kafka 之所以高性能，是因为它通过顺序写入磁盘、分区机制、批量处理、日志压缩等技术，最大化地提高了存储、网络传输和处理的效率。并且，Kafka 通过分布式设计和水平扩展，能够在处理大规模数据时保持高吞吐量和低延迟。

8.面试官：RocketMQ 和 Kafka 有什么区别？

1. 消息的组织方式：
   Kafka：
   Kafka 可以把消息分成多个分区（Partition），每个分区就像一个“消息箱”。多个生产者把消息发到不同的分区，消费者也可以并行地从多个分区读取消息。分区使得 Kafka 能处理很多消息，效率高。

RocketMQ：
RocketMQ 也是分分区，但它支持两种模式：一种是发布-订阅模式，类似广播，多个消费者可以同时收到消息；另一种是点对点模式，一个消息只能被一个消费者消费。你可以根据业务需求选择模式。

2. 消息的顺序：
   Kafka：
   Kafka 能保证同一个分区内的消息顺序，意思是如果你把消息放在一个分区里，它们的消费顺序是不会乱的。但不同分区之间的消息顺序没有保证。

RocketMQ：
RocketMQ 也能保证消息的顺序，甚至比 Kafka 更灵活。如果你有严格顺序要求的消息，RocketMQ 可以为你提供更多选择。

3. 性能和吞吐量：
   Kafka：
   Kafka 主要的优势就是高性能。它能处理非常大的数据量和高并发的消息，非常适合大数据、日志收集等场景。

RocketMQ：
RocketMQ 性能也不错，但它的优势在于提供了更多不同的功能，比如支持事务消息和延迟消息。也就是说，如果你的业务需要确保消息的可靠性或者需要一些特殊处理，RocketMQ 可能会更适合。

4. 可靠性和容错：
   Kafka：
   Kafka 通过将消息复制到多个服务器（副本）来保证可靠性，如果某个服务器出问题，消息也不会丢失。

RocketMQ：
RocketMQ 也通过类似的方式保证消息的可靠性，采用“主从”结构，确保消息不会丢失。

5. 应用场景：
   Kafka：
   Kafka 适合用在大数据处理、日志收集和流式数据处理等场景。它非常擅长高并发、海量数据的场景。

RocketMQ：
RocketMQ 更适合需要确保消息顺序、需要事务保证或者需要定时/延迟处理的场景。比如在金融系统中，可能需要保证某些消息的顺序和事务性。

总结：
Kafka： 高吞吐量，适合大规模数据流，尤其是处理日志和实时数据流。
RocketMQ： 更加灵活，支持事务、延迟等特殊场景，适合对消息顺序和可靠性有高要求的场景。
换句话说，如果你要处理大规模的数据流，Kafka 是个好选择；如果你需要确保消息的顺序或有特殊的处理需求（比如延迟消息），那 RocketMQ 会更适合你。

9.面试官：RocketMQ 为什么性能不如 Kafka？

RocketMQ 性能不如 Kafka 主要是因为：

Kafka 在设计上非常注重高吞吐量和高并发，使用了顺序写入磁盘、分区和高效的消息存储方式，这使得它能够处理大规模的数据流。
RocketMQ 虽然也具备高吞吐量，但它提供了更多的功能（如事务消息、延迟消息等），这些附加功能会增加系统的复杂性，从而影响其整体性能。

聊完两种零拷贝技术，我们回过头来看下 kafka 为什么性能比 RocketMQ 好。这是因为 RocketMQ 使用的是 mmap 零拷贝技术（4变3），而 kafka 使用的是 sendfile(4变2)。kafka 以更少的拷贝次数以及系统内核切换次数，获得了更高的性能。

10.面试官：Kafka 会丢消息吗？

1. 消息丢失场景：
   （1）生产者丢消息
   原因：
   如果生产者将消息发送给 Kafka 时，设置的 acks 参数值过低（如 acks=0），生产者不会等待 Kafka 的确认，即使消息没被成功写入 Broker，生产者也认为发送成功，从而可能导致消息丢失。

解决方法：
设置 acks=all（或 acks=-1），生产者会等待所有副本写入成功后才确认消息发送完成。
使用 retries 参数，让生产者在写入失败时自动重试。
开启 idempotence（幂等性），以避免消息重复或丢失。

（2）Broker 丢消息
原因：
Kafka 将消息写入内存后，默认是异步刷盘到磁盘。如果在消息刷盘前 Broker 宕机，内存中的消息可能丢失。
如果 Kafka 的副本同步机制未完成（如设置 min.insync.replicas 太低），且 Leader 节点出现故障，可能导致消息丢失。

解决方法：
设置 min.insync.replicas=2 或更高值，确保消息写入至少两个副本时才算成功。
将 log.flush.interval.messages 和 log.flush.interval.ms 调小，确保消息更快刷盘，但可能会影响性能。
部署可靠的 Kafka 集群，避免节点故障。

（3）消费者丢消息
原因：
消费者收到消息后还未处理完，就向 Kafka 提交了偏移量。如果消费者在处理消息时宕机，已提交的消息无法重新消费，从而导致消息丢失。
消费者组在 Rebalance 时，未正确管理消费偏移量，可能导致部分消息未被消费。

解决方法：
将 enable.auto.commit 设置为 false，手动提交消费偏移量，在消息处理完成后再提交偏移量。
使用 exactly-once 语义，确保消息处理和偏移量提交的原子性。

2. Kafka 的可靠性机制：
   Kafka 提供了一些机制来最大限度减少消息丢失：
   副本机制（Replication）：
   每个分区的消息会被复制到多个 Broker。即使 Leader 副本宕机，Follower 副本可以接替 Leader，确保数据不丢失。
   幂等性（Idempotence）：
   生产者开启幂等性后，可以确保每条消息仅写入一次，即使生产者重试也不会重复写入或丢失消息。
   事务（Transactions）：
   Kafka 支持事务，可以保证消息从生产者发送到消费者之间的端到端可靠性，确保 “exactly-once” 消费。

3. 总结：Kafka 会不会丢消息？
   Kafka 并不能完全避免丢消息，但通过合理配置和优化，可以尽量避免丢失：
   生产者配置：
   设置 acks=all，启用幂等性（enable.idempotence=true）。
   Broker 配置：
   配置更高的副本数量和 min.insync.replicas，并确保定期刷盘。
   消费者配置：
   禁用自动提交偏移量，使用手动提交，确保消息处理完成后提交偏移量。
   使用事务：
   对需要严格可靠性保证的场景，开启事务功能。
   通过这些措施，可以让 Kafka 在实际使用中做到尽量减少消息丢失，并满足绝大多数业务场景的可靠性需求。