Have you ever wondered the performance comparison of directory traversal between a regular filesystem and a filesystem implemented in SQLite database? No? Well, I did, and I couldn’t come up with a strong argument on which one would be faster.

So, as a scientist1, I thought it would be fun to do a benchmarking experiment without having strong hypothesis on how things will go.

constraints

  • The test will be using Go, specifically fs.WalkDir.
  • Therefore, SQLite implementation will be as simple as “satisfying what Go thinks of a file / filesystem”.

implementation

It started by classifying two different archetype of pointers: directories and files. A directory can point to directories and / or files, while a file can only point to itself which contains the content of a file.


CREATE TABLE litefs_entry (
  id TEXT NOT NULL,
  parent_id TEXT,
  name TEXT NOT NULL,
  modtime TEXT NOT NULL,
  content BLOB,
  PRIMARY KEY (id),
  FOREIGN KEY (parent_id) references litefs_entry(id) ON DELETE CASCADE,
  UNIQUE (parent_id, name)
);

To stay on track, I limited myself to just implementing fs.ReadDirFS.

I used kyleconroy/sqlc to generate the bindings of SQL queries and Go structs. I also used mattn/go-sqlite3 for SQLite driver.

And now, it’s time to draw the rest of the owl.

benchmarking

With the first minimal implementation done, I started writing the benchmark test.


func BenchmarkProfLiteFSWalkNoop(b *testing.B) {
  /* initialization, etc. */

  // lfs is a LiteFS instance.
  // lfs.Merge copies over a fs.FS interface into LiteFS.
  if err := lfs.Merge(context.Background(), os.DirFS(testDirPath), "."); err != nil {
    b.Fatal(err)
  }

  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    if err := fs.WalkDir(lfs, ".", func(_ string, _ fs.DirEntry, err error) error {
      return err
    }); err != nil {
      b.Error(err)
    }
  }
}

func BenchmarkProfOSFSWalkNoop(b *testing.B) {
  osFS := os.DirFS(testDirPath)
  for i := 0; i < b.N; i++ {
    if err := fs.WalkDir(osFS, ".", func(_ string, _ fs.DirEntry, err error) error {
      return err
    }); err != nil {
      b.Error(err)
    }
  }
}

The structure of testDirPath is:

  • foo/one/bar.txt
  • foo/two/bar.txt
  • foo/three/bar.txt

I did say that I have no idea how the result would be, so I should not really be surprised by any result.

❯ go test -v -run='.*Noop.*' -benchmem -bench=Noop
goos: linux
goarch: amd64
pkg: go.husin.dev/litefs
cpu: AMD Ryzen 5 PRO 3400GE w/ Radeon Vega Graphics
BenchmarkProfLiteFSWalkNoop
BenchmarkProfLiteFSWalkNoop-8     2568    438863 ns/op     21878 B/op    692 allocs/op
BenchmarkProfOSFSWalkNoop
BenchmarkProfOSFSWalkNoop-8      47486     24235 ns/op      2076 B/op     67 allocs/op
PASS
ok      go.husin.dev/litefs     2.647s

And yet, seeing how my implementation is ~20x slower, with ~10x more memory allocations somewhat caught me off guard.

SQLite is by no means slow. Most likely, the benchmarks above don’t really matter when designing a product / solution.

I hope your takeaway from this is post to ask: “what problem are we trying to solve?” in your problem-solving exercise.

One thing worth noting is that SQLite is supposedly faster than filesystem in reading files by 35%. This wasn’t explored today, maybe someday!

addendum

Through pprof, I was able to retrieve more data on resource consumption.

Pprof graph distribution on Benchmark, showing lots of resources used for runtime CGO.

My interpretation is that much of resources were consumed to execute runtime.cgocall (specifically referring to the first peak from the right). If that is true, then I think it’s fair to imply that likely either (or both) is correct:

  • my SQL queries can be further optimized
  • the SQLite driver is the bottleneck

In real product development, I would lean towards investigating the former as I expect it would yield the most return on my investment.

But, this isn’t. And I get to choose what’s fun over anything else.

So, I’m going to use my creative license — what if we swap the SQLite driver with a different one? I managed to find 3 SQLite drivers (including the currently used):

❯ benchstat mattn.out modernc.out tailscale.out

name \ time/op        mattn.out    modernc.out  tailscale.out
ProfLiteFSWalkNoop-8   441µs ± 0%   462µs ± 0%     365µs ± 0%
ProfOSFSWalkNoop-8    24.5µs ± 0%  25.7µs ± 0%    25.3µs ± 0%

name \ alloc/op       mattn.out    modernc.out  tailscale.out
ProfLiteFSWalkNoop-8  21.9kB ± 0%  18.7kB ± 0%    19.6kB ± 0%
ProfOSFSWalkNoop-8    2.08kB ± 0%  2.08kB ± 0%    2.08kB ± 0%

name \ allocs/op      mattn.out    modernc.out  tailscale.out
ProfLiteFSWalkNoop-8     692 ± 0%     511 ± 0%       599 ± 0%
ProfOSFSWalkNoop-8      67.0 ± 0%    67.0 ± 0%      67.0 ± 0%

Tailscale’s driver seems to be faster by ~20% — the pprof graph for it:

Pprof graph distribution on Benchmark using Tailscale SQLite driver.

I’m not sure I have a profound-enough statement on this graph. One thing that stands out to me is that the next optimization potential seem to be my query logic, i.e. db.(*Query).ListEntries.


  1. as a scientist: I don’t really consider myself as one, but I am in possession of a paper to claim that I am. ↩︎