Langchain needle in haystack 实验​

长上下文之后，越后面的部分的事实性细节越容易找，尤其是多事实的情况下

引发的一个思考是 rerank 时是否需要将最关注的块放在 prompt 的最后面，也就是倒序？

• 后补: 但其实又有attention sink相关的研究，可能还是需要具体任务具体测试分析

Maybe recency bias in LLMs：只记得最近的了

No retrieval guarantees

query analysis：将 question 联系到正确的文档​

routing (to right DB)

full doc -> summary -> embedding： doc 中噪声非常大, summary 是必要的，语义层次的保留 level 通过 prompt 保证

self-reflection 听起来很美好，但实际常常用不到，太慢了，并且搜不出来更多是前期处理没做好，再换着花样也很难搜出来

HyDE 对于高度 Domain Knowledge 和抽象性理解的任务基本没用:

一些自己的解释

1. 能否生成正确的假设文档， 难
2. 即使通过先行的小批量搜索教导 LLM 根据这些 example 生成假设文档，也很难让 LLM 从这些文档中抽取某个泛化的问题，经常会 过度 specific 而导致后续漏掉文档
3. 目前实验下来垂域脏文档类型最好的解决方案还是 reranker，embedder 如果不微调分布太接近了，例如全部的 chunk 都在 0.5~0.6 之间，意义寥寥

和数据分析的结合:

分析波动->(数据分析)找出波动的阶段-> 对每个波动的阶段做查询

GraphRag 这种 KG-based 的方法经常强调“对整个数据集信息的整合”

但这个要分领域，例如，个人知识库之中，这是好的

但垂域的知识文档常常是相似的格式，固定的路由，同时信息的整合关键不在“多实体”的关系上，而是在于“单个实体随时间的变化”上。

又或者说实体关系 $R(e_1, e_2)$ 本身应该建模成一个包含时间的 $R(e_1, e_2, t)$

如果仅仅是靠新加入的文档来动态更新 KG 的话，滞后性会很强

在这种半结构化的模板式文档中，LLM 实际上在干一个 Fuzzy DB manager, 提取信息，充当一个搜索引擎

利用 KG 进行某种意义上的多跳推理本质上也只是对文档的多次检索，推理跳数越多，关系越复杂，离线生成 KG 就越难，不是所有领域都像是法律一样有一个明确的 A 判例引用 BCD 法条的连接关系的，这样复杂的 KG 在要想随时间变化也更不可能

从某种意义上来说，KG 是在横向生成，而类似金融这种领域的 RAG 做的是纵向的 Timeline, 这部分对于关键实体是有数据的，并且可能数据都不需要自己做（例如各种行情的图），而离线准备好这些 timeline 之后，如何在 timeline 上进行一个跳跃和查询分析才是关键的。

如果从 DB 的角度上分析的话，金融领域这种关注点快速变化的 RAG 系统（with cache）也就相当于 lazy generated timeseries DB 了，例如问了一个 A 的价格变化，就像是生成了一个 time, delta_price, event(detail) 的 timeseries DB 表，把生成 reason 这样的 LLM 工作 lazy 化了而已

chunk 的前总结和后总结(离线在线)​

离线总结最大的问题在于总结哪些方面，实际上是文档预处理的一个部分

最简单的方法就是整个提示模板每个 chunk 问一次 LLM，有 langchain 的 map reduce 等稍微 high level 一点的工具可以支持这个事情

对长文档总结更有效一些的做法是利用好 embedding，先对 chunk embedding 做聚类，再每个聚类里面抽几个 chunk, 从而保证多样性和 chunk 数量的平衡

后总结，或者说 query-based 总结大体上是用 LLM 做比较多，但对于时延和开销的增加太高了，一个比较新的方法是 paragraph sentence-level mask bert（自己造的词），在段落中根据 q, d 的交叉编码得到句子级别的二进制掩码，从而删除无关部分。有一篇 ICLR2025 基于 bge 训了个，https://huggingface.co/blog/nadiinchi/provence

provence效果非常好，又快又几乎对齐例如GPT4.1这种顶级模型的效果

另一个思路就是绕过这个问题，切小块，依赖 rerank 和重新合并乃至知识图谱检索之类的策略保证相关性，也就是在查询完之后是合并还是切分的思路差距

半结构化数据​

https://docs.superlinked.com/getting-started/installation 聚焦半结构化的异构数据，例如朴素 embedding 方案对数字的理解不足，无法建模 1-99 的相似度分数与 higher/lower 这种文本的关系

https://github.com/microsoft/multifield-adaptive-retrieval 做多字段的权重学习(自适应选择查询应该着重的权重)

embedding 相关的调优​

colbert架构是一个better embedding的方向，其核心在于将文档的token level embedding保存下来，对于每一个query token，计算maxsim算子得到单token的score，再求和

对比朴素embedding方案，它在token level进行计算可以很好的带来类似关键词匹配的效果，有效避免长文档下，embedding过于平均化余弦相似太不敏感的问题

对比rerank方案，它的优点又在嵌入矩阵可以离线计算，不需要完全在线的交叉编码器

引入方案： https://python.langchain.com/docs/integrations/providers/ragatouille/

Prompt​

基本没有什么特别通用的工作，但值得一提的是将prompt作为一个优化变量，使用LLM在Trajatory上进行采样和跑各种论文的“prompt优化算法”的解耦框架dsPy https://dspy.ai/ 用户以类似类型/对象系统的简短注释提供给dspy作为“初始意图”，而后续复杂的提示由dspy生成，核心思想是让用户专注于编程

class CheckCitationFaithfulness(dspy.Signature):
    """Verify that the text is based on the provided context."""

    context: str = dspy.InputField(desc="facts here are assumed to be true")
    text: str = dspy.InputField()
    faithfulness: bool = dspy.OutputField()
    evidence: dict[str, list[str]] = dspy.OutputField(desc="Supporting evidence for claims")

context = "The 21-year-old made seven appearances for the Hammers and netted his only goal for them in a Europa League qualification round match against Andorran side FC Lustrains last season. Lee had two loan spells in League One last term, with Blackpool and then Colchester United. He scored twice for the U's but was unable to save them from relegation. The length of Lee's contract with the promoted Tykes has not been revealed. Find all the latest football transfers on our dedicated page."

text = "Lee scored 3 goals for Colchester United."

faithfulness = dspy.ChainOfThought(CheckCitationFaithfulness)
faithfulness(context=context, text=text)

DSPy 中的不同优化器将通过为每个模块合成良好的小样本示例 （如 dspy.BootstrapRS 1 ） 来调整程序的质量；为每个提示提出并智能地探索更好的自然语言指令 （如 dspy.MIPROv2 2 ） ，以及为您的模块构建数据集并使用它们来微调系统中的 LM 权重 （如 dspy.BootstrapFinetune 3 ）

LLM评估​

测试不可靠：有多少答案是被记忆出来的？

有多篇相关的paper在讨论这个问题，然后采用了一些方法来衡量这个事情，例如，在数学问题题集中，替换无关的描述、修改数字等等，看看模型性能变差多少

类似数学问题集这种在网络上数据中很难过滤干净，还需要考虑多语言影响

另一些评估指标如ARC-AGI通过抽象图像智力问题集来评估模型的推理能力，相对来说泄题风险小一些(并且有隐藏test set)

• 丢给LLM的时候不是图像，而是矩阵，用数字表示不同颜色

Chatbot Arena: 让全世界的人都来进行判断哪个模型好​

但还是有办法hack: 更fit人的倾向（粗体字、分点、emoji.....）

Elo Score 考虑除了人的直接倾向之外其他因素的影响，在BF模型计算时加上一项$\beta_0$, $\frac{1}{1 + exp(\beta_i - \beta_j + \beta_0)} = E_{ij}$, $E_{ij}$ 是模型i和j的胜率，$\beta_i$ 是模型i的真实评分，$\beta_0$ 是一个全局偏差项，表示人类评估者的偏好。通过最大化似然函数来估计参数$\beta_i$和$\beta_0$，从而得到模型的真实评分。

$\beta_0 = \gamma_1 * 长度差 + \gamma_2 * emoji个数差 + \gamma_3 * ...$

可以看到，考不考虑这个$\beta_0$，模型的排名差别很大

Goodhart's Law​

一旦一项指标被用作目标，它就不再是一个好的指标

http://becomingahacker.org/integrating-agentic-rag-with-mcp-servers-technical-implementation-guide-1aba8fd4e442

However, traditional RAG has limitations: it usually queries a single data source and only performs one retrieval pass, so if the initial results are poor or the query is phrased oddly, the answer will suffer 但是，传统的 RAG 存在局限性：它通常查询单个数据源，并且只执行一次检索传递，因此如果初始结果不佳或查询措辞奇怪，答案将受到影响

There’s no built-in mechanism for the system to reason about how to retrieve better information or to use additional tools if needed. 系统没有内置机制来推理如何检索更好的信息或在需要时使用其他工具。

关于结构化输出的另一篇特别好的文章: https://www.boundaryml.com/blog/schema-aligned-parsing

推理加速：是对的，例如huggingface-text-embedding项目，将各种转trt/onnx 可以让吞吐提升5x

H100 bge-reranker-v2-m3 1024 * 512char sentence， 13s -> 2.3s

关键词抽取​

基于主题LDA，词典等

小模型方法：先用spaCy、hanLP等得到语法树，再从语法树中拿到名词性关键词等

无监督，经典如YAKE！综合考虑词频，词位，共现等。可以考虑https://github.com/JackHCC/Chinese-Keyphrase-Extraction

一篇非常有insight的blog：上下文相关!=上下文充足，定量充足性和它的应用​

https://research.google/blog/deeper-insights-into-retrieval-augmented-generation-the-role-of-sufficient-context/

开发了一个交错文本和图像生成综合评估框架ISG

使用scene graph捕获文本和图像的关系，提供四个级别的评估：整体的、结构性的、块级别和特定于图像的，并引入了一个新benchmark，ISG-BENCH

作者实验认为现有模型在端到端生成文本图像交错内容时，效果不好，于是做了一个Agent来完成这个任务

motivation​

如图，现有MLLM不能直接生成交错文本和图像内容，需要将生成图像部分交给SD等外部模型再组合，带来了更大的开销与不一致性

为了专注这一任务，作者的Benchmark优先考虑视觉为中心的任务，例如风格迁移等图像输出的特定要求。

• 作者的数据集和人工标注比较有较高Pearson相似度，以此说明准确性
• 作者表示先前没什么benchmark主要以视觉为中心，以此说明新颖度
• 但有一说一，作者的表还是有点不公平的，例如它自己的sample很少(一千多)，同时评估级别是自己提出的这个四级别评估

作者的表​

方法

注意点: 中间看起来很复杂, 实际上是很多组prompt完成的

评估框架将query拆成scene-graph-like structure，其中图文作为节点，而它们的关系作为边

在整体，结构，块和图四级别的评估中，每个级别都会生成一些用于评估的QA对。作者的意图是，让整体和结构评估连贯性和整体质量，块和图像评估指令完成的细节

结构性：用一个LLM预估图文交替内容的结构，然后与实际生成的内容进行比较

整体：MLLM-as-a-Judge和CoT，用1-10打分配合Yes/No判断

块： 将prompt P用LLM表示成三元组 （subj, obj, rel）,再用LLM生成问题，并用VQA评估

图像：从prompt 给的图像中用LLM抽出三元组关系和实体，判断query类别，根据类别不同使用不同的prompt产生判断的VQA，例如如果是"How to"，则需要包含特定实体，如果是“Painting”，则需要图像的准确生成

实验结果​

所有统一模型在按照说明生成交错文本和图像内容方面都存在重大缺陷。许多模型只生成 1 到 3 张图像，而有些模型根本无法生成任何图像。

整体评估结果与三个细粒度级别的评估结果之间的不一致表明，即使同时提供用户指示和正确的黄金答案，MLLM-as-a-Judge 在全面评估回答方面也存在显着局限性。具体来说，Judge MLLM 努力根据细粒度的标准评估响应，例如输出结构（包括图像数量）和提示中规定的详细文本-图像关系。此外，我们对结果的分析揭示了 MLLM-as-a-Judge 中固有的偏见，即“图像质量偏见”，即具有更高质量图像内容的回答始终获得更高的分数，尽管这些回答可能违反用户的指导要求和评判指南。这种偏见表明，即使获得了黄金答案，MLLM-as-a-Judge 仍然无法正确地对符合指定要求的交错回答进行准确评估。

效果展示: 跑一次它这个Benchmark要60美刀

结论

1. MLLM-as-a-judge存在图像质量bias
2. 现有端到端MLLM生成图文内容效果不佳, 可能需要在工程性上的agent做补救

如果简单引入语义搜索，那么第一时间想到的肯定是向量搜索的方法

先不论小的优化，向量方法现在大体上就是两种架构，单塔和双塔，对应Cross-Encoder和普通的Encoder模型。

双塔模型如下，查询$q$和文档$d$分别通过两个独立的编码器，得到向量表示$q_v$和$d_v$，然后计算相似度（内积，余弦，等等）。

而单塔模型则是将查询和文档拼接在一起，输入到一个交叉编码器中，这个交叉编码器很多时候就直接输出相关性得分score了，即为我们所说的reranker

单塔虽然精度远高于双塔，但有无法离线计算的缺点

而双塔的一大精度困境在于，当编码的文档变长时，文档的大部分内容可能都和查询没什么关系，这会导致查询向量和文档向量的相似度计算不准确。实际上，在楼主之前的一些实验之中，一整个很大的文档集合内，和某个查询最无关和最相关的文档的余弦相似度相差也就0.2左右，这就是长文档带来的问题。

但客观地讲，长文档是无法避免的，如果把文档切成更细粒度的句子，在上下文补齐语义，后续合并等麻烦可能更多，并且会出现"长文档实际上是在让相似度检索考虑上下文"这样的情况，一个例子是，问题是"上海交大的用户论坛中，...."，而文档可能是"...水源社区是上海交大的用户论坛。水源社区....." 如果仅在句子等短文本上面匹配，那缺少了上下文的情况下，"水源社区"当然和"上海交大"没什么关系。

那么，如何保证精度的同时又能离线计算呢？

ColBERT的思路是，使用双塔模型来计算相似度，但在编码文档时，使用了一个更细粒度的向量表示。

ColBERT给每个token一个向量表示，而不是给每个文档一个向量表示。这样，查询和文档的相似度计算就可以在token级别进行。

如下图，ColBERT在拿到最后一层的输出之后（这一层有非常多的语义信息！），将每一个token对应的vector都存下来，这一部分是离线的。

而在计算相似度的时候，将query的tensor和文档的tensor进行一个$MaxSim$算子

$MaxSim$是一个最大池化操作，取出每个token的向量中与查询向量最相似的那个向量，然后计算相似度。

ColBERT的性能是逼近reranker的，这个也很好理解，毕竟交叉编码器的优势就是可以考虑$q,d$之间的交互，而ColBERT除了保留语义嵌入之外，比起更暴力的加大embedding维度，更重要的是它保存了上下文次序的信息

而ColBERT的最后一层MaxSim，而没有采用神经网络的方案，让他带来了良好的可解释性

那看了上面立刻就会想到，这每一个token保存一个768/1024/...维的向量，存储开销不会很大吗？

ColBERT也考虑到了这个问题，因此在ColBERTv2中，采用了这样质心编码的方法来降低存储开销，能降低8倍

1. 对每个token的向量进行聚类，得到$k$个质心（k是一个预定义的数字）

2. 对每个token的向量，找到距离最近的质心，并将其索引存储下来，也就是从 $(v_d, ) ->(1,)$

3. 将质心向量库构建ANN索引，例如FAISS, ScaNN

4. 在计算相似度时，查询向量也进行同样的处理，找到距离查询最近的质心索引，然后从质心向量库中取出对应的质心向量进行相似度计算

在实际使用的时候，商业rag公司甚至对大规模检索做更狠的二值化向量压缩（说实话这也能检索出来真的有点现代模型神力了），让ColBERT的开销可以和单独的embedding媲美

二值化的说法是这样的:

压缩方法通过将正维度表示为 1、负维度表示为 0 来简化文档标记向量。这种二进制表示有效地指示了文档标记向量中重要语义特征的存在与否。 正维度有助于增加点积，表明相关的语义相似性，而负维度则被忽略。

ColBERT的使用上，很多公司都有了支持，例如vespa, jina等等，开源方案则有早期的ragatouile和后来的上下游如milvus，llamaindex的支持

但是，文档ColBERT还不是它发挥全部潜能的时候，据说SPLADE算法就比他效果好不少（这个我没有实测过），它在图像又活出了第二世，即所谓的ColPali架构

ColPali是MRAG、MLLM那边的新论文和解决方案，几个月的时间砍了1.9k star，ColPali的想法是这样的

• OCR的多个组件和分块带来误差传播，且预处理流程耗时也长，能不能直接端到端一次使用文档截图解决
• 但是如果将整页的文档编码成一个向量，肯定精度不够
• 我的ViT等视觉编码器会将整页文档变成一系列的patch（可以理解为子图），进而变成一系列视觉token，那我重用ColBERT，不就又有了多向量吗？并且这个存储和交互上比每个token存一个向量更合理! 子图本身就有很多的空间位置信息

并且，你会发现ColBERT的强可解释性在图像上有更关键的作用！模型在文本中关注了什么可能是某个词，还需要人进行一点逻辑推理来判断关系是否合理，而图像中关注了什么，直接看图就知道了！

作为一种新的RAG范式，ColPali从源头上解决了复杂的OCR和切块的问题

虽然其在重文字领域上的泛化性还留待验证，精度的提升也依赖于未来VLM的发展，但无疑社区已经认同了这个想法的价值

基于 OCR 的文本提取，以及随后的布局和边界框分析，仍然是重要文档 AI 模型（例如 LayoutLM）的核心。例如， LayoutLMv3 对文档文本进行编码，包括文本标记序列的顺序、标记或线段的 OCR 边界框坐标以及文档本身。这在关键的文档 AI 任务中取得了最佳成果，但前提是第一步——OCR 文本提取——能够顺利完成。

但通常情况并非如此。

根据我最近的经验，OCR 瓶颈导致现实世界生产文档档案中的命名实体识别 (NER) 任务的性能下降近 50%。

目前例如ColQwen2这种ColBERT + Qwen2.5-VL-3B-Instruct的方案也很火，很多榜上都刷到了SOTA，感兴趣的同学也可以自己试试

美团外卖基于GPU的向量检索系统实践​

美团外卖的向量检索系统使用了GPU来加速向量检索过程。该系统主要包括以下几个方面： 美团外卖业务特点具有较强的Location Based Service（LBS）依赖，即商家的配送范围，决定了用户所能点餐的商家列表。以商品向量检索场景为例：向量检索结果集需要经过“可配送商家列表”过滤。

美团外卖向量检索基于Elasticsearch+FAISS进行搭建，实现了10亿级别+高维向量集的标量+向量混合检索的能力。为了在保证业务高召回率的同时进一步减少检索时间，我们探索基于GPU的向量检索，并实现了一套通用的检索系统。

相继使用了HNSW（Hierarchical Navigable Small World），IVF（Inverted File），IVF-PQ（Inverted File with Product Quantization）以及IVF-PQ+Refine等算法，基于CPU实现了向量检索能力

在HNSW算法中，这种导航小世界图的层次结构使得搜索过程可以从图的高层开始，快速定位到目标点的大致位置，然后逐层向下精细化搜索，最终在底层找到最近邻，在通用检索场景上有显著的优势。然而该算法在高过滤比下性能会有折损，从而导致在到家搜推这种强LBS过滤场景下会暴露其性能的劣势。业界有较多相关的benchmark可以参考，以Yahoo的向量检索系统Vespa相关博客为例

索引吞吐

Observations: 观察结果：

• Indexing throughput depends on corpus size for Annoy and HNSW, where throughput is halved when corpus size is increased by 10x. 对于 Annoy 和 HNSW，索引吞吐量取决于语料库大小，当语料库大小增加 10 倍时，吞吐量就会减半。
• Indexing throughput for RPLSH is independent of corpus size. RPLSH 的索引吞吐量与语料库大小无关。
• Annoy is 4.5 to 5 times faster than HNSW. Annoy 比 HNSW 快 4.5 到 5 倍 。
• RPLSH is 23 to 24 times faster than HNSW at 1M documents. 对于 1M 文档，RPLSH 的速度比 HNSW 快 23 到 24 倍 。

查询吞吐

Observations: 观察结果：

• HNSW outperforms Annoy and RPLSH. At corpus size 1M the QPS is 9 times as high as Annoy, and 16 times as high as RPLSH at comparable quality. Similar observations between hnswlib and Annoy are found in ANN Benchmarks, where the QPS of hnswlib is 5-10 times higher at the same quality on all tested datasets. HNSW 的表现优于 Annoy 和 RPLSH。在 1M 语料库规模下，其每秒查询速度 (QPS) 是 Annoy 的 9 倍 ，在同等质量下是 RPLSH 的 16 倍 。在 ANN 基准测试中也发现了 hnswlib 与 Annoy 之间的类似现象：在所有测试数据集上，相同质量下 hnswlib 的每秒查询速度 (QPS) 比 Annoy 高 5-10 倍。
• HNSW 搜索算法很大程度上取决于节点之间的链接数量，而链接数量又取决于语料库的大小。当语料库规模增加 10 倍时，QPS 会减半。在索引过程中，我们也看到了同样的情况，因为它使用搜索算法来查找要连接的候选节点。

内存占用

Observations: 观察结果：

• The Annoy index is almost 3 times larger than the HNSW index, which results in ~40% more total memory usage in the 1M SIFT dataset. Annoy 索引几乎比 HNSW 索引大 3 倍，这导致 1M SIFT 数据集的总内存使用量增加约 40%。
• Both indexes are independent of dimension size, but max points in a leaf node (Annoy) and max links per level (HNSW) might need adjustments with higher dimensionality to get decent quality. 这两个索引都与维度大小无关，但叶节点中的最大点数（Annoy）和每级的最大链接数（HNSW）可能需要使用更高的维度进行调整才能获得不错的质量。

博客给出了一个很重要的观察是：当超过 90% 到 95% 的文档被过滤掉时，过滤后计算精确最近邻比搜索 HNSW 索引（过滤器会丢弃候选匹配项）的成本更低

2.2 IVF （Inverted File）​

IVF是一种基于倒排索引的方法，它将高维向量空间分为多个簇（Cluster），每个簇对应一个倒排列表，存储了属于该簇的向量索引。这种方法大大减少了搜索时需要比较的向量数量，从而提高了检索速度。它的缺点是需要存储原始的向量数据，同时为了保证检索性能需要将其全量加载到内存中，从而占用了大量的内存空间，容易造成内存资源瓶颈。

2.3 IVF-PQ（Inverted File with Product Quantization）​

在候选集数量巨大的场景下，比如商品向量检索场景下，IVF带来的内存空间大的问题很快就显现出来，为了解决内存空间的问题，开始尝试使用了IVF-PQ方法。该方法在IVF的基础上，使用了乘积量化（Product Quantization，PQ）的方法来压缩向量数据。PQ将高维向量分为多个子向量，然后对每个子向量进行量化，从而大大减少了对内存空间的需求。

然而，由于量化过程会引入误差，因此IVF-PQ的检索精度会低于IVF，从而导致召回率无法满足线上要求，对召回率要求相对较低的场景可以使用IVF-PQ，对召回率有一定要求的场景需要其他解决方案。

2.4 IVF-PQ+Refine​

为了提高IVF-PQ的检索精度，进一步采用了IVF-PQ+Refine的方案，在IVF-PQ的基础上，在SSD磁盘上保存了未经压缩的原始向量数据。检索时，通过IVF-PQ召回数量更大的候选向量集合，然后获取对应的原始向量数据进行精确计算，从而提高检索精度。这种方法既保留了IVF-PQ的存储优势，解决了内存资源瓶颈，又保证了召回率，因此在实际应用中得到了广泛的使用。

2.5 基于地理位置的向量检索​

通过将经纬度编码为向量，优化具体做法是将用户或商家的经纬度以加权的方式加入查询Query和候选向量中，在计算Query和候选向量的相似度时，距离因素就可以在不同程度上影响最终的检索结果，从而达到让向量索引具备LBS属性的目标。

这里没有细讲，但怎么具体怎么融入的LBS属性还是比较有意思的，最直接的方法是将经纬度信息直接拼接到现有的文本embedding向量上，也可以将经纬度用geohash，或者以用户为中心的极坐标系统表示?

我觉得最复杂的在于：

• 如何确定经纬度特征的维度，这也算是一种权值
• 如何让经纬度特征和其他向量特征上对齐？美团是否有一个专用的embedding模型来嵌入地理信息特征，这个模型又是根据什么进行微调的？是类似推荐系统那种基于用户反馈的，还是内部有一个地理加权的人工设计公式，这个模型提供的地理特征使得整体效果向这个公式靠齐的？

https://docs.google.com/document/d/1R5nOiwFUn9ZJtuWywmos2yfB4aCWCGy1TUN5VAnMRaY/edit?usp=sharing

考虑到美团外卖的业务场景，目标方案应该满足以下要求：

• 支持向量+标量混合检索：在向量检索的基础上，支持复杂的标量过滤条件。
• 高过滤比：标量作为过滤条件，有较高的过滤比（大于99%），过滤后候选集大（以外卖商品为例，符合LBS过滤的商品向量候选集仍然超过百万）。
• 高召回率：召回率需要在95%+水平。
• 高性能：在满足高召回率的前提下，检索耗时Tp99控制在20ms以内。
• 数据量：需要支持上亿级别的候选集规模。

实现向量+标量混合检索，一般有两种方式：前置过滤（pre-filter）和后置过滤（post-filter）。前置过滤指先对全体数据进行标量过滤，得到候选结果集，然后在候选结果集中进行向量检索，得到TopK结果。后置过滤指先进行向量检索，得到TopK*N个检索结果，再对这些结果进行标量过滤，得到最终的TopK结果。其中N为扩召回倍数，主要是为了缓解向量检索结果被标量检索条件过滤，导致最终结果数不足K个的问题。

业界已有较多的成熟的全库检索的方案，后置过滤方案可以尽量复用现有框架，开发量小、风险低，因此我们优先考虑后置过滤方案。我们基于GPU的后置过滤方案快速实现了一版向量检索引擎，并验证其召回率与检索性能。GPU中成熟的检索算法有Flat、IVFFlat和IVFPQ等，在不做扩召回的情况下，召回率偏低，因此我们在benchmark上选择了较大的扩召回倍数以提高召回率。

测试结果表明，以上三种算法均无法同时满足我们对检索性能和召回率的需求。其中IVF与IVFPQ召回率较低，Flat算法虽然召回率较高，但是与全体候选集计算向量相似度导致其性能较差。

根据用户的地理位置信息计算其GeoHash值，并扩展至附近9个或25个GeoHash块，在这些GeoHash块内采用Flat算法进行向量检索，可以有效减少计算量。这种向量子空间划分方式有效地提高了检索性能，但是存在某些距离稍远的商家无法被召回的情况，最终测得的召回率只有80%左右，无法满足要求。

综上，后置过滤方案无法同时满足检索性能和召回率的需求，而GPU版本的Faiss无法实现前置过滤功能，考虑到美团外卖的业务场景，向量+标量混合检索能力是最基本的要求，因此我们决定自研GPU向量检索引擎。

基于GPU的向量检索，要想实现前置过滤，一般有三种实现方案：

1. 所有原始数据都保存在GPU显存中，由GPU完成前置过滤，再进行向量计算。
2. 所有原始数据都保存在CPU内存中，在CPU内存中完成前置过滤，将过滤后的原始向量数据传给GPU进行向量计算。(能存更大的数据集)
3. 原始向量数据保存在GPU显存中，其他标量数据保存在CPU内存中，在CPU内存完成标量过滤后，将过滤结果的下标传给GPU，GPU根据下标从显存中获取向量数据进行计算。（省显存带宽）

由于GPU与CPU结构与功能上的差异性，使用GPU完成前置过滤，显存资源占用量更大，过滤性能较差，且无法充分利用过滤比大的业务特点，因此不考虑方案1。

实验结果表明，方案2在数据拷贝阶段耗时严重，时延无法达到要求。因为在美团外卖的场景下，过滤后的数据集仍然很大，这对CPU到GPU之间的数据传输带宽（A30显卡带宽数据如下 CPU-GPU：PCIe Gen4: 64GB/s；GPU-GPU：933GB/s）提出了很高的要求，因此我们最终选择了方案3。

考虑到显存的价格远高于内存，因此我们在设计方案的过程中，尽可能将数据存储在内存当中，仅将需要GPU计算的数据存储在显存当中。

内存中保存了所有的标量数据，数据按列存储，通过位置索引可以快速找到某条数据的所有字段信息，数据按列存储具备较高的灵活性和可扩展性，同时也更容易进行数据压缩和计算加速。针对需要用于过滤的标量字段，在内存中构造了倒排索引，倒排链中保存了对应的原始数据位置索引信息，内存数据结构如下图所示

显存中保存了所有的向量数据，数据位置索引与内存中的数据一一对应，可以通过位置索引快速获取某条数据的向量信息，如下图所示：

最后的流程图(Flat)

最后的流程图(IVF)，放宽召回率，提升性能

可见，无论是Flat还是IVF，在相同的召回率下，使用前置过滤的性能都要明显好于后置过滤。

性能优化

• 高并发支持，通过Cuda Stream，GPU可以并行处理多个查询请求，高并发压测下，GPU利用率可以达到100%。

• 通过GPU实现部分标量过滤功能，支持在GPU上实现部分标量过滤功能，向量计算与标量过滤同处一个Kernel，充分利用GPU并行计算能力

• 资源管理优化，支持句柄机制，资源预先分配，重复利用。每个句柄持有一部分私有资源，包含保存向量检索中间计算结果的可读写内存、显存，以及单独的Cuda Stream执行流；共享一份全局只读公有资源。在初始化阶段，创建句柄对象池，可以通过控制句柄数量，来调整服务端并发能力，避免服务被打爆。在检索阶段，每次向量检索需从句柄对象池中申请一个空闲的句柄，然后进行后续的计算流程，并在执行完后释放响应的句柄，达到资源回收和重复利用的目的

我们最终选择了单机多卡的数据分片方案，单台服务器部署多张GPU，检索时并行从本地多张GPU中检索数据，在CPU内存中进行数据合并。

为了支持更大规模的向量数据检索，我们还在GPU检索引擎上支持了半精度计算，使用FP16替换原来的FP32进行计算，可以节省一半的GPU显存占用，经验证Flat召回率由100%下降到99.4%，依然满足需求。使用半精度之后，单机可以加载近10亿数据，足够支撑较长时间的业务数据增长。

GPU 检索系统上线后实际性能数据如下（数据量1亿+）：

22年还有一篇早期的搜索基于elasticsearch的优化实践

https://mp.weixin.qq.com/s?__biz=MjM5NjQ5MTI5OA==&mid=2651772026&idx=1&sn=6ff4cb024bb416c46d5d2850a6ae77d1&chksm=bd120d378a6584217f1838c0f951204023e5c32b0ad413a731078e2f11f8f0009b39c3dec4ea&scene=21#wechat_redirect

但这个就很工程很机架了

下午在看milvus文档的时候看到着重提了稀疏检索，注意到bge-m3是有神经稀疏检索的支持的，于是学习了一下，下面属于纯入门笔记。

https://bge-model.com/bge/bge_m3.html

和传统的BM25等稀疏嵌入不同，bge-m3的稀疏嵌入是基于模型的，复用密集嵌入的前面层

BGE-M3 实现的是一种**“learned sparse embedding”（神经稀疏语义嵌入**）。与 SPLADE、uniCOIL 这类模型类似，这些都是让模型自适应学习每个 token 某种“匹配权重”，在大规模预训练和下游 fine-tune 时引入了专门的稀疏激活目标，使输出稀疏且有用

SPLADE 模型的全称为"Sparse Lexical and Expansion Model"（稀疏词法和扩展模型），结合了传统稀疏向量检索的优点和神经网络的语义理解能力。

$w_j = max_{i\in tokens} log(1 + ReLU(w_{ij}))$

BERT 的 MLM 头部会为每个输入位置计算对词汇表中每个词元的贡献分数。这些分数反映了当前上下文下，特定词元与其他词元的关联强度。

也就是说，这个方法实际处理了三个问题:

1. 词表不够大（或者分词精度不够）的问题，采用预训练BERT的词表和分词器，可以随着预训练模型的拓展而拓展；
2. 针对传统稀疏编码需要精确词匹配、编码值实际上都是离散变化的问题，采用遍历整个词表，利用BERT的mask-预测概率，计算将原始句子的每一个词与词汇表中其他词的关联强度，对应logits即为$w_{ij}$，从而实现了词汇的拓展，允许相关词、近义词匹配等
3. 针对传统BM25中没有上下文位置关系的问题，利用BERT的位置编码和捕获双向信息的预测，将传统手工设计特征的部分取代

还有一些其他的操作比如稀疏化，用于提供较密集嵌入更强的筛选能力

SPLADE 使用 ReLU 激活和 MAX 池化操作来确保生成稀疏向量。ReLU 将负值置为零，增加稀疏性；MAX 池化则为每个词元选择所有位置中的最大贡献值，进一步增强了稀疏性 1。

此外，SPLADE 还使用正则化（如 FLOPS 正则化）来控制稀疏性程度：

L_FLOPS = λ * ||q_splade||_1 * ||d_splade||_1

这个正则化项通过惩罚向量的 L1 范数（非零元素的绝对值和）来鼓励模型生成更稀疏的向量

还有一个问题是：这个“关联强度"是什么?

从模型的角度说，这个关联强度向量就是BERT的嵌入再过一个MLP得到(vocab_size, )的向量

但实际上，这里并没有直接使用BERT的mask预测权重，而是针对信息检索进行了微调（使用MS MARCO数据集，100万条搜索引擎搜索数据）

最后的损失函数是三者的加权组合

目前SPLADE稀疏向量的召回率已经显著由于BM25传统搜索引擎的召回率

但是BM25等传统方法就完全不行了吗？也未必，有文章指出SPLADE这样的基于模型的方法始终会受到预训练语料的领域限制，并且在垂域少量数据上训练/微调的成本开销都比较大，此时未必有简单的BM25 + 领域定制词典权重好

而作为召回的一道路径来说，还有许多额外的召回规则，例如通配符和前缀，编辑距离和短语......

很fashion的reranker https://www.mixedbread.com/blog/mxbai-rerank-v2

双模搜索：https://www.mixedbread.com/blog/the-hidden-ceiling

做了一系列实验证明了OCR质量在RAG系统中的重要性和目前的OCR方法质量的局限性，多模态生成用于检索的编码，OCR生成嵌入：检索时用能理解文本布局、复杂图表的多模态嵌入，而进入LLM的时候用OCR生成的文本

• 他们也实验了使用图片/嵌入直接进视觉LLM，但效果不佳。提出的观点是LLM能够容忍文本的噪声和解析错误（文字质量下降），但不太能容忍精致且无关的文本（搜索质量下降），在传统rag流程中，OCR质量下降会直接导致搜索质量下降

mq: 异步，解耦，削峰填谷

传统项目架构下，对网络波动没有耐受性

mq多用于分布式系统间进行通信

请求方/响应方 -> 生产者/消费者

优劣​

优势：异步，解耦，削峰填谷

• 解耦: 消费方存活与否不影响生产方
• 异步: 提速
• 削峰填谷（作为一个buffer/cache）, 提升系统稳定性，应对突发性高并发冲击

例子-电子商务下单：

生产者: 订单系统 -> MQ -> 库存系统、支付系统、物流系统、大数据系统(用户数据收集)（复制与多分发）

生产者发完消息，可以继续下一步业务逻辑

订单系统不需要新增业务代码，达成解耦

同时，订单系统可以发MQ消息之后就返回。准确地说，MQ消息 + 订单入库(校验等)

劣势：

• 可用性降低: MQ宕机就寄，需要保证MQ的高可用
• 系统复杂度提高：消息丢失? 消息保序？重复消费？
• 一致性问题：多消费，部分成功，部分失败？下游失败怎么办？

市面主流MQ产品：

• ActiveMQ: 万级吞吐，主从架构，ms延迟，现在不怎么用
• RabbitMQ: erlang，us处理，万级吞吐，主从架构，较难维护
• RocketMQ: java，十万级吞吐，ms级，分布式
• kafka: scala， 十万级，ms级，分布式，功能比较少

rocketmq: 17年双十一，TPS 5600w

架构​

生产者集群 Producer

消息服务器集群 Broker 接受消息，提供消息，消息持久化，过滤消息，高可用

消费者 Consumer

命名服务器集群 NameServer Cluster 存储元数据**（Broker IPs）**

producer，broker，consumer向nameserver注册，nameserver用心跳确认其他组件的存活

支持拉推两种模式，Consumer可以主动拉取，也可以用监听器模式

能推肯定是推省资源，免去轮询等

消息

• Message
• Topic 一级标题
• Tag 二级标题

基础流程:​

Producer：​

生产者创建 - 设置nameserver - 生产者启动 - 创建消息（指定topic，tag，内容）- 发送（获取结果）- 关闭生产者

发送结果是什么？主要是记录消息元数据例如消息ID的一个结构体，和Future那种设计不一样

Consumer​

两类： DefaultLitePullConsumer 和 DefaultMQPushConsumer

对应拉取(额外线程轮询)和推送(长连接)模式

消费者创建 - 设置nameserver - 设置监听(订阅)主题 - 注册监听器(消息处理函数类，返回消息处理结果) - 消费者启动

设置监听的api rocketmq是这样设计的

subscribe(<topic>, <subExpression>)

这个subExpression通过通配符等支持，让api 表达力变强不少

• 支持tag过滤
• 支持sql过滤，在给消息追加属性的时候很有用
  • ><= BETWEEN IN IS NULL AND OR NOT

OneToMany 多消费​

多个消费者监听一个topic的默认行为：

• 一条消息只会被消费一次
• 多个消费者之间有默认的负载均衡

如果想要多个消费者都消费这条消息呢？例如上面的电商情况

• 消费者组 consumer group概念

相同组的消费者，有负载均衡，单消费

• 也可以修改消息模式，将默认的消费模式改掉
  • CLUSTERING -> BROADCASTING

单条消息会被复制数份，发送到每一个消费者组

• “复制”是指HTTP传数次，不是存储文件复制

消息类型​

同步：即时性强、必须有回执，例如短信通知

异步：即时性弱，也需要有回执，如订单信息

单向：不需要有回执，如写日志

• eg 分布式日志系统，所有Producer只管发

直接send(msg) 是发同步消息

send(msg, callback)是异步，等有结果再做处理

sendOneway是单向

延时消息

早期: v4.x

只支持不同的delayLevel，固定的1s 1m这样的时间

• 固定级别的延时消息实现简单，为每个延时类别创建单独的队列来管理， 采用内部特定主题（SCHEDULE_TOPIC_XXXX）和队列来实现延时功能
• 可能是简单的分队列定时扫描算法

后来：v5+

任意毫秒级时间戳延时，需要高效时间轮算法, 每条消息单独计时器跟踪

• 时间轮算法：小时轮，分钟轮，秒钟轮。将消息“填入时间轮槽”（即每个槽是一个TaskList）

  • 层级时间轮，如果一个任务是1分30s, 会先被放入1分的分钟轮，处理到时，减去1分，降级放入秒钟轮

• 将时间线分割成多个区间，不同区间采用不同精度的扫描策略, 近期消息采用高精度扫描，远期消息采用低频率扫描

• 高效索引，分布式时钟对齐.....

批量消息

底层支持直接传 Collection<Message>

注意:

• 相同的topic
• 不能是延时消息
• 总长度不超过4M (IBM默认最大消息长度设置，可以通过改环境变量修改，但4M算是一个实验值)
• 相同的waitStoreMsgOK

Spring IoC集成​

直接在配置文件中指定name-server， producer group之类

类似Kafka/Redis, RocketMQTemplate 链接管理

convertAndSend 方法

• convert? Spring的Template send发送的是抽象的message，只有一个byte[]的payload，convert就是在处理上层java类与下层不同的template需要的通信格式的转换

消费者也是和Kafka类似的

@Service的类 implements RocketMQListener<MessageType> 就行, @RocketMQListener(topic=, tag=,consumerGroup=, selctorExpression=, selectorType=, messageModal=)

然后这个类就作为监听类了，调用的方法就是重载方法onMessage(T t)

(这里Spring顺带还做了个返回值处理，只要没抛异常都是消费成功，抛异常消费失败回传)

其他的机制也整合了，例如同步异步单向延时批量之类对应syncSend, asyncSend, ...

消息保序​

消息错乱的原因，队列内有序，队列外无序

要做多队列的负载均衡，就不能无开销严格保证顺序

一连串的消息需要作为一个不能被拆分到多个负载均衡队列的整体

• 一个实现messagequeueSelector的实体类，例如id hash + 取模

事务消息（无丢）​

本地事务：如入本地数据库

事务状态：

• 提交状态，允许进入队列
• 回滚状态，不允许进入队列，当作没发生过
• 中间状态，未对half做二次确认

代码实现

TransactionMQProducer

setTransactionListener: 正常事务过程, 补偿过程

• executeLocalTransaction: 正常事务，入库等，根据本地事务状态返回消息状态
• checkLocalTransaction：在正常事务超时等情况（实际上是正常事务函数返回了UNKNOW状态）时被调用，本地再次查询事务状态的函数

事务补偿还是UNKNOW?写个log或者其他人工介入方式

集群搭建​

多broker：

多master多slave架构

master slave同步消息的方式可以是同步（生产者阻塞请求）也可以是异步（不阻塞）

常见：一主三从

• 只有brokerId为0的是主节点
• brokerName是集群名

每一个broker会向所有的nameserver注册

高级特性​

消息存储

一次完整的消费需要两个ACK

即Producer向Broker发消息，Broker返回ACK

Broker向Consumer发消息，Consumer返回ACK

但如果中间Broker宕机，就会出现重复消费

例如，在Broker返回ACK之前宕机，Producer就可能再发一次消息；在Consumer返回ACK之前宕机，Broker就可能再发一次消息。

解决方案是，在Broker返回Producer ACK之前，先将消息存储到磁盘上持久化（数据库中），在接收到Consumer ACK之后，Broker删除这一条消息

• 如果在返回Producer ACK之前宕机，能从磁盘读消息避免重发
• 如果在Consumer返回ACK之前宕机，也是同理

消息的存储介质

使用数据库：

• ActiveMQ：缺点是数据库瓶颈成为MQ瓶颈

文件系统：

• RocketMQ/Kafka/RabbitMQ：采用消息刷盘机制，进行数据存储

zero copy：mmap，java MappedByteBuffer

预留了一块空间进行顺序读写，默认1G commitlog

本质上，利用mmap,sendfile等系统api减少了内核空间与用户空间的数据交换次数。mmap处理文件-内存在内核态直通，sendfile处理内存-网络在内核态直通。省去的是内核态内存页到用户态内存页的拷贝，zero copy的用户程序都是没有持有数据copy的buffer的。

刷盘机制

同步刷盘：先入盘再返回ACK

• 可靠性高，性能低

异步刷盘：不挂起Producer线程，也先不写硬盘，将消息保留到内存之后就向Producer返回ACK，而是积累到一定batch的消息，再批量刷盘

高可用：

• nameserver:
  • 无状态+全服务器注册
• 消息服务器
  • 主从架构，2主2从
• 消息生产
  • 生产者将相同的topic绑定到多个group组，保障master挂掉之后，其他master仍然可以正常接受消息
• 消息消费：RocketMQ会根据master压力确认是否由master承担数据读取功能，master繁忙的时候，自动切换slave做承担数据读取的工作（读写分离）

负载均衡

Producer负载均衡

• RocketMQ内部实现了不同broker集群中对同一topic对应消费队列的负载均衡

Consumer负载均衡

• 平均分配(AABBCC)不好，循环平均分配(ABCABC)好
  • 原因，broker部分挂掉时，生产者的流量会被均分到剩下的broker上，如果平均分配，则有些对应挂掉的broker的consumer就不干活了，其他consumer压力会变大；循环平均分配则是将所有的consumer都分到剩下的broker上，避免了单个consumer压力过大

消息重试：

顺序消息：

• 当消费消息失败后，RocketMQ会以1s为间隔进行自动重试。
• 应用会出现消息消费被阻塞的情况，因此需要对顺序消息的消费情况进行监控（监控offset等），避免阻塞

无序消息：

• 仅适用于负载均衡（集群）模型下的消息消费，不适用于广播模式

• MQ设定了合理的消息重试间隔时长，有一个指数的backoff

• 当重试到达指定次数（默认16次）后，MQ将无法被正常消费的消息称为死信消息。死信消息不会被直接抛弃，而是会被发送到一个死信队列中，供后续处理

死信消息不会再被重复消费，有效期为3天，过时后会被删除

死信处理，业务逻辑处理，或者人工介入

RocketMQ不可能完全避免重复消费，还是存在可能出现重复消费的情况：

• 生产者发送重复消息，例如，网络闪断没收到ACK，生产者宕机
• Broker和消费者之间网络闪断，消费者/broker重启
• 客户端扩缩容
• ......

所以不能完全依赖RocketMQ的幂等性，还是要在业务逻辑上做幂等性处理

• 使用业务id作为消息key
• 在消费消息时，客户端对key做判定，未使用放行，使用过抛弃
• 注意：messageId由RocketMQ生成，不具有唯一性，不能做幂等判定条件

Kafka VS RocketMQ​

Kafka:

• 专注简单与吞吐量: "Do one thing and do it well"的Unix哲学，专注于高吞吐的消息传递
• 不可变数据流: 将消息视为不可变的数据流，适合事件溯源和流处理
• 客户端复杂性: 将复杂性推向客户端，保持服务端简单高效

RocketMQ:

• 丰富的消息功能: 目标是作为全功能的企业级消息系统
• 服务端智能: 在服务端实现更多功能，减轻客户端负担
• 电商场景驱动: 由阿里巴巴电商业务需求驱动设计，面向复杂业务场景

那么古尔丹，高吞吐量的代价是什么呢？

• 偏移量指针的设计只能顺序前进，无法原生支持延迟时间，通过时间戳索引查找偏移量、专用延时主题、定时扫描来达到延时队列
• 必须顺序处理消息，无法灵活跳过（异常消息）和回退（重放）
• 消息路由和分布式一致性绑定，路由灵活性受限
• 不支持消息优先级队列，因为都得按照offset指针顺序处理.....
• 无法设置可见性超时等，都需要上层应用做
• 消费失败的幂等性保证处理复杂，偏移量需要分布式维护增加网络开销.....

核心设计的哪些不同带来了这样的差异？

存储模型

Kafka:

• 分散的文件存储: 每个主题的每个分区对应一个物理文件，消息按照写入顺序存储 1
• 顺序追加写入: 使用顺序追加的方式写入文件，不允许修改已写入的数据
• 偏移量指针: 消费者通过偏移量指针确定读取位置，不复制消息

RocketMQ:

• 统一的文件存储: 所有主题的消息存储在同一组物理文件中 3
• 逻辑分区: 主题和队列仅是逻辑概念，不与物理文件一一对应
• 消息索引: 维护更复杂的索引结构，支持按多种方式查询消息

消息投递模型

Kafka:

• 基于分区的消费模型: 消费者组内的消费者分配分区，消费者只能按顺序消费分区中的消息 1
• 仅支持拉模式: 消费者主动从Broker拉取消息

RocketMQ:

• 更灵活的消费模型: 支持更多的消费模式，包括集群消费和广播消费 1
• 推拉结合: 同时支持推模式和拉模式，提供更灵活的消息投递方式
• 消息过滤: 支持在服务器端进行消息过滤，减少不必要的网络传输

消息处理机制

Kafka: 消息就是字节数组

**RocketMQ: ** 消息包含更多元数据和属性

vgg​

内存占用大，推理慢（深），但效果好

卷积层参数小，全连接层最大问题是参数太大过拟合

所以最后一层全连接是很大的问题

大参数还有内存 bound 的问题

NiN​

用卷积层替代全连接

两个 1*1 卷积无 padding, stride1 起全连接的作用(只做通道混合)

每个卷积后面跟两个全连接作为 NiN block

交替使用 NiN 块和 stride = 2 的 maxpooling 逐步减小高宽和增大通道数

最后使用全局平均池化得到输出(通道数 = 分类个数)

打印结构:

for layer in net:
    X = layer(X)
    print(layer.__class__.__name__, "output shape:\t", X.shape)

超级宽的 hidden layer: 非常容易过拟合

泛化性提高-> 收敛变慢

全连接的方案: 非常强, 收敛很快

GoogLeNet​

inception 块: 不做选择, 全都要

output = output1 + o2 + o3 + o4

o1 = conv1x1

o2 = conv1x1 + conv3x3, padding 1

o3 = conv1x1 + conv3x3, padding 1 + conv5x5, padding 2

o4 = 3x3 maxpool, padding 1

四条路径从不同层面抽取信息, 在输出通道合并 concatenation

四条路径分配不同的通道数(你认为那种模式哪个通道的信息更重要)

降低通道数来控制模型复杂度

googlenet 5 段, 9 个 inception 块

不降低维数的 1x1 卷积就是通道融合

第一个 stage 总是把通道数拉上去, 高宽减下去, 先筛选出足够多的特征

v2: batch normalization

v3: 5x5-> 3x3, 5x5-> 1x7+7x1(单长和单宽)

v4: 残差连接

优点是模型参数少, 计算复杂度低

批量归一化​

损失出现在最后, 后面的层训练快

反向传播: loss 在顶层, 数据在最底部, 底部的层(前面的层)训练慢, 底部层一变, 所有都得跟着变

导致离 loss 近的后面层需要重新学习多次, 导致收敛变慢

有没有方法让学习前面层的时候避免变化后面层?

批量归一化: 将分布固定, 来让输出模式稳定一些, 固定小批量的均值和方差

正则化, 将数据分布固定为 $N(0,1)$ 正态分布, 数据的修改只是在变化正态分布的超参数, 限制变化不要太剧烈

对于全连接, 作用 在激活函数前面, 作用在特征维度

对卷积, 作用在通道维

效果太好了, 原始论文觉得是减少内部协变量转移, 后续发现 可能就是等效于在每个小批量里面加入噪音来控制模型, 均值近似于随机偏移, 方差近似于随机缩放

因此没必要和丢弃混合使用

加速收敛(模式更稳定之后可以把 lr 调得更大), 但一般不改变模型精度

根据内存挑 batch size, 不能太大也不能太小, 然后调学习率和 epoch

ResNet​

残差的重要性不必多言

深网络必有残差思想

新硬件​

DSP 主要做数字计算处理长指令, FPGA 可编程阵列

工具链质量良莠不齐, 一次 "编译" 需要很久

AI ASIC: Google TPU eg

核心 systolic array, 专门做大矩阵乘法 2d 计算单元(PE)阵列, 卷积换成矩阵乘法

一般的矩阵乘: 切开和填充匹配 SA 大小

批量输入来降低延时, 其他硬件单元来处理别的 NN 操作子, 例如激活层

多卡并行​

数据并行(切割小批量), 模型并行(切割模型, 适用于模型太大的时候),

all reduce: 将所有 gpu 的结果放到一个 gpu 上, 然后相加, 加完再复制回其他 gpu

nn.parallel.scatter

nn.DataParallel

多卡时也要相应的加大 batchsize 和 lr

大 batch size 在小模型上会采出重复样本导致浪费和一定程度上的过拟合

分布式

GPU 和 GPU 通信快, 和 CPU 通信慢, 和交换机网卡更慢

• 类似存储器山

解法是把 parameter server 尽量从 cpu 搬到 gpu 上

这样简单的 parameter 迁移分配就能在 gpu 本地完成, 不涉及到 cpu 的 copy(感觉像 DMA)

每个 worker 拿参数, 复制到 GPU 上, 每个 GPU 算自己的梯度, GPU 梯度求和, 传回服务器, 再更新, 回发

类似 mr, server mapper, 本地 gpu 完成计算和 combine, 在 server reduce

同步 SGD, 每个 worker 同步计算一个批量

所以需要调 batch size, 来针对并行省下的时间与通信开销做 trade off

实践:

• 大数据集
• 好的 GPU-GPU 和机器-机器带宽
• 高效的数据读取和预处理
• 好的计算(FLOP)和通信(model size)比 Inception > ResNet > AlexNet
• 足够大的 batch size
• 高效优化算法（因为 batch size 变大了, 如何适配）
• 更复杂的分布式有异步, 模型并行

一般 N 个类, batch size 差不多到 10N 再往上就不太能 fit 了

数据增广​

已有数据集让他有更多多样性

• 在语言里面加背景噪音
• 改变图片的亮度, 颜色, 形状

一般的做法: 原始数据在线生成, 随机增强

测试不做增强

翻转:

• 左右翻转, 上下翻转
• 切割, 随即高宽比, 随机大小, 随机位置

其他:

• 高斯模糊
• 锐化
• 变形
• 滤镜
• 马赛克（相当于遮挡, 逼着去看全局）
• ...

从实际部署的场景反推需要什么样的增强

异常检测, 偏斜数据, 重采样, 增广

mixup 增广: 有效但不知道为什么

torchvision.transforms

微调(迁移学习)​

标注一个数据集很贵

希望在大数据集上做好的东西, 能以小代价迁移到小数据集上

神经网络分层两块: 特征提取+线性分类

dl: 让特征提取变得可以学习, 而不是人来提取特征

训练:

• 更强正则化
• 更小学习率
• 更少的数据迭代

源数据集远复杂于目标, 微调效果更好

固定一些层, 固定底部一些层的参数, 不参与更新

低层次的特征更加通用

小 trick, 微调的时候最后一层用大学习率, 前面用小的

迁移的也不能差太大, 否则效果很可能不够好

目标检测​

bounding box

锚框: 提出多个被称为锚框的区域, 预测每个框里面是否有关注的物体, 如果是, 预测锚框到真实框的偏移

交并比 IoU

每个锚框是一个训练样本, 要么标注成背景, 要么关联一个真实边缘框

可能生成大量锚框, 导致大量的负类样本

选择合适的锚框(赋予锚框标号):

先生成一堆框, 之后算锚框 i 和真实框 j 的 IoU, 在 i, j 之中找最大的, 就得到了一组锚框和真实框的对应

然后从集合中剔除这个锚框 i 和边缘框 j(删除矩阵行列), 再找下一组

重复直到真实框为空, 这就是正类样本, 剩下的锚框挑一些作为负类样本

锚框生成: 一种固定切分画格子

NMS 非极大抑制: 合并相似的预测框

• 选中非背景类的最大预测值
• 去掉所有和它 IoU 大于阈值的预测
• 重复直到所有预测要么被选中, 要么被去掉

生成锚框的另一种示例方法

宽度 $ws\sqrt r$, 高度 $hs/\sqrt{r}$

对给定几组 $(s,r)$ 对每(n)个像素生成

算法的核心之一: 如何生成高质量锚框

锚框到偏移的算法: 多种多样

autogluon

工业界很少用模型融合和测试增强, 计算代价过高

通常固定模型超参数, 简单模型, 精力花在提升数据质量和加入的新数据

RCNN:

启发式搜索算法选择锚框

预训练模型对每个锚框抽取特征

训练一个 SVM 对类别分类

训练一个线性回归来预测偏移

RoI pooling

锚框均匀分割 mxn, 输出每块里面的最大值

不管锚框多大, 总是输出 mn

Fast RCNN

不再对每一个锚框抽取特征

而是将所有的锚框丢进 cnn(输入里面对应的映射区域), 一次 CNN 对整个图片抽取

Faster RCNN: 使用区域提议网络代替启发式搜索来获得更好的锚框

2-stage

Mask RCNN 如果有像素级别的编号, 给每个像素做预测, 用 FCN 利用信息

Faster RCNN: 速度非常慢, 精度高

SSD: single stage

基础网络抽特征, 多个 conv 减半高宽

每段都生成锚框

• 底部段拟合小物体, 顶部段拟合大物体

对每个锚框预测类别和边缘框

yolo: 追求快

ssd 锚框大量重叠, 浪费计算

均匀切分 SxS 个锚框, 每个锚框预测 B 个边缘框

后续有许多微调和改进

工业常用

非锚框: 例如 central net

语义分割​

像素级分类

应用: 背景虚化, 路面分割

另一个相近的概念: 实例分割

数据集: 输入是图片, label 也是图片(每个像素的值就是 label)

crop: 怎么做, 对输入进行裁剪, 在 label 上也要相对应的裁剪

拉伸也是需要特殊处理的

旋转? 一种是可以加一个 label 是旋转角度, 另一个是可以在转完的斜框上涨再画一个大框框住斜框

人像: 难点在光照, 阴影和背景

人像语义分割: pretrain model 已经很成熟

转置卷积​

卷积的问题：不能很有效的增加高宽

类似语义分割这种-> 卷积不断减小高宽, 会影响像素级别的输出

$Y[i:i+h, j:j+w] += X[i,j] \times K$

增大输入高宽

为什么是转置卷积:

卷积等价于矩阵乘法 $Y = VX$, 转置卷积就是 $Y = V^{T}X$

nn.ConvTranspose2d

卷积是下采样, 卷积是上采样

转置卷积与线性插值: 可以用线性插值作为转置卷积核的初始值

FCN​

全连接卷积神经网络

用 dl 做语义分割的最早工作

用转置卷积替换 CNN 最后的全连接层+全局池化

• 先过 1x1 conv 压缩通道
• 再过转置卷积拉大图片, 得到像素级别的切分
  • 思想是每个像素的的 label 信息这个 feature 应该存在 channels 里面

net = nn.Sequential(*list(pretrained_cnn.children()))[:-2]

可以用双线性插值的矩阵初始化转置卷积层的 kernel

loss: 由于每一个像素都有了 label

所以在矩阵上做均值再 cross_entropy

样式迁移​

基于 CNN 的样式迁移

核心思想: 训练一个 CNN, 将他作用在内容图片上得到输出, 在样式图片上得到输出

而输出图片在内容层上的输出和内容图片在内容层上的输出相近(content loss)

输出图片在样式层上的输出和样式图片在样式层上的输出相近(style loss)

训练的不是 CNN, 而是输入网络的的“输出图片”

哪些层是“style layer”, 哪些是 "content layer"?

样式: 最小, 中间和上层, 较均匀

• 样式有全局的特征和局部的特征, 各个尺度均有

内容: 偏末尾的层, 靠近 loss

• 允许内容上更多的变形

内容损失可以是简单的 MSE

• 元素值, 通道里面的值, 认为是内容

样式损失? 通道内部和之间的统计分布, 认为是样式

• 分布匹配, 一阶平均值, 二阶协方差, 用二阶就还不错

最后: tv_loss, 不要有噪点, 每个像素和周围像素不要差太多, 计算每个与周围的 MSE 再求平均

这几个损失如何加起来? 加权平均, 权值是超参数

style 一般更重要, 例如 content:style:tv=1:1000:10

这几个超参数的调整是训练几次之后, 观察三种 loss, 调到差不多大小得出的

不更新: y.detach()

卷积只作为抽特征

麻烦: 后续技术, GAN, 使用 CNN 接收随机输入生成图片等

序列模型​

标号和样本是一个东西: 自回归模型 t-k ~ t-1 -> t

方法 A: 马尔可夫假设: 假设当前数据只和 k 个过去数据点相关

方法 B: 潜变量模型: 引入潜变量 $h_t$ 来表示过去信息 $x_t = p(x_t|h_t)$, $h_t = f(x_1,...x_{t-1})$

那我们就可以将预测拆成两步:

1. $h_t = Model1(h_{t-1}, x_{t-1})$
2. $x_t = Model2(h_t, x_{t-1})$

文本预处理​

预处理的核心是分词

GPU 上存算的是 token 索引而非字符串

语言模型:

给定文本序列, 估计联合概率

• 做预训练模型
• 生成文本
• 判断多个序列之中哪个更常见

简单方法: 基于计数建模

序列很长的时候, 由于文本量不够大, 可能 $n(x_1,...x_t)\le 1$

使用马尔可夫假设缓解, n 元语法假设, 假设只和前 n 个词相关

以二元为例, 则有 $p(x_1,x_2,x_3,x_4) = \frac{n(x_1)}{x1} \frac{n(x_1,x_2)}{n(x1)} \frac{n(x_2,x_3)}{n(x2)} \frac{n(x_3,x_4)}{n(x3)}$

RNN​

更新隐藏状态: $h_t = \phi (W_{hh}h_{t-1} + W_{hx}x_{t-1} + b_h)$

输出: $o_t = \phi (W_{ho}h_t + b_o)$

训练的模型: $W_{hh}, W_{hx}, W_{ho}, b_h, b_o$

如果没有 $W_{hh}h_{t-1}$ 就是 MLP

loss 设计: 困惑度 perplexity

把输出看成是词典大小为 label 数量的话, 可以用交叉熵, 然后对整个句子取平均

但实际不是用这个, 而是用 exp(平均交叉熵)

梯度裁剪: 在 T 个时间步上的梯度, 反向传播 O(T)矩阵乘法, 梯度爆炸

如果梯度长度超过 $\theta$, 变回 $\theta$

$g \times min(1, \frac{\theta}{||g||}) \to g$

更多的 RNN:

• 1 对多: 文本生成
• 多对 1: 文本分类
• 多对多: 问答, 机器翻译
• 多对多: tag 生成

GRU&LSTM​

对于一个序列, 记住相关观察需要 更新门(能关注的机制) + 重置门(能遗忘的机制)

$R_t = \sigma (X_tW_{xr} + H_{t-1}W_{hr} + b_r)$ reset gate

$Z_t = \sigma (X_tW_{xz} + H_{t-1}W_{hz} + b_z)$ update gate

候选隐状态

$H_{cand(t)} = tanh(X_tW_{xh} + (R_t \odot H_{t-1})W_{hh}+b_h)$

$R_t$ : $[0,1]$ 软控制

$H_t = Z_t \odot H_{t-1} + (1 - Z_t) \odot H_{cand(t)}$

隐藏层多大? 例如 128,256, 长序列就 1024

实际不考虑 RNN, 一般 GRU/LSTM

超过 100,1000 这样的长度量级, 考虑 Attention

LSTM

忘记门: 将值朝 0 减少

输入门: 决定是不是忽略输入

输出门: 决定是不是使用隐状态

更深(多个隐藏层)的 RNN, 更多的非线性性

双向 RNN

一个前向 RNN 隐层

一个反向 RNN 隐层

合并两个得到输出

output 是前向和反向的共同贡献

推理怎么推? 非常不适合做推理, 几乎不能推

主要作用: 对句子做特征提取, 填空, 而不是预测未来

输入需要定长(为了以 batch 的形式读入)

如何做不定长的? 填充或者截断, 例如翻译

encoder-decoder 架构​

encoder: 将输入编程成中间表达形式(特征)

decoder: 将中间表示解码成输出

encoder 将 state 传给解码器做输入

seq2seq​

encoder 是一个 RNN, 可以双向

decoder 是另一个 RNN

编码器是没有输出的 RNN

encoder 最后时间步的 hidden state 作为 decoder 的初始 hidden state

训练, 训练时 decoder 用目标句子作为输入

衡量生成序列的好坏: BLEU

exp 项: 防止 pred 句子长度过短偷懒提高精度

BLEU 越大越好

seq2seq: 从一个句子生成另一个句子

sequence_mask：在序列中屏蔽不相关的项(padding)

拓展 softmax 来屏蔽不相关的预测(padding 对应的 output)

预测

最开始输入 <bos>, 然后 RNN 每次输出作为下一个的输入

seq2seq 可以纯 transformer

束搜索​

beam search

seq2seq：用当前时刻预测概率最大词输出（贪心）

但贪心很可能不是最优的

暴搜指数级增长肯定不行

bin search: 对每个时刻, 保存最好的 K 个序列

每一次新预测会对 k 的 kn 个可能的下一个序列之中再调最好的 k 个

如何选择 "最好"?

单纯的概率乘总是倾向于选择短句子, 需要给长句子加权

每个候选的最终分数 $\frac{1}{L^{\alpha}}logp(y_1,...y_L)$, 取 $\alpha=0.75 < 1$ 给长句子加权

Attention​

卷积, 全连接, 池化只考虑“不随意”的线索

• "最大值", 明显的特征

注意力机制显式地考虑随意线索

• 随意线索被称为查询 query
• 每个输入是一个值 value 和不随意线索 key 的对
• 通过注意力池化层来对有偏向性的选择某些输入

非参(不需要任何先验参数)注意力池化层

给定数据(环境, 先验, context) $(x_i,y_i)$

查询: 给定一个 x, 求对应的 $y=f(x)$

注意力: $f(x)=\sum_i \alpha(x,x_i)y_i$, $\alpha(x,x_i)$ 就是注意力权重

最简单的方法: 平均池化, $f(x)=\frac{1}{n}\sum_i y_i$

更好的方案是 60 年代的 Nadaraya-Watson 核回归

$f(x)=\sum_{i} \frac{K(x-x_i)}{\sum_j K(x-x_j)}y_i$

高斯核 $K(u)=\frac{1}{\sqrt{2\pi}}exp(-\frac{u^2}{2})$

$f(x)= \sum_{i} softmax(-\frac{1}{2}(x-x_i)^2)y_i$

参数化:

再引入可以学习的 w

$f(x)= \sum_{i} softmax(-\frac{1}{2}((x-x_i)w)^2)y_i$

相较非参的注意力, 变得更不平滑

拓展到高维度 $\alpha(q, k_i)$

1. Additive Attention: 可学参数 $W_k \in R^{h\times k}$, $W_q \in R^{h\times q}$, $v \in R^{h}$

$a(k,q) = v^{T}tanh(W_kk + W_qq)$

等价于将 kv 合并之后放入一个隐藏大小为 h, 输出大小为 1 的单隐藏层 MLP

也是当 q, k 不一样长的时候最常用的做法

如果 q, k 都是同样长度的

2.Scaled Dot-Product Attention

$a(q,k_i)=<q,k_i>/\sqrt{d_k}$, 相当于 q 在 k 基上的分量+归一化

$a(Q,K)=QK^{T}/\sqrt{d}$

$f=softmax(a(Q,K))V$

Q, K, V 是一个矩阵？self-attention 自注意力 $f=softmax(XX^{T}/\sqrt d))X$

但实际运用会给 X 做不同线性线性变换后再输入

$f=softmax(XW_QX^{T}W_K/\sqrt d))XW_V$

Attention 机制的 seq2seq​

翻译的词可能相关于原始句子之中不同的值

原始 seq2seq 只能看到单一词的输入, 虽然有隐藏层, 但长距离丢失信息

• encoder 的对每个词的输出作为 key 和 value（key = value）

• decoder RNN 对上一个词的输出是 query

• attention 的输出和下一个词的 embedding 合并进入 decoder

原始的 seq2seq 相当于是只将上一个词的 state+t-1 时刻的 encoder 输出丢到了 decoder 里面

$decoder(state_{t}, eoutput_{t}, output_{t-1})$

现在拓展其表达力, 认为 decoder 应该获取的不是单单最后一个词的输出, 而是和之前的词输出(更长的上下文)都有点关系, 具体关系用 attention 学习, 以编码器的 output 作为 query key, 获取这个 output 最相关的上下文, 并认为翻译的文本之中也应该有类似的上下文关系

$decoder(state_t, attention(output_{t-1}, eoutputs, eoutputs))$

tokenizer: sentencepiece

embedding: 专业词, 需要调整 tokenizer, 需要添加词 pair, 需要训练新添加的 embedding, 正常领域 frozen 不动, 加 LoRA/Adapter

自注意力​

self-attention

序列长度是 n, 卷积核大小 k

自注意力适合处理长文本

代价: 计算代价 $n^2$ 增长

位置编码:

和 CNN, RNN 不同, 自注意力没有记录位置的信息, 位置编码将位置信息注入到输入里

• 输入 $X\in R^{n\times d}$, 叠加位置编码 P, X+P 作为自编码输入

$p_{i,2j}=sin(\frac{i}{10000^{2j/d}}),p_{i,2j+1}=cos(\frac{i}{10000^{2j/d}})$

为什么这么设计

记 $\omega_j = 1/10000^{2j/d}$, $p_{i+\delta} = RotateMatrix(\delta \omega_j) \times p_{i,\delta}$

所以实际上是相对位置的编码

也就是对于同一个序列 j, 位置 i 有 <i, i+k> 的关系的 pair 始终是一个相同的关系

Transformer​

纯基于(self-)attention

encoder-decoder 架构

multi-head attention

对同一的 QKV, 希望抽取不同的信息

使用 h 个独特的注意力池化

attention 没有时序信息, encoder 无所谓

decoder 不应该看到不该看到的信息, 需要加入掩码

计算 $x_i$ 输出时, 假装当前序列长度为 i

基于位置的前馈网络 Positionwise FFN

将输入形状 $(b, n, d)$ 变换成 $(bn, d)$, 输出再换回来

两层全连接, 添加非线性, 做更多的特征融合

$FFN(x)=f(xW^{T}_{1})W_2$

Add&Norm: 残差+归一化

编码器的输出 y_1, ... y_n

作为解码器之中第 i 个 transformer 块之中多头注意力的 key 和 value

预测, t+1 输出

decoder 输入前 t 个预测值作为 key, value, 第 t 个预测还作为 query

Bert​

nlp 的迁移学习

使用 pretrain 的模型抽取词句的特征

不更新 pretrain 模型

问题: 1. 做 embedding 的话忽略了时序信息 2.后续模型还要自己设计, 只有 embedding 似乎没有很大用处

Bert: 能不能也通过改最后一层复用?

只有编码器的 transformer

对输入的修改:

• 每个样本都是一个句子对

• 加入额外的片段嵌入

• 位置编码可学习

三种 embedding: position, segment, token

通用的任务?

任务 1: 带掩码的语言模型

带掩码的语言模型每次随机(15%概率)将一些词元换成 <mask>

微调任务之中不出现 <mask>

微调任务是没有 <mask> 标记的，如果设计方案是：只要 token 被选中 mask 处理，并且处理方法只要一种就是 token 别替换为 <mask>，这样的话，预训练任务和微调任务的数据太不一样了。BERT 的 3 种 mask 方法，可以使得，有 20%情况，句子对没有 <mask> 标记。

我理解的说白了就是不仅仅是因为看到了 <mask> 才去找上下文的信息，而是一直保持联系上下文的“习惯”

• 80%下, 变成 <mask>
• 10%, 随机(错误的结果)
• 10%, 原有(正确的结果)

10%的词会被替换成随机词元的原因： 作者在论文中谈到了采取上面的 mask 策略的好处。大致是说采用上面的策略后，Transformer encoder 就不知道会让其预测哪个单词，或者说不知道哪个单词会被随机单词给替换掉，那么它就不得不保持每个输入 token 的一个上下文的表征分布(a distributional contextual representation)。也就是说如果模型学习到了要预测的单词是什么，那么就会丢失对上下文信息的学习，而如果模型训练过程中无法学习到哪个单词会被预测，那么就必须通过学习上下文的信息来判断出需要预测的单词，这样的模型才具有对句子的特征表示能力。另外，由于随机替换相对句子中所有 tokens 的发生概率只有 1.5%(即 15%的 10%)，所以并不会影响到模型的语言理解能力。（网上复制的，这是我找到的可以说服我自己的一个解释）

任务 2: 下一句子预测:

训练样本之中, 50%选择相邻句子对, 50%选择随机句子对

微调 Bert​

bert 对每一个次元返回抽取了上下文信息的特征向量

不同的任务取不同的特征

• 句子分类, 将 <cls> 对应的向量输入到 MLP 分类
• 命名实体识别, 识别一个词元是不是命名实体, 例如人名机构位置
  • 把每一个非特殊词元(不是 <cls><sep>...)放进 MLP 分类
• 问题回答: 给定一个问题和描述文字, 找一个片段作为回答
  • 对片段的每一个词元预测是不是回答的开头或者结束

实用机器学习

不讲模型, 讲数据

知识积累, 学会读论文, 经典论文需要读懂每一句话

结合代码了解细节

对读过的论文做整理

lec2​

join: inner join, natural join, outer join

sql 实际执行模型 写起来是 SELECT - FROM - GROUP BY - HAVING - WHERE - DISTINCT - ORDER BY

实际是 FROM(table过滤) - GRUOP BY(行分组) - HAVING(组过滤) - WHERE(行过滤) - DISTINCT(行去重) - SELECT(行内列过滤)

inner join:叉积，对AB所有行组合

SELECT * FROM TABLE1 t1, TABLE2 t2 
	WHERE t1.id = t2.id
	AND ...
-- 等效于
SELECT * FROM 
	TABLE1 t1 INNER JOIN TABLE2 t2
    ON t1.id = t2.id
    WHERE ...
-- 下面这种更加清晰一点
-- 等效于
SELECT * FROM 
	TABLE1 t1 NATURAL JOIN TABLE2 t2
    WHERE ...
-- natural join就是在组合的基础上自动用了一个过滤，要求table所有相同名字的列的值都相同

outer join:

Left Outer join:

A LEFT OUTER JOIN B ON cond 如果cond满足的话，得到的是AB的组合（一行有A的列+B的列）;如果不满足，得到A的列+空

Right Outer Join 同理

Full Outer Join 同理 例如ON A.id = B.id

如果有A没有对应的B, 那就是是 A + 空

如果有B没有对应的A, 那就是 空 + B

非常好的图

alias

简化 + 看起来更清楚（尤其是self-join）

FROM TABLE1 AS x, TABLE1 AS y

String Comp

LIKE或者正则S.name ~ '^B.*' (等效于S.name LIKE 'B_%')

AND OR 做条件交并

EXCEPT UNION (ALL) INTERSECT做子查询结果集合的交并差

IN EXISTS用于子查询 (NOT IN, NOT EXIST) EXISTS是判空

SELECT S.sname FROM Sailors S WHERE S.sid IN 
	(SELECT R.sid FROM Reserves R WHERE R.bid=102)

还有ANY ALL

ARGMAX?

SELECT * FROM Sailors S WHERE
	S.rating >= ALL
		(SELECT S2.rating FROM Sailors S2)

View: Named Queries

CREATE VIEW xxx
  AS ...

SELECT * FROM xxx;

cache and reuse

或者

WITH [viewname] AS [statement]创建一个临时view

NULL 参与的运算大多是NULL, 除了IS NULL，False AND NULL这种

lec3​

Disk & Buffer

整体架构

SQL client-> Query Parsing & Optimization->Relational Operators-> Files and Index Management->Buffer Management->Disk Space Management

Concurrency Control & Recovery

磁盘太慢，需要尽量减少读写，且寻道和旋转时间是大头

"block" && "page": 一个意思，磁盘上的块状读写最小单元 一般64KB-128KB

为了重用硬件驱动，经常会将磁盘空间管理器建立在文件系统API上，但带来了一些大数据库多文件系统的问题，也有直接建立在设备上的，更快但是移植性问题

给上层的抽象是一个巨大的文件

DB file: page的集合，每个page又包含了许多records

给上层提供：CRUD on records

record解构成一个"指针" {pageID, location on page}

structures

• Unordered Heap Files(和数据结构heap没啥关系，无序records)
• Clustered Heap Files
• Sorted Files
• Index Files

如何组织page呢？

链表？ 想想就知道效率很差

类似目录的形式？ 部分page只存到其他page的指针，并且始终放在缓存之中

page解构

Page Header:

• Number of records
• Free space
• Mayba a last/next pointer
• Bitmaps, slot table

record 中间留不留空？

不留空：Fixed Length Records, Packed

header后面跟紧密定长records, 因此可以有 record id = {pageId, record number in page}， 简单运算得到location

加很简单，直接append

删，全移一遍？->O(N),自然想到能不能lazy delete或者soft delete

方法是在header里面放一个delete bit的bitmap

变长？

slotted page

将信息存在footer（称为slot directory）, record从头部开始存

由record id得到dir中位置，位置里面是pointer + length，

删，将slot dir中的项置空

插入，插在空位上，更新slot dir

fragmentation?

什么时候reorganize?->设计取舍，大部分时候没有那么多删除（乐）

slot不够->从page尾部向前增长

lec4​

cost model for ayalysis

B, D, R

• the number of data blocks
• the number of records per clock
• avg time to r/w disk block
• opt: index

indexes:

大幅度降低range操作耗时

An index is data structure that enables fast lookup and modification of data entries by search key

区间查找 & 子集搜索, 可以复合, 不需要唯一

2-d box 2-d circle n-d indexes都有

kd树啊R树啊

postgres 的 GiST index

left key opt: 最小的key是不需要的,直接拿-inf当下界就行

处理相等:>= 向右走就行

B+树

• 叶子不一定是连续的-动态分配,指针连接以支持range scan

• 阶数d, fan-out 2d+1 典型的fan-out 为2144()

• 删除, 理论上来说, 可能涉及到重新平衡等操作 但实际的操作之中, 只需要删除即可, 原因是平衡太慢了,并且删了也能再插

叶子放什么?

1. 数据

pros:

• 快

cons:

• 想要在另一列构建索引只能重新复制文件(文件只能按照一种方式实际排序存储)
• 即使真复制了,同步问题也很寄

2. 指向数据的指针 (key, page id+list of record id)

在b+树里面有重复项

3. 指向同一个键的所有records (key, list of (page id + list of record id))

减少冗余,增加复杂性

clustered: index指向的数据块在磁盘上是按照这个index排序或者近似排序的

非常大影响性能 顺序比随机快100倍

对于一个有变化的数据,例如插入或者删除,需要一些成本进行磁盘数据的重新排序来维持clustered

B+树的平衡性:

使用字节数半满(占页面容量)就行, 甚至实际上更低, 按照实际性能来决定,不严格

变长key: 前缀压缩 trie

性能的常数:

由于顺序读写比随机读写快100倍

B+树比全表扫描差不多也是涉及到1%以下的表才有显著优势

所以例如对一个非聚簇索引进行一个跨越半个表的range的扫描, 那还不如直接把全表取出来

优化

由于B+树效率真的很低,所以有很多优化策略

• bulk loading 批量装载

1. Sort the data by a key.
2. Fill leaf pages up to size f (the fill factor).
3. If the leaf page overflows, then use the insertion split algorithm from a normal B+ tree.
4. Adjust pointers to reflect new nodes if needed.

lec14 操作系统上的进程​

cpu有初始pc地址->放置固件上的初始程序(固件状态机)->启动OS(os状态机)->load init程序(程序状态机), 之后OS完全把行为转交给init(进程树的root)

llm 知道存在与知道的界限正在模糊: 知道存在且合理 逐渐趋同于 能做

例如 qemu 相关的一些东西

问llm发散出的概念->知识体系的快速建立

fork? 以状态机的视角理解

经典的for fork + printf

写了个示例

#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <stdio.h>
#include <unistd.h>
#include <vector>
#include <mutex>
#include <sys/wait.h>
#include <map>
#include <string>
using namespace std;
const size_t buf_size = 1024;
const std::map<int, std::string> mode_map = {
    {_IONBF, "no buffer"},
    {_IOLBF, "line buffer"},
    {_IOFBF, "full buffer"},
};
void test(int __modes) {
    printf("test in mode %s\n", mode_map.at(__modes).c_str());
    fflush(stdout);
    vector<int> childs;
    std::mutex mtx;
    setvbuf(stdout, nullptr, __modes, 0);
    for (int i = 0; i < 2; ++i) {
        int pid = fork();
        printf("hello from pid %d\n", pid);
        if (pid > 0) {
            std::lock_guard<mutex> lock(mtx);
            childs.push_back(pid);
        }
    }
}

int main() {
    // _IOLBF, _IOFBF, _IONBF
    test(_IOFBF);
    printf("\n");
    fflush(stdout);
    return 0;
}

在_IOLBF和_IONBF的情况下会出来6个hello

每次printf都直接刷新/检测到换行符刷新缓冲, fork的时候没有IO状态 而_IOFBF会有8个hello, 在fork第二次的时候会带着缓冲区(就是一段内存空间)进行fork,所以最后的4个进程每个都带着2个hello

系统里面没有魔法

fork: 把所有的知道的不知道的都复制了

“是不是这样?” -> 不知道的底层状态被复制了

execve: 重置状态机 argc, argv, envp -> main()

execve是唯一一个可以新建一个状态机的系统调用

exit?

• main return
• exit libc提供的
• _exit 系统调用退出（== asm volatile("mov ..., %rax; syscall")）
• 直接SYSCALL

前两个在c语言的空间, 是“normal exit”

后两个不是normal的, _exit exit_group , __exit exit self

行为区别? strace

lec15 进程的地址空间​

pmap

/proc/[pid]/maps

vvar(r), vdso(rx), vsyscall

os内只读的syscall -> 可以以内存的形式共享

其实只需要进程能和OS交互一些数据就行 —— why not进程写page, OS轮询?

• 在极端的时候能提高一些高优先级的进程的性能, 某篇OSDI

地址空间应该是在运行时可变的

所以我们需要一个不存在于c世界的操作(syscall)去操作地址空间 -> mmap, munmap

入侵进程的地址空间: gdb, perf

Game Genie 物理入侵地址空间

• 外接电路: 当cpu读地址a的时候读到x, 则替换为y

jyy现场演示mini CE(雾)

gdb attach到虚拟机,查找满足某个模式的内存值, 修改之

/proc/[pid]/mem 修改器 = 调试器

xdotool: cmd X11 automation tool

ydotool: better xdotool -> 按键精灵

evdev 按键显示脚本

xdotool测试vsc插件, crazy

或许不需要那么多的“魔法工具”

OS: 解放编程能力, 什么事情在OS上可以做

变速齿轮: syscall是感知时间的唯一方法

gdb 脚本之中, 在gettimeofday打断点, 然后修改寄存器, amazing!!!

hook

patching: 整活, kpatch, 不停机更新(软件动态链接)

old func, rx -> 修改为rwx -> 修改old func为, jmp到new func

在chcore里面看看? 或许有必要研究一下gdb(attach with qemu)

lec16 syscall & unix shell​

everything is a file

thing: 操作系统里面的对象

gpt时代的“编程”——自然语言?

//OS: API:
//	get_object_by_name(
//		"the address space file of pid=1234"
//	)

文件描述符: 指向OS对象的“指针”

windows: handle(句柄)

IPC endpoints: 例子, 管道

管道是同步的

fork + pipe? 本质是"指针"的拷贝

现在两个进程都有读口和写口啦

shell, kernel 的外壳

cli: 高效简洁的编程语言

算力的提升: cli -> gui -> 自然语言

shell as pl: 基于文本替换的快速工作流搭建

job control: 类比窗口管理器的"x", 最小化

或许不需要tmux, shell就是最简单的tmux

手册: complete ref

AI是“被动的”, 读一读shell manual

复刻unix shell

“抛开系统库”

-ffreestanding -nostdlib -static

gdb init已经很常见了, 但gdb init到python再在python里面转回/proc/[pid]/fd打印, 最后结合gdb的内置hook,在stop时候打印, fancy!

这打印的不是我们go的channel语法吗, 更有趣了

sh manual

lec 17 syscall的封装: libc​

pipe write如果小于PIPE_BUF, 是原子的

pipe 7

读者关闭: Broken pipe

libc 标准化, 稳定可靠, 移植性极好

C runtime library: -Wl, --verbose看到链接列表

调试glibc? 历史包袱重, 大量内联汇编, musl

只要实现了C ABI指定的堆栈排布的系统调用, 就可以轻松移植musl等到自己的OS上, 底层的计算由硬件指令集给出

System V ABI

脱开workload 做优化就是耍流氓

• 在开始考虑性能之前, 理解需要考虑什么样的性能

workload哪里找? 当然是paper了(顺便白得方案)

• 看wkld调性能

mm alloctor: 根基

• 大对象应该有长生存期, 否则是performance bug
• 越小的对象创建/分配越频繁
• 小对象, 中对象, 大对象

瓶颈几乎是小对象

链表/区间树不是一个好想法: 上锁, 不能很好的并行化

设置两套系统：

• Fast path 性能极好，并行度极高，覆盖大部分情况
• Slow path 不在乎速度，但把困难的事情做好
• 例如cache

init ram fs

ISA -> OS 对象/syscall -> libc -> 系统工具 coreutils, busybox -> 应用程序

initramfs

• 加载剩余必要的驱动程序, 例如磁盘/网卡

• 挂载必要的fs

• 将根文件系统和控制权移交给另一个程序, 例如systemd

initramfs作为一个非常小的启动fs, 再把磁盘这个OS Object mount进来, 最后switch root把控制权给到磁盘的的根系统

启动的第二级阶段 /sbin/init

疯狂的事情不断有人在做, 但疯狂的事情的起点其实经常很小

lec 19 可执行文件​

elf不是一个人类友好的“状态机数据结构描述”

为了性能, 彻底违背了可读(“信息局部性”)原则

可执行文件=OS的数据结构(core.dump), 描述了程序应该的初始状态

支持的特性越多, 人类越不能理解

人类友好: 平坦的

回归连接和加载的核心概念: 代码、符号、重定位

my_execve

elf file -> parse as struct

-> 将各个section load到指定的地址(mmap)->asm volatile布置好ABI调用栈(根据手册)->jmp!

如何释放旧进程的内存资源？proc里面需要有记录

lec 21 syscall & ctx switch​

dynamic linker

se给的os基础还是很扎实的 很难想象ics2里面讲了GOT和PLT

SEE ALSO是一个宝藏 man ld.so

hacking: LD_PRELOAD不需要修改libc, 动态加载的全局符号, 先到先得

劫持大法！

kernel memory mapping

低配版Linux 1.X 分段, 内核在低位, 只是分个段

低配版Linux 2.X 内核还是在物理低位, 但程序看到虚拟地址已经是高位了

today: complete memory map

qemu is a state machine simulator: 调试syscall(gdb并不能si从用户态进kernel)

另一种理解中断的方式："被"插入一条syscall

中断, 把状态机的整个寄存器状态存到内存里面

在汇编之中小心排布内存和搬运寄存器, 返回到c之中就是结构体的context

schedule的核心: 调用一个“不会返回的函数”

这个(汇编)函数以context为参数, 并且根据context, 返回到另一处控制流...

-> coroutine 也是如此! OS作为一个“状态机管理器”就在做一个"coroutine event handler"的作用

lec 22 process​

进程: “戴上VR”的thread

有自己的地址转换, 对一切的load/store会应用一个f，作用在addr上

硬件提供了“戴上VR”的指令

这个f从ds的视角来说就是int->int的映射

查页表(int->int的映射)这件事, 如何加速? --自然想到radix tree

普通实现是radix tree(x86, riscv, ...收敛到的最终方案)

每一次访存都要查这么几次的话不可接受

因此有了TLB, 但立刻带来的一个设计问题是, 谁来管TLB(以及对应的miss处理？)

x86选择放到硬件, 但丧失灵活性的后果是即使有些进程只想要f(x)=x, 也必须要老实查表, TLB在和cpu cache抢带宽

MIPS选择放到软件, miss了直接丢出来异常, 让软件来决定怎么处理TLB

疯狂的想法: inverted page table

把key从VPN换成 (VPN, pid), 然后从一一映射改成hashtable, 支持每个进程有自己的页表

缺点在例如hashtable带来的冲突时(TLB miss, etc)时间不可控(O(1) ~ O(n))

每个进程都有自己的“VR眼镜”这件事情还带来了更多的优化空间, 例如多个进程, 不同的虚拟地址块映射到同一个物理地址, 以及cow

KSM(kernel samepage merging/mermory deduplication), demand paging

fork: 进程快照, redis

cow fork的缺点: 让系统实现变复杂

改革: 砍掉所有的内核部分, 剩下的全部交给xv6

lec 23 处理器调度​

trampoline code

跳板代码, 例子

• call printf -> call *GOT(printf)
• JIT编译器
• 软件热更新(patch 函数头)

资源调度(分配)是一个非常复杂的问题

建模, 预测, 决策 -> 调度策略的设计空间

调度策略

再加一层机制 "niceness", 管理员控制nice, 越nice越能得到cpu

10 nice ~ 10倍性能差异

taskset 绑定一个process到一个cpu上

round-robin时代: MLFQ, 动态优先级

• 让出CPU(I/O) -> “好”

• 用完时间片 -> “坏”!

1960s: breakthrough!

2020s: 对很多负载都欠考虑

今天的调度: CFS(complete fair scheduling)

但有vruntime, "好人"的钟快一些

真实的处理器调度: 不要高兴得太早...

• 低优先级的在持有mutex的时候被中间优先级的赶下处理器, 可以导致高优先级的任务等待mutex退化到低优先级 -> 火星车

Linux: 没法解决, CFS凑合用

实时系统: 火星车在CPU Reset, 不能摆烂

• 优先级继承, 条件变量唤醒?

• lockdep预警

• ...

然而不止有锁, 还有多处理器...

今天的计算机系统: SMP

多处理器的矛盾困境

• 绑定一个线程:"一核有难, 八方围观"
• 谁空丢给谁: cache, TLB白干

更多的实际情况: NUMA, 异构, 多用户

• numa: 远近cpu性能差达到数倍

• 多用户的cpu共享? namespaces, cgroups, 例如一个程序开并行, 另一个程序是串行的, 是否需要给串行的保留一个核, 而不是开得越多抢得越多

• 异构, 大小核超小核, GPUNPU, 每个核的独有缓存和共享缓存...

• 更少的处理器可能更快...(反直觉, 同步cacheline带来的开销)

复杂的系统无人掌控

ghOSt: Fast & Flexible User-Space Delegation of Linux

开始下放给应用程序做调度

Others​

早期优雅的设计可能会成为后续发展的包袱: fork+exec带来的膨胀, 所有涉及到OS内部状态的api都需要考虑fork行为, 例如文件偏移量...

总线, 中断控制器, DMA

总线: 提供设备的“虚拟化”, 注册和转发, 把收到的地址(总线地址)和数据转发到对应的设备上

这样cpu只需要直连一根总线就行了!

PCI总线

• 总线可以桥接其他总线, 例如pci -> usb

lspci -tv可视化

"即插即用"的实现——非常复杂!

cpu: 只有一根中断线

启动多个cpu: cpu给其他cpu发中断!

中断仲裁: 收集各个设备中断, 选一个发给cpu

APIC(Advanced PIC):

• local APIC: 中断向量表, IPI, 时钟, ...
• IO APIC: IO设备

DMA: 很早期就有了, 解放cpu, 设计专用的电路只做memcpy

今天: PCI总线直接支持

文件 = 实现了文件操作的“Anything”

设备驱动程序: 一个 struct file_operations的实现, 就是一段普通的内核, “翻译”read/write等系统调用

/dev/null的驱动: read永远什么都不做返回0, write永远什么都不做返回count

一种"duck type"

设备不仅仅是数据, 还有配置

配置设备:

• 控制作为数据流的一部分(自定义一套write的指令编码)
• 提供一个新的接口

ioctl: 非数据的设备功能几乎完全依赖ioctl, 完全由驱动决定

数量最庞大,质量最低的shit

unix的负担: 复杂的hidden spec

/dev/kvm 硬件虚拟化, 支撑了几乎所有的云产商虚拟化方案

unix的设计: 目录树的拼接

将一棵目录树拼到另一棵上

回想最小linux系统, 只有/dev/console和几个文件

/proc, /sys, /tmp都是mount系统调用创建的

"看到的fs!=磁盘的fs", is just a view

像是procfs这种并非实际的fs更是, 可以挂载到任意的地方, 以任意的数量(因为他只是fake了read/write的“file Object”)

根本设计哲学: 灵活

灵活性带来的

• /, /home, /var都可以是独立的设备, 把有些快的放在一个目录存可执行文件, 另一些存数据...

mount一个文件? loopback device

设备驱动把设备的read/write翻译成文件的rw

FHS: Filesystem Hierarchy Standard

ln -s 图结构 as 状态机

fs: 一个”数据结构题“, 但读写的单元是一个block

FAT: 集中保存所有"next"指针, 可靠性? 存n份!

fat manual

fat 小文件ok, 大文件不行

前言​

这件事情的起因是这样的, 在开卷上机考想要部署一个本机大模型参考一下, 同时有同学和我讲qwen2.5-coder-7B非常的nice, 于是就有了下面这篇文章, 用ollama + docker部署的local LLM...

本地环境: Ubuntu24.04

以下是步骤

下载nvidia docker runtime​

参考 https://docs.nvidia.com/datacenter/cloud-native/container-toolkit/latest/install-guide.html#installing-with-apt

apt

curl -fsSL https://nvidia.github.io/libnvidia-container/gpgkey | sudo gpg --dearmor -o /usr/share/keyrings/nvidia-container-toolkit-keyring.gpg \
  && curl -s -L https://nvidia.github.io/libnvidia-container/stable/deb/nvidia-container-toolkit.list | \
    sed 's#deb https://#deb [signed-by=/usr/share/keyrings/nvidia-container-toolkit-keyring.gpg] https://#g' | \
    sudo tee /etc/apt/sources.list.d/nvidia-container-toolkit.list

sudo apt-get update
sudo apt-get install -y nvidia-container-toolkit

设置 /etc/docker/daemon.json

{
    "default-runtime": "nvidia",
    "registry-mirrors": [
        "https://1nj0zren.mirror.aliyuncs.com",
        "https://docker.mirrors.ustc.edu.cn",
        "http://f1361db2.m.daocloud.io",
        "https://registry.docker-cn.com"
    ],
    "runtimes": {
        "nvidia": {
            "args": [],
            "path": "nvidia-container-runtime"
        }
    },
}

如果你需要代理, 参考配置加上

   "proxies": {
    "http-proxy": "http://127.0.0.1:7890",
    "https-proxy": "http://127.0.0.1:7890",
    "no-proxy": ""
  }

然后重启docker服务

sudo systemctl daemon-reload    
sudo systemctl restart docker

出现找不到"nvidia" runtime错误的, 检查有没有下载过docker desktop

下载过docker desktop的:

docker context ls
docker context use default

切换回default, 然后重启docker服务

下载ollama镜像​

mkdir -p /data/containers/ollama/data
vi /data/containers/ollama/docker-compose.yml

docker-compose.yml

name: 'ollama'
services:
  ollama:
    restart: always
    image: ollama/ollama
    container_name: ollama
    runtime: nvidia
    environment:
      - TZ=Asia/Shanghai
      - NVIDIA_VISIBLE_DEVICES=all
    networks:
      - ai-tier
    ports:
      - "11434:11434"
    volumes:
      - ./data:/root/.ollama
networks:
  ai-tier:
    name: ai-tier
    driver: bridge
    ipam:
      config:
        - subnet: 172.22.1.0/24

启动

cd /data/containers/ollama
docker compose up -d

之后会拉ollama (2G)

验证成功

docker compose ps
# 得到结果应该如下
NAME      IMAGE           COMMAND               SERVICE   CREATED              STATUS              PORTS
ollama    ollama/ollama   "/bin/ollama serve"   ollama    About a minute ago   Up About a minute   0.0.0.0:11434->11434/tcp, :::11434->11434/tcp

下载模型​

qwen2.5:7b建议换成其他的代码专用模型, 根据自己的电脑显卡配置决定参数量

空间占用 7b:5G, 3b: 2G, 1B:1G

docker exec -it ollama ollama pull qwen2.5:7b

成功结果这样

pulling manifest
pulling 00e1317cbf74... 100% ▕████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████  4.7 GB
pulling 4fa551d4f938... 100% ▕████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████   12 KB
pulling 8ab4849b038c... 100% ▕████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████   254 B
pulling 577073ffcc6c... 100% ▕████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████   110 B
pulling ad1518640c43... 100% ▕████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████   483 B 
verifying sha256 digest
writing manifest
removing any unused layers
success

验证

❯ docker exec -it ollama ollama list
NAME          ID              SIZE      MODIFIED    
qwen2.5:7b    845dbda0ea48    4.7 GB    2 hours ago    

What's next:
    Try Docker Debug for seamless, persistent debugging tools in any container or image → docker debug ollama
    Learn more at https://docs.docker.com/go/debug-cli/

开始服务​

docker compose up -d

会在localhost:11434起一个服务, 浏览器输入后正常会有Ollama is running

前端套壳​

ChatBox​

直接去官网下载

https://chatboxai.app/zh/install

设置里面指定一下模型

aider版本​

参考https://aider.chat/docs/config/dotenv.html设置一下OLLAMA_BASE_API的环境变量

之后aider --model ollama/qwen2.5:7b 即可

下载自己看官网(pip install aider-chat)

ok, 大功告成！

[可选] IDE插件​

一个例子是Continue插件https://www.continue.dev/

参考官网, 据说vsc支持还行, jet bug不少