美团基架,我先开冲了!

小林coding

共 10628字,需浏览 22分钟

 ·

2024-06-22 15:27

图解学习网站:https://xiaolincoding.com

大家好,我是小林。

互联网大厂的后端开发中,主要是以 Java 和 Go 为主,Java 大厂主要是阿里巴巴、美团、快手、京东等,Go 大厂是腾讯、字节跳动、滴滴、百度等,当然腾讯还是有部分部门用 C++ 做后端开发。

整体上而言 C++ 后端开发岗位会比较少,但是互联网大厂还有基础架构岗位,这类岗位使用的语言大多数就是 C++,面向的是比较底层的技术和框架。

基础架构面试主要考察底层知识比较多,比如Linux 操作系统和网络,而后端组件考察相对较少一些。

今天就分享一位同学面试美团的基础架构部门的面经,主要考察了 C++、Redis、网络、操作系统。

问题虽然不算多,但是都是问的比较底层,大家看看难度如何?

Redis

Redis 为什么是单线程?

Redis 单线程指的是「接收客户端请求->解析请求 ->进行数据读写等操作->发送数据给客户端」这个过程是由一个线程(主线程)来完成的,这也是我们常说 Redis 是单线程的原因。官方使用基准测试的结果是,单线程的 Redis 吞吐量可以达到 10W/每秒,如下图所示:之所以 Redis 采用单线程(网络 I/O 和执行命令)那么快,有如下几个原因:

  • Redis 的大部分操作都在内存中完成,并且采用了高效的数据结构,因此 Redis 瓶颈可能是机器的内存或者网络带宽,而并非 CPU,既然 CPU 不是瓶颈,那么自然就采用单线程的解决方案了;
  • Redis 采用单线程模型可以避免了多线程之间的竞争,省去了多线程切换带来的时间和性能上的开销,而且也不会导致死锁问题。
  • Redis 采用了 I/O 多路复用机制处理大量的客户端 Socket 请求,IO 多路复用机制是指一个线程处理多个 IO 流,就是我们经常听到的 select/epoll 机制。简单来说,在 Redis 只运行单线程的情况下,该机制允许内核中,同时存在多个监听 Socket 和已连接 Socket。内核会一直监听这些 Socket 上的连接请求或数据请求。一旦有请求到达,就会交给 Redis 线程处理,这就实现了一个 Redis 线程处理多个 IO 流的效果。

Redis 持久化有哪些方式?

Redis 提供了 3 种写回硬盘的策略, 在 Redis.conf 配置文件中的 appendfsync 配置项可以有以下 3 种参数可填:

  • Always,这个单词的意思是「总是」,所以它的意思是每次写操作命令执行完后,同步将 AOF 日志数据写回硬盘;
  • Everysec,这个单词的意思是「每秒」,所以它的意思是每次写操作命令执行完后,先将命令写入到 AOF 文件的内核缓冲区,然后每隔一秒将缓冲区里的内容写回到硬盘;
  • No,意味着不由 Redis 控制写回硬盘的时机,转交给操作系统控制写回的时机,也就是每次写操作命令执行完后,先将命令写入到 AOF 文件的内核缓冲区,再由操作系统决定何时将缓冲区内容写回硬盘。

我也把这 3 个写回策略的优缺点总结成了一张表格:

RDB 快照是如何实现的呢?

因为 AOF 日志记录的是操作命令,不是实际的数据,所以用 AOF 方法做故障恢复时,需要全量把日志都执行一遍,一旦 AOF 日志非常多,势必会造成 Redis 的恢复操作缓慢。

为了解决这个问题,Redis 增加了 RDB 快照。所谓的快照,就是记录某一个瞬间东西,比如当我们给风景拍照时,那一个瞬间的画面和信息就记录到了一张照片。

所以,RDB 快照就是记录某一个瞬间的内存数据,记录的是实际数据,而 AOF 文件记录的是命令操作的日志,而不是实际的数据。

因此在 Redis 恢复数据时, RDB 恢复数据的效率会比 AOF 高些,因为直接将 RDB 文件读入内存就可以,不需要像 AOF 那样还需要额外执行操作命令的步骤才能恢复数据。 

Redis 提供了两个命令来生成 RDB 文件,分别是 save 和 bgsave,他们的区别就在于是否在「主线程」里执行:

  • 执行了 save 命令,就会在主线程生成 RDB 文件,由于和执行操作命令在同一个线程,所以如果写入 RDB 文件的时间太长,会阻塞主线程
  • 执行了 bgsave 命令,会创建一个子进程来生成 RDB 文件,这样可以避免主线程的阻塞

混合持久化

在 Redis 4.0 提出了混合持久化。如果想要开启混合持久化功能,可以在 Redis 配置文件将下面这个配置项设置成 yes:

aof-use-rdb-preamble yes

混合持久化是工作在 AOF 日志重写过程。当开启了混合持久化时,在 AOF 重写日志时,fork 出来的重写子进程会先将与主线程共享的内存数据以 RDB 方式写入到 AOF 文件,然后主线程处理的操作命令会被记录在重写缓冲区里,重写缓冲区里的增量命令会以 AOF 方式写入到 AOF 文件,写入完成后通知主进程将新的含有 RDB 格式和 AOF 格式的 AOF 文件替换旧的的 AOF 文件。 

也就是说,使用了混合持久化,AOF 文件的前半部分是 RDB 格式的全量数据,后半部分是 AOF 格式的增量数据

这样的好处在于,重启 Redis 加载数据的时候,由于前半部分是 RDB 内容,这样加载的时候速度会很快

加载完 RDB 的内容后,才会加载后半部分的 AOF 内容,这里的内容是 Redis 后台子进程重写 AOF 期间,主线程处理的操作命令,可以使得数据更少的丢失

介绍一下 Redis 中的 listpack

quicklist 虽然通过控制 quicklistNode 结构里的压缩列表的大小或者元素个数,来减少连锁更新带来的性能影响,但是并没有完全解决连锁更新的问题。因为 quicklistNode 还是用了压缩列表来保存元素,压缩列表连锁更新的问题,来源于它的结构设计,所以要想彻底解决这个问题,需要设计一个新的数据结构。

于是,Redis 在 5.0 新设计一个数据结构叫 listpack,目的是替代压缩列表,它最大特点是 listpack 中每个节点不再包含前一个节点的长度了,压缩列表每个节点正因为需要保存前一个节点的长度字段,就会有连锁更新的隐患。

listpack 采用了压缩列表的很多优秀的设计,比如还是用一块连续的内存空间来紧凑地保存数据,并且为了节省内存的开销,listpack 节点会采用不同的编码方式保存不同大小的数据。我们先看看 listpack 结构:


listpack 头包含两个属性,分别记录了 listpack 总字节数和元素数量,然后 listpack 末尾也有个结尾标识。图中的 listpack entry 就是 listpack 的节点了。每个 listpack 节点结构如下:


主要包含三个方面内容:

  • encoding,定义该元素的编码类型,会对不同长度的整数和字符串进行编码;
  • data,实际存放的数据;
  • len,encoding+data的总长度;

可以看到,listpack 没有压缩列表中记录前一个节点长度的字段了,listpack 只记录当前节点的长度,当我们向 listpack 加入一个新元素的时候,不会影响其他节点的长度字段的变化,从而避免了压缩列表的连锁更新问题

网络编程

select 和 epoll 的区别,epoll 的底层数据结构

IO多路复用是一种IO得处理方式,指的是复用一个线程,处理多个socket中的事件。能够资源复用,防止创建过多线程导致的上下文切换的开销。常见的IO多路复用系统调用有select、poll和epoll。select 实现多路复用的方式是,将已连接的 Socket 都放到一个文件描述符集合,然后调用 select 函数将文件描述符集合拷贝到内核里,让内核来检查是否有网络事件产生,检查的方式很粗暴,就是通过遍历文件描述符集合的方式,当检查到有事件产生后,将此 Socket 标记为可读或可写, 接着再把整个文件描述符集合拷贝回用户态里,然后用户态还需要再通过遍历的方法找到可读或可写的 Socket,然后再对其处理。

所以,对于 select 这种方式,需要进行 2 次「遍历」文件描述符集合,一次是在内核态里,一个次是在用户态里 ,而且还会发生 2 次「拷贝」文件描述符集合,先从用户空间传入内核空间,由内核修改后,再传出到用户空间中。

select 使用固定长度的 BitsMap,表示文件描述符集合,而且所支持的文件描述符的个数是有限制的,在 Linux 系统中,由内核中的 FD_SETSIZE 限制, 默认最大值为 1024,只能监听 0~1023 的文件描述符。

poll 不再用 BitsMap 来存储所关注的文件描述符,取而代之用动态数组,以链表形式来组织,突破了 select 的文件描述符个数限制,当然还会受到系统文件描述符限制。

但是 poll 和 select 并没有太大的本质区别,都是使用「线性结构」存储进程关注的 Socket 集合,因此都需要遍历文件描述符集合来找到可读或可写的 Socket,时间复杂度为 O(n),而且也需要在用户态与内核态之间拷贝文件描述符集合,这种方式随着并发数上来,性能的损耗会呈指数级增长。

epoll 通过两个方面,很好解决了 select/poll 的问题。

  • _第一点_,epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述字,把需要监控的 socket 通过 epoll_ctl() 函数加入内核中的红黑树里,红黑树是个高效的数据结构,增删改一般时间复杂度是 O(logn)。而 select/poll 内核里没有类似 epoll 红黑树这种保存所有待检测的 socket 的数据结构,所以 select/poll 每次操作时都传入整个 socket 集合给内核,而 epoll 因为在内核维护了红黑树,可以保存所有待检测的 socket ,所以只需要传入一个待检测的 socket,减少了内核和用户空间大量的数据拷贝和内存分配。
  • _第二点_, epoll 使用事件驱动的机制,内核里维护了一个链表来记录就绪事件,当某个 socket 有事件发生时,通过回调函数内核会将其加入到这个就绪事件列表中,当用户调用 epoll_wait() 函数时,只会返回有事件发生的文件描述符的个数,不需要像 select/poll 那样轮询扫描整个 socket 集合,大大提高了检测的效率。

操作系统

malloc 1KB和1MB 有什么区别?

malloc() 源码里默认定义了一个阈值:

  • 如果用户分配的内存小于 128 KB,则通过 brk() 申请内存;
  • 如果用户分配的内存大于 128 KB,则通过 mmap() 申请内存;

注意,不同的 glibc 版本定义的阈值也是不同的。

介绍一下brk,mmap

实际上,malloc() 并不是系统调用,而是 C 库里的函数,用于动态分配内存。malloc 申请内存的时候,会有两种方式向操作系统申请堆内存。

  • 方式一:通过 brk() 系统调用从堆分配内存
  • 方式二:通过 mmap() 系统调用在文件映射区域分配内存;

方式一实现的方式很简单,就是通过 brk() 函数将「堆顶」指针向高地址移动,获得新的内存空间。如下图:方式二通过 mmap() 系统调用中「私有匿名映射」的方式,在文件映射区分配一块内存,也就是从文件映射区“偷”了一块内存。如下图:

分页内存管理说一下

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间,我们叫(_Page_)。在 Linux 下,每一页的大小为 4KB。虚拟地址与物理地址之间通过页表来映射,如下图:页表是存储在内存里的,内存管理单元 (_MMU_)就做将虚拟内存地址转换成物理地址的工作。而当进程访问的虚拟地址在页表中查不到时,系统会产生一个缺页异常,进入系统内核空间分配物理内存、更新进程页表,最后再返回用户空间,恢复进程的运行。在分页机制下,虚拟地址分为两部分,页号页内偏移。页号作为页表的索引,页表包含物理页每页所在物理内存的基地址,这个基地址与页内偏移的组合就形成了物理内存地址,见下图。总结一下,对于一个内存地址转换,其实就是这样三个步骤:

  • 把虚拟内存地址,切分成页号和偏移量;
  • 根据页号,从页表里面,查询对应的物理页号;
  • 直接拿物理页号,加上前面的偏移量,就得到了物理内存地址。

下面举个例子,虚拟内存中的页通过页表映射为了物理内存中的页,如下图:

C++

说说你了解的C++11相关特性

  • 自动类型推断(auto):引入了auto关键字,可以根据变量初始化表达式的类型自动推断变量的类型,使得代码更具灵活性和可读性。
  • 范围for循环:通过for (element : container)语法,允许直接遍历容器中的每个元素,简化了迭代操作,减少了代码量。
  • 移动语义和右值引用:通过引入右值引用(&&)和移动构造函数,减少了资源管理时的不必要拷贝操作,提高了性能。
  • 智能指针:std::shared_ptr和std::unique_ptr等智能指针类的引入,帮助管理动态分配的内存,避免内存泄漏和悬挂指针等问题。
  • Lambda表达式:引入了匿名函数的Lambda表达式语法,能够更方便地定义和使用函数对象,减少了冗余代码。
  • nullptr空指针:引入了nullptr关键字,用于表示空指针,替代了传统的NULL,避免了空指针常量与整数间的模糊问题。
  • 初始化列表:通过使用花括号{}来对对象初始化,统一了初始化语法,提供了更安全、简洁的初始化方式。
  • 默认和删除成员函数:引入了=default和=delete来指明默认构造函数、拷贝构造函数等的生成和禁止。
  • 强类型枚举:引入了枚举类(enum class),解决了传统枚举类型带来的全局命名空间和类型安全问题。
  • 多线程支持:引入了std::thread、std::mutex等多线程支持库,使得并发编程更加方便和安全。
  • 泛型编程优化:引入了constexpr关键字,允许在编译时计算表达式,提高了程序的性能。

介绍移动语义

移动语义通过右值引用(Rvalue References)和移动构造函数(Move Constructors)来优化对象在内存中的传递和处理,避免不必要的数据复制。

传统的拷贝操作对于大型对象或资源密集型对象来说可能会有很高的开销,因为它们需要将对象的所有数据复制到新的对象中。移动语义的引入解决了这一问题,实现了对象资源的“移动”而非“复制”。

  • 右值引用(Rvalue References):通过使用双引号&&声明右值引用,可以绑定到临时对象或右值,即那些将会被销毁的临时对象。右值引用允许我们对其资源进行移动操作而不是复制操作。
T&& t = T(); // t为右值引用
  • 移动构造函数(Move Constructor):移动构造函数是专门用于将对象资源从一个右值引用对象“移动”到另一个对象的构造函数。它通过将资源所有权从一个对象转移到另一个对象来避免不必要的数据复制,从而提高程序性能。
// 移动构造函数示例
T(T&& other) {
    // 将other对象的资源移动到当前对象
}
  • 标记对象为右值(std::move):使用std::move函数可以将一个对象标记为右值,以便可以调用移动构造函数而不是拷贝构造函数。
T obj1;
T obj2 = std::move(obj1); // 将obj1标记为右值,调用移动构造函数

移动语义的应用可以在涉及对象所有权转移的情况下提高性能,特别是在动态内存管理和容器元素移动时。通过避免不必要的复制操作,移动语义使得代码更加高效和可维护,同时减少了资源的浪费。

介绍智能指针

  • std::shared_ptr:是一种引用计数智能指针,允许多个shared_ptr对象共享同一个对象,并通过引用计数来管理内存的释放,当最后一个shared_ptr指向对象析构时,会释放对象所占用的内存。不适合处理循环引用的情况,可能导致内存泄漏。
  • std::unique_ptr:是一种独占式智能指针,确保只有一个指针可以指向一个对象,不能进行复制,但可以移动它的所有权。
  • std::weak_ptr:是用于解决std::shared_ptr可能导致的循环引用问题的智能指针。它允许引用shared_ptr所管理的对象,但不会增加引用计数,不会影响对象的生命周期,避免循环引用导致的内存泄漏。

容器可以一边遍历一边插入吗?

当处理vector,string,deque时,当在一个循环中可能增加或移除元素时,要考虑到迭代器可能会失效的问题。vector插入的时候:

  • 当插入(push_back)一个元素后,end操作返回的迭代器肯定失效;
  • 当插入(push_back)一个元素后,如果vector的capacity发生了改变,则需要重新加载整个容器,此时first和end操作返回的迭代器都会失效;

list插入的时候:

  • 插入操作(insert)和接合操作(splice)不会造成原有的list迭代器失效,

deque插入的时候:

  • 在deque容器首部或者尾部插入元素,不会使得任何迭代器失效;
  • 在deque容器的任何其他位置进行插入删除操作都将使指向该容器元素的所有迭代器失效;

set和map插入的时候:

  • 与list相同,当对其进行insert或者erase操作时,操作之前的所有迭代器,在操作完成之后都依然有效,但被删除元素的迭代器失效。

使用迭代器怎么删除一个元素?

顺序容器(序列式容器,比如vector、deque)删除元素的方式:erase迭代器不仅使所指向被删除的迭代器失效,而且使被删元素之后的所有迭代器失效(list除外),所以不能使用erase(it++)的方式,但是erase的返回值是下一个有效迭代器:It = c.erase(it);

std::vector<int> arrayInt;
...
std::vector<int>::iterator it = arrayInt.begin();
while (it != arrayInt.end())
{
    if (...)
    {
        // 需要注意的是,因为顺序式容器会使本身和后面的元素迭代器都失效,所以不能简单的++操作
        // 顺序式容器的erase()会返回紧随被删除元素的下一个元素的有效迭代器(节点式容器的erase()的返回值是void)
        it = arrayInt.erase(it);
    }
    else
    {
        it++;
    }
}

关联容器(关联式容器,比如map、set、multimap、multiset等) 删除元素的方式:erase迭代器只是被删除元素的迭代器失效,但是返回值是void,所以要采用erase(it++)的方式删除迭代器;c.erase(it++)

std::map<int, struct> mapInfo;
...
std::map<int, struct>::iterator it = mapInfo.begin();
while (it != mapInfo.end())
{
    if (...)
    {
        // 删除节点的前,对迭代器进行后移的操作,因为其他元素不会失效
        mapInfo.erase(it++);
    }
    else
    {
        it++;
    }
}

算法

  • 取数组中最小的K个元素(使用了堆排序,问怎么优化堆的大小)

其他问题

  • 是否学习过一些新技术比如 OpenAI , 消息队列之类,有没有参与过开源项目
  • 简单问了一下实验室的项目
  • 有没有使用过 git
推荐阅读:
好难!腾讯面试体验已结束。。。
艰难走到字节终面了!
激动!再次被阿里云捞了一波

浏览 828
4点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
4点赞
评论
收藏
分享

手机扫一扫分享

分享
举报