<commit_before>\documentclass{bioinfo}
\copyrightyear{2014}
\pubyear{2014}
\usepackage{xspace}
\newcommand{\ps}{phylesystem\xspace}
\newcommand{\otol}{Open Tree of Life\xspace}
\newcommand{\nexson}{otNexSON\xspace}
\newcommand{\js}{JavaScript\xspace}
\newcommand{\mthcomment}[1]{{\color{red} \textsc{#1}}\xspace}

\usepackage{natbib}
\bibliographystyle{apalike}

\usepackage{hyperref}
\hypersetup{colorlinks=true, linkcolor=black, citecolor=black, hyperindex=true, backref}
\begin{document}
\firstpage{1}
\title[phylesystem git phylostore]{Phylesystem: a git-based data store for community curated phylogenetic estimates}

\author[McTavish\textit{et~al}]{
    <NAME>,$^{1,2}$
    <NAME>.~Holder,$^{1,2}$\footnote{to whom correspondence should be addressed}~
    Ann Other Author,$^{3}$
    Ann Other Author,$^{4}$
    Ann Other Author,$^{5}$ $\ldots$
}
\address{$^{1}$Department of Ecology and Evolutionary Biology, University of Kansas, Lawrence KS, USA\\
$^{2}$Heidelberg Institute of Theoretical Studies, Heidelberg, Germany}

\history{Received on XXXXX; revised on XXXXX; accepted on XXXXX}

\editor{Associate Editor: XXXXXXX}

\maketitle

\begin{abstract}
\section{Motivation:}
Archival storage of phylogenetic estimates from published studies can be accomplished
    using general platforms, like Dryad, or TreeBase.
Those services fulfill a crucial role in helping phylogenetic studies be more transparent
    and reproducible.
However, available trees require some editing to improve the accuracy and reusability of the phylogenetic statements.
Many trees in data archives or supplemental files from publications are incorrectly rooted.
Establishing the linkage between tip labels used in a tree and taxa in a single taxonomy 
    dramatically improves the ability of other researchers to reuse phylogenetic estimates.
Because the process of curating a published phylogenetic estimate is not error-free,
    retaining a full record of the provenance edits to a tree is crucial for
    openness, allowing editors to receive credit for their work, and
    making errors introduced during curation easier to correct.

\section{Results:}
Here we report the development of software infrastructure to support the open curation of
    phylogenetic data by the community of biologists.
The backend of the system provides an interface for the standard database operations of
    creating, reading, updating, and deleting records by creating commits in a git repository.
The record of the history of edits to a tree is preserved by git's version control features.
Hosting this datastore on GitHub provides a open access to the data store using tools
    familiar to many developers.
We have deployed a server running the ``phylesystem-api'', which wraps the interactions with git and GitHub.
The \otol project has also developed and deployed a \js application that uses the \ps-api and
    other web services to enable input and curation of published phylogenetic statements
\section{Availability:}
Source code for the web-service layer is available at \url{https://github.com/OpenTreeOfLife/phylesystem-api}.\\
%The library \url{https://github.com/OpenTreeOfLife/peyotl} is a prerequisite.
The data store can be cloned from: 
\url{https://github.com/OpenTreeOfLife/phylesystem}.
A web application that uses the \ps web services is deployed
at \url{http://tree.opentreeoflife.org/curator}.
Code for that tool is available from 
\url{https://github.com/OpenTreeOfLife/opentree}.

\section{Contact:} \href{mailto:<EMAIL>}{<EMAIL>}

\end{abstract}

\section{Introduction}

Characterizing and systematizing relationships among species has been a goal of biologists since Linnaeus \cite{Linne1758}.
The phylogenetic systematics ``revolution'' of the 1960's focused most of the effort toward this goal around the 
    task of estimating phylogenetic relationships.
The rapid growth in availability of molecular data, the development of models and software implementations for
    inferring phylogenies and the appreciation of the importance of phylogenetically-aware comparative methods
    \citep[e.g.][]{Felsenstein1985Comp} have led to dramatic increases in the number phylogenetic estimates.


Unfortunately, capturing the inputs and outputs of a phylogenetic analysis in a rich, standardized form is
    difficult and error prone. There is no single standard for phylogenetic data, and developers of phylogenetic
    software often create new formats or extend existing formats in ways that make them incompatible with other programs. 
Some archiving servies, such as Dryad \citep{Dryad}, have reacted to this challenge by accepting a 
    wide range of inputs and making few or no
    guarantees to users of the database that the records will be in any particular form.
This encourages sharing of data by making the submission process fast and easy, and is advantageous under Dryad's
    general purpose archival model--Dryad's scope is not limited to phylogenetic information.
However, if the authors submitting the data are not conscientious in their explanations of the data, it can be difficult
    for users of the data to reliably extract all of the information in the archive, or the data may not contain sufficient metadata for reuse.

On the opposite end of the spectrum, some databases require data providers to conform to more rigorous
    standards with respect to input format and content.
    Since 1994, TreeBase \citep{SandersonDPE1994} and its successor TreeBase version 2 \citep{TreeBase2} have served
    as the primary archival data stores for phylogenetic estimates and the data that these trees are based on.
As of 2014, TreeBase contains 4076 studes and over 12,800 trees \citep{TreeBaseWebCite}.
Many journals encourage or require that each publication that estimates phylogenetic trees cite a TreeBase
    deposition containing the associated trees.
TreeBase produces a much more feature-rich interface for phylogenetic queries than Dryad, because each 
    TreeBase submission is parsed thoroughly and converted to a set of records in a relational database.
The downside of this approach is that it requires that submissions correspond to a more uniform format and without constant updating, that format may not reflect new types phylogenetic data being generated.

Unfortunately, file formats read and written by tree estimation tools are idiosyncratic and often so 
    terse that they omit useful information about the analysis (see \citet{StoltzfusEtAl2012} for a discussion
    of this topic and other challenges relating to the archiving of phylogenetic estimates).
As a result, the TreeBase submission process usually requires the authors of a data package to reformat their data, correct
    the rooting of the tree, alter the labels of the tips of the tree, {\em etc}.
    The TreeBase project provides a 12-minute video explaining
    \footnote{\url{http://treebase.org/treebase-web/submitTutorial.html}} 
    the non-trivial procedure of preparing a submission.
Because these steps are often taken after the analyses for a publication are complete, it is more likely 
    errors introduced in the submission process will not be corrected until an observant user tries to reuse the data.
If there were a universally used, rich file format for phylogenetics analyses, then import constraints such as those
    used by TreeBase would be less of a hurdle, since the critical metadata regarding rooting, labels, etc. could be
    stored alongside the tree itself.
The xml-based NexML specification \citep{NeXML} used internally by TreeBase defines such a format, but it is not widely used.

Thus, the current state of phyloinformatic archival infrastructure is ripe for improvement in numerous ways.
One such opportunity is the development of a datastore that allows the community of biologists to improve the
    accuracy and re-usability of published phylogenetic statements.
We describe here an implementation of one such system, which we call ``phylesystem'' because it uses a set of
    versioned text files on the filesystem (and the fact that we {\em love} bad puns).
The goal of \ps is not to replace systems like Dryad or TreeBase, but to complement them by 
    storing phylogenetic statements and associated metadata in a consistent format while retaining the history of
    edits that were made to the data themselves.
We anticipate that most of the trees stored in \ps will be associated with permanent, static archives
    elsewhere (usually either TreeBase or Dryad).

\subsection{Approach}
One of the motivations of the design of \ps was to support the \otol's need for a curated set
    of rooted trees that have been aligned to a common taxonomy.
Additionally, one of the goals of the \otol project was to support infrastructure for phylogenetic
    research in an open way that encourages the community of biologists to participate in the 
    collection and curation of our knowledge of the phylogenetic relationships of life on Earth.

Thus, our goals when designing \ps were to build: 
\begin{enumerate}
    \item  a data store capable of:
        \begin{enumerate}
            \item \label{fewKStudies} storing trees from thousands of published studies. We do not intend to store the 
                data upon which the phylogenetic estimates were based.
            \item \label{fewTreesPerStudy} storing a few exemplar trees from each study. We do not anticipate that the system will be used 
                to store thousands of trees from 
                a study (such as each sampled tree from a bootstrap or MCMC analysis, for example).
            \item \label{richAnnot} handling rich annotation of the trees, the taxa to which they refer to, and metadata describing 
                the analysis that produced the trees.
            \item \label{history} storing the full history of changes made to a study and its trees,
                including an identifier to indicate who made the changes.
        \end{enumerate}
    \item \label{ws} web services around the data store to support a user-friendly curation application run in the user's browser. These include services for validation of the files against a published schema.
    \item \label{looseOpen} a loosely coupled system that would allow the community of biologists to interact with the data in a wide variety of ways.
\end{enumerate}
From these requirements, we chose to implement \ps as a set of software wrappers around a data store
    which consists of a git \citep{git} repository of phylogenetic statements serialized as a \js Object Notation (JSON).
The data model used for the JSON is a close derivative of the NeXML standard for data interoperability\citep{NeXML}.

Our expectations that the system would have to store relatively small amount of data 
    (points \#\ref{fewKStudies} and \ref{fewTreesPerStudy} above) and that most
    studies would require relatively few edits imply that
    raw performance of the basic database operations was unlikely to be a bottleneck for most
    uses of the \ps.
This made it feasible to use text files as form of data store.
Thus far, in the six months since deployment of the study curation interface, the mean number of edits 
    per study is only \mthcomment{Need to calculate this from git history - it is a small, number though}.
The total size of the stored data (in JSON format with a line ending after 
    every field) is only around 150MB.

The requirement (\#\ref{history}, above) of maintaining a history of changes 
    (including an identifier for the editor) fits naturally with software version control systems.
We note that wiki engines such as Gollum use git version control as a backend database.
The idea of using git as general database has been discussed by others \citep{git-nosql-db}.

The requirement (\#\ref{richAnnot} above) to support rich annotations,
    suggested the NeXML data standard which was designed
    to allow arbitrarily complex annotations of the entities that are crucial to phylogenetic statements.
Because \ps does not store character data, these entities are the operational taxonomic units (OTUs), trees, nodes, and edges.

We opted to version JSON files to make it more efficient for the server to provide data for a client-side
    curation application that is written in \js (requirement \#\ref{ws} above).
We developed some syntactic conventions for converting XML to JSON tersely (described below as \nexson v1.0 and v1.2).
The adoption of these conventions reduced the web-service data payload size by appoximately 50\% relative to 
    naive representation of NeXML in JSON.
This made it more feasible to load each study into the memory of the client's browser.
Despite the departure from the NeXML syntax, the \ps maintains the ability to export and ingest NeXML files.
Fundamentally the data model of the system is the data model of NeXML.

The final requirement (\#\ref{looseOpen}) of producing a maximally open,
    loosely coupled system suggested the use of a distributed
    version control system; git is the most popular distributed version control system.
Distributed version control systems do not require a single, ``primary'' repository.
Each copy of the repository maintains a copy of the entire history, and sharing documents between
    repositories is a peer-to-peer interaction.

Most people will probably think of the copy of the \ps repository that is listed under the \otol organization on
    the GitHub website (and stored on the GitHub servers) as the canonical version of the data store.
Indeed, this is likely to be the most easily accessible and highest profile clone of the \ps repo.
Nevertheless, other users of git are free to fork that repo and maintain their own variants of the data store.
Any such clone of the \ps repository maintains the ability to pull in changes from biologists who contribute
    edits to the \otol organization clone (for example, via \otol web applications).
    
The \otol project placed all of the code for the \ps under permissive, BSD-style licenses and the
    project makes no claim of ownership to any of the data in the repository. 
For new files deposited through the web application, the interface strongly encourages application of a CC0 copyright waiver, 
    allowing for later deposition in Dryad. Other data, including those files that originate from TreeBASE,
    do not have an explicit data license (although we believe that copyright does not apply to any of the data).

In most database-driven web services, the group of core maintainers who have shell access and 
    database passwords are the only people who have full access to the data in a data store.
Posting frequent dumps of a database can allow other users to obtain local copies of the data 
    for expensive, {\em ad hoc} calculations.
However, a local version of the data is clearly a second-class instance and the maintainers of the 
    canonical version of the database have {\em de facto} ownership of the project.
We hope that adopting a truly distributed backend for the datastore will reinforce the goals
    of the \otol project to build tools that can be used and controlled by the entire community of biologists 
    (rather than a few claiming ownership on the data store in perpetuity).

Currently the \ps web services use GitHub authentication for ``curators'' who edit studies.
The requirement that editors authenticate allows the provenance of each edit to include 
    a user name for the curator, while the use of GitHub credentials allows the \otol project
    to circumvent the need to maintain a database of users and passwords (or hashes).
Thus, there is no private database that would be required for someone to fork and maintain their
    own version of the corpus (on GitHub or elsewhere).
The only private information relevant to \ps that is kept by the \otol project are the ssh-private
    keys that allow the project's web servers to push updated data to the GitHub-hosted clone of the 
    repository.

\begin{methods}
\section{Methods}
The basic workflow of a curation session is:
\begin{enumerate}
    \item \label{loadAppStep} The user loads the page in his/her browser.  This fetches the \js curator application into the web browser.
    \item \label{otiListStep} A list of studies in the system is loaded from information in a study indexing service (called ``oti'', see below).
    \item The user selects the study he/she would like to view.
    \item \label{getStudyStep} The curator application requests the study in \nexson form from the \ps server.
        The curator application also receives the git commit SHA of the 
        repository at this point.
    \item \label{browseStep} The user may browse the studies and download representations of the data in NeXML, \nexson, NEXUS\cite{NEXUS}, or Newick formats without logging in.
    \item \label{authStep} If the user wants to edit a study, he/she must have a GitHub account (which are available free of charge) and must authenticate at this point.
    \item \label{userEditStep} The curator may correct tip taxon assignments using taxonomic name resolution services (the ``taxomachine'' web services, which are described
        elsewhere) or fix the rooting information about the tree. The data model of the study is modified in the memory space of the 
        browser and maintained there until the curator chooses to save the study.
    \item \label{putStep} To save, the curator application uses an http PUT verb and includes the data (in \nexson) and the SHA.
    \item \label{validateStep} The \ps-api code validates the \nexson (rejecting the request if the data is not a legal \nexson document).
    \item \label{gitSaveStep} If the data is legal, then a new git commit is created with the SHA
        provided in the PUT request as the parent commit. The commit is place on a 
        ``work-in-progress'' branch in the git history to assure that the data is stored with 
        no chance of conflict.
    \item \label{gitMergeStep} If the study in question has not changed in the master branch 
        since the parent SHA, then the edit can safely be merged to the master branch.
        If this is the case, the merge is done and the work-in-progress branch is deleted.
        If the version of the study on the master branch {\em has} changed (e.g. if two users are simultaneously editing the same study),
        then the merge is not done. The data will be saved on the server, but not merged into the master branch.
    \item\label{gitTriggerPushStep}  If the new edit was successfully merged, then an event is triggered to tell the server to push the new master branch changes to the GitHub version
        of the repository.
    \item\label{respondStep} A response is returned to the curator code indicating whether or not the data was 
        merged to the master branch and including the new SHA that will serve as the parent for a future commit.
    \item\label{pushStep}  If the push event was triggered in step \#\ref{gitTriggerPushStep}, the updated master branch will be pushed to GitHub.
    \item\label{webHookStep} Using GitHub webhooks as a callback mechanism, the push to generates a POST that triggers reindexing
        of the affected study by the oti tool.
\end{enumerate}

\section{Implementation}
Currently the \ps is implemented in a python application using web2py for as the web framework.
Most of the functionality for validating the data and creating the git commits is accomplished using
    parts of the peyotl library (manuscript in preparation).
An alternative implementation of the web services has also written in the Pyramid
    web framework.

\subsection{thread-safety}
In the current implementation, the creation of a new commit and merge are done with git's ``checkout'', ``add'', and ``commit'' commands.
This means that the repository must use a mutual exclusion lock for the duration of these events
    to ensure that a single thread completes this series of operations.
If the system encounters heavier use, then the wrappers around git may have to 
    be modified to use lower level git commands.
There are available commands that allow one to construct a commit without checking out
    the parent commit's version of all files.
These enhancements would limit or eliminate the need to lock the repository.
\subsection{Sharding}
The \ps software supports having the data spread across multiple git respositories, which
    we refer to as ``shards.''
Currently, all of the studies fit within one git repository, so one shard suffices.
Sharding can help avoid hitting limits on git repository size (for GitHub hosting) and can 
    reduce contention for the mutex lock mentioned above.

The shard repositories contain the \nexson files and a few files that are used to 
    create a unique study ID for any new study.
Thus, inspection of the shards by the server's code allows unique IDs to be generated as long as 
    each ID-minting web service is using a distinct prefix for its IDs.
The \otol project is minting ID's using the ``ot\_'' prefix;
    files that entered the system from a different curation tool, phylografter \citep{Phylografter},
    have IDs that start with ``pg\_''
Note that most of the studies in the \ps data store were imported from phylografter.
Phylografter maintains a list of curators for each study, but the \ps data store does not
    have a detailed record of each edit that was made to each study as a part of 
    curation (because phylografter did not collect this information).

The directory structure of each shard is quite simple: a ``study'' subdirectory holds 
a series of subdirectories.
Each ID has a numeric suffix.
The ID prefix and the last two digits of this numeric suffix are used to create the name
    for a subdirectory inside the study directory.
Inside this directory, each study is in subdirectory with a name that corresponds to the study ID
    in a file name that corresponds to the ID.
So, for example, the \ps-api code knows to look for study ot\_211 at the path
    study/ot\_11/ot\_211/ot\_211.json inside the git working directory.

\subsection{Mirroring on the server}
The server running the \ps-api actually maintains two clones of data repositories.
The working clone is use to save the updated data (steps \#\ref{gitSaveStep} and \ref{gitMergeStep}  in the workflow).
These operations respond to the curator client (in step \ref{respondStep}) immediately
    after these operations complete.
To push the data to the GitHub clone of the repository, the server first pulls the master branch onto a separate
    clone of the repository.
This mirror of the repository is then locked during the push operation (step \ref{pushStep}).
This architecture keeps the working clone free to save other studies while the high-latency push operation completes.
The update of the mirror from the working clone is very fast because the clones are on the same filesystem.
Therefore, links to the objects in the git database can be used instead of copy operations.

\subsection{\nexson}
The \otol project uses 3 different version of the \nexson syntax ([KAC] and we should explain why, so as to not seem completely insane -- [CEH] this says 3 different versions but only two are described, and I dont know what the third one is...), but these
    can be easily interconverted using the peyotl library.
The \ps and curator \js application use version 1.2 and 1.0 of \nexson. 
These formats are slight tweaks to the badgerfish convention \citep{badgerfish} for mapping an XML document to JSON.
As with badgerfish, key-value pairs that are attributes in XML are recognized by adding an @ symbol before the key name.
NeXML allows for unlimited addition of ``meta'' elements inside a first-class entity to associate annotations with that entity.
The \otol project uses a set of these meta annotations to introduce information from curators into the study records.
The tags used are described at \url{https://github.com/OpenTreeOfLife/phylesystem-api/wiki/NexSON}.
In the badgerfish convention, these meta elements would be placed as \js objects inside an array associated with the ``meta'' property name.
Adhering to this convention, would require any code operating on a JSON version of NeXML to search through (potentially
    long) lists of meta objects for each piece of annotation.
The \nexson 1.0 syntax simply augments the badgerfish convention by using the \^{} character at the front of a
    property name to indicate that the key-value property that corresponds to a ``meta'' element on NeXML.
This makes the files smaller and makes property lookup faster.

The \nexson 1.2 syntax reorganizes some of the elements of a NeXML.
In this version of the syntax, the OTUs, trees, nodes, and edges are contained in objects with the IDs of the entities as keys.
In a direct badgerfish version of NeXML these entities would be objects in an array, but the order of the objects
    in these arrays is not useful.
In fact, reordering the node or edge list has no effect on the tree.
Use of object IDs as keys make object look up faster, and allows the JSON to be sorted quickly when being stored in 
    the git repository so that trivial changes (such as changing the order of nodes in a node list) will not result in 
    a difference in the stored version of the study.
These formats are documented more fully on the \ps-api wiki mentioned above.

The nexson\_validation subpackage of the peyotl library is used to ensure that a \nexson file sent to the \ps
    server is valid. The validation routines also perform re-ordering of the elements within \nexson files to
    prevent large commits that would result from, for example, re-ordering the list of OTUs in a file or
    rotating left / right children of internal nodes. 
The peyotl library (manuscript in press; see \url{http://opentreeoflife.github.io/peyotl/}) also 
    provides a variety of convenience functions for operating on \nexson files (including support
    for exporting the phylogenetic data to widely used formats such as NeXML, NEXUS, and Newick).

\subsection{indexing}
A significant downside of using git as database is the fact that the use of text files to store data does not inherently
    provide a way to perform fast lookups of arbitrary objects.
Performing text-based search across all studies (i.e. reading through all \nexson text files) in the \ps to find all nodes
    in trees that match a specific set of criteria, for instance, is a prohibitively costly operation to perform on demand.
Because the capability to search the \ps repository is required for various use-cases (e.g. various aspects of
    study curation), we implemented an additional tool called oti (which stands for open tree indexer) which parses \nexson
    documents and indexes their contents to enable fast searches across studies and their included elements (e.g. trees).
OTI is implemented in a Neo4j graph database, and its search features are exposed via publicly available web services; other
    \otol tools such as \ps and the curator application interact with oti through these web services.
Currently available search methods are simplistic, allowing queries based on single properties (e.g. searching for studies
    by a particular author, or from a particular year), or taxonomic scope (e.g. searching for all trees mapped to
    any taxon included in some specified higher taxon), but more complex queries may be added in the future.

\subsection{web hooks}
If a study has been added, deleted or edited by a user and the update could be merged to the master branch of the data store,
    then an event is triggered (step \ref{gitTriggerPushStep} above) to push the updated data to the GitHub clone
    of the repository.
This assures that the publicly visible version of the data is updated very quickly, and it also allow us to use
    GitHub web hooks to trigger other operations.
In particular, once the push has succeeded, a web hook from GitHub posts data about what studies have changed
    on the GitHub clone to a \ps service.
This hook triggers the re-indexing of the studies that have changed by the oti tool so that the searchable cache is
    kept up to date.<commit_msg>minor edit<commit_after>\documentclass{bioinfo}
\copyrightyear{2014}
\pubyear{2014}
\usepackage{xspace}
\newcommand{\ps}{phylesystem\xspace}
\newcommand{\otol}{Open Tree of Life\xspace}
\newcommand{\nexson}{otNexSON\xspace}
\newcommand{\js}{JavaScript\xspace}
\newcommand{\mthcomment}[1]{{\color{red} \textsc{#1}}\xspace}

\usepackage{natbib}
\bibliographystyle{apalike}

\usepackage{hyperref}
\hypersetup{colorlinks=true, linkcolor=black, citecolor=black, hyperindex=true, backref}
\begin{document}
\firstpage{1}
\title[phylesystem git phylostore]{Phylesystem: a git-based data store for community curated phylogenetic estimates}

\author[McTavish\textit{et~al}]{
    <NAME>,$^{1,2}$
    <NAME>.~Holder,$^{1,2}$\footnote{to whom correspondence should be addressed}~
    Ann Other Author,$^{3}$
    Ann Other Author,$^{4}$
    Ann Other Author,$^{5}$ $\ldots$
}
\address{$^{1}$Department of Ecology and Evolutionary Biology, University of Kansas, Lawrence KS, USA\\
$^{2}$Heidelberg Institute of Theoretical Studies, Heidelberg, Germany}

\history{Received on XXXXX; revised on XXXXX; accepted on XXXXX}

\editor{Associate Editor: XXXXXXX}

\maketitle

\begin{abstract}
\section{Motivation:}
Archival storage of phylogenetic estimates from published studies can be accomplished
    using general platforms, like Dryad, or TreeBase.
Those services fulfill a crucial role in helping phylogenetic studies be more transparent
    and reproducible.
However, available trees require some editing to improve the accuracy and reusability of the phylogenetic statements.
Many trees in data archives or supplemental files from publications are incorrectly rooted.
Establishing the linkage between tip labels used in a tree and taxa in a single taxonomy 
    dramatically improves the ability of other researchers to reuse phylogenetic estimates.
Because the process of curating a published phylogenetic estimate is not error-free,
    retaining a full record of the provenance edits to a tree is crucial for
    openness, allowing editors to receive credit for their work, and
    making errors introduced during curation easier to correct.

\section{Results:}
Here we report the development of software infrastructure to support the open curation of
    phylogenetic data by the community of biologists.
The backend of the system provides an interface for the standard database operations of
    creating, reading, updating, and deleting records by creating commits in a git repository.
The record of the history of edits to a tree is preserved by git's version control features.
Hosting this datastore on GitHub provides a open access to the data store using tools
    familiar to many developers.
We have deployed a server running the ``phylesystem-api'', which wraps the interactions with git and GitHub.
The \otol project has also developed and deployed a \js application that uses the \ps-api and
    other web services to enable input and curation of published phylogenetic statements
\section{Availability:}
Source code for the web-service layer is available at \url{https://github.com/OpenTreeOfLife/phylesystem-api}.\\
%The library \url{https://github.com/OpenTreeOfLife/peyotl} is a prerequisite.
The data store can be cloned from: 
\url{https://github.com/OpenTreeOfLife/phylesystem}.
A web application that uses the \ps web services is deployed
at \url{http://tree.opentreeoflife.org/curator}.
Code for that tool is available from 
\url{https://github.com/OpenTreeOfLife/opentree}.

\section{Contact:} \href{mailto:<EMAIL>}{<EMAIL>}

\end{abstract}

\section{Introduction}

Characterizing and systematizing relationships among species has been a goal of biologists since Linnaeus \cite{Linne1758}.
The phylogenetic systematics ``revolution'' of the 1960's focused most of the effort toward this goal around the 
    task of estimating phylogenetic relationships.
The rapid growth in availability of molecular data, the development of models and software implementations for
    inferring phylogenies and the appreciation of the importance of phylogenetically-aware comparative methods
    \citep[e.g.][]{Felsenstein1985Comp} have led to dramatic increases in the number phylogenetic estimates.


Unfortunately, capturing the inputs and outputs of a phylogenetic analysis in a rich, standardized form is
    difficult and error prone. There is no single standard for phylogenetic data, and developers of phylogenetic
    software often create new formats or extend existing formats in ways that make them incompatible with other programs. 
Some archiving servies, such as Dryad \citep{Dryad}, have reacted to this challenge by accepting a 
    wide range of inputs and making few or no
    guarantees to users of the database that the records will be in any particular form.
This encourages sharing of data by making the submission process fast and easy, and is advantageous under Dryad's
    general purpose archival model--Dryad's scope is not limited to phylogenetic information.
However, if the authors submitting the data are not conscientious in their explanations of the data, it can be difficult
    for users of the data to reliably extract all of the information in the archive, or the data may not contain sufficient metadata for reuse.

On the opposite end of the spectrum, some databases require data providers to conform to more rigorous
    standards with respect to input format and content.
    Since 1994, TreeBase \citep{SandersonDPE1994} and its successor TreeBase version 2 \citep{TreeBase2} have served
    as the primary archival data stores for phylogenetic estimates and the data that these trees are based on.
As of 2014, TreeBase contains 4076 studes and over 12,800 trees \citep{TreeBaseWebCite}.
Many journals encourage or require that each publication that estimates phylogenetic trees cite a TreeBase
    deposition containing the associated trees.
TreeBase produces a much more feature-rich interface for phylogenetic queries than Dryad, because each 
    TreeBase submission is parsed thoroughly and converted to a set of records in a relational database.
The downside of this approach is that it requires that submissions correspond to a more uniform format and without constant updating, that format may not reflect new types phylogenetic data being generated.

Unfortunately, file formats read and written by tree estimation tools are idiosyncratic and often so 
    terse that they omit useful information about the analysis (see \citet{StoltzfusEtAl2012} for a discussion
    of this topic and other challenges relating to the archiving of phylogenetic estimates).
As a result, the TreeBase submission process usually requires the authors of a data package to reformat their data, correct
    the rooting of the tree, alter the labels of the tips of the tree, {\em etc}.
    The TreeBase project provides a 12-minute video explaining
    \footnote{\url{http://treebase.org/treebase-web/submitTutorial.html}} 
    the non-trivial procedure of preparing a submission.
Because these steps are often taken after the analyses for a publication are complete, it is more likely 
    errors introduced in the submission process will not be corrected until an observant user tries to reuse the data.
If there were a universally used, rich file format for phylogenetics analyses, then import constraints such as those
    used by TreeBase would be less of a hurdle, since the critical metadata regarding rooting, labels, etc. could be
    stored alongside the tree itself.
The xml-based NexML specification \citep{NeXML} used internally by TreeBase defines such a format, but it is not widely used.

Thus, the current state of phyloinformatic archival infrastructure is ripe for improvement in numerous ways.
One such opportunity is the development of a datastore that allows the community of biologists to improve the
    accuracy and re-usability of published phylogenetic statements.
We describe here an implementation of one such system, which we call ``phylesystem'' because it uses a set of
    versioned text files on the filesystem (and the fact that we {\em love} bad puns).
The goal of \ps is not to replace systems like Dryad or TreeBase, but to complement them by 
    storing phylogenetic statements and associated metadata in a consistent format while retaining the history of
    edits that were made to the data themselves.
We anticipate that most of the trees stored in \ps will be associated with permanent, static archives
    elsewhere (usually either TreeBase or Dryad).

\subsection{Approach}
One of the motivations of the design of \ps was to support the \otol's need for a curated set
    of rooted trees that have been aligned to a common taxonomy.
Additionally, one of the goals of the \otol project was to support infrastructure for phylogenetic
    research in an open way that encourages the community of biologists to participate in the 
    collection and curation of our knowledge of the phylogenetic relationships of life on Earth.

Thus, our goals when designing \ps were to build: 
\begin{enumerate}
    \item  a data store capable of:
        \begin{enumerate}
            \item \label{fewKStudies} storing trees from thousands of published studies. We do not intend to store the 
                data upon which the phylogenetic estimates were based.
            \item \label{fewTreesPerStudy} storing a few exemplar trees from each study. We do not anticipate that the system will be used 
                to store thousands of trees from 
                a study (such as each sampled tree from a bootstrap or MCMC analysis, for example).
            \item \label{richAnnot} handling rich annotation of the trees, the taxa to which they refer to, and metadata describing 
                the analysis that produced the trees.
            \item \label{history} storing the full history of changes made to a study and its trees,
                including an identifier to indicate who made the changes.
        \end{enumerate}
    \item \label{ws} web services around the data store to support a user-friendly curation application run in the user's browser. These include services for validation of the files against a published schema.
    \item \label{looseOpen} a loosely coupled system that would allow the community of biologists to interact with the data in a wide variety of ways.
\end{enumerate}
From these requirements, we chose to implement \ps as a set of software wrappers around a data store
    which consists of a git \citep{git} repository of phylogenetic statements serialized as a \js Object Notation (JSON).
The data model used for the JSON is a close derivative of the NeXML standard for data interoperability\citep{NeXML}.

Our expectations that the system would have to store relatively small amount of data 
    (points \#\ref{fewKStudies} and \ref{fewTreesPerStudy} above) and that most
    studies would require relatively few edits imply that
    raw performance of the basic database operations was unlikely to be a bottleneck for most
    uses of the \ps.
This made it feasible to use text files as form of data store.
Thus far, in the six months since deployment of the study curation interface, the mean number of edits 
    per study is only \mthcomment{Need to calculate this from git history - it is a small, number though}.
The total size of the stored data (in JSON format with a line ending after 
    every field) is only around 150MB.

The requirement (\#\ref{history}, above) of maintaining a history of changes 
    (including an identifier for the editor) fits naturally with software version control systems.
We note that wiki engines such as Gollum use git version control as a backend database.
The idea of using git as general database has been discussed by others \citep{git-nosql-db}.

The requirement (\#\ref{richAnnot} above) to support rich annotations,
    suggested the NeXML data standard which was designed
    to allow arbitrarily complex annotations of the entities that are crucial to phylogenetic statements.
Because \ps does not store character data, these entities are the operational taxonomic units (OTUs), trees, nodes, and edges.

We opted to version JSON files to make it more efficient for the server to provide data for a client-side
    curation application that is written in \js (requirement \#\ref{ws} above).
We developed some syntactic conventions for converting XML to JSON tersely (described below as \nexson v1.0 and v1.2).
The adoption of these conventions reduced the web-service data payload size by appoximately 50\% relative to 
    naive representation of NeXML in JSON.
This made it more feasible to load each study into the memory of the client's browser.
Despite the departure from the NeXML syntax, the \ps maintains the ability to export and ingest NeXML files.
Fundamentally the data model of the system is the data model of NeXML.

The final requirement (\#\ref{looseOpen}) of producing a maximally open,
    loosely coupled system suggested the use of a distributed
    version control system; git is the most popular distributed version control system.
Distributed version control systems do not require a single, ``primary'' repository.
Each copy of the repository maintains a copy of the entire history, and sharing documents between
    repositories is a peer-to-peer interaction.

Most people will probably think of the copy of the \ps repository that is listed under the \otol organization on
    the GitHub website (and stored on the GitHub servers) as the canonical version of the data store.
Indeed, this is likely to be the most easily accessible and highest profile clone of the \ps repo.
Nevertheless, other users of git are free to fork that repo and maintain their own variants of the data store.
Any such clone of the \ps repository maintains the ability to pull in changes from biologists who contribute
    edits to the \otol organization clone (for example, via \otol web applications).
    
The \otol project placed all of the code for the \ps under permissive, BSD-style licenses and the
    project makes no claim of ownership to any of the data in the repository. 
For new files deposited through the web application, the interface strongly encourages application of a CC0 copyright waiver, 
    allowing for later deposition in Dryad. Other data, including those files that originate from TreeBASE,
    do not have an explicit data license (although we believe that copyright does not apply to any of the data).

In most database-driven web services, the group of core maintainers who have shell access and 
    database passwords are the only people who have full access to the data in a data store.
Posting frequent dumps of a database can allow other users to obtain local copies of the data 
    for expensive, {\em ad hoc} calculations.
However, a local version of the data is clearly a second-class instance and the maintainers of the 
    canonical version of the database have {\em de facto} ownership of the project.
We hope that adopting a truly distributed backend for the datastore will reinforce the goals
    of the \otol project to build tools that can be used and controlled by the entire community of biologists 
    (rather than a few claiming ownership on the data store in perpetuity).

Currently the \ps web services use GitHub authentication for ``curators'' who edit studies.
The requirement that editors authenticate allows the provenance of each edit to include 
    a user name for the curator, while the use of GitHub credentials allows the \otol project
    to circumvent the need to maintain a database of users and passwords (or hashes).
Thus, there is no private database that would be required for someone to fork and maintain their
    own version of the corpus (on GitHub or elsewhere).
The only private information relevant to \ps that is kept by the \otol project are the ssh-private
    keys that allow the project's web servers to push updated data to the GitHub-hosted clone of the 
    repository.

\begin{methods}
\section{Methods}
The basic workflow of a curation session is:
\begin{enumerate}
    \item \label{loadAppStep} The user loads the page in his/her browser.  This fetches the \js curator application into the web browser.
    \item \label{otiListStep} A list of studies in the system is loaded from information in a study indexing service (called ``oti'', see below).
    \item The user selects the study he/she would like to view.
    \item \label{getStudyStep} The curator application requests the study in \nexson form from the \ps server.
        The curator application also receives the git commit SHA of the 
        repository at this point.
    \item \label{browseStep} The user may browse the studies and download representations of the data in NeXML, \nexson, NEXUS\cite{NEXUS}, or Newick formats without logging in.
    \item \label{authStep} If the user wants to edit a study, he/she must have a GitHub account (which are available free of charge) and must authenticate at this point.
    \item \label{userEditStep} The curator may correct tip taxon assignments using taxonomic name resolution services (the ``taxomachine'' web services, which are described
        elsewhere) or fix the rooting information about the tree. The data model of the study is modified in the memory space of the 
        browser and maintained there until the curator chooses to save the study.
    \item \label{putStep} To save, the curator application uses an http PUT verb and includes the data (in \nexson) and the SHA.
    \item \label{validateStep} The \ps-api code validates the \nexson (rejecting the request if the data is not a legal \nexson document).
    \item \label{gitSaveStep} If the data is legal, then a new git commit is created with the SHA
        provided in the PUT request as the parent commit. The commit is place on a 
        ``work-in-progress'' branch in the git history to assure that the data is stored with 
        no chance of conflict.
    \item \label{gitMergeStep} If the study in question has not changed in the master branch 
        since the parent SHA, then the edit can safely be merged to the master branch.
        If this is the case, the merge is done and the work-in-progress branch is deleted.
        If the version of the study on the master branch {\em has} changed (e.g. if two users are simultaneously editing the same study),
        then the merge is not done. The data will be saved on the server, but not merged into the master branch.
    \item\label{gitTriggerPushStep}  If the new edit was successfully merged, then an event is triggered to tell the server to push the new master branch changes to the GitHub version
        of the repository.
    \item\label{respondStep} A response is returned to the curator code indicating whether or not the data was 
        merged to the master branch and including the new SHA that will serve as the parent for a future commit.
    \item\label{pushStep}  If the push event was triggered in step \#\ref{gitTriggerPushStep}, the updated master branch will be pushed to GitHub.
    \item\label{webHookStep} Using GitHub webhooks as a callback mechanism, the push to generates a POST that triggers reindexing
        of the affected study by the oti tool.
\end{enumerate}

\section{Implementation}
Currently the \ps is implemented in a python application using web2py for as the web framework.
Most of the functionality for validating the data and creating the git commits is accomplished using
    parts of the peyotl library (manuscript in preparation).
An alternative implementation of the web services has also written in the Pyramid
    web framework.

\subsection{thread-safety}
In the current implementation, the creation of a new commit and merge are done with git's ``checkout'', ``add'', and ``commit'' commands.
This means that the repository must use a mutual exclusion lock for the duration of these events
    to ensure that a single thread completes this series of operations.
If the system encounters heavier use, then the wrappers around git may have to 
    be modified to use lower level git commands.
There are available commands that allow one to construct a commit without checking out
    the parent commit's version of all files.
These enhancements would limit or eliminate the need to lock the repository.
\subsection{Sharding}
The \ps software supports having the data spread across multiple git respositories, which
    we refer to as ``shards.''
Currently, all of the studies fit within one git repository, so one shard suffices.
Sharding can help avoid hitting limits on git repository size (for GitHub hosting) and can 
    reduce contention for the mutex lock mentioned above.

The shard repositories contain the \nexson files and a few files that are used to 
    create a unique study ID for any new study.
Thus, inspection of the shards by the server's code allows unique IDs to be generated as long as 
    each ID-minting web service is using a distinct prefix for its IDs.
The \otol project is minting ID's using the ``ot\_'' prefix;
    files that entered the system from a different curation tool, phylografter \citep{Phylografter},
    have IDs that start with ``pg\_''
Note that most of the studies in the \ps data store were imported from phylografter.
Phylografter maintains a list of curators for each study, but the \ps data store does not
    have a detailed record of each edit that was made to each study as a part of 
    curation (because phylografter did not collect this information).

The directory structure of each shard is quite simple: a ``study'' subdirectory holds 
a series of subdirectories.
Each ID has a numeric suffix.
The ID prefix and the last two digits of this numeric suffix are used to create the name
    for a subdirectory inside the study directory.
Inside this directory, each study is in subdirectory with a name that corresponds to the study ID
    in a file name that corresponds to the ID.
So, for example, the \ps-api code knows to look for study ot\_211 at the path
    study/ot\_11/ot\_211/ot\_211.json inside the git working directory.

\subsection{Mirroring on the server}
The server running the \ps-api actually maintains two clones of data repositories.
The working clone is use to save the updated data (steps \#\ref{gitSaveStep} and \ref{gitMergeStep}  in the workflow).
These operations respond to the curator client (in step \ref{respondStep}) immediately
    after these operations complete.
To push the data to the GitHub clone of the repository, the server first pulls the master branch onto a separate
    clone of the repository.
This mirror of the repository is then locked during the push operation (step \ref{pushStep}).
This architecture keeps the working clone free to save other studies while the high-latency push operation completes.
The update of the mirror from the working clone is very fast because the clones are on the same filesystem.
Therefore, links to the objects in the git database can be used instead of copy operations.

\subsection{\nexson}
The \otol project uses 3 different version of the \nexson syntax ([KAC] and we should explain why, so as to not seem completely insane -- [CEH] this says 3 different versions but only two are described, and I dont know what the third one is...), but these
    can be easily interconverted using the peyotl library.
The \ps and curator \js application use version 1.2 and 1.0 of \nexson. 
These formats are slight tweaks to the badgerfish convention \citep{badgerfish} for mapping an XML document to JSON.
As with badgerfish, key-value pairs that are attributes in XML are recognized by adding an @ symbol before the key name.
NeXML allows for unlimited addition of ``meta'' elements inside a first-class entity to associate annotations with that entity.
The \otol project uses a set of these meta annotations to introduce information from curators into the study records.
The tags used are described at \url{https://github.com/OpenTreeOfLife/phylesystem-api/wiki/NexSON}.
In the badgerfish convention, these meta elements would be placed as \js objects inside an array associated with the ``meta'' property name.
Adhering to this convention, would require any code operating on a JSON version of NeXML to search through (potentially
    long) lists of meta objects for each piece of annotation.
The \nexson 1.0 syntax simply augments the badgerfish convention by using the \^{} character at the front of a
    property name to indicate that the key-value property that corresponds to a ``meta'' element on NeXML.
This makes the files smaller and makes property lookup faster.

The \nexson 1.2 syntax reorganizes some of the elements of a NeXML.
In this version of the syntax, the OTUs, trees, nodes, and edges are contained in objects with the IDs of the entities as keys.
In a direct badgerfish version of NeXML these entities would be objects in an array, but the order of the objects
    in these arrays is not useful.
In fact, reordering the node or edge list has no effect on the tree.
Use of object IDs as keys make object look up faster, and allows the JSON to be sorted quickly when being stored in 
    the git repository so that trivial changes (such as changing the order of nodes in a node list) will not result in 
    a difference in the stored version of the study.
These formats are documented more fully on the \ps-api wiki mentioned above.

The nexson\_validation subpackage of the peyotl library is used to ensure that a \nexson file sent to the \ps
    server is valid. The validation routines also perform re-ordering of the elements within \nexson files to
    prevent large commits that would result from, for example, re-ordering the list of OTUs in a file or
    rotating left / right children of internal nodes. 
The peyotl library (manuscript in press; see \url{http://opentreeoflife.github.io/peyotl/}) also 
    provides a variety of convenience functions for operating on \nexson files (including support
    for exporting the phylogenetic data to widely used formats such as NeXML, NEXUS, and Newick).

\subsection{indexing}
A significant downside of using git as database is the fact that the use of text files to store data does not inherently
    provide a way to perform fast lookups of arbitrary objects encoded as text within the files.
Performing text-based search across all studies (i.e. reading through all \nexson text files) in the \ps to find all nodes
    in trees that match a specific set of criteria, for instance, is a prohibitively costly operation to perform on demand.
Because the capability to search the \ps repository is required for various use-cases (e.g. various aspects of
    study curation), we implemented an additional tool called oti (which stands for open tree indexer) which parses \nexson
    documents and indexes their contents to enable fast searches across studies and their included elements (e.g. trees).
OTI is implemented in a Neo4j graph database, and its search features are exposed via publicly available web services; other
    \otol tools such as \ps and the curator application interact with oti through these web services.
Currently available search methods are simplistic, allowing queries based on single properties (e.g. searching for studies
    by a particular author, or from a particular year), or taxonomic scope (e.g. searching for all trees mapped to
    any taxon included in some specified higher taxon), but more complex queries may be added in the future.

\subsection{web hooks}
If a study has been added, deleted or edited by a user and the update could be merged to the master branch of the data store,
    then an event is triggered (step \ref{gitTriggerPushStep} above) to push the updated data to the GitHub clone
    of the repository.
This assures that the publicly visible version of the data is updated very quickly, and it also allow us to use
    GitHub web hooks to trigger other operations.
In particular, once the push has succeeded, a web hook from GitHub posts data about what studies have changed
    on the GitHub clone to a \ps service.
This hook triggers the re-indexing of the studies that have changed by the oti tool so that the searchable cache is
    kept up to date.
{'fraction_non_alphanumeric': 0.0420825369859135, 'fraction_numerical': 0.0033269625539746584, 'mean_word_length': 4.042744958058183, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 2}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4909198', 'n_tokens_mistral': 14056, 'n_tokens_neox': 13134, 'n_words': 8364}