git db
decentralized data storage in git
Disclaimer: a lot of the information on this page is the result of the author's own knowledge and experience and should currently be counted as expert opinion grade but not yet proven or formally described.
git db as a standard is relatively neutral to how the data is shared. Actually, git itself solves a number of the mechanical aspect of distribution problems. The question frequently becomes, which version is considered the "master"?
The answer to this depends a lot on what the objectives of the program are. There are problems which distributing may help solve, such as scaling to truly massive sets of data, extra computing power to service a lot of requests, or resilience in the face of disasters. There are compromises to be made, such as whether results must be guaranteed or whether a "best effort" approach is acceptable.
The CAP theorem describes these trade-offs; sacrificing Consistency to allow tolerance to network Partitions and supply high Availability - BASE systems fall into this category - or whether Consistency (the "C" in ACID) must be maintained, at the expense of either Availability (distributed systems which shut down when there is a partition), or tolerance to network Partitions (implying that systems must all be on the same network).
The git db should support all of these styles of replication, through configuration - not necessarily settings in a config file or dialog box, but how the application is configured to use which facility of the git db. Mixed modes are possible, but in general more restrictive systems will not be able to share information with less restrictive systems.
In this mode, there is a single node which is the only one allowed to do updates.
An example of application here is "decentralised social networks"; holding the databases that people collaboratively edit with each other, be it a friends list or a photo collection catalogue. Yet, many other nodes have an interest in receiving the information. Each person is the master of their own database, and everyone else's versions are comments or suggestions and are not automatically promoted to be the master.
This is the easiest mode to support; assuming that the single node for updates does not change, there are no conflicts to resolve.
This case matches the majority of traditional replication systems out there.
The distribution protocol for this can be standard git protocol.
This mode of replication is appropriate for systems where the list of changes going into the system are known accurately, and there must be no conflicting answers.
In this case, the nodes must always return the same result and be Consistent. Overall, the system must behave as an ACID system; transactions must be able to be applied serially and obtain equivalent results. To achieve this, a system called 2 Phase Commit is generally employed, where commits which are "ready" to apply are voted on by participating nodes and the real result moves forward once there is agreement.
The system may provide geographical dispersion guarantees on returned answers, limiting performance but making the system very robust to localized disasters. Non-repudiating systems may take this form.
Examples of systems that work like this are clustered ACID databases (eg Oracle) and the transaction support in earlier versions of CouchDB.
The interchange of messages relating to this replication could have a protocol designed for it, or likely a redundant message queue system like AQMP could just be re-used.
This mode of replication is similar to Multi-Master, but several requirements are relaxed. It is assumed that any two conflicting updates can be resolved - called "eventual consistency" (the E in the bacronym BASE). More than one node may produce valid updates.
This approach matches the replication approach of many stored-procedure based database replication systems, such as Bucardo. Also, current versions of CouchDB.
An advantage of this style of replication is that it doesn't need a new protocol, you can just synchronize revisions and then apply the merge resolution rules. It does however require a way to specify those merge resolution rules -- for instance, in-store functions.
This is the proposed label for a cluster of multi-master nodes, where no node is trusted fully but every node is trusted equally; a voting system is used to resolve possible conflicts and auditing is possible. Additionally, it may be possible to relax strict requirements about knowing the input requests - answers to these questions should be available once more research is completed.
This is a similar use case to the Strict Multi-Master protocol, however the use of an existing message queue system or some kind of cluster "supervisor" process are not allowed, and the system should be capable of operation with each node acting in rational self-interest only.
The system of dividing tables can be used to take large sets of data and partition them in either custom ways when using a primary key, or randomly when using a UUID or a hash for the primary key.
As the full data set is not required when computing results involving the partitioned chunks - just the SHA1 sums - nodes with incomplete information can compute some limited results as if they had the full set.
While this doesn't in principal require a new protocol, the entire query system will need to be structured so that it can divide the work by the submodules present in the repository, and farm them out to nodes which have those submodules. This is likely a complex approach, but it does have at least one small piece of elegance, in that each small piece of the database can be cloned with standard git.