[GH-ISSUE #31] Potential orphaned loop issue in `RenameOp` operation

bsakaguchi commented

2026-10-26 09:43:34 +00:00

Owner

Originally created by @Clcanny on GitHub (Mar 1, 2025).
Original GitHub issue: https://github.com/deepseek-ai/3FS/issues/31

Originally assigned to: @yiyuanliu on GitHub.

Hi, thank you for your amazing work on this repository! I am currently exploring how 3FS handles distributed transactions on FoundationDB (potentially involving read and write sets across multiple partitions of FoundationDB) while maintaining excellent performance, as I am preparing to write a technical blog to introduce this topic. While reading through the code, I may have identified a potential issue related to the RenameOp operation, but I could be misunderstanding something. If that's the case, I sincerely apologize and would greatly appreciate any clarification.

In the current implementation of RenameOp, it appears that only the parent inodes and directory entries of the source and destination paths are added to the read conflict set. However, this approach might result in an orphaned loop problem, as described in Figure 8 of InfiniFS: An Efficient Metadata Service for Large-Scale Distributed Filesystems.

To illustrate, here is an example scenario:

Suppose we have two paths:
- /A/B/C, where the root inode ID is 0, and the inode IDs for A, B, and C are 1, 2, and 3, respectively.
- /D/E/F, where the inode IDs for D, E, and F are 4, 5, and 6.
Two clients attempt concurrent remame operations:
- Client 1 tries to rename /D to /A/B/C/D.
  - The read conflict sets for this operation are: 0 (inode for /), 0-D (directory entry for /D), 4 (inode for /D), 3 (inode for /A/B/C) and 3-D (directory entry for /A/B/C/D, initially not found).
  - It writes 3-D, and deletes: 0-D.
- Client 2 tries to rename /A to /D/E/F/A.
  - The read conflict sets for this operation are: 0 (inode for /), 0-A (directory entry for /A), 1 (inode for /A), 6 (inode for /D/E/F) and 6-A (directory entry for /D/E/F/A, initially not found).
  - It writes 6-A, and deletes 0-A.

From FoundationDB's perspective, it seems these two transactions would not conflict because their read and write sets do not intersect. If that is true (please correct me if I'm wrong), this could result in an orphaned loop problem, violating serializability.

More complex scenarios could also be constructed (e.g., paths with longer hierarchies or additional concurrent operations), further demonstrating potential orphaned loop issues.

I suspect this issue might occur because not all accessed items (e.g., inodes or directory entries) are added to the read conflict set. As a result, FoundationDB's conflict detection may fail to identify conflicts between such transactions, leading to non-serializable outcomes.

Originally created by @Clcanny on GitHub (Mar 1, 2025). Original GitHub issue: https://github.com/deepseek-ai/3FS/issues/31 Originally assigned to: @yiyuanliu on GitHub. Hi, thank you for your amazing work on this repository! I am currently exploring how 3FS handles distributed transactions on FoundationDB (potentially involving read and write sets across multiple partitions of FoundationDB) while maintaining excellent performance, as I am preparing to write a technical blog to introduce this topic. While reading through the code, I may have identified a potential issue related to the `RenameOp` operation, but I could be misunderstanding something. If that's the case, I sincerely apologize and would greatly appreciate any clarification. In the current implementation of [`RenameOp`](https://github.com/deepseek-ai/3FS/blob/28c3b8b4b00f791b80d3d63bcfa68ea9d08cb96d/src/meta/store/ops/Rename.cc#L301), it appears that only the parent inodes and directory entries of the source and destination paths are added to the read conflict set. However, this approach might result in an orphaned loop problem, as described in Figure 8 of [InfiniFS: An Efficient Metadata Service for Large-Scale Distributed Filesystems](https://www.usenix.org/system/files/fast22-lv.pdf). To illustrate, here is an example scenario: <img width="1101" alt="Image" src="https://github.com/user-attachments/assets/857d26b9-9f4c-48ef-b481-4f2993329323" /> - Suppose we have two paths: - /A/B/C, where the root inode ID is 0, and the inode IDs for A, B, and C are 1, 2, and 3, respectively. - /D/E/F, where the inode IDs for D, E, and F are 4, 5, and 6. - Two clients attempt concurrent remame operations: - Client 1 tries to rename /D to /A/B/C/D. - The read conflict sets for this operation are: 0 (inode for /), 0-D (directory entry for /D), 4 (inode for /D), 3 (inode for /A/B/C) and 3-D (directory entry for /A/B/C/D, initially not found). - It writes 3-D, and deletes: 0-D. - Client 2 tries to rename /A to /D/E/F/A. - The read conflict sets for this operation are: 0 (inode for /), 0-A (directory entry for /A), 1 (inode for /A), 6 (inode for /D/E/F) and 6-A (directory entry for /D/E/F/A, initially not found). - It writes 6-A, and deletes 0-A. From FoundationDB's perspective, it seems these two transactions would not conflict because their read and write sets do not intersect. If that is true (please correct me if I'm wrong), this could result in an orphaned loop problem, violating serializability. More complex scenarios could also be constructed (e.g., paths with longer hierarchies or additional concurrent operations), further demonstrating potential orphaned loop issues. I suspect this issue might occur because not all accessed items (e.g., inodes or directory entries) are added to the read conflict set. As a result, FoundationDB's conflict detection may fail to identify conflicts between such transactions, leading to non-serializable outcomes.

bsakaguchi closed this issue

2026-10-26 09:43:34 +00:00

bsakaguchi commented

2026-10-26 09:43:35 +00:00

Author

Owner

@yiyuanliu commented on GitHub (Mar 2, 2025):

Thank you for your question. We check whether the rename operation could potentially create a loop by checking the target directory's ancestors. We record the parent directory in the inode. When renaming directory, we check all ancestors of the target directory and add them to the read conflict set (see implementation here and here). If such concurrent rename exist, they should conflict.

@yiyuanliu commented on GitHub (Mar 2, 2025): Thank you for your question. We check whether the `rename` operation could potentially create a loop by checking the target directory's ancestors. We record the parent directory in the inode. When renaming directory, we check all ancestors of the target directory and add them to the read conflict set ([see implementation here](https://github.com/deepseek-ai/3FS/blob/28c3b8b4b00f791b80d3d63bcfa68ea9d08cb96d/src/meta/store/ops/Rename.cc#L76) and [here](https://github.com/deepseek-ai/3FS/blob/main/src/meta/store/Inode.cc#L207)). If such concurrent `rename` exist, they should conflict.

bsakaguchi commented

2026-10-26 09:43:35 +00:00

Author

Owner

@Clcanny commented on GitHub (Mar 2, 2025):

Thank you so much for your clarification! I really appreciate it. I still have one more question, if you don’t mind:

From the perspective of the 3FS design, is it necessary to avoid cross-partition transactions in FoundationDB to achieve better performance? For most operations (except for cases like rename and mkdirs with missing ancestors), it seems that transactions typically involve only the parent's inode and its directory entry. Does 3FS ensure that the parent's inode and its children’s directory entries are colocated within the same partition in FoundationDB to avoid cross-partition transactions and improve performance?

Thank you again for your time and for sharing your insights!

@Clcanny commented on GitHub (Mar 2, 2025): Thank you so much for your clarification! I really appreciate it. I still have one more question, if you don’t mind: From the perspective of the 3FS design, is it necessary to avoid cross-partition transactions in FoundationDB to achieve better performance? For most operations (except for cases like rename and mkdirs with missing ancestors), it seems that transactions typically involve only the parent's inode and its directory entry. Does 3FS ensure that the parent's inode and its children’s directory entries are colocated within the same partition in FoundationDB to avoid cross-partition transactions and improve performance? Thank you again for your time and for sharing your insights!

bsakaguchi commented

2026-10-26 09:43:35 +00:00

Author

Owner

@yiyuanliu commented on GitHub (Mar 2, 2025):

From the perspective of the 3FS design, is it necessary to avoid cross-partition transactions in FoundationDB to achieve better performance?

For FoundationDB, cross-partition transactions are handled the same way as single-partition transactions, and I don't think there would be significant performance differences between them. One of FoundationDB's cofounders mentioned in a related discussion:

FoundationDB delivers serializable isolation and external consistency for all transactions. There's nothing particularly special about transactions that are "cross-partition"; because of our approach to indexing and data model design generally we expect the vast majority of transactions to be in that category. So rather than make single-partition transactions fast and everything else very slow, we focused on making the general case as performant as possible.

Does 3FS ensure that the parent's inode and its children's directory entries are colocated within the same partition in FoundationDB to avoid cross-partition transactions and improve performance?

No. In 3FS, inodes and directory entries use different key prefixes (INOD and DENT respectively), so they typically won't be in the same partition. Simply collocating a parent directory's inode and directory entries wouldn't eliminate cross-partition transactions. For example, when creating a file, you need to create both the directory entry and the child file's inode. To avoid cross-partition transactions, you would need to find a way to collocate the file's inode with its parent directory as well.

@yiyuanliu commented on GitHub (Mar 2, 2025): > From the perspective of the 3FS design, is it necessary to avoid cross-partition transactions in FoundationDB to achieve better performance? For FoundationDB, cross-partition transactions are handled the same way as single-partition transactions, and I don't think there would be significant performance differences between them. One of FoundationDB's cofounders mentioned in a [related discussion](https://news.ycombinator.com/item?id=16877395#16878786): > FoundationDB delivers serializable isolation and external consistency for all transactions. There's nothing particularly special about transactions that are "cross-partition"; because of our approach to indexing and data model design generally we expect the vast majority of transactions to be in that category. So rather than make single-partition transactions fast and everything else very slow, we focused on making the general case as performant as possible. > Does 3FS ensure that the parent's inode and its children's directory entries are colocated within the same partition in FoundationDB to avoid cross-partition transactions and improve performance? No. In 3FS, inodes and directory entries use different key prefixes (INOD and DENT respectively), so they typically won't be in the same partition. Simply collocating a parent directory's inode and directory entries wouldn't eliminate cross-partition transactions. For example, when creating a file, you need to create both the directory entry and the child file's inode. To avoid cross-partition transactions, you would need to find a way to collocate the file's inode with its parent directory as well.

bsakaguchi commented

2026-10-26 09:43:35 +00:00

Author

Owner

@Clcanny commented on GitHub (Mar 2, 2025):

Got it! Thank you so much!

@Clcanny commented on GitHub (Mar 2, 2025): Got it! Thank you so much!

bsakaguchi referenced this issue

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

[PR #22] [MERGED] fix(typo): tiny correction in docs #253