Question: Hash table sizing strategy for large (compressed) filesystems to avoid costly rebuilds

[Ice-pumpkin]

I've read through quite some issues:

From https://zygo.github.io/bees/config.html we have the

unique data size |  hash table size |average dedupe extent size
    1TB          |      4GB         |        4K
    1TB          |      1GB         |       16K
    1TB          |    256MB         |       64K
    1TB          |    128MB         |      128K <- recommended
    1TB          |     16MB         |     1024K
   64TB          |      1GB         |     1024K

From #192 you say
data-to-hash ratio falls between 1000:1 and 10000:1
and from #222 you say
A filesystem with 400 GB of data (uncompressed size) should have at hash table sized between 40MB and 400MB

which I assume means unique data size : hash table size should fall between 1000:1 to 10000:1
as in the table above, 1TB : 1GB = 1024:1, and 1TB : 128MB = 8192 : 1

Then we can have

hash_entries = hash table size / average dedupe extent size
hash_bytes   = hash_entries * 16
hash_aligned = max(128 KiB, ceil(hash_bytes / 128 KiB) * 128 KiB)

Since the formular is linear, given any two of the three values unique data size hash table size average dedupe extent size, can calculate the other one.
And if the average dedupe extent size is determined, we have unique data size : hash table size determined.
Like 16K for 1TB : 1GB = 1024:1 or 100TiB : 100GiB, 128K for 1TB : 128MB = 8192 : 1.

And here's my question:

I know, that if the hash table size were to change, it's recommended to have the old .beeshome/beeshash.dat deleted and created through scan, all over (the tool to somehow make full reuse of old table doesn't exist yet), which could take tons of time with large unique data size.

If I were to have a file system with tozens of TiB, I think it would be not ideal to restart bees with a new hash table size (dynamically, every once in a while) and spend all those time to rebuild it. (I'm not really sure how fast is it... 50GiB for a night?)

So I want to use file system size as approximation of unique data size (the largest possible value), and use user's assumption of average file size as average dedupe extent size (approximate average extent size with dirty background bytes >= 128 MiB and no oflag=sync/oflag=dsync, then approximate average dedupe extent size).

Since in my understanding, a too large hash table mostly just waste RAM/storage space, but a too small hash table may severely influence deduplication efficiency. So for the reduplication efficiency's sake, it's more safe to assumingly set hash table larger, and it's fine to use file system size as approximation of unique data size.

I also think this can slightly make up for the inaccuracy from using (user's assumption of) average file size as average dedupe extent size, for that average file size will probably be larger than the average extent size, thus larger than average dedupe extent size. Since larger extent size means smaller hash table size, the optimized hash table size calculated out of the value, will be slightly smaller than it should be.

Anyway, then we have:

hash_entries = filesystem_size / avg_file_size
hash_bytes   = hash_entries * 16
hash_aligned = max(128 KiB, ceil(hash_bytes / 128 KiB) * 128 KiB)

(filesystem_size ≈ unique data size
avg_file_size ≈ average dedupe extent size)

Do you have any suggestion to my approach?
Thank you for all those explains from the other issues.

---

And some less important rambles:

I'm also not really sure how compression affect the optimized hash table size. I know you suggest 2-4x larger. But if the average file size ≈ average extent size is already 128KiB, same as the largest value of compressed extent size, will it still need to be 2-4x larger? Maybe, to calculate the opimized hash table size, it'll still comes down to average dedupe extent size, just for the value to be influenced with the max size being 1024x smaller (from 128MiB to 128K).

Is it ideal to guess compression rate beforehand (Like "I'll start using normal zstd compress when my 50% storage is used") and set the value? If no compression is 1x, full compression is 2-4x larger, is there a (maybe linear) relationship for a file system with 50% compression rate ( one that started compression with that mount command half way), like the optimized hash table size is 0.5 * 2-4x?
Though this doesn't matter if I just determine the hash table size upon file system creation / first time bees starts and never change it no matter how I expand the system or start/close compression. I don't even know how to get current average extent size conveniently as of yet.

I also also kind of wonder if it's possible to calculate optimized hash table size, every once in a while, through compression rate and file system size (every time system expansion happens), so if new optimized hash table size is significantly different (like xxx% larger than current hash table size?) or that if current one got out of the range 1000:1-10000:1, I get a warning, and automatically calculate the expected time to scan all over(no idea as of yet as well), then find a time the system is free, and run a script to reboot bees with the new hash table size...

[kakra]

And, if no compression is 1x, compression is 2-4x larger, is there a (maybe linear) relationship for 50% compressed file system (like to be 50% * 2-4x)?

bees doesn't depend on compression or extent size. What it does is identify common 4k blocks (which go into the hash table, hash calculated from the uncompressed block), and then search forward and backward from there to identify running blocks of duplicates, eventually breaking extents into new continuous extents of 4k blocks matching exactly the longest duplicate chain. So it doesn't even need to store all 4k duplicate candidates to find chains of duplicate blocks.

bees will temporarily require more storage to do this, until it cleaned up all references to the extents it broke and replaced.

When rewriting blocks, bees tries to enable compression on those extent, possibly compressing parts of your file system which previously haven't been compressed (best-effort compression heuristics built into btrfs).

It is recommended to not force-compress your whole file system, as this will explode the amount of meta data and slow down bees considerably. Compressed extents are limited to a maximum size of 128k. Forcing compression will totally destroy your avg extent size, resulting in vastly higher meta data usage, which probably hasn't been the intention of compression in the first place.

It is possible to exactly double or have the size of the hash table (while bees is not running) using truncate. This is not optimal, but as far as I know, bees will be able to still use parts of the hash table, temporarily with a vastly reduced hit rate. It's better to start over, it is quite fast processing and detecting all the dedups it has done previously, unless you're using a lot of snapshots.

So, I think, yes, the hash table size aligns with the unique data size, as you already assumed.

[Ice-pumpkin]

It is quite fast processing and detecting all the dedups it has done previously,
That's.. new, I thought it would take forever (weeks or even months if the system is often busy) if the unique data size is large enough, like for 100 TiB or larger.

unless you're using a lot of snapshots.
Oh...guess I should try investigate how many snapshot is 'a lot of'.

So, I think, yes, the hash table size aligns with the unique data size, as you already assumed.
The approach I wanted to use, is to first determine average dedupe extent size by guessing average file size (like from 4Kib to 128MiB), then cap it into 16KiB to 128KiB (as it determines the recommended range, 1000:1 to 10000:1, 16K is for 1TB : 1GB = 1024:1, and 128K is for 1TB : 128MB = 8192 : 1)
Then determine the file system size as approximation of unique data size, and calculate the 'optimized' hash table size.

Apologies if I explained it in a mess, and thank you for explaining the deeper working mechanics of bees.

[kakra]

It is quite fast processing and detecting all the dedups it has done previously,

That's.. new, I thought it would take forever (weeks or even months if the system is often busy) if the unique data size is large enough, like for 100 TiB or larger.

It's still not exactly a fast process but with the new extent based scanner, it has vastly improved (v0.11+).

unless you're using a lot of snapshots.

Oh...guess I should try investigate how many snapshot is 'a lot of'.

I have around 60-70 snapshots (hourly with age-based thining), and it looks like bees tends ti do work over and over again when fresh. But I don't think this is because this is "a lot" but because my snapshot are automated with snapper, and it's a pretty fast moving target, forcing bees to rediscover the same extents over and over again it broke up earlier. I was able to break that cycle by deduping the most expensive directory trees with duperemove first.

So, I think, yes, the hash table size aligns with the unique data size, as you already assumed.

The approach I wanted to use, is to first determine average dedupe extent size by guessing average file size (like from 4Kib to 128MiB), then cap it into 16KiB to 128KiB (as it determines the recommended range, 1000:1 to 10000:1, 16K is for 1TB : 1GB = 1024:1, and 128K is for 1TB : 128MB = 8192 : 1) Then determine the file system size as approximation of unique data size, and calculate the 'optimized' hash table size.

Bees may help your here... Start it and wait until it discovered all extents. It will probably already do work, you could start with a small hash table. Look at the stats file, do your calculations, then start with a fresh bees state.

Here are stats from my desktop system:

PROGRESS:
extsz   datasz  point gen_min gen_max this cycle start tm_left   next cycle ETA
----- -------- ------ ------- ------- ---------------- ------- ----------------
  max   3.436T 060448 5771065 5771066 2026-07-08 16:09       -             idle
  32M 683.144G 060448 5771065 5771066 2026-07-08 16:09       -             idle
   8M 425.203G 000000 5771065 5771066 2026-07-08 16:09       -             idle
   2M 252.335G 000000 5771065 5771066 2026-07-08 16:09       -             idle
 512K 225.528G 000000 5771065 5771066 2026-07-08 16:09       -             idle
 128K 365.209G 000000 5771065 5771066 2026-07-08 16:09       -             idle
total   5.342T        gen_now 5771066                  updated 2026-07-08 16:09

And these are from a server system:

PROGRESS:
extsz   datasz  point gen_min gen_max this cycle start tm_left   next cycle ETA
----- -------- ------ ------- ------- ---------------- ------- ----------------
  max   1.326T 998567 2063313 2063314 2026-07-08 16:09         2026-07-08 16:10
  32M 133.586G 998567 2063313 2063314 2026-07-08 16:09         2026-07-08 16:10
   8M 167.429G 998567 2063313 2063314 2026-07-08 16:09         2026-07-08 16:10
   2M  49.764G 998567 2063313 2063314 2026-07-08 16:09         2026-07-08 16:10
 512K  48.198G 998567 2063313 2063314 2026-07-08 16:09         2026-07-08 16:10
 128K 428.915G 615417 2033706 2059169 2026-07-07 03:05 23h 10m 2026-07-09 15:20
total   2.135T        gen_now 2063315                  updated 2026-07-08 16:10

You can probably also use compsize to calculate the avg size, it should be more straight forward because you won't have to derive extent sizes from the stats summary. However, my stats may help you evaluate how bees may end up with a different average after splitting and recombining extents. For stat blocks are running bees instances which did a lot of cycles over months or years.

Apologies if I explained it in a mess, and thank you for explaining the deeper working mechanics of bees.

No worries, I'm sometimes messy, too. ;-)

[Zygo]

The hash table size influences how many blocks there can be between two duplicate block reads before detection fails. It's effectively a giant LRU cache fed by random sampling of the input data.

It's not a true random sample, because matching blocks are retained while non-matching blocks are evicted by new data. If you're writing the same data over and over, those blocks will be kept in the hash table, regardless of its size. If you have short bursts of duplicate data with large amounts of unique data written between them, the hash table will have to be large enough to hold the duplicate data long enough for the duplicates to be found and moved to the front of LRU queues before the unique data pushes them out.

The longest distance between duplicate blocks is the true lower bound for the hash table size. It's notoriously difficult to estimate without running a full-filesystem dedupe to completion. "Distance" is measured at the point where bees reads data blocks from disk, in whatever order the scanning rules and btrfs data allocation history laid the data out. Certainly, if the hash table is large enough to hold the entire filesystem, then it is guaranteed to hold any order of block reads within the filesystem--but it will be larger than needed in most cases.

The distance is also nonlinear, because you only need to match one block between two extents to dedupe both extents in their entirety. A 128K compressed extent must keep 3% of its blocks (1 in 32). A 128M extent must keep only 0.003% of its blocks (1 in 32768). All the other blocks are inactive and eventually get evicted. This puts probability curves into the calculations. A typical user desktop has a mix of sizes, so the ideal hash size is somewhere between those extremes. The geometric mean of those ratios is 1024:1, and that's a good pessimistic assumption given no other information about the filesystem--but if you do have that information, you can estimate the adjustment factor based on use case.

Live data sets tend to work well with the LRU. If you are doing git checkouts all day long, new files will tend to be similar to other new files checked out around the same time, and less similar to older files from older versions. This often makes resizing the hash table unnecessary as the data grows, since the LRU window required is much smaller for live data than for the initial scan, meaning the current and future live data fits in the much larger space that was used for the initial scan.

You could build a test filesystem, then try various hash table sizes on a few hundred GiB of sample data, and find the hash table size where dedupe hit rate starts to fall. You can scale that hash table size up to the full size of your data set to get a minimum viable table size (the point on the dedupe-saving/table-size curve where there are no significant gains from larger tables), then multiply by 2 or 4 to get an optimal table size that can accommodate a few surprises.

Hash table resize will be a v0.12 feature, as well as changes to avoid flooding the hash table with data from large extents. Resize requires reading the existing hash table 256 times, moving the last element of the LRU bucket from the old table into the new table on each pass to preserve the LRU ordering and place entries in their new bucket locations.

[Ice-pumpkin]

Hash table resize will be a v0.12 feature
woahhhhh, the ever much anticipated feature, finally! Looking forward to it.
(#70
There's a long-standing feature request to have bees properly support resizing the hash table, or a tool that can read a hash table and write a new table with a different size.
#288
It's possible to build a tool which reads one hash table and inserts the hashes into a new table at the right positions, but it hasn't been done yet.
#322
Resizable hash tables are possible without losing all the state, but the old table entries have to be inserted into the new table in the right order--it's not as simple as truncating the hash table file to a larger size. It's becoming the most frequently requested feature.

---

in my understanding, a too large hash table mostly just waste RAM/storage space, but a too small hash table may severely influence deduplication efficiency.
May I ask if this is correct?
Because from #70, If the hash table is too large, performance decreases because bees will have stale data in the hash table that takes extra time to read and invalidate, seems like a too large hash table may also decrease efficiency.
I still think it's more safe to assumingly set hash table larger, if performance doesn't decrease too much as when the hash table is too small, dedupe ratio decreases because bees can't match extents that are far apart in space or time though.

[Zygo]

in my understanding, a too large hash table mostly just waste RAM/storage space, but a too small hash table may severely influence deduplication efficiency.

I wouldn't say "severe"--it has to be orders of magnitude too small to have a 20% drop in dedupe efficiency. Even a 1:1000000 ratio (128k hash table vs 128G data, definitely "too small") can still dedupe at around 25% efficiency in practice.

You can always make the hash table bigger than you need if you know the data will grow into it.

[Ice-pumpkin]

in my understanding, a too large hash table mostly just waste RAM/storage space, but a too small hash table may severely influence deduplication efficiency.

I wouldn't say "severe"-- it has to be orders of magnitude too small to have a 20% drop in dedupe efficiency. Even a 1:1000000 ratio (128k hash table vs 128G data, definitely "too small") can still dedupe at around 25% efficiency in practice.

I probably get that "severe" through "falls rapidly" from the config page:

Dedupe efficiency falls rapidly with hash tables smaller than 128MB/TB as the average dedupe extent size is larger than the largest possible compressed extent size (128KB).

Or maybe I used the word 'deduplication efficiency' as a very vague concept, just like 'performance' and got it wrong, as now I see it can be devided into:

• removed duplicate data / whole duplicate data, in one scan round (I think the time for each scan round won't differ much, thus 99.5%-100% deduplicated in one round would be the best performance)
• removed duplicate data / whole duplicate data, when full deduplication process finish.
• the total time spent to finish deduplication.

(currently I guess 'dedupe efficiency' means 'the ratio of duplicate data actually removed, after the full deduplication process, to the total amount of duplicate data that could potentially be removed'

though I think this already solves most my current confusion:

You can always make the hash table bigger than you need if you know the data will grow into it.

You could build a test filesystem, then try various hash table sizes on a few hundred GiB of sample data, and find the hash table size where dedupe hit rate starts to fall. You can scale that hash table size up to the full size of your data set to get a minimum viable table size (the point on the dedupe-saving/table-size curve where there are no significant gains from larger tables), then multiply by 2 or 4 to get an optimal table size that can accommodate a few surprises.

It's notoriously difficult to estimate without running a full-filesystem dedupe to completion.

There's no magic formula that works for all real-world complexities, optimal hash table size must come from practice.

thank you. ;)

and... opps, seems like I've been using code blocks for reference.