deepseek-ai/3FS

Fork 0

mirror of https://github.com/deepseek-ai/3FS.git synced 2026-11-05 00:47:47 +00:00

[GH-ISSUE #368] Non-deterministic chain shuffling across different libstdc++ versions #223

New issue

Closed

opened 2026-10-26 09:47:22 +00:00 by bsakaguchi · 1 comment

bsakaguchi commented

2026-10-26 09:47:22 +00:00

Owner

Originally created by @yiyuanliu on GitHub (Dec 26, 2025).
Original GitHub issue: https://github.com/deepseek-ai/3FS/issues/368

When creating files, 3FS allocates chains for the file based on stripe size and stores data chunks on these chains. 3FS selects a contiguous range of chains from the chain table, then shuffles them for more even data distribution. File metadata stores the chain table id/version, the chain range for the file, and the random seed used for shuffling. Clients need to perform the shuffle themselves to obtain the final chain list.

Currently, 3FS directly uses std::shuffle, which depends on the specific implementation of the standard library (libstdc++). There were some changes in random number generation starting from g++11 link, so given the same random seed, g++10 and g++11 (or later versions) may produce different results.

Whether g++10 and g++11+ produce the same result for a given array length and shuffle seed is probabilistic, and the probability of difference increases with array length (stripe size):

stripe_size=50: almost always identical (tested 900 billion seeds, all results matched between g++10 and g++11)
stripe_size=100: 12 mismatches out of 900 billion seeds tested
stripe_size=200: approximately 1 in 2.8 billion chance of mismatch
stripe_size=20000: nearly every seed produces different results between g++10 and g++11+

Impact: If binaries compiled with different g++/libstdc++ versions are mixed in the same cluster, data corruption may occur. The probability of this issue increases with stripe size.

Required fixes:

Remove dependency on std::shuffle and implement a fixed shuffle algorithm that is not affected by g++ version
The new shuffle implementation needs to be consistent with either g++10 or g++11 selectable at compile time.
Meta should avoid generating random seeds that produce different results between g++10 and g++11
Provide a tool to detect which files may have shuffle seeds that produce different results between g++10 and g++11, for users who have unfortunately mixed g++10 and g++11+ binaries in their deployment

Originally created by @yiyuanliu on GitHub (Dec 26, 2025). Original GitHub issue: https://github.com/deepseek-ai/3FS/issues/368 When creating files, 3FS allocates chains for the file based on stripe size and stores data chunks on these chains. 3FS selects a contiguous range of chains from the chain table, then shuffles them for more even data distribution. File metadata stores the chain table id/version, the chain range for the file, and the random seed used for shuffling. Clients need to perform the shuffle themselves to obtain the final chain list. Currently, 3FS directly uses `std::shuffle`, which depends on the specific implementation of the standard library (`libstdc++`). There were some changes in random number generation starting from `g++11` [link](https://github.com/gcc-mirror/gcc/commit/98c37d3bacbb2f8bbbe56ed53a9547d3be01b66b), so given the same random seed, `g++10` and `g++11` (or later versions) may produce different results. Whether `g++10` and `g++11+` produce the same result for a given array length and shuffle seed is probabilistic, and the probability of difference increases with array length (stripe size): - `stripe_size=50`: almost always identical (tested 900 billion seeds, all results matched between `g++10` and `g++11`) - `stripe_size=100`: 12 mismatches out of 900 billion seeds tested - `stripe_size=200`: approximately 1 in 2.8 billion chance of mismatch - `stripe_size=20000`: nearly every seed produces different results between g++10 and g++11+ **Impact**: If binaries compiled with different `g++`/`libstdc++` versions are mixed in the same cluster, data corruption may occur. The probability of this issue increases with stripe size. **Required fixes**: 1. Remove dependency on `std::shuffle` and implement a fixed shuffle algorithm that is not affected by `g++` version 2. The new shuffle implementation needs to be consistent with either `g++10` or `g++11` selectable at compile time. 3. Meta should avoid generating random seeds that produce different results between `g++10` and `g++11` 4. Provide a tool to detect which files may have shuffle seeds that produce different results between `g++10` and `g++11`, for users who have unfortunately mixed `g++10` and `g++11+` binaries in their deployment

bsakaguchi closed this issue

2026-10-26 09:47:22 +00:00

bsakaguchi commented

2026-10-26 09:47:24 +00:00

Author

Owner

@yiyuanliu commented on GitHub (Dec 26, 2025):

Fixed in #369

Changes:

Added compile option SHUFFLE_METHOD with possible values: g++10, g++11, or stdshuffle (not recommended). The g++11 option is compatible with g++11 and later versions. You need to manually specify cmake -DSHUFFLE_METHOD='...' when compiling.

If you have already deployed a 3FS cluster, choose g++10 or g++11 based on the compiler version used when deploying that cluster.
If you are deploying a new 3FS cluster, you can choose either g++10 or g++11, but please note that you need to keep using the same configuration afterwards.

When creating files, 3FS meta now searches for a random seed that produces the same result on both g++10 and g++11. Since file stripe sizes are generally small, it is very easy to find a qualifying random seed.

Checking for affected files in mixed-version deployments:

If you have mixed g++10 and g++11 binaries in a cluster, you can check whether any files have shuffle seeds that produce different results under different compilers:

First use admin_cli to dump inode information:

dump-inodes --fdb-cluster-file /path/to/fdb.cluster --parquet-format

Use duckdb to extract file inode, shuffle seed and stripe size information:

create table t as (select inode_id, inode_typeFile_layout_chainsChainRange_seed, inode_typeFile_layout_stripeSize from '*.parquet' where inode_typeFile_layout_chainsChainRange_seed != 0);
copy (from t) to '~/dump-inodes.csv'

Use the tool to check the results

./tests/test_common --gtest_filter='TestShuffle.CheckDump' --test_dump_path bug.csv 2> mismatch.csv

@yiyuanliu commented on GitHub (Dec 26, 2025): Fixed in #369 **Changes**: Added compile option `SHUFFLE_METHOD` with possible values: `g++10`, `g++11`, or `stdshuffle` (not recommended). The `g++11` option is compatible with `g++11` and later versions. You need to manually specify `cmake -DSHUFFLE_METHOD='...'` when compiling. - If you have already deployed a 3FS cluster, choose `g++10` or `g++11` based on the compiler version used when deploying that cluster. - If you are deploying a new 3FS cluster, you can choose either `g++10` or `g++11`, but please note that you need to keep using the same configuration afterwards. When creating files, 3FS meta now searches for a random seed that produces the same result on both `g++10` and `g++11`. Since file stripe sizes are generally small, it is very easy to find a qualifying random seed. **Checking for affected files in mixed-version deployments**: If you have mixed `g++10` and `g++11` binaries in a cluster, you can check whether any files have shuffle seeds that produce different results under different compilers: 1. First use admin_cli to dump inode information: ``` dump-inodes --fdb-cluster-file /path/to/fdb.cluster --parquet-format ``` 2. Use duckdb to extract file inode, shuffle seed and stripe size information: ``` create table t as (select inode_id, inode_typeFile_layout_chainsChainRange_seed, inode_typeFile_layout_stripeSize from '*.parquet' where inode_typeFile_layout_chainsChainRange_seed != 0); copy (from t) to '~/dump-inodes.csv' ``` 3. Use the tool to check the results ``` ./tests/test_common --gtest_filter='TestShuffle.CheckDump' --test_dump_path bug.csv 2> mismatch.csv ```

No labels

pull-request

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

deepseek-ai/3FS#223

No description provided.

Rows
Columns