apple / apple/foundationdb

Binding tester directory creation conflict

Open
#8,246 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
16.7k
Forks
1.6k
Avg merge
1d 20h
Merged PRs (30d)
126

Description

When creating a directory in the directory layer, part of the process is to confirm that a new directory does not have a prefix that conflicts with any old prefixes. In particular, it would not be legal for one directory to have a prefix that is a prefix of another directory prefix (e.g. one directory with prefix `foo` and another with prefix `foobar`). If this were allowed, their directory contents would overlap.

To prevent this, we do a search to find both the previous and next prefixes and check whether they overlap with the proposed new prefix. In the forward direction, this searches only up through `strinc(prefix)`, which is well-targeted. In the reverse direction, this searches the range all the way through the empty prefix. In theory, this could be done in a more targeted way by reading (or adding conflict ranges) only on the prefixes that could cause a conflict in the reverse direction (all candidate prefixes of the current prefix).

Because we read the whole range, the conflict range extends to include some randomly generated prefixes in the test that can differ between runs. This occasionally causes conflicts that fail the test. If we were to target the specific prefixes, the test would be able to pass.

Additionally, we do not actually set conflict ranges when the prefixes are generated automatically. I suspect this could cause issues if someone simultaneously created a manual prefix that overlapped the automatically generated one. If we enabled the conflict ranges with the current implementation, it would likely have a fairly negative impact on how well directory creations could be parallelized, but if we adopted the approach of creating targeted conflict ranges it should work fairly well.

Contributor guide

Open the contributing guide

Research direction

Start in the directory layer's directory-creation path and the binding tester test that generates random prefixes. Trace the reverse prefix search and conflict-range handling, then verify that targeted candidate-prefix ranges prevent random test conflicts and that automatically generated prefixes are covered. Run the affected binding tester test repeatedly to confirm it is stable.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, distributed-systems, testing
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.