golang優(yōu)化目錄遍歷的實現(xiàn)方法

更新時間：2024年08月01日 09:47:36 作者：apocelipes

對于go1.16的新變化,大家印象最深的可能是io包的大規(guī)模重構(gòu),但這個重構(gòu)實際上還引進(jìn)了一個優(yōu)化,這篇文章要說的就是這個優(yōu)化,所以本將給大家介紹golang是如何優(yōu)化目錄遍歷的,需要的朋友可以參考下

遍歷目錄時的優(yōu)化

遍歷目錄是個很常見的需求，尤其是對于有大量文件的目錄來說，遍歷的性能直接關(guān)系到了整體程序的性能。

go1.16對于遍歷目錄增加了幾個新接口：os.ReadDir，(*os.File).ReadDir，filepath.WalkDir。

這幾個接口最大的特征是對目錄項使用fs.DirEntry表示而不是os.FileInfo。fs.DirEntry是一個接口，它提供了類似os.FileInfo的方法：

type DirEntry interface {
        Name() string
        IsDir() bool
        Type() FileMode
        Info() (FileInfo, error)
}

它還提供了一個叫Info的方法以便獲得os.FileInfo。

這個接口有什么神奇的呢？我們看下性能測試：

func IterateDir(path string) int {
    // go1.16 的 os.ReadDir 就是這么實現(xiàn)的，為了測試我們把它展開成對(*os.File).ReadDir的調(diào)用
	f, err := os.Open(path)
	if err != nil {
		panic(err)
	}
	defer f.Close()

	files, err := f.ReadDir(-1)
	if err != nil {
		panic(err)
	}
	length := 0
	for _, finfo := range files {
		length = max(length, len(finfo.Name()))
	}
	return length
}

func IterateDir2(path string) int {
    // 1.16之前遍歷目錄的常用方法之一
	f, err := os.Open(path)
	if err != nil {
		panic(err)
	}
	defer f.Close()

	files, err := f.Readdir(-1)
	if err != nil {
		panic(err)
	}
	length := 0
	for _, finfo := range files {
		length = max(length, len(finfo.Name()))
	}
	return length
}

func BenchmarkIter1(b *testing.B) {
	for range b.N {
		IterateDir("../test")
	}
}

func BenchmarkIter2(b *testing.B) {
	for range b.N {
		IterateDir2("../test")
	}
}

test目錄是一個有5000個文件的位于Btrfs文件系統(tǒng)上的目錄，我們的測試用例會遍歷目錄并找出名字最長的文件的文件名長度。

這是測試結(jié)果：

可以看到優(yōu)化后的遍歷比原先的快了480%。換了個函數(shù)為什么就會有這么大的提升？想知道答案的話就繼續(xù)看吧。

優(yōu)化的原理

繼續(xù)深入前我們先看看老的接口是怎么獲取到目錄里的文件信息的。答案是遍歷目錄拿到路徑，然后調(diào)用os.Lstat獲取完整的文件信息：

func (f *File) Readdir(n int) ([]FileInfo, error) {
	if f == nil {
		return nil, ErrInvalid
	}
	_, _, infos, err := f.readdir(n, readdirFileInfo)
	if infos == nil {
		// Readdir has historically always returned a non-nil empty slice, never nil,
		// even on error (except misuse with nil receiver above).
		// Keep it that way to avoid breaking overly sensitive callers.
		infos = []FileInfo{}
	}
	return infos, err
}

這個f.readdir會根據(jù)第二個參數(shù)的值來改變自己的行為，根據(jù)值不同它會遵循1.16前老代碼的行為或者采用新的優(yōu)化方法。這個函數(shù)不同系統(tǒng)上的實現(xiàn)也不同，我們選則*nix系統(tǒng)上的實現(xiàn)看看：

func (f *File) readdir(n int, mode readdirMode) (names []string, dirents []DirEntry, infos []FileInfo, err error) {
	...

	for n != 0 {
		// 使用系統(tǒng)調(diào)用獲得目錄項的數(shù)據(jù)
        // 目錄項的元信息一般是存儲在目錄本身的數(shù)據(jù)里的，所以讀這些信息和讀普通文件很類似
		if d.bufp >= d.nbuf {
			d.bufp = 0
			var errno error
			d.nbuf, errno = f.pfd.ReadDirent(*d.buf)
			runtime.KeepAlive(f)
			if errno != nil {
				return names, dirents, infos, &PathError{Op: "readdirent", Path: f.name, Err: errno}
			}
			if d.nbuf <= 0 {
				break // EOF
			}
		}

		buf := (*d.buf)[d.bufp:d.nbuf]
		reclen, ok := direntReclen(buf)
		if !ok || reclen > uint64(len(buf)) {
			break
		}
        // 注意這行
		rec := buf[:reclen]

		if mode == readdirName {
			names = append(names, string(name))
		} else if mode == readdirDirEntry {
			// 這里的代碼后面再看
		} else {
			info, err := lstat(f.name + "/" + string(name))
			if IsNotExist(err) {
				// File disappeared between readdir + stat.
				// Treat as if it didn't exist.
				continue
			}
			if err != nil {
				return nil, nil, infos, err
			}
			infos = append(infos, info)
		}
	}

	if n > 0 && len(names)+len(dirents)+len(infos) == 0 {
		return nil, nil, nil, io.EOF
	}
	return names, dirents, infos, nil
}

ReadDirent對應(yīng)的是Linux上的系統(tǒng)調(diào)用getdents，這個系統(tǒng)調(diào)用會把目錄的目錄項信息讀取到一塊內(nèi)存里，之后程序可以解析這塊內(nèi)存里的數(shù)據(jù)來獲得目錄項的一些信息，這些信息一般包括了文件名，文件的類型，文件是否是目錄等信息。

老代碼在讀取完這些信息后會利用文件名再次調(diào)用lstat，這個也是系統(tǒng)調(diào)用，可以獲取更完整的文件信息，包括了文件的擁有者，文件的大小，文件的修改日期等。

老的代碼有啥問題呢？大的問題不存在，接口也算易用，但有些小瑕疵：

大多數(shù)時間遍歷目錄主要是要獲得目錄中文件的名字或者類型等屬性，顯然os.FileInfo返回的信息過多了。這些用不著的信息會浪費不少內(nèi)存，獲取這些信息也需要額外花時間——lstat需要去進(jìn)行磁盤io才能得到這些信息，而目錄里的文件不像目錄項信息那樣緊密的存儲在一起，它們是分散的，所以一一讀取它們的元信息帶來的負(fù)擔(dān)會很大。
使用的系統(tǒng)調(diào)用太多了。由于我們測試目錄的文件很多，但getdents可能要調(diào)用多次，這里假設(shè)為兩次好了。對于每一個目錄項，都需要用lstat去獲取文件的詳細(xì)信息，這樣又有5000次系統(tǒng)調(diào)用，加起來是5002次。系統(tǒng)調(diào)用的開銷是很大的，積累到5000多次則會帶來肉眼可見的性能下降。實際上linux本身對lstat有優(yōu)化，不會真的出現(xiàn)要反復(fù)進(jìn)入系統(tǒng)調(diào)用5000次的情況，但幾十到上百次還是需要的。

優(yōu)化的代碼其實只改了一行，是f.readdir(n, readdirDirEntry)，第二個參數(shù)變了。新代碼會走上面注釋掉的那段邏輯：

// rec := buf[:reclen] 防止你忘了rec是哪來的
de, err := newUnixDirent(f.name, string(name), direntType(rec))
if IsNotExist(err) {
	// File disappeared between readdir and stat.
	// Treat as if it didn't exist.
	continue
}
if err != nil {
	return nil, dirents, nil, err
}
dirents = append(dirents, de)

取代lstat的是函數(shù)newUnixDirent，這個函數(shù)可以不依賴額外的系統(tǒng)調(diào)用獲取文件的一部分元數(shù)據(jù)：

type unixDirent struct {
	parent string
	name   string
	typ    FileMode
	info   FileInfo
}

func newUnixDirent(parent, name string, typ FileMode) (DirEntry, error) {
	ude := &unixDirent{
		parent: parent,
		name:   name,
		typ:    typ,
	}
    // 檢測文件類型信息是否有效
	if typ != ^FileMode(0) && !testingForceReadDirLstat {
		return ude, nil
	}

	info, err := lstat(parent + "/" + name)
	if err != nil {
		return nil, err
	}

	ude.typ = info.Mode().Type()
	ude.info = info
	return ude, nil
}

文件名和類型都是在解析目錄項時就得到的，因此直接設(shè)置就行。不過不是每個文件系統(tǒng)都支持在目錄項數(shù)據(jù)里存儲文件類型，所以代碼里做了回退，一旦發(fā)現(xiàn)文件類型是無效數(shù)據(jù)就會使用lstat重新獲取信息。

如果只使用文件名和文件的類型這兩個信息，那么整個遍歷的邏輯流程到這就結(jié)束了，文件系統(tǒng)提供支持的情況下不需要調(diào)用lstat。所以整個遍歷只需要兩次系統(tǒng)調(diào)用。這就是為什么優(yōu)化方案會快接近五倍的原因。

對于要使用其他信息比如文件大小的用戶，優(yōu)化方案實際上也有好處，因為現(xiàn)在lstat是延遲且按需調(diào)用的：

func (d *unixDirent) Info() (FileInfo, error) {
	if d.info != nil {
		return d.info, nil
	}
    // 只會調(diào)用一次
	return lstat(d.parent + "/" + d.name)
}

這樣也能盡量減少不必要的系統(tǒng)調(diào)用。

所以整體優(yōu)化的原理是：盡量充分利用文件系統(tǒng)本身提供的信息+減少系統(tǒng)調(diào)用。要遍歷的目錄越大優(yōu)化的效果也越明顯。

優(yōu)化的支持情況

上面也說了，能做到優(yōu)化需要文件系統(tǒng)把文件類型信息存儲在目錄的目錄項數(shù)據(jù)里。這個需要文件系統(tǒng)的支持。

如果文件系統(tǒng)不支持的話最后還是需要依賴lstat去讀取具體文件的元數(shù)據(jù)。

不同文件系統(tǒng)的信息實在太分散，還有不少過時的，所以我花了幾天看代碼+查文檔做了下整理：

btrfs，ext2，ext4：這個幾個文件系統(tǒng)支持優(yōu)化，man pages加文件系統(tǒng)代碼都能證實這一點
OpenZFS：這個文件系統(tǒng)不在Linux內(nèi)核里，所以man pages里沒提到，但也支持優(yōu)化
xfs：支持優(yōu)化，但得在創(chuàng)建文件系統(tǒng)時使用類似mkfs.xfs -f -n ftype=1的選項才行
F2FS，EROFS：文檔沒提過，但看內(nèi)核的代碼里是支持的，代碼的位置在xxx_readdir這個函數(shù)附近。
fat32，exfat：文檔沒提過，但看內(nèi)核代碼發(fā)現(xiàn)是支持的，不過fat家族的文件類型沒有那么多花樣，只有目錄和普通文件這兩種，所以代碼里很粗暴的判斷目錄項是否設(shè)置了dir標(biāo)志，有就是目錄沒有統(tǒng)統(tǒng)算普通文件。這么做倒是正常的，因為fat本來就不支持別的文件類型，畢竟這個文件系統(tǒng)連軟鏈接都不支持，更不用指望Unix Domain Socket和命名管道了。
ntfs：支持，然而如注釋所說，因為ntfs和其他文件系統(tǒng)處理type的方式不一樣，導(dǎo)致雖然文件系統(tǒng)本身支持大部分文件類型，但type信息里只能獲得文件是不是目錄。所以它后面對于不是目錄的文件會去磁盤上讀取文件的inode然后再從inode里獲取文件類型——實際上相當(dāng)于執(zhí)行了一次lstat，相比lstat減少了進(jìn)入系統(tǒng)調(diào)用時的一次上下文切換，所以ntfs上優(yōu)化效果會不如其他文件系統(tǒng)。

這么一看的話基本上主流的常見的文件系統(tǒng)都支持這種優(yōu)化。

這也是為什么go1.16會引入這個優(yōu)化，不僅支持廣泛而且提升很大，免費的加速誰不愛呢。

別的語言里怎么利用這個優(yōu)化

看到這里，你應(yīng)該發(fā)現(xiàn)這個優(yōu)化其實是系統(tǒng)層面的，golang只不過是適配了一下而已。

確實是這樣的，所以這個優(yōu)化不光golang能吃到，c/c++/python都行。

先說說c里怎么利用：直接用系統(tǒng)提供的readdir函數(shù)就行，這個函數(shù)會調(diào)用getdents，然后就能自然吃到優(yōu)化了。注意事項和go的一樣，需要檢測文件系統(tǒng)是否支持設(shè)置d_type。

c++：和c一樣，另外libstdc++的filesystem就是拿readdir實現(xiàn)的，所以用filesystem標(biāo)準(zhǔn)庫也能獲得優(yōu)化：

// https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/src/filesystem/dir-common.h#L270
inline file_type
get_file_type(const std::filesystem::__gnu_posix::dirent& d [[gnu::unused]])
{
#ifdef _GLIBCXX_HAVE_STRUCT_DIRENT_D_TYPE
  switch (d.d_type)
  {
  case DT_BLK:
    return file_type::block;
  case DT_CHR:
    return file_type::character;
  case DT_DIR:
    return file_type::directory;
  case DT_FIFO:
    return file_type::fifo;
  case DT_LNK:
    return file_type::symlink;
  case DT_REG:
    return file_type::regular;
  case DT_SOCK:
    return file_type::socket;
  case DT_UNKNOWN:
    return file_type::unknown;
  default:
    return file_type::none;
  }
#else
  return file_type::none;
#endif
}

// 如果操作系統(tǒng)以及文件系統(tǒng)不支持，則回退到lstat
// https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/include/bits/fs_dir.h#L342
file_type
_M_file_type() const
{
    if (_M_type != file_type::none && _M_type != file_type::symlink)
	    return _M_type;
    return status().type();
}

唯一的區(qū)別在于如果目標(biāo)文件是軟連接，也會調(diào)用stat。

python：使用os.scandir可以獲得優(yōu)化，底層和c一樣使用readdir。