Fossil SCM
Add a reference to the idea of a "Conflict-Free Replicated Datatypes" to the sync documentation.
Commit
2b3569d19f207e2dd02f7f685a0deb18da69a010624a138ca2b77f6c427ac486
Parent
8c9eeb015191df0…
2 files changed
+1
+28
-3
| --- www/hacker-howto.wiki | ||
| +++ www/hacker-howto.wiki | ||
| @@ -8,9 +8,10 @@ | ||
| 8 | 8 | * [./makefile.wiki | The Fossil Build Process] |
| 9 | 9 | * [./tech_overview.wiki | A Technical Overview of Fossil] |
| 10 | 10 | * [./adding_code.wiki | Adding Features To Fossil] |
| 11 | 11 | * [./contribute.wiki|Contributing Code Or Enhancements To The Fossil Project] |
| 12 | 12 | * [./fileformat.wiki|Fossil Artifact File Format] |
| 13 | + * [./sync.wiki|The Sync Protocol] | |
| 13 | 14 | * [./style.wiki | Coding Style Guidelines] |
| 14 | 15 | * [./checkin.wiki | Pre-checkin Checklist] |
| 15 | 16 | * [../test/release-checklist.wiki | Release Checklist] |
| 16 | 17 | * [./backoffice.md | The "backoffice" subsystem] |
| 17 | 18 |
| --- www/hacker-howto.wiki | |
| +++ www/hacker-howto.wiki | |
| @@ -8,9 +8,10 @@ | |
| 8 | * [./makefile.wiki | The Fossil Build Process] |
| 9 | * [./tech_overview.wiki | A Technical Overview of Fossil] |
| 10 | * [./adding_code.wiki | Adding Features To Fossil] |
| 11 | * [./contribute.wiki|Contributing Code Or Enhancements To The Fossil Project] |
| 12 | * [./fileformat.wiki|Fossil Artifact File Format] |
| 13 | * [./style.wiki | Coding Style Guidelines] |
| 14 | * [./checkin.wiki | Pre-checkin Checklist] |
| 15 | * [../test/release-checklist.wiki | Release Checklist] |
| 16 | * [./backoffice.md | The "backoffice" subsystem] |
| 17 |
| --- www/hacker-howto.wiki | |
| +++ www/hacker-howto.wiki | |
| @@ -8,9 +8,10 @@ | |
| 8 | * [./makefile.wiki | The Fossil Build Process] |
| 9 | * [./tech_overview.wiki | A Technical Overview of Fossil] |
| 10 | * [./adding_code.wiki | Adding Features To Fossil] |
| 11 | * [./contribute.wiki|Contributing Code Or Enhancements To The Fossil Project] |
| 12 | * [./fileformat.wiki|Fossil Artifact File Format] |
| 13 | * [./sync.wiki|The Sync Protocol] |
| 14 | * [./style.wiki | Coding Style Guidelines] |
| 15 | * [./checkin.wiki | Pre-checkin Checklist] |
| 16 | * [../test/release-checklist.wiki | Release Checklist] |
| 17 | * [./backoffice.md | The "backoffice" subsystem] |
| 18 |
+28
-3
| --- www/sync.wiki | ||
| +++ www/sync.wiki | ||
| @@ -7,13 +7,13 @@ | ||
| 7 | 7 | |
| 8 | 8 | <p>The global state of a fossil repository consists of an unordered |
| 9 | 9 | collection of artifacts. Each artifact is identified by a cryptographic |
| 10 | 10 | hash of its content, expressed as a lower-case hexadecimal string. |
| 11 | 11 | Synchronization is the process of sharing artifacts between |
| 12 | -servers so that all servers have copies of all artifacts. Because | |
| 12 | +repositories so that all repositories have copies of all artifacts. Because | |
| 13 | 13 | artifacts are unordered, the order in which artifacts are received |
| 14 | -at a server is inconsequential. It is assumed that the hash names | |
| 14 | +is unimportant. It is assumed that the hash names | |
| 15 | 15 | of artifacts are unique - that every artifact has a different hash. |
| 16 | 16 | To a first approximation, synchronization proceeds by sharing lists |
| 17 | 17 | hash values for available artifacts, then sharing the content of artifacts |
| 18 | 18 | whose names are missing from one side or the other of the connection. |
| 19 | 19 | In practice, a repository might contain millions of artifacts. The list of |
| @@ -22,18 +22,35 @@ | ||
| 22 | 22 | shared to a few hundred.</p> |
| 23 | 23 | |
| 24 | 24 | <p>Each repository also has local state. The local state determines |
| 25 | 25 | the web-page formatting preferences, authorized users, ticket formats, |
| 26 | 26 | and similar information that varies from one repository to another. |
| 27 | -The local state is not using transferred during a sync. Except, | |
| 27 | +The local state is not usually transferred during a sync. Except, | |
| 28 | 28 | some local state is transferred during a [/help?cmd=clone|clone] |
| 29 | 29 | in order to initialize the local state of the new repository. Also, |
| 30 | 30 | an administrator can sync local state using |
| 31 | 31 | the [/help?cmd=configuration|config push] and |
| 32 | 32 | [/help?cmd=configuration|config pull] |
| 33 | 33 | commands. |
| 34 | 34 | |
| 35 | +<a name="crdt"></a> | |
| 36 | +<h3>1.1 Conflict-Free Replicated Datatypes</h3> | |
| 37 | + | |
| 38 | +<p>The "bag of artifacts" data model used by Fossil | |
| 39 | +Fossil is apparently an implementation of a particular | |
| 40 | +[https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type|Conflict-Free Replicated | |
| 41 | +Datatype (CRDT)] | |
| 42 | +called a "G-Set" or "Grow-only Set". | |
| 43 | +The academic literature on CRDTs only began to appear in about 2011, and | |
| 44 | +Fossil predates that research by at least 4 years. But it is nice to know | |
| 45 | +that theorists have now proven that the underlying data model of Fossil can | |
| 46 | +provide strongly-consistent replicas using only peer-to-peer communication | |
| 47 | +and without any kind of central authority.</p> | |
| 48 | + | |
| 49 | +<p>If you are already familiar with CRDTs and were wondering if Fossil | |
| 50 | +used them, the answer is "yes". We just don't call them by that name.</p> | |
| 51 | + | |
| 35 | 52 | |
| 36 | 53 | <h2>2.0 Transport</h2> |
| 37 | 54 | |
| 38 | 55 | <p>All communication between client and server is via HTTP requests. |
| 39 | 56 | The server is listening for incoming HTTP requests. The client |
| @@ -52,10 +69,18 @@ | ||
| 52 | 69 | |
| 53 | 70 | <p>A single push, pull, or sync might involve multiple HTTP requests. |
| 54 | 71 | The client maintains state between all requests. But on the server |
| 55 | 72 | side, each request is independent. The server does not preserve |
| 56 | 73 | any information about the client from one request to the next.</p> |
| 74 | + | |
| 75 | +<p>Note: Throughout this article, we use the terms "server" and "client" | |
| 76 | +to represent the listener and initiator of the interaction, respectively. | |
| 77 | +Nothing in this protocol requires that the server actually be a back-room | |
| 78 | +processor housed in a datacenter, nor does the client need to be a desktop | |
| 79 | +or handheld device. For the purposes of this article "client" simply means | |
| 80 | +the repository that initiates the conversation and "server" is the repository | |
| 81 | +that responds. Nothing more.</p> | |
| 57 | 82 | |
| 58 | 83 | <h4>2.0.1 Encrypted Transport</h4> |
| 59 | 84 | |
| 60 | 85 | <p>In the current implementation of Fossil, the server only |
| 61 | 86 | understands HTTP requests. The client can send either |
| 62 | 87 |
| --- www/sync.wiki | |
| +++ www/sync.wiki | |
| @@ -7,13 +7,13 @@ | |
| 7 | |
| 8 | <p>The global state of a fossil repository consists of an unordered |
| 9 | collection of artifacts. Each artifact is identified by a cryptographic |
| 10 | hash of its content, expressed as a lower-case hexadecimal string. |
| 11 | Synchronization is the process of sharing artifacts between |
| 12 | servers so that all servers have copies of all artifacts. Because |
| 13 | artifacts are unordered, the order in which artifacts are received |
| 14 | at a server is inconsequential. It is assumed that the hash names |
| 15 | of artifacts are unique - that every artifact has a different hash. |
| 16 | To a first approximation, synchronization proceeds by sharing lists |
| 17 | hash values for available artifacts, then sharing the content of artifacts |
| 18 | whose names are missing from one side or the other of the connection. |
| 19 | In practice, a repository might contain millions of artifacts. The list of |
| @@ -22,18 +22,35 @@ | |
| 22 | shared to a few hundred.</p> |
| 23 | |
| 24 | <p>Each repository also has local state. The local state determines |
| 25 | the web-page formatting preferences, authorized users, ticket formats, |
| 26 | and similar information that varies from one repository to another. |
| 27 | The local state is not using transferred during a sync. Except, |
| 28 | some local state is transferred during a [/help?cmd=clone|clone] |
| 29 | in order to initialize the local state of the new repository. Also, |
| 30 | an administrator can sync local state using |
| 31 | the [/help?cmd=configuration|config push] and |
| 32 | [/help?cmd=configuration|config pull] |
| 33 | commands. |
| 34 | |
| 35 | |
| 36 | <h2>2.0 Transport</h2> |
| 37 | |
| 38 | <p>All communication between client and server is via HTTP requests. |
| 39 | The server is listening for incoming HTTP requests. The client |
| @@ -52,10 +69,18 @@ | |
| 52 | |
| 53 | <p>A single push, pull, or sync might involve multiple HTTP requests. |
| 54 | The client maintains state between all requests. But on the server |
| 55 | side, each request is independent. The server does not preserve |
| 56 | any information about the client from one request to the next.</p> |
| 57 | |
| 58 | <h4>2.0.1 Encrypted Transport</h4> |
| 59 | |
| 60 | <p>In the current implementation of Fossil, the server only |
| 61 | understands HTTP requests. The client can send either |
| 62 |
| --- www/sync.wiki | |
| +++ www/sync.wiki | |
| @@ -7,13 +7,13 @@ | |
| 7 | |
| 8 | <p>The global state of a fossil repository consists of an unordered |
| 9 | collection of artifacts. Each artifact is identified by a cryptographic |
| 10 | hash of its content, expressed as a lower-case hexadecimal string. |
| 11 | Synchronization is the process of sharing artifacts between |
| 12 | repositories so that all repositories have copies of all artifacts. Because |
| 13 | artifacts are unordered, the order in which artifacts are received |
| 14 | is unimportant. It is assumed that the hash names |
| 15 | of artifacts are unique - that every artifact has a different hash. |
| 16 | To a first approximation, synchronization proceeds by sharing lists |
| 17 | hash values for available artifacts, then sharing the content of artifacts |
| 18 | whose names are missing from one side or the other of the connection. |
| 19 | In practice, a repository might contain millions of artifacts. The list of |
| @@ -22,18 +22,35 @@ | |
| 22 | shared to a few hundred.</p> |
| 23 | |
| 24 | <p>Each repository also has local state. The local state determines |
| 25 | the web-page formatting preferences, authorized users, ticket formats, |
| 26 | and similar information that varies from one repository to another. |
| 27 | The local state is not usually transferred during a sync. Except, |
| 28 | some local state is transferred during a [/help?cmd=clone|clone] |
| 29 | in order to initialize the local state of the new repository. Also, |
| 30 | an administrator can sync local state using |
| 31 | the [/help?cmd=configuration|config push] and |
| 32 | [/help?cmd=configuration|config pull] |
| 33 | commands. |
| 34 | |
| 35 | <a name="crdt"></a> |
| 36 | <h3>1.1 Conflict-Free Replicated Datatypes</h3> |
| 37 | |
| 38 | <p>The "bag of artifacts" data model used by Fossil |
| 39 | Fossil is apparently an implementation of a particular |
| 40 | [https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type|Conflict-Free Replicated |
| 41 | Datatype (CRDT)] |
| 42 | called a "G-Set" or "Grow-only Set". |
| 43 | The academic literature on CRDTs only began to appear in about 2011, and |
| 44 | Fossil predates that research by at least 4 years. But it is nice to know |
| 45 | that theorists have now proven that the underlying data model of Fossil can |
| 46 | provide strongly-consistent replicas using only peer-to-peer communication |
| 47 | and without any kind of central authority.</p> |
| 48 | |
| 49 | <p>If you are already familiar with CRDTs and were wondering if Fossil |
| 50 | used them, the answer is "yes". We just don't call them by that name.</p> |
| 51 | |
| 52 | |
| 53 | <h2>2.0 Transport</h2> |
| 54 | |
| 55 | <p>All communication between client and server is via HTTP requests. |
| 56 | The server is listening for incoming HTTP requests. The client |
| @@ -52,10 +69,18 @@ | |
| 69 | |
| 70 | <p>A single push, pull, or sync might involve multiple HTTP requests. |
| 71 | The client maintains state between all requests. But on the server |
| 72 | side, each request is independent. The server does not preserve |
| 73 | any information about the client from one request to the next.</p> |
| 74 | |
| 75 | <p>Note: Throughout this article, we use the terms "server" and "client" |
| 76 | to represent the listener and initiator of the interaction, respectively. |
| 77 | Nothing in this protocol requires that the server actually be a back-room |
| 78 | processor housed in a datacenter, nor does the client need to be a desktop |
| 79 | or handheld device. For the purposes of this article "client" simply means |
| 80 | the repository that initiates the conversation and "server" is the repository |
| 81 | that responds. Nothing more.</p> |
| 82 | |
| 83 | <h4>2.0.1 Encrypted Transport</h4> |
| 84 | |
| 85 | <p>In the current implementation of Fossil, the server only |
| 86 | understands HTTP requests. The client can send either |
| 87 |