# alimama **Repository Path**: warm-light-i/alimama ## Basic Information - **Project Name**: alimama - **Description**: alimama挑战赛 - **Primary Language**: C++ - **License**: Not specified - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2023-06-06 - **Last Updated**: 2023-07-12 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # alimama ## （调研）阿里妈妈极限代码挑战赛 ### 网址：[牛客竞赛 (nowcoder.com)](https://competition.nowcoder.com/87/introduce?channel=apppush#171) 初赛题型为高性能在线服务的**大数据更新**； 复赛题型为真实场景的广告**检索引擎**构建 **考察点**：高性能分布式在线服务、高性能索引和检索、分布式排序； ### 初赛赛题： 随着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)](https://developer.aliyun.com/article/1138150) - 读操作：主从库都可以 - 写操作：只能主库进行，写完同步给从库 - 主从同步的三种方式 - - 全量复制：第一次同步，可以优化为主从从模式同步 - 基于长连接的命令传播：除第一次外的正常同步 - 增量复制：遇到网络故障时进行 - 分布式一致性协议（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的请求数据对象