alimama

（调研）阿里妈妈极限代码挑战赛

网址：牛客竞赛 (nowcoder.com)

初赛题型为高性能在线服务的大数据更新；

复赛题型为真实场景的广告检索引擎构建

考察点：高性能分布式在线服务、高性能索引和检索、分布式排序；

初赛赛题：

随着AIGC/LLMs的持续火爆，大模型已成为当前AI发展的重要趋势：如何高效支持大模型的分布式存储与访问，突破单机内存瓶颈，是大模型需要面对的工程技术问题之一。在已给出模型数据本地加载及访问接口的基础上，本题要求设计一个简单的分布式系统，能够支持加载超出单机内存限制的大模型，提供模型数据访问的能力，支持数据的切换与回滚，在保证正确性的前提下考虑一致性、高性能和高可用性；

初赛提示事项：

1. docker基础知识和docker-compose工具的相关的视频、书籍和博客
2. grpc、etcd、hadoop等的命令行操作可以提前了解一下，方便开发阶段调试
3. 分布式系统的概念与设计，分布式数据库系统原理等相关的视频、书籍和博客
4. 不同方式实现redis集群的方案（官方方案/第三方方案），以及其他的nosql服务的一些视频、书籍和博客
5. windows电脑的同学建议安装 git bash，会更方便的使用题目中预提供的脚本文件

复赛赛题：

广告检索引擎是在线广告系统的核心模块，涉及到广告的匹配、过滤、排序、计价等核心能力。在单机无法容纳的广告数据规模下，如何实现高性能的广告检索是持续探索的技术问题。本题将提供一份广告数据集，要求设计实现一个包含核心功能的高性能的分布式广告检索引擎；

分布式存储的两个主要问题——数据分片和数据冗余

数据分片

• 按照一定的规则，将数据集划分成相互独立、正交的数据子集，然后将数据子集分布到不同的节点上。
• 原则：按照最主要、最频繁使用的访问方式分片

数据分片的三个问题

如何做数据分片

一般都是一致性hash

数据分片特征值的选择

最常用的字段

元数据的管理

元数据：比如数据与节点的映射关系、节点状态等重要信息

特点：需要有多个备份，由此需要满足备份之间的一致性

一致性协议：

• 主从同步——数据备份（redis）

• • 以redis为例，一致性如何保证？

  • 参考：Redis是如何保证数据一致性的-阿里云开发者社区 (aliyun.com)

  • 读操作：主从库都可以

  • 写操作：只能主库进行，写完同步给从库

  • 主从同步的三种方式

  • • 全量复制：第一次同步，可以优化为主从从模式同步
    • 基于长连接的命令传播：除第一次外的正常同步
    • 增量复制：遇到网络故障时进行

• 分布式一致性协议（raft）：所有备份均可对外提供服务

Etcd vs Redis

• 两者都是key-value数据库
• etcd更强调强一致性，保存配置信息，读多写少的场景，性能差（单节点每秒1000次写入）；另外etcd可以监控key的变化
• redis作为内存数据库，性能高得多，每秒1约万次写入，是etcd的10倍
• 从业务来说，etcd偏向于服务发现、通知等，redis偏向缓存

（过程）阿里妈妈极限代码挑战赛

根据题意分布式redis就可以？

redis只能存储小的key-value数据，对于这里的大块文件显然是不合适的

• 提供的持久化、备份等服务会加大负担

redis的一致hash、节点交互等主要功能已经实现，且性能基本没有优化的空间

• 请求是平均分配到每个节点的，且概率是一致的，我们直接把一个版本的所有切片平均分配到各个节点
• 跨机通信使用grpc实现

大版本1：Hadoop-磁盘-内存之间以切片为单位双层缓存

各主机启动后就注册开始服务，切片可能在

• 本机内存
• 本机磁盘
• 其他主机内存
• 其他主机磁盘
• Hadoop

双层缓存结构，监听前直接注册节点可用，请求要先查内存，查不到再查磁盘，再查不到最后去hadoop读

• 优化点

  • 控制内存，占用率过高进行随机unload某个切片

  • 多线程加载数据，不卡住grpc服务进程

• 存在的误区

  • 跨机通信使用grpc实现，每个request会有1000个read请求，必然超时
  • 未在内存命中的切片必定会超时

大版本2：监听前分布式平均加载，数据放内存再注册

• etcd提供服务发现，等所有节点加载到磁盘、load到内存、注册etcd完再启动服务

• 新线程监听版本切换与回滚，同样用etcd做服务发现，等所有主机转换完成开始切换

• 跨机通信过于频繁，需要分组，每次请求最多只请求5次其他主机

• 一致性维护

  • 注册服务前轮询etcd

  • 切换版本、版本回滚前轮询etcd，等所有节点准备完成，轮询etcd更新当前版本信息（这俩有想过etcd的watch中断回调，避免轮询空转CPU，但是要开六个线程，最后没加）

  • 最难维护的一致性：

    • 版本切换过程单次请求的返回要么全新要么全旧。上述版本切换/回滚过程中，新版本更新后，正在处理的rpc请求仍然是旧版本，需要返回旧数据。
    • 解决方案：在跨机rpc请求中设置版本字段，在一段时间内保留旧数据，保证正在运行的rpc请求得到旧版本的回复。

• 服务请求-工作逻辑优化

  • 按照传统的服务器“请求-服务-存储”架构，之前的工作一直在做服务-存储的优化，这里尝试优化请求-服务部分
  • 这部分没什么优化的，与http不同，这里始终只有一个客户端，一个长连接，并且是频繁数据传输，用主从多线程reactor模型来说，就只有一个用户，多个工作线程
  • 多线程、消息队列、长连接是grpc自己实现的
    • grpc使用channel这个东西来区分不同的客户端，事实上这个东西内部主要参数就是目标IP与端口号，也就是说，对于一个机器来说，请求一个目标主机一般情况下只会生成一个客户端，建立一个连接
    • 对于本场景来说，只有一个客户端，连接是同一个，不需要连接池（如果不频繁释放与建立连接）
    • 默认是持久连接，不用考虑连接的释放，在以下情况下会断开连接
      • 显式关闭连接: 你可以在客户端或服务器端显式地关闭 gRPC 连接。通过调用 Channel的 shutdown()方法或 Server的shutdown()方法来关闭连接
      • 超时: 如果连接上出现长时间没有活动的情况，可能会触发超时机制，导致连接断开
      • 网络故障:如果底层的网络连接中断或发生故障，连接也会断开
      • 服务器终止: 如果服务器端主动终止运行，连接会被关闭。
  • 可以的调整是线程数量等

• 版本切换过程服务性能下降，不能满足50%qps条件下1‰错误率。

  • 调整线程优先级，让服务函数优先被执行。但是又不能保证加载线程不会饥饿（一直不加载）（没实现）
  • 限制后台加载进程，加线程sleep，释放资源给服务函数
  • 扩大缓冲区大小，减少读写次数

大版本3：满足基础条件后的极限优化

权衡

• 高可用性qps
• 版本切换的快速/稳定：错误率在1‰，时间越快越好

allin版本切换

限制qps（实际业务场景是经常这么做的）

• 生产者消费者模型维护消息队列

• • 会爆，原因可能是Get函数的连接是端对端指定的，或者由于长时间没拿到锁被重置连接了

• 控制grpc线程数

• 最优解：Lock+全局变量计数（atomic变量）+时间戳，能够精确控制qps大小

• 下下策：死循环多线程卡性能，相当于自废武功

多线程加载

• 4线程、8线程分片加载

• • 最后发现多线程的提升随着线程数增多不明显了。按道理来说IO密集型的工作线程数越多不是越好吗？因为被磁盘读写卡了，瓶颈是磁盘读写速度。

其他bug

grpc长连接与连接池：grpc默认长连接，如果每次都新建链接，最后会消耗完文件描述符，系统崩溃。每个主机提前与其他5台主机建立5个长连接rpc。

string与char的转换，需要考虑字节流char中的\0可能并不是终结符

线程同步

• 公共变量要谨慎处理

• hdfs库并非线程安全

• • 原生C++库
  • 多数据库连接

（扩展）阿里妈妈极限代码挑战赛

总体总结与优化方向

• 我们现在的思路是降低QPS，多线程IO读取，追求极致切换速度，但是如果公用IO性能的话这么做就卡在IO的瓶颈上了，那是不是让6个节点轮转多线程加载，和同时全力加载所用的时间也是差不多的，那如果是这样的话，我们是不是可以不限制自己的qps性能，用其他五个节点提供服务（通过每三个节点完整加载一个模型版本，在一个节点磁盘加载的时候用其他节点提供切片信息，缓解加载节点的跨机通信压力），这样就可以在不怎么降低切换时间得分的情况下刷点qps的分呀。

QPS优化

通信协议优化：

• grpc中reapeated 搭配Struct，长列表的话会很慢

• 自定义跨机通信协议

• • TLV结构（Type-Length-Value）

  • • 是一种常见的数据编码和数据格式化方法
    • 实现的时候可以转字节流快速传输。虽然grpc底层也是转了字节流，但是必定会保存上层的结构体信息，这显然比不上我们自己转好的字节流通信协议。

系统架构优化：

• 双集群/三集群

• • 通过多缓存实现
  • IO有瓶颈，不要同时加载文件。同时减少正在加载文件主机的跨机通信压力
  • 容灾备份

限制/调整文件加载资源占用

O_DIRECT linux直接IO

• O_DIRECT 是一个在 Linux 系统中的文件打开选项，用于直接 I/O（Direct I/O）。它允许应用程序绕过文件系统缓存，直接在应用程序和物理存储设备之间进行数据传输，提供了一种直接访问存储设备的机制。

• 要做内存对齐和字节对齐

• 优势

• • 减少内存开销。文件系统缓存用的是内存。
  • 提高性能。减少了数据复制和缓存同步开销。
  • 数据一致性。数据不经过缓存，没有一致性、持久化问题。

Sendfile()函数（类似于DMA传输）

• 用于文件描述符之间的数据传输，与O_DIRECT一样没有缓存。并且都在内核态完成，CPU占用低。

io_uring高性能异步IO框架

• 允许应用程序以异步的方式进行文件 I/O 和网络 I/O 操作，从而提高系统的 I/O 吞吐量和响应性能。

• 背景：

• • 在传统的 I/O 模型中，应用程序通常使用阻塞 I/O 或多线程来处理文件和网络 I/O 操作。这种模型在处理大量的并发连接或高吞吐量的场景下，可能会导致线程创建和切换的开销变得非常大，影响系统性能。

• 做法

• • 通过使用异步 I/O 的方式，将 I/O 操作的处理交给内核，在应用程序中不再需要显式地创建和管理多个线程来处理 I/O。这样可以降低线程切换开销，并充分利用系统的多核处理能力。
  • 线程数一般是核心数2或4

• 珍爱生命，不写异步

绑核

• 简单来说就是把某个任务绑定到某个核心去执行

• 可以实现

• • 提高缓存（cache）利用率（命中率）
  • 控制调度，给某些任务优先级更高
  • 减少资源竞争，将不同任务分配给不同核心，减少任务间的切换消耗

• 将写文件和服务函数绑定不同核心

总体效率优化

编译优化

• C++支持O1,O2,O3三种不同级别的优化等级，高级的优化等级可以显著提高代码执行速度，但是会增加编译时间
• 一些其他目的的编译优化，如可执行文件大小、调试等
• 开O3，qps直接翻三倍

池优化

• 凡是频繁新建、销毁的东西都建个池，减轻内存分配器的压力

• • 比如grpc的请求数据对象