Lil Todo is a to-do app that I wrote for the Mac. (An iOS version of the app is coming soon!) One of the great things about it is you can run it on multiple Macs and use a single Dropbox account to save and sync all of your tasks. Mark a task completed on one device and the change shows up on all the other devices.
Since the app just uses Dropbox and doesn’t use its own sync service, you don’t need to create a new account to sync (assuming you already have a Dropbox account). This is great for me too because it means I don’t have to write and maintain a sync service. 🙂
So how does that work? From the user perspective, it sounds so simple, but behind the scenes it’s not as straightforward as you’d think.
Dropbox == Simple File Store
Dropbox is just a file store and doesn’t really handle multiple edits to the same file very well. If two people edit the same file and both attempt to save it, Dropbox will detect a conflict and save two copies of the file, letting you pick which of the two to keep. If we used a single file to represent our database of tasks in Dropbox and had multiple Macs editing and saving that file, we’d run into conflicts all the time.
If that’s the case, how can we use Dropbox to represent our database of tasks across multiple devices?
The Solution: One Weird Trick
The answer is simple but not necessarily intuitive: have each device running Lil Todo write to its own file in Dropbox. If each instance of the app has its own file to write to, we’d never have any conflicts since each file has a single owner. (Multiple devices are okay to read that same file, of course.)
That’s great, but how do you represent a database of tasks using multiple files, one for each device?
Here’s the novel bit: instead of writing to a database of tasks, have each device write the changes it would like to make to the database. In other words, each file for each device is a transaction log of all edits made from that device. (This is also known as Event Sourcing, although when I came up with my initial solution, I had no idea it was already a thing. I promise!)
Transaction Logs, Baby
When you launch Lil Todo for the first time on a device, the app is assigned a universally unique identifier (UUID). This identifier is guaranteed to be unique across all devices and is used to name the transaction log for that particular device.
When you create your first task, a “Create task” entry is added to the log with details of the new task. When you mark a task done, an “Edit task” entry is added to the log with the ‘done’ property set to true. In fact, all edits to a task (changing the title, due date, or notes) causes a new “Edit task” entry to be added to the log with a list of the properties that have changed. (Even deleting a task simply adds an “Edit task” entry with the ‘deleted’ property to true. Tasks aren’t actually deleted in the file.)
As you can see, we don’t actually write to a traditional database of tasks. Instead, we write a history of edits to all tasks.
This transaction log file grows over time and represents all task creations and edits made from that device. When you sync to Dropbox, we upload the latest version of your device’s transaction log to the Lil Todo folder in Dropbox. We also download all the transaction logs from all other devices. We then take all the transaction logs and merge them in memory to form one large, universal transaction log (which I call Voltron).
Every entry in the transaction logs has a timestamp to ensure we can sort all of the logs across all devices in the order in which they occurred. It’s simply a matter of “playing” back all entries in the universal log and reconstructing the entire database in memory. Once we have the full database reconstructed, we’re ready to show it in the UI and let the user make edits (which, remember, simply cause new entries to be added to the log for that particular device).
Dealing with Conflicts
Note that if you try to edit the same task on two different devices at about the same time, the most recent edit will “win”. In the unlikely case that the edits actually happen at exactly the same time, the device with the UUID that appears later sorted alphabetically will “win”. The system is deterministic. It has to be to ensure consistency across all devices. Once all devices sync with the most recent version of all logs, their database contents will all match. (This is a form of eventual consistency!)
It’s worth noting that the timestamps across all the devices aren’t necessarily perfectly in sync. Each device uses UTC for its timestamps, but it’s possible they could be off by a second or two. For the goals of this app, this is acceptable as the target scenario for this app is a single user jumping from device to device to make edits. I don’t expect the target audience to be editing the same task on two different devices within a second or two of each other. Most users will make a bunch of edits on a device and later move to another device later (at least not seconds) to make more edits.
This app works great for a single user, but if this app required multiple users across multiple devices, it would not work as well. We’d need to have much more active syncing of the files to ensure each user has the most up to date version. At the moment, the app syncs to Dropbox every few minutes as needed.
Replaying the transaction log does take longer and longer as it grows. At the moment, a cached version of the database is written to disk and loaded on launch to avoid the perf hit of regenerating the it, but the database does have to be regenerated if the app detects that there are new entries added to any of the transaction logs from other devices during sync.
It should be possible to alleviate some of these performance issues by occasionally creating snapshots of the database given the current state of the logs. When new transaction logs are downloaded, we’d simply re-play the universal transaction log from the most recent database snapshot that did not contain the first new log entry. (This snapshot feature has not yet been implemented in the interest of shipping the product fast! Once the author starts to feel the pain of long load-times, he promises to add this feature. 😁)
Overall, I’m quite happy with the implementation. It means I don’t have to create a new sync service. Creating a new service to host other people’s private tasks is a big deal. I’d have to worry about security, maintenance, and long-term plans (I’d have to keep the service up if people relied on it).
This sync system has been reliable thus far and there are no worries about race conditions or locking issues since each device is solely responsible for its own transaction log. The system can also scale up indefinitely (at the cost of perf) since each device gets a UUID and it’s simply a matter for all devices to “notice” the new transaction log in the shared app folder on Dropbox. There is no central registry of devices, just transaction logs representing each device. No locking of resources is ever needed.
In the future, I’d like to refactor some of the code I’ve written for this so it can be generalized to any file store (cloud or otherwise) and any type of database. If I do that, I can post it on github so others can use it.
If you’re considering writing an app and using a third party file store like Dropbox to sync across devices for a single user, I recommend giving this technique a try.
If you got this far, thanks for reading! I’d love to hear your thoughts below.
One last plug: give Lil Todo a try while you’re here! Please do check out my other projects as well.