feat(tvix/store): implement PathInfoService with sled r/5649

This uses [sled](https://github.com/spacejam/sled) to store PathInfo
objects.

Change-Id: I12e8032e5562af8f884efa23a78049fd1108fdbc
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7726
Reviewed-by: tazjin <tazjin@tvl.su>
Tested-by: BuildkiteCI

9 files changed, 652 insertions, 40 deletions

diff --git a/tvix/Cargo.lock b/tvix/Cargo.lock
index a5ea4b82e8..da7bc0c580 100644
--- a/tvix/Cargo.lock
+++ b/tvix/Cargo.lock
@@ -242,6 +242,9 @@ name = "cc"
 version = "1.0.77"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "e9f73505338f7d905b19d18738976aae232eb46b8efc15554ffc56deb5d9ebe4"
+dependencies = [
+ "jobserver",
+]
 
 [[package]]
 name = "cfg-if"
@@ -384,6 +387,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "crc32fast"
+version = "1.3.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b540bd8bc810d3885c6ea91e2018302f68baba2129ab3e88f32389ee9370880d"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
 name = "criterion"
 version = "0.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -622,6 +634,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1"
 
 [[package]]
+name = "fs2"
+version = "0.4.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9564fc758e15025b46aa6643b1b77d047d1a56a1aea6e01002ac0c7026876213"
+dependencies = [
+ "libc",
+ "winapi",
+]
+
+[[package]]
 name = "fuchsia-cprng"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -667,6 +689,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "fxhash"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c31b6d751ae2c7f11320402d34e41349dd1016f8d5d45e48c4312bc8625af50c"
+dependencies = [
+ "byteorder",
+]
+
+[[package]]
 name = "generic-array"
 version = "0.14.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -910,6 +941,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "4217ad341ebadf8d8e724e264f13e593e0648f5b3e94b3896a5df283be015ecc"
 
 [[package]]
+name = "jobserver"
+version = "0.1.25"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "068b1ee6743e4d11fb9c6a1e6064b3693a1b600e7f5f5988047d98b3dc9fb90b"
+dependencies = [
+ "libc",
+]
+
+[[package]]
 name = "js-sys"
 version = "0.3.60"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -937,6 +977,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "8f9f08d8963a6c613f4b1a78f4f4a4dbfadf8e6545b2d72861731e4858b8b47f"
 
 [[package]]
+name = "lock_api"
+version = "0.4.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "435011366fe56583b16cf956f9df0095b405b82d76425bc8981c0e22e60ec4df"
+dependencies = [
+ "autocfg",
+ "scopeguard",
+]
+
+[[package]]
 name = "log"
 version = "0.4.17"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1121,6 +1171,31 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b15813163c1d831bf4a13c3610c05c0d03b39feb07f7e09fa234dac9b15aaf39"
 
 [[package]]
+name = "parking_lot"
+version = "0.11.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7d17b78036a60663b797adeaee46f5c9dfebb86948d1255007a1d6be0271ff99"
+dependencies = [
+ "instant",
+ "lock_api",
+ "parking_lot_core",
+]
+
+[[package]]
+name = "parking_lot_core"
+version = "0.8.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "60a2cfe6f0ad2bfc16aefa463b497d5c7a5ecd44a23efa72aa342d90177356dc"
+dependencies = [
+ "cfg-if",
+ "instant",
+ "libc",
+ "redox_syscall",
+ "smallvec",
+ "winapi",
+]
+
+[[package]]
 name = "path-clean"
 version = "0.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1692,6 +1767,23 @@ dependencies = [
 ]
 
 [[package]]
+name = "sled"
+version = "0.34.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7f96b4737c2ce5987354855aed3797279def4ebf734436c6aa4552cf8e169935"
+dependencies = [
+ "crc32fast",
+ "crossbeam-epoch",
+ "crossbeam-utils",
+ "fs2",
+ "fxhash",
+ "libc",
+ "log",
+ "parking_lot",
+ "zstd",
+]
+
+[[package]]
 name = "smallvec"
 version = "1.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2259,6 +2351,8 @@ dependencies = [
  "lazy_static",
  "prost",
  "prost-build",
+ "sled",
+ "tempfile",
  "test-case",
  "thiserror",
  "tokio",
@@ -2513,3 +2607,32 @@ name = "yansi"
 version = "0.5.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "09041cd90cf85f7f8b2df60c646f853b7f535ce68f85244eb6731cf89fa498ec"
+
+[[package]]
+name = "zstd"
+version = "0.9.2+zstd.1.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2390ea1bf6c038c39674f22d95f0564725fc06034a47129179810b2fc58caa54"
+dependencies = [
+ "zstd-safe",
+]
+
+[[package]]
+name = "zstd-safe"
+version = "4.1.3+zstd.1.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e99d81b99fb3c2c2c794e3fe56c305c63d5173a16a46b5850b07c935ffc7db79"
+dependencies = [
+ "libc",
+ "zstd-sys",
+]
+
+[[package]]
+name = "zstd-sys"
+version = "1.6.2+zstd.1.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2daf2f248d9ea44454bfcb2516534e8b8ad2fc91bf818a1885495fc42bc8ac9f"
+dependencies = [
+ "cc",
+ "libc",
+]
diff --git a/tvix/Cargo.nix b/tvix/Cargo.nix
index 0f2b6bdd98..285e55fb73 100644
--- a/tvix/Cargo.nix
+++ b/tvix/Cargo.nix
@@ -769,7 +769,7 @@ rec {
         features = {
           "default" = [ "std" ];
         };
-        resolvedDefaultFeatures = [ "std" ];
+        resolvedDefaultFeatures = [ "default" "std" ];
       };
       "bytes" = rec {
         crateName = "bytes";
@@ -805,10 +805,18 @@ rec {
         authors = [
           "Alex Crichton <alex@alexcrichton.com>"
         ];
+        dependencies = [
+          {
+            name = "jobserver";
+            packageId = "jobserver";
+            optional = true;
+          }
+        ];
         features = {
           "jobserver" = [ "dep:jobserver" ];
           "parallel" = [ "jobserver" ];
         };
+        resolvedDefaultFeatures = [ "jobserver" "parallel" ];
       };
       "cfg-if" = rec {
         crateName = "cfg-if";
@@ -1182,6 +1190,26 @@ rec {
         ];
 
       };
+      "crc32fast" = rec {
+        crateName = "crc32fast";
+        version = "1.3.2";
+        edition = "2015";
+        sha256 = "03c8f29yx293yf43xar946xbls1g60c207m9drf8ilqhr25vsh5m";
+        authors = [
+          "Sam Rijs <srijs@airpost.net>"
+          "Alex Crichton <alex@alexcrichton.com>"
+        ];
+        dependencies = [
+          {
+            name = "cfg-if";
+            packageId = "cfg-if";
+          }
+        ];
+        features = {
+          "default" = [ "std" ];
+        };
+        resolvedDefaultFeatures = [ "default" "std" ];
+      };
       "criterion" = rec {
         crateName = "criterion";
         version = "0.4.0";
@@ -1408,7 +1436,7 @@ rec {
           "nightly" = [ "crossbeam-utils/nightly" ];
           "std" = [ "alloc" "crossbeam-utils/std" ];
         };
-        resolvedDefaultFeatures = [ "alloc" "std" ];
+        resolvedDefaultFeatures = [ "alloc" "default" "std" ];
       };
       "crossbeam-utils" = rec {
         crateName = "crossbeam-utils";
@@ -1821,6 +1849,29 @@ rec {
         };
         resolvedDefaultFeatures = [ "default" "std" ];
       };
+      "fs2" = rec {
+        crateName = "fs2";
+        version = "0.4.3";
+        edition = "2015";
+        sha256 = "04v2hwk7035c088f19mfl5b1lz84gnvv2hv6m935n0hmirszqr4m";
+        authors = [
+          "Dan Burkert <dan@danburkert.com>"
+        ];
+        dependencies = [
+          {
+            name = "libc";
+            packageId = "libc";
+            target = { target, features }: (target."unix" or false);
+          }
+          {
+            name = "winapi";
+            packageId = "winapi";
+            target = { target, features }: (target."windows" or false);
+            features = [ "handleapi" "processthreadsapi" "winerror" "fileapi" "winbase" "std" ];
+          }
+        ];
+
+      };
       "fuchsia-cprng" = rec {
         crateName = "fuchsia-cprng";
         version = "0.1.1";
@@ -1933,6 +1984,23 @@ rec {
         };
         resolvedDefaultFeatures = [ "alloc" ];
       };
+      "fxhash" = rec {
+        crateName = "fxhash";
+        version = "0.2.1";
+        edition = "2015";
+        sha256 = "037mb9ichariqi45xm6mz0b11pa92gj38ba0409z3iz239sns6y3";
+        libPath = "lib.rs";
+        authors = [
+          "cbreeden <github@u.breeden.cc>"
+        ];
+        dependencies = [
+          {
+            name = "byteorder";
+            packageId = "byteorder";
+          }
+        ];
+
+      };
       "generic-array" = rec {
         crateName = "generic-array";
         version = "0.14.6";
@@ -2661,6 +2729,23 @@ rec {
           "no-panic" = [ "dep:no-panic" ];
         };
       };
+      "jobserver" = rec {
+        crateName = "jobserver";
+        version = "0.1.25";
+        edition = "2018";
+        sha256 = "02xrkzfb763x0j45jpvz1rh1nfk9ndj607kakkxi2k9yfkk1x2q6";
+        authors = [
+          "Alex Crichton <alex@alexcrichton.com>"
+        ];
+        dependencies = [
+          {
+            name = "libc";
+            packageId = "libc";
+            target = { target, features }: (target."unix" or false);
+          }
+        ];
+
+      };
       "js-sys" = rec {
         crateName = "js-sys";
         version = "0.3.60";
@@ -2722,6 +2807,32 @@ rec {
         };
         resolvedDefaultFeatures = [ "errno" "general" "ioctl" "no_std" ];
       };
+      "lock_api" = rec {
+        crateName = "lock_api";
+        version = "0.4.9";
+        edition = "2018";
+        sha256 = "1py41vk243hwk345nhkn5nw0bd4m03gzjmprdjqq6rg5dwv12l23";
+        authors = [
+          "Amanieu d'Antras <amanieu@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "scopeguard";
+            packageId = "scopeguard";
+            usesDefaultFeatures = false;
+          }
+        ];
+        buildDependencies = [
+          {
+            name = "autocfg";
+            packageId = "autocfg";
+          }
+        ];
+        features = {
+          "owning_ref" = [ "dep:owning_ref" ];
+          "serde" = [ "dep:serde" ];
+        };
+      };
       "log" = rec {
         crateName = "log";
         version = "0.4.17";
@@ -3210,6 +3321,84 @@ rec {
         ];
 
       };
+      "parking_lot" = rec {
+        crateName = "parking_lot";
+        version = "0.11.2";
+        edition = "2018";
+        sha256 = "16gzf41bxmm10x82bla8d6wfppy9ym3fxsmdjyvn61m66s0bf5vx";
+        authors = [
+          "Amanieu d'Antras <amanieu@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "instant";
+            packageId = "instant";
+          }
+          {
+            name = "lock_api";
+            packageId = "lock_api";
+          }
+          {
+            name = "parking_lot_core";
+            packageId = "parking_lot_core";
+          }
+        ];
+        features = {
+          "arc_lock" = [ "lock_api/arc_lock" ];
+          "deadlock_detection" = [ "parking_lot_core/deadlock_detection" ];
+          "nightly" = [ "parking_lot_core/nightly" "lock_api/nightly" ];
+          "owning_ref" = [ "lock_api/owning_ref" ];
+          "serde" = [ "lock_api/serde" ];
+          "stdweb" = [ "instant/stdweb" ];
+          "wasm-bindgen" = [ "instant/wasm-bindgen" ];
+        };
+        resolvedDefaultFeatures = [ "default" ];
+      };
+      "parking_lot_core" = rec {
+        crateName = "parking_lot_core";
+        version = "0.8.6";
+        edition = "2018";
+        sha256 = "1p2nfcbr0b9lm9rglgm28k6mwyjwgm4knipsmqbgqaxdy3kcz8k0";
+        authors = [
+          "Amanieu d'Antras <amanieu@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "cfg-if";
+            packageId = "cfg-if";
+          }
+          {
+            name = "instant";
+            packageId = "instant";
+          }
+          {
+            name = "libc";
+            packageId = "libc";
+            target = { target, features }: (target."unix" or false);
+          }
+          {
+            name = "redox_syscall";
+            packageId = "redox_syscall";
+            target = { target, features }: ("redox" == target."os");
+          }
+          {
+            name = "smallvec";
+            packageId = "smallvec";
+          }
+          {
+            name = "winapi";
+            packageId = "winapi";
+            target = { target, features }: (target."windows" or false);
+            features = [ "winnt" "ntstatus" "minwindef" "winerror" "winbase" "errhandlingapi" "handleapi" ];
+          }
+        ];
+        features = {
+          "backtrace" = [ "dep:backtrace" ];
+          "deadlock_detection" = [ "petgraph" "thread-id" "backtrace" ];
+          "petgraph" = [ "dep:petgraph" ];
+          "thread-id" = [ "dep:thread-id" ];
+        };
+      };
       "path-clean" = rec {
         crateName = "path-clean";
         version = "0.1.0";
@@ -4859,6 +5048,74 @@ rec {
         };
         resolvedDefaultFeatures = [ "default" "std" ];
       };
+      "sled" = rec {
+        crateName = "sled";
+        version = "0.34.7";
+        edition = "2018";
+        sha256 = "0dcr2s7cylj5mb33ci3kpx7fz797jwvysnl5airrir9cgirv95kz";
+        authors = [
+          "Tyler Neely <t@jujit.su>"
+        ];
+        dependencies = [
+          {
+            name = "crc32fast";
+            packageId = "crc32fast";
+          }
+          {
+            name = "crossbeam-epoch";
+            packageId = "crossbeam-epoch";
+          }
+          {
+            name = "crossbeam-utils";
+            packageId = "crossbeam-utils";
+          }
+          {
+            name = "fs2";
+            packageId = "fs2";
+            target = { target, features }: (("linux" == target."os") || ("macos" == target."os") || ("windows" == target."os"));
+          }
+          {
+            name = "fxhash";
+            packageId = "fxhash";
+          }
+          {
+            name = "libc";
+            packageId = "libc";
+          }
+          {
+            name = "log";
+            packageId = "log";
+          }
+          {
+            name = "parking_lot";
+            packageId = "parking_lot";
+          }
+          {
+            name = "zstd";
+            packageId = "zstd";
+            optional = true;
+          }
+        ];
+        devDependencies = [
+          {
+            name = "log";
+            packageId = "log";
+          }
+        ];
+        features = {
+          "backtrace" = [ "dep:backtrace" ];
+          "color-backtrace" = [ "dep:color-backtrace" ];
+          "compression" = [ "zstd" ];
+          "default" = [ "no_metrics" ];
+          "io_uring" = [ "rio" ];
+          "no_logs" = [ "log/max_level_off" ];
+          "pretty_backtrace" = [ "color-backtrace" ];
+          "rio" = [ "dep:rio" ];
+          "testing" = [ "event_log" "lock_free_delays" "compression" "failpoints" "backtrace" ];
+          "zstd" = [ "dep:zstd" ];
+        };
+        resolvedDefaultFeatures = [ "compression" "default" "no_metrics" "zstd" ];
+      };
       "smallvec" = rec {
         crateName = "smallvec";
         version = "1.10.0";
@@ -6789,6 +7046,11 @@ rec {
             packageId = "prost";
           }
           {
+            name = "sled";
+            packageId = "sled";
+            features = [ "compression" ];
+          }
+          {
             name = "thiserror";
             packageId = "thiserror";
           }
@@ -6831,6 +7093,10 @@ rec {
         ];
         devDependencies = [
           {
+            name = "tempfile";
+            packageId = "tempfile";
+          }
+          {
             name = "test-case";
             packageId = "test-case";
           }
@@ -7655,7 +7921,7 @@ rec {
         features = {
           "debug" = [ "impl-debug" ];
         };
-        resolvedDefaultFeatures = [ "basetsd" "consoleapi" "errhandlingapi" "fileapi" "handleapi" "knownfolders" "minwinbase" "minwindef" "ntdef" "ntsecapi" "objbase" "processenv" "profileapi" "shellapi" "shlobj" "std" "stringapiset" "synchapi" "winbase" "wincon" "winerror" "winnt" "winuser" "ws2ipdef" "ws2tcpip" ];
+        resolvedDefaultFeatures = [ "basetsd" "consoleapi" "errhandlingapi" "fileapi" "handleapi" "knownfolders" "minwinbase" "minwindef" "ntdef" "ntsecapi" "ntstatus" "objbase" "processenv" "processthreadsapi" "profileapi" "shellapi" "shlobj" "std" "stringapiset" "synchapi" "winbase" "wincon" "winerror" "winnt" "winuser" "ws2ipdef" "ws2tcpip" ];
       };
       "winapi-i686-pc-windows-gnu" = rec {
         crateName = "winapi-i686-pc-windows-gnu";
@@ -8168,6 +8434,97 @@ rec {
         ];
 
       };
+      "zstd" = rec {
+        crateName = "zstd";
+        version = "0.9.2+zstd.1.5.1";
+        edition = "2018";
+        sha256 = "0m5aik2jy2w1g68i4isa0c3gq9a7avq9abgjfjbc6f60yqdym413";
+        authors = [
+          "Alexandre Bury <alexandre.bury@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "zstd-safe";
+            packageId = "zstd-safe";
+            usesDefaultFeatures = false;
+            features = [ "std" ];
+          }
+        ];
+        features = {
+          "arrays" = [ "zstd-safe/arrays" ];
+          "bindgen" = [ "zstd-safe/bindgen" ];
+          "debug" = [ "zstd-safe/debug" ];
+          "default" = [ "legacy" "arrays" ];
+          "experimental" = [ "zstd-safe/experimental" ];
+          "legacy" = [ "zstd-safe/legacy" ];
+          "no_asm" = [ "zstd-safe/no_asm" ];
+          "pkg-config" = [ "zstd-safe/pkg-config" ];
+          "thin" = [ "zstd-safe/thin" ];
+          "zstdmt" = [ "zstd-safe/zstdmt" ];
+        };
+        resolvedDefaultFeatures = [ "arrays" "default" "legacy" ];
+      };
+      "zstd-safe" = rec {
+        crateName = "zstd-safe";
+        version = "4.1.3+zstd.1.5.1";
+        edition = "2018";
+        sha256 = "0yfvqzzkbj871f2vaikal5rm2gf60p1mdzp3jk3w5hmkkywq37g9";
+        authors = [
+          "Alexandre Bury <alexandre.bury@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "libc";
+            packageId = "libc";
+          }
+          {
+            name = "zstd-sys";
+            packageId = "zstd-sys";
+            usesDefaultFeatures = false;
+          }
+        ];
+        features = {
+          "bindgen" = [ "zstd-sys/bindgen" ];
+          "debug" = [ "zstd-sys/debug" ];
+          "default" = [ "legacy" "arrays" ];
+          "experimental" = [ "zstd-sys/experimental" ];
+          "legacy" = [ "zstd-sys/legacy" ];
+          "no_asm" = [ "zstd-sys/no_asm" ];
+          "pkg-config" = [ "zstd-sys/pkg-config" ];
+          "std" = [ "zstd-sys/std" ];
+          "thin" = [ "zstd-sys/thin" ];
+          "zstdmt" = [ "zstd-sys/zstdmt" ];
+        };
+        resolvedDefaultFeatures = [ "arrays" "legacy" "std" ];
+      };
+      "zstd-sys" = rec {
+        crateName = "zstd-sys";
+        version = "1.6.2+zstd.1.5.1";
+        edition = "2018";
+        sha256 = "17xcr0mw8ps9hlc8m0dzj7yd52lb9r9ic9fbpxa4994yilj2zbrd";
+        authors = [
+          "Alexandre Bury <alexandre.bury@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "libc";
+            packageId = "libc";
+          }
+        ];
+        buildDependencies = [
+          {
+            name = "cc";
+            packageId = "cc";
+            features = [ "parallel" ];
+          }
+        ];
+        features = {
+          "bindgen" = [ "dep:bindgen" ];
+          "default" = [ "legacy" ];
+          "pkg-config" = [ "dep:pkg-config" ];
+        };
+        resolvedDefaultFeatures = [ "legacy" "std" ];
+      };
     };
 
     #
diff --git a/tvix/store/Cargo.toml b/tvix/store/Cargo.toml
index abbd9b0dcb..0f1dd50e2b 100644
--- a/tvix/store/Cargo.toml
+++ b/tvix/store/Cargo.toml
@@ -13,6 +13,7 @@ data-encoding = "2.3.3"
 lazy_static = "1.4.0"
 clap = { version = "4.0", features = ["derive", "env"] }
 prost = "0.11.2"
+sled = { version = "0.34.7", features = ["compression"] }
 thiserror = "1.0.38"
 tokio = { version = "1.23.0", features = ["rt-multi-thread"] }
 tokio-stream = "0.1.11"
@@ -30,6 +31,7 @@ tonic-build = "0.8.2"
 
 [dev-dependencies]
 test-case = "2.2.2"
+tempfile = "3.3.0"
 
 [features]
 default = [
diff --git a/tvix/store/src/dummy_path_info_service.rs b/tvix/store/src/dummy_path_info_service.rs
deleted file mode 100644
index 93359377f3..0000000000
--- a/tvix/store/src/dummy_path_info_service.rs
+++ /dev/null
@@ -1,35 +0,0 @@
-use crate::proto::path_info_service_server::PathInfoService;
-use crate::proto::CalculateNarResponse;
-use crate::proto::GetPathInfoRequest;
-use crate::proto::Node;
-use crate::proto::PathInfo;
-use tonic::{Request, Response, Result, Status};
-use tracing::{instrument, warn};
-
-pub struct DummyPathInfoService {}
-
-const NOT_IMPLEMENTED_MSG: &str = "not implemented";
-
-#[tonic::async_trait]
-impl PathInfoService for DummyPathInfoService {
-    #[instrument(skip(self))]
-    async fn get(&self, _request: Request<GetPathInfoRequest>) -> Result<Response<PathInfo>> {
-        warn!(NOT_IMPLEMENTED_MSG);
-        Err(Status::unimplemented(NOT_IMPLEMENTED_MSG))
-    }
-
-    #[instrument(skip(self))]
-    async fn put(&self, _request: Request<PathInfo>) -> Result<Response<PathInfo>> {
-        warn!(NOT_IMPLEMENTED_MSG);
-        Err(Status::unimplemented(NOT_IMPLEMENTED_MSG))
-    }
-
-    #[instrument(skip(self))]
-    async fn calculate_nar(
-        &self,
-        _request: Request<Node>,
-    ) -> Result<Response<CalculateNarResponse>> {
-        warn!(NOT_IMPLEMENTED_MSG);
-        Err(Status::unimplemented(NOT_IMPLEMENTED_MSG))
-    }
-}
diff --git a/tvix/store/src/lib.rs b/tvix/store/src/lib.rs
index 642d285990..8d7d45d028 100644
--- a/tvix/store/src/lib.rs
+++ b/tvix/store/src/lib.rs
@@ -4,7 +4,7 @@ pub mod store_path;
 
 pub mod dummy_blob_service;
 pub mod dummy_directory_service;
-pub mod dummy_path_info_service;
+pub mod sled_path_info_service;
 
 #[cfg(test)]
 mod tests;
diff --git a/tvix/store/src/main.rs b/tvix/store/src/main.rs
index 0ad1857db6..4fa09f28a2 100644
--- a/tvix/store/src/main.rs
+++ b/tvix/store/src/main.rs
@@ -36,7 +36,8 @@ async fn main() -> Result<(), Box<dyn std::error::Error>> {
 
     let blob_service = tvix_store::dummy_blob_service::DummyBlobService {};
     let directory_service = tvix_store::dummy_directory_service::DummyDirectoryService {};
-    let path_info_service = tvix_store::dummy_path_info_service::DummyPathInfoService {};
+    let path_info_service =
+        tvix_store::sled_path_info_service::SledPathInfoService::new("pathinfo.sled".into())?;
 
     let mut router = server
         .add_service(BlobServiceServer::new(blob_service))
diff --git a/tvix/store/src/sled_path_info_service.rs b/tvix/store/src/sled_path_info_service.rs
new file mode 100644
index 0000000000..3215fd0e47
--- /dev/null
+++ b/tvix/store/src/sled_path_info_service.rs
@@ -0,0 +1,89 @@
+use prost::Message;
+use std::path::PathBuf;
+
+use crate::proto::get_path_info_request::ByWhat;
+use crate::proto::path_info_service_server::PathInfoService;
+use crate::proto::CalculateNarResponse;
+use crate::proto::GetPathInfoRequest;
+use crate::proto::Node;
+use crate::proto::PathInfo;
+use crate::store_path::DIGEST_SIZE;
+use tonic::{Request, Response, Result, Status};
+use tracing::{instrument, warn};
+
+const NOT_IMPLEMENTED_MSG: &str = "not implemented";
+
+/// SledPathInfoService stores PathInfo in a [sled](https://github.com/spacejam/sled).
+///
+/// The PathInfo messages are stored as encoded protos, and keyed by their output hash,
+/// as that's currently the only request type available.
+pub struct SledPathInfoService {
+    db: sled::Db,
+}
+
+impl SledPathInfoService {
+    pub fn new(p: PathBuf) -> Result<Self, anyhow::Error> {
+        let config = sled::Config::default().use_compression(true).path(p);
+        let db = config.open()?;
+
+        Ok(Self { db })
+    }
+}
+
+#[tonic::async_trait]
+impl PathInfoService for SledPathInfoService {
+    #[instrument(skip(self))]
+    async fn get(&self, request: Request<GetPathInfoRequest>) -> Result<Response<PathInfo>> {
+        match request.into_inner().by_what {
+            None => Err(Status::unimplemented("by_what needs to be specified")),
+            Some(ByWhat::ByOutputHash(digest)) => {
+                if digest.len() != DIGEST_SIZE {
+                    return Err(Status::invalid_argument("invalid digest length"));
+                }
+
+                match self.db.get(digest) {
+                    Ok(None) => Err(Status::not_found("PathInfo not found")),
+                    Ok(Some(data)) => match PathInfo::decode(&*data) {
+                        Ok(path_info) => Ok(Response::new(path_info)),
+                        Err(e) => {
+                            warn!("failed to decode stored PathInfo: {}", e);
+                            Err(Status::internal("failed to decode stored PathInfo"))
+                        }
+                    },
+                    Err(e) => {
+                        warn!("failed to retrieve PathInfo: {}", e);
+                        Err(Status::internal("error during PathInfo lookup"))
+                    }
+                }
+            }
+        }
+    }
+
+    #[instrument(skip(self))]
+    async fn put(&self, request: Request<PathInfo>) -> Result<Response<PathInfo>> {
+        let path_info = request.into_inner();
+
+        // Call validate on the received PathInfo message.
+        match path_info.validate() {
+            Err(e) => Err(Status::invalid_argument(e.to_string())),
+            // In case the PathInfo is valid, and we were able to extract a NixPath, store it in the database.
+            // This overwrites existing PathInfo objects.
+            Ok(nix_path) => match self.db.insert(nix_path.digest, path_info.encode_to_vec()) {
+                Ok(_) => Ok(Response::new(path_info)),
+                Err(e) => {
+                    warn!("failed to insert PathInfo: {}", e);
+                    Err(Status::internal("failed to insert PathInfo"))
+                }
+            },
+        }
+    }
+
+    #[instrument(skip(self))]
+    async fn calculate_nar(
+        &self,
+        _request: Request<Node>,
+    ) -> Result<Response<CalculateNarResponse>> {
+        warn!(NOT_IMPLEMENTED_MSG);
+        Err(Status::unimplemented(NOT_IMPLEMENTED_MSG))
+    }
+}
diff --git a/tvix/store/src/tests/mod.rs b/tvix/store/src/tests/mod.rs
index b5fb0648e6..3f5d044d65 100644
--- a/tvix/store/src/tests/mod.rs
+++ b/tvix/store/src/tests/mod.rs
@@ -1,6 +1,7 @@
 use crate::proto::{Directory, DirectoryNode, FileNode, SymlinkNode, ValidateDirectoryError};
 use lazy_static::lazy_static;
 
+mod path_info_service;
 mod pathinfo;
 
 lazy_static! {
diff --git a/tvix/store/src/tests/path_info_service.rs b/tvix/store/src/tests/path_info_service.rs
new file mode 100644
index 0000000000..dca61fe12a
--- /dev/null
+++ b/tvix/store/src/tests/path_info_service.rs
@@ -0,0 +1,74 @@
+use tempfile::TempDir;
+
+use crate::proto::path_info_service_server::PathInfoService;
+use crate::proto::GetPathInfoRequest;
+use crate::proto::{get_path_info_request, PathInfo};
+use crate::sled_path_info_service::SledPathInfoService;
+
+use lazy_static::lazy_static;
+
+lazy_static! {
+    static ref DUMMY_OUTPUT_HASH: Vec<u8> = vec![
+        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+        0x00, 0x00, 0x00, 0x00, 0x00
+    ];
+}
+
+/// Trying to get a non-existent PathInfo should return a not found error.
+#[tokio::test]
+async fn not_found() -> anyhow::Result<()> {
+    let service = SledPathInfoService::new(TempDir::new()?.path().to_path_buf())?;
+
+    let resp = service
+        .get(tonic::Request::new(GetPathInfoRequest {
+            by_what: Some(get_path_info_request::ByWhat::ByOutputHash(
+                DUMMY_OUTPUT_HASH.to_vec(),
+            )),
+        }))
+        .await;
+
+    match resp {
+        Err(status) => {
+            assert_eq!(status.code(), tonic::Code::NotFound);
+        }
+        Ok(_) => panic!("must fail"),
+    };
+
+    Ok(())
+}
+
+/// Put a PathInfo into the store, get it back.
+#[tokio::test]
+async fn put_get() -> anyhow::Result<()> {
+    let service = SledPathInfoService::new(TempDir::new()?.path().to_path_buf())?;
+
+    let path_info = PathInfo {
+        node: Some(crate::proto::Node {
+            node: Some(crate::proto::node::Node::Symlink(
+                crate::proto::SymlinkNode {
+                    name: "00000000000000000000000000000000-foo".to_string(),
+                    target: "doesntmatter".to_string(),
+                },
+            )),
+        }),
+        ..Default::default()
+    };
+
+    let resp = service.put(tonic::Request::new(path_info.clone())).await;
+
+    assert!(resp.is_ok());
+    assert_eq!(resp.expect("must succeed").into_inner(), path_info);
+
+    let resp = service
+        .get(tonic::Request::new(GetPathInfoRequest {
+            by_what: Some(get_path_info_request::ByWhat::ByOutputHash(
+                DUMMY_OUTPUT_HASH.to_vec(),
+            )),
+        }))
+        .await;
+
+    assert!(resp.is_ok());
+    assert_eq!(resp.expect("must succeed").into_inner(), path_info);
+
+    Ok(())
+}