파일 구성이 파일 액세스 효율성에 미치는 영향

디렉터리 구조의 파일 구성은 파일 액세스 효율성에 큰 영향을 미칠 수 있습니다(인용하다). 예를 들어, 두 개의 디렉토리 A와 가 B각각 10^6개의 파일을 포함하고 전자의 경우 하나의 디렉토리로 구성되고 후자의 경우 10^3개의 하위 디렉토리로 구성되어 있다고 가정해 보세요. 전자의 경우 모든 파일을 계산하거나 나열하는 속도가 상당히 느려집니다. 내 시스템에서:

파일을 생성합니다:

$ mkdir A; pushd A; seq -w 1E6 | xargs touch; popd
$ mkdir B; pushd B; seq -w 1E3 | xargs mkdir; for d in *; do pushd "$d"; seq -w 1E3 | xargs touch; popd; done; popd

파일 나열:

$ for d in A B; do
    time for i in {1..100}; do
        {
            echo 3 | sudo tee /proc/sys/vm/drop_caches
            find "$d" -type f
        }
    done >/dev/null
done

# case A (0 subdirectories)
real    4m49.805s
user    1m43.696s
sys     1m13.540s

# case B (1000 subdirectories)
real    3m32.338s
user    0m40.824s
sys     1m13.176s

차이점은 디스크 캐시와 관계없이 재현 가능하며 명령에 따라 다르지 않습니다 find(예: 동일한 크기 차이 찾기 사용 ls -RU). 두 경우 모두 커널 공간의 시간은 동일하므로 커널(및 파일 시스템 메커니즘)의 책임이 줄어듭니다. 따로 분석은 안해봤지만 메인 시스템 콜은 거의 확실하게 이루어지고 있고, readdir()아이 getdents()노드 개수는 두 경우 모두 동일(0.1% 이내)하기 때문에 파일의 크기나 걸리는 시간도 그렇고요. 커널이 이러한 호출을 다르게 수행하기 때문에 동일합니다. 따라서 실행 시간의 차이는 사용자 공간 코드에 기인할 수 있습니다.

일부 GNU coreutils(예 sort: )에 스레딩 지원이 추가되었습니다. 내 시스템에는 4개의 하드웨어 스레드가 있고 GNU(내 시스템 버전은 4.7.0-git)에 멀티스레딩 기능이 있는지 확실하지 않기 때문에 find단일 하드웨어 스레드에 명시적으로 바인딩된 프로세스를 사용하여 차이점이 존재하는지 확인했습니다.

$ cat find.sh
#!/bin/bash
for i in {1..100}; do
  {
    echo 3 | sudo tee /proc/sys/vm/drop_caches
    find "$1" -type f
  }
done >/dev/null

$ for d in A B; do time taskset -c 0 ./find.sh "$d"; done

# case A (0 subdirectories)
real    4m7.827s
user    1m31.080s
sys     0m55.660s

# case B (1000 subdirectories)
real    2m53.059s
user    0m33.256s
sys     0m52.772s

따라서 내 초기 질문은 다음과 같이 구체화될 수 있습니다. 순전히 파일 시스템 구성의 차이로 인한 액세스 시간의 차이로 인해 사용자 공간이 비효율적인 이유는 무엇입니까? 이러한 비효율성을 이해하면 파일 액세스 루틴을 더 잘 구현할 수 있습니다.

편집하다:ext4나는 Linux 커널을 실행하는 컴퓨터에서 파일 시스템을 사용하고 있지만 4.9.0-4-amd64선택한 파일 시스템에 따라 대답이 얼마나 달라지는지 알고 싶습니다.