CoChat

P-HNSW: Crash-Consistent HNSW for Vector Databases on Persistent Memory

Open access
Lee, Haena, Park, Taeyoon, Na, Yedam, Kim, Wook-Hee · 2025 · Applied Sciences

The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.

Abstract

The rapid growth of Large Language Models (LLMs) has generated massive amounts of high-dimensional feature vectors extracted from diverse datasets. Efficient storage and retrieval of such data are critical for enabling accurate and fast query responses. Vector databases (Vector DBs) provide efficient storage and retrieval for high-dimensional vectors. These systems rely on Approximate Nearest Neighbor Search (ANNS) indexes, such as HNSW, to handle large-scale data efficiently. However, the original HNSW is implemented on DRAM, which is both costly and vulnerable to crashes. Therefore, we propose P-HNSW, a crash-consistent HNSW on persistent memory. To guarantee crash consistency, P-HNSW introduces two logs, NLog and NlistLog. We describe the logging process during the operation and the recovery process in the event of system crashes. Our experimental results demonstrate that the overhead of the proposed logging mechanism is negligible, while P-HNSW achieves superior performance compared with SSD-based recovery mechanisms.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.3390/app151910554

Cites

32 of 32 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Hierarchical Navigable Small World (HNSW) with a label-to-node mapping table. During the search process, HNSW first finds the nearest node to the query vector and iteratively traverses to the lower layers. Upon reaching layer 0, HNSW retrieves the topk nodes and returns the corresponding labels using the mapping table.
Figure 1 Hierarchical Navigable Small World (HNSW) with a label-to-node mapping table. During the search process, HNSW first finds the nearest node to the query vector and iteratively traverses to the lower layers. Upon reaching layer 0, HNSW retrieves the topk nodes and returns the corresponding labels using the mapping table.CC-BY · From the PDF
Figure 2 Node layouts in HNSW. #N indicates the number of neighbors (out-edges).
Figure 2 Node layouts in HNSW. #N indicates the number of neighbors (out-edges).CC-BY · From the PDF
Figure 3 Design overview of P-HNSW. The figure summarizes the limitations of DRAM-based HNSW, the contributions of P-HNSW, and the resulting effects of our techniques. NLOG is the Node Log, and NLISTLOG is the Neighbor List Log.
Figure 3 Design overview of P-HNSW. The figure summarizes the limitations of DRAM-based HNSW, the contributions of P-HNSW, and the resulting effects of our techniques. NLOG is the Node Log, and NLISTLOG is the Neighbor List Log.CC-BY · From the PDF
Image 4
CC-BY · From the PDF
Figure 5 State machine diagram of NLOG and NLISTLOG showing recovery invariants and flush points for each state transition. The log states ensure that incomplete operations are either safely ignored ( LOGGING ) or deterministically reconstructed ( LOGGED , N_COMPLETE ) during recovery.
Figure 5 State machine diagram of NLOG and NLISTLOG showing recovery invariants and flush points for each state transition. The log states ensure that incomplete operations are either safely ignored ( LOGGING ) or deterministically reconstructed ( LOGGED , N_COMPLETE ) during recovery.CC-BY · From the PDF
Figure 6 Recovery process with NLOG. In ( a ), the dashed arrows represent the information corrupted due to a system crash, while in ( b , c ), the red arrows indicate the information restored by the recovery algorithm. The graph in state ( a ) is recovered sequentially through ( b , c ).
Figure 6 Recovery process with NLOG. In ( a ), the dashed arrows represent the information corrupted due to a system crash, while in ( b , c ), the red arrows indicate the information restored by the recovery algorithm. The graph in state ( a ) is recovered sequentially through ( b , c ).CC-BY · From the PDF
Figure 7 Recovery process with NLISTLOG. ① Astructural inconsistency occurred after the neighbor count was updated, but the neighbor list was only partially persisted. The question mark indicates a partially written (crash-corrupted) value. ② The NLISTLOG restores the neighbor list to ensure consistency.
Figure 7 Recovery process with NLISTLOG. ① Astructural inconsistency occurred after the neighbor count was updated, but the neighbor list was only partially persisted. The question mark indicates a partially written (crash-corrupted) value. ② The NLISTLOG restores the neighbor list to ensure consistency.CC-BY · From the PDF
Figure 8 Single-thread insertion time of different index types evaluated on the ( a ) SIFT and ( b ) GIST datasets with varying data sizes. The results show that P-HNSW consistently achieves lower overhead than HNSWSNAP and HNSWWAL, with only a small gap compared with the original HNSW.
Figure 8 Single-thread insertion time of different index types evaluated on the ( a ) SIFT and ( b ) GIST datasets with varying data sizes. The results show that P-HNSW consistently achieves lower overhead than HNSWSNAP and HNSWWAL, with only a small gap compared with the original HNSW.CC-BY · From the PDF
Figure 9 Multi-thread insertion throughput across index types evaluated on the ( a ) SIFT and ( b ) GIST datasets. P-HNSW consistently scales well with increasing threads, achieving throughput comparable with or higher than that of HNSW, while HNSWSNAP suffers from scalability limitations. HNSWWAL also benefits from multi-threading, though its throughput remains lower than that of P-HNSW.
Figure 9 Multi-thread insertion throughput across index types evaluated on the ( a ) SIFT and ( b ) GIST datasets. P-HNSW consistently scales well with increasing threads, achieving throughput comparable with or higher than that of HNSW, while HNSWSNAP suffers from scalability limitations. HNSWWAL also benefits from multi-threading, though its throughput remains lower than that of P-HNSW.CC-BY · From the PDF
Figure 10 Breakdown of multi-thread insertion time on SIFT10M. While the original HNSW spends nearly all its time on search, P-HNSW adds only small overhead for updates and logging. HNSWSNAP is dominated by snapshot saving, which severely limits scalability, whereas HNSWWAL shows better scalability.
Figure 10 Breakdown of multi-thread insertion time on SIFT10M. While the original HNSW spends nearly all its time on search, P-HNSW adds only small overhead for updates and logging. HNSWSNAP is dominated by snapshot saving, which severely limits scalability, whereas HNSWWAL shows better scalability.CC-BY · From the PDF
Figure 11 Breakdown of multi-thread insertion time on GIST1M. Compared with SIFT, the search proportion is higher due to the 960-dimensional vectors. P-HNSW keeps logging the overhead as nearly constant even as the thread count increases, while HNSWSNAP is dominated by snapshot saving.
Figure 11 Breakdown of multi-thread insertion time on GIST1M. Compared with SIFT, the search proportion is higher due to the 960-dimensional vectors. P-HNSW keeps logging the overhead as nearly constant even as the thread count increases, while HNSWSNAP is dominated by snapshot saving.CC-BY · From the PDF
Figure 12 Recovery time for the indexes evaluated on the ( a ) SIFT and ( b ) GIST datasets. P-HNSW achieves consistently fast recovery by directly accessing data in persistent memory. In contrast, both HNSWSNAP and HNSWWAL show a recovery time that increases linearly with dataset size; HNSWSNAP suffers from full-index loading overhead, while HNSWWAL requires replaying each log entry to rebuild the graph.
Figure 12 Recovery time for the indexes evaluated on the ( a ) SIFT and ( b ) GIST datasets. P-HNSW achieves consistently fast recovery by directly accessing data in persistent memory. In contrast, both HNSWSNAP and HNSWWAL show a recovery time that increases linearly with dataset size; HNSWSNAP suffers from full-index loading overhead, while HNSWWAL requires replaying each log entry to rebuild the graph.CC-BY · From the PDF

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 5

  1. Subramanya, S.J., Kadekodi, R., Krishaswamy, R., and Simhadri, H.V. (2019, January 8–14). DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. Proceedings of the 33rd Conference and Workshop on Neural Information Processing Systems (NeurIPS), Vancouver, BC, Canada.
  2. Li, S., Zhou, Y.E., Ren, H., and Huang, J. (April, January 30). ByteFS: System Support for (CXL-based) Memory-Semantic Solid-State Drives. Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’25, Rotterdam, The Netherlands.
  3. Nam, M., Cha, H., Choi, Y.r., Noh, S.H., and Nam, B. (2019, January 25–28). Write-Optimized Dynamic Hashing for Persistent Memory. Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST), Boston, MA, USA.
  4. Ma, S., Chen, K., Chen, S., Liu, M., Zhu, J., Kang, H., and Wu, Y. (2021, January 23–25). ROART: Range-query optimized persistent ART. Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST 21), Virtual Event.
  5. Lu, B., Hao, X., Wang, T., and Lo, E. (September, January 31). Dash: Scalable Hashing on Persistent Memory. Proceedings of the 46th International Conference on Very Large Data Bases (VLDB), Tokyo, Japan.

Cited by

Metadata

Authors
Lee, H., Park, T., Na, Y., & Kim, W.-H.
Affiliations
Konkuk University (KR)
Corresponding author
Kim, Wook-Hee
Venue
Applied Sciences
Publisher
MDPI AG
Published
2025-09-29
Volume
15
Issue
19
Pages
10554
ISSN
2076-3417 (ISSN-L)
OpenAlex
W4414669346
Cited by
1
References
23
Citations by year
2026: 1
FWCI
0.42
Type
journal article
Language
en
Open access
Locations
  • Applied Sciences (publishedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
Funders
Institute of Information and Communications Technology Planning and Evaluation (IITP) under the Metaverse Support Program to Nurture the Best Talents (IITP-2025-RS-2023-00256615)
Topics
  • Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
  • Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Data Storage Technologies
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
Keywords
HNSW index, persistent memory, crash consistency, approximate nearest neighbor search, vector databases, crash recovery

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.