about summary refs log tree commit diff
path: root/src/libstore
diff options
context:
space:
mode:
Diffstat (limited to 'src/libstore')
-rw-r--r--src/libstore/binary-cache-store.cc180
-rw-r--r--src/libstore/binary-cache-store.hh50
-rw-r--r--src/libstore/build.cc429
-rw-r--r--src/libstore/builtins.cc2
-rw-r--r--src/libstore/derivations.cc2
-rw-r--r--src/libstore/download.cc4
-rw-r--r--src/libstore/gc.cc10
-rw-r--r--src/libstore/globals.cc15
-rw-r--r--src/libstore/globals.hh30
-rw-r--r--src/libstore/http-binary-cache-store.cc27
-rw-r--r--src/libstore/local-binary-cache-store.cc49
-rw-r--r--src/libstore/local-store.cc330
-rw-r--r--src/libstore/local-store.hh39
-rw-r--r--src/libstore/local.mk2
-rw-r--r--src/libstore/misc.cc17
-rw-r--r--src/libstore/nar-info-disk-cache.cc224
-rw-r--r--src/libstore/nar-info-disk-cache.hh29
-rw-r--r--src/libstore/nar-info.cc20
-rw-r--r--src/libstore/nar-info.hh4
-rw-r--r--src/libstore/optimise-store.cc2
-rw-r--r--src/libstore/remote-store.cc92
-rw-r--r--src/libstore/remote-store.hh12
-rw-r--r--src/libstore/s3-binary-cache-store.cc253
-rw-r--r--src/libstore/s3-binary-cache-store.hh34
-rw-r--r--src/libstore/sqlite.cc5
-rw-r--r--src/libstore/sqlite.hh1
-rw-r--r--src/libstore/store-api.cc181
-rw-r--r--src/libstore/store-api.hh89
-rw-r--r--src/libstore/worker-protocol.hh8
29 files changed, 1229 insertions, 911 deletions
diff --git a/src/libstore/binary-cache-store.cc b/src/libstore/binary-cache-store.cc
index 7016eedfa701..411d10130a31 100644
--- a/src/libstore/binary-cache-store.cc
+++ b/src/libstore/binary-cache-store.cc
@@ -8,20 +8,20 @@
 #include "sync.hh"
 #include "worker-protocol.hh"
 #include "nar-accessor.hh"
+#include "nar-info-disk-cache.hh"
 
 #include <chrono>
 
 namespace nix {
 
 BinaryCacheStore::BinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile)
+    const StoreParams & params)
     : localStore(localStore)
+    , compression(get(params, "compression", "xz"))
 {
-    if (secretKeyFile != "") {
+    auto secretKeyFile = get(params, "secret-key", "");
+    if (secretKeyFile != "")
         secretKey = std::unique_ptr<SecretKey>(new SecretKey(readFile(secretKeyFile)));
-        publicKeys = std::unique_ptr<PublicKeys>(new PublicKeys);
-        publicKeys->emplace(secretKey->name, secretKey->toPublicKey());
-    }
 
     StringSink sink;
     sink << narVersionMagic1;
@@ -40,57 +40,65 @@ void BinaryCacheStore::notImpl()
     throw Error("operation not implemented for binary cache stores");
 }
 
-const BinaryCacheStore::Stats & BinaryCacheStore::getStats()
-{
-    return stats;
-}
-
 Path BinaryCacheStore::narInfoFileFor(const Path & storePath)
 {
     assertStorePath(storePath);
     return storePathToHash(storePath) + ".narinfo";
 }
 
-void BinaryCacheStore::addToCache(const ValidPathInfo & info,
-    const string & nar)
+void BinaryCacheStore::addToCache(const ValidPathInfo & info, ref<std::string> nar)
 {
+    /* Verify that all references are valid. This may do some .narinfo
+       reads, but typically they'll already be cached. */
+    for (auto & ref : info.references)
+        try {
+            if (ref != info.path)
+                queryPathInfo(ref);
+        } catch (InvalidPath &) {
+            throw Error(format("cannot add ‘%s’ to the binary cache because the reference ‘%s’ is not valid")
+                % info.path % ref);
+        }
+
     auto narInfoFile = narInfoFileFor(info.path);
     if (fileExists(narInfoFile)) return;
 
-    assert(nar.compare(0, narMagic.size(), narMagic) == 0);
+    assert(nar->compare(0, narMagic.size(), narMagic) == 0);
 
     auto narInfo = make_ref<NarInfo>(info);
 
-    narInfo->narSize = nar.size();
-    narInfo->narHash = hashString(htSHA256, nar);
+    narInfo->narSize = nar->size();
+    narInfo->narHash = hashString(htSHA256, *nar);
 
-    if (info.narHash.type != htUnknown && info.narHash != narInfo->narHash)
+    if (info.narHash && info.narHash != narInfo->narHash)
         throw Error(format("refusing to copy corrupted path ‘%1%’ to binary cache") % info.path);
 
     /* Compress the NAR. */
-    narInfo->compression = "xz";
+    narInfo->compression = compression;
     auto now1 = std::chrono::steady_clock::now();
-    string narXz = compressXZ(nar);
+    auto narCompressed = compress(compression, nar);
     auto now2 = std::chrono::steady_clock::now();
-    narInfo->fileHash = hashString(htSHA256, narXz);
-    narInfo->fileSize = narXz.size();
+    narInfo->fileHash = hashString(htSHA256, *narCompressed);
+    narInfo->fileSize = narCompressed->size();
 
     auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1).count();
     printMsg(lvlTalkative, format("copying path ‘%1%’ (%2% bytes, compressed %3$.1f%% in %4% ms) to binary cache")
         % narInfo->path % narInfo->narSize
-        % ((1.0 - (double) narXz.size() / nar.size()) * 100.0)
+        % ((1.0 - (double) narCompressed->size() / nar->size()) * 100.0)
         % duration);
 
     /* Atomically write the NAR file. */
-    narInfo->url = "nar/" + printHash32(narInfo->fileHash) + ".nar.xz";
+    narInfo->url = "nar/" + printHash32(narInfo->fileHash) + ".nar"
+        + (compression == "xz" ? ".xz" :
+           compression == "bzip2" ? ".bz2" :
+           "");
     if (!fileExists(narInfo->url)) {
         stats.narWrite++;
-        upsertFile(narInfo->url, narXz);
+        upsertFile(narInfo->url, *narCompressed);
     } else
         stats.narWriteAverted++;
 
-    stats.narWriteBytes += nar.size();
-    stats.narWriteCompressedBytes += narXz.size();
+    stats.narWriteBytes += nar->size();
+    stats.narWriteCompressedBytes += narCompressed->size();
     stats.narWriteCompressionTimeMs += duration;
 
     /* Atomically write the NAR info file.*/
@@ -98,69 +106,21 @@ void BinaryCacheStore::addToCache(const ValidPathInfo & info,
 
     upsertFile(narInfoFile, narInfo->to_string());
 
-    {
-        auto state_(state.lock());
-        state_->narInfoCache.upsert(narInfo->path, narInfo);
-        stats.narInfoCacheSize = state_->narInfoCache.size();
-    }
+    auto hashPart = storePathToHash(narInfo->path);
 
-    stats.narInfoWrite++;
-}
-
-NarInfo BinaryCacheStore::readNarInfo(const Path & storePath)
-{
     {
         auto state_(state.lock());
-        auto res = state_->narInfoCache.get(storePath);
-        if (res) {
-            stats.narInfoReadAverted++;
-            if (!*res)
-                throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
-            return **res;
-        }
-    }
-
-    auto narInfoFile = narInfoFileFor(storePath);
-    auto data = getFile(narInfoFile);
-    if (!data) {
-        stats.narInfoMissing++;
-        auto state_(state.lock());
-        state_->narInfoCache.upsert(storePath, 0);
-        stats.narInfoCacheSize = state_->narInfoCache.size();
-        throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
-    }
-
-    auto narInfo = make_ref<NarInfo>(*data, narInfoFile);
-    if (narInfo->path != storePath)
-        throw Error(format("NAR info file for store path ‘%1%’ does not match ‘%2%’") % narInfo->path % storePath);
-
-    stats.narInfoRead++;
-
-    if (publicKeys) {
-        if (!narInfo->checkSignatures(*publicKeys))
-            throw Error(format("no good signature on NAR info file ‘%1%’") % narInfoFile);
+        state_->pathInfoCache.upsert(hashPart, std::shared_ptr<NarInfo>(narInfo));
     }
 
-    {
-        auto state_(state.lock());
-        state_->narInfoCache.upsert(storePath, narInfo);
-        stats.narInfoCacheSize = state_->narInfoCache.size();
-    }
+    if (diskCache)
+        diskCache->upsertNarInfo(getUri(), hashPart, std::shared_ptr<NarInfo>(narInfo));
 
-    return *narInfo;
+    stats.narInfoWrite++;
 }
 
-bool BinaryCacheStore::isValidPath(const Path & storePath)
+bool BinaryCacheStore::isValidPathUncached(const Path & storePath)
 {
-    {
-        auto state_(state.lock());
-        auto res = state_->narInfoCache.get(storePath);
-        if (res) {
-            stats.narInfoReadAverted++;
-            return *res != 0;
-        }
-    }
-
     // FIXME: this only checks whether a .narinfo with a matching hash
     // part exists. So ‘f4kb...-foo’ matches ‘f4kb...-bar’, even
     // though they shouldn't. Not easily fixed.
@@ -169,23 +129,23 @@ bool BinaryCacheStore::isValidPath(const Path & storePath)
 
 void BinaryCacheStore::narFromPath(const Path & storePath, Sink & sink)
 {
-    auto res = readNarInfo(storePath);
+    auto info = queryPathInfo(storePath).cast<const NarInfo>();
 
-    auto nar = getFile(res.url);
+    auto nar = getFile(info->url);
 
-    if (!nar) throw Error(format("file ‘%s’ missing from binary cache") % res.url);
+    if (!nar) throw Error(format("file ‘%s’ missing from binary cache") % info->url);
 
     stats.narRead++;
     stats.narReadCompressedBytes += nar->size();
 
     /* Decompress the NAR. FIXME: would be nice to have the remote
        side do this. */
-    if (res.compression == "none")
-        ;
-    else if (res.compression == "xz")
-        nar = decompressXZ(*nar);
-    else
-        throw Error(format("unknown NAR compression type ‘%1%’") % nar);
+    try {
+        nar = decompress(info->compression, ref<std::string>(nar));
+    } catch (UnknownCompressionMethod &) {
+        throw Error(format("binary cache path ‘%s’ uses unknown compression method ‘%s’")
+            % storePath % info->compression);
+    }
 
     stats.narReadBytes += nar->size();
 
@@ -200,13 +160,13 @@ void BinaryCacheStore::exportPath(const Path & storePath, bool sign, Sink & sink
 {
     assert(!sign);
 
-    auto res = readNarInfo(storePath);
+    auto res = queryPathInfo(storePath);
 
     narFromPath(storePath, sink);
 
     // FIXME: check integrity of NAR.
 
-    sink << exportMagic << storePath << res.references << res.deriver << 0;
+    sink << exportMagic << storePath << res->references << res->deriver << 0;
 }
 
 Paths BinaryCacheStore::importPaths(bool requireSignature, Source & source,
@@ -244,9 +204,17 @@ struct NopSink : ParseSink
 {
 };
 
-ValidPathInfo BinaryCacheStore::queryPathInfo(const Path & storePath)
+std::shared_ptr<ValidPathInfo> BinaryCacheStore::queryPathInfoUncached(const Path & storePath)
 {
-    return ValidPathInfo(readNarInfo(storePath));
+    auto narInfoFile = narInfoFileFor(storePath);
+    auto data = getFile(narInfoFile);
+    if (!data) return 0;
+
+    auto narInfo = make_ref<NarInfo>(*data, narInfoFile);
+
+    stats.narInfoRead++;
+
+    return std::shared_ptr<NarInfo>(narInfo);
 }
 
 void BinaryCacheStore::querySubstitutablePathInfos(const PathSet & paths,
@@ -257,16 +225,16 @@ void BinaryCacheStore::querySubstitutablePathInfos(const PathSet & paths,
     if (!localStore) return;
 
     for (auto & storePath : paths) {
-        if (!localStore->isValidPath(storePath)) {
+        try {
+            auto info = localStore->queryPathInfo(storePath);
+            SubstitutablePathInfo sub;
+            sub.references = info->references;
+            sub.downloadSize = 0;
+            sub.narSize = info->narSize;
+            infos.emplace(storePath, sub);
+        } catch (InvalidPath &) {
             left.insert(storePath);
-            continue;
         }
-        ValidPathInfo info = localStore->queryPathInfo(storePath);
-        SubstitutablePathInfo sub;
-        sub.references = info.references;
-        sub.downloadSize = 0;
-        sub.narSize = info.narSize;
-        infos.emplace(storePath, sub);
     }
 
     if (settings.useSubstitutes)
@@ -296,7 +264,7 @@ Path BinaryCacheStore::addToStore(const string & name, const Path & srcPath,
     info.path = makeFixedOutputPath(recursive, hashAlgo, h, name);
 
     if (repair || !isValidPath(info.path))
-        addToCache(info, *sink.s);
+        addToCache(info, sink.s);
 
     return info.path;
 }
@@ -311,7 +279,7 @@ Path BinaryCacheStore::addTextToStore(const string & name, const string & s,
     if (repair || !isValidPath(info.path)) {
         StringSink sink;
         dumpString(s, sink);
-        addToCache(info, *sink.s);
+        addToCache(info, sink.s);
     }
 
     return info.path;
@@ -332,16 +300,16 @@ void BinaryCacheStore::buildPaths(const PathSet & paths, BuildMode buildMode)
         if (!localStore->isValidPath(storePath))
             localStore->ensurePath(storePath);
 
-        ValidPathInfo info = localStore->queryPathInfo(storePath);
+        auto info = localStore->queryPathInfo(storePath);
 
-        for (auto & ref : info.references)
+        for (auto & ref : info->references)
             if (ref != storePath)
                 ensurePath(ref);
 
         StringSink sink;
         dumpPath(storePath, sink);
 
-        addToCache(info, *sink.s);
+        addToCache(*info, sink.s);
     }
 }
 
@@ -439,7 +407,7 @@ Path BinaryCacheStore::importPath(Source & source, std::shared_ptr<FSAccessor> a
     bool haveSignature = readInt(source) == 1;
     assert(!haveSignature);
 
-    addToCache(info, *tee.data);
+    addToCache(info, tee.data);
 
     auto accessor_ = std::dynamic_pointer_cast<BinaryCacheStoreAccessor>(accessor);
     if (accessor_)
diff --git a/src/libstore/binary-cache-store.hh b/src/libstore/binary-cache-store.hh
index 95e5d68b70ae..46a38a1e0fc3 100644
--- a/src/libstore/binary-cache-store.hh
+++ b/src/libstore/binary-cache-store.hh
@@ -3,8 +3,6 @@
 #include "crypto.hh"
 #include "store-api.hh"
 
-#include "lru-cache.hh"
-#include "sync.hh"
 #include "pool.hh"
 
 #include <atomic>
@@ -18,20 +16,15 @@ class BinaryCacheStore : public Store
 private:
 
     std::unique_ptr<SecretKey> secretKey;
-    std::unique_ptr<PublicKeys> publicKeys;
 
     std::shared_ptr<Store> localStore;
 
-    struct State
-    {
-        LRUCache<Path, std::shared_ptr<NarInfo>> narInfoCache{64 * 1024};
-    };
-
-    Sync<State> state;
+    std::string compression;
 
 protected:
 
-    BinaryCacheStore(std::shared_ptr<Store> localStore, const Path & secretKeyFile);
+    BinaryCacheStore(std::shared_ptr<Store> localStore,
+        const StoreParams & params);
 
     [[noreturn]] void notImpl();
 
@@ -47,42 +40,17 @@ public:
 
     virtual void init();
 
-    struct Stats
-    {
-        std::atomic<uint64_t> narInfoRead{0};
-        std::atomic<uint64_t> narInfoReadAverted{0};
-        std::atomic<uint64_t> narInfoMissing{0};
-        std::atomic<uint64_t> narInfoWrite{0};
-        std::atomic<uint64_t> narInfoCacheSize{0};
-        std::atomic<uint64_t> narRead{0};
-        std::atomic<uint64_t> narReadBytes{0};
-        std::atomic<uint64_t> narReadCompressedBytes{0};
-        std::atomic<uint64_t> narWrite{0};
-        std::atomic<uint64_t> narWriteAverted{0};
-        std::atomic<uint64_t> narWriteBytes{0};
-        std::atomic<uint64_t> narWriteCompressedBytes{0};
-        std::atomic<uint64_t> narWriteCompressionTimeMs{0};
-    };
-
-    const Stats & getStats();
-
 private:
 
-    Stats stats;
-
     std::string narMagic;
 
     std::string narInfoFileFor(const Path & storePath);
 
-    void addToCache(const ValidPathInfo & info, const string & nar);
-
-protected:
-
-    NarInfo readNarInfo(const Path & storePath);
+    void addToCache(const ValidPathInfo & info, ref<std::string> nar);
 
 public:
 
-    bool isValidPath(const Path & path) override;
+    bool isValidPathUncached(const Path & path) override;
 
     PathSet queryValidPaths(const PathSet & paths) override
     { notImpl(); }
@@ -90,18 +58,12 @@ public:
     PathSet queryAllValidPaths() override
     { notImpl(); }
 
-    ValidPathInfo queryPathInfo(const Path & path) override;
-
-    Hash queryPathHash(const Path & path) override
-    { notImpl(); }
+    std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) override;
 
     void queryReferrers(const Path & path,
         PathSet & referrers) override
     { notImpl(); }
 
-    Path queryDeriver(const Path & path) override
-    { return ""; }
-
     PathSet queryValidDerivers(const Path & path) override
     { return {}; }
 
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index ba3f3a371d8c..65df2eea59a0 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -8,11 +8,14 @@
 #include "archive.hh"
 #include "affinity.hh"
 #include "builtins.hh"
+#include "finally.hh"
 
 #include <algorithm>
 #include <iostream>
 #include <map>
 #include <sstream>
+#include <thread>
+#include <future>
 
 #include <limits.h>
 #include <time.h>
@@ -199,8 +202,6 @@ struct Child
     time_t timeStarted;
 };
 
-typedef map<pid_t, Child> Children;
-
 
 /* The worker class. */
 class Worker
@@ -220,7 +221,7 @@ private:
     WeakGoals wantingToBuild;
 
     /* Child processes currently running. */
-    Children children;
+    std::list<Child> children;
 
     /* Number of build slots occupied.  This includes local builds and
        substitutions but not remote builds via the build hook. */
@@ -278,14 +279,14 @@ public:
 
     /* Registers a running child process.  `inBuildSlot' means that
        the process counts towards the jobs limit. */
-    void childStarted(GoalPtr goal, pid_t pid,
-        const set<int> & fds, bool inBuildSlot, bool respectTimeouts);
+    void childStarted(GoalPtr goal, const set<int> & fds,
+        bool inBuildSlot, bool respectTimeouts);
 
     /* Unregisters a running child process.  `wakeSleepers' should be
        false if there is no sense in waking up goals that are sleeping
        because they can't run yet (e.g., there is no free build slot,
        or the hook would still say `postpone'). */
-    void childTerminated(pid_t pid, bool wakeSleepers = true);
+    void childTerminated(GoalPtr goal, bool wakeSleepers = true);
 
     /* Put `goal' to sleep until a build slot becomes available (which
        might be right away). */
@@ -633,7 +634,6 @@ HookInstance::HookInstance()
             baseNameOf(buildHook),
             settings.thisSystem,
             (format("%1%") % settings.maxSilentTime).str(),
-            (format("%1%") % settings.printBuildTrace).str(),
             (format("%1%") % settings.buildTimeout).str()
         };
 
@@ -748,6 +748,12 @@ private:
     /* Number of bytes received from the builder's stdout/stderr. */
     unsigned long logSize;
 
+    /* The most recent log lines. */
+    std::list<std::string> logTail;
+
+    std::string currentLogLine;
+    size_t currentLogLinePos = 0; // to handle carriage return
+
     /* Pipe for the builder's standard output/error. */
     Pipe builderOut;
 
@@ -873,6 +879,7 @@ private:
     /* Callback used by the worker to write to the log. */
     void handleChildOutput(int fd, const string & data) override;
     void handleEOF(int fd) override;
+    void flushLine();
 
     /* Return the set of (in)valid paths. */
     PathSet checkPathValidity(bool returnValid, bool checkHash);
@@ -936,7 +943,7 @@ DerivationGoal::~DerivationGoal()
 void DerivationGoal::killChild()
 {
     if (pid != -1) {
-        worker.childTerminated(pid);
+        worker.childTerminated(shared_from_this());
 
         if (buildUser.enabled()) {
             /* If we're using a build user, then there is a tricky
@@ -960,8 +967,6 @@ void DerivationGoal::killChild()
 
 void DerivationGoal::timedOut()
 {
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ build-failed %1% - timeout") % drvPath);
     killChild();
     done(BuildResult::TimedOut);
 }
@@ -1362,9 +1367,6 @@ void DerivationGoal::tryToBuild()
         printMsg(lvlError, e.msg());
         outputLocks.unlock();
         buildUser.release();
-        if (settings.printBuildTrace)
-            printMsg(lvlError, format("@ build-failed %1% - %2% %3%")
-                % drvPath % 0 % e.msg());
         worker.permanentFailure = true;
         done(BuildResult::InputRejected, e.msg());
         return;
@@ -1402,22 +1404,14 @@ void DerivationGoal::buildDone()
        to have terminated.  In fact, the builder could also have
        simply have closed its end of the pipe --- just don't do that
        :-) */
-    int status;
-    pid_t savedPid;
-    if (hook) {
-        savedPid = hook->pid;
-        status = hook->pid.wait(true);
-    } else {
-        /* !!! this could block! security problem! solution: kill the
-           child */
-        savedPid = pid;
-        status = pid.wait(true);
-    }
+    /* !!! this could block! security problem! solution: kill the
+       child */
+    int status = hook ? hook->pid.wait(true) : pid.wait(true);
 
     debug(format("builder process for ‘%1%’ finished") % drvPath);
 
     /* So the child is gone now. */
-    worker.childTerminated(savedPid);
+    worker.childTerminated(shared_from_this());
 
     /* Close the read side of the logger pipe. */
     if (hook) {
@@ -1468,11 +1462,19 @@ void DerivationGoal::buildDone()
                     if (pathExists(chrootRootDir + i))
                         rename((chrootRootDir + i).c_str(), i.c_str());
 
+            std::string msg = (format("builder for ‘%1%’ %2%")
+                % drvPath % statusToString(status)).str();
+
+            if (!settings.verboseBuild && !logTail.empty()) {
+                msg += (format("; last %d log lines:") % logTail.size()).str();
+                for (auto & line : logTail)
+                    msg += "\n  " + line;
+            }
+
             if (diskFull)
-                printMsg(lvlError, "note: build failure may have been caused by lack of free disk space");
+                msg += "\nnote: build failure may have been caused by lack of free disk space";
 
-            throw BuildError(format("builder for ‘%1%’ %2%")
-                % drvPath % statusToString(status));
+            throw BuildError(msg);
         }
 
         /* Compute the FS closure of the outputs and register them as
@@ -1517,23 +1519,13 @@ void DerivationGoal::buildDone()
 
         BuildResult::Status st = BuildResult::MiscFailure;
 
-        if (hook && WIFEXITED(status) && WEXITSTATUS(status) == 101) {
-            if (settings.printBuildTrace)
-                printMsg(lvlError, format("@ build-failed %1% - timeout") % drvPath);
+        if (hook && WIFEXITED(status) && WEXITSTATUS(status) == 101)
             st = BuildResult::TimedOut;
-        }
 
         else if (hook && (!WIFEXITED(status) || WEXITSTATUS(status) != 100)) {
-            if (settings.printBuildTrace)
-                printMsg(lvlError, format("@ hook-failed %1% - %2% %3%")
-                    % drvPath % status % e.msg());
         }
 
         else {
-            if (settings.printBuildTrace)
-                printMsg(lvlError, format("@ build-failed %1% - %2% %3%")
-                    % drvPath % 1 % e.msg());
-
             st =
                 dynamic_cast<NotDeterministic*>(&e) ? BuildResult::NotDeterministic :
                 statusOk(status) ? BuildResult::OutputRejected :
@@ -1548,9 +1540,6 @@ void DerivationGoal::buildDone()
     /* Release the build user, if applicable. */
     buildUser.release();
 
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ build-succeeded %1% -") % drvPath);
-
     done(BuildResult::Built);
 }
 
@@ -1625,11 +1614,7 @@ HookReply DerivationGoal::tryBuildHook()
     set<int> fds;
     fds.insert(hook->fromHook.readSide);
     fds.insert(hook->builderOut.readSide);
-    worker.childStarted(shared_from_this(), hook->pid, fds, false, false);
-
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ build-started %1% - %2% %3%")
-            % drvPath % drv->platform % logFile);
+    worker.childStarted(shared_from_this(), fds, false, false);
 
     return rpAccept;
 }
@@ -1657,12 +1642,10 @@ void DerivationGoal::startBuilder()
         nrRounds > 1 ? "building path(s) %1% (round %2%/%3%)" :
         "building path(s) %1%");
     f.exceptions(boost::io::all_error_bits ^ boost::io::too_many_args_bit);
-    startNest(nest, lvlInfo, f % showPaths(missingPaths) % curRound % nrRounds);
+    printMsg(lvlInfo, f % showPaths(missingPaths) % curRound % nrRounds);
 
     /* Right platform? */
     if (!drv->canBuildLocally()) {
-        if (settings.printBuildTrace)
-            printMsg(lvlError, format("@ unsupported-platform %1% %2%") % drvPath % drv->platform);
         throw Error(
             format("a ‘%1%’ is required to build ‘%3%’, but I am a ‘%2%’")
             % drv->platform % settings.thisSystem % drvPath);
@@ -2165,7 +2148,7 @@ void DerivationGoal::startBuilder()
     /* parent */
     pid.setSeparatePG(true);
     builderOut.writeSide.close();
-    worker.childStarted(shared_from_this(), pid,
+    worker.childStarted(shared_from_this(),
         singleton<set<int> >(builderOut.readSide), true, true);
 
     /* Check if setting up the build environment failed. */
@@ -2177,11 +2160,6 @@ void DerivationGoal::startBuilder()
         }
         printMsg(lvlDebug, msg);
     }
-
-    if (settings.printBuildTrace) {
-        printMsg(lvlError, format("@ build-started %1% - %2% %3%")
-            % drvPath % drv->platform % logFile);
-    }
 }
 
 
@@ -2192,8 +2170,6 @@ void DerivationGoal::runChild()
 
     try { /* child */
 
-        logType = ltFlat;
-
         commonChildInit(builderOut);
 
 #if __linux__
@@ -2535,7 +2511,6 @@ void DerivationGoal::runChild()
         /* Execute the program.  This should not return. */
         if (drv->isBuiltin()) {
             try {
-                logType = ltFlat;
                 if (drv->builder == "builtin:fetchurl")
                     builtinFetchurl(*drv);
                 else
@@ -2667,8 +2642,7 @@ void DerivationGoal::registerOutputs()
             rewritten = true;
         }
 
-        startNest(nest, lvlTalkative,
-            format("scanning for references inside ‘%1%’") % path);
+        Activity act(*logger, lvlTalkative, format("scanning for references inside ‘%1%’") % path);
 
         /* Check that fixed-output derivations produced the right
            outputs (i.e., the content hash should match the specified
@@ -2724,7 +2698,7 @@ void DerivationGoal::registerOutputs()
 
         if (buildMode == bmCheck) {
             if (!worker.store.isValidPath(path)) continue;
-            ValidPathInfo info = worker.store.queryPathInfo(path);
+            auto info = *worker.store.queryPathInfo(path);
             if (hash.first != info.narHash) {
                 if (settings.keepFailed) {
                     Path dst = path + checkSuffix;
@@ -2775,14 +2749,25 @@ void DerivationGoal::registerOutputs()
             } else
                 used = references;
 
+            PathSet badPaths;
+
             for (auto & i : used)
                 if (allowed) {
                     if (spec.find(i) == spec.end())
-                        throw BuildError(format("output ‘%1%’ is not allowed to refer to path ‘%2%’") % actualPath % i);
+                        badPaths.insert(i);
                 } else {
                     if (spec.find(i) != spec.end())
-                        throw BuildError(format("output ‘%1%’ is not allowed to refer to path ‘%2%’") % actualPath % i);
+                        badPaths.insert(i);
                 }
+
+            if (!badPaths.empty()) {
+                string badPathsStr;
+                for (auto & i : badPaths) {
+                    badPathsStr += "\n\t";
+                    badPathsStr += i;
+                }
+                throw BuildError(format("output ‘%1%’ is not allowed to refer to the following paths:%2%") % actualPath % badPathsStr);
+            }
         };
 
         checkRefs("allowedReferences", true, false);
@@ -2943,8 +2928,18 @@ void DerivationGoal::handleChildOutput(int fd, const string & data)
             done(BuildResult::LogLimitExceeded);
             return;
         }
-        if (verbosity >= settings.buildVerbosity)
-            writeToStderr(filterANSIEscapes(data, true));
+
+        for (auto c : data)
+            if (c == '\r')
+                currentLogLinePos = 0;
+            else if (c == '\n')
+                flushLine();
+            else {
+                if (currentLogLinePos >= currentLogLine.size())
+                    currentLogLine.resize(currentLogLinePos + 1);
+                currentLogLine[currentLogLinePos++] = c;
+            }
+
         if (bzLogFile) {
             int err;
             BZ2_bzWrite(&err, bzLogFile, (unsigned char *) data.data(), data.size());
@@ -2954,16 +2949,30 @@ void DerivationGoal::handleChildOutput(int fd, const string & data)
     }
 
     if (hook && fd == hook->fromHook.readSide)
-        writeToStderr(data);
+        printMsg(lvlError, data); // FIXME?
 }
 
 
 void DerivationGoal::handleEOF(int fd)
 {
+    if (!currentLogLine.empty()) flushLine();
     worker.wakeUp(shared_from_this());
 }
 
 
+void DerivationGoal::flushLine()
+{
+    if (settings.verboseBuild)
+        printMsg(lvlInfo, filterANSIEscapes(currentLogLine, true));
+    else {
+        logTail.push_back(currentLogLine);
+        if (logTail.size() > settings.logLines) logTail.pop_front();
+    }
+    currentLogLine = "";
+    currentLogLinePos = 0;
+}
+
+
 PathSet DerivationGoal::checkPathValidity(bool returnValid, bool checkHash)
 {
     PathSet result;
@@ -3016,28 +3025,24 @@ private:
     Path storePath;
 
     /* The remaining substituters. */
-    Paths subs;
+    std::list<ref<Store>> subs;
 
     /* The current substituter. */
-    Path sub;
+    std::shared_ptr<Store> sub;
 
-    /* Whether any substituter can realise this path */
+    /* Whether any substituter can realise this path. */
     bool hasSubstitute;
 
     /* Path info returned by the substituter's query info operation. */
-    SubstitutablePathInfo info;
+    std::shared_ptr<const ValidPathInfo> info;
 
     /* Pipe for the substituter's standard output. */
     Pipe outPipe;
 
-    /* Pipe for the substituter's standard error. */
-    Pipe logPipe;
-
-    /* The process ID of the builder. */
-    Pid pid;
+    /* The substituter thread. */
+    std::thread thr;
 
-    /* Lock on the store path. */
-    std::shared_ptr<PathLocks> outputLock;
+    std::promise<void> promise;
 
     /* Whether to try to repair a valid path. */
     bool repair;
@@ -3053,7 +3058,7 @@ public:
     SubstitutionGoal(const Path & storePath, Worker & worker, bool repair = false);
     ~SubstitutionGoal();
 
-    void timedOut();
+    void timedOut() { abort(); };
 
     string key()
     {
@@ -3094,20 +3099,14 @@ SubstitutionGoal::SubstitutionGoal(const Path & storePath, Worker & worker, bool
 
 SubstitutionGoal::~SubstitutionGoal()
 {
-    if (pid != -1) worker.childTerminated(pid);
-}
-
-
-void SubstitutionGoal::timedOut()
-{
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ substituter-failed %1% timeout") % storePath);
-    if (pid != -1) {
-        pid_t savedPid = pid;
-        pid.kill();
-        worker.childTerminated(savedPid);
+    try {
+        if (thr.joinable()) {
+            thr.join();
+            worker.childTerminated(shared_from_this());
+        }
+    } catch (...) {
+        ignoreException();
     }
-    amDone(ecFailed);
 }
 
 
@@ -3132,7 +3131,7 @@ void SubstitutionGoal::init()
     if (settings.readOnlyMode)
         throw Error(format("cannot substitute path ‘%1%’ - no write access to the Nix store") % storePath);
 
-    subs = settings.substituters;
+    subs = getDefaultSubstituters();
 
     tryNext();
 }
@@ -3157,17 +3156,19 @@ void SubstitutionGoal::tryNext()
     sub = subs.front();
     subs.pop_front();
 
-    SubstitutablePathInfos infos;
-    PathSet dummy(singleton<PathSet>(storePath));
-    worker.store.querySubstitutablePathInfos(sub, dummy, infos);
-    SubstitutablePathInfos::iterator k = infos.find(storePath);
-    if (k == infos.end()) { tryNext(); return; }
-    info = k->second;
+    try {
+        // FIXME: make async
+        info = sub->queryPathInfo(storePath);
+    } catch (InvalidPath &) {
+        tryNext();
+        return;
+    }
+
     hasSubstitute = true;
 
     /* To maintain the closure invariant, we first have to realise the
        paths referenced by this one. */
-    for (auto & i : info.references)
+    for (auto & i : info->references)
         if (i != storePath) /* ignore self-references */
             addWaitee(worker.makeSubstitutionGoal(i));
 
@@ -3188,7 +3189,7 @@ void SubstitutionGoal::referencesValid()
         return;
     }
 
-    for (auto & i : info.references)
+    for (auto & i : info->references)
         if (i != storePath) /* ignore self-references */
             assert(worker.store.isValidPath(i));
 
@@ -3210,75 +3211,32 @@ void SubstitutionGoal::tryToRun()
         return;
     }
 
-    /* Maybe a derivation goal has already locked this path
-       (exceedingly unlikely, since it should have used a substitute
-       first, but let's be defensive). */
-    outputLock.reset(); // make sure this goal's lock is gone
-    if (pathIsLockedByMe(storePath)) {
-        debug(format("restarting substitution of ‘%1%’ because it's locked by another goal")
-            % storePath);
-        worker.waitForAnyGoal(shared_from_this());
-        return; /* restart in the tryToRun() state when another goal finishes */
-    }
-
-    /* Acquire a lock on the output path. */
-    outputLock = std::make_shared<PathLocks>();
-    if (!outputLock->lockPaths(singleton<PathSet>(storePath), "", false)) {
-        worker.waitForAWhile(shared_from_this());
-        return;
-    }
-
-    /* Check again whether the path is invalid. */
-    if (!repair && worker.store.isValidPath(storePath)) {
-        debug(format("store path ‘%1%’ has become valid") % storePath);
-        outputLock->setDeletion(true);
-        amDone(ecSuccess);
-        return;
-    }
-
     printMsg(lvlInfo, format("fetching path ‘%1%’...") % storePath);
 
     outPipe.create();
-    logPipe.create();
-
-    destPath = repair ? storePath + ".tmp" : storePath;
 
-    /* Remove the (stale) output path if it exists. */
-    deletePath(destPath);
+    promise = std::promise<void>();
 
-    worker.store.setSubstituterEnv();
+    thr = std::thread([this]() {
+        try {
+            /* Wake up the worker loop when we're done. */
+            Finally updateStats([this]() { outPipe.writeSide.close(); });
 
-    /* Fill in the arguments. */
-    Strings args;
-    args.push_back(baseNameOf(sub));
-    args.push_back("--substitute");
-    args.push_back(storePath);
-    args.push_back(destPath);
-
-    /* Fork the substitute program. */
-    pid = startProcess([&]() {
-
-        commonChildInit(logPipe);
-
-        if (dup2(outPipe.writeSide, STDOUT_FILENO) == -1)
-            throw SysError("cannot dup output pipe into stdout");
+            StringSink sink;
+            sub->exportPaths({storePath}, false, sink);
 
-        execv(sub.c_str(), stringsToCharPtrs(args).data());
+            StringSource source(*sink.s);
+            worker.store.importPaths(false, source, 0);
 
-        throw SysError(format("executing ‘%1%’") % sub);
+            promise.set_value();
+        } catch (...) {
+            promise.set_exception(std::current_exception());
+        }
     });
 
-    pid.setSeparatePG(true);
-    pid.setKillSignal(SIGTERM);
-    outPipe.writeSide.close();
-    logPipe.writeSide.close();
-    worker.childStarted(shared_from_this(),
-        pid, singleton<set<int> >(logPipe.readSide), true, true);
+    worker.childStarted(shared_from_this(), {outPipe.readSide}, true, false);
 
     state = &SubstitutionGoal::finished;
-
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ substituter-started %1% %2%") % storePath % sub);
 }
 
 
@@ -3286,110 +3244,40 @@ void SubstitutionGoal::finished()
 {
     trace("substitute finished");
 
-    /* Since we got an EOF on the logger pipe, the substitute is
-       presumed to have terminated.  */
-    pid_t savedPid = pid;
-    int status = pid.wait(true);
-
-    /* So the child is gone now. */
-    worker.childTerminated(savedPid);
+    thr.join();
+    worker.childTerminated(shared_from_this());
 
-    /* Close the read side of the logger pipe. */
-    logPipe.readSide.close();
-
-    /* Get the hash info from stdout. */
-    string dummy = readLine(outPipe.readSide);
-    string expectedHashStr = statusOk(status) ? readLine(outPipe.readSide) : "";
-    outPipe.readSide.close();
-
-    /* Check the exit status and the build result. */
-    HashResult hash;
     try {
-
-        if (!statusOk(status))
-            throw SubstError(format("fetching path ‘%1%’ %2%")
-                % storePath % statusToString(status));
-
-        if (!pathExists(destPath))
-            throw SubstError(format("substitute did not produce path ‘%1%’") % destPath);
-
-        hash = hashPath(htSHA256, destPath);
-
-        /* Verify the expected hash we got from the substituer. */
-        if (expectedHashStr != "") {
-            size_t n = expectedHashStr.find(':');
-            if (n == string::npos)
-                throw Error(format("bad hash from substituter: %1%") % expectedHashStr);
-            HashType hashType = parseHashType(string(expectedHashStr, 0, n));
-            if (hashType == htUnknown)
-                throw Error(format("unknown hash algorithm in ‘%1%’") % expectedHashStr);
-            Hash expectedHash = parseHash16or32(hashType, string(expectedHashStr, n + 1));
-            Hash actualHash = hashType == htSHA256 ? hash.first : hashPath(hashType, destPath).first;
-            if (expectedHash != actualHash)
-                throw SubstError(format("hash mismatch in downloaded path ‘%1%’: expected %2%, got %3%")
-                    % storePath % printHash(expectedHash) % printHash(actualHash));
-        }
-
-    } catch (SubstError & e) {
-
+        promise.get_future().get();
+    } catch (Error & e) {
         printMsg(lvlInfo, e.msg());
 
-        if (settings.printBuildTrace) {
-            printMsg(lvlError, format("@ substituter-failed %1% %2% %3%")
-                % storePath % status % e.msg());
-        }
-
         /* Try the next substitute. */
         state = &SubstitutionGoal::tryNext;
         worker.wakeUp(shared_from_this());
         return;
     }
 
-    if (repair) replaceValidPath(storePath, destPath);
-
-    canonicalisePathMetaData(storePath, -1);
-
-    worker.store.optimisePath(storePath); // FIXME: combine with hashPath()
-
-    ValidPathInfo info2;
-    info2.path = storePath;
-    info2.narHash = hash.first;
-    info2.narSize = hash.second;
-    info2.references = info.references;
-    info2.deriver = info.deriver;
-    worker.store.registerValidPath(info2);
-
-    outputLock->setDeletion(true);
-    outputLock.reset();
-
     worker.markContentsGood(storePath);
 
     printMsg(lvlChatty,
         format("substitution of path ‘%1%’ succeeded") % storePath);
 
-    if (settings.printBuildTrace)
-        printMsg(lvlError, format("@ substituter-succeeded %1%") % storePath);
-
     amDone(ecSuccess);
 }
 
 
 void SubstitutionGoal::handleChildOutput(int fd, const string & data)
 {
-    assert(fd == logPipe.readSide);
-    if (verbosity >= settings.buildVerbosity) writeToStderr(data);
-    /* Don't write substitution output to a log file for now.  We
-       probably should, though. */
 }
 
 
 void SubstitutionGoal::handleEOF(int fd)
 {
-    if (fd == logPipe.readSide) worker.wakeUp(shared_from_this());
+    if (fd == outPipe.readSide) worker.wakeUp(shared_from_this());
 }
 
 
-
 //////////////////////////////////////////////////////////////////////
 
 
@@ -3505,9 +3393,8 @@ unsigned Worker::getNrLocalBuilds()
 }
 
 
-void Worker::childStarted(GoalPtr goal,
-    pid_t pid, const set<int> & fds, bool inBuildSlot,
-    bool respectTimeouts)
+void Worker::childStarted(GoalPtr goal, const set<int> & fds,
+    bool inBuildSlot, bool respectTimeouts)
 {
     Child child;
     child.goal = goal;
@@ -3515,30 +3402,29 @@ void Worker::childStarted(GoalPtr goal,
     child.timeStarted = child.lastOutput = time(0);
     child.inBuildSlot = inBuildSlot;
     child.respectTimeouts = respectTimeouts;
-    children[pid] = child;
+    children.emplace_back(child);
     if (inBuildSlot) nrLocalBuilds++;
 }
 
 
-void Worker::childTerminated(pid_t pid, bool wakeSleepers)
+void Worker::childTerminated(GoalPtr goal, bool wakeSleepers)
 {
-    assert(pid != -1); /* common mistake */
-
-    Children::iterator i = children.find(pid);
+    auto i = std::find_if(children.begin(), children.end(),
+        [&](const Child & child) { return child.goal.lock() == goal; });
     assert(i != children.end());
 
-    if (i->second.inBuildSlot) {
+    if (i->inBuildSlot) {
         assert(nrLocalBuilds > 0);
         nrLocalBuilds--;
     }
 
-    children.erase(pid);
+    children.erase(i);
 
     if (wakeSleepers) {
 
         /* Wake up goals waiting for a build slot. */
-        for (auto & i : wantingToBuild) {
-            GoalPtr goal = i.lock();
+        for (auto & j : wantingToBuild) {
+            GoalPtr goal = j.lock();
             if (goal) wakeUp(goal);
         }
 
@@ -3575,7 +3461,7 @@ void Worker::run(const Goals & _topGoals)
 {
     for (auto & i : _topGoals) topGoals.insert(i);
 
-    startNest(nest, lvlDebug, format("entered goal loop"));
+    Activity act(*logger, lvlDebug, "entered goal loop");
 
     while (1) {
 
@@ -3640,11 +3526,11 @@ void Worker::waitForInput()
     assert(sizeof(time_t) >= sizeof(long));
     time_t nearest = LONG_MAX; // nearest deadline
     for (auto & i : children) {
-        if (!i.second.respectTimeouts) continue;
+        if (!i.respectTimeouts) continue;
         if (settings.maxSilentTime != 0)
-            nearest = std::min(nearest, i.second.lastOutput + settings.maxSilentTime);
+            nearest = std::min(nearest, i.lastOutput + settings.maxSilentTime);
         if (settings.buildTimeout != 0)
-            nearest = std::min(nearest, i.second.timeStarted + settings.buildTimeout);
+            nearest = std::min(nearest, i.timeStarted + settings.buildTimeout);
     }
     if (nearest != LONG_MAX) {
         timeout.tv_sec = std::max((time_t) 1, nearest - before);
@@ -3662,7 +3548,6 @@ void Worker::waitForInput()
         timeout.tv_sec = std::max((time_t) 1, (time_t) (lastWokenUp + settings.pollInterval - before));
     } else lastWokenUp = 0;
 
-    using namespace std;
     /* Use select() to wait for the input side of any logger pipe to
        become `available'.  Note that `available' (i.e., non-blocking)
        includes EOF. */
@@ -3670,7 +3555,7 @@ void Worker::waitForInput()
     FD_ZERO(&fds);
     int fdMax = 0;
     for (auto & i : children) {
-        for (auto & j : i.second.fds) {
+        for (auto & j : i.fds) {
             FD_SET(j, &fds);
             if (j >= fdMax) fdMax = j + 1;
         }
@@ -3684,22 +3569,16 @@ void Worker::waitForInput()
     time_t after = time(0);
 
     /* Process all available file descriptors. */
+    decltype(children)::iterator i;
+    for (auto j = children.begin(); j != children.end(); j = i) {
+        i = std::next(j);
 
-    /* Since goals may be canceled from inside the loop below (causing
-       them go be erased from the `children' map), we have to be
-       careful that we don't keep iterators alive across calls to
-       timedOut(). */
-    set<pid_t> pids;
-    for (auto & i : children) pids.insert(i.first);
-
-    for (auto & i : pids) {
         checkInterrupt();
-        Children::iterator j = children.find(i);
-        if (j == children.end()) continue; // child destroyed
-        GoalPtr goal = j->second.goal.lock();
+
+        GoalPtr goal = j->goal.lock();
         assert(goal);
 
-        set<int> fds2(j->second.fds);
+        set<int> fds2(j->fds);
         for (auto & k : fds2) {
             if (FD_ISSET(k, &fds)) {
                 unsigned char buffer[4096];
@@ -3711,12 +3590,12 @@ void Worker::waitForInput()
                 } else if (rd == 0) {
                     debug(format("%1%: got EOF") % goal->getName());
                     goal->handleEOF(k);
-                    j->second.fds.erase(k);
+                    j->fds.erase(k);
                 } else {
                     printMsg(lvlVomit, format("%1%: read %2% bytes")
                         % goal->getName() % rd);
                     string data((char *) buffer, rd);
-                    j->second.lastOutput = after;
+                    j->lastOutput = after;
                     goal->handleChildOutput(k, data);
                 }
             }
@@ -3724,8 +3603,8 @@ void Worker::waitForInput()
 
         if (goal->getExitCode() == Goal::ecBusy &&
             settings.maxSilentTime != 0 &&
-            j->second.respectTimeouts &&
-            after - j->second.lastOutput >= (time_t) settings.maxSilentTime)
+            j->respectTimeouts &&
+            after - j->lastOutput >= (time_t) settings.maxSilentTime)
         {
             printMsg(lvlError,
                 format("%1% timed out after %2% seconds of silence")
@@ -3735,8 +3614,8 @@ void Worker::waitForInput()
 
         else if (goal->getExitCode() == Goal::ecBusy &&
             settings.buildTimeout != 0 &&
-            j->second.respectTimeouts &&
-            after - j->second.timeStarted >= (time_t) settings.buildTimeout)
+            j->respectTimeouts &&
+            after - j->timeStarted >= (time_t) settings.buildTimeout)
         {
             printMsg(lvlError,
                 format("%1% timed out after %2% seconds")
@@ -3767,14 +3646,14 @@ bool Worker::pathContentsGood(const Path & path)
     std::map<Path, bool>::iterator i = pathContentsGoodCache.find(path);
     if (i != pathContentsGoodCache.end()) return i->second;
     printMsg(lvlInfo, format("checking path ‘%1%’...") % path);
-    ValidPathInfo info = store.queryPathInfo(path);
+    auto info = store.queryPathInfo(path);
     bool res;
     if (!pathExists(path))
         res = false;
     else {
-        HashResult current = hashPath(info.narHash.type, path);
+        HashResult current = hashPath(info->narHash.type, path);
         Hash nullHash(htSHA256);
-        res = info.narHash == nullHash || info.narHash == current.first;
+        res = info->narHash == nullHash || info->narHash == current.first;
     }
     pathContentsGoodCache[path] = res;
     if (!res) printMsg(lvlError, format("path ‘%1%’ is corrupted or missing!") % path);
@@ -3793,8 +3672,6 @@ void Worker::markContentsGood(const Path & path)
 
 void LocalStore::buildPaths(const PathSet & drvPaths, BuildMode buildMode)
 {
-    startNest(nest, lvlDebug, format("building %1%") % showPaths(drvPaths));
-
     Worker worker(*this);
 
     Goals goals;
@@ -3824,8 +3701,6 @@ void LocalStore::buildPaths(const PathSet & drvPaths, BuildMode buildMode)
 BuildResult LocalStore::buildDerivation(const Path & drvPath, const BasicDerivation & drv,
     BuildMode buildMode)
 {
-    startNest(nest, lvlDebug, format("building %1%") % showPaths({drvPath}));
-
     Worker worker(*this);
     auto goal = worker.makeBasicDerivationGoal(drvPath, drv, buildMode);
 
@@ -3870,7 +3745,7 @@ void LocalStore::repairPath(const Path & path)
     if (goal->getExitCode() != Goal::ecSuccess) {
         /* Since substituting the path didn't work, if we have a valid
            deriver, then rebuild the deriver. */
-        Path deriver = queryDeriver(path);
+        auto deriver = queryPathInfo(path)->deriver;
         if (deriver != "" && isValidPath(deriver)) {
             goals.clear();
             goals.insert(worker.makeDerivationGoal(deriver, StringSet(), bmRepair));
diff --git a/src/libstore/builtins.cc b/src/libstore/builtins.cc
index 50417b644a02..a4785d6905bb 100644
--- a/src/libstore/builtins.cc
+++ b/src/libstore/builtins.cc
@@ -31,7 +31,7 @@ void builtinFetchurl(const BasicDerivation & drv)
     auto unpack = drv.env.find("unpack");
     if (unpack != drv.env.end() && unpack->second == "1") {
         if (string(*data.data, 0, 6) == string("\xfd" "7zXZ\0", 6))
-            data.data = decompressXZ(*data.data);
+            data.data = decompress("xz", ref<std::string>(data.data));
         StringSource source(*data.data);
         restorePath(storePath, source);
     } else
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index d9b009d40322..becf8524546c 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -290,7 +290,7 @@ Hash hashDerivationModulo(Store & store, Derivation drv)
     DerivationInputs inputs2;
     for (auto & i : drv.inputDrvs) {
         Hash h = drvHashes[i.first];
-        if (h.type == htUnknown) {
+        if (!h) {
             assert(store.isValidPath(i.first));
             Derivation drv2 = readDerivation(i.first);
             h = hashDerivationModulo(store, drv2);
diff --git a/src/libstore/download.cc b/src/libstore/download.cc
index 8cd3ad741e10..6e39330e40d9 100644
--- a/src/libstore/download.cc
+++ b/src/libstore/download.cc
@@ -225,7 +225,7 @@ Path Downloader::downloadCached(ref<Store> store, const string & url_, bool unpa
 {
     auto url = resolveUri(url_);
 
-    Path cacheDir = getEnv("XDG_CACHE_HOME", getEnv("HOME", "") + "/.cache") + "/nix/tarballs";
+    Path cacheDir = getCacheDir() + "/nix/tarballs";
     createDirs(cacheDir);
 
     string urlHash = printHash32(hashString(htSHA256, url));
@@ -313,7 +313,7 @@ bool isUri(const string & s)
     size_t pos = s.find("://");
     if (pos == string::npos) return false;
     string scheme(s, 0, pos);
-    return scheme == "http" || scheme == "https" || scheme == "file" || scheme == "channel";
+    return scheme == "http" || scheme == "https" || scheme == "file" || scheme == "channel" || scheme == "git";
 }
 
 
diff --git a/src/libstore/gc.cc b/src/libstore/gc.cc
index 52afa1b14e03..8fc582f4c20d 100644
--- a/src/libstore/gc.cc
+++ b/src/libstore/gc.cc
@@ -305,7 +305,7 @@ void LocalStore::findRoots(const Path & path, unsigned char type, Roots & roots)
 
         else if (type == DT_REG) {
             Path storePath = settings.nixStore + "/" + baseNameOf(path);
-            if (isValidPath(storePath))
+            if (isStorePath(storePath) && isValidPath(storePath))
                 roots[path] = storePath;
         }
 
@@ -407,7 +407,7 @@ void LocalStore::deletePathRecursive(GCState & state, const Path & path)
         queryReferrers(path, referrers);
         for (auto & i : referrers)
             if (i != path) deletePathRecursive(state, i);
-        size = queryPathInfo(path).narSize;
+        size = queryPathInfo(path)->narSize;
         invalidatePathChecked(path);
     }
 
@@ -485,7 +485,7 @@ bool LocalStore::canReachRoot(GCState & state, PathSet & visited, const Path & p
     if (state.gcKeepDerivations && isDerivation(path)) {
         PathSet outputs = queryDerivationOutputs(path);
         for (auto & i : outputs)
-            if (isValidPath(i) && queryDeriver(i) == path)
+            if (isValidPath(i) && queryPathInfo(i)->deriver == path)
                 incoming.insert(i);
     }
 
@@ -514,7 +514,7 @@ void LocalStore::tryToDelete(GCState & state, const Path & path)
 
     if (path == linksDir || path == state.trashDir) return;
 
-    startNest(nest, lvlDebug, format("considering whether to delete ‘%1%’") % path);
+    Activity act(*logger, lvlDebug, format("considering whether to delete ‘%1%’") % path);
 
     if (!isValidPath(path)) {
         /* A lock file belonging to a path that we're building right
@@ -691,7 +691,7 @@ void LocalStore::collectGarbage(const GCOptions & options, GCResults & results)
                 string name = dirent->d_name;
                 if (name == "." || name == "..") continue;
                 Path path = settings.nixStore + "/" + name;
-                if (isValidPath(path))
+                if (isStorePath(path) && isValidPath(path))
                     entries.push_back(path);
                 else
                     tryToDelete(state, path);
diff --git a/src/libstore/globals.cc b/src/libstore/globals.cc
index b6078253319f..c12178e4028a 100644
--- a/src/libstore/globals.cc
+++ b/src/libstore/globals.cc
@@ -28,7 +28,6 @@ Settings::Settings()
     keepFailed = false;
     keepGoing = false;
     tryFallback = false;
-    buildVerbosity = lvlError;
     maxBuildJobs = 1;
     buildCores = 1;
 #ifdef _SC_NPROCESSORS_ONLN
@@ -40,7 +39,6 @@ Settings::Settings()
     maxSilentTime = 0;
     buildTimeout = 0;
     useBuildHook = true;
-    printBuildTrace = false;
     reservedSize = 8 * 1024 * 1024;
     fsyncMetadata = true;
     useSQLiteWAL = true;
@@ -186,19 +184,6 @@ void Settings::update()
     _get(enableImportNative, "allow-unsafe-native-code-during-evaluation");
     _get(useCaseHack, "use-case-hack");
     _get(preBuildHook, "pre-build-hook");
-
-    string subs = getEnv("NIX_SUBSTITUTERS", "default");
-    if (subs == "default") {
-        substituters.clear();
-#if 0
-        if (getEnv("NIX_OTHER_STORES") != "")
-            substituters.push_back(nixLibexecDir + "/nix/substituters/copy-from-other-stores.pl");
-#endif
-        substituters.push_back(nixLibexecDir + "/nix/substituters/download-from-binary-cache.pl");
-        if (useSshSubstituter && !sshSubstituterHosts.empty())
-            substituters.push_back(nixLibexecDir + "/nix/substituters/download-via-ssh");
-    } else
-        substituters = tokenizeString<Strings>(subs, ":");
 }
 
 
diff --git a/src/libstore/globals.hh b/src/libstore/globals.hh
index 572fa7188c14..65f763ace3c7 100644
--- a/src/libstore/globals.hh
+++ b/src/libstore/globals.hh
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "types.hh"
+#include "logging.hh"
 
 #include <map>
 #include <sys/types.h>
@@ -77,8 +78,12 @@ struct Settings {
        instead. */
     bool tryFallback;
 
-    /* Verbosity level for build output. */
-    Verbosity buildVerbosity;
+    /* Whether to show build log output in real time. */
+    bool verboseBuild = true;
+
+    /* If verboseBuild is false, the number of lines of the tail of
+       the log to show if a build fails. */
+    size_t logLines = 10;
 
     /* Maximum number of parallel build jobs.  0 means unlimited. */
     unsigned int maxBuildJobs;
@@ -105,31 +110,10 @@ struct Settings {
        means infinity.  */
     time_t buildTimeout;
 
-    /* The substituters.  There are programs that can somehow realise
-       a store path without building, e.g., by downloading it or
-       copying it from a CD. */
-    Paths substituters;
-
     /* Whether to use build hooks (for distributed builds).  Sometimes
        users want to disable this from the command-line. */
     bool useBuildHook;
 
-    /* Whether buildDerivations() should print out lines on stderr in
-       a fixed format to allow its progress to be monitored.  Each
-       line starts with a "@".  The following are defined:
-
-       @ build-started <drvpath> <outpath> <system> <logfile>
-       @ build-failed <drvpath> <outpath> <exitcode> <error text>
-       @ build-succeeded <drvpath> <outpath>
-       @ substituter-started <outpath> <substituter>
-       @ substituter-failed <outpath> <exitcode> <error text>
-       @ substituter-succeeded <outpath>
-
-       Best combined with --no-build-output, otherwise stderr might
-       conceivably contain lines in this format printed by the
-       builders. */
-    bool printBuildTrace;
-
     /* Amount of reserved space for the garbage collector
        (/nix/var/nix/db/reserved). */
     off_t reservedSize;
diff --git a/src/libstore/http-binary-cache-store.cc b/src/libstore/http-binary-cache-store.cc
index 6dcea1cbf090..92d94aeeacd5 100644
--- a/src/libstore/http-binary-cache-store.cc
+++ b/src/libstore/http-binary-cache-store.cc
@@ -1,6 +1,7 @@
 #include "binary-cache-store.hh"
 #include "download.hh"
 #include "globals.hh"
+#include "nar-info-disk-cache.hh"
 
 namespace nix {
 
@@ -15,8 +16,8 @@ private:
 public:
 
     HttpBinaryCacheStore(std::shared_ptr<Store> localStore,
-        const Path & secretKeyFile, const Path & _cacheUri)
-        : BinaryCacheStore(localStore, secretKeyFile)
+        const StoreParams & params, const Path & _cacheUri)
+        : BinaryCacheStore(localStore, params)
         , cacheUri(_cacheUri)
         , downloaders(
             std::numeric_limits<size_t>::max(),
@@ -24,13 +25,23 @@ public:
     {
         if (cacheUri.back() == '/')
             cacheUri.pop_back();
+
+        diskCache = getNarInfoDiskCache();
+    }
+
+    std::string getUri() override
+    {
+        return cacheUri;
     }
 
     void init() override
     {
         // FIXME: do this lazily?
-        if (!fileExists("nix-cache-info"))
-            throw Error(format("‘%s’ does not appear to be a binary cache") % cacheUri);
+        if (!diskCache->cacheExists(cacheUri)) {
+            if (!fileExists("nix-cache-info"))
+                throw Error(format("‘%s’ does not appear to be a binary cache") % cacheUri);
+            diskCache->createCache(cacheUri);
+        }
     }
 
 protected:
@@ -74,12 +85,14 @@ protected:
 
 };
 
-static RegisterStoreImplementation regStore([](const std::string & uri) -> std::shared_ptr<Store> {
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
+{
     if (std::string(uri, 0, 7) != "http://" &&
         std::string(uri, 0, 8) != "https://") return 0;
     auto store = std::make_shared<HttpBinaryCacheStore>(std::shared_ptr<Store>(0),
-        settings.get("binary-cache-secret-key-file", string("")),
-        uri);
+        params, uri);
     store->init();
     return store;
 });
diff --git a/src/libstore/local-binary-cache-store.cc b/src/libstore/local-binary-cache-store.cc
index 7968c98b9558..2c2944938761 100644
--- a/src/libstore/local-binary-cache-store.cc
+++ b/src/libstore/local-binary-cache-store.cc
@@ -12,10 +12,19 @@ private:
 public:
 
     LocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-        const Path & secretKeyFile, const Path & binaryCacheDir);
+        const StoreParams & params, const Path & binaryCacheDir)
+        : BinaryCacheStore(localStore, params)
+        , binaryCacheDir(binaryCacheDir)
+    {
+    }
 
     void init() override;
 
+    std::string getUri() override
+    {
+        return "file://" + binaryCacheDir;
+    }
+
 protected:
 
     bool fileExists(const std::string & path) override;
@@ -24,14 +33,21 @@ protected:
 
     std::shared_ptr<std::string> getFile(const std::string & path) override;
 
-};
+    PathSet queryAllValidPaths() override
+    {
+        PathSet paths;
 
-LocalBinaryCacheStore::LocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile, const Path & binaryCacheDir)
-    : BinaryCacheStore(localStore, secretKeyFile)
-    , binaryCacheDir(binaryCacheDir)
-{
-}
+        for (auto & entry : readDirectory(binaryCacheDir)) {
+            if (entry.name.size() != 40 ||
+                !hasSuffix(entry.name, ".narinfo"))
+                continue;
+            paths.insert(settings.nixStore + "/" + entry.name.substr(0, entry.name.size() - 8));
+        }
+
+        return paths;
+    }
+
+};
 
 void LocalBinaryCacheStore::init()
 {
@@ -69,20 +85,15 @@ std::shared_ptr<std::string> LocalBinaryCacheStore::getFile(const std::string &
     }
 }
 
-ref<Store> openLocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile, const Path & binaryCacheDir)
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
 {
-    auto store = make_ref<LocalBinaryCacheStore>(
-        localStore, secretKeyFile, binaryCacheDir);
+    if (std::string(uri, 0, 7) != "file://") return 0;
+    auto store = std::make_shared<LocalBinaryCacheStore>(
+        std::shared_ptr<Store>(0), params, std::string(uri, 7));
     store->init();
     return store;
-}
-
-static RegisterStoreImplementation regStore([](const std::string & uri) -> std::shared_ptr<Store> {
-    if (std::string(uri, 0, 7) != "file://") return 0;
-    return openLocalBinaryCacheStore(std::shared_ptr<Store>(0),
-        settings.get("binary-cache-secret-key-file", string("")),
-        std::string(uri, 7));
 });
 
 }
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index d6e1e4d7e0d4..01a11f11f65d 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -5,12 +5,11 @@
 #include "pathlocks.hh"
 #include "worker-protocol.hh"
 #include "derivations.hh"
-#include "affinity.hh"
+#include "nar-info.hh"
 
 #include <iostream>
 #include <algorithm>
 #include <cstring>
-#include <atomic>
 
 #include <sys/types.h>
 #include <sys/stat.h>
@@ -220,19 +219,6 @@ LocalStore::~LocalStore()
     auto state(_state.lock());
 
     try {
-        for (auto & i : state->runningSubstituters) {
-            if (i.second.disabled) continue;
-            i.second.to.close();
-            i.second.from.close();
-            i.second.error.close();
-            if (i.second.pid != -1)
-                i.second.pid.wait(true);
-        }
-    } catch (...) {
-        ignoreException();
-    }
-
-    try {
         if (state->fdTempRoots != -1) {
             state->fdTempRoots.close();
             unlink(state->fnTempRoots.c_str());
@@ -243,6 +229,12 @@ LocalStore::~LocalStore()
 }
 
 
+std::string LocalStore::getUri()
+{
+    return "local";
+}
+
+
 int LocalStore::getSchema()
 {
     int curSchema = 0;
@@ -577,6 +569,11 @@ uint64_t LocalStore::addValidPath(State & state,
         }
     }
 
+    {
+        auto state_(Store::state.lock());
+        state_->pathInfoCache.upsert(storePathToHash(info.path), std::make_shared<ValidPathInfo>(info));
+    }
+
     return id;
 }
 
@@ -595,44 +592,44 @@ Hash parseHashField(const Path & path, const string & s)
 }
 
 
-ValidPathInfo LocalStore::queryPathInfo(const Path & path)
+std::shared_ptr<ValidPathInfo> LocalStore::queryPathInfoUncached(const Path & path)
 {
-    ValidPathInfo info;
-    info.path = path;
+    auto info = std::make_shared<ValidPathInfo>();
+    info->path = path;
 
     assertStorePath(path);
 
-    return retrySQLite<ValidPathInfo>([&]() {
+    return retrySQLite<std::shared_ptr<ValidPathInfo>>([&]() {
         auto state(_state.lock());
 
         /* Get the path info. */
         auto useQueryPathInfo(state->stmtQueryPathInfo.use()(path));
 
         if (!useQueryPathInfo.next())
-            throw Error(format("path ‘%1%’ is not valid") % path);
+            return std::shared_ptr<ValidPathInfo>();
 
-        info.id = useQueryPathInfo.getInt(0);
+        info->id = useQueryPathInfo.getInt(0);
 
-        info.narHash = parseHashField(path, useQueryPathInfo.getStr(1));
+        info->narHash = parseHashField(path, useQueryPathInfo.getStr(1));
 
-        info.registrationTime = useQueryPathInfo.getInt(2);
+        info->registrationTime = useQueryPathInfo.getInt(2);
 
         auto s = (const char *) sqlite3_column_text(state->stmtQueryPathInfo, 3);
-        if (s) info.deriver = s;
+        if (s) info->deriver = s;
 
         /* Note that narSize = NULL yields 0. */
-        info.narSize = useQueryPathInfo.getInt(4);
+        info->narSize = useQueryPathInfo.getInt(4);
 
-        info.ultimate = useQueryPathInfo.getInt(5) == 1;
+        info->ultimate = useQueryPathInfo.getInt(5) == 1;
 
         s = (const char *) sqlite3_column_text(state->stmtQueryPathInfo, 6);
-        if (s) info.sigs = tokenizeString<StringSet>(s, " ");
+        if (s) info->sigs = tokenizeString<StringSet>(s, " ");
 
         /* Get the references. */
-        auto useQueryReferences(state->stmtQueryReferences.use()(info.id));
+        auto useQueryReferences(state->stmtQueryReferences.use()(info->id));
 
         while (useQueryReferences.next())
-            info.references.insert(useQueryReferences.getStr(0));
+            info->references.insert(useQueryReferences.getStr(0));
 
         return info;
     });
@@ -661,17 +658,17 @@ uint64_t LocalStore::queryValidPathId(State & state, const Path & path)
 }
 
 
-bool LocalStore::isValidPath(State & state, const Path & path)
+bool LocalStore::isValidPath_(State & state, const Path & path)
 {
     return state.stmtQueryPathInfo.use()(path).next();
 }
 
 
-bool LocalStore::isValidPath(const Path & path)
+bool LocalStore::isValidPathUncached(const Path & path)
 {
     return retrySQLite<bool>([&]() {
         auto state(_state.lock());
-        return isValidPath(*state, path);
+        return isValidPath_(*state, path);
     });
 }
 
@@ -716,12 +713,6 @@ void LocalStore::queryReferrers(const Path & path, PathSet & referrers)
 }
 
 
-Path LocalStore::queryDeriver(const Path & path)
-{
-    return queryPathInfo(path).deriver;
-}
-
-
 PathSet LocalStore::queryValidDerivers(const Path & path)
 {
     assertStorePath(path);
@@ -793,215 +784,46 @@ Path LocalStore::queryPathFromHashPart(const string & hashPart)
 }
 
 
-void LocalStore::setSubstituterEnv()
-{
-    static std::atomic_flag done;
-
-    if (done.test_and_set()) return;
-
-    /* Pass configuration options (including those overridden with
-       --option) to substituters. */
-    setenv("_NIX_OPTIONS", settings.pack().c_str(), 1);
-}
-
-
-void LocalStore::startSubstituter(const Path & substituter, RunningSubstituter & run)
-{
-    if (run.disabled || run.pid != -1) return;
-
-    debug(format("starting substituter program ‘%1%’") % substituter);
-
-    Pipe toPipe, fromPipe, errorPipe;
-
-    toPipe.create();
-    fromPipe.create();
-    errorPipe.create();
-
-    setSubstituterEnv();
-
-    run.pid = startProcess([&]() {
-        if (dup2(toPipe.readSide, STDIN_FILENO) == -1)
-            throw SysError("dupping stdin");
-        if (dup2(fromPipe.writeSide, STDOUT_FILENO) == -1)
-            throw SysError("dupping stdout");
-        if (dup2(errorPipe.writeSide, STDERR_FILENO) == -1)
-            throw SysError("dupping stderr");
-        execl(substituter.c_str(), substituter.c_str(), "--query", NULL);
-        throw SysError(format("executing ‘%1%’") % substituter);
-    });
-
-    run.program = baseNameOf(substituter);
-    run.to = toPipe.writeSide.borrow();
-    run.from = run.fromBuf.fd = fromPipe.readSide.borrow();
-    run.error = errorPipe.readSide.borrow();
-
-    toPipe.readSide.close();
-    fromPipe.writeSide.close();
-    errorPipe.writeSide.close();
-
-    /* The substituter may exit right away if it's disabled in any way
-       (e.g. copy-from-other-stores.pl will exit if no other stores
-       are configured). */
-    try {
-        getLineFromSubstituter(run);
-    } catch (EndOfFile & e) {
-        run.to.close();
-        run.from.close();
-        run.error.close();
-        run.disabled = true;
-        if (run.pid.wait(true) != 0) throw;
-    }
-}
-
-
-/* Read a line from the substituter's stdout, while also processing
-   its stderr. */
-string LocalStore::getLineFromSubstituter(RunningSubstituter & run)
-{
-    string res, err;
-
-    /* We might have stdout data left over from the last time. */
-    if (run.fromBuf.hasData()) goto haveData;
-
-    while (1) {
-        checkInterrupt();
-
-        fd_set fds;
-        FD_ZERO(&fds);
-        FD_SET(run.from, &fds);
-        FD_SET(run.error, &fds);
-
-        /* Wait for data to appear on the substituter's stdout or
-           stderr. */
-        if (select(run.from > run.error ? run.from + 1 : run.error + 1, &fds, 0, 0, 0) == -1) {
-            if (errno == EINTR) continue;
-            throw SysError("waiting for input from the substituter");
-        }
-
-        /* Completely drain stderr before dealing with stdout. */
-        if (FD_ISSET(run.error, &fds)) {
-            char buf[4096];
-            ssize_t n = read(run.error, (unsigned char *) buf, sizeof(buf));
-            if (n == -1) {
-                if (errno == EINTR) continue;
-                throw SysError("reading from substituter's stderr");
-            }
-            if (n == 0) throw EndOfFile(format("substituter ‘%1%’ died unexpectedly") % run.program);
-            err.append(buf, n);
-            string::size_type p;
-            while ((p = err.find('\n')) != string::npos) {
-                printMsg(lvlError, run.program + ": " + string(err, 0, p));
-                err = string(err, p + 1);
-            }
-        }
-
-        /* Read from stdout until we get a newline or the buffer is empty. */
-        else if (run.fromBuf.hasData() || FD_ISSET(run.from, &fds)) {
-        haveData:
-            do {
-                unsigned char c;
-                run.fromBuf(&c, 1);
-                if (c == '\n') {
-                    if (!err.empty()) printMsg(lvlError, run.program + ": " + err);
-                    return res;
-                }
-                res += c;
-            } while (run.fromBuf.hasData());
-        }
-    }
-}
-
-
-template<class T> T LocalStore::getIntLineFromSubstituter(RunningSubstituter & run)
-{
-    string s = getLineFromSubstituter(run);
-    T res;
-    if (!string2Int(s, res)) throw Error("integer expected from stream");
-    return res;
-}
-
-
 PathSet LocalStore::querySubstitutablePaths(const PathSet & paths)
 {
-    auto state(_state.lock());
-
     PathSet res;
-    for (auto & i : settings.substituters) {
-        if (res.size() == paths.size()) break;
-        RunningSubstituter & run(state->runningSubstituters[i]);
-        startSubstituter(i, run);
-        if (run.disabled) continue;
-        string s = "have ";
-        for (auto & j : paths)
-            if (res.find(j) == res.end()) { s += j; s += " "; }
-        writeLine(run.to, s);
-        while (true) {
-            /* FIXME: we only read stderr when an error occurs, so
-               substituters should only write (short) messages to
-               stderr when they fail.  I.e. they shouldn't write debug
-               output. */
-            Path path = getLineFromSubstituter(run);
-            if (path == "") break;
-            res.insert(path);
+    for (auto & sub : getDefaultSubstituters()) {
+        for (auto & path : paths) {
+            if (res.count(path)) continue;
+            debug(format("checking substituter ‘%s’ for path ‘%s’")
+                % sub->getUri() % path);
+            if (sub->isValidPath(path))
+                res.insert(path);
         }
     }
-
     return res;
 }
 
 
-void LocalStore::querySubstitutablePathInfos(const Path & substituter,
-    PathSet & paths, SubstitutablePathInfos & infos)
-{
-    auto state(_state.lock());
-
-    RunningSubstituter & run(state->runningSubstituters[substituter]);
-    startSubstituter(substituter, run);
-    if (run.disabled) return;
-
-    string s = "info ";
-    for (auto & i : paths)
-        if (infos.find(i) == infos.end()) { s += i; s += " "; }
-    writeLine(run.to, s);
-
-    while (true) {
-        Path path = getLineFromSubstituter(run);
-        if (path == "") break;
-        if (paths.find(path) == paths.end())
-            throw Error(format("got unexpected path ‘%1%’ from substituter") % path);
-        paths.erase(path);
-        SubstitutablePathInfo & info(infos[path]);
-        info.deriver = getLineFromSubstituter(run);
-        if (info.deriver != "") assertStorePath(info.deriver);
-        int nrRefs = getIntLineFromSubstituter<int>(run);
-        while (nrRefs--) {
-            Path p = getLineFromSubstituter(run);
-            assertStorePath(p);
-            info.references.insert(p);
-        }
-        info.downloadSize = getIntLineFromSubstituter<long long>(run);
-        info.narSize = getIntLineFromSubstituter<long long>(run);
-    }
-}
-
-
 void LocalStore::querySubstitutablePathInfos(const PathSet & paths,
     SubstitutablePathInfos & infos)
 {
-    PathSet todo = paths;
-    for (auto & i : settings.substituters) {
-        if (todo.empty()) break;
-        querySubstitutablePathInfos(i, todo, infos);
+    for (auto & sub : getDefaultSubstituters()) {
+        for (auto & path : paths) {
+            if (infos.count(path)) continue;
+            debug(format("checking substituter ‘%s’ for path ‘%s’")
+                % sub->getUri() % path);
+            try {
+                auto info = sub->queryPathInfo(path);
+                auto narInfo = std::dynamic_pointer_cast<const NarInfo>(
+                    std::shared_ptr<const ValidPathInfo>(info));
+                infos[path] = SubstitutablePathInfo{
+                    info->deriver,
+                    info->references,
+                    narInfo ? narInfo->fileSize : 0,
+                    info->narSize};
+            } catch (InvalidPath) {
+            }
+        }
     }
 }
 
 
-Hash LocalStore::queryPathHash(const Path & path)
-{
-    return queryPathInfo(path).narHash;
-}
-
-
 void LocalStore::registerValidPath(const ValidPathInfo & info)
 {
     ValidPathInfos infos;
@@ -1026,7 +848,7 @@ void LocalStore::registerValidPaths(const ValidPathInfos & infos)
 
         for (auto & i : infos) {
             assert(i.narHash.type == htSHA256);
-            if (isValidPath(*state, i.path))
+            if (isValidPath_(*state, i.path))
                 updatePathInfo(*state, i);
             else
                 addValidPath(*state, i, false);
@@ -1071,6 +893,11 @@ void LocalStore::invalidatePath(State & state, const Path & path)
 
     /* Note that the foreign key constraints on the Refs table take
        care of deleting the references entries for `path'. */
+
+    {
+        auto state_(Store::state.lock());
+        state_->pathInfoCache.erase(storePathToHash(path));
+    }
 }
 
 
@@ -1225,8 +1052,7 @@ void LocalStore::exportPath(const Path & path, bool sign,
 
     printMsg(lvlTalkative, format("exporting path ‘%1%’") % path);
 
-    if (!isValidPath(path))
-        throw Error(format("path ‘%1%’ is not valid") % path);
+    auto info = queryPathInfo(path);
 
     HashAndWriteSink hashAndWriteSink(sink);
 
@@ -1236,15 +1062,11 @@ void LocalStore::exportPath(const Path & path, bool sign,
        filesystem corruption from spreading to other machines.
        Don't complain if the stored hash is zero (unknown). */
     Hash hash = hashAndWriteSink.currentHash();
-    Hash storedHash = queryPathHash(path);
-    if (hash != storedHash && storedHash != Hash(storedHash.type))
+    if (hash != info->narHash && info->narHash != Hash(info->narHash.type))
         throw Error(format("hash of path ‘%1%’ has changed from ‘%2%’ to ‘%3%’!") % path
-            % printHash(storedHash) % printHash(hash));
-
-    PathSet references;
-    queryReferences(path, references);
+            % printHash(info->narHash) % printHash(hash));
 
-    hashAndWriteSink << exportMagic << path << references << queryDeriver(path);
+    hashAndWriteSink << exportMagic << path << info->references << info->deriver;
 
     if (sign) {
         Hash hash = hashAndWriteSink.currentHash();
@@ -1440,7 +1262,7 @@ void LocalStore::invalidatePathChecked(const Path & path)
 
         SQLiteTxn txn(state->db);
 
-        if (isValidPath(*state, path)) {
+        if (isValidPath_(*state, path)) {
             PathSet referrers; queryReferrers(*state, path, referrers);
             referrers.erase(path); /* ignore self-references */
             if (!referrers.empty())
@@ -1486,38 +1308,38 @@ bool LocalStore::verifyStore(bool checkContents, bool repair)
 
         for (auto & i : validPaths) {
             try {
-                ValidPathInfo info = queryPathInfo(i);
+                auto info = std::const_pointer_cast<ValidPathInfo>(std::shared_ptr<const ValidPathInfo>(queryPathInfo(i)));
 
                 /* Check the content hash (optionally - slow). */
                 printMsg(lvlTalkative, format("checking contents of ‘%1%’") % i);
-                HashResult current = hashPath(info.narHash.type, i);
+                HashResult current = hashPath(info->narHash.type, i);
 
-                if (info.narHash != nullHash && info.narHash != current.first) {
+                if (info->narHash != nullHash && info->narHash != current.first) {
                     printMsg(lvlError, format("path ‘%1%’ was modified! "
                             "expected hash ‘%2%’, got ‘%3%’")
-                        % i % printHash(info.narHash) % printHash(current.first));
+                        % i % printHash(info->narHash) % printHash(current.first));
                     if (repair) repairPath(i); else errors = true;
                 } else {
 
                     bool update = false;
 
                     /* Fill in missing hashes. */
-                    if (info.narHash == nullHash) {
+                    if (info->narHash == nullHash) {
                         printMsg(lvlError, format("fixing missing hash on ‘%1%’") % i);
-                        info.narHash = current.first;
+                        info->narHash = current.first;
                         update = true;
                     }
 
                     /* Fill in missing narSize fields (from old stores). */
-                    if (info.narSize == 0) {
+                    if (info->narSize == 0) {
                         printMsg(lvlError, format("updating size field on ‘%1%’ to %2%") % i % current.second);
-                        info.narSize = current.second;
+                        info->narSize = current.second;
                         update = true;
                     }
 
                     if (update) {
                         auto state(_state.lock());
-                        updatePathInfo(*state, info);
+                        updatePathInfo(*state, *info);
                     }
 
                 }
@@ -1656,11 +1478,11 @@ void LocalStore::addSignatures(const Path & storePath, const StringSet & sigs)
 
         SQLiteTxn txn(state->db);
 
-        auto info = queryPathInfo(storePath);
+        auto info = std::const_pointer_cast<ValidPathInfo>(std::shared_ptr<const ValidPathInfo>(queryPathInfo(storePath)));
 
-        info.sigs.insert(sigs.begin(), sigs.end());
+        info->sigs.insert(sigs.begin(), sigs.end());
 
-        updatePathInfo(*state, info);
+        updatePathInfo(*state, *info);
 
         txn.commit();
     });
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index 14ff92c35cc5..6f2341decfbd 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -40,17 +40,6 @@ struct OptimiseStats
 };
 
 
-struct RunningSubstituter
-{
-    Path program;
-    Pid pid;
-    AutoCloseFD to, from, error;
-    FdSource fromBuf;
-    bool disabled;
-    RunningSubstituter() : disabled(false) { };
-};
-
-
 class LocalStore : public LocalFSStore
 {
 private:
@@ -80,10 +69,6 @@ private:
         /* The file to which we write our temporary roots. */
         Path fnTempRoots;
         AutoCloseFD fdTempRoots;
-
-        typedef std::map<Path, RunningSubstituter> RunningSubstituters;
-        RunningSubstituters runningSubstituters;
-
     };
 
     Sync<State, std::recursive_mutex> _state;
@@ -102,20 +87,18 @@ public:
 
     /* Implementations of abstract store API methods. */
 
-    bool isValidPath(const Path & path) override;
+    std::string getUri() override;
+
+    bool isValidPathUncached(const Path & path) override;
 
     PathSet queryValidPaths(const PathSet & paths) override;
 
     PathSet queryAllValidPaths() override;
 
-    ValidPathInfo queryPathInfo(const Path & path) override;
-
-    Hash queryPathHash(const Path & path) override;
+    std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) override;
 
     void queryReferrers(const Path & path, PathSet & referrers) override;
 
-    Path queryDeriver(const Path & path) override;
-
     PathSet queryValidDerivers(const Path & path) override;
 
     PathSet queryDerivationOutputs(const Path & path) override;
@@ -126,9 +109,6 @@ public:
 
     PathSet querySubstitutablePaths(const PathSet & paths) override;
 
-    void querySubstitutablePathInfos(const Path & substituter,
-        PathSet & paths, SubstitutablePathInfos & infos);
-
     void querySubstitutablePathInfos(const PathSet & paths,
         SubstitutablePathInfos & infos) override;
 
@@ -196,8 +176,6 @@ public:
        a substituter (if available). */
     void repairPath(const Path & path);
 
-    void setSubstituterEnv();
-
     void addSignatures(const Path & storePath, const StringSet & sigs) override;
 
     static bool haveWriteAccess();
@@ -250,13 +228,6 @@ private:
 
     void removeUnusedLinks(const GCState & state);
 
-    void startSubstituter(const Path & substituter,
-        RunningSubstituter & runningSubstituter);
-
-    string getLineFromSubstituter(RunningSubstituter & run);
-
-    template<class T> T getIntLineFromSubstituter(RunningSubstituter & run);
-
     Path createTempDirInStore();
 
     Path importPath(bool requireSignature, Source & source);
@@ -270,7 +241,7 @@ private:
     void optimisePath_(OptimiseStats & stats, const Path & path, InodeHash & inodeHash);
 
     // Internal versions that are not wrapped in retry_sqlite.
-    bool isValidPath(State & state, const Path & path);
+    bool isValidPath_(State & state, const Path & path);
     void queryReferrers(State & state, const Path & path, PathSet & referrers);
 
     /* Add signatures to a ValidPathInfo using the secret keys
diff --git a/src/libstore/local.mk b/src/libstore/local.mk
index 9a01596c36be..22b0f235e0b2 100644
--- a/src/libstore/local.mk
+++ b/src/libstore/local.mk
@@ -8,7 +8,7 @@ libstore_SOURCES := $(wildcard $(d)/*.cc)
 
 libstore_LIBS = libutil libformat
 
-libstore_LDFLAGS = $(SQLITE3_LIBS) -lbz2 $(LIBCURL_LIBS) $(SODIUM_LIBS)
+libstore_LDFLAGS = $(SQLITE3_LIBS) -lbz2 $(LIBCURL_LIBS) $(SODIUM_LIBS) -laws-cpp-sdk-s3 -laws-cpp-sdk-core -pthread
 
 ifeq ($(OS), SunOS)
 	libstore_LDFLAGS += -lsocket
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index 12472f017ce4..5c284d1b9ab2 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -35,12 +35,13 @@ void Store::computeFSClosure(const Path & path,
         if (includeDerivers && isDerivation(path)) {
             PathSet outputs = queryDerivationOutputs(path);
             for (auto & i : outputs)
-                if (isValidPath(i) && queryDeriver(i) == path)
+                if (isValidPath(i) && queryPathInfo(i)->deriver == path)
                     edges.insert(i);
         }
 
     } else {
-        queryReferences(path, edges);
+        auto info = queryPathInfo(path);
+        edges = info->references;
 
         if (includeOutputs && isDerivation(path)) {
             PathSet outputs = queryDerivationOutputs(path);
@@ -48,10 +49,8 @@ void Store::computeFSClosure(const Path & path,
                 if (isValidPath(i)) edges.insert(i);
         }
 
-        if (includeDerivers) {
-            Path deriver = queryDeriver(path);
-            if (isValidPath(deriver)) edges.insert(deriver);
-        }
+        if (includeDerivers && isValidPath(info->deriver))
+            edges.insert(info->deriver);
     }
 
     for (auto & i : edges)
@@ -189,8 +188,10 @@ Paths Store::topoSortPaths(const PathSet & paths)
         parents.insert(path);
 
         PathSet references;
-        if (isValidPath(path))
-            queryReferences(path, references);
+        try {
+            references = queryPathInfo(path)->references;
+        } catch (InvalidPath &) {
+        }
 
         for (auto & i : references)
             /* Don't traverse into paths that don't exist.  That can
diff --git a/src/libstore/nar-info-disk-cache.cc b/src/libstore/nar-info-disk-cache.cc
new file mode 100644
index 000000000000..d8b0815bf757
--- /dev/null
+++ b/src/libstore/nar-info-disk-cache.cc
@@ -0,0 +1,224 @@
+#include "nar-info-disk-cache.hh"
+#include "sync.hh"
+#include "sqlite.hh"
+#include "globals.hh"
+
+#include <sqlite3.h>
+
+namespace nix {
+
+static const char * schema = R"sql(
+
+create table if not exists BinaryCaches (
+    id        integer primary key autoincrement not null,
+    url       text unique not null,
+    timestamp integer not null,
+    storeDir  text not null,
+    wantMassQuery integer not null,
+    priority  integer not null
+);
+
+create table if not exists NARs (
+    cache            integer not null,
+    hashPart         text not null,
+    namePart         text not null,
+    url              text,
+    compression      text,
+    fileHash         text,
+    fileSize         integer,
+    narHash          text,
+    narSize          integer,
+    refs             text,
+    deriver          text,
+    sigs             text,
+    timestamp        integer not null,
+    primary key (cache, hashPart),
+    foreign key (cache) references BinaryCaches(id) on delete cascade
+);
+
+create table if not exists NARExistence (
+    cache            integer not null,
+    storePath        text not null,
+    exist            integer not null,
+    timestamp        integer not null,
+    primary key (cache, storePath),
+    foreign key (cache) references BinaryCaches(id) on delete cascade
+);
+
+)sql";
+
+class NarInfoDiskCacheImpl : public NarInfoDiskCache
+{
+public:
+
+    /* How long negative lookups are valid. */
+    const int ttlNegative = 3600;
+
+    struct State
+    {
+        SQLite db;
+        SQLiteStmt insertCache, queryCache, insertNAR, queryNAR, insertNARExistence, queryNARExistence;
+        std::map<std::string, int> caches;
+    };
+
+    Sync<State> _state;
+
+    NarInfoDiskCacheImpl()
+    {
+        auto state(_state.lock());
+
+        Path dbPath = getCacheDir() + "/nix/binary-cache-v4.sqlite";
+        createDirs(dirOf(dbPath));
+
+        if (sqlite3_open_v2(dbPath.c_str(), &state->db.db,
+                SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE, 0) != SQLITE_OK)
+            throw Error(format("cannot open store cache ‘%s’") % dbPath);
+
+        if (sqlite3_busy_timeout(state->db, 60 * 60 * 1000) != SQLITE_OK)
+            throwSQLiteError(state->db, "setting timeout");
+
+        // We can always reproduce the cache.
+        if (sqlite3_exec(state->db, "pragma synchronous = off", 0, 0, 0) != SQLITE_OK)
+            throwSQLiteError(state->db, "making database asynchronous");
+        if (sqlite3_exec(state->db, "pragma main.journal_mode = truncate", 0, 0, 0) != SQLITE_OK)
+            throwSQLiteError(state->db, "setting journal mode");
+
+        if (sqlite3_exec(state->db, schema, 0, 0, 0) != SQLITE_OK)
+            throwSQLiteError(state->db, "initialising database schema");
+
+        state->insertCache.create(state->db,
+            "insert or replace into BinaryCaches(url, timestamp, storeDir, wantMassQuery, priority) values (?, ?, ?, ?, ?)");
+
+        state->queryCache.create(state->db,
+            "select id, storeDir, wantMassQuery, priority from BinaryCaches where url = ?");
+
+        state->insertNAR.create(state->db,
+            "insert or replace into NARs(cache, hashPart, namePart, url, compression, fileHash, fileSize, narHash, "
+            "narSize, refs, deriver, sigs, timestamp) values (?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?)");
+
+        state->queryNAR.create(state->db,
+            "select * from NARs where cache = ? and hashPart = ?");
+
+        state->insertNARExistence.create(state->db,
+            "insert or replace into NARExistence(cache, storePath, exist, timestamp) values (?, ?, ?, ?)");
+
+        state->queryNARExistence.create(state->db,
+            "select exist, timestamp from NARExistence where cache = ? and storePath = ?");
+    }
+
+    int uriToInt(State & state, const std::string & uri)
+    {
+        auto i = state.caches.find(uri);
+        if (i == state.caches.end()) abort();
+        return i->second;
+    }
+
+    void createCache(const std::string & uri) override
+    {
+        auto state(_state.lock());
+
+        // FIXME: race
+
+        state->insertCache.use()(uri)(time(0))(settings.nixStore)(1)(0).exec();
+        assert(sqlite3_changes(state->db) == 1);
+        state->caches[uri] = sqlite3_last_insert_rowid(state->db);
+    }
+
+    bool cacheExists(const std::string & uri) override
+    {
+        auto state(_state.lock());
+
+        auto i = state->caches.find(uri);
+        if (i != state->caches.end()) return true;
+
+        auto queryCache(state->queryCache.use()(uri));
+
+        if (queryCache.next()) {
+            state->caches[uri] = queryCache.getInt(0);
+            return true;
+        }
+
+        return false;
+    }
+
+    std::pair<Outcome, std::shared_ptr<NarInfo>> lookupNarInfo(
+        const std::string & uri, const std::string & hashPart) override
+    {
+        auto state(_state.lock());
+
+        auto queryNAR(state->queryNAR.use()
+            (uriToInt(*state, uri))
+            (hashPart));
+
+        if (!queryNAR.next())
+            // FIXME: check NARExistence
+            return {oUnknown, 0};
+
+        auto narInfo = make_ref<NarInfo>();
+
+        // FIXME: implement TTL.
+
+        auto namePart = queryNAR.getStr(2);
+        narInfo->path = settings.nixStore + "/" +
+            hashPart + (namePart.empty() ? "" : "-" + namePart);
+        narInfo->url = queryNAR.getStr(3);
+        narInfo->compression = queryNAR.getStr(4);
+        if (!queryNAR.isNull(5))
+            narInfo->fileHash = parseHash(queryNAR.getStr(5));
+        narInfo->fileSize = queryNAR.getInt(6);
+        narInfo->narHash = parseHash(queryNAR.getStr(7));
+        narInfo->narSize = queryNAR.getInt(8);
+        for (auto & r : tokenizeString<Strings>(queryNAR.getStr(9), " "))
+            narInfo->references.insert(settings.nixStore + "/" + r);
+        if (!queryNAR.isNull(10))
+            narInfo->deriver = settings.nixStore + "/" + queryNAR.getStr(10);
+        for (auto & sig : tokenizeString<Strings>(queryNAR.getStr(11), " "))
+            narInfo->sigs.insert(sig);
+
+        return {oValid, narInfo};
+    }
+
+    void upsertNarInfo(
+        const std::string & uri, const std::string & hashPart,
+        std::shared_ptr<ValidPathInfo> info) override
+    {
+        auto state(_state.lock());
+
+        if (info) {
+
+            auto narInfo = std::dynamic_pointer_cast<NarInfo>(info);
+
+            assert(hashPart == storePathToHash(info->path));
+
+            state->insertNAR.use()
+                (uriToInt(*state, uri))
+                (hashPart)
+                (storePathToName(info->path))
+                (narInfo ? narInfo->url : "", narInfo != 0)
+                (narInfo ? narInfo->compression : "", narInfo != 0)
+                (narInfo && narInfo->fileHash ? narInfo->fileHash.to_string() : "", narInfo && narInfo->fileHash)
+                (narInfo ? narInfo->fileSize : 0, narInfo != 0 && narInfo->fileSize)
+                (info->narHash.to_string())
+                (info->narSize)
+                (concatStringsSep(" ", info->shortRefs()))
+                (info->deriver != "" ? baseNameOf(info->deriver) : "", info->deriver != "")
+                (concatStringsSep(" ", info->sigs))
+                (time(0)).exec();
+
+        } else {
+            // not implemented
+            abort();
+        }
+    }
+};
+
+ref<NarInfoDiskCache> getNarInfoDiskCache()
+{
+    static Sync<std::shared_ptr<NarInfoDiskCache>> cache;
+
+    auto cache_(cache.lock());
+    if (!*cache_) *cache_ = std::make_shared<NarInfoDiskCacheImpl>();
+    return ref<NarInfoDiskCache>(*cache_);
+}
+
+}
diff --git a/src/libstore/nar-info-disk-cache.hh b/src/libstore/nar-info-disk-cache.hh
new file mode 100644
index 000000000000..f4e3fbbdcbdc
--- /dev/null
+++ b/src/libstore/nar-info-disk-cache.hh
@@ -0,0 +1,29 @@
+#pragma once
+
+#include "ref.hh"
+#include "nar-info.hh"
+
+namespace nix {
+
+class NarInfoDiskCache
+{
+public:
+    typedef enum { oValid, oInvalid, oUnknown } Outcome;
+
+    virtual void createCache(const std::string & uri) = 0;
+
+    virtual bool cacheExists(const std::string & uri) = 0;
+
+    virtual std::pair<Outcome, std::shared_ptr<NarInfo>> lookupNarInfo(
+        const std::string & uri, const std::string & hashPart) = 0;
+
+    virtual void upsertNarInfo(
+        const std::string & uri, const std::string & hashPart,
+        std::shared_ptr<ValidPathInfo> info) = 0;
+};
+
+/* Return a singleton cache object that can be used concurrently by
+   multiple threads. */
+ref<NarInfoDiskCache> getNarInfoDiskCache();
+
+}
diff --git a/src/libstore/nar-info.cc b/src/libstore/nar-info.cc
index 680facdcfeb8..c0c5cecd1730 100644
--- a/src/libstore/nar-info.cc
+++ b/src/libstore/nar-info.cc
@@ -5,16 +5,16 @@ namespace nix {
 
 NarInfo::NarInfo(const std::string & s, const std::string & whence)
 {
-    auto corrupt = [&]() {
+    auto corrupt = [&]() [[noreturn]] {
         throw Error("NAR info file ‘%1%’ is corrupt");
     };
 
     auto parseHashField = [&](const string & s) {
-        string::size_type colon = s.find(':');
-        if (colon == string::npos) corrupt();
-        HashType ht = parseHashType(string(s, 0, colon));
-        if (ht == htUnknown) corrupt();
-        return parseHash16or32(ht, string(s, colon + 1));
+        try {
+            return parseHash(s);
+        } catch (BadHash &) {
+            corrupt();
+        }
     };
 
     size_t pos = 0;
@@ -103,12 +103,4 @@ std::string NarInfo::to_string() const
     return res;
 }
 
-Strings NarInfo::shortRefs() const
-{
-    Strings refs;
-    for (auto & r : references)
-        refs.push_back(baseNameOf(r));
-    return refs;
-}
-
 }
diff --git a/src/libstore/nar-info.hh b/src/libstore/nar-info.hh
index 3c783cf83fef..6bc2f03b139b 100644
--- a/src/libstore/nar-info.hh
+++ b/src/libstore/nar-info.hh
@@ -19,10 +19,6 @@ struct NarInfo : ValidPathInfo
     NarInfo(const std::string & s, const std::string & whence);
 
     std::string to_string() const;
-
-private:
-
-    Strings shortRefs() const;
 };
 
 }
diff --git a/src/libstore/optimise-store.cc b/src/libstore/optimise-store.cc
index 23cbe7e26b47..ad7fe0e8bebf 100644
--- a/src/libstore/optimise-store.cc
+++ b/src/libstore/optimise-store.cc
@@ -228,7 +228,7 @@ void LocalStore::optimiseStore(OptimiseStats & stats)
     for (auto & i : paths) {
         addTempRoot(i);
         if (!isValidPath(i)) continue; /* path was GC'ed, probably */
-        startNest(nest, lvlChatty, format("hashing files in ‘%1%’") % i);
+        Activity act(*logger, lvlChatty, format("hashing files in ‘%1%’") % i);
         optimisePath_(stats, i, inodeHash);
     }
 }
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 761e835481a8..5a254a6104f4 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -49,6 +49,12 @@ RemoteStore::RemoteStore(size_t maxConnections)
 }
 
 
+std::string RemoteStore::getUri()
+{
+    return "daemon";
+}
+
+
 ref<RemoteStore::Connection> RemoteStore::openConnection()
 {
     auto conn = make_ref<Connection>();
@@ -120,9 +126,9 @@ void RemoteStore::setOptions(ref<Connection> conn)
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 2)
         conn->to << settings.useBuildHook;
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 4)
-        conn->to << settings.buildVerbosity
-           << logType
-           << settings.printBuildTrace;
+        conn->to << (settings.verboseBuild ? lvlError : lvlVomit)
+                 << 0 // obsolete log type
+                 << 0 /* obsolete print build trace */;
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 6)
         conn->to << settings.buildCores;
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 10)
@@ -141,7 +147,7 @@ void RemoteStore::setOptions(ref<Connection> conn)
 }
 
 
-bool RemoteStore::isValidPath(const Path & path)
+bool RemoteStore::isValidPathUncached(const Path & path)
 {
     auto conn(connections->get());
     conn->to << wopIsValidPath << path;
@@ -239,48 +245,38 @@ void RemoteStore::querySubstitutablePathInfos(const PathSet & paths,
 }
 
 
-ValidPathInfo RemoteStore::queryPathInfo(const Path & path)
+std::shared_ptr<ValidPathInfo> RemoteStore::queryPathInfoUncached(const Path & path)
 {
     auto conn(connections->get());
     conn->to << wopQueryPathInfo << path;
-    conn->processStderr();
-    ValidPathInfo info;
-    info.path = path;
-    info.deriver = readString(conn->from);
-    if (info.deriver != "") assertStorePath(info.deriver);
-    info.narHash = parseHash(htSHA256, readString(conn->from));
-    info.references = readStorePaths<PathSet>(conn->from);
-    info.registrationTime = readInt(conn->from);
-    info.narSize = readLongLong(conn->from);
+    try {
+        conn->processStderr();
+    } catch (Error & e) {
+        // Ugly backwards compatibility hack.
+        if (e.msg().find("is not valid") != std::string::npos)
+            throw InvalidPath(e.what());
+        throw;
+    }
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 17) {
+        bool valid = readInt(conn->from) != 0;
+        if (!valid) throw InvalidPath(format("path ‘%s’ is not valid") % path);
+    }
+    auto info = std::make_shared<ValidPathInfo>();
+    info->path = path;
+    info->deriver = readString(conn->from);
+    if (info->deriver != "") assertStorePath(info->deriver);
+    info->narHash = parseHash(htSHA256, readString(conn->from));
+    info->references = readStorePaths<PathSet>(conn->from);
+    info->registrationTime = readInt(conn->from);
+    info->narSize = readLongLong(conn->from);
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 16) {
-        info.ultimate = readInt(conn->from) != 0;
-        info.sigs = readStrings<StringSet>(conn->from);
+        info->ultimate = readInt(conn->from) != 0;
+        info->sigs = readStrings<StringSet>(conn->from);
     }
     return info;
 }
 
 
-Hash RemoteStore::queryPathHash(const Path & path)
-{
-    auto conn(connections->get());
-    conn->to << wopQueryPathHash << path;
-    conn->processStderr();
-    string hash = readString(conn->from);
-    return parseHash(htSHA256, hash);
-}
-
-
-void RemoteStore::queryReferences(const Path & path,
-    PathSet & references)
-{
-    auto conn(connections->get());
-    conn->to << wopQueryReferences << path;
-    conn->processStderr();
-    PathSet references2 = readStorePaths<PathSet>(conn->from);
-    references.insert(references2.begin(), references2.end());
-}
-
-
 void RemoteStore::queryReferrers(const Path & path,
     PathSet & referrers)
 {
@@ -292,17 +288,6 @@ void RemoteStore::queryReferrers(const Path & path,
 }
 
 
-Path RemoteStore::queryDeriver(const Path & path)
-{
-    auto conn(connections->get());
-    conn->to << wopQueryDeriver << path;
-    conn->processStderr();
-    Path drvPath = readString(conn->from);
-    if (drvPath != "") assertStorePath(drvPath);
-    return drvPath;
-}
-
-
 PathSet RemoteStore::queryValidDerivers(const Path & path)
 {
     auto conn(connections->get());
@@ -517,6 +502,11 @@ void RemoteStore::collectGarbage(const GCOptions & options, GCResults & results)
     results.paths = readStrings<PathSet>(conn->from);
     results.bytesFreed = readLongLong(conn->from);
     readLongLong(conn->from); // obsolete
+
+    {
+        auto state_(Store::state.lock());
+        state_->pathInfoCache.clear();
+    }
 }
 
 
@@ -577,10 +567,8 @@ void RemoteStore::Connection::processStderr(Sink * sink, Source * source)
             writeString(buf, source->read(buf, len), to);
             to.flush();
         }
-        else {
-            string s = readString(from);
-            writeToStderr(s);
-        }
+        else
+            printMsg(lvlError, chomp(readString(from)));
     }
     if (msg == STDERR_ERROR) {
         string error = readString(from);
diff --git a/src/libstore/remote-store.hh b/src/libstore/remote-store.hh
index 45bc41804ccf..8e45a7449e2e 100644
--- a/src/libstore/remote-store.hh
+++ b/src/libstore/remote-store.hh
@@ -26,22 +26,18 @@ public:
 
     /* Implementations of abstract store API methods. */
 
-    bool isValidPath(const Path & path) override;
+    std::string getUri() override;
+
+    bool isValidPathUncached(const Path & path) override;
 
     PathSet queryValidPaths(const PathSet & paths) override;
 
     PathSet queryAllValidPaths() override;
 
-    ValidPathInfo queryPathInfo(const Path & path) override;
-
-    Hash queryPathHash(const Path & path) override;
-
-    void queryReferences(const Path & path, PathSet & references) override;
+    std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) override;
 
     void queryReferrers(const Path & path, PathSet & referrers) override;
 
-    Path queryDeriver(const Path & path) override;
-
     PathSet queryValidDerivers(const Path & path) override;
 
     PathSet queryDerivationOutputs(const Path & path) override;
diff --git a/src/libstore/s3-binary-cache-store.cc b/src/libstore/s3-binary-cache-store.cc
new file mode 100644
index 000000000000..cffcb1bf214f
--- /dev/null
+++ b/src/libstore/s3-binary-cache-store.cc
@@ -0,0 +1,253 @@
+#include "s3-binary-cache-store.hh"
+#include "nar-info.hh"
+#include "nar-info-disk-cache.hh"
+#include "globals.hh"
+
+#include <aws/core/client/ClientConfiguration.h>
+#include <aws/s3/S3Client.h>
+#include <aws/s3/model/CreateBucketRequest.h>
+#include <aws/s3/model/GetBucketLocationRequest.h>
+#include <aws/s3/model/GetObjectRequest.h>
+#include <aws/s3/model/HeadObjectRequest.h>
+#include <aws/s3/model/PutObjectRequest.h>
+#include <aws/s3/model/ListObjectsRequest.h>
+
+namespace nix {
+
+struct S3Error : public Error
+{
+    Aws::S3::S3Errors err;
+    S3Error(Aws::S3::S3Errors err, const FormatOrString & fs)
+        : Error(fs), err(err) { };
+};
+
+/* Helper: given an Outcome<R, E>, return R in case of success, or
+   throw an exception in case of an error. */
+template<typename R, typename E>
+R && checkAws(const FormatOrString & fs, Aws::Utils::Outcome<R, E> && outcome)
+{
+    if (!outcome.IsSuccess())
+        throw S3Error(
+            outcome.GetError().GetErrorType(),
+            fs.s + ": " + outcome.GetError().GetMessage());
+    return outcome.GetResultWithOwnership();
+}
+
+struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
+{
+    std::string bucketName;
+
+    ref<Aws::Client::ClientConfiguration> config;
+    ref<Aws::S3::S3Client> client;
+
+    Stats stats;
+
+    S3BinaryCacheStoreImpl(std::shared_ptr<Store> localStore,
+        const StoreParams & params, const std::string & bucketName)
+        : S3BinaryCacheStore(localStore, params)
+        , bucketName(bucketName)
+        , config(makeConfig())
+        , client(make_ref<Aws::S3::S3Client>(*config))
+    {
+        diskCache = getNarInfoDiskCache();
+    }
+
+    std::string getUri()
+    {
+        return "s3://" + bucketName;
+    }
+
+    ref<Aws::Client::ClientConfiguration> makeConfig()
+    {
+        auto res = make_ref<Aws::Client::ClientConfiguration>();
+        res->region = Aws::Region::US_EAST_1; // FIXME: make configurable
+        res->requestTimeoutMs = 600 * 1000;
+        return res;
+    }
+
+    void init()
+    {
+        if (!diskCache->cacheExists(getUri())) {
+
+            /* Create the bucket if it doesn't already exists. */
+            // FIXME: HeadBucket would be more appropriate, but doesn't return
+            // an easily parsed 404 message.
+            auto res = client->GetBucketLocation(
+                Aws::S3::Model::GetBucketLocationRequest().WithBucket(bucketName));
+
+            if (!res.IsSuccess()) {
+                if (res.GetError().GetErrorType() != Aws::S3::S3Errors::NO_SUCH_BUCKET)
+                    throw Error(format("AWS error checking bucket ‘%s’: %s") % bucketName % res.GetError().GetMessage());
+
+                checkAws(format("AWS error creating bucket ‘%s’") % bucketName,
+                    client->CreateBucket(
+                        Aws::S3::Model::CreateBucketRequest()
+                        .WithBucket(bucketName)
+                        .WithCreateBucketConfiguration(
+                            Aws::S3::Model::CreateBucketConfiguration()
+                            /* .WithLocationConstraint(
+                               Aws::S3::Model::BucketLocationConstraint::US) */ )));
+            }
+
+            BinaryCacheStore::init();
+
+            diskCache->createCache(getUri());
+        }
+    }
+
+    const Stats & getS3Stats()
+    {
+        return stats;
+    }
+
+    /* This is a specialisation of isValidPath() that optimistically
+       fetches the .narinfo file, rather than first checking for its
+       existence via a HEAD request. Since .narinfos are small, doing
+       a GET is unlikely to be slower than HEAD. */
+    bool isValidPathUncached(const Path & storePath)
+    {
+        try {
+            queryPathInfo(storePath);
+            return true;
+        } catch (InvalidPath & e) {
+            return false;
+        }
+    }
+
+    bool fileExists(const std::string & path)
+    {
+        stats.head++;
+
+        auto res = client->HeadObject(
+            Aws::S3::Model::HeadObjectRequest()
+            .WithBucket(bucketName)
+            .WithKey(path));
+
+        if (!res.IsSuccess()) {
+            auto & error = res.GetError();
+            if (error.GetErrorType() == Aws::S3::S3Errors::UNKNOWN // FIXME
+                && error.GetMessage().find("404") != std::string::npos)
+                return false;
+            throw Error(format("AWS error fetching ‘%s’: %s") % path % error.GetMessage());
+        }
+
+        return true;
+    }
+
+    void upsertFile(const std::string & path, const std::string & data)
+    {
+        auto request =
+            Aws::S3::Model::PutObjectRequest()
+            .WithBucket(bucketName)
+            .WithKey(path);
+
+        auto stream = std::make_shared<std::stringstream>(data);
+
+        request.SetBody(stream);
+
+        stats.put++;
+        stats.putBytes += data.size();
+
+        auto now1 = std::chrono::steady_clock::now();
+
+        auto result = checkAws(format("AWS error uploading ‘%s’") % path,
+            client->PutObject(request));
+
+        auto now2 = std::chrono::steady_clock::now();
+
+        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1).count();
+
+        printMsg(lvlInfo, format("uploaded ‘s3://%1%/%2%’ (%3% bytes) in %4% ms")
+            % bucketName % path % data.size() % duration);
+
+        stats.putTimeMs += duration;
+    }
+
+    std::shared_ptr<std::string> getFile(const std::string & path)
+    {
+        debug(format("fetching ‘s3://%1%/%2%’...") % bucketName % path);
+
+        auto request =
+            Aws::S3::Model::GetObjectRequest()
+            .WithBucket(bucketName)
+            .WithKey(path);
+
+        request.SetResponseStreamFactory([&]() {
+            return Aws::New<std::stringstream>("STRINGSTREAM");
+        });
+
+        stats.get++;
+
+        try {
+
+            auto now1 = std::chrono::steady_clock::now();
+
+            auto result = checkAws(format("AWS error fetching ‘%s’") % path,
+                client->GetObject(request));
+
+            auto now2 = std::chrono::steady_clock::now();
+
+            auto res = dynamic_cast<std::stringstream &>(result.GetBody()).str();
+
+            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1).count();
+
+            printMsg(lvlTalkative, format("downloaded ‘s3://%1%/%2%’ (%3% bytes) in %4% ms")
+                % bucketName % path % res.size() % duration);
+
+            stats.getBytes += res.size();
+            stats.getTimeMs += duration;
+
+            return std::make_shared<std::string>(res);
+
+        } catch (S3Error & e) {
+            if (e.err == Aws::S3::S3Errors::NO_SUCH_KEY) return 0;
+            throw;
+        }
+    }
+
+    PathSet queryAllValidPaths() override
+    {
+        PathSet paths;
+        std::string marker;
+
+        do {
+            debug(format("listing bucket ‘s3://%s’ from key ‘%s’...") % bucketName % marker);
+
+            auto res = checkAws(format("AWS error listing bucket ‘%s’") % bucketName,
+                client->ListObjects(
+                    Aws::S3::Model::ListObjectsRequest()
+                    .WithBucket(bucketName)
+                    .WithDelimiter("/")
+                    .WithMarker(marker)));
+
+            auto & contents = res.GetContents();
+
+            debug(format("got %d keys, next marker ‘%s’")
+                % contents.size() % res.GetNextMarker());
+
+            for (auto object : contents) {
+                auto & key = object.GetKey();
+                if (key.size() != 40 || !hasSuffix(key, ".narinfo")) continue;
+                paths.insert(settings.nixStore + "/" + key.substr(0, key.size() - 8));
+            }
+
+            marker = res.GetNextMarker();
+        } while (!marker.empty());
+
+        return paths;
+    }
+
+};
+
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
+{
+    if (std::string(uri, 0, 5) != "s3://") return 0;
+    auto store = std::make_shared<S3BinaryCacheStoreImpl>(std::shared_ptr<Store>(0),
+        params, std::string(uri, 5));
+    store->init();
+    return store;
+});
+
+}
diff --git a/src/libstore/s3-binary-cache-store.hh b/src/libstore/s3-binary-cache-store.hh
new file mode 100644
index 000000000000..2751a9d01cdb
--- /dev/null
+++ b/src/libstore/s3-binary-cache-store.hh
@@ -0,0 +1,34 @@
+#pragma once
+
+#include "binary-cache-store.hh"
+
+#include <atomic>
+
+namespace nix {
+
+class S3BinaryCacheStore : public BinaryCacheStore
+{
+protected:
+
+    S3BinaryCacheStore(std::shared_ptr<Store> localStore,
+        const StoreParams & params)
+        : BinaryCacheStore(localStore, params)
+    { }
+
+public:
+
+    struct Stats
+    {
+        std::atomic<uint64_t> put{0};
+        std::atomic<uint64_t> putBytes{0};
+        std::atomic<uint64_t> putTimeMs{0};
+        std::atomic<uint64_t> get{0};
+        std::atomic<uint64_t> getBytes{0};
+        std::atomic<uint64_t> getTimeMs{0};
+        std::atomic<uint64_t> head{0};
+    };
+
+    const Stats & getS3Stats();
+};
+
+}
diff --git a/src/libstore/sqlite.cc b/src/libstore/sqlite.cc
index f93fa0857588..816f9984d6eb 100644
--- a/src/libstore/sqlite.cc
+++ b/src/libstore/sqlite.cc
@@ -139,6 +139,11 @@ int64_t SQLiteStmt::Use::getInt(int col)
     return sqlite3_column_int64(stmt, col);
 }
 
+bool SQLiteStmt::Use::isNull(int col)
+{
+    return sqlite3_column_type(stmt, col) == SQLITE_NULL;
+}
+
 SQLiteTxn::SQLiteTxn(sqlite3 * db)
 {
     this->db = db;
diff --git a/src/libstore/sqlite.hh b/src/libstore/sqlite.hh
index 326e4a4855b7..d6b4a8d9117b 100644
--- a/src/libstore/sqlite.hh
+++ b/src/libstore/sqlite.hh
@@ -58,6 +58,7 @@ struct SQLiteStmt
 
         std::string getStr(int col);
         int64_t getInt(int col);
+        bool isNull(int col);
     };
 
     Use use()
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index cc91ed287768..463e132e0299 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -2,6 +2,7 @@
 #include "globals.hh"
 #include "store-api.hh"
 #include "util.hh"
+#include "nar-info-disk-cache.hh"
 
 
 namespace nix {
@@ -16,6 +17,7 @@ bool isInStore(const Path & path)
 bool isStorePath(const Path & path)
 {
     return isInStore(path)
+        && path.size() >= settings.nixStore.size() + 1 + storePathHashLen
         && path.find('/', settings.nixStore.size() + 1) == Path::npos;
 }
 
@@ -62,13 +64,16 @@ Path followLinksToStorePath(const Path & path)
 string storePathToName(const Path & path)
 {
     assertStorePath(path);
-    return string(path, settings.nixStore.size() + storePathHashLen + 2);
+    auto l = settings.nixStore.size() + 1 + storePathHashLen;
+    assert(path.size() >= l);
+    return path.size() == l ? "" : string(path, l + 1);
 }
 
 
 string storePathToHash(const Path & path)
 {
     assertStorePath(path);
+    assert(path.size() >= settings.nixStore.size() + 1 + storePathHashLen);
     return string(path, settings.nixStore.size() + 1, storePathHashLen);
 }
 
@@ -225,10 +230,89 @@ Path computeStorePathForText(const string & name, const string & s,
 }
 
 
-void Store::queryReferences(const Path & path, PathSet & references)
+std::string Store::getUri()
 {
-    ValidPathInfo info = queryPathInfo(path);
-    references.insert(info.references.begin(), info.references.end());
+    return "";
+}
+
+
+bool Store::isValidPath(const Path & storePath)
+{
+    auto hashPart = storePathToHash(storePath);
+
+    {
+        auto state_(state.lock());
+        auto res = state_->pathInfoCache.get(hashPart);
+        if (res) {
+            stats.narInfoReadAverted++;
+            return *res != 0;
+        }
+    }
+
+    if (diskCache) {
+        auto res = diskCache->lookupNarInfo(getUri(), hashPart);
+        if (res.first != NarInfoDiskCache::oUnknown) {
+            stats.narInfoReadAverted++;
+            auto state_(state.lock());
+            state_->pathInfoCache.upsert(hashPart,
+                res.first == NarInfoDiskCache::oInvalid ? 0 : res.second);
+            return res.first == NarInfoDiskCache::oValid;
+        }
+    }
+
+    return isValidPathUncached(storePath);
+
+    // FIXME: insert result into NARExistence table of diskCache.
+}
+
+
+ref<const ValidPathInfo> Store::queryPathInfo(const Path & storePath)
+{
+    auto hashPart = storePathToHash(storePath);
+
+    {
+        auto state_(state.lock());
+        auto res = state_->pathInfoCache.get(hashPart);
+        if (res) {
+            stats.narInfoReadAverted++;
+            if (!*res)
+                throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
+            return ref<ValidPathInfo>(*res);
+        }
+    }
+
+    if (diskCache) {
+        auto res = diskCache->lookupNarInfo(getUri(), hashPart);
+        if (res.first != NarInfoDiskCache::oUnknown) {
+            stats.narInfoReadAverted++;
+            auto state_(state.lock());
+            state_->pathInfoCache.upsert(hashPart,
+                res.first == NarInfoDiskCache::oInvalid ? 0 : res.second);
+            if (res.first == NarInfoDiskCache::oInvalid ||
+                (res.second->path != storePath && storePathToName(storePath) != ""))
+                throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
+            return ref<ValidPathInfo>(res.second);
+        }
+    }
+
+    auto info = queryPathInfoUncached(storePath);
+
+    if (diskCache && info)
+        diskCache->upsertNarInfo(getUri(), hashPart, info);
+
+    {
+        auto state_(state.lock());
+        state_->pathInfoCache.upsert(hashPart, info);
+    }
+
+    if (!info
+        || (info->path != storePath && storePathToName(storePath) != ""))
+    {
+        stats.narInfoMissing++;
+        throw InvalidPath(format("path ‘%s’ is not valid") % storePath);
+    }
+
+    return ref<ValidPathInfo>(info);
 }
 
 
@@ -243,19 +327,19 @@ string Store::makeValidityRegistration(const PathSet & paths,
     for (auto & i : paths) {
         s += i + "\n";
 
-        ValidPathInfo info = queryPathInfo(i);
+        auto info = queryPathInfo(i);
 
         if (showHash) {
-            s += printHash(info.narHash) + "\n";
-            s += (format("%1%\n") % info.narSize).str();
+            s += printHash(info->narHash) + "\n";
+            s += (format("%1%\n") % info->narSize).str();
         }
 
-        Path deriver = showDerivers ? info.deriver : "";
+        Path deriver = showDerivers ? info->deriver : "";
         s += deriver + "\n";
 
-        s += (format("%1%\n") % info.references.size()).str();
+        s += (format("%1%\n") % info->references.size()).str();
 
-        for (auto & j : info.references)
+        for (auto & j : info->references)
             s += j + "\n";
     }
 
@@ -263,6 +347,16 @@ string Store::makeValidityRegistration(const PathSet & paths,
 }
 
 
+const Store::Stats & Store::getStats()
+{
+    {
+        auto state_(state.lock());
+        stats.pathInfoCacheSize = state_->pathInfoCache.size();
+    }
+    return stats;
+}
+
+
 ValidPathInfo decodeValidPathInfo(std::istream & str, bool hashGiven)
 {
     ValidPathInfo info;
@@ -312,7 +406,7 @@ void Store::exportPaths(const Paths & paths,
 
 std::string ValidPathInfo::fingerprint() const
 {
-    if (narSize == 0 || narHash.type == htUnknown)
+    if (narSize == 0 || !narHash)
         throw Error(format("cannot calculate fingerprint of path ‘%s’ because its size/hash is not known")
             % path);
     return
@@ -345,6 +439,15 @@ bool ValidPathInfo::checkSignature(const PublicKeys & publicKeys, const std::str
 }
 
 
+Strings ValidPathInfo::shortRefs() const
+{
+    Strings refs;
+    for (auto & r : references)
+        refs.push_back(baseNameOf(r));
+    return refs;
+}
+
+
 }
 
 
@@ -358,10 +461,22 @@ namespace nix {
 RegisterStoreImplementation::Implementations * RegisterStoreImplementation::implementations = 0;
 
 
-ref<Store> openStoreAt(const std::string & uri)
+ref<Store> openStoreAt(const std::string & uri_)
 {
+    auto uri(uri_);
+    StoreParams params;
+    auto q = uri.find('?');
+    if (q != std::string::npos) {
+        for (auto s : tokenizeString<Strings>(uri.substr(q + 1), "&")) {
+            auto e = s.find('=');
+            if (e != std::string::npos)
+                params[s.substr(0, e)] = s.substr(e + 1);
+        }
+        uri = uri_.substr(0, q);
+    }
+
     for (auto fun : *RegisterStoreImplementation::implementations) {
-        auto store = fun(uri);
+        auto store = fun(uri, params);
         if (store) return ref<Store>(store);
     }
 
@@ -375,7 +490,10 @@ ref<Store> openStore()
 }
 
 
-static RegisterStoreImplementation regStore([](const std::string & uri) -> std::shared_ptr<Store> {
+static RegisterStoreImplementation regStore([](
+    const std::string & uri, const StoreParams & params)
+    -> std::shared_ptr<Store>
+{
     enum { mDaemon, mLocal, mAuto } mode;
 
     if (uri == "daemon") mode = mDaemon;
@@ -398,4 +516,39 @@ static RegisterStoreImplementation regStore([](const std::string & uri) -> std::
 });
 
 
+std::list<ref<Store>> getDefaultSubstituters()
+{
+    struct State {
+        bool done = false;
+        std::list<ref<Store>> stores;
+    };
+    static Sync<State> state_;
+
+    auto state(state_.lock());
+
+    if (state->done) return state->stores;
+
+    StringSet done;
+
+    auto addStore = [&](const std::string & uri) {
+        if (done.count(uri)) return;
+        done.insert(uri);
+        state->stores.push_back(openStoreAt(uri));
+    };
+
+    for (auto uri : settings.get("substituters", Strings()))
+        addStore(uri);
+
+    for (auto uri : settings.get("binary-caches", Strings()))
+        addStore(uri);
+
+    for (auto uri : settings.get("extra-binary-caches", Strings()))
+        addStore(uri);
+
+    state->done = true;
+
+    return state->stores;
+}
+
+
 }
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 8827654fafdd..29685c9d1676 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -3,11 +3,14 @@
 #include "hash.hh"
 #include "serialise.hh"
 #include "crypto.hh"
+#include "lru-cache.hh"
+#include "sync.hh"
 
-#include <string>
+#include <atomic>
 #include <limits>
 #include <map>
 #include <memory>
+#include <string>
 
 
 namespace nix {
@@ -130,6 +133,10 @@ struct ValidPathInfo
 
     /* Verify a single signature. */
     bool checkSignature(const PublicKeys & publicKeys, const std::string & sig) const;
+
+    Strings shortRefs() const;
+
+    virtual ~ValidPathInfo() { }
 };
 
 typedef list<ValidPathInfo> ValidPathInfos;
@@ -165,42 +172,62 @@ struct BuildResult
 struct BasicDerivation;
 struct Derivation;
 class FSAccessor;
+class NarInfoDiskCache;
 
 
 class Store : public std::enable_shared_from_this<Store>
 {
+protected:
+
+    struct State
+    {
+        LRUCache<std::string, std::shared_ptr<ValidPathInfo>> pathInfoCache{64 * 1024};
+    };
+
+    Sync<State> state;
+
+    std::shared_ptr<NarInfoDiskCache> diskCache;
+
 public:
 
     virtual ~Store() { }
 
+    virtual std::string getUri() = 0;
+
     /* Check whether a path is valid. */
-    virtual bool isValidPath(const Path & path) = 0;
+    bool isValidPath(const Path & path);
+
+protected:
+
+    virtual bool isValidPathUncached(const Path & path) = 0;
+
+public:
 
     /* Query which of the given paths is valid. */
     virtual PathSet queryValidPaths(const PathSet & paths) = 0;
 
-    /* Query the set of all valid paths. */
+    /* Query the set of all valid paths. Note that for some store
+       backends, the name part of store paths may be omitted
+       (i.e. you'll get /nix/store/<hash> rather than
+       /nix/store/<hash>-<name>). Use queryPathInfo() to obtain the
+       full store path. */
     virtual PathSet queryAllValidPaths() = 0;
 
-    /* Query information about a valid path. */
-    virtual ValidPathInfo queryPathInfo(const Path & path) = 0;
+    /* Query information about a valid path. It is permitted to omit
+       the name part of the store path. */
+    ref<const ValidPathInfo> queryPathInfo(const Path & path);
+
+protected:
 
-    /* Query the hash of a valid path. */
-    virtual Hash queryPathHash(const Path & path) = 0;
+    virtual std::shared_ptr<ValidPathInfo> queryPathInfoUncached(const Path & path) = 0;
 
-    /* Query the set of outgoing FS references for a store path. The
-       result is not cleared. */
-    virtual void queryReferences(const Path & path, PathSet & references);
+public:
 
     /* Queries the set of incoming FS references for a store path.
        The result is not cleared. */
     virtual void queryReferrers(const Path & path,
         PathSet & referrers) = 0;
 
-    /* Query the deriver of a store path.  Return the empty string if
-       no deriver has been set. */
-    virtual Path queryDeriver(const Path & path) = 0;
-
     /* Return all currently valid derivations that have `path' as an
        output.  (Note that the result of `queryDeriver()' is the
        derivation that was actually used to produce `path', which may
@@ -373,6 +400,29 @@ public:
        relation.  If p refers to q, then p preceeds q in this list. */
     Paths topoSortPaths(const PathSet & paths);
 
+    struct Stats
+    {
+        std::atomic<uint64_t> narInfoRead{0};
+        std::atomic<uint64_t> narInfoReadAverted{0};
+        std::atomic<uint64_t> narInfoMissing{0};
+        std::atomic<uint64_t> narInfoWrite{0};
+        std::atomic<uint64_t> pathInfoCacheSize{0};
+        std::atomic<uint64_t> narRead{0};
+        std::atomic<uint64_t> narReadBytes{0};
+        std::atomic<uint64_t> narReadCompressedBytes{0};
+        std::atomic<uint64_t> narWrite{0};
+        std::atomic<uint64_t> narWriteAverted{0};
+        std::atomic<uint64_t> narWriteBytes{0};
+        std::atomic<uint64_t> narWriteCompressedBytes{0};
+        std::atomic<uint64_t> narWriteCompressionTimeMs{0};
+    };
+
+    const Stats & getStats();
+
+protected:
+
+    Stats stats;
+
 };
 
 
@@ -479,12 +529,17 @@ ref<Store> openStoreAt(const std::string & uri);
 ref<Store> openStore();
 
 
-ref<Store> openLocalBinaryCacheStore(std::shared_ptr<Store> localStore,
-    const Path & secretKeyFile, const Path & binaryCacheDir);
+/* Return the default substituter stores, defined by the
+   ‘substituters’ option and various legacy options like
+   ‘binary-caches’. */
+std::list<ref<Store>> getDefaultSubstituters();
 
 
 /* Store implementation registration. */
-typedef std::function<std::shared_ptr<Store>(const std::string & uri)> OpenStore;
+typedef std::map<std::string, std::string> StoreParams;
+
+typedef std::function<std::shared_ptr<Store>(
+    const std::string & uri, const StoreParams & params)> OpenStore;
 
 struct RegisterStoreImplementation
 {
diff --git a/src/libstore/worker-protocol.hh b/src/libstore/worker-protocol.hh
index c10598d5d301..d133328d1e76 100644
--- a/src/libstore/worker-protocol.hh
+++ b/src/libstore/worker-protocol.hh
@@ -6,7 +6,7 @@ namespace nix {
 #define WORKER_MAGIC_1 0x6e697863
 #define WORKER_MAGIC_2 0x6478696f
 
-#define PROTOCOL_VERSION 0x110
+#define PROTOCOL_VERSION 0x111
 #define GET_PROTOCOL_MAJOR(x) ((x) & 0xff00)
 #define GET_PROTOCOL_MINOR(x) ((x) & 0x00ff)
 
@@ -14,8 +14,8 @@ namespace nix {
 typedef enum {
     wopIsValidPath = 1,
     wopHasSubstitutes = 3,
-    wopQueryPathHash = 4,
-    wopQueryReferences = 5,
+    wopQueryPathHash = 4, // obsolete
+    wopQueryReferences = 5, // obsolete
     wopQueryReferrers = 6,
     wopAddToStore = 7,
     wopAddTextToStore = 8,
@@ -26,7 +26,7 @@ typedef enum {
     wopSyncWithGC = 13,
     wopFindRoots = 14,
     wopExportPath = 16,
-    wopQueryDeriver = 18,
+    wopQueryDeriver = 18, // obsolete
     wopSetOptions = 19,
     wopCollectGarbage = 20,
     wopQuerySubstitutablePathInfo = 21,