Firebase Database not pruning tracked queries

[marcbaldwin]

• Xcode version: 9.4.1 (9F2000)
• Firebase SDK version: 5.4.0
• Firebase Component: Database
• Component version: 5.4.0

Description of the problem

The time it takes for the first callback to occur when observing a reference increases proportionally with the number of writes made. In some cases this means it takes nearly three minutes for the first callback to occur.

Note: Turning off persistence fixes the issue.

Steps to reproduce:

Enable persistence.
Observe a database reference
Make thousands of writes
Re-open the app, the time taken before the first callback of the reference will have increased

I profiled the app in instruments and narrowed down the cause to FTrackedQueryManager.initWithStorageEngine

It loops through all tracked queries, in my case I had some 200,000 tracked queries. Looking at them in the debug viewer I noticed most were from writes which were made months ago.

It appears as though every time a write occurs a tracked query is added for the path of the write and is never removed, so overtime these tracked queries build up, leading to an ever increasing start up time for the FTrackedQueryManager.

There are functions to purge the cache but these are not public and they don't appear to be invoked when the Database is initialised.

Relevant Code:

Database.database().isPersistenceEnabled = true

[morganchen12]

@mikelehen the repro steps seem pretty ordinary, I'm surprised this hasn't shown up before. Is this a regression?

[mikelehen]

This is probably related to

firebase-ios-sdk/Firebase/Database/Persistence/FPersistenceManager.m

Line 124 in c6b4b03

// This is a hack to guess whether we already cached this because we got a server data update for this

When you perform a write we add it to our cache, which includes adding it to our tracked queries (which helps us know that we have complete data for that location and can raise events for it if you listen in the future).

I believe our cache policy tries to keep only up to 1000 tracked queries (

firebase-ios-sdk/Firebase/Database/Persistence/FCachePolicy.m

Line 26 in c6b4b03

static const NSUInteger kFMaxNumberOfPrunableQueriesToKeep = 1000;

) but we only check whether to prune the cache after every 1000 listen updates (see the line above). So if your app only does writes (or mostly writes with very few listens or very infrequently-changing listens) then we may never attempt to prune the cache, allowing the tracked queries to grow...

A simple improvement may be to add a call to doPruneCheckAfterServerUpdate (

firebase-ios-sdk/Firebase/Database/Persistence/FPersistenceManager.m

Line 153 in c6b4b03

- (void)doPruneCheckAfterServerUpdate {

) from applyUserWrite (

firebase-ios-sdk/Firebase/Database/Persistence/FPersistenceManager.m

Line 123 in c6b4b03

- (void)applyUserWrite:(id<FNode>)write toServerCacheAtPath:(FPath *)path {

). That way we'd do the prune check after each write and should actually limit you to ~1000 tracked queries. [though we also should do some renaming of afterServerUpdate or at least add comments to explain what's going on]

@schmidt-sebastian officially maintains the Realtime Database SDK though I don't know if he has cycles to look into / implement / test this. If you were so inclined, providing a PR might be more likely to get this fixed in the near-term. :-)

[marcbaldwin]

Thanks @mikelehen for the speedy response. @schmidt-sebastian do you think you'll be able to have a look? If not I'd be happy to have a go at fixing it :)

Thanks!

[schmidt-sebastian]

I can take a look at this next week or so. If you want to take a stab at it in the meantime, I would be more than happy to support you along the way. Thanks!

[marcbaldwin]

Some more info...

After a write FPersistenceManager.doPruneCheckAfterServerUpdate is executed which checks to see if a prune is required according to its cache policy pacing in its serverCacheUpdatesSinceLastPruneCheck value. However as the serverCacheUpdatesSinceLastPruneCheck is not persisted between app restarts, a prune will only occur after 1000 server updates during a single app session.

Some options:

• Always perform a prune check (it doesn't appear to be a very CPU intensive task)
• Reduce the maximum number of server updates before performing a prune
• Persist the number of server updates since last prune check between app sessions
• On first server update of any app session, always perform a prune

What do you suggest @schmidt-sebastian

[schmidt-sebastian]

I would suggest you pick option 4 and perform a prune check at startup, and then once every 1000 operations. Since we target a wide range of mobile devices, it is sometimes very hard to predict what the perceived performance characteristics of changes in the persistence logic are.

[mikelehen]

doPruneCheckAfterServerUpdate is actually pretty expensive because it has to iterate the entire database to estimate the cache size. It ends up calling https://github.com/firebase/firebase-ios-sdk/blob/master/Firebase/Database/third_party/Wrap-leveldb/APLevelDB.mm#L289

So option 4 is the most palatable of your options but it'll still slow down app starts for everybody. And it'll still only help apps once they restart. During the life of the app, if they're only doing writes (and not getting server updates) they'll never do another prune.

And so I still think my suggestion in #1518 (comment) probably makes the most sense.

[marcbaldwin]

Thanks for the input.

@mikelehen If doPruneCheckAfterServerUpdate is expensive then would it not be a bad idea to be calling it inapplyUserWrite? In some cases our app might make multiple writes per second.

Could another option be to add a public method to perform a prune? Then users can perform it when it best suits the needs of their app. For example, I'd probably choose to do it after start-up and after an initial fetch from the database, or maybe when the app is sent to the background.

[mikelehen]

@marcbaldwin Well, because of the kFServerUpdatesBetweenCacheSizeChecks counter in there it would still only do the expensive part of the check once every 1000 writes... so you might see the occasional delayed write, but it shouldn't be too bad... hopefully. :-)

Adding an API would certainly provide the most control for developers, but 1) ideally we'd solve this transparently for the majority of use cases without developers needing to change their code, and 2) adding an API is frankly more time-consuming and expensive. The Firebase APIs are carefully curated and there's an internal design / approval process that we'd need to go through to make changes. It's certainly doable, but it's not something to be taken too lightly.

[marcbaldwin]

@mikelehen @schmidt-sebastian sorry for the delayed response, I've been away on holiday.

@mikelehen calling doPruneCheckAfterServerUpdate from applyUserWrite still won't help unless our app performs 1000 writes or we change the if statement to account for the number of tracked queries.

// Current
- (void)doPruneCheckAfterServerUpdate {
    self.serverCacheUpdatesSinceLastPruneCheck++;
    if ([self.cachePolicy shouldCheckCacheSize: self.serverCacheUpdatesSinceLastPruneCheck]) {

/// proposed
- (void)doPruneCheckAfterServerUpdate {
    self.serverCacheUpdatesSinceLastPruneCheck++;
    if ([self.cachePolicy shouldCheckCacheSize: self.serverCacheUpdatesSinceLastPruneCheck 
                numberOfTrackedQueries: self.trackedQueryManager.numberOfPrunableQueries]) {

Thanks!

[mikelehen]

@marcbaldwin Hrm. Are you saying that your app is not doing more than 1000 writes? From your original statement about having 200,000 tracked queries, my assumption was that the pruning would kick in every time you reached ~1000, which should be sufficient to keep the performance good.

self.trackedQueryManager.numberOfPrunableQueries is an O(n) operation (it requires walking all of the tracked queries) and so doing it after every write or server update could impact performance significantly.

It also wouldn't help unless we also changed our current cache policy, since kFMaxNumberOfPrunableQueriesToKeep is set to 1000 (

firebase-ios-sdk/Firebase/Database/Persistence/FCachePolicy.m

Line 26 in 1d484d3

static const NSUInteger kFMaxNumberOfPrunableQueriesToKeep = 1000;

).

[marcbaldwin]

The problem is, that it's unlikely our app will do more than 1000 writes in a given app session. As serverCacheUpdatesSinceLastPruneCheck is not persisted between app restarts. So if we don't hit 1000 writes or server updates in a single app session, no tracked queries will ever be pruned.

At the moment with 200,000 tracked queries, our app is unusable for about three minutes whilst all those queries are traversed. Having 1000 tracked queries, that time is less than a second.

Going back to my earlier suggestion, could we simply persist serverCacheUpdatesSinceLastPruneCheck between app restarts and increment it after every write? We should then never exceed 1000 tracked queries and have predictable write and start-up performance?

Thanks again for the support!

[mikelehen]

Out of curiosity, how many app sessions does it take for your app to hit 200,000? I assumed there must be some action in your app that triggers a large number of writes and hopefully it'd (at least periodically?) exceed 1000 and the pruning would kick in. It's not foolproof but I would expect it'd be good enough for most apps.

But yeah, persisting serverCacheUpdatesSinceLastPruneCheck would be more foolproof, dealing with the case of an app that accumulates many tracked queries over time but only a small number each app session. But I'm somewhat wary of making schema changes. Most of our development effort is going into Cloud Firestore and we only have limited bandwidth to implement / test features for Realtime Database. Schema changes are more risky and time-consuming. :-/

Also FWIW, persisting an extra value on every write / server update would make persistence a little slower... so if most apps don't need it, it may not be the right trade-off (Ideally we'd benchmark the perf impact, but again that's more work).