[LU-14380] Make statahead better support Breadth First Search (BFS) or Depth First Search (DFS)

• Type: Improvement
• Resolution: Unresolved
• Priority: Minor
• Fix Version/s: Lustre 2.17.0
• Labels: WBC
• Assignee: Qian Yingjin
• Reporter: Qian Yingjin

Description

Batching processing can obtain boost performance.
However, in some file system tree, each level may contain less than 100 entries, but with high depth.
It can do statahead according to Breadth First Search (BFS) or Depth First Search (DFS) access pattern once detect, each time statahead a subtree with more than 1 level, collect enough statahead entries, send the batching RPC via bulk I/O, to improve the tree walking performance.

BFS_Traverse(DIR, Q) {
	Q.enqueue(DIR);
	while |Q| > 0 do
		dir = Q.dequeue()
		opendir(dir);
		while dent = readdir(dir) != NULL do
			stat(dent); process(dent);
			if dent is a directory do
				Q.enqueue(dent);
			end if
		end while
		closedir(dir);
	end while
}
DFS_Traverse(dir) {
	openddir(dir);
	while (dent = readdir(dir) != NULL) do
		if dent is a file then
			stat(dent); process(dent);
		else /* a directory */
			DFS_Traverse(dent)
		end if
	end while
	closedir(dir);
}

Issue Links

• is related to: LU-8582 Interop: master<->b2_8 - sanity test_255a: test failed to respond and timed out
• is related to: LU-23 Improve performance for traversing large directory with readdir+
• is related to: LU-14361 Add support for statahead pattern with regularized file name
• is related to: LU-14139 batched statahead processing

Comments

[Andreas Dilger]

It is unfortunately too late for 2.16.0, but it would be good to rebase and land these patches for 2.17.0.

[Gerrit Updater]

Yingjin Qian ([e-mail]) uploaded a new patch: https://review.whamcloud.com/43170
Subject: LU-14380 statahead: clean up misc debug code
Project: fs/lustre-release
Branch: master
Current Patch Set: 1
Commit: f113be1941c5b18b65e94d5c364b9d69e49151c3

[Gerrit Updater]

Yingjin Qian ([e-mail]) uploaded a new patch: https://review.whamcloud.com/42115
Subject: LU-14380 statahead: Breadth First Search algo for statahead
Project: fs/lustre-release
Branch: master
Current Patch Set: 1
Commit: 0f03bca9cdf4d011f3a5d564c565a437818cc80e

[Gerrit Updater]

Yingjin Qian ([e-mail]) uploaded a new patch: https://review.whamcloud.com/41692
Subject: LU-14380 statahead: make statahead better support DFS
Project: fs/lustre-release
Branch: master
Current Patch Set: 1
Commit: 4300683c82b1f6ce7afd9355f157dc929b7d6d31

[Gerrit Updater]

Yingjin Qian ([e-mail]) uploaded a new patch: https://review.whamcloud.com/41422
Subject: LU-14380 statahead: refine per process statahead control
Project: fs/lustre-release
Branch: master
Current Patch Set: 1
Commit: 2e6ba7c009ac74dcdc89b22533592db4229ada73