Initial

15 files changed, 2065 insertions, 0 deletions

diff --git a/Firebase/Database/Persistence/FCachePolicy.h b/Firebase/Database/Persistence/FCachePolicy.h
new file mode 100644
index 0000000..16b49fb
--- /dev/null
+++ b/Firebase/Database/Persistence/FCachePolicy.h
@@ -0,0 +1,41 @@
+/*
+ * 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>
+
+@protocol FCachePolicy <NSObject>
+
+- (BOOL)shouldPruneCacheWithSize:(NSUInteger)cacheSize numberOfTrackedQueries:(NSUInteger)numTrackedQueries;
+- (BOOL)shouldCheckCacheSize:(NSUInteger)serverUpdatesSinceLastCheck;
+- (float)percentOfQueriesToPruneAtOnce;
+- (NSUInteger)maxNumberOfQueriesToKeep;
+
+@end
+
+
+@interface FLRUCachePolicy : NSObject<FCachePolicy>
+
+@property (nonatomic, readonly) NSUInteger maxSize;
+
+- (id)initWithMaxSize:(NSUInteger)maxSize;
+
+@end
+
+@interface FNoCachePolicy : NSObject<FCachePolicy>
+
++ (FNoCachePolicy *)noCachePolicy;
+
+@end
diff --git a/Firebase/Database/Persistence/FCachePolicy.m b/Firebase/Database/Persistence/FCachePolicy.m
new file mode 100644
index 0000000..7da76ef
--- /dev/null
+++ b/Firebase/Database/Persistence/FCachePolicy.m
@@ -0,0 +1,79 @@
+/*
+ * 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 "FCachePolicy.h"
+
+@interface FLRUCachePolicy ()
+
+@property (nonatomic, readwrite) NSUInteger maxSize;
+
+@end
+
+static const NSUInteger kFServerUpdatesBetweenCacheSizeChecks = 1000;
+static const NSUInteger kFMaxNumberOfPrunableQueriesToKeep = 1000;
+static const float kFPercentOfQueriesToPruneAtOnce = 0.2f;
+
+@implementation FLRUCachePolicy
+
+- (id)initWithMaxSize:(NSUInteger)maxSize {
+    self = [super init];
+    if (self != nil) {
+        self->_maxSize = maxSize;
+    }
+    return self;
+}
+
+- (BOOL)shouldPruneCacheWithSize:(NSUInteger)cacheSize numberOfTrackedQueries:(NSUInteger)numTrackedQueries {
+    return cacheSize > self.maxSize || numTrackedQueries > kFMaxNumberOfPrunableQueriesToKeep;
+}
+
+- (BOOL)shouldCheckCacheSize:(NSUInteger)serverUpdatesSinceLastCheck {
+    return serverUpdatesSinceLastCheck > kFServerUpdatesBetweenCacheSizeChecks;
+}
+
+- (float)percentOfQueriesToPruneAtOnce {
+    return kFPercentOfQueriesToPruneAtOnce;
+}
+
+- (NSUInteger)maxNumberOfQueriesToKeep {
+    return kFMaxNumberOfPrunableQueriesToKeep;
+}
+
+@end
+
+@implementation FNoCachePolicy
+
++ (FNoCachePolicy *)noCachePolicy {
+    return [[FNoCachePolicy alloc] init];
+}
+
+- (BOOL)shouldPruneCacheWithSize:(NSUInteger)cacheSize numberOfTrackedQueries:(NSUInteger)numTrackedQueries {
+    return NO;
+}
+
+- (BOOL)shouldCheckCacheSize:(NSUInteger)serverUpdatesSinceLastCheck {
+    return NO;
+}
+
+- (float)percentOfQueriesToPruneAtOnce {
+    return 0;
+}
+
+- (NSUInteger)maxNumberOfQueriesToKeep {
+    return NSUIntegerMax;
+}
+
+@end
diff --git a/Firebase/Database/Persistence/FLevelDBStorageEngine.h b/Firebase/Database/Persistence/FLevelDBStorageEngine.h
new file mode 100644
index 0000000..059a071
--- /dev/null
+++ b/Firebase/Database/Persistence/FLevelDBStorageEngine.h
@@ -0,0 +1,37 @@
+/*
+ * 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 "FStorageEngine.h"
+#import "FNode.h"
+#import "FPath.h"
+#import "FCompoundWrite.h"
+#import "FQuerySpec.h"
+
+@class FCacheNode;
+@class FTrackedQuery;
+@class FPruneForest;
+@class FRepoInfo;
+
+@interface FLevelDBStorageEngine : NSObject<FStorageEngine>
+
+- (id)initWithPath:(NSString *)path;
+
+- (void)runLegacyMigration:(FRepoInfo *)info;
+- (void)purgeEverything;
+
+@end
diff --git a/Firebase/Database/Persistence/FLevelDBStorageEngine.m b/Firebase/Database/Persistence/FLevelDBStorageEngine.m
new file mode 100644
index 0000000..4b324b8
--- /dev/null
+++ b/Firebase/Database/Persistence/FLevelDBStorageEngine.m
@@ -0,0 +1,717 @@
+/*
+ * 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 "FLevelDBStorageEngine.h"
+
+#import "APLevelDB.h"
+#import "FSnapshotUtilities.h"
+#import "FWriteRecord.h"
+#import "FTrackedQuery.h"
+#import "FQueryParams.h"
+#import "FEmptyNode.h"
+#import "FPruneForest.h"
+#import "FUtilities.h"
+#import "FPendingPut.h" // For legacy migration
+
+@interface FLevelDBStorageEngine ()
+
+@property (nonatomic, strong) NSString *basePath;
+@property (nonatomic, strong) APLevelDB *writesDB;
+@property (nonatomic, strong) APLevelDB *serverCacheDB;
+
+@end
+
+// WARNING: If you change this, you need to write a migration script
+static NSString * const kFPersistenceVersion = @"1";
+
+static NSString * const kFServerDBPath = @"server_data";
+static NSString * const kFWritesDBPath = @"writes";
+
+static NSString * const kFUserWriteId = @"id";
+static NSString * const kFUserWritePath = @"path";
+static NSString * const kFUserWriteOverwrite = @"o";
+static NSString * const kFUserWriteMerge = @"m";
+
+static NSString * const kFTrackedQueryId = @"id";
+static NSString * const kFTrackedQueryPath = @"path";
+static NSString * const kFTrackedQueryParams = @"p";
+static NSString * const kFTrackedQueryLastUse = @"lu";
+static NSString * const kFTrackedQueryIsComplete = @"c";
+static NSString * const kFTrackedQueryIsActive = @"a";
+
+static NSString * const kFServerCachePrefix = @"/server_cache/";
+// '~' is the last non-control character in the ASCII table until 127
+// We wan't the entire range of thing stored in the DB
+static NSString * const kFServerCacheRangeEnd = @"/server_cache~";
+static NSString * const kFTrackedQueriesPrefix = @"/tracked_queries/";
+static NSString * const kFTrackedQueryKeysPrefix = @"/tracked_query_keys/";
+
+// Failed to load JSON because a valid JSON turns out to be NaN while deserializing
+static const NSInteger kFNanFailureCode = 3840;
+
+static NSString* writeRecordKey(NSUInteger writeId) {
+    return [NSString stringWithFormat:@"%lu", (unsigned long)(writeId)];
+}
+
+static NSString* serverCacheKey(FPath *path) {
+    return [NSString stringWithFormat:@"%@%@", kFServerCachePrefix, ([path toStringWithTrailingSlash])];
+}
+
+static NSString* trackedQueryKey(NSUInteger trackedQueryId) {
+    return [NSString stringWithFormat:@"%@%lu", kFTrackedQueriesPrefix, (unsigned long)trackedQueryId];
+}
+
+static NSString* trackedQueryKeysKeyPrefix(NSUInteger trackedQueryId) {
+    return [NSString stringWithFormat:@"%@%lu/", kFTrackedQueryKeysPrefix, (unsigned long)trackedQueryId];
+}
+
+static NSString* trackedQueryKeysKey(NSUInteger trackedQueryId, NSString *key) {
+    return [NSString stringWithFormat:@"%@%lu/%@", kFTrackedQueryKeysPrefix, (unsigned long)trackedQueryId, key];
+}
+
+@implementation FLevelDBStorageEngine
+#pragma mark - Constructors
+
+- (id)initWithPath:(NSString*)dbPath
+{
+    self = [super init];
+    if (self) {
+        self.basePath = [[FLevelDBStorageEngine firebaseDir] stringByAppendingPathComponent:dbPath];
+        /* For reference:
+         serverDataDB = [aPersistence createDbByName:@"server_data"];
+         FPangolinDB *completenessDb = [aPersistence createDbByName:@"server_complete"];
+         */
+        [FLevelDBStorageEngine ensureDir:self.basePath markAsDoNotBackup:YES];
+        [self runMigration];
+        [self openDatabases];
+    }
+    return self;
+}
+
+- (void)runMigration {
+    // Currently we're at version 1, so all we need to do is write that to a file
+    NSString *versionFile = [self.basePath stringByAppendingPathComponent:@"version"];
+    NSError *error;
+    NSString *oldVersion = [NSString stringWithContentsOfFile:versionFile encoding:NSUTF8StringEncoding error:&error];
+    if (!oldVersion) {
+        // This is probably fine, we don't have a version file yet
+        BOOL success = [kFPersistenceVersion writeToFile:versionFile atomically:NO encoding:NSUTF8StringEncoding error:&error];
+        if (!success) {
+            FFWarn(@"I-RDB076001", @"Failed to write version for database: %@", error);
+        }
+    } else if ([oldVersion isEqualToString:kFPersistenceVersion]) {
+        // Everythings fine no need for migration
+    } else {
+        // If we add more versions in the future, we need to run migration here
+        [NSException raise:NSInternalInconsistencyException format:@"Unrecognized database version: %@", oldVersion];
+    }
+}
+
+- (void)runLegacyMigration:(FRepoInfo *)info {
+    NSArray *dirPaths = NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES);
+    NSString *documentsDir = [dirPaths objectAtIndex:0];
+    NSString *firebaseDir = [documentsDir stringByAppendingPathComponent:@"firebase"];
+    NSString* repoHashString = [NSString stringWithFormat:@"%@_%@", info.host, info.namespace];
+    NSString *legacyBaseDir = [NSString stringWithFormat:@"%@/1/%@/v1", firebaseDir, repoHashString];
+    if ([[NSFileManager defaultManager] fileExistsAtPath:legacyBaseDir]) {
+        FFWarn(@"I-RDB076002", @"Legacy database found, migrating...");
+        // We only need to migrate writes
+        NSError *error = nil;
+        APLevelDB *writes = [APLevelDB levelDBWithPath:[legacyBaseDir stringByAppendingPathComponent:@"outstanding_puts"] error:&error];
+        if (writes != nil) {
+            __block NSUInteger numberOfWritesRestored = 0;
+            // Maybe we could use write batches, but what the heck, I'm sure it'll go fine :P
+            [writes enumerateKeysAndValuesAsData:^(NSString *key, NSData *data, BOOL *stop) {
+                id pendingPut = [NSKeyedUnarchiver unarchiveObjectWithData:data];
+                if ([pendingPut isKindOfClass:[FPendingPut class]]) {
+                    FPendingPut *put = pendingPut;
+                    id<FNode> newNode = [FSnapshotUtilities nodeFrom:put.data priority:put.priority];
+                    [self saveUserOverwrite:newNode atPath:put.path writeId:[key integerValue]];
+                    numberOfWritesRestored++;
+                } else if ([pendingPut isKindOfClass:[FPendingPutPriority class]]) {
+                    // This is for backwards compatibility. Older clients will save FPendingPutPriority. New ones will need to read it and translate.
+                    FPendingPutPriority *putPriority = pendingPut;
+                    FPath *priorityPath = [putPriority.path childFromString:@".priority"];
+                    id<FNode> newNode = [FSnapshotUtilities nodeFrom:putPriority.priority priority:nil];
+                    [self saveUserOverwrite:newNode atPath:priorityPath writeId:[key integerValue]];
+                    numberOfWritesRestored++;
+                } else if ([pendingPut isKindOfClass:[FPendingUpdate class]]) {
+                    FPendingUpdate *update = pendingPut;
+                    FCompoundWrite *merge = [FCompoundWrite compoundWriteWithValueDictionary:update.data];
+                    [self saveUserMerge:merge atPath:update.path writeId:[key integerValue]];
+                    numberOfWritesRestored++;
+                } else {
+                    FFWarn(@"I-RDB076003", @"Failed to migrate legacy write, meh!");
+                }
+            }];
+            FFWarn(@"I-RDB076004", @"Migrated %lu writes", (unsigned long)numberOfWritesRestored);
+            [writes close];
+            FFWarn(@"I-RDB076005", @"Deleting legacy database...");
+            BOOL success = [[NSFileManager defaultManager] removeItemAtPath:legacyBaseDir error:&error];
+            if (!success) {
+                FFWarn(@"I-RDB076006", @"Failed to delete legacy database: %@", error);
+            } else {
+                FFWarn(@"I-RDB076007", @"Finished migrating legacy database.");
+            }
+        } else {
+            FFWarn(@"I-RDB076008", @"Failed to migrate old database: %@", error);
+        }
+    }
+}
+
+- (void)openDatabases {
+    self.serverCacheDB = [self createDB:kFServerDBPath];
+    self.writesDB = [self createDB:kFWritesDBPath];
+}
+
+- (void)purgeEverything {
+    [self close];
+    [@[kFServerDBPath, kFWritesDBPath]
+     enumerateObjectsUsingBlock:^(NSString *dbPath, NSUInteger idx, BOOL *stop) {
+         NSString *path = [self.basePath stringByAppendingPathComponent:dbPath];
+         NSError *error;
+         FFDebug(@"I-RDB076009", @"Deleting database at path %@", path);
+         BOOL success = [[NSFileManager defaultManager] removeItemAtPath:path error:&error];
+         if (!success) {
+             [NSException raise:NSInternalInconsistencyException format:@"Failed to delete database files: %@", error];
+         }
+    }];
+
+    [self openDatabases];
+}
+
+- (void)close {
+    // autoreleasepool will cause deallocation which will close the DB
+    @autoreleasepool {
+        [self.serverCacheDB close];
+        self.serverCacheDB = nil;
+        [self.writesDB close];
+        self.writesDB = nil;
+    }
+}
+
++ (NSString *) firebaseDir {
+#if TARGET_OS_IPHONE
+    NSArray *dirPaths = NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES);
+    NSString *documentsDir = [dirPaths objectAtIndex:0];
+    return [documentsDir stringByAppendingPathComponent:@"firebase"];
+#else // this must be OSX then
+    return [NSHomeDirectory() stringByAppendingPathComponent:@".firebase"];
+#endif
+}
+
+- (APLevelDB *)createDB:(NSString *)name {
+    NSError *err = nil;
+    NSString *path = [self.basePath stringByAppendingPathComponent:name];
+    APLevelDB *db = [APLevelDB levelDBWithPath:path error:&err];
+    if(err) {
+        NSString *reason = [NSString stringWithFormat:@"Error initializing persistence: %@", [err description]];
+        @throw [NSException exceptionWithName:@"FirebaseDatabasePersistenceFailure" reason:reason userInfo:nil];
+    }
+    return db;
+}
+
+- (void)saveUserOverwrite:(id<FNode>)node atPath:(FPath *)path writeId:(NSUInteger)writeId {
+    NSDictionary *write =
+    @{ kFUserWriteId: @(writeId),
+       kFUserWritePath: [path toStringWithTrailingSlash],
+       kFUserWriteOverwrite: [node valForExport:YES] };
+    NSError *error = nil;
+    NSData *data = [NSJSONSerialization dataWithJSONObject:write options:0 error:&error];
+    NSAssert(data, @"Failed to serialize user overwrite: %@, (Error: %@)", write, error);
+    [self.writesDB setData:data forKey:writeRecordKey(writeId)];
+}
+
+- (void)saveUserMerge:(FCompoundWrite *)merge atPath:(FPath *)path writeId:(NSUInteger)writeId {
+    NSDictionary *write =
+    @{ kFUserWriteId: @(writeId),
+       kFUserWritePath: [path toStringWithTrailingSlash],
+       kFUserWriteMerge: [merge valForExport:YES] };
+    NSError *error = nil;
+    NSData *data = [NSJSONSerialization dataWithJSONObject:write options:0 error:&error];
+    NSAssert(data, @"Failed to serialize user merge: %@ (Error: %@)", write, error);
+    [self.writesDB setData:data forKey:writeRecordKey(writeId)];
+}
+
+- (void)removeUserWrite:(NSUInteger)writeId {
+    [self.writesDB removeKey:writeRecordKey(writeId)];
+}
+
+- (void)removeAllUserWrites {
+    __block NSUInteger count = 0;
+    NSDate *start = [NSDate date];
+    id<APLevelDBWriteBatch> batch = [self.writesDB beginWriteBatch];
+    [self.writesDB enumerateKeys:^(NSString *key, BOOL *stop) {
+        [batch removeKey:key];
+        count++;
+    }];
+    BOOL success = [batch commit];
+    if (!success) {
+        FFWarn(@"I-RDB076010", @"Failed to remove all users writes on disk!");
+    } else {
+        FFDebug(@"I-RDB076011", @"Removed %lu writes in %fms", (unsigned long)count, [start timeIntervalSinceNow]*-1000);
+    }
+}
+
+- (NSArray *)userWrites {
+    NSDate *date = [NSDate date];
+    NSMutableArray *writes = [NSMutableArray array];
+    [self.writesDB enumerateKeysAndValuesAsData:^(NSString *key, NSData *data, BOOL *stop) {
+        NSError *error = nil;
+        NSDictionary *writeJSON = [NSJSONSerialization JSONObjectWithData:data options:0 error:&error];
+        if (writeJSON == nil) {
+            if (error.code == kFNanFailureCode) {
+                FFWarn(@"I-RDB076012", @"Failed to deserialize write (%@), likely because of out of range doubles (Error: %@)",
+                       [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding],
+                       error);
+                FFWarn(@"I-RDB076013", @"Removing failed write with key %@", key);
+                [self.writesDB removeKey:key];
+            } else {
+                [NSException raise:NSInternalInconsistencyException format:@"Failed to deserialize write: %@", error];
+            }
+        } else {
+            NSInteger writeId = ((NSNumber *)writeJSON[kFUserWriteId]).integerValue;
+            FPath *path = [FPath pathWithString:writeJSON[kFUserWritePath]];
+            FWriteRecord *writeRecord;
+            if (writeJSON[kFUserWriteMerge] != nil) {
+                // It's a merge
+                FCompoundWrite *merge = [FCompoundWrite compoundWriteWithValueDictionary:writeJSON[kFUserWriteMerge]];
+                writeRecord = [[FWriteRecord alloc] initWithPath:path merge:merge writeId:writeId];
+            } else {
+                // It's an overwrite
+                NSAssert(writeJSON[kFUserWriteOverwrite] != nil, @"Persisted write did not contain merge or overwrite!");
+                id<FNode> node = [FSnapshotUtilities nodeFrom:writeJSON[kFUserWriteOverwrite]];
+                writeRecord = [[FWriteRecord alloc] initWithPath:path overwrite:node writeId:writeId visible:YES];
+            }
+            [writes addObject:writeRecord];
+        }
+    }];
+    // Make sure writes are sorted
+    [writes sortUsingComparator:^NSComparisonResult(FWriteRecord *one, FWriteRecord *two) {
+        if (one.writeId < two.writeId) {
+            return NSOrderedAscending;
+        } else if (one.writeId > two.writeId) {
+            return NSOrderedDescending;
+        } else {
+            return NSOrderedSame;
+        }
+    }];
+    FFDebug(@"I-RDB076014", @"Loaded %lu writes in %fms", (unsigned long)writes.count, [date timeIntervalSinceNow]*-1000);
+    return writes;
+}
+
+- (id<FNode>)serverCacheAtPath:(FPath *)path {
+    NSDate *start = [NSDate date];
+    id data = [self internalNestedDataForPath:path];
+    id<FNode> node = [FSnapshotUtilities nodeFrom:data];
+    FFDebug(@"I-RDB076015", @"Loaded node with %d children at %@ in %fms", [node numChildren], path, [start timeIntervalSinceNow]*-1000);
+    return node;
+}
+
+- (id<FNode>)serverCacheForKeys:(NSSet *)keys atPath:(FPath *)path {
+    NSDate *start = [NSDate date];
+    __block id<FNode> node = [FEmptyNode emptyNode];
+    [keys enumerateObjectsUsingBlock:^(NSString *key, BOOL *stop) {
+        id data = [self internalNestedDataForPath:[path childFromString:key]];
+        node = [node updateImmediateChild:key withNewChild:[FSnapshotUtilities nodeFrom:data]];
+    }];
+    FFDebug(@"I-RDB076016", @"Loaded node with %d children for %lu keys at %@ in %fms", [node numChildren], (unsigned long)keys.count, path, [start timeIntervalSinceNow]*-1000);
+    return node;
+}
+
+- (void)updateServerCache:(id<FNode>)node atPath:(FPath *)path merge:(BOOL)merge {
+    NSDate *start = [NSDate date];
+    id<APLevelDBWriteBatch> batch = [self.serverCacheDB beginWriteBatch];
+    // Remove any leaf nodes that might be higher up
+    [self removeAllLeafNodesOnPath:path batch:batch];
+    __block NSUInteger counter = 0;
+    if (merge) {
+        // remove any children that exist
+        [node enumerateChildrenUsingBlock:^(NSString *childKey, id<FNode> childNode, BOOL *stop) {
+            FPath *childPath = [path childFromString:childKey];
+            [self removeAllWithPrefix:serverCacheKey(childPath) batch:batch database:self.serverCacheDB];
+            [self saveNodeInternal:childNode atPath:childPath batch:batch counter:&counter];
+        }];
+    } else {
+        // remove everything
+        [self removeAllWithPrefix:serverCacheKey(path) batch:batch database:self.serverCacheDB];
+        [self saveNodeInternal:node atPath:path batch:batch counter:&counter];
+    }
+    BOOL success = [batch commit];
+    if (!success) {
+        FFWarn(@"I-RDB076017", @"Failed to update server cache on disk!");
+    } else {
+        FFDebug(@"I-RDB076018", @"Saved %lu leaf nodes for overwrite in %fms", (unsigned long)counter, [start timeIntervalSinceNow]*-1000);
+    }
+}
+
+- (void)updateServerCacheWithMerge:(FCompoundWrite *)merge atPath:(FPath *)path {
+    NSDate *start = [NSDate date];
+    __block NSUInteger counter = 0;
+    id<APLevelDBWriteBatch> batch = [self.serverCacheDB beginWriteBatch];
+    // Remove any leaf nodes that might be higher up
+    [self removeAllLeafNodesOnPath:path batch:batch];
+    [merge enumerateWrites:^(FPath *relativePath, id<FNode> node, BOOL *stop) {
+        FPath *childPath = [path child:relativePath];
+        [self removeAllWithPrefix:serverCacheKey(childPath) batch:batch database:self.serverCacheDB];
+        [self saveNodeInternal:node atPath:childPath batch:batch counter:&counter];
+    }];
+    BOOL success = [batch commit];
+    if (!success) {
+        FFWarn(@"I-RDB076019", @"Failed to update server cache on disk!");
+    } else {
+        FFDebug(@"I-RDB076020", @"Saved %lu leaf nodes for merge in %fms", (unsigned long)counter, [start timeIntervalSinceNow]*-1000);
+    }
+}
+
+- (void)saveNodeInternal:(id<FNode>)node atPath:(FPath *)path batch:(id<APLevelDBWriteBatch>)batch counter:(NSUInteger *)counter {
+    id data = [node valForExport:YES];
+    if(data != nil && ![data isKindOfClass:[NSNull class]]) {
+        [self internalSetNestedData:data forKey:serverCacheKey(path) withBatch:batch counter:counter];
+    }
+}
+
+- (NSUInteger)serverCacheEstimatedSizeInBytes {
+    // Use the exact size, because for pruning the approximate size can lead to weird situations where we prune everything
+    // because no compaction is ever run
+    return [self.serverCacheDB exactSizeFrom:kFServerCachePrefix to:kFServerCacheRangeEnd];
+}
+
+- (void)pruneCache:(FPruneForest *)pruneForest atPath:(FPath *)path {
+    // TODO: be more intelligent, don't scan entire database...
+
+    __block NSUInteger pruned = 0;
+    __block NSUInteger kept = 0;
+    NSDate *start = [NSDate date];
+
+    NSString *prefix = serverCacheKey(path);
+    id<APLevelDBWriteBatch> batch = [self.serverCacheDB beginWriteBatch];
+
+    [self.serverCacheDB enumerateKeysWithPrefix:prefix usingBlock:^(NSString *dbKey, BOOL *stop) {
+        NSString *pathStr = [dbKey substringFromIndex:prefix.length];
+        FPath *relativePath = [[FPath alloc] initWith:pathStr];
+        if ([pruneForest shouldPruneUnkeptDescendantsAtPath:relativePath]) {
+            pruned++;
+            [batch removeKey:dbKey];
+        } else {
+            kept++;
+        }
+    }];
+    BOOL success = [batch commit];
+    if (!success) {
+        FFWarn(@"I-RDB076021", @"Failed to prune cache on disk!");
+    } else {
+        FFDebug(@"I-RDB076022", @"Pruned %lu paths, kept %lu paths in %fms", (unsigned long)pruned, (unsigned long)kept, [start timeIntervalSinceNow]*-1000);
+    }
+}
+
+#pragma mark - Tracked Queries
+
+- (NSArray *)loadTrackedQueries {
+    NSDate *date = [NSDate date];
+    NSMutableArray *trackedQueries = [NSMutableArray array];
+    [self.serverCacheDB enumerateKeysWithPrefix:kFTrackedQueriesPrefix asData:^(NSString *key, NSData *data, BOOL *stop) {
+        NSError *error = nil;
+        NSDictionary *queryJSON = [NSJSONSerialization JSONObjectWithData:data options:0 error:&error];
+        if (queryJSON == nil) {
+            if (error.code == kFNanFailureCode) {
+                FFWarn(@"I-RDB076023", @"Failed to deserialize tracked query (%@), likely because of out of range doubles (Error: %@)",
+                       [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding],
+                       error);
+                FFWarn(@"I-RDB076024", @"Removing failed tracked query with key %@", key);
+                [self.serverCacheDB removeKey:key];
+            } else {
+                [NSException raise:NSInternalInconsistencyException format:@"Failed to deserialize tracked query: %@", error];
+            }
+        } else {
+            NSUInteger queryId = ((NSNumber *)queryJSON[kFTrackedQueryId]).unsignedIntegerValue;
+            FPath *path = [FPath pathWithString:queryJSON[kFTrackedQueryPath]];
+            FQueryParams *params = [FQueryParams fromQueryObject:queryJSON[kFTrackedQueryParams]];
+            FQuerySpec *query = [[FQuerySpec alloc] initWithPath:path params:params];
+            BOOL isComplete = [queryJSON[kFTrackedQueryIsComplete] boolValue];
+            BOOL isActive = [queryJSON[kFTrackedQueryIsActive] boolValue];
+            NSTimeInterval lastUse = [queryJSON[kFTrackedQueryLastUse] doubleValue];
+
+            FTrackedQuery *trackedQuery = [[FTrackedQuery alloc] initWithId:queryId
+                                                                      query:query
+                                                                    lastUse:lastUse
+                                                                   isActive:isActive
+                                                                 isComplete:isComplete];
+
+            [trackedQueries addObject:trackedQuery];
+        }
+    }];
+    FFDebug(@"I-RDB076025", @"Loaded %lu tracked queries in %fms", (unsigned long)trackedQueries.count, [date timeIntervalSinceNow]*-1000);
+    return trackedQueries;
+}
+
+- (void)removeTrackedQuery:(NSUInteger)queryId {
+    NSDate *start = [NSDate date];
+    id<APLevelDBWriteBatch> batch = [self.serverCacheDB beginWriteBatch];
+    [batch removeKey:trackedQueryKey(queryId)];
+    __block NSUInteger keyCount = 0;
+    [self.serverCacheDB enumerateKeysWithPrefix:trackedQueryKeysKeyPrefix(queryId) usingBlock:^(NSString *key, BOOL *stop) {
+        [batch removeKey:key];
+        keyCount++;
+    }];
+
+    BOOL success = [batch commit];
+    if (!success) {
+        FFWarn(@"I-RDB076026", @"Failed to remove tracked query on disk!");
+    } else {
+        FFDebug(@"I-RDB076027", @"Removed query with id %lu (and removed %lu keys) in %fms",
+                (unsigned long)queryId,
+                (unsigned long)keyCount,
+                [start timeIntervalSinceNow]*-1000);
+    }
+}
+
+- (void)saveTrackedQuery:(FTrackedQuery *)query {
+    NSDate *start = [NSDate date];
+    NSDictionary *trackedQuery =
+    @{
+      kFTrackedQueryId: @(query.queryId),
+      kFTrackedQueryPath: [query.query.path toStringWithTrailingSlash],
+      kFTrackedQueryParams: [query.query.params wireProtocolParams],
+      kFTrackedQueryLastUse: @(query.lastUse),
+      kFTrackedQueryIsComplete: @(query.isComplete),
+      kFTrackedQueryIsActive: @(query.isActive)
+    };
+    NSError *error = nil;
+    NSData *data = [NSJSONSerialization dataWithJSONObject:trackedQuery options:0 error:&error];
+    NSAssert(data, @"Failed to serialize tracked query (Error: %@)", error);
+    [self.serverCacheDB setData:data forKey:trackedQueryKey(query.queryId)];
+    FFDebug(@"I-RDB076028", @"Saved tracked query %lu in %fms", (unsigned long)query.queryId, [start timeIntervalSinceNow]*-1000);
+}
+
+- (void)setTrackedQueryKeys:(NSSet *)keys forQueryId:(NSUInteger)queryId {
+    NSDate *start = [NSDate date];
+    __block NSUInteger removed = 0;
+    __block NSUInteger added = 0;
+    id<APLevelDBWriteBatch> batch = [self.serverCacheDB beginWriteBatch];
+    NSMutableSet *seenKeys = [NSMutableSet set];
+    // First, delete any keys that might be stored and are not part of the current keys
+    [self.serverCacheDB enumerateKeysWithPrefix:trackedQueryKeysKeyPrefix(queryId) asStrings:^(NSString *dbKey, NSString *actualKey, BOOL *stop) {
+        if ([keys containsObject:actualKey]) {
+            // Already in DB
+            [seenKeys addObject:actualKey];
+        } else {
+            // Not part of set, delete key
+            [batch removeKey:dbKey];
+            removed++;
+        }
+    }];
+
+    // Next add any keys that are missing in the database
+    [keys enumerateObjectsUsingBlock:^(NSString *childKey, BOOL *stop) {
+        if (![seenKeys containsObject:childKey]) {
+            [batch setString:childKey forKey:trackedQueryKeysKey(queryId, childKey)];
+            added++;
+        }
+    }];
+    BOOL success = [batch commit];
+    if (!success) {
+        FFWarn(@"I-RDB076029", @"Failed to set tracked queries on disk!");
+    } else {
+        FFDebug(@"I-RDB076030", @"Set %lu tracked keys (%lu added, %lu removed) for query %lu in %fms",
+                (unsigned long)keys.count,
+                (unsigned long)added,
+                (unsigned long)removed,
+                (unsigned long)queryId,
+                [start timeIntervalSinceNow]*-1000);
+    }
+}
+
+- (void)updateTrackedQueryKeysWithAddedKeys:(NSSet *)added removedKeys:(NSSet *)removed forQueryId:(NSUInteger)queryId {
+    NSDate *start = [NSDate date];
+    id<APLevelDBWriteBatch> batch = [self.serverCacheDB beginWriteBatch];
+    [removed enumerateObjectsUsingBlock:^(NSString *key, BOOL *stop) {
+        [batch removeKey:trackedQueryKeysKey(queryId, key)];
+    }];
+    [added enumerateObjectsUsingBlock:^(NSString *key, BOOL *stop) {
+        [batch setString:key forKey:trackedQueryKeysKey(queryId, key)];
+    }];
+    BOOL success = [batch commit];
+    if (!success) {
+        FFWarn(@"I-RDB076031", @"Failed to update tracked queries on disk!");
+    } else {
+        FFDebug(@"I-RDB076032", @"Added %lu tracked keys, removed %lu for query %lu in %fms", (unsigned long)added.count, (unsigned long)removed.count, (unsigned long)queryId, [start timeIntervalSinceNow]*-1000);
+    }
+}
+
+- (NSSet *)trackedQueryKeysForQuery:(NSUInteger)queryId {
+    NSDate *start = [NSDate date];
+    NSMutableSet *set = [NSMutableSet set];
+    [self.serverCacheDB enumerateKeysWithPrefix:trackedQueryKeysKeyPrefix(queryId) asStrings:^(NSString *dbKey, NSString *actualKey, BOOL *stop) {
+        [set addObject:actualKey];
+    }];
+    FFDebug(@"I-RDB076033", @"Loaded %lu tracked keys for query %lu in %fms", (unsigned long)set.count, (unsigned long)queryId, [start timeIntervalSinceNow]*-1000);
+    return set;
+}
+
+#pragma mark - Internal methods
+
+- (void)removeAllLeafNodesOnPath:(FPath *)path batch:(id<APLevelDBWriteBatch>)batch {
+    while (!path.isEmpty) {
+        [batch removeKey:serverCacheKey(path)];
+        path = [path parent];
+    }
+    // Make sure to delete any nodes at the root
+    [batch removeKey:serverCacheKey([FPath empty])];
+}
+
+- (void)removeAllWithPrefix:(NSString *)prefix batch:(id<APLevelDBWriteBatch>)batch database:(APLevelDB *)database {
+    assert(prefix != nil);
+
+    [database enumerateKeysWithPrefix:prefix usingBlock:^(NSString *key, BOOL *stop) {
+        [batch removeKey:key];
+    }];
+}
+
+#pragma mark - Internal helper methods
+
+- (void)internalSetNestedData:(id)value forKey:(NSString *)key withBatch:(id<APLevelDBWriteBatch>)batch counter:(NSUInteger *)counter {
+    if([value isKindOfClass:[NSDictionary class]]) {
+        NSDictionary* dictionary = value;
+        [dictionary enumerateKeysAndObjectsUsingBlock:^(id childKey, id obj, BOOL *stop) {
+            assert(obj != nil);
+            NSString* childPath = [NSString stringWithFormat:@"%@%@/", key, childKey];
+            [self internalSetNestedData:obj forKey:childPath withBatch:batch counter:counter];
+        }];
+    }
+    else {
+        NSData *data = [self serializePrimitive:value];
+        [batch setData:data forKey:key];
+        (*counter)++;
+    }
+}
+
+- (id)internalNestedDataForPath:(FPath *)path {
+    NSAssert(path != nil, @"Path was nil!");
+
+    NSString *baseKey = serverCacheKey(path);
+
+    // HACK to make sure iter is freed now to avoid race conditions (if self.db is deleted before iter, you get an access violation).
+    @autoreleasepool {
+        APLevelDBIterator* iter = [APLevelDBIterator iteratorWithLevelDB:self.serverCacheDB];
+
+        [iter seekToKey:baseKey];
+        if (iter.key == nil || ![iter.key hasPrefix:baseKey]) {
+            // No data.
+            return nil;
+        } else {
+            return [self internalNestedDataFromIterator:iter andKeyPrefix:baseKey];
+        }
+    }
+}
+
+- (id) internalNestedDataFromIterator:(APLevelDBIterator*)iterator andKeyPrefix:(NSString*)prefix {
+    NSString* key = iterator.key;
+
+    if ([key isEqualToString:prefix]) {
+        id result = [self deserializePrimitive:iterator.valueAsData];
+        [iterator nextKey];
+        return result;
+    } else {
+        NSMutableDictionary *dict = [[NSMutableDictionary alloc] init];
+        while (key != nil && [key hasPrefix:prefix]) {
+            NSString *relativePath = [key substringFromIndex:prefix.length];
+            NSArray* pathPieces = [relativePath componentsSeparatedByString:@"/"];
+            assert(pathPieces.count > 0);
+            NSString *childName = pathPieces[0];
+            NSString *childPath = [NSString stringWithFormat:@"%@%@/", prefix, childName];
+            id childValue = [self internalNestedDataFromIterator:iterator andKeyPrefix:childPath];
+            [dict setValue:childValue forKey:childName];
+
+            key = iterator.key;
+        }
+        return dict;
+    }
+}
+
+
+- (NSData*) serializePrimitive:(id)value {
+    // HACK: The built-in serialization only works on dicts and arrays.  So we create an array and then strip off
+    // the leading / trailing byte (the [ and ]).
+    NSError *error = nil;
+    NSData *data = [NSJSONSerialization dataWithJSONObject:@[value] options:0 error:&error];
+    NSAssert(data, @"Failed to serialize primitive: %@", error);
+
+    return [data subdataWithRange:NSMakeRange(1, data.length - 2)];
+}
+
+- (id)fixDoubleParsing:(id)value {
+    // The parser for double values in JSONSerialization at the root takes some short-cuts and delivers wrong results
+    // (wrong rounding) for some double values, including 2.47. Because we use the exact bytes for hashing on the server
+    // this will lead to hash mismatches. The parser of NSNumber seems to be more in line with what the server expects,
+    // so we use that here
+    if ([value isKindOfClass:[NSNumber class]]) {
+        CFNumberType type = CFNumberGetType((CFNumberRef)value);
+        if (type == kCFNumberDoubleType || type == kCFNumberFloatType) {
+            // The NSJSON parser returns all numbers as double values, even those that contain no exponent. To
+            // make sure that the String conversion below doesn't unexpectedly reduce precision, we make sure that
+            // our number is indeed not an integer.
+            if ((double)(long long)[value doubleValue] != [value doubleValue]) {
+                NSString *doubleString = [value stringValue];
+                return [NSNumber numberWithDouble:[doubleString doubleValue]];
+            }
+        }
+    }
+    return value;
+}
+
+- (id) deserializePrimitive:(NSData*)data {
+    NSError *error = nil;
+    id result = [NSJSONSerialization JSONObjectWithData:data options:NSJSONReadingAllowFragments error:&error];
+    if (result != nil) {
+        return [self fixDoubleParsing:result];
+    } else {
+        if (error.code == kFNanFailureCode) {
+            FFWarn(@"I-RDB076034", @"Failed to load primitive %@, likely because doubles where out of range (Error: %@)",
+                   [[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding], error);
+            return [NSNull null];
+        } else {
+            [NSException raise:NSInternalInconsistencyException format:@"Failed to deserialiaze primitive: %@", error];
+            return nil;
+        }
+    }
+
+}
+
++ (void)ensureDir:(NSString*)path markAsDoNotBackup:(BOOL)markAsDoNotBackup {
+    NSError* error;
+    BOOL success = [[NSFileManager defaultManager] createDirectoryAtPath:path
+                                             withIntermediateDirectories:YES
+                                                              attributes:nil
+                                                                   error:&error];
+    if (!success) {
+        @throw [NSException exceptionWithName:@"FailedToCreatePersistenceDir" reason:@"Failed to create persistence directory." userInfo:@{ @"path": path }];
+    }
+
+    if (markAsDoNotBackup) {
+        NSURL *firebaseDirURL = [NSURL fileURLWithPath:path];
+        success = [firebaseDirURL setResourceValue:@YES
+                                            forKey:NSURLIsExcludedFromBackupKey
+                                             error:&error];
+        if (!success) {
+            FFWarn(@"I-RDB076035", @"Failed to mark firebase database folder as do not backup: %@", error);
+            [NSException raise:@"Error marking as do not backup" format:@"Failed to mark folder %@ as do not backup", firebaseDirURL];
+        }
+    }
+}
+
+
+@end
diff --git a/Firebase/Database/Persistence/FPendingPut.h b/Firebase/Database/Persistence/FPendingPut.h
new file mode 100644
index 0000000..0d8de55
--- /dev/null
+++ b/Firebase/Database/Persistence/FPendingPut.h
@@ -0,0 +1,55 @@
+/*
+ * 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 "FPath.h"
+
+// These are all legacy classes and are used to migrate older persistence data base to newer ones
+// These classes should not be used in newer code
+
+@interface FPendingPut : NSObject<NSCoding>
+
+@property (nonatomic, strong) FPath* path;
+@property (nonatomic, strong) id data;
+@property (nonatomic, strong) id priority;
+
+- (id) initWithPath:(FPath*)aPath andData:(id)aData andPriority:aPriority;
+- (void)encodeWithCoder:(NSCoder *)aCoder;
+- (id)initWithCoder:(NSCoder *)aDecoder;
+@end
+
+
+@interface FPendingPutPriority : NSObject<NSCoding>
+
+@property (nonatomic, strong) FPath* path;
+@property (nonatomic, strong) id priority;
+
+- (id) initWithPath:(FPath*)aPath andPriority:(id)aPriority;
+- (void)encodeWithCoder:(NSCoder *)aCoder;
+- (id)initWithCoder:(NSCoder *)aDecoder;
+
+@end
+
+
+@interface FPendingUpdate : NSObject<NSCoding>
+
+@property (nonatomic, strong) FPath* path;
+@property (nonatomic, strong) NSDictionary* data;
+
+- (id) initWithPath:(FPath*)aPath andData:(NSDictionary*)aData;
+- (void)encodeWithCoder:(NSCoder *)aCoder;
+- (id)initWithCoder:(NSCoder *)aDecoder;
+@end
diff --git a/Firebase/Database/Persistence/FPendingPut.m b/Firebase/Database/Persistence/FPendingPut.m
new file mode 100644
index 0000000..12be825
--- /dev/null
+++ b/Firebase/Database/Persistence/FPendingPut.m
@@ -0,0 +1,112 @@
+/*
+ * 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 "FPendingPut.h"
+
+@implementation FPendingPut
+
+@synthesize path;
+@synthesize data;
+
+- (id) initWithPath:(FPath *)aPath andData:(id)aData andPriority:(id)aPriority {
+    self = [super init];
+    if (self) {
+        self.path = aPath;
+        self.data = aData;
+        self.priority = aPriority;
+    }
+    return self;
+}
+
+- (void)encodeWithCoder:(NSCoder *)aCoder {
+    [aCoder encodeObject:[self.path description] forKey:@"path"];
+    [aCoder encodeObject:self.data forKey:@"data"];
+    [aCoder encodeObject:self.priority forKey:@"priority"];
+}
+
+- (id)initWithCoder:(NSCoder *)aDecoder {
+    self = [super init];
+    if(self) {
+        self.path = [[FPath alloc] initWith:[aDecoder decodeObjectForKey:@"path"]];
+        self.data = [aDecoder decodeObjectForKey:@"data"];
+        self.priority = [aDecoder decodeObjectForKey:@"priority"];
+    }
+    return self;
+}
+
+@end
+
+
+@implementation FPendingPutPriority
+
+@synthesize path;
+@synthesize priority;
+
+- (id) initWithPath:(FPath *)aPath andPriority:(id)aPriority {
+    self = [super init];
+    if (self) {
+        self.path = aPath;
+        self.priority = aPriority;
+    }
+    return self;
+}
+
+- (void)encodeWithCoder:(NSCoder *)aCoder {
+    [aCoder encodeObject:[self.path description] forKey:@"path"];
+    [aCoder encodeObject:self.priority forKey:@"priority"];
+}
+
+- (id)initWithCoder:(NSCoder *)aDecoder {
+    self = [super init];
+    if(self) {
+        self.path = [[FPath alloc] initWith:[aDecoder decodeObjectForKey:@"path"]];
+        self.priority = [aDecoder decodeObjectForKey:@"priority"];
+    }
+    return self;
+}
+
+@end
+
+
+@implementation FPendingUpdate
+
+@synthesize path;
+@synthesize data;
+
+- (id) initWithPath:(FPath *)aPath andData:(id)aData {
+    self = [super init];
+    if (self) {
+        self.path = aPath;
+        self.data = aData;
+    }
+    return self;
+}
+
+- (void)encodeWithCoder:(NSCoder *)aCoder {
+    [aCoder encodeObject:[self.path description] forKey:@"path"];
+    [aCoder encodeObject:self.data forKey:@"data"];
+}
+
+- (id)initWithCoder:(NSCoder *)aDecoder {
+    self = [super init];
+    if(self) {
+        self.path = [[FPath alloc] initWith:[aDecoder decodeObjectForKey:@"path"]];
+        self.data = [aDecoder decodeObjectForKey:@"data"];
+    }
+    return self;
+}
+
+@end
diff --git a/Firebase/Database/Persistence/FPersistenceManager.h b/Firebase/Database/Persistence/FPersistenceManager.h
new file mode 100644
index 0000000..a3688b3
--- /dev/null
+++ b/Firebase/Database/Persistence/FPersistenceManager.h
@@ -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 <Foundation/Foundation.h>
+
+#import "FNode.h"
+#import "FCompoundWrite.h"
+#import "FQuerySpec.h"
+#import "FRepoInfo.h"
+#import "FStorageEngine.h"
+#import "FCachePolicy.h"
+#import "FCacheNode.h"
+
+@interface FPersistenceManager : NSObject
+
+- (id)initWithStorageEngine:(id<FStorageEngine>)storageEngine cachePolicy:(id<FCachePolicy>)cachePolicy;
+- (void)close;
+
+- (void)saveUserOverwrite:(id<FNode>)node atPath:(FPath *)path writeId:(NSUInteger)writeId;
+- (void)saveUserMerge:(FCompoundWrite *)merge atPath:(FPath *)path writeId:(NSUInteger)writeId;
+- (void)removeUserWrite:(NSUInteger)writeId;
+- (void)removeAllUserWrites;
+- (NSArray *)userWrites;
+
+- (FCacheNode *)serverCacheForQuery:(FQuerySpec *)spec;
+- (void)updateServerCacheWithNode:(id<FNode>)node forQuery:(FQuerySpec *)spec;
+- (void)updateServerCacheWithMerge:(FCompoundWrite *)merge atPath:(FPath *)path;
+
+- (void)applyUserWrite:(id<FNode>)write toServerCacheAtPath:(FPath *)path;
+- (void)applyUserMerge:(FCompoundWrite *)merge toServerCacheAtPath:(FPath *)path;
+
+- (void)setQueryComplete:(FQuerySpec *)spec;
+- (void)setQueryActive:(FQuerySpec *)spec;
+- (void)setQueryInactive:(FQuerySpec *)spec;
+
+- (void)setTrackedQueryKeys:(NSSet *)keys forQuery:(FQuerySpec *)query;
+- (void)updateTrackedQueryKeysWithAddedKeys:(NSSet *)added removedKeys:(NSSet *)removed forQuery:(FQuerySpec *)query;
+
+@end
diff --git a/Firebase/Database/Persistence/FPersistenceManager.m b/Firebase/Database/Persistence/FPersistenceManager.m
new file mode 100644
index 0000000..fb38192
--- /dev/null
+++ b/Firebase/Database/Persistence/FPersistenceManager.m
@@ -0,0 +1,190 @@
+/*
+ * 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 "FPersistenceManager.h"
+#import "FLevelDBStorageEngine.h"
+#import "FCacheNode.h"
+#import "FIndexedNode.h"
+#import "FTrackedQueryManager.h"
+#import "FTrackedQuery.h"
+#import "FUtilities.h"
+#import "FPruneForest.h"
+#import "FClock.h"
+
+@interface FPersistenceManager ()
+
+@property (nonatomic, strong) id<FStorageEngine> storageEngine;
+@property (nonatomic, strong) id<FCachePolicy> cachePolicy;
+@property (nonatomic, strong) FTrackedQueryManager *trackedQueryManager;
+@property (nonatomic) NSUInteger serverCacheUpdatesSinceLastPruneCheck;
+
+@end
+
+@implementation FPersistenceManager
+
+- (id)initWithStorageEngine:(id<FStorageEngine>)storageEngine cachePolicy:(id<FCachePolicy>)cachePolicy {
+    self = [super init];
+    if (self != nil) {
+        self->_storageEngine = storageEngine;
+        self->_cachePolicy = cachePolicy;
+        self->_trackedQueryManager = [[FTrackedQueryManager alloc] initWithStorageEngine:self.storageEngine
+                                                                                   clock:[FSystemClock clock]];
+    }
+    return self;
+}
+
+- (void)close {
+    [self.storageEngine close];
+    self.storageEngine = nil;
+    self.trackedQueryManager = nil;
+}
+
+- (void)saveUserOverwrite:(id<FNode>)node atPath:(FPath *)path writeId:(NSUInteger)writeId {
+    [self.storageEngine saveUserOverwrite:node atPath:path writeId:writeId];
+}
+
+- (void)saveUserMerge:(FCompoundWrite *)merge atPath:(FPath *)path writeId:(NSUInteger)writeId {
+    [self.storageEngine saveUserMerge:merge atPath:path writeId:writeId];
+}
+
+- (void)removeUserWrite:(NSUInteger)writeId {
+    [self.storageEngine removeUserWrite:writeId];
+}
+
+- (void)removeAllUserWrites {
+    [self.storageEngine removeAllUserWrites];
+}
+
+- (NSArray *)userWrites {
+    return [self.storageEngine userWrites];
+}
+
+- (FCacheNode *)serverCacheForQuery:(FQuerySpec *)query {
+    NSSet *trackedKeys;
+    BOOL complete;
+    // TODO[offline]: Should we use trackedKeys to find out if this location is a child of a complete query?
+    if ([self.trackedQueryManager isQueryComplete:query]) {
+        complete = YES;
+        FTrackedQuery *trackedQuery = [self.trackedQueryManager findTrackedQuery:query];
+        if (!query.loadsAllData && trackedQuery.isComplete) {
+            trackedKeys = [self.storageEngine trackedQueryKeysForQuery:trackedQuery.queryId];
+        } else {
+            trackedKeys = nil;
+        }
+    } else {
+        complete = NO;
+        trackedKeys = [self.trackedQueryManager knownCompleteChildrenAtPath:query.path];
+    }
+
+    id<FNode> node;
+    if (trackedKeys != nil) {
+        node = [self.storageEngine serverCacheForKeys:trackedKeys atPath:query.path];
+    } else {
+        node = [self.storageEngine serverCacheAtPath:query.path];
+    }
+
+    FIndexedNode *indexedNode = [FIndexedNode indexedNodeWithNode:node index:query.index];
+    return [[FCacheNode alloc] initWithIndexedNode:indexedNode isFullyInitialized:complete isFiltered:(trackedKeys != nil)];
+}
+
+- (void)updateServerCacheWithNode:(id<FNode>)node forQuery:(FQuerySpec *)query {
+    BOOL merge = !query.loadsAllData;
+    [self.storageEngine updateServerCache:node atPath:query.path merge:merge];
+    [self setQueryComplete:query];
+    [self doPruneCheckAfterServerUpdate];
+}
+
+- (void)updateServerCacheWithMerge:(FCompoundWrite *)merge atPath:(FPath *)path {
+    [self.storageEngine updateServerCacheWithMerge:merge atPath:path];
+    [self doPruneCheckAfterServerUpdate];
+}
+
+- (void)applyUserMerge:(FCompoundWrite *)merge toServerCacheAtPath:(FPath *)path {
+    // TODO[offline]: rework this to be more efficient
+    [merge enumerateWrites:^(FPath *relativePath, id<FNode> node, BOOL *stop) {
+        [self applyUserWrite:node toServerCacheAtPath:[path child:relativePath]];
+    }];
+}
+
+- (void)applyUserWrite:(id<FNode>)write toServerCacheAtPath:(FPath *)path {
+    // This is a hack to guess whether we already cached this because we got a server data update for this
+    // write via an existing active default query.  If we didn't, then we'll manually cache this and add a
+    // tracked query to mark it complete and keep it cached.
+    // Unfortunately this is just a guess and it's possible that we *did* get an update (e.g. via a filtered
+    // query) and by overwriting the cache here, we'll actually store an incorrect value (e.g. in the case
+    // that we wrote a ServerValue.TIMESTAMP and the server resolved it to a different value).
+    // TODO[offline]: Consider reworking.
+    if (![self.trackedQueryManager hasActiveDefaultQueryAtPath:path]) {
+        [self.storageEngine updateServerCache:write atPath:path merge:NO];
+        [self.trackedQueryManager ensureCompleteTrackedQueryAtPath:path];
+    }
+}
+
+- (void)setQueryComplete:(FQuerySpec *)query {
+    if (query.loadsAllData) {
+        [self.trackedQueryManager setQueriesCompleteAtPath:query.path];
+    } else {
+        [self.trackedQueryManager setQueryComplete:query];
+    }
+}
+
+- (void)setQueryActive:(FQuerySpec *)spec {
+    [self.trackedQueryManager setQueryActive:spec];
+}
+
+- (void)setQueryInactive:(FQuerySpec *)spec {
+    [self.trackedQueryManager setQueryInactive:spec];
+}
+
+- (void)doPruneCheckAfterServerUpdate {
+    self.serverCacheUpdatesSinceLastPruneCheck++;
+    if ([self.cachePolicy shouldCheckCacheSize:self.serverCacheUpdatesSinceLastPruneCheck]) {
+        FFDebug(@"I-RDB078001", @"Reached prune check threshold. Checking...");
+        NSDate *date = [NSDate date];
+        self.serverCacheUpdatesSinceLastPruneCheck = 0;
+        BOOL canPrune = YES;
+        NSUInteger cacheSize = [self.storageEngine serverCacheEstimatedSizeInBytes];
+        FFDebug(@"I-RDB078002", @"Server cache size: %lu", (unsigned long)cacheSize);
+        while (canPrune && [self.cachePolicy shouldPruneCacheWithSize:cacheSize
+                                               numberOfTrackedQueries:self.trackedQueryManager.numberOfPrunableQueries]) {
+            FPruneForest *pruneForest = [self.trackedQueryManager pruneOldQueries:self.cachePolicy];
+            if (pruneForest.prunesAnything) {
+                [self.storageEngine pruneCache:pruneForest atPath:[FPath empty]];
+            } else {
+                canPrune = NO;
+            }
+            cacheSize = [self.storageEngine serverCacheEstimatedSizeInBytes];
+            FFDebug(@"I-RDB078003", @"Cache size after pruning: %lu", (unsigned long)cacheSize);
+        }
+        FFDebug(@"I-RDB078004", @"Pruning round took %fms", [date timeIntervalSinceNow]*-1000);
+    }
+}
+
+- (void)setTrackedQueryKeys:(NSSet *)keys forQuery:(FQuerySpec *)query {
+    NSAssert(!query.loadsAllData, @"We should only track keys for filtered queries");
+    FTrackedQuery *trackedQuery = [self.trackedQueryManager findTrackedQuery:query];
+    NSAssert(trackedQuery.isActive, @"We only expect tracked keys for currently-active queries.");
+    [self.storageEngine setTrackedQueryKeys:keys forQueryId:trackedQuery.queryId];
+}
+
+- (void)updateTrackedQueryKeysWithAddedKeys:(NSSet *)added removedKeys:(NSSet *)removed forQuery:(FQuerySpec *)query {
+    NSAssert(!query.loadsAllData, @"We should only track keys for filtered queries");
+    FTrackedQuery *trackedQuery = [self.trackedQueryManager findTrackedQuery:query];
+    NSAssert(trackedQuery.isActive, @"We only expect tracked keys for currently-active queries.");
+    [self.storageEngine updateTrackedQueryKeysWithAddedKeys:added removedKeys:removed forQueryId:trackedQuery.queryId];
+}
+
+@end
diff --git a/Firebase/Database/Persistence/FPruneForest.h b/Firebase/Database/Persistence/FPruneForest.h
new file mode 100644
index 0000000..9e77217
--- /dev/null
+++ b/Firebase/Database/Persistence/FPruneForest.h
@@ -0,0 +1,38 @@
+/*
+ * 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 FPath;
+
+@interface FPruneForest : NSObject
+
++ (FPruneForest *)empty;
+
+- (BOOL)prunesAnything;
+- (BOOL)shouldPruneUnkeptDescendantsAtPath:(FPath *)path;
+- (BOOL)shouldKeepPath:(FPath *)path;
+- (BOOL)affectsPath:(FPath *)path;
+- (FPruneForest *)child:(NSString *)childKey;
+- (FPruneForest *)childAtPath:(FPath *)childKey;
+- (FPruneForest *)prunePath:(FPath *)path;
+- (FPruneForest *)keepPath:(FPath *)path;
+- (FPruneForest *)keepAll:(NSSet *)children atPath:(FPath *)path;
+- (FPruneForest *)pruneAll:(NSSet *)children atPath:(FPath *)path;
+
+- (void)enumarateKeptNodesUsingBlock:(void (^)(FPath *path))block;
+
+@end
diff --git a/Firebase/Database/Persistence/FPruneForest.m b/Firebase/Database/Persistence/FPruneForest.m
new file mode 100644
index 0000000..3dae6d8
--- /dev/null
+++ b/Firebase/Database/Persistence/FPruneForest.m
@@ -0,0 +1,177 @@
+/*
+ * 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 "FPruneForest.h"
+
+#import "FImmutableTree.h"
+
+@interface FPruneForest ()
+
+@property (nonatomic, strong) FImmutableTree *pruneForest;
+
+@end
+
+@implementation FPruneForest
+
+static BOOL (^kFPrunePredicate)(id) = ^BOOL(NSNumber *pruneValue) {
+    return [pruneValue boolValue];
+};
+
+static BOOL (^kFKeepPredicate)(id) = ^BOOL(NSNumber *pruneValue) {
+    return ![pruneValue boolValue];
+};
+
+
++ (FImmutableTree *)pruneTree {
+    static dispatch_once_t onceToken;
+    static FImmutableTree *pruneTree;
+    dispatch_once(&onceToken, ^{
+        pruneTree = [[FImmutableTree alloc] initWithValue:@YES];
+    });
+    return pruneTree;
+}
+
++ (FImmutableTree *)keepTree {
+    static dispatch_once_t onceToken;
+    static FImmutableTree *keepTree;
+    dispatch_once(&onceToken, ^{
+        keepTree = [[FImmutableTree alloc] initWithValue:@NO];
+    });
+    return keepTree;
+}
+
+- (id) initWithForest:(FImmutableTree *)tree {
+    self = [super init];
+    if (self != nil) {
+        self->_pruneForest = tree;
+    }
+    return self;
+}
+
++ (FPruneForest *)empty {
+    static dispatch_once_t onceToken;
+    static FPruneForest *forest;
+    dispatch_once(&onceToken, ^{
+        forest = [[FPruneForest alloc] initWithForest:[FImmutableTree empty]];
+    });
+    return forest;
+}
+
+- (BOOL)prunesAnything {
+    return [self.pruneForest containsValueMatching:kFPrunePredicate];
+}
+
+- (BOOL)shouldPruneUnkeptDescendantsAtPath:(FPath *)path {
+    NSNumber *shouldPrune = [self.pruneForest leafMostValueOnPath:path];
+    return shouldPrune != nil && [shouldPrune boolValue];
+}
+
+- (BOOL)shouldKeepPath:(FPath *)path {
+    NSNumber *shouldPrune = [self.pruneForest leafMostValueOnPath:path];
+    return shouldPrune != nil && ![shouldPrune boolValue];
+}
+
+- (BOOL)affectsPath:(FPath *)path {
+    return [self.pruneForest rootMostValueOnPath:path] != nil || ![[self.pruneForest subtreeAtPath:path] isEmpty];
+}
+
+- (FPruneForest *)child:(NSString *)childKey {
+    FImmutableTree *childPruneForest = [self.pruneForest.children get:childKey];
+    if (childPruneForest == nil) {
+        if (self.pruneForest.value != nil) {
+            childPruneForest = [self.pruneForest.value boolValue] ? [FPruneForest pruneTree] : [FPruneForest keepTree];
+        } else {
+            childPruneForest = [FImmutableTree empty];
+        }
+    } else {
+        if (childPruneForest.value == nil && self.pruneForest.value != nil) {
+            childPruneForest = [childPruneForest setValue:self.pruneForest.value atPath:[FPath empty]];
+        }
+    }
+    return [[FPruneForest alloc] initWithForest:childPruneForest];
+}
+
+- (FPruneForest *)childAtPath:(FPath *)path {
+    if (path.isEmpty) {
+        return self;
+    } else {
+        return [[self child:path.getFront] childAtPath:[path popFront]];
+    }
+}
+
+- (FPruneForest *)prunePath:(FPath *)path {
+    if ([self.pruneForest rootMostValueOnPath:path matching:kFKeepPredicate]) {
+        [NSException raise:NSInvalidArgumentException format:@"Can't prune path that was kept previously!"];
+    }
+    if ([self.pruneForest rootMostValueOnPath:path matching:kFPrunePredicate]) {
+        // This path will already be pruned
+        return self;
+    } else {
+        FImmutableTree *newPruneForest = [self.pruneForest setTree:[FPruneForest pruneTree] atPath:path];
+        return [[FPruneForest alloc] initWithForest:newPruneForest];
+    }
+}
+
+- (FPruneForest *)keepPath:(FPath *)path {
+    if ([self.pruneForest rootMostValueOnPath:path matching:kFKeepPredicate]) {
+        // This path will already be kept
+        return self;
+    } else {
+        FImmutableTree *newPruneForest = [self.pruneForest setTree:[FPruneForest keepTree] atPath:path];
+        return [[FPruneForest alloc] initWithForest:newPruneForest];
+    }
+}
+
+- (FPruneForest *)keepAll:(NSSet *)children atPath:(FPath *)path {
+    if ([self.pruneForest rootMostValueOnPath:path matching:kFKeepPredicate]) {
+        // This path will already be kept
+        return self;
+    } else {
+        return [self setPruneValue:[FPruneForest keepTree] forAll:children atPath:path];
+    }
+}
+
+- (FPruneForest *)pruneAll:(NSSet *)children atPath:(FPath *)path {
+    if ([self.pruneForest rootMostValueOnPath:path matching:kFKeepPredicate]) {
+        [NSException raise:NSInvalidArgumentException format:@"Can't prune path that was kept previously!"];
+    }
+    if ([self.pruneForest rootMostValueOnPath:path matching:kFPrunePredicate]) {
+        // This path will already be kept
+        return self;
+    } else {
+        return [self setPruneValue:[FPruneForest pruneTree] forAll:children atPath:path];
+    }
+}
+
+- (FPruneForest *)setPruneValue:(FImmutableTree *)pruneValue forAll:(NSSet *)children atPath:(FPath *)path {
+    FImmutableTree *subtree = [self.pruneForest subtreeAtPath:path];
+    __block FImmutableSortedDictionary *childrenDictionary = subtree.children;
+    [children enumerateObjectsUsingBlock:^(NSString *childKey, BOOL *stop) {
+        childrenDictionary = [childrenDictionary insertKey:childKey withValue:pruneValue];
+    }];
+    FImmutableTree *newSubtree = [[FImmutableTree alloc] initWithValue:subtree.value children:childrenDictionary];
+    return [[FPruneForest alloc] initWithForest:[self.pruneForest setTree:newSubtree atPath:path]];
+}
+
+- (void)enumarateKeptNodesUsingBlock:(void (^)(FPath *))block {
+    [self.pruneForest forEach:^(FPath *path, id value) {
+        if (value != nil && ![value boolValue]) {
+            block(path);
+        }
+    }];
+}
+
+@end
diff --git a/Firebase/Database/Persistence/FStorageEngine.h b/Firebase/Database/Persistence/FStorageEngine.h
new file mode 100644
index 0000000..4f168e7
--- /dev/null
+++ b/Firebase/Database/Persistence/FStorageEngine.h
@@ -0,0 +1,53 @@
+/*
+ * 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>
+
+@protocol FNode;
+@class FPruneForest;
+@class FPath;
+@class FCompoundWrite;
+@class FQuerySpec;
+@class FTrackedQuery;
+
+@protocol FStorageEngine <NSObject>
+
+- (void)close;
+
+- (void)saveUserOverwrite:(id<FNode>)node atPath:(FPath *)path writeId:(NSUInteger)writeId;
+- (void)saveUserMerge:(FCompoundWrite *)merge atPath:(FPath *)path writeId:(NSUInteger)writeId;
+- (void)removeUserWrite:(NSUInteger)writeId;
+- (void)removeAllUserWrites;
+- (NSArray *)userWrites;
+
+- (id<FNode>)serverCacheAtPath:(FPath *)path;
+- (id<FNode>)serverCacheForKeys:(NSSet *)keys atPath:(FPath *)path;
+- (void)updateServerCache:(id<FNode>)node atPath:(FPath *)path merge:(BOOL)merge;
+- (void)updateServerCacheWithMerge:(FCompoundWrite *)merge atPath:(FPath *)path;
+- (NSUInteger)serverCacheEstimatedSizeInBytes;
+
+- (void)pruneCache:(FPruneForest *)pruneForest atPath:(FPath *)path;
+
+- (NSArray *)loadTrackedQueries;
+- (void)removeTrackedQuery:(NSUInteger)queryId;
+- (void)saveTrackedQuery:(FTrackedQuery *)query;
+
+- (void)setTrackedQueryKeys:(NSSet *)keys forQueryId:(NSUInteger)queryId;
+- (void)updateTrackedQueryKeysWithAddedKeys:(NSSet *)added removedKeys:(NSSet *)removed forQueryId:(NSUInteger)queryId;
+- (NSSet *)trackedQueryKeysForQuery:(NSUInteger)queryId;
+
+
+@end
diff --git a/Firebase/Database/Persistence/FTrackedQuery.h b/Firebase/Database/Persistence/FTrackedQuery.h
new file mode 100644
index 0000000..7bc8ef1
--- /dev/null
+++ b/Firebase/Database/Persistence/FTrackedQuery.h
@@ -0,0 +1,40 @@
+/*
+ * 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 FQuerySpec;
+
+@interface FTrackedQuery : NSObject
+
+@property (nonatomic, readonly) NSUInteger queryId;
+@property (nonatomic, strong, readonly) FQuerySpec *query;
+@property (nonatomic, readonly) NSTimeInterval lastUse;
+@property (nonatomic, readonly) BOOL isComplete;
+@property (nonatomic, readonly) BOOL isActive;
+
+- (id)initWithId:(NSUInteger)queryId query:(FQuerySpec *)query lastUse:(NSTimeInterval)lastUse isActive:(BOOL)isActive;
+- (id)initWithId:(NSUInteger)queryId
+           query:(FQuerySpec *)query
+         lastUse:(NSTimeInterval)lastUse
+        isActive:(BOOL)isActive
+      isComplete:(BOOL)isComplete;
+
+- (FTrackedQuery *)updateLastUse:(NSTimeInterval)lastUse;
+- (FTrackedQuery *)setComplete;
+- (FTrackedQuery *)setActiveState:(BOOL)isActive;
+
+@end
diff --git a/Firebase/Database/Persistence/FTrackedQuery.m b/Firebase/Database/Persistence/FTrackedQuery.m
new file mode 100644
index 0000000..1720805
--- /dev/null
+++ b/Firebase/Database/Persistence/FTrackedQuery.m
@@ -0,0 +1,102 @@
+/*
+ * 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 "FTrackedQuery.h"
+
+#import "FQuerySpec.h"
+
+@interface FTrackedQuery ()
+
+@property (nonatomic, readwrite) NSUInteger queryId;
+@property (nonatomic, strong, readwrite) FQuerySpec *query;
+@property (nonatomic, readwrite) NSTimeInterval lastUse;
+@property (nonatomic, readwrite) BOOL isComplete;
+@property (nonatomic, readwrite) BOOL isActive;
+
+@end
+
+
+@implementation FTrackedQuery
+
+- (id)initWithId:(NSUInteger)queryId
+           query:(FQuerySpec *)query
+         lastUse:(NSTimeInterval)lastUse
+        isActive:(BOOL)isActive
+      isComplete:(BOOL)isComplete {
+    self = [super init];
+    if (self != nil) {
+        self->_queryId = queryId;
+        self->_query = query;
+        self->_lastUse = lastUse;
+        self->_isComplete = isComplete;
+        self->_isActive = isActive;
+    }
+    return self;
+}
+
+- (id)initWithId:(NSUInteger)queryId query:(FQuerySpec *)query lastUse:(NSTimeInterval)lastUse isActive:(BOOL)isActive {
+    return [self initWithId:queryId query:query lastUse:lastUse isActive:isActive isComplete:NO];
+}
+
+- (FTrackedQuery *)updateLastUse:(NSTimeInterval)lastUse {
+    return [[FTrackedQuery alloc] initWithId:self.queryId
+                                       query:self.query
+                                     lastUse:lastUse
+                                    isActive:self.isActive
+                                  isComplete:self.isComplete];
+}
+
+- (FTrackedQuery *)setComplete {
+    return [[FTrackedQuery alloc] initWithId:self.queryId
+                                       query:self.query
+                                     lastUse:self.lastUse
+                                    isActive:self.isActive
+                                  isComplete:YES];
+}
+
+- (FTrackedQuery *)setActiveState:(BOOL)isActive {
+    return [[FTrackedQuery alloc] initWithId:self.queryId
+                                       query:self.query
+                                     lastUse:self.lastUse
+                                    isActive:isActive
+                                  isComplete:self.isComplete];
+}
+
+- (BOOL)isEqual:(id)object {
+    if (![object isKindOfClass:[FTrackedQuery class]]) {
+        return NO;
+    }
+    FTrackedQuery *other = (FTrackedQuery *)object;
+    if (self.queryId != other.queryId) return NO;
+    if (self.query != other.query && ![self.query isEqual:other.query]) return NO;
+    if (self.lastUse != other.lastUse) return NO;
+    if (self.isComplete != other.isComplete) return NO;
+    if (self.isActive != other.isActive) return NO;
+
+    return YES;
+}
+
+- (NSUInteger)hash {
+    NSUInteger hash = self.queryId;
+    hash = hash * 31 + self.query.hash;
+    hash = hash * 31 + (self.isActive ? 1 : 0);
+    hash = hash * 31 + (NSUInteger)self.lastUse;
+    hash = hash * 31 + (self.isComplete ? 1 : 0);
+    hash = hash * 31 + (self.isActive ? 1 : 0);
+    return hash;
+}
+
+@end
diff --git a/Firebase/Database/Persistence/FTrackedQueryManager.h b/Firebase/Database/Persistence/FTrackedQueryManager.h
new file mode 100644
index 0000000..ba2631b
--- /dev/null
+++ b/Firebase/Database/Persistence/FTrackedQueryManager.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>
+
+@protocol FStorageEngine;
+@protocol FClock;
+@protocol FCachePolicy;
+@class FQuerySpec;
+@class FPath;
+@class FTrackedQuery;
+@class FPruneForest;
+
+@interface FTrackedQueryManager : NSObject
+
+- (id)initWithStorageEngine:(id<FStorageEngine>)storageEngine clock:(id<FClock>)clock;
+
+- (FTrackedQuery *)findTrackedQuery:(FQuerySpec *)query;
+
+- (BOOL)isQueryComplete:(FQuerySpec *)query;
+
+- (void)removeTrackedQuery:(FQuerySpec *)query;
+- (void)setQueryComplete:(FQuerySpec *)query;
+- (void)setQueriesCompleteAtPath:(FPath *)path;
+- (void)setQueryActive:(FQuerySpec *)query;
+- (void)setQueryInactive:(FQuerySpec *)query;
+
+- (BOOL)hasActiveDefaultQueryAtPath:(FPath *)path;
+- (void)ensureCompleteTrackedQueryAtPath:(FPath *)path;
+
+- (FPruneForest *)pruneOldQueries:(id<FCachePolicy>)cachePolicy;
+- (NSUInteger)numberOfPrunableQueries;
+- (NSSet *)knownCompleteChildrenAtPath:(FPath *)path;
+
+// For testing
+- (void)verifyCache;
+
+@end
diff --git a/Firebase/Database/Persistence/FTrackedQueryManager.m b/Firebase/Database/Persistence/FTrackedQueryManager.m
new file mode 100644
index 0000000..bf9753d
--- /dev/null
+++ b/Firebase/Database/Persistence/FTrackedQueryManager.m
@@ -0,0 +1,321 @@
+/*
+ * 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 "FTrackedQueryManager.h"
+#import "FImmutableTree.h"
+#import "FLevelDBStorageEngine.h"
+#import "FUtilities.h"
+#import "FTrackedQuery.h"
+#import "FPruneForest.h"
+#import "FClock.h"
+#import "FUtilities.h"
+#import "FCachePolicy.h"
+
+@interface FTrackedQueryManager ()
+
+@property (nonatomic, strong) FImmutableTree *trackedQueryTree;
+@property (nonatomic, strong) id<FStorageEngine> storageEngine;
+@property (nonatomic, strong) id<FClock> clock;
+@property (nonatomic) NSUInteger currentQueryId;
+
+@end
+
+@implementation FTrackedQueryManager
+
+- (id)initWithStorageEngine:(id<FStorageEngine>)storageEngine clock:(id<FClock>)clock {
+    self = [super init];
+    if (self != nil) {
+        self->_storageEngine = storageEngine;
+        self->_clock = clock;
+        self->_trackedQueryTree = [FImmutableTree empty];
+
+        NSTimeInterval lastUse = [clock currentTime];
+
+        NSArray *trackedQueries = [self.storageEngine loadTrackedQueries];
+        [trackedQueries enumerateObjectsUsingBlock:^(FTrackedQuery *trackedQuery, NSUInteger idx, BOOL *stop) {
+            self.currentQueryId = MAX(trackedQuery.queryId + 1, self.currentQueryId);
+            if (trackedQuery.isActive) {
+                trackedQuery = [[trackedQuery setActiveState:NO] updateLastUse:lastUse];
+                FFDebug(@"I-RDB081001", @"Setting active query %lu from previous app start inactive", (unsigned long)trackedQuery.queryId);
+                [self.storageEngine saveTrackedQuery:trackedQuery];
+            }
+            [self cacheTrackedQuery:trackedQuery];
+        }];
+    }
+    return self;
+}
+
++ (void)assertValidTrackedQuery:(FQuerySpec *)query {
+    NSAssert(!query.loadsAllData || query.isDefault, @"Can't have tracked non-default query that loads all data");
+}
+
++ (FQuerySpec *)normalizeQuery:(FQuerySpec *)query {
+    return query.loadsAllData ? [FQuerySpec defaultQueryAtPath:query.path] : query;
+}
+
+- (FTrackedQuery *)findTrackedQuery:(FQuerySpec *)query {
+    query = [FTrackedQueryManager normalizeQuery:query];
+    NSDictionary *set = [self.trackedQueryTree valueAtPath:query.path];
+    return set[query.params];
+}
+
+- (void)removeTrackedQuery:(FQuerySpec *)query {
+    query = [FTrackedQueryManager normalizeQuery:query];
+    FTrackedQuery *trackedQuery = [self findTrackedQuery:query];
+    NSAssert(trackedQuery, @"Tracked query must exist to be removed!");
+
+    [self.storageEngine removeTrackedQuery:trackedQuery.queryId];
+    NSMutableDictionary *trackedQueries = [self.trackedQueryTree valueAtPath:query.path];
+    [trackedQueries removeObjectForKey:query.params];
+}
+
+- (void)setQueryActive:(FQuerySpec *)query {
+    [self setQueryActive:YES forQuery:query];
+}
+
+- (void)setQueryInactive:(FQuerySpec *)query {
+    [self setQueryActive:NO forQuery:query];
+}
+
+- (void)setQueryActive:(BOOL)isActive forQuery:(FQuerySpec *)query {
+    query = [FTrackedQueryManager normalizeQuery:query];
+    FTrackedQuery *trackedQuery = [self findTrackedQuery:query];
+
+    // Regardless of whether it's now active or no langer active, we update the lastUse time
+    NSTimeInterval lastUse = [self.clock currentTime];
+    if (trackedQuery != nil) {
+        trackedQuery = [[trackedQuery updateLastUse:lastUse] setActiveState:isActive];
+        [self.storageEngine saveTrackedQuery:trackedQuery];
+    } else {
+        NSAssert(isActive, @"If we're setting the query to inactive, we should already be tracking it!");
+        trackedQuery = [[FTrackedQuery alloc] initWithId:self.currentQueryId++
+                                                   query:query
+                                                 lastUse:lastUse
+                                                isActive:isActive];
+        [self.storageEngine saveTrackedQuery:trackedQuery];
+    }
+
+    [self cacheTrackedQuery:trackedQuery];
+}
+
+- (void)setQueryComplete:(FQuerySpec *)query {
+    query = [FTrackedQueryManager normalizeQuery:query];
+    FTrackedQuery *trackedQuery = [self findTrackedQuery:query];
+    if (!trackedQuery) {
+        // We might have removed a query and pruned it before we got the complete message from the server...
+        FFWarn(@"I-RDB081002", @"Trying to set a query complete that is not tracked!");
+    } else if (!trackedQuery.isComplete) {
+        trackedQuery = [trackedQuery setComplete];
+        [self.storageEngine saveTrackedQuery:trackedQuery];
+        [self cacheTrackedQuery:trackedQuery];
+    } else {
+        // Nothing to do, already marked complete
+    }
+}
+
+- (void)setQueriesCompleteAtPath:(FPath *)path {
+    [[self.trackedQueryTree subtreeAtPath:path] forEach:^(FPath *childPath, NSDictionary *trackedQueries) {
+        [trackedQueries enumerateKeysAndObjectsUsingBlock:^(FQueryParams *parms, FTrackedQuery *trackedQuery, BOOL *stop) {
+            if (!trackedQuery.isComplete) {
+                FTrackedQuery *newTrackedQuery = [trackedQuery setComplete];
+                [self.storageEngine saveTrackedQuery:newTrackedQuery];
+                [self cacheTrackedQuery:newTrackedQuery];
+            }
+        }];
+    }];
+}
+
+- (BOOL)isQueryComplete:(FQuerySpec *)query {
+    if ([self isIncludedInDefaultCompleteQuery:query]) {
+        return YES;
+    } else if (query.loadsAllData) {
+        // We didn't find a default complete query, so must not be complete.
+        return NO;
+    } else {
+        NSDictionary *trackedQueries = [self.trackedQueryTree valueAtPath:query.path];
+        return [trackedQueries[query.params] isComplete];
+    }
+}
+
+- (BOOL)hasActiveDefaultQueryAtPath:(FPath *)path {
+    return [self.trackedQueryTree rootMostValueOnPath:path matching:^BOOL(NSDictionary *trackedQueries) {
+        return [trackedQueries[[FQueryParams defaultInstance]] isActive];
+    }] != nil;
+}
+
+- (void)ensureCompleteTrackedQueryAtPath:(FPath *)path {
+    FQuerySpec *query = [FQuerySpec defaultQueryAtPath:path];
+    if (![self isIncludedInDefaultCompleteQuery:query]) {
+        FTrackedQuery *trackedQuery = [self findTrackedQuery:query];
+        if (trackedQuery == nil) {
+            trackedQuery = [[FTrackedQuery alloc] initWithId:self.currentQueryId++
+                                                       query:query
+                                                     lastUse:[self.clock currentTime]
+                                                    isActive:NO
+                                                  isComplete:YES];
+        } else {
+            NSAssert(!trackedQuery.isComplete, @"This should have been handled above!");
+            trackedQuery = [trackedQuery setComplete];
+        }
+        [self.storageEngine saveTrackedQuery:trackedQuery];
+        [self cacheTrackedQuery:trackedQuery];
+    }
+}
+
+- (BOOL)isIncludedInDefaultCompleteQuery:(FQuerySpec *)query {
+    return [self.trackedQueryTree findRootMostMatchingPath:query.path predicate:^BOOL(NSDictionary *trackedQueries) {
+        return [trackedQueries[[FQueryParams defaultInstance]] isComplete];
+    }] != nil;
+}
+
+- (void)cacheTrackedQuery:(FTrackedQuery *)query {
+    [FTrackedQueryManager assertValidTrackedQuery:query.query];
+    NSMutableDictionary *trackedDict = [self.trackedQueryTree valueAtPath:query.query.path];
+    if (trackedDict == nil) {
+        trackedDict = [NSMutableDictionary dictionary];
+        self.trackedQueryTree = [self.trackedQueryTree setValue:trackedDict atPath:query.query.path];
+    }
+    trackedDict[query.query.params] = query;
+}
+
+- (NSUInteger) numberOfQueriesToPrune:(id<FCachePolicy>)cachePolicy prunableCount:(NSUInteger)numPrunable {
+    NSUInteger numPercent = (NSUInteger)ceilf(numPrunable * [cachePolicy percentOfQueriesToPruneAtOnce]);
+    NSUInteger maxToKeep = [cachePolicy maxNumberOfQueriesToKeep];
+    NSUInteger numMax = (numPrunable > maxToKeep) ? numPrunable - maxToKeep : 0;
+    // Make sure we get below number of max queries to prune
+    return MAX(numMax, numPercent);
+}
+
+- (FPruneForest *)pruneOldQueries:(id<FCachePolicy>)cachePolicy {
+    NSMutableArray *pruneableQueries = [NSMutableArray array];
+    NSMutableArray *unpruneableQueries = [NSMutableArray array];
+    [self.trackedQueryTree forEach:^(FPath *path, NSDictionary *trackedQueries) {
+        [trackedQueries enumerateKeysAndObjectsUsingBlock:^(FQueryParams *params, FTrackedQuery *trackedQuery, BOOL *stop) {
+            if (!trackedQuery.isActive) {
+                [pruneableQueries addObject:trackedQuery];
+            } else {
+                [unpruneableQueries addObject:trackedQuery];
+            }
+        }];
+    }];
+    [pruneableQueries sortUsingComparator:^NSComparisonResult(FTrackedQuery *q1, FTrackedQuery *q2) {
+        if (q1.lastUse < q2.lastUse) {
+            return NSOrderedAscending;
+        } else if (q1.lastUse > q2.lastUse) {
+            return NSOrderedDescending;
+        } else {
+            return NSOrderedSame;
+        }
+    }];
+
+
+    __block FPruneForest *pruneForest = [FPruneForest empty];
+    NSUInteger numToPrune = [self numberOfQueriesToPrune:cachePolicy prunableCount:pruneableQueries.count];
+
+    // TODO: do in transaction
+    for (NSUInteger i = 0; i < numToPrune; i++) {
+        FTrackedQuery *toPrune = pruneableQueries[i];
+        pruneForest = [pruneForest prunePath:toPrune.query.path];
+        [self removeTrackedQuery:toPrune.query];
+    }
+
+    // Keep the rest of the prunable queries
+    for (NSUInteger i = numToPrune; i < pruneableQueries.count; i++) {
+        FTrackedQuery *toKeep = pruneableQueries[i];
+        pruneForest = [pruneForest keepPath:toKeep.query.path];
+    }
+
+    // Also keep unprunable queries
+    [unpruneableQueries enumerateObjectsUsingBlock:^(FTrackedQuery *toKeep, NSUInteger idx, BOOL *stop) {
+        pruneForest = [pruneForest keepPath:toKeep.query.path];
+    }];
+
+    return pruneForest;
+}
+
+- (NSUInteger)numberOfPrunableQueries {
+    __block NSUInteger count = 0;
+    [self.trackedQueryTree forEach:^(FPath *path, NSDictionary *trackedQueries) {
+        [trackedQueries enumerateKeysAndObjectsUsingBlock:^(FQueryParams *params, FTrackedQuery *trackedQuery, BOOL *stop) {
+            if (!trackedQuery.isActive) {
+                count++;
+            }
+        }];
+    }];
+    return count;
+}
+
+- (NSSet *)filteredQueryIdsAtPath:(FPath *)path {
+    NSDictionary *queries = [self.trackedQueryTree valueAtPath:path];
+    if (queries) {
+        NSMutableSet *ids = [NSMutableSet set];
+        [queries enumerateKeysAndObjectsUsingBlock:^(FQueryParams *params, FTrackedQuery *query, BOOL *stop) {
+            if (!query.query.loadsAllData) {
+                [ids addObject:@(query.queryId)];
+            }
+        }];
+        return ids;
+    } else {
+        return [NSSet set];
+    }
+}
+
+- (NSSet *)knownCompleteChildrenAtPath:(FPath *)path {
+    NSAssert(![self isQueryComplete:[FQuerySpec defaultQueryAtPath:path]], @"Path is fully complete");
+
+    NSMutableSet *completeChildren = [NSMutableSet set];
+    // First, get complete children from any queries at this location.
+    NSSet *queryIds = [self filteredQueryIdsAtPath:path];
+    [queryIds enumerateObjectsUsingBlock:^(NSNumber *queryId, BOOL *stop) {
+        NSSet *keys = [self.storageEngine trackedQueryKeysForQuery:[queryId unsignedIntegerValue]];
+        [completeChildren unionSet:keys];
+    }];
+
+    // Second, get any complete default queries immediately below us.
+    [[[self.trackedQueryTree subtreeAtPath:path] children] enumerateKeysAndObjectsUsingBlock:^(NSString *childKey, FImmutableTree *childTree, BOOL *stop) {
+        if ([childTree.value[[FQueryParams defaultInstance]] isComplete]) {
+            [completeChildren addObject:childKey];
+        }
+    }];
+
+    return completeChildren;
+}
+
+- (void)verifyCache {
+    NSArray *storedTrackedQueries = [self.storageEngine loadTrackedQueries];
+    NSMutableArray *trackedQueries = [NSMutableArray array];
+
+    [self.trackedQueryTree forEach:^(FPath *path, NSDictionary *queryDict) {
+        [trackedQueries addObjectsFromArray:queryDict.allValues];
+    }];
+    NSComparator comparator = ^NSComparisonResult(FTrackedQuery *q1, FTrackedQuery *q2) {
+        if (q1.queryId < q2.queryId) {
+            return NSOrderedAscending;
+        } else if (q1.queryId > q2.queryId) {
+            return NSOrderedDescending;
+        } else {
+            return NSOrderedSame;
+        }
+    };
+    [trackedQueries sortUsingComparator:comparator];
+    storedTrackedQueries = [storedTrackedQueries sortedArrayUsingComparator:comparator];
+
+    if (![trackedQueries isEqualToArray:storedTrackedQueries]) {
+        [NSException raise:NSInternalInconsistencyException format:@"Tracked queries and queries stored on disk don't match"];
+    }
+}
+
+@end