This document attempts to describe why and how the Bif project management tool does what it does.
0.1.0_28 (2014-09-23)
The development of Distributed Version Control System (DVCS) software enabled developers to discover the joys of working with a fully-featured, always available local repository. A number of benefits related to productivity (working when not connected) and efficiency (fast executing commands) appeared. Shortly afterwards developers re-discovered the pain of still having to use centralised, web-based bug/issue tracking systems, which kind of muted the joy somewhat.
The first open attempts at a Distributed Project Management System (DPMS) such as Bugs Everywhere, ScmBug, DisTract, DITrack, ticgit and ditz, were implemented on top of a DVCS. With a bit of hindsight, one can theorize that their failure to gain real traction was in part due to not understanding that DVCS and DPMS systems do not have the same information models. With time, most projects have also realized that there are users other than developers who need to interact with such a tool.
Later, DPMS systems were built on different models, but offered a non-UNIXy implementation (Fossil) or suffered documentation and implementation issues (Simple Defects - SD). As of late 2011 the Debian BTS (debbugs), SD and Launchpad (Canonical) appear to be the only systems that provide some kind of interproject cooperation (one issue with different status), but neither debbugs nor Launchpad are really distributed.
It was in this context that Bif was started in with the vague aim of doing something better. While I can say I was trying to learn from earlier efforts, I had nothing like the clarity of mind at the beginning that the above paragraphs imply. Like several others I actually started out building Bif on top of Git. This is no surprise because like everyone else I found the easy replication and plumbing toolset attractive. Experience finally taught me too that the Git model was the wrong one for this application, so after briefly playing with SQLite + Git I settled on SQLite alone with a purpose-built schema and a completely new synchronisation protocol.
The user manual says that Bif aims to be:
"... a distributed communication system that carries both conversations and structured meta-data."
To put it another way, the goal of Bif is to provide users with a fully functional local issue tracker that interacts with remote instances as needed.
Note that some of the distributed requirements for a *project* tracking system are actually quite different to the distributed requirements for a *software* tracking system. DVCS focus on managing a multi-tentacled, pick-from-anywhere, many-versions-at-a-time set of changes to files. DPMS focus is on tracking items of work at the organisational or personal level.
Context switching from the shell to the browser is costly. Good engineering means that the CLI is anyway a thin layer over the database, meaning that adding other interfaces later is relatively easy.
CLI should be consistent, semi-similar to other CLI programs. Oh yeah, I almost forgot. The CLI should be responsive enough to be almost instantaneous. There will be no Moose in this CLI tool. Even though I upgraded my laptop recently with an SSD I still can't believe how much it affects the startup time in things like App::TimeTracker. If I release something like that the thoughts of the first (non-Perl-aware) user will be "Do we need to rewrite this in Go?"
For management-style reports, for custom queries, for dealing with the whole interproject cooperation requirement. Users need to quickly see summaries of the current status as well as the change history.
As much as possible, the tool should work everywhere that you can. In effect that means data replication, but should only be as much as is needed. It doesn't make sense to transfer and synchronize large amounts of data that will never be queried. "As much as is needed" is a somewhat nebulous description - each person probably has a different meaning in mind.
There is no way that a sequential scan and check for matching rows in databases should be done each time a user wants to synchronise.
A RESTful object API just doesn't seem suitable either for working with large collections of objects like bugs or projects, and how does one not lose all the benefits associated with database transactions?
A project history is not a hierarchical tree al-la Git trees. Changes can be merged without needing to reparent anything.
We cannot subject users to identifiers that look like abb382f3c.
If we are going to distribute things, we should do it properly. That means an issue can be tracked by multiple projects, and that each project could consider it to have a different status, and that each project can see the status in the other projects.
No reason that every project in the whole Bif ecosystem must use the same status types.
Scalability was not an initially identified requirement, but as development has proceeded I have found myself taking it more and more into consideration. How would bif have to work to be useful to an organisation the size of Debian?
There were close to forty thousand packages in Debian 7.0, progressively fewer in previous distributions. Packages were released multiple times during development and for security changes, and each package release could probably be considered a bif project. A single, centralized database, with email-based communication seems to work ok for that project. It will take some thought to determine whether replacing that model with a bif-supported workflow provides any advantages.
Aside from functionality, for this to be successful it has to be useable, approachable, and understandable. In many ways this comes down to the quality of the documentation.
Necessary for exchanging changes between systems that have their own requirements for locally unique identifiers.
We assume that there are relatively few project changes in comparison to task and issue changes.
There are tables for $THINGS which usually also have a row in the "topics" table: projects, tasks, issues, hubs, hub locations, and status types for all of those. They have columns for a current state if applicable, and may have columns that indicate a relationship (e.g. projects.hub_id).
There are sometimes tables for many-to-many relationships, such as an issue having a different status for each project.
A Bif change can actually be composed of many operations in the database, but everything relates to a single row in the changes table. The changes table has an integer primary key which is used for local operations and foreign key targets. It also has a 40 character Universally Unique ID (UUID).
changes
There is a table for "changes" that represent changes, but that table only contains generic items such as timestamps, author details, and a message.
The UUIDs of changes (same for UUIDs of topics) are SHA1 hashes calculated from the content of the change (or topic). This provides a builtin checksum mechanism that is useful during synchronisation to indicate a full and accurate transfer, and potentially simplifies signing changes in the future. The main purposes of the UUID however is for looking up local IDs when inserting changes with foreign key requirements.
There are tables for $THINGS_deltas, which relate changes to $THINGS with a particular change.
Operations happen like this:
create a row in the changes table that identifies the author, time, timezone, message
add the changes in the *_deltas tables for each topic
Changes are "resolved" by inserting a row into func_merge_changes that calculates the changes.uuid SHA1 hash. If changes.uuid is already set (i.e. it was passed in from another repository) then it must match otherwise an error is raised. In this way we ensure a reliable copy of the data.
Changes are immutable, and they can't be easily deleted from everywhere. For the moment at least. Possibly thinking about changes to an change...
One of the actions that takes place when an change is resolved is the merging of any received deltas to set the current value of the user's project, task or issue status. The merge is very simple: the latest result according to the change timestamp wins.
Two types of meta data are calculated and stored in addition to the user data. The end result of the calculations are Merkle trees, which are the basis on which synchronisation occurs.
In each repository we track the related hub_delta, hub_repo_deltas, project_deltas and *_status_deltas in the "hub_related_changes" table.
+---------++---------+ | task || hub | | status || changes | | changes || | +---------++---------+ | | | | v v +----------+ +--------------------+ +---------+ | hub | | | | issue | | location | | | | status | | changes | --> | hub | <-- | changes | +----------+ | related | +---------+ +----------+ | changes | +---------+ | project | | | | project | | changes | | | | status | | | --> | | <-- | changes | +----------+ +--------------------+ +---------+
These are tracked not just for the local repository, but also for remote repositories (hubs).
When a local user pulls a hub all project-only details are imported. Initially this so that the local user can see what projects are available on the hub. Therefore, for each hub we track the related project_deltas and *_status_deltas in the "hub_related_changes" table.
Current state of topics, table for changes to topics, tables to track meta data (Merkle trees).
There is a Merkle tree associated with every project/hub combination, representing all of the changes contained therein.
Bif does not implement a single distributed database, at least not in the sense where all nodes need to agree in almost-real-time on what the "current" or "latest" values for all objects are. What bif does is simbly exchange a certain set of changes to a certain set of nodes on demand. The state of a particular node is the result of the subset of changes it has, and it doesn't care what the other nodes are doing. This works because the users do not need a real-time global view of all projects in an organisation, in the same way they don't need real-time copies of all emails not addressed to them.
Bif communicates using JSON sentences terminated by a double-newline (\n\n). Communication is bi-directional, often asynchronous, and occurs on a single channel.
Commands or instructions are sent as array references with the first element being an UPPERCASE string, and the remaining elements vary depending on the instruction.
["SYNC","project","f6f4f48ef6846421a5d","82e38655"]
Status replies are array references generally containing a just a single CamelCase string element.
["ProjectMatch"]
Sometimes instead of a status reply a counter-instruction is sent, and sometimes multiple instructions are sent without waiting for a reply:
["NEW","change",{"mtime":14153122121,"message":"Hello"] ["NEW","project",{"mtime":14153122121,"title":"todo"] ["NEW","project_status",{"mtime":14153122121,"title":"run"] ["UPDATE","project",{"status_uuid":"11eb3ba88ae0f"]
The server will generally keep the connection open and answering commands until the client sends a QUIT message:
["QUIT"]
When a local user pulls a hub all project-only details are imported from the "hub_related_changes" table. Initially this so that the local user can see what projects are available on the hub.
+-------+ hub_related_changes +-----+ | local | <--------------------- | hub | +-------+ +-----+
The first part of a project export (push) is a local operation. The local project-only changes are added to hub_related_changes. The next time a hub sync happens the details will be transferred across.
+-------+ hub_related_changes +-----+ | local | <---------------------> | hub | +-------+ +-----+
If nothing else happened this could be considered a shallow export, meaning the project can be referenced on the hub, but is not fully available there. This is useful for inter-hub collaboration as we shall see later.
The second part of an export is to change the project to set its hub_id values.
The third part of an export is the synchronisation of the project_related_changes on both sides. However given that the hub doesn't have anyting in there yet this is effectively a one-way copy.
We already have project-only changes for $PROJECT in the database. We may also have issue changes related to $PROJECT locally.
Basically just copies everything relating to a project from one repository to another.
A sync operation with a hub happens in two steps. First of all the hub-related changes (which are actually project meta-data) are exchanged, then the project-related changes (which are actually task and issue data) are exchanged.
Syncing hub-related changes is relatively easy. The hub_related_changes_merkle table from each end is recursively compared top down - need to check) to discover the differences, from which a set of changes is stored in a temporary table. The changes are then tranferred to the other end in the order they were created in the database.
Syncing project-related changes starts out the same way as hub-related change synchronisation. The project_related_changes_merkle table from each end is recursively compared top down to discover the differences.
However, the set of changes which are stored at each end to be transferred cannot be directly inferred from the merkle tree because the client is only synchronising the projects which it has locally (i.e. have been imported). The challenge is how to do that when an issue exists in two projects but only one is local
The changes are then tranferred to the other end in the order they were created in the database.
Bif is a Perl wrapper around an SQLite database, structured as follows:
A utility module responsible for finding the .bif repository and setting up debug, pagers, formatting tables, etc.
A module for the implementation of each bif command.
The implementation of the bifsync synchronization command.
Database access.
Roles that implement the core of the bif network protocol.
Classes that provide client and server interfaces for the App::bif::* commands.
Commands are dispatched to Perl modules under the App::bif::* namespace by OptArgs. Execution happens like this:
The shell runs the bif file, which due to the #! hashbang line results in perl being executed on that file.
bif
perl
The bif script loads the Perl module OptArgs and calls the OptArgs::dispatch function against the App::bif namespace.
OptArgs::dispatch
App::bif defines all of the subcommands, their arguments and options, which the dispatch function uses to dispatch to the appropriate App::bif::* module.
The App::bif::sub::command module run method is called.
run
Sub-command classes use functions from App::bif::Context to discover the location of the repository, the user configuration, access the database, render output, generate errors and so on.
the program ends.
Each command uses either Bif::DB or Bif::DBW (based on DBIx::ThinSQL, DBI, and DBD::SQLite) to access the database.
As much as possible is done inside the database with the goal of ensuring data consistency regardless of what application is entering the data. Preparing for some other tool than Bif to be making modifications.
SQLite does not have a built-in procedural programming language with a function calling interface. We cheat by defining BEFORE INSERT triggers on normal tables that do their required work and then cancel the insert with a SELECT RAISE(IGNORE) statement.
BEFORE INSERT
SELECT RAISE(IGNORE)
Bif uses ssh to run the bifsync program on remote hosts when exchanging changes with a hub, or else calls bifsync directly when exchanging changes with a local repository. Regardless, it ends up being Bif::Client that is talking to Bif::Server, although most of the functionality is in the parent Bif::Role::Sync class.
Client/Server is a bit of a misnomer, as the protocol is actually about exchanging changes equally, and not particularly about a user needing a resource like HTTP verbs imply.
Mark Lawrence <nomad@null.net>
Copyright 2013-2014 Mark Lawrence <nomad@null.net>
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
To install App::bif, copy and paste the appropriate command in to your terminal.
cpanm
cpanm App::bif
CPAN shell
perl -MCPAN -e shell install App::bif
For more information on module installation, please visit the detailed CPAN module installation guide.