💻 computer science

Onyx: Cost-Efficient Disk-Oblivious ANN Search

Onyx 通过提出一种成本高效的磁盘不可知近似最近邻搜索方案，利用 Onyx-ANNS 的紧凑中间表示和 Onyx-ORAM 的局部感知浅层树设计，在可信执行环境中实现了带宽与访问次数的协同优化，从而显著降低了搜索成本与延迟。

原作者： Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa

发布于 2026-04-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一个名为 Onyx 的新系统，它的目标是让 AI 在查找相似信息（比如“给我找几首和这首歌很像的歌”）时，既能保护用户隐私，又能省钱、跑得快。

为了让你更容易理解，我们可以把整个过程想象成在一个巨大的、充满秘密的图书馆里找书。

1. 背景：为什么我们需要 Onyx？

想象一下，你有一个巨大的图书馆（AI 数据库），里面有几亿本书（数据）。你想找几本和你手里这本书最像的书（近似最近邻搜索，ANN）。

隐私问题：你不想让图书馆管理员（云服务商）知道你在找什么书，甚至不想让他知道你翻开了哪几页。
传统做法的困境：
- 加密：如果你只是把书加密了，管理员虽然看不懂内容，但他能看到你翻书的顺序。比如，你总是先翻第 10 页，再翻第 50 页。聪明的管理员可以通过这个“翻书顺序”猜出你在找什么，甚至猜出整本书的内容。
- 全内存方案（太贵）：为了彻底隐藏翻书顺序，以前的方法是把所有书都放在一个只有你能看到的“保险柜”（可信执行环境 TEE）里。但这就像把整个图书馆的几亿本书都搬进一个只有几平米的保险柜，租金贵得离谱，根本用不起。
- 硬盘方案（泄露隐私）：为了省钱，大家把书放在外面的普通仓库（硬盘 SSD）里，只把“目录”放在保险柜里。但这样，管理员就能看到你去仓库取书的路径，隐私又泄露了。
- 旧式“隐形衣”（ORAM）太慢：以前有一种“隐形衣”技术（ORAM），能让你去仓库取书时，假装去取很多本无关的书，以此掩盖真实目标。但这就像为了拿一本书，你要在仓库里假装乱跑几百圈，速度极慢，效率极低。

核心矛盾：以前的方案要么太贵（全内存），要么太慢（旧式隐形衣），要么不安全（直接读硬盘）。

2. Onyx 的绝招：反其道而行之

Onyx 团队发现，以前的设计思路是反的。他们做了一个大胆的决定：把“隐形衣”和“找书策略”互换一下角色。

以前的思路：让“找书的人”（ANN 算法）尽量少跑几趟（减少访问次数），让“隐形衣”（ORAM）尽量多带点东西（利用带宽）。
- 结果：找书的人为了少跑，每次都要搬一大箱书（浪费带宽）；隐形衣为了伪装，每次都要跑很多趟（浪费次数）。两边都浪费了。
Onyx 的思路：
- 让找书的人（ANN）变得极其精明：只拿最小的、最必要的东西，哪怕多跑几趟也没关系，因为每次拿的很少。
- 让隐形衣（ORAM）变得极其擅长伪装：既然找书的人每次只拿一点点，那隐形衣就专门优化这种“小包裹”的伪装，用更少的次数完成伪装。

3. Onyx 的两大核心发明

Onyx 由两个配合默契的组件组成，我们可以用**“寻宝游戏”**来比喻：

组件一：Onyx-ANNS（精明的寻宝向导）

传统做法：向导每到一个路口，都要把整本地图册（包含所有详细信息的大文件）从仓库搬出来看一遍，太慢了。
Onyx 的做法：向导发明了一种**“极简线索卡”**。
- 当向导走到一个路口时，他不再搬整本地图册，而是只搬一张小小的线索卡（只有几十字节）。
- 这张卡片上写着：“往左走，大概有 80% 的可能是你要找的宝藏”。
- 向导拿着这张小卡片，快速筛选掉 90% 的假路。
- 只有在确定了那 10% 最可能的路之后，他才去搬那本巨大的“真地图册”（完整数据）。
效果：虽然向导多跑了几趟去拿小卡片，但他搬运的总重量（带宽）减少了 5 倍！因为大部分时间他都在搬轻飘飘的卡片，而不是沉重的地图册。

组件二：Onyx-ORAM（伪装大师）

传统做法：以前的伪装大师（如 RingORAM）喜欢用“二叉树”结构，每次都要爬很多层楼梯，还要频繁地上下楼，效率不高。
Onyx 的做法：向导把伪装大师升级成了**“宽体电梯”**（多叉树，d-ary tree）。
- 以前是爬 10 层楼梯（二叉树），现在直接坐电梯，只爬 3 层（8 叉树）。
- 虽然电梯每层能装的人更多了，但因为向导每次只送“小包裹”（小数据块），电梯的伪装成本反而降低了。
- 它设计了一种**“本地化”**策略：在电梯里就把大部分伪装工作做好了，不需要每次都跑到大楼外面去。
效果：伪装大师的动作次数减少了 2 倍，而且因为配合了向导的小包裹策略，整体速度飞快。

4. 最终成果：既快又省

把这两个组件放在一起，Onyx 就像是一个既懂策略又懂伪装的超级特工：

速度：以前找书要 1 秒多，现在只要 12 毫秒（快了 10 倍以上）。
成本：以前为了跑得快，需要租 4 台服务器和 8 块硬盘；现在只需要 1 台服务器和 1 块硬盘，就能处理同样的任务。
性价比：每花 1 美元，以前只能查 100 次，现在能查 800 万次！

总结

Onyx 的核心思想就是：不要试图用笨办法去掩盖所有痕迹，而是通过优化“拿什么”和“怎么拿”，让伪装变得自然且高效。

它证明了，在保护隐私的同时，我们不需要牺牲速度或支付高昂的费用。就像那个聪明的寻宝向导，他不再盲目地搬运整座图书馆，而是只拿最关键的线索，配合一个高效的伪装系统，最终在几秒钟内就找到了宝藏，还让图书馆管理员完全猜不到他在找什么。

这对于我们未来的 AI 应用（比如私人聊天助手、医疗数据分析）非常重要，意味着我们可以放心地把敏感数据交给云端处理，而不用担心隐私泄露，同时还能享受快速、便宜的服务。

Onyx: 面向成本效益的磁盘无关（Disk-Oblivious）ANN 搜索技术总结

1. 研究背景与问题定义

背景：
近似最近邻（ANN）搜索是许多 AI 系统（如 RAG、推荐系统、搜索）的核心组件。随着这些系统越来越多地部署在第三方云基础设施上并处理敏感数据，隐私保护变得至关重要。虽然可信执行环境（TEE）可以保护内存中的数据，但为了成本效益，索引通常存储在 TEE 信任边界之外的外部 SSD 上。

核心问题：
当 ANN 搜索在 TEE 中运行但索引存储在外部 SSD 时，**磁盘访问模式（Disk Access Patterns）**会泄露用户查询信息。即使数据是加密的，攻击者（如云服务商）通过观察 I/O 序列，可以利用侧信道攻击（如泄漏滥用攻击）推断出查询内容甚至重建整个数据集。

现有方案的局限性：

纯加密方案（如 Compass）： 使用 Oblivious RAM (ORAM) 隐藏访问模式，但成本极高，延迟大（>1 秒），吞吐量低（~100 查询/美元），无法满足生产环境需求。
TEE + 现有 ORAM-ANN 组合： 将现有的 ORAM-ANN 设计（如 Compass）直接放入 TEE 运行，虽然解决了内存泄露，但未能针对磁盘 I/O 特性进行优化。现有的设计在“访问次数”和“带宽”之间存在错误的权衡：ANN 层为了减少访问次数而获取大块数据，浪费了带宽；ORAM 层为了减少带宽而进行细粒度访问，导致访问次数激增。这种双重低效导致需要大量的 CPU 和 SSD 资源，成本高昂且延迟高。

2. 方法论：Onyx 系统架构

Onyx 提出了一种根本性的重新设计，通过ANN 搜索与 ORAM 的协同设计（Co-design），在磁盘设置下平衡带宽和访问次数。其核心思想是**“反转”传统设计**：让 ANN 层专注于最小化带宽消耗，让 ORAM 层专注于最小化访问次数。

2.1 核心组件

Onyx 由两个协同设计的组件组成，均运行在 TEE 内部：

A. Onyx-ANNS（带宽高效的 ANN 搜索引擎）

目标： 最小化从 SSD 读取的数据量（带宽）。
创新点：
1. 解耦遍历与细化（Decoupling）： 传统磁盘 ANN（如 DiskANN）在遍历图时直接获取完整的浮点向量（Full-precision vectors）。Onyx 将遍历（Traversal）和细化（Refinement）解耦。
2. 紧凑的剪枝提示（Compact Pruning Hints）： 引入一种新的中间表示 $H_{prn}$ （紧凑剪枝提示）。在遍历阶段，系统只获取邻居列表 $N$ 和 $H_{prn}$ （大小仅为 256-512 字节），而不是完整的向量（3KB+）。
3. 三阶段细化策略：
  - 遍历： 使用内存中的粗略提示 $H_{trv}$ 和磁盘上的 $N \parallel H_{prn}$ 进行图遍历，仅获取小块数据。
  - 剪枝： 利用预取的 $H_{prn}$ 对候选列表进行重排序和剪枝，大幅减少后续需要获取完整向量的节点数量。
  - 细化： 仅对剪枝后剩余的少量候选节点获取完整的浮点向量 $F$ 进行精确距离计算。
效果： 在不增加内存占用的情况下，将带宽消耗降低了 2-5 倍，仅增加了 5-15% 的访问次数。

B. Onyx-ORAM（访问次数高效的 ORAM 客户端）

目标： 最小化 SSD 的 I/O 请求次数（Access Count），同时保持带宽效率。
创新点：
1. 本地化元数据（Local Bucket Metadata）： 将原本需要在每次访问时从磁盘读取的桶元数据存储在 TEE 内存中，消除了每层级的元数据读取开销。
2. 全桶读取（Full Bucket Reads）： 在驱逐（Eviction）阶段，一次性读取整个桶（包括填充的假数据块），将多次随机读取转化为一次顺序读取，大幅降低访问次数。
3. 感知局部性的浅层树（Locality-Aware Shallow Trees）： 将传统的二叉树 ORAM 改为 $d$ -ary 树（如 8 叉树）。
  - 这直接将树深度从 $\log_2 N$ 减少到 $\log_d N$ ，从而线性减少访问次数。
  - 虽然 $d$ -ary 树通常会导致更频繁的驱逐，但 Onyx 利用大桶（Large Buckets）和上述优化，使得驱逐带来的带宽增加被抵消，最终实现了访问次数减少 3 倍而带宽几乎不增加的效果。
效果： 相比现有方案，访问次数降低 2 倍，带宽降低 4.6 倍。

2.2 协同效应

Onyx-ANNS 产生的小数据块（256-512 字节）恰好是 Onyx-ORAM 性能最优的块大小范围。Onyx-ORAM 的浅层树设计极大地减少了访问这些小块所需的 I/O 次数。两者相互强化，实现了资源利用的最优化。

3. 关键贡献

设计范式的转变： 首次提出在磁盘 ORAM-ANN 系统中“反转”优化目标，即 ANN 层负责带宽优化，ORAM 层负责访问次数优化，解决了以往设计中资源双重浪费的问题。
Onyx-ANNS 算法： 提出了一种基于紧凑剪枝提示的三阶段搜索策略，在保持高召回率的同时，显著减少了带宽密集型的全精度向量读取。
Onyx-ORAM 协议： 设计了基于 $d$ -ary 树的浅层树结构，结合本地元数据和全桶读取技术，在保持大桶带宽效率的同时，显著降低了 I/O 访问次数。
系统实现与评估： 构建了完整的 Onyx 系统，并在多种数据集和硬件配置下进行了全面评估。

4. 实验结果

实验在 AMD SEV-SNP TEE 环境下进行，使用了 SIFT、MS-MARCO、WIKI、DEEP 等数据集，对比了 Compass-in-TEE、RingORAM+DiskANN、PathORAM+DiskANN 等基线。

成本效益（Cost-Efficiency）：
- 相比 Compass-in-TEE，Onyx 实现了 1.7–9.9 倍 的成本降低（Queries/$）。
- 在单 vCPU 和单 SSD 配置下，Onyx 可支持 64GB 索引，达到 70 QPS，延迟仅为 12ms，召回率 90%。
- 相比其他最佳基线组合，成本降低 2.6–4.2 倍。
延迟与吞吐量（Latency & Throughput）：
- 相比 Compass-in-TEE，延迟降低 2.3–12.3 倍，吞吐量提升 2.3–12.2 倍。
- 相比磁盘优化的基线（如 RingORAM+DiskANN），延迟降低 4.0–4.5 倍。
资源利用率：
- Onyx 仅需 1 个 SSD 单元 即可满足大多数基准测试需求，而 Compass-in-TEE 在大型数据集上需要 4-8 个 SSD 单元。
- 存储放大率（Storage Amplification）仅为 2.0–2.7 倍，显著优于 Compass（8-13 倍）。

5. 意义与影响

实用化隐私保护： Onyx 证明了在第三方云基础设施上，利用 TEE 和外部 SSD 进行低成本、低延迟的隐私保护 ANN 搜索是可行的。它填补了纯加密方案（太慢太贵）和纯明文方案（不安全）之间的空白。
推动 AI 应用落地： 对于 RAG、个性化 AI 代理等需要处理敏感用户数据（如聊天记录、浏览历史）的应用，Onyx 提供了一种可部署的解决方案，使得企业无需担心数据泄露即可利用云端的弹性扩展能力。
系统优化启示： 该工作展示了在安全系统设计中，打破传统组件（ANN 和 ORAM）的独立优化思维，进行跨层协同设计（Co-design），可以带来数量级的性能提升。

总结： Onyx 通过创新的协同设计，成功解决了 TEE 环境下磁盘 ANN 搜索的隐私与性能矛盾，将隐私保护搜索的成本和延迟降低了一个数量级，使其具备了大规模商业部署的潜力。