Release 4.3.0 (#327)

Initial release of Firestore at 0.8.0
Bump FirebaseCommunity to 0.1.3

50 files changed, 6960 insertions, 0 deletions

diff --git a/Firestore/Source/Local/FSTDocumentReference.h b/Firestore/Source/Local/FSTDocumentReference.h
new file mode 100644
index 0000000..eff60e4
--- /dev/null
+++ b/Firestore/Source/Local/FSTDocumentReference.h
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+@class FSTDocumentKey;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * An immutable value used to keep track of an association between some referencing target or batch
+ * and a document key that the target or batch references.
+ *
+ * A reference can be from either listen targets (identified by their FSTTargetID) or mutation
+ * batches (identified by their FSTBatchID). See FSTGarbageCollector for more details.
+ *
+ * Not to be confused with FIRDocumentReference.
+ */
+@interface FSTDocumentReference : NSObject <NSCopying>
+
+/** Initializes the document reference with the given key and ID. */
+- (instancetype)initWithKey:(FSTDocumentKey *)key ID:(int)ID NS_DESIGNATED_INITIALIZER;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** The document key that's the target of this reference. */
+@property(nonatomic, strong, readonly) FSTDocumentKey *key;
+
+/**
+ * The targetID of a referring target or the batchID of a referring mutation batch. (Which this
+ * is depends upon which FSTReferenceSet this reference is a part of.)
+ */
+@property(nonatomic, assign, readonly) int ID;
+
+@end
+
+#pragma mark Comparators
+
+/** Sorts document references by key then ID. */
+extern const NSComparator FSTDocumentReferenceComparatorByKey;
+
+/** Sorts document references by ID then key. */
+extern const NSComparator FSTDocumentReferenceComparatorByID;
+
+/** A callback for use when enumerating an FSTImmutableSortedSet of FSTDocumentReferences. */
+typedef void (^FSTDocumentReferenceBlock)(FSTDocumentReference *reference, BOOL *stop);
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTDocumentReference.m b/Firestore/Source/Local/FSTDocumentReference.m
new file mode 100644
index 0000000..7d9e3db
--- /dev/null
+++ b/Firestore/Source/Local/FSTDocumentReference.m
@@ -0,0 +1,83 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTDocumentReference.h"
+
+#import "FSTComparison.h"
+#import "FSTDocumentKey.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTDocumentReference
+
+- (instancetype)initWithKey:(FSTDocumentKey *)key ID:(int)ID {
+  self = [super init];
+  if (self) {
+    _key = key;
+    _ID = ID;
+  }
+  return self;
+}
+
+- (BOOL)isEqual:(id)other {
+  if (other == self) return YES;
+  if (!other || ![[other class] isEqual:[self class]]) return NO;
+
+  FSTDocumentReference *reference = (FSTDocumentReference *)other;
+
+  return [self.key isEqualToKey:reference.key] && self.ID == reference.ID;
+}
+
+- (NSUInteger)hash {
+  NSUInteger result = [self.key hash];
+  result = result * 31u + self.ID;
+  return result;
+}
+
+- (NSString *)description {
+  return [NSString stringWithFormat:@"<FSTDocumentReference: key=%@, ID=%d>", self.key, self.ID];
+}
+
+- (id)copyWithZone:(nullable NSZone *)zone {
+  // FSTDocumentReference is immutable
+  return self;
+}
+
+@end
+
+#pragma mark Comparators
+
+/** Sorts document references by key then ID. */
+const NSComparator FSTDocumentReferenceComparatorByKey =
+    ^NSComparisonResult(FSTDocumentReference *left, FSTDocumentReference *right) {
+      NSComparisonResult result = FSTDocumentKeyComparator(left.key, right.key);
+      if (result != NSOrderedSame) {
+        return result;
+      }
+      return FSTCompareInts(left.ID, right.ID);
+    };
+
+/** Sorts document references by ID then key. */
+const NSComparator FSTDocumentReferenceComparatorByID =
+    ^NSComparisonResult(FSTDocumentReference *left, FSTDocumentReference *right) {
+      NSComparisonResult result = FSTCompareInts(left.ID, right.ID);
+      if (result != NSOrderedSame) {
+        return result;
+      }
+      return FSTDocumentKeyComparator(left.key, right.key);
+    };
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTEagerGarbageCollector.h b/Firestore/Source/Local/FSTEagerGarbageCollector.h
new file mode 100644
index 0000000..f2f373c
--- /dev/null
+++ b/Firestore/Source/Local/FSTEagerGarbageCollector.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTGarbageCollector.h"
+
+@class FSTDocumentKey;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * A garbage collector implementation that eagerly collects documents as soon as they're no longer
+ * referenced in any of its registered FSTGarbageSources.
+ *
+ * This implementation keeps track of a set of keys that are potentially garbage without keeping
+ * an exact reference count. During -collectGarbage, the collector verifies that all potential
+ * garbage keys actually have no references by consulting its list of garbage sources.
+ */
+@interface FSTEagerGarbageCollector : NSObject <FSTGarbageCollector>
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTEagerGarbageCollector.m b/Firestore/Source/Local/FSTEagerGarbageCollector.m
new file mode 100644
index 0000000..971f368
--- /dev/null
+++ b/Firestore/Source/Local/FSTEagerGarbageCollector.m
@@ -0,0 +1,89 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTEagerGarbageCollector.h"
+
+#import "FSTDocumentKey.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTMultiReferenceSet
+
+@interface FSTEagerGarbageCollector ()
+
+/** The garbage collectible sources to double-check during garbage collection. */
+@property(nonatomic, strong, readonly) NSMutableArray<id<FSTGarbageSource>> *sources;
+
+/** A set of potentially garbage keys. */
+@property(nonatomic, strong, readonly) NSMutableSet<FSTDocumentKey *> *potentialGarbage;
+
+@end
+
+@implementation FSTEagerGarbageCollector
+
+- (instancetype)init {
+  self = [super init];
+  if (self) {
+    _sources = [NSMutableArray array];
+    _potentialGarbage = [[NSMutableSet alloc] init];
+  }
+  return self;
+}
+
+- (BOOL)isEager {
+  return YES;
+}
+
+- (void)addGarbageSource:(id<FSTGarbageSource>)garbageSource {
+  [self.sources addObject:garbageSource];
+  garbageSource.garbageCollector = self;
+}
+
+- (void)removeGarbageSource:(id<FSTGarbageSource>)garbageSource {
+  [self.sources removeObject:garbageSource];
+  garbageSource.garbageCollector = nil;
+}
+
+- (void)addPotentialGarbageKey:(FSTDocumentKey *)key {
+  [self.potentialGarbage addObject:key];
+}
+
+- (NSMutableSet<FSTDocumentKey *> *)collectGarbage {
+  NSMutableArray<id<FSTGarbageSource>> *sources = self.sources;
+
+  NSMutableSet<FSTDocumentKey *> *actualGarbage = [NSMutableSet set];
+  for (FSTDocumentKey *key in self.potentialGarbage) {
+    BOOL isGarbage = YES;
+    for (id<FSTGarbageSource> source in sources) {
+      if ([source containsKey:key]) {
+        isGarbage = NO;
+        break;
+      }
+    }
+
+    if (isGarbage) {
+      [actualGarbage addObject:key];
+    }
+  }
+
+  // Clear locally retained potential keys and returned confirmed garbage.
+  [self.potentialGarbage removeAllObjects];
+  return actualGarbage;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTGarbageCollector.h b/Firestore/Source/Local/FSTGarbageCollector.h
new file mode 100644
index 0000000..c999f66
--- /dev/null
+++ b/Firestore/Source/Local/FSTGarbageCollector.h
@@ -0,0 +1,95 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTTypes.h"
+
+@class FSTDocumentKey;
+@class FSTDocumentReference;
+@protocol FSTGarbageCollector;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * A pseudo-collection that maintains references to documents. FSTGarbageSource collections
+ * notify the FSTGarbageCollector when references to documents change through the
+ * -addPotentialGarbageKey: message.
+ */
+@protocol FSTGarbageSource
+
+/**
+ * The garbage collector to which this collection should send -addPotentialGarbageKey: messages.
+ */
+@property(nonatomic, weak, readwrite, nullable) id<FSTGarbageCollector> garbageCollector;
+
+/**
+ * Checks to see if there are any references to a document with the given key. This can be used by
+ * garbage collectors to double-check if a key exists in this collection when it was released
+ * elsewhere.
+ */
+- (BOOL)containsKey:(FSTDocumentKey *)key;
+
+@end
+
+/**
+ * Tracks different kinds of references to a document, for all the different ways the client
+ * needs to retain a document.
+ *
+ * Usually the local store this means tracking of three different types of references to a
+ * document:
+ * 1. RemoteTarget reference identified by a target ID.
+ * 2. LocalView reference identified also by a target ID.
+ * 3. Local mutation reference identified by a batch ID.
+ *
+ * The idea is that we want to keep a document around at least as long as any remote target or
+ * local (latency compensated) view is referencing it, or there's an outstanding local mutation to
+ * that document.
+ */
+@protocol FSTGarbageCollector
+
+/**
+ * A property that describes whether or not the collector wants to eagerly collect keys.
+ *
+ * TODO(b/33384523) Delegate deleting released queries to the GC.
+ * This flag is a temporary workaround for dealing with a persistent query cache. The collector
+ * really should have an API for releasing queries that does the right thing for its policy.
+ */
+@property(nonatomic, assign, readonly, getter=isEager) BOOL eager;
+
+/** Adds a garbage source to the collector. */
+- (void)addGarbageSource:(id<FSTGarbageSource>)garbageSource;
+
+/** Removes a garbage source from the collector. */
+- (void)removeGarbageSource:(id<FSTGarbageSource>)garbageSource;
+
+/**
+ * Notifies the garbage collector that a document with the given key may have become garbage.
+ *
+ * This is useful in both when a document has definitely been released (for example when removed
+ * from a garbage source) but also when a document has been updated. Documents should be marked in
+ * this way because the client accepts updates for documents even after the document no longer
+ * matches any active targets. This behavior allows the client to avoid re-showing an old document
+ * in the next latency-compensated view.
+ */
+- (void)addPotentialGarbageKey:(FSTDocumentKey *)key;
+
+/** Returns the contents of the garbage bin and clears it. */
+- (NSSet<FSTDocumentKey *> *)collectGarbage;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDB.h b/Firestore/Source/Local/FSTLevelDB.h
new file mode 100644
index 0000000..a2c838d
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDB.h
@@ -0,0 +1,105 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTPersistence.h"
+
+#ifdef __cplusplus
+#include <memory>
+
+namespace leveldb {
+class DB;
+class Status;
+}
+#endif
+
+@class FSTDatabaseInfo;
+@class FSTLocalSerializer;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** A LevelDB-backed instance of FSTPersistence. */
+// TODO(mikelehen): Rename to FSTLevelDBPersistence.
+@interface FSTLevelDB : NSObject <FSTPersistence>
+
+/**
+ * Initializes the LevelDB in the given directory. Note that all expensive startup work including
+ * opening any database files is deferred until -[FSTPersistence start] is called.
+ */
+- (instancetype)initWithDirectory:(NSString *)directory
+                       serializer:(FSTLocalSerializer *)serializer NS_DESIGNATED_INITIALIZER;
+
+- (instancetype)init __attribute__((unavailable("Use -initWithDirectory: instead.")));
+
+/** Finds a suitable directory to serve as the root of all Firestore local storage. */
++ (NSString *)documentsDirectory;
+
+/**
+ * Computes a unique storage directory for the given identifying components of local storage.
+ *
+ * @param databaseInfo The identifying information for the local storage instance.
+ * @param documentsDirectory The root document directory relative to which the storage directory
+ *     will be created. Usually just +[FSTLevelDB documentsDir].
+ * @return A storage directory unique to the instance identified by databaseInfo.
+ */
++ (NSString *)storageDirectoryForDatabaseInfo:(FSTDatabaseInfo *)databaseInfo
+                           documentsDirectory:(NSString *)documentsDirectory;
+
+/**
+ * Starts LevelDB-backed persistent storage by opening the database files, creating the DB if it
+ * does not exist.
+ *
+ * The leveldb directory is created relative to the appropriate document storage directory for the
+ * platform: NSDocumentDirectory on iOS or $HOME/.firestore on macOS.
+ */
+- (BOOL)start:(NSError **)error;
+
+#ifdef __cplusplus
+// What follows is the Objective-C++ extension to the API.
+
+/**
+ * Creates an NSError based on the given status if the status is not ok.
+ *
+ * @param status The status of the preceding LevelDB operation.
+ * @param description A printf-style format string describing what kind of failure happened if
+ *     @a status is not ok. Additional parameters are substituted into the placeholders in this
+ *     format string.
+ *
+ * @return An NSError with its localizedDescription composed from the description format and its
+ *     localizedFailureReason composed from any error message embedded in @a status.
+ */
++ (nullable NSError *)errorWithStatus:(leveldb::Status)status
+                          description:(NSString *)description, ... NS_FORMAT_FUNCTION(2, 3);
+
+/**
+ * Converts the given @a status to an NSString describing the status condition, suitable for
+ * logging or inclusion in an NSError.
+ *
+ * @param status The status of the preceding LevelDB operation.
+ *
+ * @return An NSString describing the status (even if the status was ok).
+ */
++ (NSString *)descriptionOfStatus:(leveldb::Status)status;
+
+/** The native db pointer, allocated during start. */
+@property(nonatomic, assign, readonly) std::shared_ptr<leveldb::DB> ptr;
+
+#endif
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDB.mm b/Firestore/Source/Local/FSTLevelDB.mm
new file mode 100644
index 0000000..81e1064
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDB.mm
@@ -0,0 +1,246 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLevelDB.h"
+
+#include <leveldb/db.h>
+
+#import "FIRFirestoreErrors.h"
+#import "FSTAssert.h"
+#import "FSTDatabaseID.h"
+#import "FSTDatabaseInfo.h"
+#import "FSTLevelDBMutationQueue.h"
+#import "FSTLevelDBQueryCache.h"
+#import "FSTLevelDBRemoteDocumentCache.h"
+#import "FSTLogger.h"
+#import "FSTSerializerBeta.h"
+#import "FSTWriteGroup.h"
+#import "FSTWriteGroupTracker.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+static NSString *const kReservedPathComponent = @"firestore";
+
+using leveldb::DB;
+using leveldb::Options;
+using leveldb::Status;
+using leveldb::WriteOptions;
+
+@interface FSTLevelDB ()
+
+@property(nonatomic, copy) NSString *directory;
+@property(nonatomic, strong) FSTWriteGroupTracker *writeGroupTracker;
+@property(nonatomic, assign, getter=isStarted) BOOL started;
+@property(nonatomic, strong, readonly) FSTLocalSerializer *serializer;
+
+@end
+
+@implementation FSTLevelDB
+
+- (instancetype)initWithDirectory:(NSString *)directory
+                       serializer:(FSTLocalSerializer *)serializer {
+  if (self = [super init]) {
+    _directory = [directory copy];
+    _writeGroupTracker = [FSTWriteGroupTracker tracker];
+    _serializer = serializer;
+  }
+  return self;
+}
+
++ (NSString *)documentsDirectory {
+#if TARGET_OS_IPHONE
+  NSArray<NSString *> *directories =
+      NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES);
+  return [directories[0] stringByAppendingPathComponent:kReservedPathComponent];
+
+#elif TARGET_OS_MAC
+  NSString *dotPrefixed = [@"." stringByAppendingString:kReservedPathComponent];
+  return [NSHomeDirectory() stringByAppendingPathComponent:dotPrefixed];
+
+#else
+#error "local storage on tvOS"
+// TODO(mcg): Writing to NSDocumentsDirectory on tvOS will fail; we need to write to Caches
+// https://developer.apple.com/library/content/documentation/General/Conceptual/AppleTV_PG/
+
+#endif
+}
+
++ (NSString *)storageDirectoryForDatabaseInfo:(FSTDatabaseInfo *)databaseInfo
+                           documentsDirectory:(NSString *)documentsDirectory {
+  // Use two different path formats:
+  //
+  //   * persistenceKey / projectID . databaseID / name
+  //   * persistenceKey / projectID / name
+  //
+  // projectIDs are DNS-compatible names and cannot contain dots so there's
+  // no danger of collisions.
+  NSString *directory = documentsDirectory;
+  directory = [directory stringByAppendingPathComponent:databaseInfo.persistenceKey];
+
+  NSString *segment = databaseInfo.databaseID.projectID;
+  if (![databaseInfo.databaseID isDefaultDatabase]) {
+    segment = [NSString stringWithFormat:@"%@.%@", segment, databaseInfo.databaseID.databaseID];
+  }
+  directory = [directory stringByAppendingPathComponent:segment];
+
+  // Reserve one additional path component to allow multiple physical databases
+  directory = [directory stringByAppendingPathComponent:@"main"];
+  return directory;
+}
+
+#pragma mark - Startup
+
+- (BOOL)start:(NSError **)error {
+  FSTAssert(!self.isStarted, @"FSTLevelDB double-started!");
+  self.started = YES;
+  NSString *directory = self.directory;
+  if (![self ensureDirectory:directory error:error]) {
+    return NO;
+  }
+
+  DB *database = [self createDBWithDirectory:directory error:error];
+  if (!database) {
+    return NO;
+  }
+
+  _ptr.reset(database);
+  return YES;
+}
+
+/** Creates the directory at @a directory and marks it as excluded from iCloud backup. */
+- (BOOL)ensureDirectory:(NSString *)directory error:(NSError **)error {
+  NSError *localError;
+  NSFileManager *files = [NSFileManager defaultManager];
+
+  BOOL success = [files createDirectoryAtPath:directory
+                  withIntermediateDirectories:YES
+                                   attributes:nil
+                                        error:&localError];
+  if (!success) {
+    *error =
+        [NSError errorWithDomain:FIRFirestoreErrorDomain
+                            code:FIRFirestoreErrorCodeInternal
+                        userInfo:@{
+                          NSLocalizedDescriptionKey : @"Failed to create persistence directory",
+                          NSUnderlyingErrorKey : localError
+                        }];
+    return NO;
+  }
+
+  NSURL *dirURL = [NSURL fileURLWithPath:directory];
+  success = [dirURL setResourceValue:@YES forKey:NSURLIsExcludedFromBackupKey error:&localError];
+  if (!success) {
+    *error = [NSError errorWithDomain:FIRFirestoreErrorDomain
+                                 code:FIRFirestoreErrorCodeInternal
+                             userInfo:@{
+                               NSLocalizedDescriptionKey :
+                                   @"Failed mark persistence directory as excluded from backups",
+                               NSUnderlyingErrorKey : localError
+                             }];
+    return NO;
+  }
+
+  return YES;
+}
+
+/** Opens the database within the given directory. */
+- (nullable DB *)createDBWithDirectory:(NSString *)directory error:(NSError **)error {
+  Options options;
+  options.create_if_missing = true;
+
+  DB *database;
+  Status status = DB::Open(options, [directory UTF8String], &database);
+  if (!status.ok()) {
+    if (error) {
+      NSString *name = [directory lastPathComponent];
+      *error =
+          [FSTLevelDB errorWithStatus:status
+                          description:@"Failed to create database %@ at path %@", name, directory];
+    }
+    return nullptr;
+  }
+
+  return database;
+}
+
+#pragma mark - Persistence Factory methods
+
+- (id<FSTMutationQueue>)mutationQueueForUser:(FSTUser *)user {
+  return [FSTLevelDBMutationQueue mutationQueueWithUser:user db:_ptr serializer:self.serializer];
+}
+
+- (id<FSTQueryCache>)queryCache {
+  return [[FSTLevelDBQueryCache alloc] initWithDB:_ptr serializer:self.serializer];
+}
+
+- (id<FSTRemoteDocumentCache>)remoteDocumentCache {
+  return [[FSTLevelDBRemoteDocumentCache alloc] initWithDB:_ptr serializer:self.serializer];
+}
+
+- (FSTWriteGroup *)startGroupWithAction:(NSString *)action {
+  return [self.writeGroupTracker startGroupWithAction:action];
+}
+
+- (void)commitGroup:(FSTWriteGroup *)group {
+  [self.writeGroupTracker endGroup:group];
+
+  NSString *description = [group description];
+  FSTLog(@"Committing %@", description);
+
+  Status status = [group writeToDB:_ptr];
+  if (!status.ok()) {
+    FSTFail(@"%@ failed with status: %s, description: %@", group.action, status.ToString().c_str(),
+            description);
+  }
+}
+
+- (void)shutdown {
+  FSTAssert(self.isStarted, @"FSTLevelDB shutdown without start!");
+  self.started = NO;
+  _ptr.reset();
+}
+
+#pragma mark - Error and Status
+
++ (nullable NSError *)errorWithStatus:(Status)status description:(NSString *)description, ... {
+  if (status.ok()) {
+    return nil;
+  }
+
+  va_list args;
+  va_start(args, description);
+
+  NSString *message = [[NSString alloc] initWithFormat:description arguments:args];
+  NSString *reason = [self descriptionOfStatus:status];
+  NSError *result = [NSError errorWithDomain:FIRFirestoreErrorDomain
+                                        code:FIRFirestoreErrorCodeInternal
+                                    userInfo:@{
+                                      NSLocalizedDescriptionKey : message,
+                                      NSLocalizedFailureReasonErrorKey : reason
+                                    }];
+
+  va_end(args);
+
+  return result;
+}
+
++ (NSString *)descriptionOfStatus:(Status)status {
+  return [NSString stringWithCString:status.ToString().c_str() encoding:NSUTF8StringEncoding];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBKey.h b/Firestore/Source/Local/FSTLevelDBKey.h
new file mode 100644
index 0000000..bad7829
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBKey.h
@@ -0,0 +1,344 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __cplusplus
+#error "FSTLevelDBKey is Objective-C++ and can only be included from .mm files"
+#endif
+
+#import <Foundation/Foundation.h>
+
+#import "FSTTypes.h"
+
+#import "StringView.h"
+
+@class FSTDocumentKey;
+@class FSTResourcePath;
+
+NS_ASSUME_NONNULL_BEGIN
+
+// All leveldb logical tables should have their keys structures described in this file.
+//
+// mutations:
+//   - tableName: string = "mutation"
+//   - userID: string
+//   - batchID: FSTBatchID
+//
+// document_mutations:
+//   - tableName: string = "document_mutation"
+//   - userID: string
+//   - path: FSTResourcePath
+//   - batchID: FSTBatchID
+//
+// mutation_queues:
+//   - tableName: string = "mutation_queue"
+//   - userID: string
+//
+// targets:
+//   - tableName: string = "target"
+//   - targetId: FSTTargetID
+//
+// target_globals:
+//   - tableName: string = "target_global"
+//
+// query_targets:
+//   - tableName: string = "query_target"
+//   - canonicalID: string
+//   - targetId: FSTTargetID
+//
+// target_documents:
+//   - tableName: string = "target_document"
+//   - targetID: FSTTargetID
+//   - path: FSTResourcePath
+//
+// document_targets:
+//   - tableName: string = "document_target"
+//   - path: FSTResourcePath
+//   - targetID: FSTTargetID
+//
+// remote_documents:
+//   - tableName: string = "remote_document"
+//   - path: FSTResourcePath
+
+/** Helpers for any LevelDB key. */
+@interface FSTLevelDBKey : NSObject
+
+/**
+ * Parses the given key and returns a human readable description of its contents, suitable for
+ * error messages and logging.
+ */
++ (NSString *)descriptionForKey:(Firestore::StringView)key;
+
+@end
+
+/** A key in the mutations table. */
+@interface FSTLevelDBMutationKey : NSObject
+
+/** Creates a key prefix that points just before the first key in the table. */
++ (std::string)keyPrefix;
+
+/** Creates a key prefix that points just before the first key for the given userID. */
++ (std::string)keyPrefixWithUserID:(Firestore::StringView)userID;
+
+/** Creates a complete key that points to a specific userID and batchID. */
++ (std::string)keyWithUserID:(Firestore::StringView)userID batchID:(FSTBatchID)batchID;
+
+/**
+ * Decodes the given complete key, storing the decoded values as properties of the receiver.
+ *
+ * @return YES if the key successfully decoded, NO otherwise. If NO is returned, the properties of
+ *     the receiver are in an undefined state until the next call to -decodeKey:.
+ */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+/** The user that owns the mutation batches. */
+@property(nonatomic, assign, readonly) const std::string &userID;
+
+/** The batchID of the batch. */
+@property(nonatomic, assign, readonly) FSTBatchID batchID;
+
+@end
+
+/**
+ * A key in the document mutations index, which stores the batches in which documents are mutated.
+ */
+@interface FSTLevelDBDocumentMutationKey : NSObject
+
+/** Creates a key prefix that points just before the first key in the table. */
++ (std::string)keyPrefix;
+
+/** Creates a key prefix that points just before the first key for the given userID. */
++ (std::string)keyPrefixWithUserID:(Firestore::StringView)userID;
+
+/**
+ * Creates a key prefix that points just before the first key for the userID and resource path.
+ *
+ * Note that this uses an FSTResourcePath rather than an FSTDocumentKey in order to allow prefix
+ * scans over a collection. However a naive scan over those results isn't useful since it would
+ * match both immediate children of the collection and any subcollections.
+ */
++ (std::string)keyPrefixWithUserID:(Firestore::StringView)userID
+                      resourcePath:(FSTResourcePath *)resourcePath;
+
+/** Creates a complete key that points to a specific userID, document key, and batchID. */
++ (std::string)keyWithUserID:(Firestore::StringView)userID
+                 documentKey:(FSTDocumentKey *)documentKey
+                     batchID:(FSTBatchID)batchID;
+
+/**
+ * Decodes the given complete key, storing the decoded values as properties of the receiver.
+ *
+ * @return YES if the key successfully decoded, NO otherwise. If NO is returned, the properties of
+ *     the receiver are in an undefined state until the next call to -decodeKey:.
+ */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+/** The user that owns the mutation batches. */
+@property(nonatomic, assign, readonly) const std::string &userID;
+
+/** The path to the document, as encoded in the key. */
+@property(nonatomic, strong, readonly, nullable) FSTDocumentKey *documentKey;
+
+/** The batchID in which the document participates. */
+@property(nonatomic, assign, readonly) FSTBatchID batchID;
+
+@end
+
+/**
+ * A key in the mutation_queues table.
+ *
+ * Note that where mutation_queues contains one row about each queue, mutations contains the actual
+ * mutation batches themselves.
+ */
+@interface FSTLevelDBMutationQueueKey : NSObject
+
+/** Creates a key prefix that points just before the first key in the table. */
++ (std::string)keyPrefix;
+
+/** Creates a complete key that points to a specific mutation queue entry for the given userID. */
++ (std::string)keyWithUserID:(Firestore::StringView)userID;
+
+/**
+ * Decodes the given complete key, storing the decoded values as properties of the receiver.
+ *
+ * @return YES if the key successfully decoded, NO otherwise. If NO is returned, the properties of
+ *     the receiver are in an undefined state until the next call to -decodeKey:.
+ */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+@property(nonatomic, assign, readonly) const std::string &userID;
+
+@end
+
+/** A key in the target globals table, a record of global values across all targets. */
+@interface FSTLevelDBTargetGlobalKey : NSObject
+
+/** Creates a key that points to the single target global row. */
++ (std::string)key;
+
+/**
+ * Decodes the contents of a target global key, essentially just verifying that the key has the
+ * correct table name.
+ */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+@end
+
+/** A key in the targets table. */
+@interface FSTLevelDBTargetKey : NSObject
+
+/** Creates a key prefix that points just before the first key in the table. */
++ (std::string)keyPrefix;
+
+/** Creates a complete key that points to a specific target, by targetID. */
++ (std::string)keyWithTargetID:(FSTTargetID)targetID;
+
+/**
+ * Decodes the contents of a target key into properties on this instance.
+ *
+ * @return YES if the key successfully decoded, NO otherwise. If NO is returned, the properties of
+ *     the receiver are in an undefined state until the next call to -decodeKey:.
+ */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+/** The targetID identifying a target. */
+@property(nonatomic, assign, readonly) FSTTargetID targetID;
+
+@end
+
+/**
+ * A key in the query targets table, an index of canonicalIDs to the targets they may match. This
+ * is not a unique mapping because canonicalID does not promise a unique name for all possible
+ * queries.
+ */
+@interface FSTLevelDBQueryTargetKey : NSObject
+
+/**
+ * Creates a key that contains just the query targets table prefix and points just before the
+ * first key.
+ */
++ (std::string)keyPrefix;
+
+/** Creates a key that points to the first query-target association for a canonicalID. */
++ (std::string)keyPrefixWithCanonicalID:(Firestore::StringView)canonicalID;
+
+/** Creates a key that points to a specific query-target entry. */
++ (std::string)keyWithCanonicalID:(Firestore::StringView)canonicalID targetID:(FSTTargetID)targetID;
+
+/** Decodes the contents of a query target key into properties on this instance. */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+/** The canonicalID derived from the query. */
+@property(nonatomic, assign, readonly) const std::string &canonicalID;
+
+/** The targetID identifying a target. */
+@property(nonatomic, assign, readonly) FSTTargetID targetID;
+
+@end
+
+/**
+ * A key in the target documents table, an index of targetIDs to the documents they contain.
+ */
+@interface FSTLevelDBTargetDocumentKey : NSObject
+
+/**
+ * Creates a key that contains just the target documents table prefix and points just before the
+ * first key.
+ */
++ (std::string)keyPrefix;
+
+/** Creates a key that points to the first target-document association for a targetID. */
++ (std::string)keyPrefixWithTargetID:(FSTTargetID)targetID;
+
+/** Creates a key that points to a specific target-document entry. */
++ (std::string)keyWithTargetID:(FSTTargetID)targetID documentKey:(FSTDocumentKey *)documentKey;
+
+/** Decodes the contents of a target document key into properties on this instance. */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+/** The targetID identifying a target. */
+@property(nonatomic, assign, readonly) FSTTargetID targetID;
+
+/** The path to the document, as encoded in the key. */
+@property(nonatomic, strong, readonly, nullable) FSTDocumentKey *documentKey;
+
+@end
+
+/**
+ * A key in the document targets table, an index from documents to the targets that contain them.
+ */
+@interface FSTLevelDBDocumentTargetKey : NSObject
+
+/**
+ * Creates a key that contains just the document targets table prefix and points just before the
+ * first key.
+ */
++ (std::string)keyPrefix;
+
+/** Creates a key that points to the first document-target association for document. */
++ (std::string)keyPrefixWithResourcePath:(FSTResourcePath *)resourcePath;
+
+/** Creates a key that points to a specific document-target entry. */
++ (std::string)keyWithDocumentKey:(FSTDocumentKey *)documentKey targetID:(FSTTargetID)targetID;
+
+/** Decodes the contents of a document target key into properties on this instance. */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+/** The targetID identifying a target. */
+@property(nonatomic, assign, readonly) FSTTargetID targetID;
+
+/** The path to the document, as encoded in the key. */
+@property(nonatomic, strong, readonly, nullable) FSTDocumentKey *documentKey;
+
+@end
+
+/** A key in the remote documents table. */
+@interface FSTLevelDBRemoteDocumentKey : NSObject
+
+/**
+ * Creates a key that contains just the remote documents table prefix and points just before the
+ * first remote document key.
+ */
++ (std::string)keyPrefix;
+
+/**
+ * Creates a complete key that points to a specific document. The documentKey must have an even
+ * number of path segments.
+ */
++ (std::string)keyWithDocumentKey:(FSTDocumentKey *)key;
+
+/**
+ * Creates a key prefix that contains a part of a document path. Odd numbers of segments create a
+ * collection key prefix, while an even number of segments create a document key prefix. Note that
+ * a document key prefix will match the document itself and any documents that exist in its
+ * subcollections.
+ */
++ (std::string)keyPrefixWithResourcePath:(FSTResourcePath *)resourcePath;
+
+/**
+ * Decodes the contents of a remote document key into properties on this instance. This can only
+ * decode complete document paths (i.e. the result of +keyWithDocumentKey:).
+ *
+ * @return YES if the key successfully decoded, NO otherwise. If NO is returned, the properties of
+ *     the receiver are in an undefined state until the next call to -decodeKey:.
+ */
+- (BOOL)decodeKey:(Firestore::StringView)key;
+
+/** The path to the document, as encoded in the key. */
+@property(nonatomic, strong, readonly, nullable) FSTDocumentKey *documentKey;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBKey.mm b/Firestore/Source/Local/FSTLevelDBKey.mm
new file mode 100644
index 0000000..ee3e270
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBKey.mm
@@ -0,0 +1,757 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLevelDBKey.h"
+
+#include <string>
+
+#include "ordered_code.h"
+#include "string_util.h"
+#import "FSTDocumentKey.h"
+#import "FSTPath.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+using Firestore::OrderedCode;
+using Firestore::PrefixSuccessor;
+using Firestore::StringView;
+using leveldb::Slice;
+
+static const char *kMutationsTable = "mutation";
+static const char *kDocumentMutationsTable = "document_mutation";
+static const char *kMutationQueuesTable = "mutation_queue";
+static const char *kTargetGlobalTable = "target_global";
+static const char *kTargetsTable = "target";
+static const char *kQueryTargetsTable = "query_target";
+static const char *kTargetDocumentsTable = "target_document";
+static const char *kDocumentTargetsTable = "document_target";
+static const char *kRemoteDocumentsTable = "remote_document";
+
+/**
+ * Labels for the components of keys. These serve to make keys self-describing.
+ *
+ * These are intended to sort similarly to keys in the server storage format.
+ *
+ * Note that the server writes component labels using the equivalent to
+ * OrderedCode::WriteSignedNumDecreasing. This means that despite the higher numeric value, a
+ * terminator sorts before a path segment. In order to avoid needing the WriteSignedNumDecreasing
+ * code just for these values, this enum's values are in the reverse order to the server side.
+ *
+ * Most server-side values don't apply here. For example, the server embeds projects, databases,
+ * namespaces and similar values in its entity keys where the clients just open a different
+ * leveldb. Similarly, many of these values don't apply to the server since the server is backed
+ * by spanner which natively has concepts of tables and indexes. Where there's overlap, a comment
+ * denotes the server value from the storage_format_internal.proto.
+ */
+typedef NS_ENUM(int64_t, FSTComponentLabel) {
+  /**
+   * A terminator is the final component of a key. All complete keys have a terminator and a key
+   * is known to be a key prefix if it doesn't have a terminator.
+   */
+  FSTComponentLabelTerminator = 0,  // TERMINATOR_COMPONENT = 63, server-side
+
+  /** A table name component names the logical table to which the key belongs. */
+  FSTComponentLabelTableName = 5,
+
+  /** A component containing the batch ID of a mutation. */
+  FSTComponentLabelBatchID = 10,
+
+  /** A component containing the canonical ID of a query. */
+  FSTComponentLabelCanonicalID = 11,
+
+  /** A component containing the target ID of a query. */
+  FSTComponentLabelTargetID = 12,
+
+  /** A component containing a user ID. */
+  FSTComponentLabelUserID = 13,
+
+  /**
+   * A path segment describes just a single segment in a resource path. Path segments that occur
+   * sequentially in a key represent successive segments in a single path.
+   *
+   * This value must be greater than FSTComponentLabelTerminator to ensure that longer paths sort
+   * after paths that are prefixes of them.
+   *
+   * This value must also be larger than other separators so that path suffixes sort after other
+   * key components.
+   */
+  FSTComponentLabelPathSegment = 62,  // PATH = 60, server-side
+
+  /** The maximum value that can be encoded by WriteSignedNumIncreasing in a single byte. */
+  FSTComponentLabelUnknown = 63,
+};
+
+namespace {
+
+/** Writes a component label to the given key destination. */
+void WriteComponentLabel(std::string *dest, FSTComponentLabel label) {
+  OrderedCode::WriteSignedNumIncreasing(dest, label);
+}
+
+/**
+ * Reads a component label from the given key contents.
+ *
+ * If the read is unsuccessful, returns NO, and changes none of its arguments.
+ *
+ * If the read is successful, returns YES, contents will be updated to the next unread byte, and
+ * label will be set to the decoded label value.
+ */
+BOOL ReadComponentLabel(leveldb::Slice *contents, FSTComponentLabel *label) {
+  int64_t rawResult = 0;
+  Slice tmp = *contents;
+  if (OrderedCode::ReadSignedNumIncreasing(&tmp, &rawResult)) {
+    if (rawResult >= FSTComponentLabelTerminator && rawResult <= FSTComponentLabelUnknown) {
+      *label = static_cast<FSTComponentLabel>(rawResult);
+      *contents = tmp;
+      return YES;
+    }
+  }
+  return NO;
+}
+
+/**
+ * Reads a component label from the given key contents.
+ *
+ * If the read is unsuccessful or if the read was successful but the label that was read did not
+ * match the expectedLabel returns NO and changes none of its arguments.
+ *
+ * If the read is successful, returns YES and contents will be updated to the next unread byte.
+ */
+BOOL ReadComponentLabelMatching(Slice *contents, FSTComponentLabel expectedLabel) {
+  int64_t rawResult = 0;
+  Slice tmp = *contents;
+  if (OrderedCode::ReadSignedNumIncreasing(&tmp, &rawResult)) {
+    if (rawResult == expectedLabel) {
+      *contents = tmp;
+      return YES;
+    }
+  }
+  return NO;
+}
+
+/**
+ * Reads a signed number from the given key contents and verifies that the value fits in a 32-bit
+ * integer.
+ *
+ * If the read is unsuccessful or the number that was read was out of bounds for an int32_t,
+ * returns NO, and changes none of its arguments.
+ *
+ * If the read is successful, returns YES, contents will be updated to the next unread byte, and
+ * result will be set to the decoded integer value.
+ */
+BOOL ReadInt32(Slice *contents, int32_t *result) {
+  int64_t rawResult = 0;
+  Slice tmp = *contents;
+  if (OrderedCode::ReadSignedNumIncreasing(&tmp, &rawResult)) {
+    if (rawResult >= INT32_MIN && rawResult <= INT32_MAX) {
+      *contents = tmp;
+      *result = static_cast<int32_t>(rawResult);
+      return YES;
+    }
+  }
+  return NO;
+}
+
+/** Writes a component label and a signed integer to the given key destination. */
+void WriteLabeledInt32(std::string *dest, FSTComponentLabel label, int32_t value) {
+  WriteComponentLabel(dest, label);
+  OrderedCode::WriteSignedNumIncreasing(dest, value);
+}
+
+/**
+ * Reads a component label and signed number from the given key contents and verifies that the
+ * label matches the expectedLabel and the value fits in a 32-bit integer.
+ *
+ * If the read is unsuccessful, the label didn't match, or the number that was read was out of
+ * bounds for an int32_t, returns NO, and changes none of its arguments.
+ *
+ * If the read is successful, returns YES, contents will be updated to the next unread byte, and
+ * value will be set to the decoded integer value.
+ */
+BOOL ReadLabeledInt32(Slice *contents, FSTComponentLabel expectedLabel, int32_t *value) {
+  Slice tmp = *contents;
+  if (ReadComponentLabelMatching(&tmp, expectedLabel)) {
+    if (ReadInt32(&tmp, value)) {
+      *contents = tmp;
+      return YES;
+    }
+  }
+  return NO;
+}
+
+/** Writes a component label and an encoded string to the given key destination. */
+void WriteLabeledString(std::string *dest, FSTComponentLabel label, StringView value) {
+  WriteComponentLabel(dest, label);
+  OrderedCode::WriteString(dest, value);
+}
+
+/**
+ * Reads a component label and a string from the given key contents and verifies that the label
+ * matches the expectedLabel.
+ *
+ * If the read is unsuccessful or the label didn't match, returns NO, and changes none of its
+ * arguments.
+ *
+ * If the read is successful, returns YES, contents will be updated to the next unread byte, and
+ * value will be set to the decoded string value.
+ */
+BOOL ReadLabeledString(Slice *contents, FSTComponentLabel expectedLabel, std::string *value) {
+  Slice tmp = *contents;
+  if (ReadComponentLabelMatching(&tmp, expectedLabel)) {
+    if (OrderedCode::ReadString(&tmp, value)) {
+      *contents = tmp;
+      return YES;
+    }
+  }
+
+  return NO;
+}
+
+/**
+ * Reads a component label and a string from the given key contents and verifies that the label
+ * matches the expectedLabel and the string matches the expectedValue.
+ *
+ * If the read is unsuccessful, the label or didn't match, or the string value didn't match,
+ * returns NO, and changes none of its arguments.
+ *
+ * If the read is successful, returns YES, contents will be updated to the next unread byte.
+ */
+BOOL ReadLabeledStringMatching(Slice *contents,
+                               FSTComponentLabel expectedLabel,
+                               const char *expectedValue) {
+  std::string value;
+  Slice tmp = *contents;
+  if (ReadLabeledString(&tmp, expectedLabel, &value)) {
+    if (value == expectedValue) {
+      *contents = tmp;
+      return YES;
+    }
+  }
+
+  return NO;
+}
+
+/**
+ * For each segment in the given resource path writes an FSTComponentLabelPathSegment component
+ * label and a string containing the path segment.
+ */
+void WriteResourcePath(std::string *dest, FSTResourcePath *path) {
+  for (int i = 0; i < path.length; i++) {
+    WriteComponentLabel(dest, FSTComponentLabelPathSegment);
+    OrderedCode::WriteString(dest, StringView([path segmentAtIndex:i]));
+  }
+}
+
+/**
+ * Reads component labels and strings from the given key contents until it finds a component label
+ * other that FSTComponentLabelPathSegment. All matched path segments are assembled into a resource
+ * path and wrapped in an FSTDocumentKey.
+ *
+ * If the read is unsuccessful or the document key is invalid, returns NO, and changes none of its
+ * arguments.
+ *
+ * If the read is successful, returns YES, contents will be updated to the next unread byte, and
+ * value will be set to the decoded document key.
+ */
+BOOL ReadDocumentKey(Slice *contents, FSTDocumentKey *__strong *result) {
+  Slice completeSegments = *contents;
+
+  std::string segment;
+  NSMutableArray<NSString *> *pathSegments = [NSMutableArray array];
+  for (;;) {
+    // Advance a temporary slice to avoid advancing contents into the next key component which may
+    // not be a path segment.
+    Slice readPosition = completeSegments;
+    if (!ReadComponentLabelMatching(&readPosition, FSTComponentLabelPathSegment)) {
+      break;
+    }
+    if (!OrderedCode::ReadString(&readPosition, &segment)) {
+      return NO;
+    }
+
+    NSString *pathSegment = [[NSString alloc] initWithUTF8String:segment.c_str()];
+    [pathSegments addObject:pathSegment];
+    segment.clear();
+
+    completeSegments = readPosition;
+  }
+
+  FSTResourcePath *path = [FSTResourcePath pathWithSegments:pathSegments];
+  if (path.length > 0 && [FSTDocumentKey isDocumentKey:path]) {
+    *contents = completeSegments;
+    *result = [FSTDocumentKey keyWithPath:path];
+    return YES;
+  }
+
+  return NO;
+}
+
+// Trivial shortcuts that make reading and writing components type-safe.
+
+inline void WriteTerminator(std::string *dest) {
+  OrderedCode::WriteSignedNumIncreasing(dest, FSTComponentLabelTerminator);
+}
+
+inline BOOL ReadTerminator(Slice *contents) {
+  return ReadComponentLabelMatching(contents, FSTComponentLabelTerminator);
+}
+
+inline void WriteTableName(std::string *dest, const char *tableName) {
+  WriteLabeledString(dest, FSTComponentLabelTableName, tableName);
+}
+
+inline BOOL ReadTableNameMatching(Slice *contents, const char *expectedTableName) {
+  return ReadLabeledStringMatching(contents, FSTComponentLabelTableName, expectedTableName);
+}
+
+inline void WriteBatchID(std::string *dest, FSTBatchID batchID) {
+  WriteLabeledInt32(dest, FSTComponentLabelBatchID, batchID);
+}
+
+inline BOOL ReadBatchID(Slice *contents, FSTBatchID *batchID) {
+  return ReadLabeledInt32(contents, FSTComponentLabelBatchID, batchID);
+}
+
+inline void WriteCanonicalID(std::string *dest, StringView canonicalID) {
+  WriteLabeledString(dest, FSTComponentLabelCanonicalID, canonicalID);
+}
+
+inline BOOL ReadCanonicalID(Slice *contents, std::string *canonicalID) {
+  return ReadLabeledString(contents, FSTComponentLabelCanonicalID, canonicalID);
+}
+
+inline void WriteTargetID(std::string *dest, FSTTargetID targetID) {
+  WriteLabeledInt32(dest, FSTComponentLabelTargetID, targetID);
+}
+
+inline BOOL ReadTargetID(Slice *contents, FSTTargetID *targetID) {
+  return ReadLabeledInt32(contents, FSTComponentLabelTargetID, targetID);
+}
+
+inline void WriteUserID(std::string *dest, StringView userID) {
+  WriteLabeledString(dest, FSTComponentLabelUserID, userID);
+}
+
+inline BOOL ReadUserID(Slice *contents, std::string *userID) {
+  return ReadLabeledString(contents, FSTComponentLabelUserID, userID);
+}
+
+/** Returns a base64-encoded string for an invalid key, used for debug-friendly description text. */
+NSString *InvalidKey(const Slice &key) {
+  NSData *keyData =
+      [[NSData alloc] initWithBytesNoCopy:(void *)key.data() length:key.size() freeWhenDone:NO];
+  return [keyData base64EncodedStringWithOptions:0];
+}
+
+}  // namespace
+
+@implementation FSTLevelDBKey
+
++ (NSString *)descriptionForKey:(StringView)key {
+  Slice contents = key;
+  BOOL isTerminated = NO;
+
+  NSMutableString *description = [NSMutableString string];
+  [description appendString:@"["];
+  while (contents.size() > 0) {
+    Slice tmp = contents;
+    FSTComponentLabel label = FSTComponentLabelUnknown;
+    if (!ReadComponentLabel(&tmp, &label)) {
+      break;
+    }
+
+    if (label == FSTComponentLabelTerminator) {
+      isTerminated = YES;
+      contents = tmp;
+      break;
+    }
+
+    // Reset tmp since all the different read routines expect to see the separator first
+    tmp = contents;
+
+    if (label == FSTComponentLabelPathSegment) {
+      FSTDocumentKey *documentKey = nil;
+      if (!ReadDocumentKey(&tmp, &documentKey)) {
+        break;
+      }
+      [description appendFormat:@" key=%@", [documentKey.path description]];
+
+    } else if (label == FSTComponentLabelTableName) {
+      std::string table;
+      if (!ReadLabeledString(&tmp, FSTComponentLabelTableName, &table)) {
+        break;
+      }
+      [description appendFormat:@"%s:", table.c_str()];
+
+    } else if (label == FSTComponentLabelBatchID) {
+      FSTBatchID batchID;
+      if (!ReadBatchID(&tmp, &batchID)) {
+        break;
+      }
+      [description appendFormat:@" batchID=%d", batchID];
+
+    } else if (label == FSTComponentLabelCanonicalID) {
+      std::string canonicalID;
+      if (!ReadCanonicalID(&tmp, &canonicalID)) {
+        break;
+      }
+      [description appendFormat:@" canonicalID=%s", canonicalID.c_str()];
+
+    } else if (label == FSTComponentLabelTargetID) {
+      FSTTargetID targetID;
+      if (!ReadTargetID(&tmp, &targetID)) {
+        break;
+      }
+      [description appendFormat:@" targetID=%d", targetID];
+
+    } else if (label == FSTComponentLabelUserID) {
+      std::string userID;
+      if (!ReadUserID(&tmp, &userID)) {
+        break;
+      }
+      [description appendFormat:@" userID=%s", userID.c_str()];
+
+    } else {
+      [description appendFormat:@" unknown label=%d", (int)label];
+      break;
+    }
+
+    contents = tmp;
+  }
+
+  if (contents.size() > 0) {
+    [description appendFormat:@" invalid key=<%@>", InvalidKey(key)];
+
+  } else if (!isTerminated) {
+    [description appendFormat:@" incomplete key"];
+  }
+
+  [description appendString:@"]"];
+  return description;
+}
+
+@end
+
+@implementation FSTLevelDBMutationKey {
+  std::string _userID;
+}
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kMutationsTable);
+  return result;
+}
+
++ (std::string)keyPrefixWithUserID:(StringView)userID {
+  std::string result;
+  WriteTableName(&result, kMutationsTable);
+  WriteUserID(&result, userID);
+  return result;
+}
+
++ (std::string)keyWithUserID:(StringView)userID batchID:(FSTBatchID)batchID {
+  std::string result;
+  WriteTableName(&result, kMutationsTable);
+  WriteUserID(&result, userID);
+  WriteBatchID(&result, batchID);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (const std::string &)userID {
+  return _userID;
+}
+
+- (BOOL)decodeKey:(StringView)key {
+  _userID.clear();
+
+  Slice contents = key;
+  return ReadTableNameMatching(&contents, kMutationsTable) && ReadUserID(&contents, &_userID) &&
+         ReadBatchID(&contents, &_batchID) && ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBDocumentMutationKey {
+  std::string _userID;
+}
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kDocumentMutationsTable);
+  return result;
+}
+
++ (std::string)keyPrefixWithUserID:(StringView)userID {
+  std::string result;
+  WriteTableName(&result, kDocumentMutationsTable);
+  WriteUserID(&result, userID);
+  return result;
+}
+
++ (std::string)keyPrefixWithUserID:(StringView)userID resourcePath:(FSTResourcePath *)resourcePath {
+  std::string result;
+  WriteTableName(&result, kDocumentMutationsTable);
+  WriteUserID(&result, userID);
+  WriteResourcePath(&result, resourcePath);
+  return result;
+}
+
++ (std::string)keyWithUserID:(StringView)userID
+                 documentKey:(FSTDocumentKey *)documentKey
+                     batchID:(FSTBatchID)batchID {
+  std::string result;
+  WriteTableName(&result, kDocumentMutationsTable);
+  WriteUserID(&result, userID);
+  WriteResourcePath(&result, documentKey.path);
+  WriteBatchID(&result, batchID);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (const std::string &)userID {
+  return _userID;
+}
+
+- (BOOL)decodeKey:(StringView)key {
+  _userID.clear();
+  _documentKey = nil;
+
+  Slice contents = key;
+  return ReadTableNameMatching(&contents, kDocumentMutationsTable) &&
+         ReadUserID(&contents, &_userID) && ReadDocumentKey(&contents, &_documentKey) &&
+         ReadBatchID(&contents, &_batchID) && ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBMutationQueueKey {
+  std::string _userID;
+}
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kMutationQueuesTable);
+  return result;
+}
+
++ (std::string)keyWithUserID:(StringView)userID {
+  std::string result;
+  WriteTableName(&result, kMutationQueuesTable);
+  WriteUserID(&result, userID);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (const std::string &)userID {
+  return _userID;
+}
+
+- (BOOL)decodeKey:(StringView)key {
+  _userID.clear();
+
+  Slice contents = key;
+  return ReadTableNameMatching(&contents, kMutationQueuesTable) &&
+         ReadUserID(&contents, &_userID) && ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBTargetGlobalKey
+
++ (std::string)key {
+  std::string result;
+  WriteTableName(&result, kTargetGlobalTable);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (BOOL)decodeKey:(StringView)key {
+  Slice contents = key;
+  return ReadTableNameMatching(&contents, kTargetGlobalTable) && ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBTargetKey
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kTargetsTable);
+  return result;
+}
+
++ (std::string)keyWithTargetID:(FSTTargetID)targetID {
+  std::string result;
+  WriteTableName(&result, kTargetsTable);
+  WriteTargetID(&result, targetID);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (BOOL)decodeKey:(StringView)key {
+  Slice contents = key;
+  return ReadTableNameMatching(&contents, kTargetsTable) && ReadTargetID(&contents, &_targetID) &&
+         ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBQueryTargetKey {
+  std::string _canonicalID;
+}
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kQueryTargetsTable);
+  return result;
+}
+
++ (std::string)keyPrefixWithCanonicalID:(StringView)canonicalID {
+  std::string result;
+  WriteTableName(&result, kQueryTargetsTable);
+  WriteCanonicalID(&result, canonicalID);
+  return result;
+}
+
++ (std::string)keyWithCanonicalID:(StringView)canonicalID targetID:(FSTTargetID)targetID {
+  std::string result;
+  WriteTableName(&result, kQueryTargetsTable);
+  WriteCanonicalID(&result, canonicalID);
+  WriteTargetID(&result, targetID);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (const std::string &)canonicalID {
+  return _canonicalID;
+}
+
+- (BOOL)decodeKey:(StringView)key {
+  _canonicalID.clear();
+
+  Slice contents = key;
+  return ReadTableNameMatching(&contents, kQueryTargetsTable) &&
+         ReadCanonicalID(&contents, &_canonicalID) && ReadTargetID(&contents, &_targetID) &&
+         ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBTargetDocumentKey
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kTargetDocumentsTable);
+  return result;
+}
+
++ (std::string)keyPrefixWithTargetID:(FSTTargetID)targetID {
+  std::string result;
+  WriteTableName(&result, kTargetDocumentsTable);
+  WriteTargetID(&result, targetID);
+  return result;
+}
+
++ (std::string)keyWithTargetID:(FSTTargetID)targetID documentKey:(FSTDocumentKey *)documentKey {
+  std::string result;
+  WriteTableName(&result, kTargetDocumentsTable);
+  WriteTargetID(&result, targetID);
+  WriteResourcePath(&result, documentKey.path);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (BOOL)decodeKey:(Firestore::StringView)key {
+  _documentKey = nil;
+
+  leveldb::Slice contents = key;
+  return ReadTableNameMatching(&contents, kTargetDocumentsTable) &&
+         ReadTargetID(&contents, &_targetID) && ReadDocumentKey(&contents, &_documentKey) &&
+         ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBDocumentTargetKey
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kDocumentTargetsTable);
+  return result;
+}
+
++ (std::string)keyPrefixWithResourcePath:(FSTResourcePath *)resourcePath {
+  std::string result;
+  WriteTableName(&result, kDocumentTargetsTable);
+  WriteResourcePath(&result, resourcePath);
+  return result;
+}
+
++ (std::string)keyWithDocumentKey:(FSTDocumentKey *)documentKey targetID:(FSTTargetID)targetID {
+  std::string result;
+  WriteTableName(&result, kDocumentTargetsTable);
+  WriteResourcePath(&result, documentKey.path);
+  WriteTargetID(&result, targetID);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (BOOL)decodeKey:(Firestore::StringView)key {
+  _documentKey = nil;
+
+  leveldb::Slice contents = key;
+  return ReadTableNameMatching(&contents, kDocumentTargetsTable) &&
+         ReadDocumentKey(&contents, &_documentKey) && ReadTargetID(&contents, &_targetID) &&
+         ReadTerminator(&contents);
+}
+
+@end
+
+@implementation FSTLevelDBRemoteDocumentKey
+
++ (std::string)keyPrefix {
+  std::string result;
+  WriteTableName(&result, kRemoteDocumentsTable);
+  return result;
+}
+
++ (std::string)keyPrefixWithResourcePath:(FSTResourcePath *)path {
+  std::string result;
+  WriteTableName(&result, kRemoteDocumentsTable);
+  WriteResourcePath(&result, path);
+  return result;
+}
+
++ (std::string)keyWithDocumentKey:(FSTDocumentKey *)key {
+  std::string result;
+  WriteTableName(&result, kRemoteDocumentsTable);
+  WriteResourcePath(&result, key.path);
+  WriteTerminator(&result);
+  return result;
+}
+
+- (BOOL)decodeKey:(StringView)key {
+  _documentKey = nil;
+
+  Slice contents = key;
+  return ReadTableNameMatching(&contents, kRemoteDocumentsTable) &&
+         ReadDocumentKey(&contents, &_documentKey) && ReadTerminator(&contents);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBMutationQueue.h b/Firestore/Source/Local/FSTLevelDBMutationQueue.h
new file mode 100644
index 0000000..c9b5166
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBMutationQueue.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTMutationQueue.h"
+
+#ifdef __cplusplus
+#include <memory>
+
+namespace leveldb {
+class DB;
+}
+#endif
+
+@class FSTLevelDB;
+@class FSTLocalSerializer;
+@class FSTUser;
+@protocol FSTGarbageCollector;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** A mutation queue for a specific user, backed by LevelDB. */
+@interface FSTLevelDBMutationQueue : NSObject <FSTMutationQueue>
+
+- (instancetype)init __attribute__((unavailable("Use a static constructor")));
+
+/** The garbage collector to notify about potential garbage keys. */
+@property(nonatomic, weak, readwrite, nullable) id<FSTGarbageCollector> garbageCollector;
+
+#ifdef __cplusplus
+/**
+ * Creates a new mutation queue for the given user, in the given LevelDB.
+ *
+ * @param user The user for which to create a mutation queue.
+ * @param db The LevelDB in which to create the queue.
+ */
++ (instancetype)mutationQueueWithUser:(FSTUser *)user
+                                   db:(std::shared_ptr<leveldb::DB>)db
+                           serializer:(FSTLocalSerializer *)serializer;
+
+/**
+ * Returns one larger than the largest batch ID that has been stored. If there are no mutations
+ * returns 0. Note that batch IDs are global.
+ */
++ (FSTBatchID)loadNextBatchIDFromDB:(std::shared_ptr<leveldb::DB>)db;
+#endif
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBMutationQueue.mm b/Firestore/Source/Local/FSTLevelDBMutationQueue.mm
new file mode 100644
index 0000000..d57a15d
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBMutationQueue.mm
@@ -0,0 +1,637 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLevelDBMutationQueue.h"
+
+#include <leveldb/db.h>
+#include <leveldb/write_batch.h>
+#include <set>
+#include <string>
+
+#import "Mutation.pbobjc.h"
+#import "FSTUser.h"
+#import "FSTQuery.h"
+#import "FSTLevelDB.h"
+#import "FSTLevelDBKey.h"
+#import "FSTLocalSerializer.h"
+#import "FSTWriteGroup.h"
+#import "FSTDocumentKey.h"
+#import "FSTMutation.h"
+#import "FSTMutationBatch.h"
+#import "FSTPath.h"
+#import "FSTAssert.h"
+
+#include "ordered_code.h"
+#include "string_util.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+using Firestore::OrderedCode;
+using Firestore::StringView;
+using leveldb::DB;
+using leveldb::Iterator;
+using leveldb::ReadOptions;
+using leveldb::Slice;
+using leveldb::Status;
+using leveldb::WriteBatch;
+using leveldb::WriteOptions;
+
+@interface FSTLevelDBMutationQueue ()
+
+- (instancetype)initWithUserID:(NSString *)userID
+                            db:(std::shared_ptr<DB>)db
+                    serializer:(FSTLocalSerializer *)serializer NS_DESIGNATED_INITIALIZER;
+
+/** The normalized userID (e.g. nil UID => @"" userID) used in our LevelDB keys. */
+@property(nonatomic, strong, readonly) NSString *userID;
+
+/**
+ * Next value to use when assigning sequential IDs to each mutation batch.
+ *
+ * NOTE: There can only be one FSTLevelDBMutationQueue for a given db at a time, hence it is safe
+ * to track nextBatchID as an instance-level property. Should we ever relax this constraint we'll
+ * need to revisit this.
+ */
+@property(nonatomic, assign) FSTBatchID nextBatchID;
+
+/** A write-through cache copy of the metadata describing the current queue. */
+@property(nonatomic, strong, nullable) FSTPBMutationQueue *metadata;
+
+@property(nonatomic, strong, readonly) FSTLocalSerializer *serializer;
+
+@end
+
+/**
+ * Returns a standard set of read options.
+ *
+ * For now this is paranoid, but perhaps disable that in production builds.
+ */
+static ReadOptions StandardReadOptions() {
+  ReadOptions options;
+  options.verify_checksums = true;
+  return options;
+}
+
+@implementation FSTLevelDBMutationQueue {
+  // The DB pointer is shared with all cooperating LevelDB-related objects.
+  std::shared_ptr<DB> _db;
+}
+
++ (instancetype)mutationQueueWithUser:(FSTUser *)user
+                                   db:(std::shared_ptr<DB>)db
+                           serializer:(FSTLocalSerializer *)serializer {
+  FSTAssert(![user.UID isEqual:@""], @"UserID must not be an empty string.");
+  NSString *userID = user.isUnauthenticated ? @"" : user.UID;
+
+  return [[FSTLevelDBMutationQueue alloc] initWithUserID:userID db:db serializer:serializer];
+}
+
+- (instancetype)initWithUserID:(NSString *)userID
+                            db:(std::shared_ptr<DB>)db
+                    serializer:(FSTLocalSerializer *)serializer {
+  if (self = [super init]) {
+    _userID = userID;
+    _db = db;
+    _serializer = serializer;
+  }
+  return self;
+}
+
+- (void)startWithGroup:(FSTWriteGroup *)group {
+  FSTBatchID nextBatchID = [FSTLevelDBMutationQueue loadNextBatchIDFromDB:_db];
+
+  // On restart, nextBatchId may end up lower than lastAcknowledgedBatchId since it's computed from
+  // the queue contents, and there may be no mutations in the queue. In this case, we need to reset
+  // lastAcknowledgedBatchId (which is safe since the queue must be empty).
+  std::string key = [self keyForCurrentMutationQueue];
+  FSTPBMutationQueue *metadata = [self metadataForKey:key];
+  if (!metadata) {
+    metadata = [FSTPBMutationQueue message];
+
+    // proto3's default value for lastAcknowledgedBatchId is zero, but that would consider the first
+    // entry in the queue to be acknowledged without that acknowledgement actually happening.
+    metadata.lastAcknowledgedBatchId = kFSTBatchIDUnknown;
+  } else {
+    FSTBatchID lastAcked = metadata.lastAcknowledgedBatchId;
+    if (lastAcked >= nextBatchID) {
+      FSTAssert([self isEmpty], @"Reset nextBatchID is only possible when the queue is empty");
+      lastAcked = kFSTBatchIDUnknown;
+
+      metadata.lastAcknowledgedBatchId = lastAcked;
+      [group setMessage:metadata forKey:[self keyForCurrentMutationQueue]];
+    }
+  }
+
+  self.nextBatchID = nextBatchID;
+  self.metadata = metadata;
+}
+
+- (void)shutdown {
+  _db.reset();
+}
+
++ (FSTBatchID)loadNextBatchIDFromDB:(std::shared_ptr<DB>)db {
+  std::unique_ptr<Iterator> it(db->NewIterator(StandardReadOptions()));
+
+  auto tableKey = [FSTLevelDBMutationKey keyPrefix];
+
+  FSTLevelDBMutationKey *rowKey = [[FSTLevelDBMutationKey alloc] init];
+  FSTBatchID maxBatchID = kFSTBatchIDUnknown;
+
+  BOOL moreUserIDs = NO;
+  std::string nextUserID;
+
+  it->Seek(tableKey);
+  if (it->Valid() && [rowKey decodeKey:it->key()]) {
+    moreUserIDs = YES;
+    nextUserID = rowKey.userID;
+  }
+
+  // This loop assumes that nextUserId contains the next username at the start of the iteration.
+  while (moreUserIDs) {
+    // Compute the first key after the last mutation for nextUserID.
+    auto userEnd = [FSTLevelDBMutationKey keyPrefixWithUserID:nextUserID];
+    userEnd = Firestore::PrefixSuccessor(userEnd);
+
+    // Seek to that key with the intent of finding the boundary between nextUserID's mutations
+    // and the one after that (if any).
+    it->Seek(userEnd);
+
+    // At this point there are three possible cases to handle differently. Each case must prepare
+    // the next iteration (by assigning to nextUserID or setting moreUserIDs = NO) and seek the
+    // iterator to the last row in the current user's mutation sequence.
+    if (!it->Valid()) {
+      // The iterator is past the last row altogether (there are no additional userIDs and now
+      // rows in any table after mutations). The last row will have the highest batchID.
+      moreUserIDs = NO;
+      it->SeekToLast();
+
+    } else if ([rowKey decodeKey:it->key()]) {
+      // The iterator is valid and the key decoded successfully so the next user was just decoded.
+      nextUserID = rowKey.userID;
+      it->Prev();
+
+    } else {
+      // The iterator is past the end of the mutations table but there are other rows.
+      moreUserIDs = NO;
+      it->Prev();
+    }
+
+    // In all the cases above there was at least one row for the current user and each case has
+    // set things up such that iterator points to it.
+    if (![rowKey decodeKey:it->key()]) {
+      FSTFail(@"There should have been a key previous to %s", userEnd.c_str());
+    }
+
+    if (rowKey.batchID > maxBatchID) {
+      maxBatchID = rowKey.batchID;
+    }
+  }
+
+  return maxBatchID + 1;
+}
+
+- (BOOL)isEmpty {
+  std::string userKey = [FSTLevelDBMutationKey keyPrefixWithUserID:self.userID];
+
+  std::unique_ptr<Iterator> it(_db->NewIterator(StandardReadOptions()));
+  it->Seek(userKey);
+
+  BOOL empty = YES;
+  if (it->Valid() && it->key().starts_with(userKey)) {
+    empty = NO;
+  }
+
+  Status status = it->status();
+  if (!status.ok()) {
+    FSTFail(@"isEmpty failed with status: %s", status.ToString().c_str());
+  }
+
+  return empty;
+}
+
+- (FSTBatchID)highestAcknowledgedBatchID {
+  return self.metadata.lastAcknowledgedBatchId;
+}
+
+- (void)acknowledgeBatch:(FSTMutationBatch *)batch
+             streamToken:(nullable NSData *)streamToken
+                   group:(FSTWriteGroup *)group {
+  FSTBatchID batchID = batch.batchID;
+  FSTAssert(batchID > self.highestAcknowledgedBatchID,
+            @"Mutation batchIDs must be acknowledged in order");
+
+  FSTPBMutationQueue *metadata = self.metadata;
+  metadata.lastAcknowledgedBatchId = batchID;
+  metadata.lastStreamToken = streamToken;
+
+  [group setMessage:metadata forKey:[self keyForCurrentMutationQueue]];
+}
+
+- (nullable NSData *)lastStreamToken {
+  return self.metadata.lastStreamToken;
+}
+
+- (void)setLastStreamToken:(nullable NSData *)streamToken group:(FSTWriteGroup *)group {
+  FSTPBMutationQueue *metadata = self.metadata;
+  metadata.lastStreamToken = streamToken;
+
+  [group setMessage:metadata forKey:[self keyForCurrentMutationQueue]];
+}
+
+- (std::string)keyForCurrentMutationQueue {
+  return [FSTLevelDBMutationQueueKey keyWithUserID:self.userID];
+}
+
+- (nullable FSTPBMutationQueue *)metadataForKey:(const std::string &)key {
+  std::string value;
+  Status status = _db->Get(StandardReadOptions(), key, &value);
+  if (status.ok()) {
+    return [self parsedMetadata:value];
+  } else if (status.IsNotFound()) {
+    return nil;
+  } else {
+    FSTFail(@"metadataForKey: failed loading key %s with status: %s", key.c_str(),
+            status.ToString().c_str());
+  }
+}
+
+- (FSTMutationBatch *)addMutationBatchWithWriteTime:(FSTTimestamp *)localWriteTime
+                                          mutations:(NSArray<FSTMutation *> *)mutations
+                                              group:(FSTWriteGroup *)group {
+  FSTBatchID batchID = self.nextBatchID;
+  self.nextBatchID += 1;
+
+  FSTMutationBatch *batch = [[FSTMutationBatch alloc] initWithBatchID:batchID
+                                                       localWriteTime:localWriteTime
+                                                            mutations:mutations];
+  std::string key = [self mutationKeyForBatch:batch];
+  [group setMessage:[self.serializer encodedMutationBatch:batch] forKey:key];
+
+  NSString *userID = self.userID;
+
+  // Store an empty value in the index which is equivalent to serializing a GPBEmpty message. In the
+  // future if we wanted to store some other kind of value here, we can parse these empty values as
+  // with some other protocol buffer (and the parser will see all default values).
+  std::string emptyBuffer;
+
+  for (FSTMutation *mutation in mutations) {
+    key = [FSTLevelDBDocumentMutationKey keyWithUserID:userID
+                                           documentKey:mutation.key
+                                               batchID:batchID];
+    [group setData:emptyBuffer forKey:key];
+  }
+
+  return batch;
+}
+
+- (nullable FSTMutationBatch *)lookupMutationBatch:(FSTBatchID)batchID {
+  std::string key = [self mutationKeyForBatchID:batchID];
+
+  std::string value;
+  Status status = _db->Get(StandardReadOptions(), key, &value);
+  if (!status.ok()) {
+    if (status.IsNotFound()) {
+      return nil;
+    }
+    FSTFail(@"Lookup mutation batch (%@, %d) failed with status: %s", self.userID, batchID,
+            status.ToString().c_str());
+  }
+
+  return [self decodedMutationBatch:value];
+}
+
+- (nullable FSTMutationBatch *)nextMutationBatchAfterBatchID:(FSTBatchID)batchID {
+  std::string key = [self mutationKeyForBatchID:batchID + 1];
+  std::unique_ptr<Iterator> it(_db->NewIterator(StandardReadOptions()));
+  it->Seek(key);
+
+  Status status = it->status();
+  if (!status.ok()) {
+    FSTFail(@"Seek to mutation batch (%@, %d) failed with status: %s", self.userID, batchID,
+            status.ToString().c_str());
+  }
+
+  FSTLevelDBMutationKey *rowKey = [[FSTLevelDBMutationKey alloc] init];
+  if (!it->Valid() || ![rowKey decodeKey:it->key()]) {
+    // Past the last row in the DB or out of the mutations table
+    return nil;
+  }
+
+  if (rowKey.userID != [self.userID UTF8String]) {
+    // Jumped past the last mutation for this user
+    return nil;
+  }
+
+  FSTAssert(rowKey.batchID > batchID, @"Should have found mutation after %d", batchID);
+  return [self decodedMutationBatch:it->value()];
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesThroughBatchID:(FSTBatchID)batchID {
+  std::string userKey = [FSTLevelDBMutationKey keyPrefixWithUserID:self.userID];
+  const char *userID = [self.userID UTF8String];
+
+  std::unique_ptr<Iterator> it(_db->NewIterator(StandardReadOptions()));
+  it->Seek(userKey);
+
+  NSMutableArray *result = [NSMutableArray array];
+  FSTLevelDBMutationKey *rowKey = [[FSTLevelDBMutationKey alloc] init];
+  for (; it->Valid() && [rowKey decodeKey:it->key()]; it->Next()) {
+    if (rowKey.userID != userID) {
+      // End of this user's mutations
+      break;
+    } else if (rowKey.batchID > batchID) {
+      // This mutation is past what we're looking for
+      break;
+    }
+
+    [result addObject:[self decodedMutationBatch:it->value()]];
+  }
+
+  Status status = it->status();
+  if (!status.ok()) {
+    FSTFail(@"Find all mutations through mutation batch (%@, %d) failed with status: %s",
+            self.userID, batchID, status.ToString().c_str());
+  }
+
+  return result;
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesAffectingDocumentKey:
+    (FSTDocumentKey *)documentKey {
+  NSString *userID = self.userID;
+
+  // Scan the document-mutation index starting with a prefix starting with the given documentKey.
+  std::string indexPrefix =
+      [FSTLevelDBDocumentMutationKey keyPrefixWithUserID:self.userID resourcePath:documentKey.path];
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(StandardReadOptions()));
+  indexIterator->Seek(indexPrefix);
+
+  // Simultaneously scan the mutation queue. This works because each (key, batchID) pair is unique
+  // and ordered, so when scanning a table prefixed by exactly key, all the batchIDs encountered
+  // will be unique and in order.
+  std::string mutationsPrefix = [FSTLevelDBMutationKey keyPrefixWithUserID:userID];
+  std::unique_ptr<Iterator> mutationIterator(_db->NewIterator(StandardReadOptions()));
+
+  NSMutableArray *result = [NSMutableArray array];
+  FSTLevelDBDocumentMutationKey *rowKey = [[FSTLevelDBDocumentMutationKey alloc] init];
+  for (; indexIterator->Valid(); indexIterator->Next()) {
+    Slice indexKey = indexIterator->key();
+
+    // Only consider rows matching exactly the specific key of interest. Note that because we order
+    // by path first, and we order terminators before path separators, we'll encounter all the
+    // index rows for documentKey contiguously. In particular, all the rows for documentKey will
+    // occur before any rows for documents nested in a subcollection beneath documentKey so we can
+    // stop as soon as we hit any such row.
+    if (!indexKey.starts_with(indexPrefix) || ![rowKey decodeKey:indexKey] ||
+        ![rowKey.documentKey isEqualToKey:documentKey]) {
+      break;
+    }
+
+    // Each row is a unique combination of key and batchID, so this foreign key reference can
+    // only occur once.
+    std::string mutationKey = [FSTLevelDBMutationKey keyWithUserID:userID batchID:rowKey.batchID];
+    mutationIterator->Seek(mutationKey);
+    if (!mutationIterator->Valid() || mutationIterator->key() != mutationKey) {
+      NSString *foundKeyDescription = @"the end of the table";
+      if (mutationIterator->Valid()) {
+        foundKeyDescription = [FSTLevelDBKey descriptionForKey:mutationIterator->key()];
+      }
+      FSTFail(@"Dangling document-mutation reference found: "
+              @"%@ points to %@; seeking there found %@",
+              [FSTLevelDBKey descriptionForKey:indexKey],
+              [FSTLevelDBKey descriptionForKey:mutationKey], foundKeyDescription);
+    }
+
+    [result addObject:[self decodedMutationBatch:mutationIterator->value()]];
+  }
+  return result;
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesAffectingQuery:(FSTQuery *)query {
+  FSTAssert(![query isDocumentQuery], @"Document queries shouldn't go down this path");
+  NSString *userID = self.userID;
+
+  FSTResourcePath *queryPath = query.path;
+  int immediateChildrenPathLength = queryPath.length + 1;
+
+  // TODO(mcg): Actually implement a single-collection query
+  //
+  // This is actually executing an ancestor query, traversing the whole subtree below the
+  // collection which can be horrifically inefficient for some structures. The right way to
+  // solve this is to implement the full value index, but that's not in the cards in the near
+  // future so this is the best we can do for the moment.
+  //
+  // Since we don't yet index the actual properties in the mutations, our current approach is to
+  // just return all mutation batches that affect documents in the collection being queried.
+  //
+  // Unlike allMutationBatchesAffectingDocumentKey, this iteration will scan the document-mutation
+  // index for more than a single document so the associated batchIDs will be neither necessarily
+  // unique nor in order. This means an efficient simultaneous scan isn't possible.
+  std::string indexPrefix =
+      [FSTLevelDBDocumentMutationKey keyPrefixWithUserID:self.userID resourcePath:queryPath];
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(StandardReadOptions()));
+  indexIterator->Seek(indexPrefix);
+
+  NSMutableArray *result = [NSMutableArray array];
+  FSTLevelDBDocumentMutationKey *rowKey = [[FSTLevelDBDocumentMutationKey alloc] init];
+
+  // Collect up unique batchIDs encountered during a scan of the index. Use a set<FSTBatchID> to
+  // accumulate batch IDs so they can be traversed in order in a scan of the main table.
+  //
+  // This method is faster than performing lookups of the keys with _db->Get and keeping a hash of
+  // batchIDs that have already been looked up. The performance difference is minor for small
+  // numbers of keys but > 30% faster for larger numbers of keys.
+  std::set<FSTBatchID> uniqueBatchIds;
+  for (; indexIterator->Valid(); indexIterator->Next()) {
+    Slice indexKey = indexIterator->key();
+
+    if (!indexKey.starts_with(indexPrefix) || ![rowKey decodeKey:indexKey]) {
+      break;
+    }
+
+    // Rows with document keys more than one segment longer than the query path can't be matches.
+    // For example, a query on 'rooms' can't match the document /rooms/abc/messages/xyx.
+    // TODO(mcg): we'll need a different scanner when we implement ancestor queries.
+    if (rowKey.documentKey.path.length != immediateChildrenPathLength) {
+      continue;
+    }
+
+    uniqueBatchIds.insert(rowKey.batchID);
+  }
+
+  // Given an ordered set of unique batchIDs perform a skipping scan over the main table to find
+  // the mutation batches.
+  std::unique_ptr<Iterator> mutationIterator(_db->NewIterator(StandardReadOptions()));
+
+  for (FSTBatchID batchID : uniqueBatchIds) {
+    std::string mutationKey = [FSTLevelDBMutationKey keyWithUserID:userID batchID:batchID];
+    mutationIterator->Seek(mutationKey);
+    if (!mutationIterator->Valid() || mutationIterator->key() != mutationKey) {
+      NSString *foundKeyDescription = @"the end of the table";
+      if (mutationIterator->Valid()) {
+        foundKeyDescription = [FSTLevelDBKey descriptionForKey:mutationIterator->key()];
+      }
+      FSTFail(@"Dangling document-mutation reference found: "
+              @"Missing batch %@; seeking there found %@",
+              [FSTLevelDBKey descriptionForKey:mutationKey], foundKeyDescription);
+    }
+
+    [result addObject:[self decodedMutationBatch:mutationIterator->value()]];
+  }
+  return result;
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatches {
+  std::string userKey = [FSTLevelDBMutationKey keyPrefixWithUserID:self.userID];
+
+  std::unique_ptr<Iterator> it(_db->NewIterator(StandardReadOptions()));
+  it->Seek(userKey);
+
+  NSMutableArray *result = [NSMutableArray array];
+  for (; it->Valid() && it->key().starts_with(userKey); it->Next()) {
+    [result addObject:[self decodedMutationBatch:it->value()]];
+  }
+
+  Status status = it->status();
+  if (!status.ok()) {
+    FSTFail(@"Find all mutation batches failed with status: %s", status.ToString().c_str());
+  }
+
+  return result;
+}
+
+- (void)removeMutationBatches:(NSArray<FSTMutationBatch *> *)batches group:(FSTWriteGroup *)group {
+  NSString *userID = self.userID;
+  id<FSTGarbageCollector> garbageCollector = self.garbageCollector;
+
+  std::unique_ptr<Iterator> checkIterator(_db->NewIterator(StandardReadOptions()));
+
+  for (FSTMutationBatch *batch in batches) {
+    FSTBatchID batchID = batch.batchID;
+    std::string key = [FSTLevelDBMutationKey keyWithUserID:userID batchID:batchID];
+
+    // As a sanity check, verify that the mutation batch exists before deleting it.
+    checkIterator->Seek(key);
+    FSTAssert(checkIterator->Valid(), @"Mutation batch %@ did not exist",
+              [FSTLevelDBKey descriptionForKey:key]);
+
+    FSTAssert(key == checkIterator->key(), @"Mutation batch %@ not found; found %@",
+              [FSTLevelDBKey descriptionForKey:key],
+              [FSTLevelDBKey descriptionForKey:checkIterator->key()]);
+
+    [group removeMessageForKey:key];
+
+    for (FSTMutation *mutation in batch.mutations) {
+      key = [FSTLevelDBDocumentMutationKey keyWithUserID:userID
+                                             documentKey:mutation.key
+                                                 batchID:batchID];
+      [group removeMessageForKey:key];
+      [garbageCollector addPotentialGarbageKey:mutation.key];
+    }
+  }
+}
+
+- (void)performConsistencyCheck {
+  if (![self isEmpty]) {
+    return;
+  }
+
+  // Verify that there are no entries in the document-mutation index if the queue is empty.
+  std::string indexPrefix = [FSTLevelDBDocumentMutationKey keyPrefixWithUserID:self.userID];
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(StandardReadOptions()));
+  indexIterator->Seek(indexPrefix);
+
+  NSMutableArray<NSString *> *danglingMutationReferences = [NSMutableArray array];
+
+  for (; indexIterator->Valid(); indexIterator->Next()) {
+    Slice indexKey = indexIterator->key();
+
+    // Only consider rows matching this index prefix for the current user.
+    if (!indexKey.starts_with(indexPrefix)) {
+      break;
+    }
+
+    [danglingMutationReferences addObject:[FSTLevelDBKey descriptionForKey:indexKey]];
+  }
+
+  FSTAssert(danglingMutationReferences.count == 0,
+            @"Document leak -- detected dangling mutation references when queue "
+            @"is empty. Dangling keys: %@",
+            danglingMutationReferences);
+}
+
+- (std::string)mutationKeyForBatch:(FSTMutationBatch *)batch {
+  return [FSTLevelDBMutationKey keyWithUserID:self.userID batchID:batch.batchID];
+}
+
+- (std::string)mutationKeyForBatchID:(FSTBatchID)batchID {
+  return [FSTLevelDBMutationKey keyWithUserID:self.userID batchID:batchID];
+}
+
+/** Parses the MutationQueue metadata from the given LevelDB row contents. */
+- (FSTPBMutationQueue *)parsedMetadata:(Slice)slice {
+  NSData *data =
+      [[NSData alloc] initWithBytesNoCopy:(void *)slice.data() length:slice.size() freeWhenDone:NO];
+
+  NSError *error;
+  FSTPBMutationQueue *proto = [FSTPBMutationQueue parseFromData:data error:&error];
+  if (!proto) {
+    FSTFail(@"FSTPBMutationQueue failed to parse: %@", error);
+  }
+
+  return proto;
+}
+
+- (FSTMutationBatch *)decodedMutationBatch:(Slice)slice {
+  NSData *data =
+      [[NSData alloc] initWithBytesNoCopy:(void *)slice.data() length:slice.size() freeWhenDone:NO];
+
+  NSError *error;
+  FSTPBWriteBatch *proto = [FSTPBWriteBatch parseFromData:data error:&error];
+  if (!proto) {
+    FSTFail(@"FSTPBMutationBatch failed to parse: %@", error);
+  }
+
+  return [self.serializer decodedMutationBatch:proto];
+}
+
+#pragma mark - FSTGarbageSource implementation
+
+- (BOOL)containsKey:(FSTDocumentKey *)documentKey {
+  std::string indexPrefix =
+      [FSTLevelDBDocumentMutationKey keyPrefixWithUserID:self.userID resourcePath:documentKey.path];
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(StandardReadOptions()));
+  indexIterator->Seek(indexPrefix);
+
+  if (indexIterator->Valid()) {
+    FSTLevelDBDocumentMutationKey *rowKey = [[FSTLevelDBDocumentMutationKey alloc] init];
+    Slice iteratorKey = indexIterator->key();
+
+    // Check both that the key prefix matches and that the decoded document key is exactly the key
+    // we're looking for.
+    if (iteratorKey.starts_with(indexPrefix) && [rowKey decodeKey:iteratorKey] &&
+        [rowKey.documentKey isEqualToKey:documentKey]) {
+      return YES;
+    }
+  }
+
+  return NO;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBQueryCache.h b/Firestore/Source/Local/FSTLevelDBQueryCache.h
new file mode 100644
index 0000000..3f24e6a
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBQueryCache.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTQueryCache.h"
+
+#ifdef __cplusplus
+#include <memory>
+
+namespace leveldb {
+class DB;
+}
+#endif
+
+@class FSTLocalSerializer;
+@protocol FSTGarbageCollector;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** Cached Queries backed by LevelDB. */
+@interface FSTLevelDBQueryCache : NSObject <FSTQueryCache>
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** The garbage collector to notify about potential garbage keys. */
+@property(nonatomic, weak, readwrite, nullable) id<FSTGarbageCollector> garbageCollector;
+
+#ifdef __cplusplus
+/**
+ * Creates a new query cache in the given LevelDB.
+ *
+ * @param db The LevelDB in which to create the cache.
+ */
+- (instancetype)initWithDB:(std::shared_ptr<leveldb::DB>)db
+                serializer:(FSTLocalSerializer *)serializer NS_DESIGNATED_INITIALIZER;
+#endif
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBQueryCache.mm b/Firestore/Source/Local/FSTLevelDBQueryCache.mm
new file mode 100644
index 0000000..c1ba654
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBQueryCache.mm
@@ -0,0 +1,340 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLevelDBQueryCache.h"
+
+#include <leveldb/db.h>
+#include <leveldb/write_batch.h>
+#include <string>
+
+#import "Target.pbobjc.h"
+#import "FSTQuery.h"
+#import "FSTLevelDBKey.h"
+#import "FSTLocalSerializer.h"
+#import "FSTQueryData.h"
+#import "FSTWriteGroup.h"
+#import "FSTDocumentKey.h"
+#import "FSTAssert.h"
+
+#include "ordered_code.h"
+#include "string_util.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+using Firestore::OrderedCode;
+using Firestore::StringView;
+using leveldb::DB;
+using leveldb::Iterator;
+using leveldb::ReadOptions;
+using leveldb::Slice;
+using leveldb::Status;
+using leveldb::WriteOptions;
+
+/**
+ * Returns a standard set of read options.
+ *
+ * For now this is paranoid, but perhaps disable that in production builds.
+ */
+static ReadOptions GetStandardReadOptions() {
+  ReadOptions options;
+  options.verify_checksums = true;
+  return options;
+}
+
+@interface FSTLevelDBQueryCache ()
+
+/** A write-through cached copy of the metadata for the query cache. */
+@property(nonatomic, strong, nullable) FSTPBTargetGlobal *metadata;
+
+@property(nonatomic, strong, readonly) FSTLocalSerializer *serializer;
+
+@end
+
+@implementation FSTLevelDBQueryCache {
+  // The DB pointer is shared with all cooperating LevelDB-related objects.
+  std::shared_ptr<DB> _db;
+
+  /**
+   * The last received snapshot version. This is part of `metadata` but we store it separately to
+   * avoid extra conversion to/from GPBTimestamp.
+   */
+  FSTSnapshotVersion *_lastRemoteSnapshotVersion;
+}
+
+- (instancetype)initWithDB:(std::shared_ptr<DB>)db serializer:(FSTLocalSerializer *)serializer {
+  if (self = [super init]) {
+    FSTAssert(db, @"db must not be NULL");
+    _db = db;
+    _serializer = serializer;
+  }
+  return self;
+}
+
+- (void)start {
+  std::string key = [FSTLevelDBTargetGlobalKey key];
+  FSTPBTargetGlobal *metadata = [self metadataForKey:key];
+  if (!metadata) {
+    metadata = [FSTPBTargetGlobal message];
+  }
+  _lastRemoteSnapshotVersion = [self.serializer decodedVersion:metadata.lastRemoteSnapshotVersion];
+
+  self.metadata = metadata;
+}
+
+#pragma mark - FSTQueryCache implementation
+
+- (FSTTargetID)highestTargetID {
+  return self.metadata.highestTargetId;
+}
+
+- (FSTSnapshotVersion *)lastRemoteSnapshotVersion {
+  return _lastRemoteSnapshotVersion;
+}
+
+- (void)setLastRemoteSnapshotVersion:(FSTSnapshotVersion *)snapshotVersion
+                               group:(FSTWriteGroup *)group {
+  _lastRemoteSnapshotVersion = snapshotVersion;
+  self.metadata.lastRemoteSnapshotVersion = [self.serializer encodedVersion:snapshotVersion];
+  [group setMessage:self.metadata forKey:[FSTLevelDBTargetGlobalKey key]];
+}
+
+- (void)shutdown {
+  _db.reset();
+}
+
+- (void)addQueryData:(FSTQueryData *)queryData group:(FSTWriteGroup *)group {
+  // TODO(mcg): actually populate listen sequence number
+  FSTTargetID targetID = queryData.targetID;
+  std::string key = [FSTLevelDBTargetKey keyWithTargetID:targetID];
+  [group setMessage:[self.serializer encodedQueryData:queryData] forKey:key];
+
+  NSString *canonicalID = queryData.query.canonicalID;
+  std::string indexKey =
+      [FSTLevelDBQueryTargetKey keyWithCanonicalID:canonicalID targetID:targetID];
+  std::string emptyBuffer;
+  [group setData:emptyBuffer forKey:indexKey];
+
+  FSTPBTargetGlobal *metadata = self.metadata;
+  if (targetID > metadata.highestTargetId) {
+    metadata.highestTargetId = targetID;
+    [group setMessage:metadata forKey:[FSTLevelDBTargetGlobalKey key]];
+  }
+}
+
+- (void)removeQueryData:(FSTQueryData *)queryData group:(FSTWriteGroup *)group {
+  FSTTargetID targetID = queryData.targetID;
+
+  [self removeMatchingKeysForTargetID:targetID group:group];
+
+  std::string key = [FSTLevelDBTargetKey keyWithTargetID:targetID];
+  [group removeMessageForKey:key];
+
+  std::string indexKey =
+      [FSTLevelDBQueryTargetKey keyWithCanonicalID:queryData.query.canonicalID targetID:targetID];
+  [group removeMessageForKey:indexKey];
+}
+
+/**
+ * Looks up the query global metadata associated with the given key.
+ *
+ * @return the parsed protocol buffer message or nil if the row referenced by the given key does
+ *     not exist.
+ */
+- (nullable FSTPBTargetGlobal *)metadataForKey:(const std::string &)key {
+  std::string value;
+  Status status = _db->Get(GetStandardReadOptions(), key, &value);
+  if (status.IsNotFound()) {
+    return nil;
+  } else if (!status.ok()) {
+    FSTFail(@"metadataForKey: failed loading key %s with status: %s", key.c_str(),
+            status.ToString().c_str());
+  }
+
+  NSData *data =
+      [[NSData alloc] initWithBytesNoCopy:(void *)value.data() length:value.size() freeWhenDone:NO];
+
+  NSError *error;
+  FSTPBTargetGlobal *proto = [FSTPBTargetGlobal parseFromData:data error:&error];
+  if (!proto) {
+    FSTFail(@"FSTPBTargetGlobal failed to parse: %@", error);
+  }
+
+  return proto;
+}
+
+/**
+ * Parses the given bytes as an FSTPBTarget protocol buffer and then converts to the equivalent
+ * query data.
+ */
+- (FSTQueryData *)decodedTargetWithSlice:(Slice)slice {
+  NSData *data =
+      [[NSData alloc] initWithBytesNoCopy:(void *)slice.data() length:slice.size() freeWhenDone:NO];
+
+  NSError *error;
+  FSTPBTarget *proto = [FSTPBTarget parseFromData:data error:&error];
+  if (!proto) {
+    FSTFail(@"FSTPBTarget failed to parse: %@", error);
+  }
+
+  return [self.serializer decodedQueryData:proto];
+}
+
+- (nullable FSTQueryData *)queryDataForQuery:(FSTQuery *)query {
+  // Scan the query-target index starting with a prefix starting with the given query's canonicalID.
+  // Note that this is a scan rather than a get because canonicalIDs are not required to be unique
+  // per target.
+  Slice canonicalID = StringView(query.canonicalID);
+  std::unique_ptr<Iterator> indexItererator(_db->NewIterator(GetStandardReadOptions()));
+  std::string indexPrefix = [FSTLevelDBQueryTargetKey keyPrefixWithCanonicalID:canonicalID];
+  indexItererator->Seek(indexPrefix);
+
+  // Simultaneously scan the targets table. This works because each (canonicalID, targetID) pair is
+  // unique and ordered, so when scanning a table prefixed by exactly one canonicalID, all the
+  // targetIDs will be unique and in order.
+  std::string targetPrefix = [FSTLevelDBTargetKey keyPrefix];
+  std::unique_ptr<Iterator> targetIterator(_db->NewIterator(GetStandardReadOptions()));
+
+  FSTLevelDBQueryTargetKey *rowKey = [[FSTLevelDBQueryTargetKey alloc] init];
+  for (; indexItererator->Valid(); indexItererator->Next()) {
+    Slice indexKey = indexItererator->key();
+
+    // Only consider rows matching exactly the specific canonicalID of interest.
+    if (!indexKey.starts_with(indexPrefix) || ![rowKey decodeKey:indexKey] ||
+        canonicalID != rowKey.canonicalID) {
+      // End of this canonicalID's possible targets.
+      break;
+    }
+
+    // Each row is a unique combination of canonicalID and targetID, so this foreign key reference
+    // can only occur once.
+    std::string targetKey = [FSTLevelDBTargetKey keyWithTargetID:rowKey.targetID];
+    targetIterator->Seek(targetKey);
+    if (!targetIterator->Valid() || targetIterator->key() != targetKey) {
+      NSString *foundKeyDescription = @"the end of the table";
+      if (targetIterator->Valid()) {
+        foundKeyDescription = [FSTLevelDBKey descriptionForKey:targetIterator->key()];
+      }
+      FSTFail(@"Dangling query-target reference found: "
+              @"%@ points to %@; seeking there found %@",
+              [FSTLevelDBKey descriptionForKey:indexKey],
+              [FSTLevelDBKey descriptionForKey:targetKey], foundKeyDescription);
+    }
+
+    // Finally after finding a potential match, check that the query is actually equal to the
+    // requested query.
+    FSTQueryData *target = [self decodedTargetWithSlice:targetIterator->value()];
+    if ([target.query isEqual:query]) {
+      return target;
+    }
+  }
+
+  return nil;
+}
+
+#pragma mark Matching Key tracking
+
+- (void)addMatchingKeys:(FSTDocumentKeySet *)keys
+            forTargetID:(FSTTargetID)targetID
+                  group:(FSTWriteGroup *)group {
+  // Store an empty value in the index which is equivalent to serializing a GPBEmpty message. In the
+  // future if we wanted to store some other kind of value here, we can parse these empty values as
+  // with some other protocol buffer (and the parser will see all default values).
+  std::string emptyBuffer;
+
+  [keys enumerateObjectsUsingBlock:^(FSTDocumentKey *documentKey, BOOL *stop) {
+    [group setData:emptyBuffer
+            forKey:[FSTLevelDBTargetDocumentKey keyWithTargetID:targetID documentKey:documentKey]];
+    [group setData:emptyBuffer
+            forKey:[FSTLevelDBDocumentTargetKey keyWithDocumentKey:documentKey targetID:targetID]];
+  }];
+}
+
+- (void)removeMatchingKeys:(FSTDocumentKeySet *)keys
+               forTargetID:(FSTTargetID)targetID
+                     group:(FSTWriteGroup *)group {
+  [keys enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+    [group
+        removeMessageForKey:[FSTLevelDBTargetDocumentKey keyWithTargetID:targetID documentKey:key]];
+    [group
+        removeMessageForKey:[FSTLevelDBDocumentTargetKey keyWithDocumentKey:key targetID:targetID]];
+    [self.garbageCollector addPotentialGarbageKey:key];
+  }];
+}
+
+- (void)removeMatchingKeysForTargetID:(FSTTargetID)targetID group:(FSTWriteGroup *)group {
+  std::string indexPrefix = [FSTLevelDBTargetDocumentKey keyPrefixWithTargetID:targetID];
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(GetStandardReadOptions()));
+  indexIterator->Seek(indexPrefix);
+
+  FSTLevelDBTargetDocumentKey *rowKey = [[FSTLevelDBTargetDocumentKey alloc] init];
+  for (; indexIterator->Valid(); indexIterator->Next()) {
+    Slice indexKey = indexIterator->key();
+
+    // Only consider rows matching this specific targetID.
+    if (![rowKey decodeKey:indexKey] || rowKey.targetID != targetID) {
+      break;
+    }
+    FSTDocumentKey *documentKey = rowKey.documentKey;
+
+    // Delete both index rows
+    [group removeMessageForKey:indexKey];
+    [group removeMessageForKey:[FSTLevelDBDocumentTargetKey keyWithDocumentKey:documentKey
+                                                                      targetID:targetID]];
+    [self.garbageCollector addPotentialGarbageKey:documentKey];
+  }
+}
+
+- (FSTDocumentKeySet *)matchingKeysForTargetID:(FSTTargetID)targetID {
+  std::string indexPrefix = [FSTLevelDBTargetDocumentKey keyPrefixWithTargetID:targetID];
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(GetStandardReadOptions()));
+  indexIterator->Seek(indexPrefix);
+
+  FSTDocumentKeySet *result = [FSTDocumentKeySet keySet];
+  FSTLevelDBTargetDocumentKey *rowKey = [[FSTLevelDBTargetDocumentKey alloc] init];
+  for (; indexIterator->Valid(); indexIterator->Next()) {
+    Slice indexKey = indexIterator->key();
+
+    // Only consider rows matching this specific targetID.
+    if (![rowKey decodeKey:indexKey] || rowKey.targetID != targetID) {
+      break;
+    }
+
+    result = [result setByAddingObject:rowKey.documentKey];
+  }
+
+  return result;
+}
+
+#pragma mark - FSTGarbageSource implementation
+
+- (BOOL)containsKey:(FSTDocumentKey *)key {
+  std::string indexPrefix = [FSTLevelDBDocumentTargetKey keyPrefixWithResourcePath:key.path];
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(GetStandardReadOptions()));
+  indexIterator->Seek(indexPrefix);
+
+  if (indexIterator->Valid()) {
+    FSTLevelDBDocumentTargetKey *rowKey = [[FSTLevelDBDocumentTargetKey alloc] init];
+    if ([rowKey decodeKey:indexIterator->key()] && [rowKey.documentKey isEqualToKey:key]) {
+      return YES;
+    }
+  }
+
+  return NO;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.h b/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.h
new file mode 100644
index 0000000..f327813
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.h
@@ -0,0 +1,50 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTRemoteDocumentCache.h"
+
+#ifdef __cplusplus
+#include <memory>
+
+namespace leveldb {
+class DB;
+}
+#endif
+
+@class FSTLocalSerializer;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** Cached Remote Documents backed by leveldb. */
+@interface FSTLevelDBRemoteDocumentCache : NSObject <FSTRemoteDocumentCache>
+
+- (instancetype)init NS_UNAVAILABLE;
+
+#ifdef __cplusplus
+/**
+ * Creates a new remote documents cache in the given leveldb.
+ *
+ * @param db The leveldb in which to create the cache.
+ */
+- (instancetype)initWithDB:(std::shared_ptr<leveldb::DB>)db
+                serializer:(FSTLocalSerializer *)serializer NS_DESIGNATED_INITIALIZER;
+#endif
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.mm b/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.mm
new file mode 100644
index 0000000..e2424b9
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.mm
@@ -0,0 +1,153 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLevelDBRemoteDocumentCache.h"
+
+#include <leveldb/db.h>
+#include <leveldb/write_batch.h>
+#include <string>
+
+#import "MaybeDocument.pbobjc.h"
+#import "FSTLevelDBKey.h"
+#import "FSTLocalSerializer.h"
+#import "FSTWriteGroup.h"
+#import "FSTDocument.h"
+#import "FSTDocumentDictionary.h"
+#import "FSTDocumentKey.h"
+#import "FSTDocumentSet.h"
+#import "FSTAssert.h"
+
+#include "ordered_code.h"
+#include "string_util.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+using Firestore::OrderedCode;
+using leveldb::DB;
+using leveldb::Iterator;
+using leveldb::ReadOptions;
+using leveldb::Slice;
+using leveldb::Status;
+using leveldb::WriteOptions;
+
+@interface FSTLevelDBRemoteDocumentCache ()
+
+@property(nonatomic, strong, readonly) FSTLocalSerializer *serializer;
+
+@end
+
+/**
+ * Returns a standard set of read options.
+ *
+ * For now this is paranoid, but perhaps disable that in production builds.
+ */
+static ReadOptions StandardReadOptions() {
+  ReadOptions options;
+  options.verify_checksums = true;
+  return options;
+}
+
+@implementation FSTLevelDBRemoteDocumentCache {
+  // The DB pointer is shared with all cooperating LevelDB-related objects.
+  std::shared_ptr<DB> _db;
+}
+
+- (instancetype)initWithDB:(std::shared_ptr<DB>)db serializer:(FSTLocalSerializer *)serializer {
+  if (self = [super init]) {
+    _db = db;
+    _serializer = serializer;
+  }
+  return self;
+}
+
+- (void)shutdown {
+  _db.reset();
+}
+
+- (void)addEntry:(FSTMaybeDocument *)document group:(FSTWriteGroup *)group {
+  std::string key = [self remoteDocumentKey:document.key];
+  [group setMessage:[self.serializer encodedMaybeDocument:document] forKey:key];
+}
+
+- (void)removeEntryForKey:(FSTDocumentKey *)documentKey group:(FSTWriteGroup *)group {
+  std::string key = [self remoteDocumentKey:documentKey];
+  [group removeMessageForKey:key];
+}
+
+- (nullable FSTMaybeDocument *)entryForKey:(FSTDocumentKey *)documentKey {
+  std::string key = [FSTLevelDBRemoteDocumentKey keyWithDocumentKey:documentKey];
+  std::string value;
+  Status status = _db->Get(StandardReadOptions(), key, &value);
+  if (status.IsNotFound()) {
+    return nil;
+  } else if (status.ok()) {
+    return [self decodedMaybeDocument:value withKey:documentKey];
+  } else {
+    FSTFail(@"Fetch document for key (%@) failed with status: %s", documentKey,
+            status.ToString().c_str());
+  }
+}
+
+- (FSTDocumentDictionary *)documentsMatchingQuery:(FSTQuery *)query {
+  // TODO(mikelehen): PERF: At least filter to the documents that match the path of the query.
+  FSTDocumentDictionary *results = [FSTDocumentDictionary documentDictionary];
+
+  std::string startKey = [FSTLevelDBRemoteDocumentKey keyPrefix];
+  std::unique_ptr<Iterator> it(_db->NewIterator(StandardReadOptions()));
+  it->Seek(startKey);
+
+  FSTLevelDBRemoteDocumentKey *currentKey = [[FSTLevelDBRemoteDocumentKey alloc] init];
+  for (; it->Valid() && [currentKey decodeKey:it->key()]; it->Next()) {
+    FSTMaybeDocument *maybeDoc =
+        [self decodedMaybeDocument:it->value() withKey:currentKey.documentKey];
+    if ([maybeDoc isKindOfClass:[FSTDocument class]]) {
+      results = [results dictionaryBySettingObject:(FSTDocument *)maybeDoc forKey:maybeDoc.key];
+    }
+  }
+
+  Status status = it->status();
+  if (!status.ok()) {
+    FSTFail(@"Find documents matching query (%@) failed with status: %s", query,
+            status.ToString().c_str());
+  }
+
+  return results;
+}
+
+- (std::string)remoteDocumentKey:(FSTDocumentKey *)key {
+  return [FSTLevelDBRemoteDocumentKey keyWithDocumentKey:key];
+}
+
+- (FSTMaybeDocument *)decodedMaybeDocument:(Slice)slice withKey:(FSTDocumentKey *)documentKey {
+  NSData *data =
+      [[NSData alloc] initWithBytesNoCopy:(void *)slice.data() length:slice.size() freeWhenDone:NO];
+
+  NSError *error;
+  FSTPBMaybeDocument *proto = [FSTPBMaybeDocument parseFromData:data error:&error];
+  if (!proto) {
+    FSTFail(@"FSTPBMaybeDocument failed to parse: %@", error);
+  }
+
+  FSTMaybeDocument *maybeDocument = [self.serializer decodedMaybeDocument:proto];
+  FSTAssert([maybeDocument.key isEqualToKey:documentKey],
+            @"Read document has key (%@) instead of expected key (%@).", maybeDocument.key,
+            documentKey);
+  return maybeDocument;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalDocumentsView.h b/Firestore/Source/Local/FSTLocalDocumentsView.h
new file mode 100644
index 0000000..60571c2
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalDocumentsView.h
@@ -0,0 +1,62 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTDocumentDictionary.h"
+#import "FSTDocumentKeySet.h"
+
+@class FSTDocumentKey;
+@class FSTMaybeDocument;
+@class FSTQuery;
+@protocol FSTMutationQueue;
+@protocol FSTRemoteDocumentCache;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * A readonly view of the local state of all documents we're tracking (i.e. we have a cached
+ * version in remoteDocumentCache or local mutations for the document). The view is computed by
+ * applying the mutations in the FSTMutationQueue to the FSTRemoteDocumentCache.
+ */
+@interface FSTLocalDocumentsView : NSObject
+
++ (instancetype)viewWithRemoteDocumentCache:(id<FSTRemoteDocumentCache>)remoteDocumentCache
+                              mutationQueue:(id<FSTMutationQueue>)mutationQueue;
+
+- (instancetype)init __attribute__((unavailable("Use a static constructor")));
+
+/**
+ * Get the local view of the document identified by `key`.
+ *
+ * @return Local view of the document or nil if we don't have any cached state for it.
+ */
+- (nullable FSTMaybeDocument *)documentForKey:(FSTDocumentKey *)key;
+
+/**
+ * Gets the local view of the documents identified by `keys`.
+ *
+ * If we don't have cached state for a document in `keys`, a FSTDeletedDocument will be stored
+ * for that key in the resulting set.
+ */
+- (FSTMaybeDocumentDictionary *)documentsForKeys:(FSTDocumentKeySet *)keys;
+
+/** Performs a query against the local view of all documents. */
+- (FSTDocumentDictionary *)documentsMatchingQuery:(FSTQuery *)query;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalDocumentsView.m b/Firestore/Source/Local/FSTLocalDocumentsView.m
new file mode 100644
index 0000000..0cad593
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalDocumentsView.m
@@ -0,0 +1,182 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLocalDocumentsView.h"
+
+#import "FSTAssert.h"
+#import "FSTDocument.h"
+#import "FSTDocumentDictionary.h"
+#import "FSTDocumentKey.h"
+#import "FSTMutation.h"
+#import "FSTMutationBatch.h"
+#import "FSTMutationQueue.h"
+#import "FSTQuery.h"
+#import "FSTRemoteDocumentCache.h"
+#import "FSTSnapshotVersion.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLocalDocumentsView ()
+- (instancetype)initWithRemoteDocumentCache:(id<FSTRemoteDocumentCache>)remoteDocumentCache
+                              mutationQueue:(id<FSTMutationQueue>)mutationQueue
+    NS_DESIGNATED_INITIALIZER;
+@property(nonatomic, strong, readonly) id<FSTRemoteDocumentCache> remoteDocumentCache;
+@property(nonatomic, strong, readonly) id<FSTMutationQueue> mutationQueue;
+@end
+
+@implementation FSTLocalDocumentsView
+
++ (instancetype)viewWithRemoteDocumentCache:(id<FSTRemoteDocumentCache>)remoteDocumentCache
+                              mutationQueue:(id<FSTMutationQueue>)mutationQueue {
+  return [[FSTLocalDocumentsView alloc] initWithRemoteDocumentCache:remoteDocumentCache
+                                                      mutationQueue:mutationQueue];
+}
+
+- (instancetype)initWithRemoteDocumentCache:(id<FSTRemoteDocumentCache>)remoteDocumentCache
+                              mutationQueue:(id<FSTMutationQueue>)mutationQueue {
+  if (self = [super init]) {
+    _remoteDocumentCache = remoteDocumentCache;
+    _mutationQueue = mutationQueue;
+  }
+  return self;
+}
+
+- (nullable FSTMaybeDocument *)documentForKey:(FSTDocumentKey *)key {
+  FSTMaybeDocument *_Nullable remoteDoc = [self.remoteDocumentCache entryForKey:key];
+  return [self localDocument:remoteDoc key:key];
+}
+
+- (FSTMaybeDocumentDictionary *)documentsForKeys:(FSTDocumentKeySet *)keys {
+  FSTMaybeDocumentDictionary *results = [FSTMaybeDocumentDictionary maybeDocumentDictionary];
+  for (FSTDocumentKey *key in keys.objectEnumerator) {
+    // TODO(mikelehen): PERF: Consider fetching all remote documents at once rather than one-by-one.
+    FSTMaybeDocument *maybeDoc = [self documentForKey:key];
+    // TODO(http://b/32275378): Don't conflate missing / deleted.
+    if (!maybeDoc) {
+      maybeDoc = [FSTDeletedDocument documentWithKey:key version:[FSTSnapshotVersion noVersion]];
+    }
+    results = [results dictionaryBySettingObject:maybeDoc forKey:key];
+  }
+  return results;
+}
+
+- (FSTDocumentDictionary *)documentsMatchingQuery:(FSTQuery *)query {
+  if ([FSTDocumentKey isDocumentKey:query.path]) {
+    return [self documentsMatchingDocumentQuery:query.path];
+  } else {
+    return [self documentsMatchingCollectionQuery:query];
+  }
+}
+
+- (FSTDocumentDictionary *)documentsMatchingDocumentQuery:(FSTResourcePath *)docPath {
+  FSTDocumentDictionary *result = [FSTDocumentDictionary documentDictionary];
+  // Just do a simple document lookup.
+  FSTMaybeDocument *doc = [self documentForKey:[FSTDocumentKey keyWithPath:docPath]];
+  if ([doc isKindOfClass:[FSTDocument class]]) {
+    result = [result dictionaryBySettingObject:(FSTDocument *)doc forKey:doc.key];
+  }
+  return result;
+}
+
+- (FSTDocumentDictionary *)documentsMatchingCollectionQuery:(FSTQuery *)query {
+  // Query the remote documents and overlay mutations.
+  // TODO(mikelehen): There may be significant overlap between the mutations affecting these
+  // remote documents and the allMutationBatchesAffectingQuery mutations. Consider optimizing.
+  __block FSTDocumentDictionary *results = [self.remoteDocumentCache documentsMatchingQuery:query];
+  results = [self localDocuments:results];
+
+  // Now use the mutation queue to discover any other documents that may match the query after
+  // applying mutations.
+  FSTDocumentKeySet *matchingKeys = [FSTDocumentKeySet keySet];
+  NSArray<FSTMutationBatch *> *matchingMutationBatches =
+      [self.mutationQueue allMutationBatchesAffectingQuery:query];
+  for (FSTMutationBatch *batch in matchingMutationBatches) {
+    for (FSTMutation *mutation in batch.mutations) {
+      // TODO(mikelehen): PERF: Check if this mutation actually affects the query to reduce work.
+
+      // If the key is already in the results, we can skip it.
+      if (![results containsKey:mutation.key]) {
+        matchingKeys = [matchingKeys setByAddingObject:mutation.key];
+      }
+    }
+  }
+
+  // Now add in results for the matchingKeys.
+  for (FSTDocumentKey *key in matchingKeys.objectEnumerator) {
+    FSTMaybeDocument *doc = [self documentForKey:key];
+    if ([doc isKindOfClass:[FSTDocument class]]) {
+      results = [results dictionaryBySettingObject:(FSTDocument *)doc forKey:key];
+    }
+  }
+
+  // Finally, filter out any documents that don't actually match the query. Note that the extra
+  // reference here prevents ARC from deallocating the initial unfiltered results while we're
+  // enumerating them.
+  FSTDocumentDictionary *unfiltered = results;
+  [unfiltered
+      enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key, FSTDocument *doc, BOOL *stop) {
+        if (![query matchesDocument:doc]) {
+          results = [results dictionaryByRemovingObjectForKey:key];
+        }
+      }];
+
+  return results;
+}
+
+/**
+ * Takes a remote document and applies local mutations to generate the local view of the
+ * document.
+ *
+ * @param document The base remote document to apply mutations to.
+ * @param documentKey The key of the document (necessary when remoteDocument is nil).
+ */
+- (nullable FSTMaybeDocument *)localDocument:(nullable FSTMaybeDocument *)document
+                                         key:(FSTDocumentKey *)documentKey {
+  NSArray<FSTMutationBatch *> *batches =
+      [self.mutationQueue allMutationBatchesAffectingDocumentKey:documentKey];
+  for (FSTMutationBatch *batch in batches) {
+    document = [batch applyTo:document documentKey:documentKey];
+  }
+
+  return document;
+}
+
+/**
+ * Takes a set of remote documents and applies local mutations to generate the local view of
+ * the documents.
+ *
+ * @param documents The base remote documents to apply mutations to.
+ * @return The local view of the documents.
+ */
+- (FSTDocumentDictionary *)localDocuments:(FSTDocumentDictionary *)documents {
+  __block FSTDocumentDictionary *result = documents;
+  [documents enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key, FSTDocument *remoteDocument,
+                                                 BOOL *stop) {
+    FSTMaybeDocument *mutatedDoc = [self localDocument:remoteDocument key:key];
+    if ([mutatedDoc isKindOfClass:[FSTDeletedDocument class]]) {
+      result = [documents dictionaryByRemovingObjectForKey:key];
+    } else if ([mutatedDoc isKindOfClass:[FSTDocument class]]) {
+      result = [documents dictionaryBySettingObject:(FSTDocument *)mutatedDoc forKey:key];
+    } else {
+      FSTFail(@"Unknown document: %@", mutatedDoc);
+    }
+  }];
+  return result;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalSerializer.h b/Firestore/Source/Local/FSTLocalSerializer.h
new file mode 100644
index 0000000..6ca7f01
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalSerializer.h
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+@class FSTMaybeDocument;
+@class FSTMutationBatch;
+@class FSTQueryData;
+@class FSTSerializerBeta;
+@class FSTSnapshotVersion;
+
+@class FSTPBMaybeDocument;
+@class FSTPBTarget;
+@class FSTPBWriteBatch;
+
+@class GPBTimestamp;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * Serializer for values stored in the LocalStore.
+ *
+ * Note that FSTLocalSerializer currently delegates to the serializer for the Firestore v1beta1 RPC
+ * protocol to save implementation time and code duplication. We'll need to revisit this when the
+ * RPC protocol we use diverges from local storage.
+ */
+@interface FSTLocalSerializer : NSObject
+
+- (instancetype)initWithRemoteSerializer:(FSTSerializerBeta *)remoteSerializer;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** Encodes an FSTMaybeDocument model to the equivalent protocol buffer for local storage. */
+- (FSTPBMaybeDocument *)encodedMaybeDocument:(FSTMaybeDocument *)document;
+
+/** Decodes an FSTPBMaybeDocument proto to the equivalent model. */
+- (FSTMaybeDocument *)decodedMaybeDocument:(FSTPBMaybeDocument *)proto;
+
+/** Encodes an FSTMutationBatch model for local storage in the mutation queue. */
+- (FSTPBWriteBatch *)encodedMutationBatch:(FSTMutationBatch *)batch;
+
+/** Decodes an FSTPBWriteBatch proto into a MutationBatch model. */
+- (FSTMutationBatch *)decodedMutationBatch:(FSTPBWriteBatch *)batch;
+
+/** Encodes an FSTQueryData model for local storage in the query cache. */
+- (FSTPBTarget *)encodedQueryData:(FSTQueryData *)queryData;
+
+/** Decodes an FSTPBTarget proto from local storage into an FSTQueryData model. */
+- (FSTQueryData *)decodedQueryData:(FSTPBTarget *)target;
+
+/** Encodes an FSTSnapshotVersion model into a GPBTimestamp proto. */
+- (GPBTimestamp *)encodedVersion:(FSTSnapshotVersion *)version;
+
+/** Decodes a GPBTimestamp proto into a FSTSnapshotVersion model. */
+- (FSTSnapshotVersion *)decodedVersion:(GPBTimestamp *)version;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalSerializer.m b/Firestore/Source/Local/FSTLocalSerializer.m
new file mode 100644
index 0000000..58b09af
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalSerializer.m
@@ -0,0 +1,208 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLocalSerializer.h"
+
+#import "Document.pbobjc.h"
+#import "FSTAssert.h"
+#import "FSTDocument.h"
+#import "FSTFieldValue.h"
+#import "FSTMutationBatch.h"
+#import "FSTQuery.h"
+#import "FSTQueryData.h"
+#import "FSTSerializerBeta.h"
+#import "MaybeDocument.pbobjc.h"
+#import "Mutation.pbobjc.h"
+#import "Target.pbobjc.h"
+
+@interface FSTLocalSerializer ()
+
+@property(nonatomic, strong, readonly) FSTSerializerBeta *remoteSerializer;
+
+@end
+
+/** Serializer for values stored in the LocalStore. */
+@implementation FSTLocalSerializer
+
+- (instancetype)initWithRemoteSerializer:(FSTSerializerBeta *)remoteSerializer {
+  self = [super init];
+  if (self) {
+    _remoteSerializer = remoteSerializer;
+  }
+  return self;
+}
+
+- (FSTPBMaybeDocument *)encodedMaybeDocument:(FSTMaybeDocument *)document {
+  FSTPBMaybeDocument *proto = [FSTPBMaybeDocument message];
+
+  if ([document isKindOfClass:[FSTDeletedDocument class]]) {
+    proto.noDocument = [self encodedDeletedDocument:(FSTDeletedDocument *)document];
+  } else if ([document isKindOfClass:[FSTDocument class]]) {
+    proto.document = [self encodedDocument:(FSTDocument *)document];
+  } else {
+    FSTFail(@"Unknown document type %@", NSStringFromClass([document class]));
+  }
+
+  return proto;
+}
+
+- (FSTMaybeDocument *)decodedMaybeDocument:(FSTPBMaybeDocument *)proto {
+  switch (proto.documentTypeOneOfCase) {
+    case FSTPBMaybeDocument_DocumentType_OneOfCase_Document:
+      return [self decodedDocument:proto.document];
+
+    case FSTPBMaybeDocument_DocumentType_OneOfCase_NoDocument:
+      return [self decodedDeletedDocument:proto.noDocument];
+
+    default:
+      FSTFail(@"Unknown MaybeDocument %@", proto);
+  }
+}
+
+/**
+ * Encodes a Document for local storage. This differs from the v1beta1 RPC serializer for
+ * Documents in that it preserves the updateTime, which is considered an output only value by the
+ * server.
+ */
+- (GCFSDocument *)encodedDocument:(FSTDocument *)document {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  GCFSDocument *proto = [GCFSDocument message];
+  proto.name = [remoteSerializer encodedDocumentKey:document.key];
+  proto.fields = [remoteSerializer encodedFields:document.data];
+  proto.updateTime = [remoteSerializer encodedVersion:document.version];
+
+  return proto;
+}
+
+/** Decodes a Document proto to the equivalent model. */
+- (FSTDocument *)decodedDocument:(GCFSDocument *)document {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  FSTObjectValue *data = [remoteSerializer decodedFields:document.fields];
+  FSTDocumentKey *key = [remoteSerializer decodedDocumentKey:document.name];
+  FSTSnapshotVersion *version = [remoteSerializer decodedVersion:document.updateTime];
+  return [FSTDocument documentWithData:data key:key version:version hasLocalMutations:NO];
+}
+
+/** Encodes a NoDocument value to the equivalent proto. */
+- (FSTPBNoDocument *)encodedDeletedDocument:(FSTDeletedDocument *)document {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  FSTPBNoDocument *proto = [FSTPBNoDocument message];
+  proto.name = [remoteSerializer encodedDocumentKey:document.key];
+  proto.readTime = [remoteSerializer encodedVersion:document.version];
+  return proto;
+}
+
+/** Decodes a NoDocument proto to the equivalent model. */
+- (FSTDeletedDocument *)decodedDeletedDocument:(FSTPBNoDocument *)proto {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  FSTDocumentKey *key = [remoteSerializer decodedDocumentKey:proto.name];
+  FSTSnapshotVersion *version = [remoteSerializer decodedVersion:proto.readTime];
+  return [FSTDeletedDocument documentWithKey:key version:version];
+}
+
+- (FSTPBWriteBatch *)encodedMutationBatch:(FSTMutationBatch *)batch {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  FSTPBWriteBatch *proto = [FSTPBWriteBatch message];
+  proto.batchId = batch.batchID;
+  proto.localWriteTime = [remoteSerializer encodedTimestamp:batch.localWriteTime];
+
+  NSMutableArray<GCFSWrite *> *writes = proto.writesArray;
+  for (FSTMutation *mutation in batch.mutations) {
+    [writes addObject:[remoteSerializer encodedMutation:mutation]];
+  }
+  return proto;
+}
+
+- (FSTMutationBatch *)decodedMutationBatch:(FSTPBWriteBatch *)batch {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  int batchID = batch.batchId;
+  NSMutableArray<FSTMutation *> *mutations = [NSMutableArray array];
+  for (GCFSWrite *write in batch.writesArray) {
+    [mutations addObject:[remoteSerializer decodedMutation:write]];
+  }
+
+  FSTTimestamp *localWriteTime = [remoteSerializer decodedTimestamp:batch.localWriteTime];
+
+  return [[FSTMutationBatch alloc] initWithBatchID:batchID
+                                    localWriteTime:localWriteTime
+                                         mutations:mutations];
+}
+
+- (FSTPBTarget *)encodedQueryData:(FSTQueryData *)queryData {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  FSTAssert(queryData.purpose == FSTQueryPurposeListen,
+            @"only queries with purpose %lu may be stored, got %lu",
+            (unsigned long)FSTQueryPurposeListen, (unsigned long)queryData.purpose);
+
+  FSTPBTarget *proto = [FSTPBTarget message];
+  proto.targetId = queryData.targetID;
+  proto.snapshotVersion = [remoteSerializer encodedVersion:queryData.snapshotVersion];
+  proto.resumeToken = queryData.resumeToken;
+
+  FSTQuery *query = queryData.query;
+  if ([query isDocumentQuery]) {
+    proto.documents = [remoteSerializer encodedDocumentsTarget:query];
+  } else {
+    proto.query = [remoteSerializer encodedQueryTarget:query];
+  }
+
+  return proto;
+}
+
+- (FSTQueryData *)decodedQueryData:(FSTPBTarget *)target {
+  FSTSerializerBeta *remoteSerializer = self.remoteSerializer;
+
+  FSTTargetID targetID = target.targetId;
+  FSTSnapshotVersion *version = [remoteSerializer decodedVersion:target.snapshotVersion];
+  NSData *resumeToken = target.resumeToken;
+
+  FSTQuery *query;
+  switch (target.targetTypeOneOfCase) {
+    case FSTPBTarget_TargetType_OneOfCase_Documents:
+      query = [remoteSerializer decodedQueryFromDocumentsTarget:target.documents];
+      break;
+
+    case FSTPBTarget_TargetType_OneOfCase_Query:
+      query = [remoteSerializer decodedQueryFromQueryTarget:target.query];
+      break;
+
+    default:
+      FSTFail(@"Unknown Target.targetType %" PRId32, target.targetTypeOneOfCase);
+  }
+
+  return [[FSTQueryData alloc] initWithQuery:query
+                                    targetID:targetID
+                                     purpose:FSTQueryPurposeListen
+                             snapshotVersion:version
+                                 resumeToken:resumeToken];
+}
+
+- (GPBTimestamp *)encodedVersion:(FSTSnapshotVersion *)version {
+  return [self.remoteSerializer encodedVersion:version];
+}
+
+- (FSTSnapshotVersion *)decodedVersion:(GPBTimestamp *)version {
+  return [self.remoteSerializer decodedVersion:version];
+}
+
+@end
diff --git a/Firestore/Source/Local/FSTLocalStore.h b/Firestore/Source/Local/FSTLocalStore.h
new file mode 100644
index 0000000..0fdc08e
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalStore.h
@@ -0,0 +1,194 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTDocumentDictionary.h"
+#import "FSTDocumentKeySet.h"
+#import "FSTDocumentVersionDictionary.h"
+#import "FSTTypes.h"
+
+@class FSTLocalViewChanges;
+@class FSTLocalWriteResult;
+@class FSTMutation;
+@class FSTMutationBatch;
+@class FSTMutationBatchResult;
+@class FSTQuery;
+@class FSTQueryData;
+@class FSTRemoteEvent;
+@class FSTUser;
+@protocol FSTPersistence;
+@protocol FSTGarbageCollector;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * Local storage in the Firestore client. Coordinates persistence components like the mutation
+ * queue and remote document cache to present a latency compensated view of stored data.
+ *
+ * The LocalStore is responsible for accepting mutations from the Sync Engine. Writes from the
+ * client are put into a queue as provisional Mutations until they are processed by the RemoteStore
+ * and confirmed as having been written to the server.
+ *
+ * The local store provides the local version of documents that have been modified locally. It
+ * maintains the constraint:
+ *
+ *  LocalDocument = RemoteDocument + Active(LocalMutations)
+ *
+ * (Active mutations are those that are enqueued and have not been previously acknowledged or
+ * rejected).
+ *
+ * The RemoteDocument ("ground truth") state is provided via the applyChangeBatch method. It will
+ * be some version of a server-provided document OR will be a server-provided document PLUS
+ * acknowledged mutations:
+ *
+ *  RemoteDocument' = RemoteDocument + Acknowledged(LocalMutations)
+ *
+ * Note that this "dirty" version of a RemoteDocument will not be identical to a server base
+ * version, since it has LocalMutations added to it pending getting an authoritative copy from the
+ * server.
+ *
+ * Since LocalMutations can be rejected by the server, we have to be able to revert a LocalMutation
+ * that has already been applied to the LocalDocument (typically done by replaying all remaining
+ * LocalMutations to the RemoteDocument to re-apply).
+ *
+ * The LocalStore is responsible for the garbage collection of the documents it contains. For now,
+ * it every doc referenced by a view, the mutation queue, or the RemoteStore.
+ *
+ * It also maintains the persistence of mapping queries to resume tokens and target ids. It needs
+ * to know this data about queries to properly know what docs it would be allowed to garbage
+ * collect.
+ *
+ * The LocalStore must be able to efficiently execute queries against its local cache of the
+ * documents, to provide the initial set of results before any remote changes have been received.
+ */
+@interface FSTLocalStore : NSObject
+
+/** Creates a new instance of the FSTLocalStore with its required dependencies as parameters. */
+- (instancetype)initWithPersistence:(id<FSTPersistence>)persistence
+                   garbageCollector:(id<FSTGarbageCollector>)garbageCollector
+                        initialUser:(FSTUser *)initialUser NS_DESIGNATED_INITIALIZER;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** Performs any initial startup actions required by the local store. */
+- (void)start;
+
+/** Releases any open resources. */
+- (void)shutdown;
+
+/**
+ * Tells the FSTLocalStore that the currently authenticated user has changed.
+ *
+ * In response the local store switches the mutation queue to the new user and returns any
+ * resulting document changes.
+ */
+- (FSTMaybeDocumentDictionary *)userDidChange:(FSTUser *)user;
+
+/** Accepts locally generated Mutations and commits them to storage. */
+- (FSTLocalWriteResult *)locallyWriteMutations:(NSArray<FSTMutation *> *)mutations;
+
+/** Returns the current value of a document with a given key, or nil if not found. */
+- (nullable FSTMaybeDocument *)readDocument:(FSTDocumentKey *)key;
+
+/**
+ * Acknowledges the given batch.
+ *
+ * On the happy path when a batch is acknowledged, the local store will
+ *
+ * + remove the batch from the mutation queue;
+ * + apply the changes to the remote document cache;
+ * + recalculate the latency compensated view implied by those changes (there may be mutations in
+ *   the queue that affect the documents but haven't been acknowledged yet); and
+ * + give the changed documents back the sync engine
+ *
+ * @return The resulting (modified) documents.
+ */
+- (FSTMaybeDocumentDictionary *)acknowledgeBatchWithResult:(FSTMutationBatchResult *)batchResult;
+
+/**
+ * Removes mutations from the MutationQueue for the specified batch. LocalDocuments will be
+ * recalculated.
+ *
+ * @return The resulting (modified) documents.
+ */
+- (FSTMaybeDocumentDictionary *)rejectBatchID:(FSTBatchID)batchID;
+
+/** Returns the last recorded stream token for the current user. */
+- (nullable NSData *)lastStreamToken;
+
+/**
+ * Sets the stream token for the current user without acknowledging any mutation batch. This is
+ * usually only useful after a stream handshake or in response to an error that requires clearing
+ * the stream token.
+ */
+- (void)setLastStreamToken:(nullable NSData *)streamToken;
+
+/**
+ * Returns the last consistent snapshot processed (used by the RemoteStore to determine whether to
+ * buffer incoming snapshots from the backend).
+ */
+- (FSTSnapshotVersion *)lastRemoteSnapshotVersion;
+
+/**
+ * Updates the "ground-state" (remote) documents. We assume that the remote event reflects any
+ * write batches that have been acknowledged or rejected (i.e. we do not re-apply local mutations
+ * to updates from this event).
+ *
+ * LocalDocuments are re-calculated if there are remaining mutations in the queue.
+ */
+- (FSTMaybeDocumentDictionary *)applyRemoteEvent:(FSTRemoteEvent *)remoteEvent;
+
+/**
+ * Returns the keys of the documents that are associated with the given targetID in the remote
+ * table.
+ */
+- (FSTDocumentKeySet *)remoteDocumentKeysForTarget:(FSTTargetID)targetID;
+
+/**
+ * Collects garbage if necessary.
+ *
+ * Should be called periodically by Sync Engine to recover resources. The implementation must
+ * guarantee that GC won't happen in other places than this method call.
+ */
+- (void)collectGarbage;
+
+/**
+ * Assigns @a query an internal ID so that its results can be pinned so they don't get GC'd.
+ * A query must be allocated in the local store before the store can be used to manage its view.
+ */
+- (FSTQueryData *)allocateQuery:(FSTQuery *)query;
+
+/** Unpin all the documents associated with @a query. */
+- (void)releaseQuery:(FSTQuery *)query;
+
+/** Runs @a query against all the documents in the local store and returns the results. */
+- (FSTDocumentDictionary *)executeQuery:(FSTQuery *)query;
+
+/** Notify the local store of the changed views to locally pin / unpin documents. */
+- (void)notifyLocalViewChanges:(NSArray<FSTLocalViewChanges *> *)viewChanges;
+
+/**
+ * Gets the mutation batch after the passed in batchId in the mutation queue or nil if empty.
+ *
+ * @param batchID The batch to search after, or -1 for the first mutation in the queue.
+ * @return the next mutation or nil if there wasn't one.
+ */
+- (nullable FSTMutationBatch *)nextMutationBatchAfterBatchID:(FSTBatchID)batchID;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalStore.m b/Firestore/Source/Local/FSTLocalStore.m
new file mode 100644
index 0000000..d31712a
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalStore.m
@@ -0,0 +1,546 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLocalStore.h"
+
+#import "FSTAssert.h"
+#import "FSTDocument.h"
+#import "FSTDocumentDictionary.h"
+#import "FSTDocumentKey.h"
+#import "FSTGarbageCollector.h"
+#import "FSTLocalDocumentsView.h"
+#import "FSTLocalViewChanges.h"
+#import "FSTLocalWriteResult.h"
+#import "FSTLogger.h"
+#import "FSTMutation.h"
+#import "FSTMutationBatch.h"
+#import "FSTMutationQueue.h"
+#import "FSTPersistence.h"
+#import "FSTQuery.h"
+#import "FSTQueryCache.h"
+#import "FSTQueryData.h"
+#import "FSTReferenceSet.h"
+#import "FSTRemoteDocumentCache.h"
+#import "FSTRemoteDocumentChangeBuffer.h"
+#import "FSTRemoteEvent.h"
+#import "FSTSnapshotVersion.h"
+#import "FSTTargetIDGenerator.h"
+#import "FSTTimestamp.h"
+#import "FSTUser.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLocalStore ()
+
+/** Manages our in-memory or durable persistence. */
+@property(nonatomic, strong, readonly) id<FSTPersistence> persistence;
+
+/** The set of all mutations that have been sent but not yet been applied to the backend. */
+@property(nonatomic, strong) id<FSTMutationQueue> mutationQueue;
+
+/** The set of all cached remote documents. */
+@property(nonatomic, strong) id<FSTRemoteDocumentCache> remoteDocumentCache;
+
+/** The "local" view of all documents (layering mutationQueue on top of remoteDocumentCache). */
+@property(nonatomic, strong) FSTLocalDocumentsView *localDocuments;
+
+/** The set of document references maintained by any local views. */
+@property(nonatomic, strong) FSTReferenceSet *localViewReferences;
+
+/**
+ * The garbage collector collects documents that should no longer be cached (e.g. if they are no
+ * longer retained by the above reference sets and the garbage collector is performing eager
+ * collection).
+ */
+@property(nonatomic, strong) id<FSTGarbageCollector> garbageCollector;
+
+/** Maps a query to the data about that query. */
+@property(nonatomic, strong) id<FSTQueryCache> queryCache;
+
+/** Maps a targetID to data about its query. */
+@property(nonatomic, strong) NSMutableDictionary<NSNumber *, FSTQueryData *> *targetIDs;
+
+/** Used to generate targetIDs for queries tracked locally. */
+@property(nonatomic, strong) FSTTargetIDGenerator *targetIDGenerator;
+
+/**
+ * A heldBatchResult is a mutation batch result (from a write acknowledgement) that arrived before
+ * the watch stream got notified of a snapshot that includes the write.  So we "hold" it until
+ * the watch stream catches up. It ensures that the local write remains visible (latency
+ * compensation) and doesn't temporarily appear reverted because the watch stream is slower than
+ * the write stream and so wasn't reflecting it.
+ *
+ * NOTE: Eventually we want to move this functionality into the remote store.
+ */
+@property(nonatomic, strong) NSMutableArray<FSTMutationBatchResult *> *heldBatchResults;
+
+@end
+
+@implementation FSTLocalStore
+
+- (instancetype)initWithPersistence:(id<FSTPersistence>)persistence
+                   garbageCollector:(id<FSTGarbageCollector>)garbageCollector
+                        initialUser:(FSTUser *)initialUser {
+  if (self = [super init]) {
+    _persistence = persistence;
+    _mutationQueue = [persistence mutationQueueForUser:initialUser];
+    _remoteDocumentCache = [persistence remoteDocumentCache];
+    _queryCache = [persistence queryCache];
+    _localDocuments = [FSTLocalDocumentsView viewWithRemoteDocumentCache:_remoteDocumentCache
+                                                           mutationQueue:_mutationQueue];
+    _localViewReferences = [[FSTReferenceSet alloc] init];
+
+    _garbageCollector = garbageCollector;
+    [_garbageCollector addGarbageSource:_queryCache];
+    [_garbageCollector addGarbageSource:_localViewReferences];
+    [_garbageCollector addGarbageSource:_mutationQueue];
+
+    _targetIDs = [NSMutableDictionary dictionary];
+    _heldBatchResults = [NSMutableArray array];
+  }
+  return self;
+}
+
+- (void)start {
+  [self startMutationQueue];
+  [self startQueryCache];
+}
+
+- (void)startMutationQueue {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Start MutationQueue"];
+  [self.mutationQueue startWithGroup:group];
+
+  // If we have any leftover mutation batch results from a prior run, just drop them.
+  // TODO(http://b/33446471): We probably need to repopulate heldBatchResults or similar instead,
+  // but that is not straightforward since we're not persisting the write ack versions.
+  [self.heldBatchResults removeAllObjects];
+
+  // TODO(mikelehen): This is the only usage of getAllMutationBatchesThroughBatchId:. Consider
+  // removing it in favor of a getAcknowledgedBatches method.
+  FSTBatchID highestAck = [self.mutationQueue highestAcknowledgedBatchID];
+  if (highestAck != kFSTBatchIDUnknown) {
+    NSArray<FSTMutationBatch *> *batches =
+        [self.mutationQueue allMutationBatchesThroughBatchID:highestAck];
+    if (batches.count > 0) {
+      // NOTE: This could be more efficient if we had a removeBatchesThroughBatchID, but this set
+      // should be very small and this code should go away eventually.
+      [self.mutationQueue removeMutationBatches:batches group:group];
+    }
+  }
+  [self.persistence commitGroup:group];
+}
+
+- (void)startQueryCache {
+  [self.queryCache start];
+
+  FSTTargetID targetID = [self.queryCache highestTargetID];
+  self.targetIDGenerator = [FSTTargetIDGenerator generatorForLocalStoreStartingAfterID:targetID];
+}
+
+- (void)shutdown {
+  [self.mutationQueue shutdown];
+  [self.remoteDocumentCache shutdown];
+  [self.queryCache shutdown];
+}
+
+- (FSTMaybeDocumentDictionary *)userDidChange:(FSTUser *)user {
+  // Swap out the mutation queue, grabbing the pending mutation batches before and after.
+  NSArray<FSTMutationBatch *> *oldBatches = [self.mutationQueue allMutationBatches];
+
+  [self.mutationQueue shutdown];
+  [self.garbageCollector removeGarbageSource:self.mutationQueue];
+
+  self.mutationQueue = [self.persistence mutationQueueForUser:user];
+  [self.garbageCollector addGarbageSource:self.mutationQueue];
+
+  [self startMutationQueue];
+
+  NSArray<FSTMutationBatch *> *newBatches = [self.mutationQueue allMutationBatches];
+
+  // Recreate our LocalDocumentsView using the new MutationQueue.
+  self.localDocuments = [FSTLocalDocumentsView viewWithRemoteDocumentCache:self.remoteDocumentCache
+                                                             mutationQueue:self.mutationQueue];
+
+  // Union the old/new changed keys.
+  FSTDocumentKeySet *changedKeys = [FSTDocumentKeySet keySet];
+  for (NSArray<FSTMutationBatch *> *batches in @[ oldBatches, newBatches ]) {
+    for (FSTMutationBatch *batch in batches) {
+      for (FSTMutation *mutation in batch.mutations) {
+        changedKeys = [changedKeys setByAddingObject:mutation.key];
+      }
+    }
+  }
+
+  // Return the set of all (potentially) changed documents as the result of the user change.
+  return [self.localDocuments documentsForKeys:changedKeys];
+}
+
+- (FSTLocalWriteResult *)locallyWriteMutations:(NSArray<FSTMutation *> *)mutations {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Locally write mutations"];
+  FSTTimestamp *localWriteTime = [FSTTimestamp timestamp];
+  FSTMutationBatch *batch = [self.mutationQueue addMutationBatchWithWriteTime:localWriteTime
+                                                                    mutations:mutations
+                                                                        group:group];
+  [self.persistence commitGroup:group];
+
+  FSTDocumentKeySet *keys = [batch keys];
+  FSTMaybeDocumentDictionary *changedDocuments = [self.localDocuments documentsForKeys:keys];
+  return [FSTLocalWriteResult resultForBatchID:batch.batchID changes:changedDocuments];
+}
+
+- (FSTMaybeDocumentDictionary *)acknowledgeBatchWithResult:(FSTMutationBatchResult *)batchResult {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Acknowledge batch"];
+  id<FSTMutationQueue> mutationQueue = self.mutationQueue;
+
+  [mutationQueue acknowledgeBatch:batchResult.batch
+                      streamToken:batchResult.streamToken
+                            group:group];
+
+  FSTDocumentKeySet *affected;
+  if ([self shouldHoldBatchResultWithVersion:batchResult.commitVersion]) {
+    [self.heldBatchResults addObject:batchResult];
+    affected = [FSTDocumentKeySet keySet];
+  } else {
+    FSTRemoteDocumentChangeBuffer *remoteDocuments =
+        [FSTRemoteDocumentChangeBuffer changeBufferWithCache:self.remoteDocumentCache];
+
+    affected =
+        [self releaseBatchResults:@[ batchResult ] group:group remoteDocuments:remoteDocuments];
+
+    [remoteDocuments applyToWriteGroup:group];
+  }
+
+  [self.persistence commitGroup:group];
+  [self.mutationQueue performConsistencyCheck];
+
+  return [self.localDocuments documentsForKeys:affected];
+}
+
+- (FSTMaybeDocumentDictionary *)rejectBatchID:(FSTBatchID)batchID {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Reject batch"];
+
+  FSTMutationBatch *toReject = [self.mutationQueue lookupMutationBatch:batchID];
+  FSTAssert(toReject, @"Attempt to reject nonexistent batch!");
+
+  FSTBatchID lastAcked = [self.mutationQueue highestAcknowledgedBatchID];
+  FSTAssert(batchID > lastAcked, @"Acknowledged batches can't be rejected.");
+
+  FSTDocumentKeySet *affected = [self removeMutationBatch:toReject group:group];
+
+  [self.persistence commitGroup:group];
+  [self.mutationQueue performConsistencyCheck];
+
+  return [self.localDocuments documentsForKeys:affected];
+}
+
+- (nullable NSData *)lastStreamToken {
+  return [self.mutationQueue lastStreamToken];
+}
+
+- (void)setLastStreamToken:(nullable NSData *)streamToken {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Set stream token"];
+
+  [self.mutationQueue setLastStreamToken:streamToken group:group];
+  [self.persistence commitGroup:group];
+}
+
+- (FSTSnapshotVersion *)lastRemoteSnapshotVersion {
+  return [self.queryCache lastRemoteSnapshotVersion];
+}
+
+- (FSTMaybeDocumentDictionary *)applyRemoteEvent:(FSTRemoteEvent *)remoteEvent {
+  id<FSTQueryCache> queryCache = self.queryCache;
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Apply remote event"];
+  FSTRemoteDocumentChangeBuffer *remoteDocuments =
+      [FSTRemoteDocumentChangeBuffer changeBufferWithCache:self.remoteDocumentCache];
+
+  [remoteEvent.targetChanges enumerateKeysAndObjectsUsingBlock:^(
+                                 NSNumber *targetIDNumber, FSTTargetChange *change, BOOL *stop) {
+    FSTTargetID targetID = targetIDNumber.intValue;
+
+    // Do not ref/unref unassigned targetIDs - it may lead to leaks.
+    FSTQueryData *queryData = self.targetIDs[targetIDNumber];
+    if (!queryData) {
+      return;
+    }
+
+    FSTTargetMapping *mapping = change.mapping;
+    if (mapping) {
+      // First make sure that all references are deleted.
+      if ([mapping isKindOfClass:[FSTResetMapping class]]) {
+        FSTResetMapping *reset = (FSTResetMapping *)mapping;
+        [queryCache removeMatchingKeysForTargetID:targetID group:group];
+        [queryCache addMatchingKeys:reset.documents forTargetID:targetID group:group];
+
+      } else if ([mapping isKindOfClass:[FSTUpdateMapping class]]) {
+        FSTUpdateMapping *update = (FSTUpdateMapping *)mapping;
+        [queryCache removeMatchingKeys:update.removedDocuments forTargetID:targetID group:group];
+        [queryCache addMatchingKeys:update.addedDocuments forTargetID:targetID group:group];
+
+      } else {
+        FSTFail(@"Unknown mapping type: %@", mapping);
+      }
+    }
+
+    // Update the resume token if the change includes one. Don't clear any preexisting value.
+    NSData *resumeToken = change.resumeToken;
+    if (resumeToken.length > 0) {
+      queryData = [queryData queryDataByReplacingSnapshotVersion:change.snapshotVersion
+                                                     resumeToken:resumeToken];
+      self.targetIDs[targetIDNumber] = queryData;
+      [self.queryCache addQueryData:queryData group:group];
+    }
+  }];
+
+  // TODO(klimt): This could probably be an NSMutableDictionary.
+  __block FSTDocumentKeySet *changedDocKeys = [FSTDocumentKeySet keySet];
+  [remoteEvent.documentUpdates
+      enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key, FSTMaybeDocument *doc, BOOL *stop) {
+        changedDocKeys = [changedDocKeys setByAddingObject:key];
+        FSTMaybeDocument *existingDoc = [remoteDocuments entryForKey:key];
+        // Make sure we don't apply an old document version to the remote cache, though we
+        // make an exception for [SnapshotVersion noVersion] which can happen for manufactured
+        // events (e.g. in the case of a limbo document resolution failing).
+        if (!existingDoc || [doc.version isEqual:[FSTSnapshotVersion noVersion]] ||
+            [doc.version compare:existingDoc.version] != NSOrderedAscending) {
+          [remoteDocuments addEntry:doc];
+        } else {
+          FSTLog(
+              @"FSTLocalStore Ignoring outdated watch update for %@. "
+               "Current version: %@  Watch version: %@",
+              key, existingDoc.version, doc.version);
+        }
+
+        // The document might be garbage because it was unreferenced by everything.
+        // Make sure to mark it as garbage if it is...
+        [self.garbageCollector addPotentialGarbageKey:key];
+      }];
+
+  // HACK: The only reason we allow omitting snapshot version is so we can synthesize remote events
+  // when we get permission denied errors while trying to resolve the state of a locally cached
+  // document that is in limbo.
+  FSTSnapshotVersion *lastRemoteVersion = [self.queryCache lastRemoteSnapshotVersion];
+  FSTSnapshotVersion *remoteVersion = remoteEvent.snapshotVersion;
+  if (![remoteVersion isEqual:[FSTSnapshotVersion noVersion]]) {
+    FSTAssert([remoteVersion compare:lastRemoteVersion] != NSOrderedAscending,
+              @"Watch stream reverted to previous snapshot?? (%@ < %@)", remoteVersion,
+              lastRemoteVersion);
+    [self.queryCache setLastRemoteSnapshotVersion:remoteVersion group:group];
+  }
+
+  FSTDocumentKeySet *releasedWriteKeys =
+      [self releaseHeldBatchResultsWithGroup:group remoteDocuments:remoteDocuments];
+
+  [remoteDocuments applyToWriteGroup:group];
+
+  [self.persistence commitGroup:group];
+
+  // Union the two key sets.
+  __block FSTDocumentKeySet *keysToRecalc = changedDocKeys;
+  [releasedWriteKeys enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+    keysToRecalc = [keysToRecalc setByAddingObject:key];
+  }];
+
+  return [self.localDocuments documentsForKeys:keysToRecalc];
+}
+
+- (void)notifyLocalViewChanges:(NSArray<FSTLocalViewChanges *> *)viewChanges {
+  FSTReferenceSet *localViewReferences = self.localViewReferences;
+  for (FSTLocalViewChanges *view in viewChanges) {
+    FSTQueryData *queryData = [self.queryCache queryDataForQuery:view.query];
+    FSTAssert(queryData, @"Local view changes contain unallocated query.");
+    FSTTargetID targetID = queryData.targetID;
+    [localViewReferences addReferencesToKeys:view.addedKeys forID:targetID];
+    [localViewReferences removeReferencesToKeys:view.removedKeys forID:targetID];
+  }
+}
+
+- (nullable FSTMutationBatch *)nextMutationBatchAfterBatchID:(FSTBatchID)batchID {
+  return [self.mutationQueue nextMutationBatchAfterBatchID:batchID];
+}
+
+- (nullable FSTMaybeDocument *)readDocument:(FSTDocumentKey *)key {
+  return [self.localDocuments documentForKey:key];
+}
+
+- (FSTQueryData *)allocateQuery:(FSTQuery *)query {
+  FSTQueryData *cached = [self.queryCache queryDataForQuery:query];
+  FSTTargetID targetID;
+  if (cached) {
+    // This query has been listened to previously, so reuse the previous targetID.
+    // TODO(mcg): freshen last accessed date?
+    targetID = cached.targetID;
+  } else {
+    FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Allocate query"];
+
+    targetID = [self.targetIDGenerator nextID];
+    cached =
+        [[FSTQueryData alloc] initWithQuery:query targetID:targetID purpose:FSTQueryPurposeListen];
+    [self.queryCache addQueryData:cached group:group];
+
+    [self.persistence commitGroup:group];
+  }
+
+  // Sanity check to ensure that even when resuming a query it's not currently active.
+  FSTBoxedTargetID *boxedTargetID = @(targetID);
+  FSTAssert(!self.targetIDs[boxedTargetID], @"Tried to allocate an already allocated query: %@",
+            query);
+  self.targetIDs[boxedTargetID] = cached;
+  return cached;
+}
+
+- (void)releaseQuery:(FSTQuery *)query {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Release query"];
+
+  FSTQueryData *queryData = [self.queryCache queryDataForQuery:query];
+  FSTAssert(queryData, @"Tried to release nonexistent query: %@", query);
+
+  [self.localViewReferences removeReferencesForID:queryData.targetID];
+  if (self.garbageCollector.isEager) {
+    [self.queryCache removeQueryData:queryData group:group];
+  }
+  [self.targetIDs removeObjectForKey:@(queryData.targetID)];
+
+  // If this was the last watch target, then we won't get any more watch snapshots, so we should
+  // release any held batch results.
+  if ([self.targetIDs count] == 0) {
+    FSTRemoteDocumentChangeBuffer *remoteDocuments =
+        [FSTRemoteDocumentChangeBuffer changeBufferWithCache:self.remoteDocumentCache];
+
+    [self releaseHeldBatchResultsWithGroup:group remoteDocuments:remoteDocuments];
+
+    [remoteDocuments applyToWriteGroup:group];
+  }
+
+  [self.persistence commitGroup:group];
+}
+
+- (FSTDocumentDictionary *)executeQuery:(FSTQuery *)query {
+  return [self.localDocuments documentsMatchingQuery:query];
+}
+
+- (FSTDocumentKeySet *)remoteDocumentKeysForTarget:(FSTTargetID)targetID {
+  return [self.queryCache matchingKeysForTargetID:targetID];
+}
+
+- (void)collectGarbage {
+  // Call collectGarbage regardless of whether isGCEnabled so the referenceSet doesn't continue to
+  // accumulate the garbage keys.
+  NSSet<FSTDocumentKey *> *garbage = [self.garbageCollector collectGarbage];
+  if (garbage.count > 0) {
+    FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Garbage Collection"];
+    for (FSTDocumentKey *key in garbage) {
+      [self.remoteDocumentCache removeEntryForKey:key group:group];
+    }
+    [self.persistence commitGroup:group];
+  }
+}
+
+/**
+ * Releases all the held mutation batches up to the current remote version received, and
+ * applies their mutations to the docs in the remote documents cache.
+ *
+ * @return the set of keys of docs that were modified by those writes.
+ */
+- (FSTDocumentKeySet *)releaseHeldBatchResultsWithGroup:(FSTWriteGroup *)group
+                                        remoteDocuments:
+                                            (FSTRemoteDocumentChangeBuffer *)remoteDocuments {
+  NSMutableArray<FSTMutationBatchResult *> *toRelease = [NSMutableArray array];
+  for (FSTMutationBatchResult *batchResult in self.heldBatchResults) {
+    if (![self isRemoteUpToVersion:batchResult.commitVersion]) {
+      break;
+    }
+    [toRelease addObject:batchResult];
+  }
+
+  if (toRelease.count == 0) {
+    return [FSTDocumentKeySet keySet];
+  } else {
+    [self.heldBatchResults removeObjectsInRange:NSMakeRange(0, toRelease.count)];
+    return [self releaseBatchResults:toRelease group:group remoteDocuments:remoteDocuments];
+  }
+}
+
+- (BOOL)isRemoteUpToVersion:(FSTSnapshotVersion *)version {
+  // If there are no watch targets, then we won't get remote snapshots, and are always "up-to-date."
+  return [version compare:self.queryCache.lastRemoteSnapshotVersion] != NSOrderedDescending ||
+         self.targetIDs.count == 0;
+}
+
+- (BOOL)shouldHoldBatchResultWithVersion:(FSTSnapshotVersion *)version {
+  // Check if watcher isn't up to date or prior results are already held.
+  return ![self isRemoteUpToVersion:version] || self.heldBatchResults.count > 0;
+}
+
+- (FSTDocumentKeySet *)releaseBatchResults:(NSArray<FSTMutationBatchResult *> *)batchResults
+                                     group:(FSTWriteGroup *)group
+                           remoteDocuments:(FSTRemoteDocumentChangeBuffer *)remoteDocuments {
+  NSMutableArray<FSTMutationBatch *> *batches = [NSMutableArray array];
+  for (FSTMutationBatchResult *batchResult in batchResults) {
+    [self applyBatchResult:batchResult toRemoteDocuments:remoteDocuments];
+    [batches addObject:batchResult.batch];
+  }
+
+  return [self removeMutationBatches:batches group:group];
+}
+
+- (FSTDocumentKeySet *)removeMutationBatch:(FSTMutationBatch *)batch group:(FSTWriteGroup *)group {
+  return [self removeMutationBatches:@[ batch ] group:group];
+}
+
+/** Removes all the mutation batches named in the given array. */
+- (FSTDocumentKeySet *)removeMutationBatches:(NSArray<FSTMutationBatch *> *)batches
+                                       group:(FSTWriteGroup *)group {
+  // TODO(klimt): Could this be an NSMutableDictionary?
+  __block FSTDocumentKeySet *affectedDocs = [FSTDocumentKeySet keySet];
+
+  for (FSTMutationBatch *batch in batches) {
+    for (FSTMutation *mutation in batch.mutations) {
+      FSTDocumentKey *key = mutation.key;
+      affectedDocs = [affectedDocs setByAddingObject:key];
+    }
+  }
+
+  [self.mutationQueue removeMutationBatches:batches group:group];
+
+  return affectedDocs;
+}
+
+- (void)applyBatchResult:(FSTMutationBatchResult *)batchResult
+       toRemoteDocuments:(FSTRemoteDocumentChangeBuffer *)remoteDocuments {
+  FSTMutationBatch *batch = batchResult.batch;
+  FSTDocumentKeySet *docKeys = batch.keys;
+  [docKeys enumerateObjectsUsingBlock:^(FSTDocumentKey *docKey, BOOL *stop) {
+    FSTMaybeDocument *_Nullable remoteDoc = [remoteDocuments entryForKey:docKey];
+    FSTMaybeDocument *_Nullable doc = remoteDoc;
+    FSTSnapshotVersion *ackVersion = batchResult.docVersions[docKey];
+    FSTAssert(ackVersion, @"docVersions should contain every doc in the write.");
+    if (!doc || [doc.version compare:ackVersion] == NSOrderedAscending) {
+      doc = [batch applyTo:doc documentKey:docKey mutationBatchResult:batchResult];
+      if (!doc) {
+        FSTAssert(!remoteDoc, @"Mutation batch %@ applied to document %@ resulted in nil.", batch,
+                  remoteDoc);
+      } else {
+        [remoteDocuments addEntry:doc];
+      }
+    }
+  }];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalViewChanges.h b/Firestore/Source/Local/FSTLocalViewChanges.h
new file mode 100644
index 0000000..d44959e
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalViewChanges.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTDocumentKeySet.h"
+
+@class FSTDocumentKey;
+@class FSTDocumentSet;
+@class FSTMutation;
+@class FSTQuery;
+@class FSTRemoteEvent;
+@class FSTViewSnapshot;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * A set of changes to what documents are currently in view and out of view for a given query.
+ * These changes are sent to the LocalStore by the View (via the SyncEngine) and are used to pin /
+ * unpin documents as appropriate.
+ */
+@interface FSTLocalViewChanges : NSObject
+
++ (instancetype)changesForQuery:(FSTQuery *)query
+                      addedKeys:(FSTDocumentKeySet *)addedKeys
+                    removedKeys:(FSTDocumentKeySet *)removedKeys;
+
++ (instancetype)changesForViewSnapshot:(FSTViewSnapshot *)viewSnapshot;
+
+- (id)init NS_UNAVAILABLE;
+
+@property(nonatomic, strong, readonly) FSTQuery *query;
+@property(nonatomic, strong) FSTDocumentKeySet *addedKeys;
+@property(nonatomic, strong) FSTDocumentKeySet *removedKeys;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalViewChanges.m b/Firestore/Source/Local/FSTLocalViewChanges.m
new file mode 100644
index 0000000..05407b2
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalViewChanges.m
@@ -0,0 +1,76 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLocalViewChanges.h"
+
+#import "FSTDocument.h"
+#import "FSTViewSnapshot.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLocalViewChanges ()
+- (instancetype)initWithQuery:(FSTQuery *)query
+                    addedKeys:(FSTDocumentKeySet *)addedKeys
+                  removedKeys:(FSTDocumentKeySet *)removedKeys NS_DESIGNATED_INITIALIZER;
+@end
+
+@implementation FSTLocalViewChanges
+
++ (instancetype)changesForViewSnapshot:(FSTViewSnapshot *)viewSnapshot {
+  FSTDocumentKeySet *addedKeys = [FSTDocumentKeySet keySet];
+  FSTDocumentKeySet *removedKeys = [FSTDocumentKeySet keySet];
+
+  for (FSTDocumentViewChange *docChange in viewSnapshot.documentChanges) {
+    switch (docChange.type) {
+      case FSTDocumentViewChangeTypeAdded:
+        addedKeys = [addedKeys setByAddingObject:docChange.document.key];
+        break;
+
+      case FSTDocumentViewChangeTypeRemoved:
+        removedKeys = [removedKeys setByAddingObject:docChange.document.key];
+        break;
+
+      default:
+        // Do nothing.
+        break;
+    }
+  }
+
+  return [self changesForQuery:viewSnapshot.query addedKeys:addedKeys removedKeys:removedKeys];
+}
+
++ (instancetype)changesForQuery:(FSTQuery *)query
+                      addedKeys:(FSTDocumentKeySet *)addedKeys
+                    removedKeys:(FSTDocumentKeySet *)removedKeys {
+  return
+      [[FSTLocalViewChanges alloc] initWithQuery:query addedKeys:addedKeys removedKeys:removedKeys];
+}
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                    addedKeys:(FSTDocumentKeySet *)addedKeys
+                  removedKeys:(FSTDocumentKeySet *)removedKeys {
+  self = [super init];
+  if (self) {
+    _query = query;
+    _addedKeys = addedKeys;
+    _removedKeys = removedKeys;
+  }
+  return self;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalWriteResult.h b/Firestore/Source/Local/FSTLocalWriteResult.h
new file mode 100644
index 0000000..4cd7d34
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalWriteResult.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTDocumentDictionary.h"
+#import "FSTTypes.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** The result of a write to the local store. */
+@interface FSTLocalWriteResult : NSObject
+
++ (instancetype)resultForBatchID:(FSTBatchID)batchID changes:(FSTMaybeDocumentDictionary *)changes;
+
+- (id)init __attribute__((unavailable("Use resultForBatchID:changes:")));
+
+@property(nonatomic, assign, readonly) FSTBatchID batchID;
+@property(nonatomic, strong, readonly) FSTMaybeDocumentDictionary *changes;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLocalWriteResult.m b/Firestore/Source/Local/FSTLocalWriteResult.m
new file mode 100644
index 0000000..7586686
--- /dev/null
+++ b/Firestore/Source/Local/FSTLocalWriteResult.m
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTLocalWriteResult.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLocalWriteResult ()
+- (instancetype)initWithBatchID:(FSTBatchID)batchID
+                        changes:(FSTMaybeDocumentDictionary *)changes NS_DESIGNATED_INITIALIZER;
+@end
+
+@implementation FSTLocalWriteResult
+
++ (instancetype)resultForBatchID:(FSTBatchID)batchID changes:(FSTMaybeDocumentDictionary *)changes {
+  return [[FSTLocalWriteResult alloc] initWithBatchID:batchID changes:changes];
+}
+
+- (instancetype)initWithBatchID:(FSTBatchID)batchID changes:(FSTMaybeDocumentDictionary *)changes {
+  self = [super init];
+  if (self) {
+    _batchID = batchID;
+    _changes = changes;
+  }
+  return self;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryMutationQueue.h b/Firestore/Source/Local/FSTMemoryMutationQueue.h
new file mode 100644
index 0000000..6d917b7
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryMutationQueue.h
@@ -0,0 +1,34 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTMutationQueue.h"
+
+@protocol FSTGarbageCollector;
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTMemoryMutationQueue : NSObject <FSTMutationQueue>
+
++ (instancetype)mutationQueue;
+
+/** The garbage collector to notify about potential garbage keys. */
+@property(nonatomic, weak, readwrite, nullable) id<FSTGarbageCollector> garbageCollector;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryMutationQueue.m b/Firestore/Source/Local/FSTMemoryMutationQueue.m
new file mode 100644
index 0000000..6118ad6
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryMutationQueue.m
@@ -0,0 +1,441 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTMemoryMutationQueue.h"
+
+#import "FSTAssert.h"
+#import "FSTComparison.h"
+#import "FSTDocumentKey.h"
+#import "FSTDocumentReference.h"
+#import "FSTMutation.h"
+#import "FSTMutationBatch.h"
+#import "FSTPath.h"
+#import "FSTQuery.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTMemoryMutationQueue ()
+
+/**
+ * A FIFO queue of all mutations to apply to the backend. Mutations are added to the end of the
+ * queue as they're written, and removed from the front of the queue as the mutations become
+ * visible or are rejected.
+ *
+ * When successfully applied, mutations must be acknowledged by the write stream and made visible
+ * on the watch stream. It's possible for the watch stream to fall behind in which case the batches
+ * at the head of the queue will be acknowledged but held until the watch stream sees the changes.
+ *
+ * If a batch is rejected while there are held write acknowledgements at the head of the queue
+ * the rejected batch is converted to a tombstone: its mutations are removed but the batch remains
+ * in the queue. This maintains a simple consecutive ordering of batches in the queue.
+ *
+ * Once the held write acknowledgements become visible they are removed from the head of the queue
+ * along with any tombstones that follow.
+ */
+@property(nonatomic, strong, readonly) NSMutableArray<FSTMutationBatch *> *queue;
+
+/** An ordered mapping between documents and the mutation batch IDs. */
+@property(nonatomic, strong) FSTImmutableSortedSet<FSTDocumentReference *> *batchesByDocumentKey;
+
+/** The next value to use when assigning sequential IDs to each mutation batch. */
+@property(nonatomic, assign) FSTBatchID nextBatchID;
+
+/** The highest acknowledged mutation in the queue. */
+@property(nonatomic, assign) FSTBatchID highestAcknowledgedBatchID;
+
+/**
+ * The last received stream token from the server, used to acknowledge which responses the client
+ * has processed. Stream tokens are opaque checkpoint markers whose only real value is their
+ * inclusion in the next request.
+ */
+@property(nonatomic, strong, nullable) NSData *lastStreamToken;
+
+@end
+
+@implementation FSTMemoryMutationQueue
+
++ (instancetype)mutationQueue {
+  return [[FSTMemoryMutationQueue alloc] init];
+}
+
+- (instancetype)init {
+  if (self = [super init]) {
+    _queue = [NSMutableArray array];
+    _batchesByDocumentKey =
+        [FSTImmutableSortedSet setWithComparator:FSTDocumentReferenceComparatorByKey];
+
+    _nextBatchID = 1;
+    _highestAcknowledgedBatchID = kFSTBatchIDUnknown;
+  }
+  return self;
+}
+
+#pragma mark - FSTMutationQueue implementation
+
+- (void)startWithGroup:(FSTWriteGroup *)group {
+  // Note: The queue may be shutdown / started multiple times, since we maintain the queue for the
+  // duration of the app session in case a user logs out / back in. To behave like the
+  // LevelDB-backed MutationQueue (and accommodate tests that expect as much), we reset nextBatchID
+  // and highestAcknowledgedBatchID if the queue is empty.
+  if (self.isEmpty) {
+    self.nextBatchID = 1;
+    self.highestAcknowledgedBatchID = kFSTBatchIDUnknown;
+  }
+  FSTAssert(self.highestAcknowledgedBatchID < self.nextBatchID,
+            @"highestAcknowledgedBatchID must be less than the nextBatchID");
+}
+
+- (void)shutdown {
+}
+
+- (BOOL)isEmpty {
+  // If the queue has any entries at all, the first entry must not be a tombstone (otherwise it
+  // would have been removed already).
+  return self.queue.count == 0;
+}
+
+- (FSTBatchID)highestAcknowledgedBatchID {
+  return _highestAcknowledgedBatchID;
+}
+
+- (void)acknowledgeBatch:(FSTMutationBatch *)batch
+             streamToken:(nullable NSData *)streamToken
+                   group:(__unused FSTWriteGroup *)group {
+  NSMutableArray<FSTMutationBatch *> *queue = self.queue;
+
+  FSTBatchID batchID = batch.batchID;
+  FSTAssert(batchID > self.highestAcknowledgedBatchID,
+            @"Mutation batchIDs must be acknowledged in order");
+
+  NSInteger batchIndex = [self indexOfExistingBatchID:batchID action:@"acknowledged"];
+
+  // Verify that the batch in the queue is the one to be acknowledged.
+  FSTMutationBatch *check = queue[(NSUInteger)batchIndex];
+  FSTAssert(batchID == check.batchID, @"Queue ordering failure: expected batch %d, got batch %d",
+            batchID, check.batchID);
+  FSTAssert(![check isTombstone], @"Can't acknowledge a previously removed batch");
+
+  self.highestAcknowledgedBatchID = batchID;
+  self.lastStreamToken = streamToken;
+}
+
+- (void)setLastStreamToken:(nullable NSData *)streamToken group:(__unused FSTWriteGroup *)group {
+  self.lastStreamToken = streamToken;
+}
+
+- (FSTMutationBatch *)addMutationBatchWithWriteTime:(FSTTimestamp *)localWriteTime
+                                          mutations:(NSArray<FSTMutation *> *)mutations
+                                              group:(FSTWriteGroup *)group {
+  FSTAssert(mutations.count > 0, @"Mutation batches should not be empty");
+
+  FSTBatchID batchID = self.nextBatchID;
+  self.nextBatchID += 1;
+
+  NSMutableArray<FSTMutationBatch *> *queue = self.queue;
+  if (queue.count > 0) {
+    FSTMutationBatch *prior = queue[queue.count - 1];
+    FSTAssert(prior.batchID < batchID, @"Mutation batchIDs must be monotonically increasing order");
+  }
+
+  FSTMutationBatch *batch = [[FSTMutationBatch alloc] initWithBatchID:batchID
+                                                       localWriteTime:localWriteTime
+                                                            mutations:mutations];
+  [queue addObject:batch];
+
+  // Track references by document key.
+  FSTImmutableSortedSet<FSTDocumentReference *> *references = self.batchesByDocumentKey;
+  for (FSTMutation *mutation in batch.mutations) {
+    references = [references
+        setByAddingObject:[[FSTDocumentReference alloc] initWithKey:mutation.key ID:batchID]];
+  }
+  self.batchesByDocumentKey = references;
+
+  return batch;
+}
+
+- (nullable FSTMutationBatch *)lookupMutationBatch:(FSTBatchID)batchID {
+  NSMutableArray<FSTMutationBatch *> *queue = self.queue;
+
+  NSInteger index = [self indexOfBatchID:batchID];
+  if (index < 0 || index >= queue.count) {
+    return nil;
+  }
+
+  FSTMutationBatch *batch = queue[(NSUInteger)index];
+  FSTAssert(batch.batchID == batchID, @"If found batch must match");
+  return [batch isTombstone] ? nil : batch;
+}
+
+- (nullable FSTMutationBatch *)nextMutationBatchAfterBatchID:(FSTBatchID)batchID {
+  NSMutableArray<FSTMutationBatch *> *queue = self.queue;
+  NSUInteger count = queue.count;
+
+  // All batches with batchID <= self.highestAcknowledgedBatchID have been acknowledged so the
+  // first unacknowledged batch after batchID will have a batchID larger than both of these values.
+  batchID = MAX(batchID + 1, self.highestAcknowledgedBatchID);
+
+  // The requested batchID may still be out of range so normalize it to the start of the queue.
+  NSInteger rawIndex = [self indexOfBatchID:batchID];
+  NSUInteger index = rawIndex < 0 ? 0 : (NSUInteger)rawIndex;
+
+  // Finally return the first non-tombstone batch.
+  for (; index < count; index++) {
+    FSTMutationBatch *batch = queue[index];
+    if (![batch isTombstone]) {
+      return batch;
+    }
+  }
+
+  return nil;
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatches {
+  return [self allLiveMutationBatchesBeforeIndex:self.queue.count];
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesThroughBatchID:(FSTBatchID)batchID {
+  NSMutableArray<FSTMutationBatch *> *queue = self.queue;
+  NSUInteger count = queue.count;
+
+  NSInteger endIndex = [self indexOfBatchID:batchID];
+  if (endIndex < 0) {
+    endIndex = 0;
+  } else if (endIndex >= count) {
+    endIndex = count;
+  } else {
+    // The endIndex is in the queue so increment to pull everything in the queue including it.
+    endIndex += 1;
+  }
+
+  return [self allLiveMutationBatchesBeforeIndex:(NSUInteger)endIndex];
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesAffectingDocumentKey:
+    (FSTDocumentKey *)documentKey {
+  FSTDocumentReference *start = [[FSTDocumentReference alloc] initWithKey:documentKey ID:0];
+
+  NSMutableArray<FSTMutationBatch *> *result = [NSMutableArray array];
+  FSTDocumentReferenceBlock block = ^(FSTDocumentReference *reference, BOOL *stop) {
+    if (![documentKey isEqualToKey:reference.key]) {
+      *stop = YES;
+      return;
+    }
+
+    FSTMutationBatch *batch = [self lookupMutationBatch:reference.ID];
+    FSTAssert(batch, @"Batches in the index must exist in the main table");
+    [result addObject:batch];
+  };
+
+  [self.batchesByDocumentKey enumerateObjectsFrom:start to:nil usingBlock:block];
+  return result;
+}
+
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesAffectingQuery:(FSTQuery *)query {
+  // Use the query path as a prefix for testing if a document matches the query.
+  FSTResourcePath *prefix = query.path;
+  int immediateChildrenPathLength = prefix.length + 1;
+
+  // Construct a document reference for actually scanning the index. Unlike the prefix, the document
+  // key in this reference must have an even number of segments. The empty segment can be used as
+  // a suffix of the query path because it precedes all other segments in an ordered traversal.
+  FSTResourcePath *startPath = query.path;
+  if (![FSTDocumentKey isDocumentKey:startPath]) {
+    startPath = [startPath pathByAppendingSegment:@""];
+  }
+  FSTDocumentReference *start =
+      [[FSTDocumentReference alloc] initWithKey:[FSTDocumentKey keyWithPath:startPath] ID:0];
+
+  // Find unique batchIDs referenced by all documents potentially matching the query.
+  __block FSTImmutableSortedSet<NSNumber *> *uniqueBatchIDs =
+      [FSTImmutableSortedSet setWithComparator:FSTNumberComparator];
+  FSTDocumentReferenceBlock block = ^(FSTDocumentReference *reference, BOOL *stop) {
+    FSTResourcePath *rowKeyPath = reference.key.path;
+    if (![prefix isPrefixOfPath:rowKeyPath]) {
+      *stop = YES;
+      return;
+    }
+
+    // Rows with document keys more than one segment longer than the query path can't be matches.
+    // For example, a query on 'rooms' can't match the document /rooms/abc/messages/xyx.
+    // TODO(mcg): we'll need a different scanner when we implement ancestor queries.
+    if (rowKeyPath.length != immediateChildrenPathLength) {
+      return;
+    }
+
+    uniqueBatchIDs = [uniqueBatchIDs setByAddingObject:@(reference.ID)];
+  };
+  [self.batchesByDocumentKey enumerateObjectsFrom:start to:nil usingBlock:block];
+
+  // Construct an array of matching batches, sorted by batchID to ensure that multiple mutations
+  // affecting the same document key are applied in order.
+  NSMutableArray<FSTMutationBatch *> *result = [NSMutableArray array];
+  [uniqueBatchIDs enumerateObjectsUsingBlock:^(NSNumber *batchID, BOOL *stop) {
+    FSTMutationBatch *batch = [self lookupMutationBatch:[batchID intValue]];
+    if (batch) {
+      [result addObject:batch];
+    }
+  }];
+
+  return result;
+}
+
+- (void)removeMutationBatches:(NSArray<FSTMutationBatch *> *)batches group:(FSTWriteGroup *)group {
+  NSUInteger batchCount = batches.count;
+  FSTAssert(batchCount > 0, @"Should not remove mutations when none exist.");
+
+  FSTBatchID firstBatchID = batches[0].batchID;
+
+  NSMutableArray<FSTMutationBatch *> *queue = self.queue;
+  NSUInteger queueCount = queue.count;
+
+  // Find the position of the first batch for removal. This need not be the first entry in the
+  // queue.
+  NSUInteger startIndex = [self indexOfExistingBatchID:firstBatchID action:@"removed"];
+  FSTAssert(queue[startIndex].batchID == firstBatchID, @"Removed batches must exist in the queue");
+
+  // Check that removed batches are contiguous (while excluding tombstones).
+  NSUInteger batchIndex = 1;
+  NSUInteger queueIndex = startIndex + 1;
+  while (batchIndex < batchCount && queueIndex < queueCount) {
+    FSTMutationBatch *batch = queue[queueIndex];
+    if ([batch isTombstone]) {
+      queueIndex++;
+      continue;
+    }
+
+    FSTAssert(batch.batchID == batches[batchIndex].batchID,
+              @"Removed batches must be contiguous in the queue");
+    batchIndex++;
+    queueIndex++;
+  }
+
+  // Only actually remove batches if removing at the front of the queue. Previously rejected batches
+  // may have left tombstones in the queue, so expand the removal range to include any tombstones.
+  if (startIndex == 0) {
+    for (; queueIndex < queueCount; queueIndex++) {
+      FSTMutationBatch *batch = queue[queueIndex];
+      if (![batch isTombstone]) {
+        break;
+      }
+    }
+
+    NSUInteger length = queueIndex - startIndex;
+    [queue removeObjectsInRange:NSMakeRange(startIndex, length)];
+
+  } else {
+    // Mark tombstones
+    for (NSUInteger i = startIndex; i < queueIndex; i++) {
+      queue[i] = [queue[i] toTombstone];
+    }
+  }
+
+  // Remove entries from the index too.
+  id<FSTGarbageCollector> garbageCollector = self.garbageCollector;
+  FSTImmutableSortedSet<FSTDocumentReference *> *references = self.batchesByDocumentKey;
+  for (FSTMutationBatch *batch in batches) {
+    FSTBatchID batchID = batch.batchID;
+    for (FSTMutation *mutation in batch.mutations) {
+      FSTDocumentKey *key = mutation.key;
+      [garbageCollector addPotentialGarbageKey:key];
+
+      FSTDocumentReference *reference = [[FSTDocumentReference alloc] initWithKey:key ID:batchID];
+      references = [references setByRemovingObject:reference];
+    }
+  }
+  self.batchesByDocumentKey = references;
+}
+
+- (void)performConsistencyCheck {
+  if (self.queue.count == 0) {
+    FSTAssert([self.batchesByDocumentKey isEmpty],
+              @"Document leak -- detected dangling mutation references when queue is empty.");
+  }
+}
+
+#pragma mark - FSTGarbageSource implementation
+
+- (BOOL)containsKey:(FSTDocumentKey *)key {
+  // Create a reference with a zero ID as the start position to find any document reference with
+  // this key.
+  FSTDocumentReference *reference = [[FSTDocumentReference alloc] initWithKey:key ID:0];
+
+  NSEnumerator<FSTDocumentReference *> *enumerator =
+      [self.batchesByDocumentKey objectEnumeratorFrom:reference];
+  FSTDocumentKey *_Nullable firstKey = [enumerator nextObject].key;
+  return [firstKey isEqual:key];
+}
+
+#pragma mark - Helpers
+
+/**
+ * A private helper that collects all the mutation batches in the queue up to but not including
+ * the given endIndex. All tombstones in the queue are excluded.
+ */
+- (NSArray<FSTMutationBatch *> *)allLiveMutationBatchesBeforeIndex:(NSUInteger)endIndex {
+  NSMutableArray<FSTMutationBatch *> *result = [NSMutableArray arrayWithCapacity:endIndex];
+
+  NSUInteger index = 0;
+  for (FSTMutationBatch *batch in self.queue) {
+    if (index++ >= endIndex) break;
+
+    if (![batch isTombstone]) {
+      [result addObject:batch];
+    }
+  }
+
+  return result;
+}
+
+/**
+ * Finds the index of the given batchID in the mutation queue. This operation is O(1).
+ *
+ * @return The computed index of the batch with the given batchID, based on the state of the
+ *     queue. Note this index can negative if the requested batchID has already been removed from
+ *     the queue or past the end of the queue if the batchID is larger than the last added batch.
+ */
+- (NSInteger)indexOfBatchID:(FSTBatchID)batchID {
+  NSMutableArray<FSTMutationBatch *> *queue = self.queue;
+  NSUInteger count = queue.count;
+  if (count == 0) {
+    // As an index this is past the end of the queue
+    return 0;
+  }
+
+  // Examine the front of the queue to figure out the difference between the batchID and indexes
+  // in the array. Note that since the queue is ordered by batchID, if the first batch has a larger
+  // batchID then the requested batchID doesn't exist in the queue.
+  FSTMutationBatch *firstBatch = queue[0];
+  FSTBatchID firstBatchID = firstBatch.batchID;
+  return batchID - firstBatchID;
+}
+
+/**
+ * Finds the index of the given batchID in the mutation queue and asserts that the resulting
+ * index is within the bounds of the queue.
+ *
+ * @param batchID The batchID to search for
+ * @param action A description of what the caller is doing, phrased in passive form (e.g.
+ *     "acknowledged" in a routine that acknowledges batches).
+ */
+- (NSUInteger)indexOfExistingBatchID:(FSTBatchID)batchID action:(NSString *)action {
+  NSInteger index = [self indexOfBatchID:batchID];
+  FSTAssert(index >= 0 && index < self.queue.count, @"Batches must exist to be %@", action);
+  return (NSUInteger)index;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryPersistence.h b/Firestore/Source/Local/FSTMemoryPersistence.h
new file mode 100644
index 0000000..c52962a
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryPersistence.h
@@ -0,0 +1,33 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTPersistence.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * An in-memory implementation of the FSTPersistence protocol. Values are stored only in RAM and
+ * are never persisted to any durable storage.
+ */
+@interface FSTMemoryPersistence : NSObject <FSTPersistence>
+
++ (instancetype)persistence;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryPersistence.m b/Firestore/Source/Local/FSTMemoryPersistence.m
new file mode 100644
index 0000000..9caf3e7
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryPersistence.m
@@ -0,0 +1,107 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTMemoryPersistence.h"
+
+#import "FSTAssert.h"
+#import "FSTMemoryMutationQueue.h"
+#import "FSTMemoryQueryCache.h"
+#import "FSTMemoryRemoteDocumentCache.h"
+#import "FSTUser.h"
+#import "FSTWriteGroup.h"
+#import "FSTWriteGroupTracker.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTMemoryPersistence ()
+@property(nonatomic, strong, nonnull) FSTWriteGroupTracker *writeGroupTracker;
+@property(nonatomic, strong, nonnull)
+    NSMutableDictionary<FSTUser *, id<FSTMutationQueue>> *mutationQueues;
+@property(nonatomic, assign, getter=isStarted) BOOL started;
+@end
+
+@implementation FSTMemoryPersistence {
+  /**
+   * The FSTQueryCache representing the persisted cache of queries.
+   *
+   * Note that this is retained here to make it easier to write tests affecting both the in-memory
+   * and LevelDB-backed persistence layers. Tests can create a new FSTLocalStore wrapping this
+   * FSTPersistence instance and this will make the in-memory persistence layer behave as if it
+   * were actually persisting values.
+   */
+  FSTMemoryQueryCache *_queryCache;
+
+  /** The FSTRemoteDocumentCache representing the persisted cache of remote documents. */
+  FSTMemoryRemoteDocumentCache *_remoteDocumentCache;
+}
+
++ (instancetype)persistence {
+  return [[FSTMemoryPersistence alloc] init];
+}
+
+- (instancetype)init {
+  if (self = [super init]) {
+    _writeGroupTracker = [FSTWriteGroupTracker tracker];
+    _queryCache = [[FSTMemoryQueryCache alloc] init];
+    _remoteDocumentCache = [[FSTMemoryRemoteDocumentCache alloc] init];
+    _mutationQueues = [NSMutableDictionary dictionary];
+  }
+  return self;
+}
+
+- (BOOL)start:(NSError **)error {
+  // No durable state to read on startup.
+  FSTAssert(!self.isStarted, @"FSTMemoryPersistence double-started!");
+  self.started = YES;
+  return YES;
+}
+
+- (void)shutdown {
+  // No durable state to ensure is closed on shutdown.
+  FSTAssert(self.isStarted, @"FSTMemoryPersistence shutdown without start!");
+  self.started = NO;
+}
+
+- (id<FSTMutationQueue>)mutationQueueForUser:(FSTUser *)user {
+  id<FSTMutationQueue> queue = self.mutationQueues[user];
+  if (!queue) {
+    queue = [FSTMemoryMutationQueue mutationQueue];
+    self.mutationQueues[user] = queue;
+  }
+  return queue;
+}
+
+- (id<FSTQueryCache>)queryCache {
+  return _queryCache;
+}
+
+- (id<FSTRemoteDocumentCache>)remoteDocumentCache {
+  return _remoteDocumentCache;
+}
+
+- (FSTWriteGroup *)startGroupWithAction:(NSString *)action {
+  return [self.writeGroupTracker startGroupWithAction:action];
+}
+
+- (void)commitGroup:(FSTWriteGroup *)group {
+  [self.writeGroupTracker endGroup:group];
+
+  FSTAssert(group.isEmpty, @"Memory persistence shouldn't use write groups: %@", group.action);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryQueryCache.h b/Firestore/Source/Local/FSTMemoryQueryCache.h
new file mode 100644
index 0000000..58e0133
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryQueryCache.h
@@ -0,0 +1,30 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTQueryCache.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * An implementation of the FSTQueryCache protocol that merely keeps queries in memory, suitable
+ * for online only clients with persistence disabled.
+ */
+@interface FSTMemoryQueryCache : NSObject <FSTQueryCache>
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryQueryCache.m b/Firestore/Source/Local/FSTMemoryQueryCache.m
new file mode 100644
index 0000000..1466caa
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryQueryCache.m
@@ -0,0 +1,131 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTMemoryQueryCache.h"
+
+#import "FSTQuery.h"
+#import "FSTQueryData.h"
+#import "FSTReferenceSet.h"
+#import "FSTSnapshotVersion.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTMemoryQueryCache ()
+
+/** Maps a query to the data about that query. */
+@property(nonatomic, strong, readonly) NSMutableDictionary<FSTQuery *, FSTQueryData *> *queries;
+
+/** A ordered bidirectional mapping between documents and the remote target IDs. */
+@property(nonatomic, strong, readonly) FSTReferenceSet *references;
+
+/** The highest numbered target ID encountered. */
+@property(nonatomic, assign) FSTTargetID highestTargetID;
+
+@end
+
+@implementation FSTMemoryQueryCache {
+  /** The last received snapshot version. */
+  FSTSnapshotVersion *_lastRemoteSnapshotVersion;
+}
+
+- (instancetype)init {
+  if (self = [super init]) {
+    _queries = [NSMutableDictionary dictionary];
+    _references = [[FSTReferenceSet alloc] init];
+    _lastRemoteSnapshotVersion = [FSTSnapshotVersion noVersion];
+  }
+  return self;
+}
+
+#pragma mark - FSTQueryCache implementation
+#pragma mark Query tracking
+
+- (void)start {
+  // Nothing to do.
+}
+
+- (void)shutdown {
+  // No resources to release.
+}
+
+- (FSTTargetID)highestTargetID {
+  return _highestTargetID;
+}
+
+- (FSTSnapshotVersion *)lastRemoteSnapshotVersion {
+  return _lastRemoteSnapshotVersion;
+}
+
+- (void)setLastRemoteSnapshotVersion:(FSTSnapshotVersion *)snapshotVersion
+                               group:(FSTWriteGroup *)group {
+  _lastRemoteSnapshotVersion = snapshotVersion;
+}
+
+- (void)addQueryData:(FSTQueryData *)queryData group:(__unused FSTWriteGroup *)group {
+  self.queries[queryData.query] = queryData;
+  if (queryData.targetID > self.highestTargetID) {
+    self.highestTargetID = queryData.targetID;
+  }
+}
+
+- (void)removeQueryData:(FSTQueryData *)queryData group:(__unused FSTWriteGroup *)group {
+  [self.queries removeObjectForKey:queryData.query];
+  [self.references removeReferencesForID:queryData.targetID];
+}
+
+- (nullable FSTQueryData *)queryDataForQuery:(FSTQuery *)query {
+  return self.queries[query];
+}
+
+#pragma mark Reference tracking
+
+- (void)addMatchingKeys:(FSTDocumentKeySet *)keys
+            forTargetID:(FSTTargetID)targetID
+                  group:(__unused FSTWriteGroup *)group {
+  [self.references addReferencesToKeys:keys forID:targetID];
+}
+
+- (void)removeMatchingKeys:(FSTDocumentKeySet *)keys
+               forTargetID:(FSTTargetID)targetID
+                     group:(__unused FSTWriteGroup *)group {
+  [self.references removeReferencesToKeys:keys forID:targetID];
+}
+
+- (void)removeMatchingKeysForTargetID:(FSTTargetID)targetID group:(__unused FSTWriteGroup *)group {
+  [self.references removeReferencesForID:targetID];
+}
+
+- (FSTDocumentKeySet *)matchingKeysForTargetID:(FSTTargetID)targetID {
+  return [self.references referencedKeysForID:targetID];
+}
+
+#pragma mark - FSTGarbageSource implementation
+
+- (nullable id<FSTGarbageCollector>)garbageCollector {
+  return self.references.garbageCollector;
+}
+
+- (void)setGarbageCollector:(nullable id<FSTGarbageCollector>)garbageCollector {
+  self.references.garbageCollector = garbageCollector;
+}
+
+- (BOOL)containsKey:(FSTDocumentKey *)key {
+  return [self.references containsKey:key];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryRemoteDocumentCache.h b/Firestore/Source/Local/FSTMemoryRemoteDocumentCache.h
new file mode 100644
index 0000000..aca0ca1
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryRemoteDocumentCache.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTRemoteDocumentCache.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTMemoryRemoteDocumentCache : NSObject <FSTRemoteDocumentCache>
+
+- (instancetype)init NS_DESIGNATED_INITIALIZER;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMemoryRemoteDocumentCache.m b/Firestore/Source/Local/FSTMemoryRemoteDocumentCache.m
new file mode 100644
index 0000000..175be43
--- /dev/null
+++ b/Firestore/Source/Local/FSTMemoryRemoteDocumentCache.m
@@ -0,0 +1,84 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTMemoryRemoteDocumentCache.h"
+
+#import "FSTDocument.h"
+#import "FSTDocumentDictionary.h"
+#import "FSTDocumentKey.h"
+#import "FSTPath.h"
+#import "FSTQuery.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTMemoryRemoteDocumentCache ()
+
+/** Underlying cache of documents. */
+@property(nonatomic, strong) FSTMaybeDocumentDictionary *docs;
+
+@end
+
+@implementation FSTMemoryRemoteDocumentCache
+
+- (instancetype)init {
+  if (self = [super init]) {
+    _docs = [FSTMaybeDocumentDictionary maybeDocumentDictionary];
+  }
+  return self;
+}
+
+- (void)shutdown {
+}
+
+- (void)addEntry:(FSTMaybeDocument *)document group:(FSTWriteGroup *)group {
+  self.docs = [self.docs dictionaryBySettingObject:document forKey:document.key];
+}
+
+- (void)removeEntryForKey:(FSTDocumentKey *)key group:(FSTWriteGroup *)group {
+  self.docs = [self.docs dictionaryByRemovingObjectForKey:key];
+}
+
+- (nullable FSTMaybeDocument *)entryForKey:(FSTDocumentKey *)key {
+  return self.docs[key];
+}
+
+- (FSTDocumentDictionary *)documentsMatchingQuery:(FSTQuery *)query {
+  FSTDocumentDictionary *result = [FSTDocumentDictionary documentDictionary];
+
+  // Documents are ordered by key, so we can use a prefix scan to narrow down the documents
+  // we need to match the query against.
+  FSTDocumentKey *prefix = [FSTDocumentKey keyWithPath:[query.path pathByAppendingSegment:@""]];
+  NSEnumerator<FSTDocumentKey *> *enumerator = [self.docs keyEnumeratorFrom:prefix];
+  for (FSTDocumentKey *key in enumerator) {
+    if (![query.path isPrefixOfPath:key.path]) {
+      break;
+    }
+    FSTMaybeDocument *maybeDoc = self.docs[key];
+    if (![maybeDoc isKindOfClass:[FSTDocument class]]) {
+      continue;
+    }
+    FSTDocument *doc = (FSTDocument *)maybeDoc;
+    if ([query matchesDocument:doc]) {
+      result = [result dictionaryBySettingObject:doc forKey:doc.key];
+    }
+  }
+
+  return result;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTMutationQueue.h b/Firestore/Source/Local/FSTMutationQueue.h
new file mode 100644
index 0000000..c822b96
--- /dev/null
+++ b/Firestore/Source/Local/FSTMutationQueue.h
@@ -0,0 +1,159 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTGarbageCollector.h"
+#import "FSTTypes.h"
+
+@class FSTDocumentKey;
+@class FSTMutation;
+@class FSTMutationBatch;
+@class FSTQuery;
+@class FSTTimestamp;
+@class FSTWriteGroup;
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTMutationQueue
+
+/** A queue of mutations to apply to the remote store. */
+@protocol FSTMutationQueue <NSObject, FSTGarbageSource>
+
+/**
+ * Starts the mutation queue, performing any initial reads that might be required to establish
+ * invariants, etc.
+ *
+ * After starting, the mutation queue must guarantee that the highestAcknowledgedBatchID is less
+ * than nextBatchID. This prevents the local store from creating new batches that the mutation
+ * queue would consider erroneously acknowledged.
+ */
+- (void)startWithGroup:(FSTWriteGroup *)group;
+
+/** Shuts this mutation queue down, closing open files, etc. */
+- (void)shutdown;
+
+/** Returns YES if this queue contains no mutation batches. */
+- (BOOL)isEmpty;
+
+/**
+ * Returns the next FSTBatchID that will be assigned to a new mutation batch.
+ *
+ * Callers generally don't care about this value except to test that the mutation queue is
+ * properly maintaining the invariant that highestAcknowledgedBatchID is less than nextBatchID.
+ */
+- (FSTBatchID)nextBatchID;
+
+/**
+ * Returns the highest batchID that has been acknowledged. If no batches have been acknowledged
+ * or if there are no batches in the queue this can return kFSTBatchIDUnknown.
+ */
+- (FSTBatchID)highestAcknowledgedBatchID;
+
+/** Acknowledges the given batch. */
+- (void)acknowledgeBatch:(FSTMutationBatch *)batch
+             streamToken:(nullable NSData *)streamToken
+                   group:(FSTWriteGroup *)group;
+
+/** Returns the current stream token for this mutation queue. */
+- (nullable NSData *)lastStreamToken;
+
+/** Sets the stream token for this mutation queue. */
+- (void)setLastStreamToken:(nullable NSData *)streamToken group:(FSTWriteGroup *)group;
+
+/** Creates a new mutation batch and adds it to this mutation queue. */
+- (FSTMutationBatch *)addMutationBatchWithWriteTime:(FSTTimestamp *)localWriteTime
+                                          mutations:(NSArray<FSTMutation *> *)mutations
+                                              group:(FSTWriteGroup *)group;
+
+/** Loads the mutation batch with the given batchID. */
+- (nullable FSTMutationBatch *)lookupMutationBatch:(FSTBatchID)batchID;
+
+/**
+ * Gets the first unacknowledged mutation batch after the passed in batchId in the mutation queue
+ * or nil if empty.
+ *
+ * @param batchID The batch to search after, or kFSTBatchIDUnknown for the first mutation in the
+ * queue.
+ *
+ * @return the next mutation or nil if there wasn't one.
+ */
+- (nullable FSTMutationBatch *)nextMutationBatchAfterBatchID:(FSTBatchID)batchID;
+
+/** Gets all mutation batches in the mutation queue. */
+// TODO(mikelehen): PERF: Current consumer only needs mutated keys; if we can provide that
+// cheaply, we should replace this.
+- (NSArray<FSTMutationBatch *> *)allMutationBatches;
+
+/**
+ * Finds all mutations with a batchID less than or equal to the given batchID.
+ *
+ * Generally the caller should be asking for the next unacknowledged batchID and the number of
+ * acknowledged batches should be very small when things are functioning well.
+ *
+ * @param batchID The batch to search through.
+ *
+ * @return an NSArray containing all batches with matching batchIDs.
+ */
+// TODO(mcg): This should really return NSEnumerator and the caller should be adjusted to only
+// loop through these once.
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesThroughBatchID:(FSTBatchID)batchID;
+
+/**
+ * Finds all mutation batches that could @em possibly affect the given document key. Not all
+ * mutations in a batch will necessarily affect the document key, so when looping through the
+ * batch you'll need to check that the mutation itself matches the key.
+ *
+ * Note that because of this requirement implementations are free to return mutation batches that
+ * don't contain the document key at all if it's convenient.
+ */
+// TODO(mcg): This should really return an NSEnumerator
+// also for b/32992024, all backing stores should really index by document key
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesAffectingDocumentKey:
+    (FSTDocumentKey *)documentKey;
+
+/**
+ * Finds all mutation batches that could affect the results for the given query. Not all
+ * mutations in a batch will necessarily affect the query, so when looping through the batch
+ * you'll need to check that the mutation itself matches the query.
+ *
+ * Note that because of this requirement implementations are free to return mutation batches that
+ * don't match the query at all if it's convenient.
+ *
+ * NOTE: A FSTPatchMutation does not need to include all fields in the query filter criteria in
+ * order to be a match (but any fields it does contain do need to match).
+ */
+// TODO(mikelehen): This should perhaps return an NSEnumerator, though I'm not sure we can avoid
+// loading them all in memory.
+- (NSArray<FSTMutationBatch *> *)allMutationBatchesAffectingQuery:(FSTQuery *)query;
+
+/**
+ * Removes the given mutation batches from the queue. This is useful in two circumstances:
+ *
+ * + Removing applied mutations from the head of the queue
+ * + Removing rejected mutations from anywhere in the queue
+ *
+ * In both cases, the array of mutations to remove must be a contiguous range of batchIds. This is
+ * most easily accomplished by loading mutations with @a -allMutationBatchesThroughBatchID:.
+ */
+- (void)removeMutationBatches:(NSArray<FSTMutationBatch *> *)batches group:(FSTWriteGroup *)group;
+
+/** Performs a consistency check, examining the mutation queue for any leaks, if possible. */
+- (void)performConsistencyCheck;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTNoOpGarbageCollector.h b/Firestore/Source/Local/FSTNoOpGarbageCollector.h
new file mode 100644
index 0000000..8873a1b
--- /dev/null
+++ b/Firestore/Source/Local/FSTNoOpGarbageCollector.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTGarbageCollector.h"
+
+@class FSTDocumentKey;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * A garbage collector implementation that does absolutely nothing. It ignores all
+ * addGarbageSource: and addPotentialGarbageKey: messages and never produces any garbage.
+ */
+@interface FSTNoOpGarbageCollector : NSObject <FSTGarbageCollector>
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTNoOpGarbageCollector.m b/Firestore/Source/Local/FSTNoOpGarbageCollector.m
new file mode 100644
index 0000000..6e035ab
--- /dev/null
+++ b/Firestore/Source/Local/FSTNoOpGarbageCollector.m
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTNoOpGarbageCollector.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTNoOpGarbageCollector
+
+- (BOOL)isEager {
+  return NO;
+}
+
+- (void)addGarbageSource:(id<FSTGarbageSource>)garbageSource {
+  // Not tracking garbage so don't track sources.
+}
+
+- (void)removeGarbageSource:(id<FSTGarbageSource>)garbageSource {
+  // Not tracking garbage so don't track sources.
+}
+
+- (void)addPotentialGarbageKey:(FSTDocumentKey *)key {
+  // Not tracking garbage so ignore.
+}
+
+- (NSSet<FSTDocumentKey *> *)collectGarbage {
+  return [NSSet set];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTPersistence.h b/Firestore/Source/Local/FSTPersistence.h
new file mode 100644
index 0000000..cf07a9e
--- /dev/null
+++ b/Firestore/Source/Local/FSTPersistence.h
@@ -0,0 +1,103 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+@class FSTUser;
+@class FSTWriteGroup;
+@protocol FSTMutationQueue;
+@protocol FSTQueryCache;
+@protocol FSTRemoteDocumentCache;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * FSTPersistence is the lowest-level shared interface to persistent storage in Firestore.
+ *
+ * FSTPersistence is used to create FSTMutationQueue and FSTRemoteDocumentCache instances backed
+ * by persistence (which might be in-memory or LevelDB).
+ *
+ * FSTPersistence also exposes an API to create and commit FSTWriteGroup instances.
+ * Implementations of FSTWriteGroup/FSTPersistence only need to guarantee that writes made
+ * against the FSTWriteGroup are not made to durable storage until commitGroup:action: is called
+ * here. Since memory-only storage components do not alter durable storage, they are free to ignore
+ * the group.
+ *
+ * This contract is enough to allow the FSTLocalStore be be written independently of whether or not
+ * the stored state actually is durably persisted. If persistent storage is enabled, writes are
+ * grouped together to avoid inconsistent state that could cause crashes.
+ *
+ * Concretely, when persistent storage is enabled, the persistent versions of FSTMutationQueue,
+ * FSTRemoteDocumentCache, and others (the mutators) will defer their writes into an FSTWriteGroup.
+ * Once the local store has completed one logical operation, it commits the write group using
+ * [FSTPersistence commitGroup:action:].
+ *
+ * When persistent storage is disabled, the non-persistent versions of the mutators ignore the
+ * FSTWriteGroup and [FSTPersistence commitGroup:action:] is a no-op. This short-cut is allowed
+ * because memory-only storage leaves no state so it cannot be inconsistent.
+ *
+ * This simplifies the implementations of the mutators and allows memory-only implementations to
+ * supplement the persistent ones without requiring any special dual-store implementation of
+ * FSTPersistence. The cost is that the FSTLocalStore needs to be slightly careful about the order
+ * of its reads and writes in order to avoid relying on being able to read back uncommitted writes.
+ */
+@protocol FSTPersistence <NSObject>
+
+/**
+ * Starts persistent storage, opening the database or similar.
+ *
+ * @param error An error object that will be populated if startup fails.
+ * @return YES if persistent storage started successfully, NO otherwise.
+ */
+- (BOOL)start:(NSError **)error;
+
+/** Releases any resources held during eager shutdown. */
+- (void)shutdown;
+
+/**
+ * Returns an FSTMutationQueue representing the persisted mutations for the given user.
+ *
+ * <p>Note: The implementation is free to return the same instance every time this is called for a
+ * given user. In particular, the memory-backed implementation does this to emulate the persisted
+ * implementation to the extent possible (e.g. in the case of uid switching from
+ * sally=>jack=>sally, sally's mutation queue will be preserved).
+ */
+- (id<FSTMutationQueue>)mutationQueueForUser:(FSTUser *)user;
+
+/** Creates an FSTQueryCache representing the persisted cache of queries. */
+- (id<FSTQueryCache>)queryCache;
+
+/** Creates an FSTRemoteDocumentCache representing the persisted cache of remote documents. */
+- (id<FSTRemoteDocumentCache>)remoteDocumentCache;
+
+/**
+ * Creates an FSTWriteGroup with the specified action description.
+ *
+ * @param action A description of the action performed by this group, used for logging.
+ * @return The created group.
+ */
+- (FSTWriteGroup *)startGroupWithAction:(NSString *)action;
+
+/**
+ * Commits all accumulated changes in the given group. If there are no changes this is a no-op.
+ *
+ * @param group The group of changes to write as a unit.
+ */
+- (void)commitGroup:(FSTWriteGroup *)group;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTQueryCache.h b/Firestore/Source/Local/FSTQueryCache.h
new file mode 100644
index 0000000..87ee342
--- /dev/null
+++ b/Firestore/Source/Local/FSTQueryCache.h
@@ -0,0 +1,113 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTDocumentKeySet.h"
+#import "FSTGarbageCollector.h"
+#import "FSTTypes.h"
+
+@class FSTDocumentKey;
+@class FSTDocumentSet;
+@class FSTMaybeDocument;
+@class FSTQuery;
+@class FSTQueryData;
+@class FSTWriteGroup;
+@class FSTSnapshotVersion;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * Represents cached queries received from the remote backend. This contains both a mapping between
+ * queries and the documents that matched them according to the server, but also metadata about the
+ * queries.
+ *
+ * The cache is keyed by FSTQuery and entries in the cache are FSTQueryData instances.
+ */
+@protocol FSTQueryCache <NSObject, FSTGarbageSource>
+
+/** Starts the query cache up. */
+- (void)start;
+
+/** Shuts this cache down, closing open files, etc. */
+- (void)shutdown;
+
+/**
+ * Returns the highest target ID of any query in the cache. Typically called during startup to
+ * seed a target ID generator and avoid collisions with existing queries. If there are no queries
+ * in the cache, returns zero.
+ */
+- (FSTTargetID)highestTargetID;
+
+/**
+ * A global snapshot version representing the last consistent snapshot we received from the
+ * backend. This is monotonically increasing and any snapshots received from the backend prior to
+ * this version (e.g. for targets resumed with a resume_token) should be suppressed (buffered)
+ * until the backend has caught up to this snapshot version again. This prevents our cache from
+ * ever going backwards in time.
+ *
+ * This is updated whenever our we get a TargetChange with a read_time and empty target_ids.
+ */
+- (FSTSnapshotVersion *)lastRemoteSnapshotVersion;
+
+/**
+ * Set the snapshot version representing the last consistent snapshot received from the backend.
+ * (see -lastRemoteSnapshotVersion for more details).
+ *
+ * @param snapshotVersion The new snapshot version.
+ */
+- (void)setLastRemoteSnapshotVersion:(FSTSnapshotVersion *)snapshotVersion
+                               group:(FSTWriteGroup *)group;
+
+/**
+ * Adds or replaces an entry in the cache.
+ *
+ * The cache key is extracted from `queryData.query`. If there is already a cache entry for the
+ * key, it will be replaced.
+ *
+ * @param queryData An FSTQueryData instance to put in the cache.
+ */
+- (void)addQueryData:(FSTQueryData *)queryData group:(FSTWriteGroup *)group;
+
+/** Removes the cached entry for the given query data (no-op if no entry exists). */
+- (void)removeQueryData:(FSTQueryData *)queryData group:(FSTWriteGroup *)group;
+
+/**
+ * Looks up an FSTQueryData entry in the cache.
+ *
+ * @param query The query corresponding to the entry to look up.
+ * @return The cached FSTQueryData entry, or nil if the cache has no entry for the query.
+ */
+- (nullable FSTQueryData *)queryDataForQuery:(FSTQuery *)query;
+
+/** Adds the given document keys to cached query results of the given target ID. */
+- (void)addMatchingKeys:(FSTDocumentKeySet *)keys
+            forTargetID:(FSTTargetID)targetID
+                  group:(FSTWriteGroup *)group;
+
+/** Removes the given document keys from the cached query results of the given target ID. */
+- (void)removeMatchingKeys:(FSTDocumentKeySet *)keys
+               forTargetID:(FSTTargetID)targetID
+                     group:(FSTWriteGroup *)group;
+
+/** Removes all the keys in the query results of the given target ID. */
+- (void)removeMatchingKeysForTargetID:(FSTTargetID)targetID group:(FSTWriteGroup *)group;
+
+- (FSTDocumentKeySet *)matchingKeysForTargetID:(FSTTargetID)targetID;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTQueryData.h b/Firestore/Source/Local/FSTQueryData.h
new file mode 100644
index 0000000..060fd78
--- /dev/null
+++ b/Firestore/Source/Local/FSTQueryData.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTTypes.h"
+
+@class FSTQuery;
+@class FSTSnapshotVersion;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** An enumeration of the different purposes we have for queries. */
+typedef NS_ENUM(NSInteger, FSTQueryPurpose) {
+  /** A regular, normal query. */
+  FSTQueryPurposeListen,
+
+  /** The query was used to refill a query after an existence filter mismatch. */
+  FSTQueryPurposeExistenceFilterMismatch,
+
+  /** The query was used to resolve a limbo document. */
+  FSTQueryPurposeLimboResolution,
+};
+
+/** An immutable set of metadata that the store will need to keep track of for each query. */
+@interface FSTQueryData : NSObject
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                     targetID:(FSTTargetID)targetID
+                      purpose:(FSTQueryPurpose)purpose
+              snapshotVersion:(FSTSnapshotVersion *)snapshotVersion
+                  resumeToken:(NSData *)resumeToken NS_DESIGNATED_INITIALIZER;
+
+/** Convenience initializer for use when creating an FSTQueryData for the first time. */
+- (instancetype)initWithQuery:(FSTQuery *)query
+                     targetID:(FSTTargetID)targetID
+                      purpose:(FSTQueryPurpose)purpose;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** Creates a new query data instance with an updated snapshot version and resume token. */
+- (instancetype)queryDataByReplacingSnapshotVersion:(FSTSnapshotVersion *)snapshotVersion
+                                        resumeToken:(NSData *)resumeToken;
+
+/** The query being listened to. */
+@property(nonatomic, strong, readonly) FSTQuery *query;
+
+/**
+ * The targetID to which the query corresponds, assigned by the FSTLocalStore for user queries or
+ * the FSTSyncEngine for limbo queries.
+ */
+@property(nonatomic, assign, readonly) FSTTargetID targetID;
+
+/** The purpose of the query. */
+@property(nonatomic, assign, readonly) FSTQueryPurpose purpose;
+
+/** The latest snapshot version seen for this target. */
+@property(nonatomic, strong, readonly) FSTSnapshotVersion *snapshotVersion;
+
+/**
+ * An opaque, server-assigned token that allows watching a query to be resumed after disconnecting
+ * without retransmitting all the data that matches the query. The resume token essentially
+ * identifies a point in time from which the server should resume sending results.
+ */
+@property(nonatomic, copy, readonly) NSData *resumeToken;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTQueryData.m b/Firestore/Source/Local/FSTQueryData.m
new file mode 100644
index 0000000..438f229
--- /dev/null
+++ b/Firestore/Source/Local/FSTQueryData.m
@@ -0,0 +1,93 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTQueryData.h"
+
+#import "FSTQuery.h"
+#import "FSTSnapshotVersion.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTQueryData
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                     targetID:(FSTTargetID)targetID
+                      purpose:(FSTQueryPurpose)purpose
+              snapshotVersion:(FSTSnapshotVersion *)snapshotVersion
+                  resumeToken:(NSData *)resumeToken {
+  self = [super init];
+  if (self) {
+    _query = query;
+    _targetID = targetID;
+    _purpose = purpose;
+    _snapshotVersion = snapshotVersion;
+    _resumeToken = [resumeToken copy];
+  }
+  return self;
+}
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                     targetID:(FSTTargetID)targetID
+                      purpose:(FSTQueryPurpose)purpose {
+  return [self initWithQuery:query
+                    targetID:targetID
+                     purpose:purpose
+             snapshotVersion:[FSTSnapshotVersion noVersion]
+                 resumeToken:[NSData data]];
+}
+
+- (BOOL)isEqual:(id)object {
+  if (self == object) {
+    return YES;
+  }
+  if (![object isKindOfClass:[FSTQueryData class]]) {
+    return NO;
+  }
+
+  FSTQueryData *other = (FSTQueryData *)object;
+  return [self.query isEqual:other.query] && self.targetID == other.targetID &&
+         self.purpose == other.purpose && [self.snapshotVersion isEqual:other.snapshotVersion] &&
+         [self.resumeToken isEqual:other.resumeToken];
+}
+
+- (NSUInteger)hash {
+  NSUInteger result = [self.query hash];
+  result = result * 31 + self.targetID;
+  result = result * 31 + self.purpose;
+  result = result * 31 + [self.snapshotVersion hash];
+  result = result * 31 + [self.resumeToken hash];
+  return result;
+}
+
+- (NSString *)description {
+  return [NSString
+      stringWithFormat:@"<FSTQueryData: query:%@ target:%d purpose:%lu version:%@ resumeToken:%@)>",
+                       self.query, self.targetID, (unsigned long)self.purpose, self.snapshotVersion,
+                       self.resumeToken];
+}
+
+- (instancetype)queryDataByReplacingSnapshotVersion:(FSTSnapshotVersion *)snapshotVersion
+                                        resumeToken:(NSData *)resumeToken {
+  return [[FSTQueryData alloc] initWithQuery:self.query
+                                    targetID:self.targetID
+                                     purpose:self.purpose
+                             snapshotVersion:snapshotVersion
+                                 resumeToken:resumeToken];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTReferenceSet.h b/Firestore/Source/Local/FSTReferenceSet.h
new file mode 100644
index 0000000..e4f50a7
--- /dev/null
+++ b/Firestore/Source/Local/FSTReferenceSet.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTDocumentKeySet.h"
+#import "FSTGarbageCollector.h"
+#import "FSTTypes.h"
+
+@class FSTDocumentKey;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * A collection of references to a document from some kind of numbered entity (either a targetID or
+ * batchID). As references are added to or removed from the set corresponding events are emitted to
+ * a registered garbage collector.
+ *
+ * Each reference is represented by a FSTDocumentReference object. Each of them contains enough
+ * information to uniquely identify the reference. They are all stored primarily in a set sorted
+ * by key. A document is considered garbage if there's no references in that set (this can be
+ * efficiently checked thanks to sorting by key).
+ *
+ * FSTReferenceSet also keeps a secondary set that contains references sorted by IDs. This one is
+ * used to efficiently implement removal of all references by some target ID.
+ */
+@interface FSTReferenceSet : NSObject <FSTGarbageSource>
+
+/** Keeps track of keys that have references. */
+@property(nonatomic, weak, readwrite, nullable) id<FSTGarbageCollector> garbageCollector;
+
+/** Returns YES if the reference set contains no references. */
+- (BOOL)isEmpty;
+
+/** Adds a reference to the given document key for the given ID. */
+- (void)addReferenceToKey:(FSTDocumentKey *)key forID:(int)ID;
+
+/** Add references to the given document keys for the given ID. */
+- (void)addReferencesToKeys:(FSTDocumentKeySet *)keys forID:(int)ID;
+
+/** Removes a reference to the given document key for the given ID. */
+- (void)removeReferenceToKey:(FSTDocumentKey *)key forID:(int)ID;
+
+/** Removes references to the given document keys for the given ID. */
+- (void)removeReferencesToKeys:(FSTDocumentKeySet *)keys forID:(int)ID;
+
+/** Clears all references with a given ID. Calls -removeReferenceToKey: for each key removed. */
+- (void)removeReferencesForID:(int)ID;
+
+/** Clears all references for all IDs. */
+- (void)removeAllReferences;
+
+/** Returns all of the document keys that have had references added for the given ID. */
+- (FSTDocumentKeySet *)referencedKeysForID:(int)ID;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTReferenceSet.m b/Firestore/Source/Local/FSTReferenceSet.m
new file mode 100644
index 0000000..2326ded
--- /dev/null
+++ b/Firestore/Source/Local/FSTReferenceSet.m
@@ -0,0 +1,135 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTReferenceSet.h"
+
+#import "FSTDocumentKey.h"
+#import "FSTDocumentReference.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTReferenceSet
+
+@interface FSTReferenceSet ()
+
+/** A set of outstanding references to a document sorted by key. */
+@property(nonatomic, strong) FSTImmutableSortedSet<FSTDocumentReference *> *referencesByKey;
+
+/** A set of outstanding references to a document sorted by target ID (or batch ID). */
+@property(nonatomic, strong) FSTImmutableSortedSet<FSTDocumentReference *> *referencesByID;
+
+@end
+
+@implementation FSTReferenceSet
+
+#pragma mark - Initializer
+
+- (instancetype)init {
+  self = [super init];
+  if (self) {
+    _referencesByKey =
+        [FSTImmutableSortedSet setWithComparator:FSTDocumentReferenceComparatorByKey];
+    _referencesByID = [FSTImmutableSortedSet setWithComparator:FSTDocumentReferenceComparatorByID];
+  }
+  return self;
+}
+
+#pragma mark - Testing helper methods
+
+- (BOOL)isEmpty {
+  return [self.referencesByKey isEmpty];
+}
+
+- (NSUInteger)count {
+  return self.referencesByKey.count;
+}
+
+#pragma mark - Public methods
+
+- (void)addReferenceToKey:(FSTDocumentKey *)key forID:(int)ID {
+  FSTDocumentReference *reference = [[FSTDocumentReference alloc] initWithKey:key ID:ID];
+  self.referencesByKey = [self.referencesByKey setByAddingObject:reference];
+  self.referencesByID = [self.referencesByID setByAddingObject:reference];
+}
+
+- (void)addReferencesToKeys:(FSTDocumentKeySet *)keys forID:(int)ID {
+  [keys enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+    [self addReferenceToKey:key forID:ID];
+  }];
+}
+
+- (void)removeReferenceToKey:(FSTDocumentKey *)key forID:(int)ID {
+  [self removeReference:[[FSTDocumentReference alloc] initWithKey:key ID:ID]];
+}
+
+- (void)removeReferencesToKeys:(FSTDocumentKeySet *)keys forID:(int)ID {
+  [keys enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+    [self removeReferenceToKey:key forID:ID];
+  }];
+}
+
+- (void)removeReferencesForID:(int)ID {
+  FSTDocumentKey *emptyKey = [FSTDocumentKey keyWithSegments:@[]];
+  FSTDocumentReference *start = [[FSTDocumentReference alloc] initWithKey:emptyKey ID:ID];
+  FSTDocumentReference *end = [[FSTDocumentReference alloc] initWithKey:emptyKey ID:(ID + 1)];
+
+  [self.referencesByID enumerateObjectsFrom:start
+                                         to:end
+                                 usingBlock:^(FSTDocumentReference *reference, BOOL *stop) {
+                                   [self removeReference:reference];
+                                 }];
+}
+
+- (void)removeAllReferences {
+  for (FSTDocumentReference *reference in self.referencesByKey.objectEnumerator) {
+    [self removeReference:reference];
+  }
+}
+
+- (void)removeReference:(FSTDocumentReference *)reference {
+  self.referencesByKey = [self.referencesByKey setByRemovingObject:reference];
+  self.referencesByID = [self.referencesByID setByRemovingObject:reference];
+  [self.garbageCollector addPotentialGarbageKey:reference.key];
+}
+
+- (FSTDocumentKeySet *)referencedKeysForID:(int)ID {
+  FSTDocumentKey *emptyKey = [FSTDocumentKey keyWithSegments:@[]];
+  FSTDocumentReference *start = [[FSTDocumentReference alloc] initWithKey:emptyKey ID:ID];
+  FSTDocumentReference *end = [[FSTDocumentReference alloc] initWithKey:emptyKey ID:(ID + 1)];
+
+  __block FSTDocumentKeySet *keys = [FSTDocumentKeySet keySet];
+  [self.referencesByID enumerateObjectsFrom:start
+                                         to:end
+                                 usingBlock:^(FSTDocumentReference *reference, BOOL *stop) {
+                                   keys = [keys setByAddingObject:reference.key];
+                                 }];
+  return keys;
+}
+
+- (BOOL)containsKey:(FSTDocumentKey *)key {
+  // Create a reference with a zero ID as the start position to find any document reference with
+  // this key.
+  FSTDocumentReference *reference = [[FSTDocumentReference alloc] initWithKey:key ID:0];
+
+  NSEnumerator<FSTDocumentReference *> *enumerator =
+      [self.referencesByKey objectEnumeratorFrom:reference];
+  FSTDocumentKey *_Nullable firstKey = [enumerator nextObject].key;
+  return [firstKey isEqual:reference.key];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTRemoteDocumentCache.h b/Firestore/Source/Local/FSTRemoteDocumentCache.h
new file mode 100644
index 0000000..8979455
--- /dev/null
+++ b/Firestore/Source/Local/FSTRemoteDocumentCache.h
@@ -0,0 +1,76 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTDocumentDictionary.h"
+
+@class FSTDocumentKey;
+@class FSTMaybeDocument;
+@class FSTQuery;
+@class FSTWriteGroup;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * Represents cached documents received from the remote backend.
+ *
+ * The cache is keyed by FSTDocumentKey and entries in the cache are FSTMaybeDocument instances,
+ * meaning we can cache both FSTDocument instances (an actual document with data) as well as
+ * FSTDeletedDocument instances (indicating that the document is known to not exist).
+ */
+@protocol FSTRemoteDocumentCache <NSObject>
+
+/** Shuts this cache down, closing open files, etc. */
+- (void)shutdown;
+
+/**
+ * Adds or replaces an entry in the cache.
+ *
+ * The cache key is extracted from `maybeDocument.key`. If there is already a cache entry for
+ * the key, it will be replaced.
+ *
+ * @param maybeDocument A FSTDocument or FSTDeletedDocument to put in the cache.
+ */
+- (void)addEntry:(FSTMaybeDocument *)maybeDocument group:(FSTWriteGroup *)group;
+
+/** Removes the cached entry for the given key (no-op if no entry exists). */
+- (void)removeEntryForKey:(FSTDocumentKey *)documentKey group:(FSTWriteGroup *)group;
+
+/**
+ * Looks up an entry in the cache.
+ *
+ * @param documentKey The key of the entry to look up.
+ * @return The cached FSTDocument or FSTDeletedDocument entry, or nil if we have nothing cached.
+ */
+- (nullable FSTMaybeDocument *)entryForKey:(FSTDocumentKey *)documentKey;
+
+/**
+ * Executes a query against the cached FSTDocument entries
+ *
+ * Implementations may return extra documents if convenient. The results should be re-filtered
+ * by the consumer before presenting them to the user.
+ *
+ * Cached FSTDeletedDocument entries have no bearing on query results.
+ *
+ * @param query The query to match documents against.
+ * @return The set of matching documents.
+ */
+- (FSTDocumentDictionary *)documentsMatchingQuery:(FSTQuery *)query;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTRemoteDocumentChangeBuffer.h b/Firestore/Source/Local/FSTRemoteDocumentChangeBuffer.h
new file mode 100644
index 0000000..be0d609
--- /dev/null
+++ b/Firestore/Source/Local/FSTRemoteDocumentChangeBuffer.h
@@ -0,0 +1,66 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+NS_ASSUME_NONNULL_BEGIN
+
+@protocol FSTRemoteDocumentCache;
+@class FSTMaybeDocument;
+@class FSTDocumentKey;
+@class FSTWriteGroup;
+
+/**
+ * An in-memory buffer of entries to be written to an FSTRemoteDocumentCache. It can be used to
+ * batch up a set of changes to be written to the cache, but additionally supports reading entries
+ * back with the `entryForKey:` method, falling back to the underlying FSTRemoteDocumentCache if
+ * no entry is buffered. In the absence of LevelDB transactions (that would allow reading back
+ * uncommitted writes), this greatly simplifies the implementation of complex operations that
+ * may want to freely read/write entries to the FSTRemoteDocumentCache while still ensuring that
+ * the final writing of the buffered entries is atomic.
+ *
+ * For doing blind writes that don't depend on the current state of the FSTRemoteDocumentCache
+ * or for plain reads, you can/should still just use the FSTRemoteDocumentCache directly.
+ */
+@interface FSTRemoteDocumentChangeBuffer : NSObject
+
++ (instancetype)changeBufferWithCache:(id<FSTRemoteDocumentCache>)cache;
+
+- (instancetype)init __attribute__((unavailable("Use a static constructor instead")));
+
+/** Buffers an `FSTRemoteDocumentCache addEntry:group:` call. */
+- (void)addEntry:(FSTMaybeDocument *)maybeDocument;
+
+// NOTE: removeEntryForKey: is not presently necessary and so is omitted.
+
+/**
+ * Looks up an entry in the cache. The buffered changes will first be checked, and if no
+ * buffered change applies, this will forward to `FSTRemoteDocumentCache entryForKey:`.
+ *
+ * @param documentKey The key of the entry to look up.
+ * @return The cached FSTDocument or FSTDeletedDocument entry, or nil if we have nothing cached.
+ */
+- (nullable FSTMaybeDocument *)entryForKey:(FSTDocumentKey *)documentKey;
+
+/**
+ * Applies buffered changes to the underlying FSTRemoteDocumentCache, using the provided
+ * FSTWriteGroup.
+ */
+- (void)applyToWriteGroup:(FSTWriteGroup *)group;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTRemoteDocumentChangeBuffer.m b/Firestore/Source/Local/FSTRemoteDocumentChangeBuffer.m
new file mode 100644
index 0000000..12a68ff
--- /dev/null
+++ b/Firestore/Source/Local/FSTRemoteDocumentChangeBuffer.m
@@ -0,0 +1,88 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTRemoteDocumentChangeBuffer.h"
+
+#import "FSTAssert.h"
+#import "FSTDocument.h"
+#import "FSTDocumentKey.h"
+#import "FSTRemoteDocumentCache.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTRemoteDocumentChangeBuffer ()
+
+- (instancetype)initWithCache:(id<FSTRemoteDocumentCache>)cache;
+
+/** The underlying cache we're buffering changes for. */
+@property(nonatomic, strong, nonnull) id<FSTRemoteDocumentCache> remoteDocumentCache;
+
+/** The buffered changes, stored as a dictionary for easy lookups. */
+@property(nonatomic, strong, nullable)
+    NSMutableDictionary<FSTDocumentKey *, FSTMaybeDocument *> *changes;
+
+@end
+
+@implementation FSTRemoteDocumentChangeBuffer
+
++ (instancetype)changeBufferWithCache:(id<FSTRemoteDocumentCache>)cache {
+  return [[FSTRemoteDocumentChangeBuffer alloc] initWithCache:cache];
+}
+
+- (instancetype)initWithCache:(id<FSTRemoteDocumentCache>)cache {
+  if (self = [super init]) {
+    _remoteDocumentCache = cache;
+    _changes = [NSMutableDictionary dictionary];
+  }
+  return self;
+}
+
+- (void)addEntry:(FSTMaybeDocument *)maybeDocument {
+  [self assertValid];
+
+  self.changes[maybeDocument.key] = maybeDocument;
+}
+
+- (nullable FSTMaybeDocument *)entryForKey:(FSTDocumentKey *)documentKey {
+  [self assertValid];
+
+  FSTMaybeDocument *bufferedEntry = self.changes[documentKey];
+  if (bufferedEntry) {
+    return bufferedEntry;
+  } else {
+    return [self.remoteDocumentCache entryForKey:documentKey];
+  }
+}
+
+- (void)applyToWriteGroup:(FSTWriteGroup *)group {
+  [self assertValid];
+
+  [self.changes enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key, FSTMaybeDocument *value,
+                                                    BOOL *stop) {
+    [self.remoteDocumentCache addEntry:value group:group];
+  }];
+
+  // We should not be used to buffer any more changes.
+  self.changes = nil;
+}
+
+- (void)assertValid {
+  FSTAssert(self.changes, @"Changes have already been applied.");
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTWriteGroup.h b/Firestore/Source/Local/FSTWriteGroup.h
new file mode 100644
index 0000000..21482af
--- /dev/null
+++ b/Firestore/Source/Local/FSTWriteGroup.h
@@ -0,0 +1,97 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+#ifdef __cplusplus
+#include <memory>
+
+#include "StringView.h"
+
+namespace leveldb {
+class DB;
+class Status;
+}
+
+#endif
+
+NS_ASSUME_NONNULL_BEGIN
+
+@class GPBMessage;
+
+/**
+ * A group of writes that will be applied together atomically to persistent storage.
+ *
+ * This class is usable by both Objective-C and Objective-C++ clients. Objective-C clients are able
+ * to create a new group and commit it. Objective-C++ clients can additionally add to the group
+ * using deleteKey: and putKey:value:.
+ *
+ * Note that this is a write "group" even though the underlying LevelDB concept is a write "batch"
+ * because Firestore already has a concept of mutation batches, which are user-specified groups of
+ * changes. This means that an FSTWriteGroup may contain the application of multiple user-specified
+ * mutation batches.
+ */
+@interface FSTWriteGroup : NSObject
+
+/**
+ * Creates a new, empty write group.
+ *
+ * @param action A description of the action performed by this group, used for logging.
+ */
++ (instancetype)groupWithAction:(NSString *)action;
+
+- (instancetype)init __attribute__((unavailable("Use a static constructor instead")));
+
+/** The action description assigned to this write group. */
+@property(nonatomic, copy, readonly) NSString *action;
+
+/** Returns YES if the write group has no messages in it. */
+- (BOOL)isEmpty;
+
+#ifdef __cplusplus
+
+/**
+ * Marks the given key for deletion.
+ *
+ * @param key The LevelDB key of the row to delete
+ */
+- (void)removeMessageForKey:(Firestore::StringView)key;
+
+/**
+ * Sets the row identified by the given key to the value of the given protocol buffer message.
+ *
+ * @param key The LevelDB Key of the row to set.
+ * @param message The protocol buffer message whose serialized contents should be used for the
+ *     value associated with the key.
+ */
+- (void)setMessage:(GPBMessage *)message forKey:(Firestore::StringView)key;
+
+/**
+ * Sets the row identified by the given key to the value of the given data bytes.
+ *
+ * @param key The LevelDB Key of the row to set.
+ * @param data The exact value to be associated with the key.
+ */
+- (void)setData:(Firestore::StringView)data forKey:(Firestore::StringView)key;
+
+/** Writes the contents to the given LevelDB. */
+- (leveldb::Status)writeToDB:(std::shared_ptr<leveldb::DB>)db;
+
+#endif
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTWriteGroup.mm b/Firestore/Source/Local/FSTWriteGroup.mm
new file mode 100644
index 0000000..e6da131
--- /dev/null
+++ b/Firestore/Source/Local/FSTWriteGroup.mm
@@ -0,0 +1,145 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTWriteGroup.h"
+
+#import <Protobuf/GPBProtocolBuffers.h>
+#include <leveldb/db.h>
+#include <leveldb/write_batch.h>
+
+#import "FSTLevelDBKey.h"
+#import "FSTAssert.h"
+
+#include "ordered_code.h"
+
+using Firestore::OrderedCode;
+using Firestore::StringView;
+using leveldb::DB;
+using leveldb::Slice;
+using leveldb::Status;
+using leveldb::WriteBatch;
+using leveldb::WriteOptions;
+
+NS_ASSUME_NONNULL_BEGIN
+
+namespace Firestore {
+
+/**
+ * A WriteBatch::Handler implementation that extracts batch details from a leveldb::WriteBatch.
+ * This is used for describing a write batch primarily in log messages after a failure.
+ */
+class BatchDescription : public WriteBatch::Handler {
+ public:
+  BatchDescription() : ops_(0), size_(0), message_([NSMutableString string]) {}
+  virtual ~BatchDescription();
+  virtual void Put(const Slice &key, const Slice &value);
+  virtual void Delete(const Slice &key);
+
+  // Converts the batch to a printable string description of it
+  NSString *ToString() const {
+    return [NSString
+        stringWithFormat:@"%d changes (%lu bytes):%@", ops_, (unsigned long)size_, message_];
+  }
+
+  // Disallow copies and moves
+  BatchDescription(const BatchDescription &) = delete;
+  BatchDescription &operator=(const BatchDescription &) = delete;
+  BatchDescription(BatchDescription &&) = delete;
+  BatchDescription &operator=(BatchDescription &&) = delete;
+
+ private:
+  int ops_;
+  size_t size_;
+  NSMutableString *message_;
+};
+
+BatchDescription::~BatchDescription() {}
+
+void BatchDescription::Put(const Slice &key, const Slice &value) {
+  ops_ += 1;
+  size_ += value.size();
+
+  [message_ appendFormat:@"\n  - Put %@ (%lu bytes)", [FSTLevelDBKey descriptionForKey:key],
+                         (unsigned long)value.size()];
+}
+
+void BatchDescription::Delete(const Slice &key) {
+  ops_ += 1;
+
+  [message_ appendFormat:@"\n  - Delete %@", [FSTLevelDBKey descriptionForKey:key]];
+}
+
+}  // namespace Firestore
+
+@interface FSTWriteGroup ()
+- (instancetype)initWithAction:(NSString *)action NS_DESIGNATED_INITIALIZER;
+@end
+
+@implementation FSTWriteGroup {
+  int _changes;
+  WriteBatch _contents;
+}
+
++ (instancetype)groupWithAction:(NSString *)action {
+  return [[FSTWriteGroup alloc] initWithAction:action];
+}
+
+- (instancetype)initWithAction:(NSString *)action {
+  if (self = [super init]) {
+    _action = action;
+  }
+  return self;
+}
+
+- (NSString *)description {
+  Firestore::BatchDescription description;
+  Status status = _contents.Iterate(&description);
+  if (!status.ok()) {
+    FSTFail(@"Iterate over write batch should not fail");
+  }
+  return [NSString
+      stringWithFormat:@"<FSTWriteGroup for %@: %@>", self.action, description.ToString()];
+}
+
+- (void)removeMessageForKey:(StringView)key {
+  _contents.Delete(key);
+  _changes += 1;
+}
+
+- (void)setMessage:(GPBMessage *)message forKey:(StringView)key {
+  NSData *data = [message data];
+  Slice value((const char *)data.bytes, data.length);
+
+  _contents.Put(key, value);
+  _changes += 1;
+}
+
+- (void)setData:(StringView)data forKey:(StringView)key {
+  _contents.Put(key, data);
+  _changes += 1;
+}
+
+- (leveldb::Status)writeToDB:(std::shared_ptr<leveldb::DB>)db {
+  return db->Write(leveldb::WriteOptions(), &_contents);
+}
+
+- (BOOL)isEmpty {
+  return _changes == 0;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTWriteGroupTracker.h b/Firestore/Source/Local/FSTWriteGroupTracker.h
new file mode 100644
index 0000000..bd26a46
--- /dev/null
+++ b/Firestore/Source/Local/FSTWriteGroupTracker.h
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+
+@class FSTWriteGroup;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * Helper class for FSTPersistence implementations to create WriteGroups and verify internal
+ * contracts are maintained:
+ * 1. Can't create a group when an uncommitted group exists (no nesting).
+ * 2. Can't commit a group that differs from the last created one.
+ */
+@interface FSTWriteGroupTracker : NSObject
+
+/** Creates and returns an FSTWriteGroupTracker instance. */
++ (instancetype)tracker;
+
+/**
+ * Verifies there's no active group already and then creates a new group and stores it for later
+ * validation with `endGroup`.
+ */
+- (FSTWriteGroup *)startGroupWithAction:(NSString *)action;
+
+/** Ends a group previously started with `startGroupWithAction`. */
+- (void)endGroup:(FSTWriteGroup *)group;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTWriteGroupTracker.m b/Firestore/Source/Local/FSTWriteGroupTracker.m
new file mode 100644
index 0000000..1c6c84d
--- /dev/null
+++ b/Firestore/Source/Local/FSTWriteGroupTracker.m
@@ -0,0 +1,52 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import "FSTWriteGroupTracker.h"
+
+#import "FSTAssert.h"
+#import "FSTWriteGroup.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTWriteGroupTracker ()
+@property(nonatomic, strong, nullable) FSTWriteGroup *activeGroup;
+@end
+
+@implementation FSTWriteGroupTracker
+
++ (instancetype)tracker {
+  return [[FSTWriteGroupTracker alloc] init];
+}
+
+- (FSTWriteGroup *)startGroupWithAction:(NSString *)action {
+  // NOTE: We can relax this to allow nesting if/when we find we need it.
+  FSTAssert(!self.activeGroup,
+            @"Attempt to create write group (%@) while existing write group (%@) still active.",
+            action, self.activeGroup.action);
+  self.activeGroup = [FSTWriteGroup groupWithAction:action];
+  return self.activeGroup;
+}
+
+- (void)endGroup:(FSTWriteGroup *)group {
+  FSTAssert(self.activeGroup == group,
+            @"Attempted to end write group (%@) which is different from active group (%@)",
+            group.action, self.activeGroup.action);
+  self.activeGroup = nil;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/StringView.h b/Firestore/Source/Local/StringView.h
new file mode 100644
index 0000000..799baf8
--- /dev/null
+++ b/Firestore/Source/Local/StringView.h
@@ -0,0 +1,85 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef IPHONE_FIRESTORE_SOURCE_LOCAL_STRING_VIEW_H_
+#define IPHONE_FIRESTORE_SOURCE_LOCAL_STRING_VIEW_H_
+
+#ifndef __cplusplus
+#error "StringView is Objective-C++ and can only be included from .mm files"
+#endif
+
+#import <Foundation/Foundation.h>
+
+#include <leveldb/slice.h>
+#include <string>
+
+namespace Firestore {
+
+// A simple wrapper for the character data of any string-like type to which
+// we'd like to temporarily refer as an argument.
+//
+// This is superficially similar to StringPiece and leveldb::Slice except
+// that it also supports implicit conversion from NSString *, which is useful
+// when writing Objective-C++ methods that accept any string-like type.
+//
+// Note that much like any other view-type class in C++, the caller is
+// responsible for ensuring that the lifetime of the string-like data is longer
+// than the lifetime of the StringView.
+//
+// Functions that take a StringView argument promise that they won't keep the
+// pointer beyond the immediate scope of their own stack frame.
+class StringView {
+ public:
+  // Creates a StringView from an NSString. When StringView is an argument type
+  // into which an NSString* is passed, the caller should ensure that the
+  // NSString is retained.
+  StringView(NSString *str) : data_([str UTF8String]), size_(str.length) {
+  }
+
+  // Creates a StringView from the given char* pointer with an explicit size.
+  // The character data can contain NUL bytes as a result.
+  StringView(const char *data, size_t size) : data_(data), size_(size) {
+  }
+
+  // Creates a StringView from the given char* pointer but computes the size
+  // with strlen. This is really only suitable for passing C string literals.
+  StringView(const char *data) : data_(data), size_(strlen(data)) {
+  }
+
+  // Creates a StringView from the given slice.
+  StringView(leveldb::Slice slice) : data_(slice.data()), size_(slice.size()) {
+  }
+
+  // Creates a StringView from the given std::string. The string must be an
+  // lvalue for the lifetime requirements to be satisfied.
+  StringView(const std::string &str) : data_(str.data()), size_(str.size()) {
+  }
+
+  // Converts this StringView to a Slice, which is an equivalent (and more
+  // functional) type. The returned slice has the same lifetime as this
+  // StringView.
+  operator leveldb::Slice() {
+    return leveldb::Slice(data_, size_);
+  }
+
+ private:
+  const char *data_;
+  const size_t size_;
+};
+
+}  // namespace Firestore
+
+#endif  // IPHONE_FIRESTORE_SOURCE_LOCAL_STRING_VIEW_H_