Replicating memes

Current upstream situation

In Tracker‘s RDF store we journal all inserts and deletes. When we replay the journal, we replay every event that ever happened. That way you end up in precisely the same situation as when the last journal entry was appended. We use the journal also for making a backup. At restore we remove the SQLite database, put your backup file where the journal belongs, and replay it.

We also use the journal to cope with ontology changes. When an ontology change takes place for which we have no support using SQLite’s limited ALTER, we replay the journal over a new SQLite database schema. While we replay we ignore errors; some ontology changes can cause loss of data (ie. removal of a property or class).

This journal has a few problems:

• First the obvious space problem: when you insert a lot of data and later remove it all; instead of consuming no space at all it consumes twice the amount of space for an empty database. Unless you remove the journal, you can’t get it back. It’s all textual data so even when trying really, really hard wont you consume gigabytes that way. Nowadays are typical hard drives several hundreds of gigabytes in size. But yes, it’s definitely not nice.
• Second problem is less obvious, but far worse: your privacy. When you delete data you expect it to be gone. Especially when a lot of desktop interaction involves inserting or deleting data with Tracker. For example recently visited websites. When a user wants to permanently remove his browser history, he doesn’t want us to keep a copy of the insert and the delete of that information. With some effort it’s still retrievable. That’s not only bad, it’s a defect!

This was indeed not acceptable for Nokia’s N9. We decided to come up with an ad-hoc solution which we plan to someday replace with a permanent solution. I’ll discuss the permanent solution last.

The ad-hoc solution for the N9

For the N9 we decided to add a compile option to disable our own journal and instead use SQLite’s synchronous journaling. In this mode SQLite guarantees safe writes using fsync.

Before we didn’t use synchronous journaling of SQLite and had it replaced with our own journal for earlier features (backup, ontology change coping) but also, more importantly, because the N9′s storage hardware has a high latency on fsync: we wanted to take full control by using our own journal. Also because at first we were told it wouldn’t be possible to force-shutdown the device, and then this suddenly was again possible in some ways: we needed high performance plus we don’t want to lose your data, ever.

The storage space issue was less severe: the device’s storage capacity is huge compared to the significance of that problem. However, we did not want the privacy issue so I managed to get ourselves the right priorities for this problem before any launch of the N9.

The performance was significantly worse with SQLite’s synchronous journaling, so we implemented manual checkpointing in a background thread for our usage of SQLite. With this we have more control over when fsync happens on SQLite’s WAL journal. After some tuning we got comparable performance figures even with our high latency storage hardware.

We of course replaced the backup / restore to just use a copy of the SQLite database using SQLite’s backup API.

Above solution means that we lost an important feature: coping with certain ontology changes. It’s true that the N9 will not cope with just any ontology change, whereas upstream Tracker does cope with more kinds of ontology changes.

The solution for the N9 will be pragmatic: we won’t do any ontology changes, on any future release that is to be deployed on the phone, that we can’t cope with, unless the new ontology gets shipped alongside a new release of Tracker that is specifically adapted and tested to cope with that ontology change.

Planned permanent solution for upstream

The permanent solution will probably be one where the custom journal isn’t disabled and periodically gets truncated to have a first transaction that contains an entire copy of the SQLite database. This doesn’t completely solve the privacy issue, but we can provide an API to make the truncating happen at a specific time, wiping deleted information from the journal.

A few months ago we added the implicit tracker:modified property to all resources. This property is an auto-increment. It used to be that the property was incremented on ~ each SQL update-query that happens. The value is stored per resource.

We are now changing this to be per transaction. A transaction in Tracker is one set of SPARQL-Update INSERT or DELETE queries. You can do inserts and deletes about multiple resources in one such sentence (a sentence can contain multiple space delimited Update queries). An exception is everything related to ontology changes. These ontology changes get the first increment as their value for tracker:modified. This is also for ontology changes that happen after the initial ontology transaction (at the first start, is this first transaction made). The exception is made for supporting future ontology changes and the possibly needed data conversions.

The per-resource tracker:modified value is useful for application’s synchronization purposes: you can test your application’s stored tracker:modified value against the always increasing (w. exception at int. overflow) Tracker’s tracker:modified value to know whether or not your version is older.

The reason why we are changing this to per-transaction is because this way we can guarantee that the value will be restored after a journal replay and/or a backup’s restore without having to store it in either the journal nor the backup. This means that we now guarantee the value being restored without having to change either the backup’s format nor the journal’s format.

Having a persistent journal we actually make a simple copy of the journal to deliver you a backup in a fast file-copy. But let this deception be known only by the people who care about the implementation. Sssht!

We’re already rotating and compressing the rotated chunks for reducing the journal size. We’re working on not journaling data that is embedded in local files this week. A re-index of that local file will re-insert the data anyway. This will significantly reduce the size of the journal too.

It has been a long time since we wrote propaganda about the Tracker project. That has a lot to do with both the holiday-season and the fact that we’re preparing for a stable release. This means that we are increasingly reluctant to new features.

We still made quite some progress, though. We for example ported almost everything from dbus-glib and dbus-1 to GDBus and GVariant. This was quite a work; next few weeks will be used for cleaning up and regression fixing. Jürg decided that it was more easy to simply port ~ all of tracker-store to Vala than to port tracker-store’s dbus-glib and dbus-1 C code to GDBus. This should please contributors who will now have a much more easy to understand codebase.

Tracker’s tracker-store is mostly an IPC layer above libtracker-data plus the signaling mechanism. The public libtracker-sparql is a API layer above the same private libtracker-data that protects you from doing things that you should not do. Like trying to do writes without going over the IPC layer.

This week we’re working on transient properties and adding tracker:modified to the journal and backup file. The tracker:modified property is an auto-incremented value. It’s useful for synchronization purposes. Right now when you replay the journal or restore a backup, we reset the count. This means that in between journal replays and/or backup restores you wont have the same tracker:modified values for your resources. This is what we are changing. We plan to restore the tracker:modified value during journal replay and backup-restore.

Transient properties are properties that are reset after restart of tracker-store (per Desktop session), they aren’t backed up (and therefor not restored either) and they aren’t journaled. They are useful for for example presence status of a contact.

The nice guys and girls at the QSparql team are working on a simple cursor that doesn’t do any buffering nor uses any threads. This is useful for Qt applications that want maximum performance while reading the results of a query.

Last week we introduced and ported to our newest location ontology, SLO.

Tracker 0.8′s situation

In Tracker 0.8 we have a signal system that causes quite a bit of overhead. The overhead comes from:

1. Having to store the URIs of the resources involved in a changeset in tracker-store‘s memory;
2. Having to store the predicates involved in a changeset in tracker-store‘s memory (less severe than A because we can store a pointer to an instance instead of a string);
3. Having to UTF-8 validate the strings when we emit them over D-Bus (D-Bus does this implicitly);
4. DBus’s own copying and handling of string data;
5. Heavy traffic on D-Bus;
6. Context switching between tracker-store and dbus-daemon;
7. We have to wait with turning on the D-Bus objects until after we have the latest ontology. So after journal replay. And we need to reset the situation after a backup restore. Complex!

Not all aggregators show this list as A, B, C, D, E, F and G. Sorry for that. I’ll nevertheless refer to the items as such later in this article.

Consumer’s problems with Tracker 0.8′s signal

1. Aforementioned overhead: consumes a lot of D-Bus traffic. This is caused by sending over URLs for the subjects and the predicates;
2. Doesn’t make it possible, in case of a delete of <a>, to know <b> in <a> nfo:isLogicalPartOf <b>, as <a> is removed at the point of signal emission;
3. Round trips to know the literals create more D-Bus traffic;
4. Transactional changes can’t be reliably identified with SubjectsAdded, SubjectsChanged and SubjectsRemoved being separate signals;
5. A lot of D-Bus objects, instead of letting clients use D-Bus’s filtering system.

The solution that we’re developing for Tracker 0.9

Direct access

With direct-access we remove most of the round-trip cost of a query coming from a consumer that wants a literal object involved in a changeset: by utilizing the TrackerSparqlCursor API with direct-access enabled, you end up doing sqlite3_step() in your own process, directly on meta.db.

For the consumers of the signal, this removes 3.

Sending integer IDs instead of string URIs

A while ago we introduced the SPARQL function tracker:id(resource uri). The tracker:id(resource uri) function gives you a unique number that Tracker’s RDF store uses internally.

Each resource, each class and each predicate (latter are resources like any other) have such an unique internal ID.

Given that Tracker’s class signal system is specific anyway, we decided not to give you subject URL strings. Instead, we’ll give you the integer IDs.

The Writeback signal also got changed to do this, for the same reasons. But this API is entirely internal and shouldn’t be used outside of the project.

This for us removes A, B, C, D and E. For the consumers of the signal, this removes 1.

Merge added, changed and removed into the one signal

We give you two arrays in one signal: inserts and deletes.

For consumers of the signal, this removes 4.

Add the class name to the signal

This allows you to use a string filter on your signal subscription in D-Bus.

For us this removes G. For consumers of the signal, this removes 5.

Pass the object-id for resource objects

You’ll get a third number in the inserts and deletes arrays: object-id. We don’t send object literals, although for integral objects we’re still discussing this. But for resource objects we give without much extra cost the object-id.

For consumers of the signal, this removes 2.

SPARQL IN, tracker:id(resource uri) and tracker:uri(int id)

We recently added support for SPARQL IN, we already had tracker:id(resource uri) and I implemented tracker:uri(int id).

This makes things like this possible:

SELECT ?t { ?r nie:title ?t .
            FILTER (tracker:id(?r) IN (800, 801, 802, 807)) }

Where 800, 801, 802 and 807 will be the IDs that you receive in the class signal. And with tracker:uri(int id) it goes like:

SELECT tracker:uri (800) tracker:uri (801)
       tracker:uri (802) tracker:uri (807) { }

For consumers this removes most of the burden introduced by the IDs.

Context switching of processes

What is left is context switching between tracker-store and dbus-daemon, F. Mostly important for mobile targets (ARM hardware). We reduce them by grouping transactions together and then bursting larger sets. It’s both timeout and data-size based (after either a certain amount of time, or a certain memory limit, we emit). We’re still testing what the most ideal timeouts and sizes are on target hardware.

Where is the stuff?

The work isn’t yet reviewed nor thoroughly tested. This will happen next few days and weeks.

Anyway, here’s the branch, documentation, example in Plain C, example in Vala