Implement links compression by xzfc · Pull Request #5492 · qdrant/qdrant

xzfc · 2024-11-20T10:59:59Z

This PR add HNSW graph links compression implementation, both for reading and writing.

The integration is added in #5489: it's disabled by default unless __QDRANT_COMPRESSED_LINKS is set.

~~Depends on #5486, #5487, #5489, #5490, #5491. Ignore all but the last commit during the review.~~

timvisee

Looks good!

I'm not 100% confident I covered all the nitty gritty details in this PR as it's quite difficult to see everything. I did go over the PR twice though, and no real questions or remarks come to mind.

Your extensive testing and unit tests do add trust. Thanks for implementing them!

timvisee · 2024-12-10T10:26:33Z

lib/segment/src/index/hnsw_index/graph_links.rs

+    bits_per_unsorted: u8,
 }

 #[derive(AsBytes, FromBytes, FromZeroes)]


Can we just extend the header type (and size) here without problems?

Yes, we can. We have HEADER_SIZE constant which is larger that actual size of this structure. It allows us to extend this struct. Only one thing to check. New fields will be zeroes in old files

IvanPleshkov · 2024-12-10T10:48:10Z

lib/segment/src/index/hnsw_index/graph_links.rs

    total_offsets_len: u64,
-    offsets_padding: u64, // 0 or 4
+    offsets_padding: u64,
+    m: u16,


Do we need to store m and m0 here? Can we provide it from the graph where these values are already known? My concern is if links are uncompressed, m and m0 are zeroes. Right now it's clear why, but this behavior may spend long hours of debugging in the future, I find it untrivial behavior

As an alternative, if you wish to store m and m0 anyway, you may create an additional structure with compression option. In this way you explicitly mark m and m0 fields as compression options and say that in non-compression case developer cannot rely on m/m0 fields

IvanPleshkov · 2024-12-10T10:52:57Z

lib/segment/src/index/hnsw_index/graph_links.rs

+            } else {
+                self.offsets_padding as u64
+            },
+            m: if self.compressed { self.m as u16 } else { 0 },


I mentioned in another thread that this behaviour is very untrivial and in the future develops may struggle of the situation where m and m0 are zeroes. I proposed a couple of solutions

Updated: these values are present in HeaderCompressed but not in HeaderPlain.

IvanPleshkov · 2024-12-10T10:59:06Z

lib/segment/src/index/hnsw_index/graph_links.rs

+    converter.save_as(path)?;
+    let new_size = path.metadata()?.len();
+
+    log::info!(


I propose to change log level to debug because HNSW graph logs have debug severity

IvanPleshkov · 2024-12-10T17:26:14Z

lib/segment/src/index/hnsw_index/graph_layers_builder.rs

            let links_builder = graph_layers_builder.links_layers[idx][0].read();
            let link_container_from_builder = links_builder.iter().copied().collect::<Vec<_>>();
-            assert_eq!(links_orig, &link_container_from_builder);
+            let m = if compressed { M * 2 } else { 0 };


As mentioned in another PR, logic max_m = m * 2 should have one source of true. In means moving in a separate function

IvanPleshkov

need resolution about m and m0 which are 0 in non-compressed links

lib/common/common/src/bitpacking_links.rs

IvanPleshkov · 2024-12-12T12:36:25Z

lib/segment/src/index/hnsw_index/graph_links.rs

+    /// Deliberately placed at the same offset as [`HeaderV0::levels_count`] and
+    /// set to an impossibly large number to make old Qdrant versions fail fast
+    /// when trying to read the new format.
+    version: U64,


If you place version at the end, you might compare with 0 instead of magic 0xFFFF_FFFF_FFFF_FF01, because old version header are guaranteed to be zeroed after it's end

Moreover, you may read version this way version directly and avoid the complicated levels_count_or_version variable while loading. Do you have any concerns about this approach?

I want an old Qdrant (≤1.12) to explicitly crash if it try to read a compressed file. If we place a new field to the end, it would just ignore it as it doesn't know about it.

While links compression is a hidden experimental feature that is not enabled by default, we won't bump the segment version soon.

As we discussed separately, old qdrant versions will throw the error in this approach. But the error will be segfault, it does not say that user tries to open new links with older qdrant. I don't remember why we cannot increase the segment version in this case, can you remind please complains about the segment version update?

IvanPleshkov · 2024-12-12T12:38:03Z

lib/segment/src/index/hnsw_index/graph_links.rs

+    zero_padding: [u8; 8],
+}
+
+const HEADER_VERSION_1: u64 = 0xFFFF_FFFF_FFFF_FF01;


Maybe these constants are more clear, WDYT

const CURRENT_HEADER_VERSION: u64 = 1; const HEADER_VERSION_FILE_CONTENT: u64 = u64::MAX - CURRENT_HEADER_VERSION;

I prefer to have 0xFFFF_FFFF_FFFF_FF01 explicitly written in the code since it's the value that is visible in hexdump graph.links | head -1. More convenient for debugging/troubleshooting.

IvanPleshkov · 2024-12-12T12:41:28Z

lib/segment/src/index/hnsw_index/graph_links.rs

+            .get();
+
+        match levels_count_or_version {
+            _ if u64::from_le(levels_count_or_version) <= 1 << 32 => {


Compare version with 1 << 32 is untrivial. I propose to move it as a separate line of code with additional comment

lib/segment/src/index/hnsw_index/graph_links.rs

IvanPleshkov · 2024-12-12T12:49:15Z

lib/segment/src/index/hnsw_index/graph_links.rs

-
-        // 2. header padding
-        writer.write_zeros(HEADER_SIZE - size_of::<GraphLinksFileHeader>())?;
+        if self.compressed {


I disagree with this approach. If we update the header version, we may save only in the new format and drop old version in the future. Currently, HeaderV1 is not a new version of the header — it's, in fact, a header for compressed links only.

IvanPleshkov · 2024-12-12T12:52:18Z

lib/segment/src/index/hnsw_index/graph_links.rs

+        let links_range = (offset0 as usize)..(offset1 as usize);
+
+        if let Some(compression) = &self.info.compression {
+            for_each_packed_link(


If unpacking costs something, we may think in the future about partial links decompression, we need only first links that pass filtering. It's not a proposal for this PR but we may improve the speed if additional checks costs less that unpacking

IvanPleshkov · 2024-12-12T12:57:07Z

lib/common/common/benches/bitpacking.rs

    });
 }

+pub fn bench_bitpacking_links(c: &mut Criterion) {


Thanks for benchmarking! =)

* common::bitpacking::packed_bits * BitWriter::new(): append, don't clear the buffer * common::bitpacking_links * Implement links compression * Update

xzfc requested review from IvanPleshkov, generall and timvisee November 20, 2024 10:59

xzfc force-pushed the links-comp-impl branch from ad0012f to bd3c06e Compare November 26, 2024 21:50

github-actions bot mentioned this pull request Nov 26, 2024

Flaky test byte_storage_quantization_test::test_byte_storage_binary_quantization_hnsw::case_09_nearest_scalar_dot #4348

Closed

xzfc force-pushed the links-comp-impl branch from bd3c06e to 1882785 Compare December 3, 2024 15:50

github-actions bot mentioned this pull request Dec 3, 2024

Flaky test payload_index_test::test_keyword_facet #5059

Closed

xzfc force-pushed the links-comp-impl branch 3 times, most recently from af21899 to 8c99ec6 Compare December 9, 2024 17:32

timvisee approved these changes Dec 10, 2024

View reviewed changes

IvanPleshkov reviewed Dec 10, 2024

View reviewed changes

IvanPleshkov requested changes Dec 10, 2024

View reviewed changes

xzfc force-pushed the links-comp-impl branch from ad9795b to b51b78f Compare December 12, 2024 09:31

IvanPleshkov reviewed Dec 12, 2024

View reviewed changes

xzfc added 5 commits December 16, 2024 21:39

common::bitpacking::packed_bits

8c06497

BitWriter::new(): append, don't clear the buffer

a33123a

common::bitpacking_links

c2b60fa

Implement links compression

372f03a

Update

24857cc

xzfc force-pushed the links-comp-impl branch from b51b78f to 24857cc Compare December 17, 2024 01:34

xzfc mentioned this pull request Dec 17, 2024

Update hnsw_search_graph benchmark #5666

Merged

xzfc requested a review from IvanPleshkov December 17, 2024 02:20

xzfc added this to the hnsw-links-compression milestone Dec 17, 2024

xzfc mentioned this pull request Dec 17, 2024

GraphLinks: replace trait with enum #5651

Merged

IvanPleshkov approved these changes Dec 18, 2024

View reviewed changes

xzfc merged commit 372a421 into dev Dec 18, 2024

xzfc deleted the links-comp-impl branch December 18, 2024 11:29

timvisee pushed a commit that referenced this pull request Jan 8, 2025

Implement links compression (#5492)

5c072a2

* common::bitpacking::packed_bits * BitWriter::new(): append, don't clear the buffer * common::bitpacking_links * Implement links compression * Update

Conversation

xzfc commented Nov 20, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

timvisee left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

IvanPleshkov Dec 10, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

IvanPleshkov left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

IvanPleshkov Dec 12, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

xzfc commented Nov 20, 2024 •

edited

Loading

IvanPleshkov Dec 10, 2024 •

edited

Loading

IvanPleshkov Dec 12, 2024 •

edited

Loading