首页 文章 精选 留言 我的

精选列表

搜索[分布式检索]，共10005篇文章
优秀的个人博客,低调大师

论文赏析：基于NVM的高性能向量检索方案HM-ANN

HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogenous Memory 是一篇被2020年 Conference on Neural Information Processing Systems (NeurIPS 2020). 本文提出了一种基于图的相似性搜索的新型算法，称为 HM-ANN。该算法在现代硬件设置中同时考虑了内存异质性和数据异质性。HM-ANN 可以在单台机器上实现十亿级的相似性搜索，同时没有采用任何数据压缩技术。异质存储器（HM）代表了快速但小的 DRAM 和缓慢但大的 PMem 的组合。HM-ANN 实现了低搜索延迟和高搜索精度，特别是在数据集无法装入单机有限 DRAM 的情况下。与最先进的近似近邻（ANN）搜索方案相比，该算法具有明显的优势。 动机 由于 DRAM 容量有限，ANN 搜索算法在查询精度和查询延迟之间进行了基本的权衡。为了在 DRAM 中存储索引以实现快速查询，有必要限制数据点的数量或存储压缩的向量，这两者都会损害搜索的准确性。基于图形的索引（如 HNSW）具有优越的查询运行时间性能和查询精度。然而，当在十亿规模的数据集上操作时，这些索引也会消耗 TiB 等级的 DRAM。 还有其他的变通方法来避免让 DRAM 以原始格式存储十亿规模的数据集。当一个数据集太大，无法装入单台机器的 DRAM 时，就会使用数据压缩的方法，如对数据集的点进行乘积量化。但是，由于量化过程中精度的损失，这些索引在压缩数据集上的召回率通常很低。Subramanya 等人[1]探索了利用固态硬盘 SSD 实现十亿级 ANN 搜索的方法，该方法称为 Disk-ANN ，其中原始数据集存储在 SSD 上，压缩后的表示方法存储在 DRAM 上。 Heterogeneous Memory的介绍 内存/存储的层次结构与HM 图片来源: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf Heterogeneous memory (HM) 代表了快速但小的 DRAM 和慢速但大的 PMem 的组合。DRAM 是每个现代服务器中都能找到的硬件，其访问速度相对较快。新的 PMem 技术，如英特尔® Optane™DC Persistent Memory Modules，弥补了基于 NAND-based flash（SSD）和 DRAM 之间的差距，消除了 I/O 瓶颈。PMem 像 SSD 一样可以在断电情况下持久化数据，又像 DRAM 一样可由 CPU 直接对每一个 Byte 寻址。Renen 等人 [2] 发现，在配置的实验环境中，PMem 的读取带宽比 DRAM 低 2.6 倍，而写入带宽低 7.5 倍。 HM-ANN 的设计 HM-ANN 是一种准确而快速的十亿级 ANN 搜索算法，在单机上运行时无需压缩。HM-ANN 的设计概括了 HNSW 的思想，其分层结构自然适合 HM。HNSW 由多层组成: 只有第 0 层包含整个数据集，其余每一层都包含其正下方那一层的一个子集。 一个 3 层 HNSW 的例子 图片来源: https://arxiv.org/pdf/1603.09320.pdf 上层的元素，只包括数据集的子集，消耗了整个存储消耗的一小部分。这一现象使它们非常合适去被放置在 DRAM 中。这样一来，HM-ANN 上的大部分搜索都会发生在上层，这就最大限度地利用了 DRAM 的快速访问特性。然而，在 HNSW 中大多数搜索发生在底层。 最底层承载着整个数据集，这使得它适合被放在 PMem 中。 由于访问第 0 层的速度较慢，最好是每个查询只访问一小部分，并降低访问频率。 图构建算法 HM-ANN的索引构造例子 图片来源: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf HM-ANN 构造的关键思想是构建高质量的上层，以便为第 0 层的搜索提供更好的导航指导能力。因此，大多数内存访问发生在 DRAM 中，所以 PMem 中的访问则被减少。为了实现这一点，HM-ANN 的构建算法有一个自上而下的 selection 阶段和一个自下而上的 promotion 阶段。 自上而下的插入阶段建立了一个 navigable small-world graph，因为最底层是放在 PMem 上的。 自下而上的促进阶段从底层 promote pivot 点，以形成放置在 DRAM 上的上层，而不会失去很多准确性。如果在第 1 层创建了第 0 层元素的高质量投影，那么第 0 层的搜索只需几跳就能找到查询的准确近邻。 HM-ANN 没有使用 HNSW 的 random selection for promotion，而是使用高度推广策略high-degree promotion strategy，将第 0 层中度数最高的元素推广到第1层。对于更高的层，HM-ANN 根据 promotion rate 将高度数节点推广到上层。 HM-ANN 将更多的节点从第 0 层 promote 到第 1 层，并为第 1 层的每个元素设置更大的最大邻居数。上层节点的数量是由可用的 DRAM 空间决定的。由于第 0 层不存储在 DRAM 中，因此使存储在 DRAM 中的每一层更密集，可以提高搜索质量。 图搜索算法 HM-ANN的索引搜索例子 图片来源: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf 该搜索算法由两个阶段组成: fast memory search 与 parallel layer-0 search with prefetching. Fast memory search 与 HNSW 相同，DRAM 中的搜索从最顶层的入口点开始，然后从顶层到第 2 层执行 1-greedy search。为了缩小第 0 层的搜索空间，HM-ANN 在第 1 层进行搜索，搜索预算为 efSearchL1，这限制了第 1 层的 candidate list 的大小。HNSW 只使用一个 entry point ，但在 HM-ANN 中，第 0 层和第 1 层之间的关系比任何其他两层之间处理得更加特别。 Parallel layer-0 search with prefetching 在底层，HM-ANN 将上述来自搜索第 1 层的 candidates 均匀分开，并将其视为 entry points，以执行parallel multi-start 1-greedy search with threads。每次搜索出来的 top candidates 被收集起来，以找到 best candidates。众所周知，从第 1 层下到第 0 层正好是进入 PMem。 并行搜索隐藏了 PMem 的延迟，并充分利用内存带宽，在不增加搜索时间的情况下提高搜索质量。 HM-ANN 在 DRAM 中实现了一个 software-managed buffer，在 DRAM 访问发生之前从 PMem 中 prefetch 数据。当搜索第 1 层时，HM-ANN 异步地将 efSearchL1中的那些 candidates 的邻居元素及其在第 1 层的连接从 PMem 复制到 buffer。当第 0 层的搜索发生时，一部分数据已经在 DRAM 中被 prefetched 了，这就隐藏了访问 PMem 的延迟，导致了更短的查询时间。这与 HM-ANN 的设计目标相吻合，即大部分内存访问发生在 DRAM 中，而 PMem 中的内存访问被减少。 性能测试 在 HM-ANN 这个论文中，对这个新索引算法进行了广泛的评估。所有的实验都是在一台装有 Intel Xeon Gold 6252 CPU@2.3GHz 的机器上进行的。它使用DDR4（96GB）作为快速内存，Optane DC PMM（1.5TB）作为慢速内存。对五个数据集进行了评估。BIGANN、DEEP1B、SIFT1M、DEEP1M 和 GIST1M。对于十亿规模的测试，包括以下方案：基于十亿规模量化的方法（IMI+OPQ 和 L&C），以及非压缩的方法（HNSW 和 NSG）。 十亿规模的算法比较 在 Table 1 中，比较了不同的基于图的索引的索引时间和内存消耗。HNSW 在建立索引时速度最快，HM-ANN 比 HNSW 多需要 8% 的时间。在总体存储使用方面，HM-ANN 索引比 HSNW 大 5-13%，因为它将更多的节点从第 0 层推广到第 1 层。 在 Figure 1 中，对不同索引的查询性能进行了分析。图1（a）和（b）显示，HM-ANN 在 1 毫秒内取得了 >95% 的 top-1 召回率。图1（c）和（d）显示， HM-ANN 在 4 毫秒内获得了 >90% 的 top-100 召回率。与其他所有方法相比，HM-ANN 提供了更好的 latency-recall 性能。 百万规模的算法比较 在 Figure 2 中，不同索引的查询性能在纯 DRAM 环境下进行了分析。HNSW、NSG 和 HM-ANN 是用一个适合 DRAM 容量的 300 万规模的数据集进行评估的。HM-ANN 仍然取得了比 HNSW 更好的查询性能。原因是，当它们都旨在实现 99% 的召回率目标时，HM-ANN 的距离计算总数（平均 850 次/查询）要少于 HNSW（平均 900 次/查询）。 High-degree promotion的效果 在 Figure 3 中，random promotion 和 high-degree promotion strategies 在同一配置下进行了比较。high-degree promotion strategies 的效果优于 baseline。在达到 95%、99% 和 99.5%的召回率目标时，high-degree promotion strategies 的表现比 random promotion 快 1.8 倍、4.3 倍和 3.9 倍。 内存管理技术的性能 Figure 5 包含了 HNSW 和 HM-ANN 之间的一系列步骤，以显示 HM-ANN 的每项优化对其改进的贡献。BP 代表索引构建中自下而上的 promotion，PL0 代表 Parallel layer-0 search，DP 代表从 PMem 到 DRAM 的数据 prefetching。每走一步，HM-ANN 的搜索性能都会被进一步推高。 结论 一种新的基于图的索引和搜索算法，称为 HM-ANN，将基于图的 ANN 搜索算法的分层设计与 HM 中的快慢内存异质性进行了映射。评估表明，HM-ANN 是一种新的最先进的适用于十亿数据集的索引。 在学术界和工业界中，在 PMem 上建立索引正变得越来越流行。为了减轻 DRAM 的压力，Disk-ANN [1] 是一个建立在 SSD 上的索引，但是 SSD 吞吐量明显低于 PMem。 然而，建立 HM-ANN 仍然需要几天时间，这与 Disk-ANN 的构建时间没有数量级的区别。我们相信，通过更仔细地利用 PMem 的特性（例如，意识到 PMem 的粒度为 256字节），以及使用指令 bypass cache lines，是可以优化 HM-ANN 的索引时间。我们还预计，将来会提出更多的持久存储设备的方法。 Reference [1]: Suhas Jayaram Subramanya and Devvrit and Rohan Kadekodi and Ravishankar Krishaswamy and Ravishankar Krishaswamy: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, NIPS, 2019 DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node - Microsoft Research DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node [2]: Alexander van Renen and Lukas Vogel and Viktor Leis and Thomas Neumann and Alfons Kemper: Persistent Memory I/O Primitives, CoRR & DaMoN, 2019 https://dl.acm.org/doi/abs/10.1145/3329785.3329930 Persistent Memory I/O Primitives 本篇博文作者： 罗济高，Zilliz 实习研究员，本科毕业于慕尼黑工业大学，目前是该校数据工程与分析专业研究生在读。兴趣领域包含关系数据库与性能分析，喜欢研究关系数据库內核，对数据库各个子领域的进展拥有高度好奇心。他的 Github 账号是 https://github.com/cakebytheoceanLuo，博客地址是https://cakebytheoceanluo.github.io/
2021-08-04
优秀的个人博客,低调大师

分布式演化

应用发展历程： 1、第一版应用 图1-1 第二版 单机负载越来越高，数据库服务器和应用服务器分离 图1-2 第三版应用服务器做集群 图1-3 当做到这个部分的时候，就会出现一个问题，应用服务器集群的session共享问题 解决session跨域共享问题： 1、session sticky 2、session replication 3、session集中存储 存储在DB、存储在缓存服务器中（redis） 4、cookie（主流） access_token(userid/token/timestamp) soa架构和微服务架构 如何做请求转发 第四版 数据库的高性能操作 图1-4 1、数据库读写分离怎么操作 2、数据库的数据同步 3、数据库路由mycat 电商平台最多的操作： 搜索商品 图1-5 问题： 1、搜索引擎的索引数据怎么去做同步，实时增量同步？ 还是定时全量同步？ 第六版 解决访问量持续增高，引入缓存机制 用户量是没有上限的 缓存、 限流、 降级 图1-6 第8️版本数据库的水平/垂直拆分 图1-7 第9版本
2018-08-06

资源下载

更多资源
腾讯云软件源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

时间: 2026-08-21 大小: 1MB 下载: 10次
Nacos

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

时间: 2026-09-24 大小: 189MB 下载: 9次
Rocky Linux

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

时间: 2026-08-21 大小: 1.42GB 下载: 6次
WebStorm

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。

时间: 2025-12-13 大小: 249.54MB 下载: 22次
热门标签
DeepSeek Jdk25 OpenAi HarmonyOS6 Nacos3 SpringBoot4 SpringCloud Docker Kubernetes Service Mesh Redis Gemini3 Rocky

欢迎您来访！

登录后，您将获得更多功能！
热门文章
联系我们

有任何问题或合作意向欢迎联系我们

Email: 99873273@qq.com

QQ: 99873273

用户登录
用户注册