Fossil

Check-in [2b3569d1]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add a reference to the idea of a "Conflict-Free Replicated Datatypes" to the sync documentation.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 2b3569d19f207e2dd02f7f685a0deb18da69a010624a138ca2b77f6c427ac486
User & Date: drh 2019-07-10 22:19:33.332
Context
2019-07-11
12:19
Make sure the backoffice does not try to reuse file descriptors that it has previously closed. ... (check-in: 458ced35 user: drh tags: trunk)
2019-07-10
22:19
Add a reference to the idea of a "Conflict-Free Replicated Datatypes" to the sync documentation. ... (check-in: 2b3569d1 user: drh tags: trunk)
18:55
Update the built-in SQLite to the 3.29.0 release. ... (check-in: 8c9eeb01 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to www/hacker-howto.wiki.
1
2
3
4
5
6
7
8
9
10
11
12

13
14
15
16
<title>Fossil Hackers How-To</title>

The following links are of interest to programmers who want to modify
or enhance Fossil.  Ordinary users can safely ignore this information.

  *  [./build.wiki | How To Compile And Install Fossil]
  *  [./customskin.md | Theming Fossil]
  *  [./makefile.wiki | The Fossil Build Process]
  *  [./tech_overview.wiki | A Technical Overview of Fossil]
  *  [./adding_code.wiki | Adding Features To Fossil]
  *  [./contribute.wiki|Contributing Code Or Enhancements To The Fossil Project]
  *  [./fileformat.wiki|Fossil Artifact File Format]

  *  [./style.wiki | Coding Style Guidelines]
  *  [./checkin.wiki | Pre-checkin Checklist]
  *  [../test/release-checklist.wiki | Release Checklist]
  *  [./backoffice.md | The "backoffice" subsystem]












>




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<title>Fossil Hackers How-To</title>

The following links are of interest to programmers who want to modify
or enhance Fossil.  Ordinary users can safely ignore this information.

  *  [./build.wiki | How To Compile And Install Fossil]
  *  [./customskin.md | Theming Fossil]
  *  [./makefile.wiki | The Fossil Build Process]
  *  [./tech_overview.wiki | A Technical Overview of Fossil]
  *  [./adding_code.wiki | Adding Features To Fossil]
  *  [./contribute.wiki|Contributing Code Or Enhancements To The Fossil Project]
  *  [./fileformat.wiki|Fossil Artifact File Format]
  *  [./sync.wiki|The Sync Protocol]
  *  [./style.wiki | Coding Style Guidelines]
  *  [./checkin.wiki | Pre-checkin Checklist]
  *  [../test/release-checklist.wiki | Release Checklist]
  *  [./backoffice.md | The "backoffice" subsystem]
Changes to www/sync.wiki.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

















35
36
37
38
39
40
41
<title>The Fossil Sync Protocol</title>

<p>This document describes the wire protocol used to synchronize
content between two Fossil repositories.</p>

<h2>1.0 Overview</h2>

<p>The global state of a fossil repository consists of an unordered
collection of artifacts.  Each artifact is identified by a cryptographic
hash of its content, expressed as a lower-case hexadecimal string.
Synchronization is the process of sharing artifacts between
servers so that all servers have copies of all artifacts.  Because
artifacts are unordered, the order in which artifacts are received
at a server is inconsequential.  It is assumed that the hash names
of artifacts are unique - that every artifact has a different hash.
To a first approximation, synchronization proceeds by sharing lists
hash values for available artifacts, then sharing the content of artifacts
whose names are missing from one side or the other of the connection.
In practice, a repository might contain millions of artifacts.  The list of
hash names for this many artifacts can be large.  So optimizations are
employed that usually reduce the number of hashes that need to be
shared to a few hundred.</p>

<p>Each repository also has local state.  The local state determines
the web-page formatting preferences, authorized users, ticket formats,
and similar information that varies from one repository to another.
The local state is not using transferred during a sync.  Except,
some local state is transferred during a [/help?cmd=clone|clone]
in order to initialize the local state of the new repository.  Also,
an administrator can sync local state using
the [/help?cmd=configuration|config push] and
[/help?cmd=configuration|config pull]
commands.



















<h2>2.0 Transport</h2>

<p>All communication between client and server is via HTTP requests.
The server is listening for incoming HTTP requests.  The client
issues one or more HTTP requests and receives replies for each
request.</p>











|

|












|







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
<title>The Fossil Sync Protocol</title>

<p>This document describes the wire protocol used to synchronize
content between two Fossil repositories.</p>

<h2>1.0 Overview</h2>

<p>The global state of a fossil repository consists of an unordered
collection of artifacts.  Each artifact is identified by a cryptographic
hash of its content, expressed as a lower-case hexadecimal string.
Synchronization is the process of sharing artifacts between
repositories so that all repositories have copies of all artifacts.  Because
artifacts are unordered, the order in which artifacts are received
is unimportant.  It is assumed that the hash names
of artifacts are unique - that every artifact has a different hash.
To a first approximation, synchronization proceeds by sharing lists
hash values for available artifacts, then sharing the content of artifacts
whose names are missing from one side or the other of the connection.
In practice, a repository might contain millions of artifacts.  The list of
hash names for this many artifacts can be large.  So optimizations are
employed that usually reduce the number of hashes that need to be
shared to a few hundred.</p>

<p>Each repository also has local state.  The local state determines
the web-page formatting preferences, authorized users, ticket formats,
and similar information that varies from one repository to another.
The local state is not usually transferred during a sync.  Except,
some local state is transferred during a [/help?cmd=clone|clone]
in order to initialize the local state of the new repository.  Also,
an administrator can sync local state using
the [/help?cmd=configuration|config push] and
[/help?cmd=configuration|config pull]
commands.

<a name="crdt"></a>
<h3>1.1 Conflict-Free Replicated Datatypes</h3>

<p>The "bag of artifacts" data model used by Fossil
Fossil is apparently an implementation of a particular 
[https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type|Conflict-Free Replicated
Datatype (CRDT)]
called a "G-Set" or "Grow-only Set".
The academic literature on CRDTs only began to appear in about 2011, and
Fossil predates that research by at least 4 years.  But it is nice to know
that theorists have now proven that the underlying data model of Fossil can
provide strongly-consistent replicas using only peer-to-peer communication
and without any kind of central authority.</p>

<p>If you are already familiar with CRDTs and were wondering if Fossil
used them, the answer is "yes".  We just don't call them by that name.</p>


<h2>2.0 Transport</h2>

<p>All communication between client and server is via HTTP requests.
The server is listening for incoming HTTP requests.  The client
issues one or more HTTP requests and receives replies for each
request.</p>
50
51
52
53
54
55
56








57
58
59
60
61
62
63
The important point is that the server is listening for requests and
the client is the issuer of the requests.</p>

<p>A single push, pull, or sync might involve multiple HTTP requests.
The client maintains state between all requests.  But on the server
side, each request is independent.  The server does not preserve
any information about the client from one request to the next.</p>









<h4>2.0.1 Encrypted Transport</h4>

<p>In the current implementation of Fossil, the server only
understands HTTP requests.  The client can send either
clear-text HTTP requests or encrypted HTTPS requests.  But when
HTTPS requests are sent, they first must be decrypted by a webserver







>
>
>
>
>
>
>
>







67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
The important point is that the server is listening for requests and
the client is the issuer of the requests.</p>

<p>A single push, pull, or sync might involve multiple HTTP requests.
The client maintains state between all requests.  But on the server
side, each request is independent.  The server does not preserve
any information about the client from one request to the next.</p>

<p>Note: Throughout this article, we use the terms "server" and "client"
to represent the listener and initiator of the interaction, respectively.
Nothing in this protocol requires that the server actually be a back-room
processor housed in a datacenter, nor does the client need to be a desktop
or handheld device.  For the purposes of this article "client" simply means
the repository that initiates the conversation and "server" is the repository
that responds.  Nothing more.</p>

<h4>2.0.1 Encrypted Transport</h4>

<p>In the current implementation of Fossil, the server only
understands HTTP requests.  The client can send either
clear-text HTTP requests or encrypted HTTPS requests.  But when
HTTPS requests are sent, they first must be decrypted by a webserver