<commit_before>#+TITLE: geschichte
#+TAGS: bug feature review theory
#+TODO: TODO(t) STARTED(s) DONE(d) 
#+TODO: CANCELED(c@)
#+CATEGORY: geschichte
#+STARTUP: overview 
#+STARTUP: hidestars
#+PROPERTY: Assigned_to_ALL kordano whilo

* geschichte

`geschichte` (meaning history in German) is a distributed eventual consistent database for web applications. Instead of programming thin web-clients around a central server/cloud, you operate on your local data like a native application both on client- and (if you wish to) server-side. You can also view it in reverse as a cloud being expanded to all end-points.
Commit whenever you want and access values whenever you want no matter if the remote peer (server) is *available* or not. You can imagine it as a `git` for [[https://github.com/edn-format/edn][edn]] database + automatic eventual consistent synchronization. The motivation is to share data openly and develop applications on shared well-defined data carrying over the immutable value semantics of [[http://clojure.org/][Clojure]]. This allows not only to fork code, but much more importantly to fork the data of applications and extend it in unplanned ways.
The tradeoff is that your application may have to support after-the-fact conflict resolution, which can be achieved fairly easily with strict data-models like [[https://github.com/tonsky/datascript][datascript]], but in some cases users will have to decide conflicts.

A prototype application, with an example deployment, can be found here: [[(https://github.com/ghubber/topiq][topiq]].

** Usage

Use this to store your application state, e.g. with `datascript` and `om`, to easily compose applications and data. You need to create a `peer` and potentially a `stage` or `pull-hooks`.

** Design

geschichte consists of two parts, a core of [CRDTs](http://hal.inria.fr/docs/00/55/55/88/PDF/techreport.pdf), especially a new design for a repository in the `geschichte.crdt.repo` namespaces, and a generic replication protocol for CRDTs in `geschichte.replicate` and some middlewares. The replication can be extended for any CRDT and we will try to provide as many implementations as possible by default. Together the CRDTs and the replication provide conflict-free synchronization. They decouple resolution of application level conflicts from synchronization over a network.

The replication protocol partitions the global state space into user specific places for CRDTs, `[email crdt-id]`, possibly further dividing this inside the CRDT into identities (e.g. branches). All replication happens between these places. All peers automatically synchronize CRDTs of each user they subscribe to and push changes as soon as they have all data.

We make heavy use of [core.async](https://github.com/clojure/core.async) to model peers platform- and network-agnostic just as peers having a pair of messaging channels for `edn` messages. We build on platform-neutral durable storage through [konserve](https://github.com/ghubber/konserve). At the core is a `pub-sub` scheme between peers, but most functionality is factored into `middlewares` filtering and tweaking the in/out channel pair of each peers pub-sub core. This allows decoupled extension of the network protocol.

For detailed documentation of the repository CRDT look at the [introduction](http://ghubber.github.io/geschichte/). Or to understand the [pub-sub message protocol for synching](http://ghubber.github.io/geschichte/synching.html).

* Repository CRDT

For the special repository CRDT implicit conflicts might occur (if a device is offline for instance). But committing to the same CRDT on different peers in general is not supposed to be the best way to organize distributed writes. Instead, explicit pulling or merging between branches or users allows for supervised pulls or merges under each user's control, e.g. through pull-hooks or supervised on stage.

** Twisting CAP

Having distributed writes in any system puts it under the restrictions of the [[https://en.wikipedia.org/wiki/CAP_theorem][CAP theorem]]. Similar to `git` there is no design-level decision of how to deal with breaks of consistency and how to modulate convergence. So feel free to organize different write schemes, from a singular writer like Datomic to a totally distributed landscape of non-consistent always available repositories (like git) are possible. Ideally some preconfigurable schemes should emerge.

*** Scheme 0: Personal applications

For "high-level", low write-throughput data (like a port of a classical desktop application for personal data management) which is not immediately synchronized in a global state between several users by your application, everything is fine and you don't need to worry about CAP. An example would be a personal address book manager, a personal todo app, ... All you need to do is cover conflict resolution.

*** Scheme 1: Tree of coordinators

The currently supposed coordination around writes is a Linux kernel-development inspired tree like structure of synching groups consisting of one central user (e.g. user corresponding to the state of the application/database on the server) we call the `coordinator`.

The **coordinator**:

1. tracks changes in all authenticated users clones
2. checks for integrity
3. pulls and hence decides on a new upstream value
4. and propagates it back to all peers
5. users pull *and* merge any changes

Latency differences between users together with a high volume of writes can cause the network to diverge, because high latency peers have no chance anymore to be pulled from and diverge from the coordinator. To avoid a runaway effect in this scenario we introduce a delay cost to merge gradually rising with the ratio of merges vs. normal commits in the repository on user-side. In CAP terms we reduce availability, but do not directly gain consistency, only limit divergence.
In this scenario the application is supposed to notify each user about the diverged state and if this persists, recommend joining a lower write-intensive coordinator. Coordinators then form a tree around the central coordinator themselves being users. This reassignment can be done automatically on server side (but has not been worked out yet) corresponding to load-balancing, a P2P load-balancer is also conceivable.

** JavaScript

It is supposed to work from JavaScript as well, ping me and I will have a look what is necessary to make interop more painfree if you have problems.

*Any help or patches are very welcome :-)*

** TODOs for a first release

- Define CRDT Algebra for synching and repo. Use downstream ops of INRIA techreport [DONE]
- Allow dual op-based vs. state-based representation of a CRDT for constant time synching [DONE]
- Give message exchanges unique id to track pub-sub exchanges without network topology. [DONE]
- Refactor core replication to break apart from repository CRDT [MOSTLY DONE]
- Handle tag-table for messaging (transit?).

- Rename all messaging: remove ambiguous "meta" terminology :meta-pub -> :crdt/pub, :metas->:pubs, :transactions -> :prepared (?) ...
- Reactivate cljs port

- Visualize repo state.

** Roadmap

- Atomic cross-CRDT updates.
- Partially propagate updates and allow them to be delayed and reassembled again to stay atomic?
- Make usage from JavaScript straightforward (including JSON values). Browser and nodejs.
- Passwordless authentication (and authorisation) based on email verification or password and inter-peer trust network as p2p middleware.
- Implement useful CRDTs from techreview and other papers and ship by default.
- Allow management of subscriptions of peers.
- Limit inline value size, avoid pulling huge fetched values in memory. Distribute bandwidth between CRDTs.
- Negotiate middlewares with versioning.
- Build extendable command and control interface for peers (middleware?).
- Encryption of transaction with repo key encrypted by userkeys, public key schema, explore pub/private key solutions. Maybe metadata signing can work (slowly) on a DHT?
- Add a basic web toolbar for applications to communicate their synching state to the user in a uniform way.
- Provide example for durable undo and redo for `react`-like applications.
- Make peers and stage records(?).
- Implement diverse prototypes, from real-time to "big-data".
- Evaluate lowest-common-ancestor algorithms if merging becomes too expansive.
  See also [[http://slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search#btnNext][lca in haskell (including repository monad)]]

*** TODOs
**** TODO fix geschichte example 					:bug:
    :PROPERTIES:
    :Assigned_to: kordano
    :END:
**** TODO go macros 						    :feature:
    :PROPERTIES:
    :Assigned_to: whilo
    :END:
    - Note taken on [2015-06-17 Mi 13:07] \\
      see full-async
**** TODO build cljs repl 					    :feature:
    DEADLINE: <2015-06-19 Fr>
    :PROPERTIES:
    :Assigned_to: kordano 
    :END:
**** TODO fix pull-hooks 						:bug:
    :PROPERTIES:
    :Assigned_to: whilo
    :END:
**** TODO create crdt bibliography 				     :theory:
    DEADLINE: <2015-06-22 Mo>
    :PROPERTIES:
    :Assigned_to: whilo
    :END:
** License

Copyright © 2013-2015 <NAME> & <NAME>

Distributed under the Eclipse Public License, the same as Clojure.<commit_msg>adjust readme org<commit_after>#+TITLE: geschichte
#+TAGS: bug feature review theory
#+TODO: TODO(t) STARTED(s) DONE(d) 
#+TODO: CANCELED(c@)
#+CATEGORY: geschichte
#+STARTUP: overview 
#+STARTUP: hidestars
#+PROPERTY: Assigned_to_ALL kordano whilo

* geschichte

`geschichte` (meaning history in German) is a distributed eventual consistent database for web applications. Instead of programming thin web-clients around a central server/cloud, you operate on your local data like a native application both on client- and (if you wish to) server-side. You can also view it in reverse as a cloud being expanded to all end-points.
Commit whenever you want and access values whenever you want no matter if the remote peer (server) is *available* or not. You can imagine it as a `git` for [[https://github.com/edn-format/edn][edn]] database + automatic eventual consistent synchronization. The motivation is to share data openly and develop applications on shared well-defined data carrying over the immutable value semantics of [[http://clojure.org/][Clojure]]. This allows not only to fork code, but much more importantly to fork the data of applications and extend it in unplanned ways.
The tradeoff is that your application may have to support after-the-fact conflict resolution, which can be achieved fairly easily with strict data-models like [[https://github.com/tonsky/datascript][datascript]], but in some cases users will have to decide conflicts.

A prototype application, with an example deployment, can be found here: [[(https://github.com/ghubber/topiq][topiq]].

** Usage

Use this to store your application state, e.g. with `datascript` and `om`, to easily compose applications and data. You need to create a `peer` and potentially a `stage` or `pull-hooks`.

** Design

geschichte consists of two parts, a core of [CRDTs](http://hal.inria.fr/docs/00/55/55/88/PDF/techreport.pdf), especially a new design for a repository in the `geschichte.crdt.repo` namespaces, and a generic replication protocol for CRDTs in `geschichte.replicate` and some middlewares. The replication can be extended for any CRDT and we will try to provide as many implementations as possible by default. Together the CRDTs and the replication provide conflict-free synchronization. They decouple resolution of application level conflicts from synchronization over a network.

The replication protocol partitions the global state space into user specific places for CRDTs, `[email crdt-id]`, possibly further dividing this inside the CRDT into identities (e.g. branches). All replication happens between these places. All peers automatically synchronize CRDTs of each user they subscribe to and push changes as soon as they have all data.

We make heavy use of [core.async](https://github.com/clojure/core.async) to model peers platform- and network-agnostic just as peers having a pair of messaging channels for `edn` messages. We build on platform-neutral durable storage through [konserve](https://github.com/ghubber/konserve). At the core is a `pub-sub` scheme between peers, but most functionality is factored into `middlewares` filtering and tweaking the in/out channel pair of each peers pub-sub core. This allows decoupled extension of the network protocol.

For detailed documentation of the repository CRDT look at the [introduction](http://ghubber.github.io/geschichte/). Or to understand the [pub-sub message protocol for synching](http://ghubber.github.io/geschichte/synching.html).

* Repository CRDT

For the special repository CRDT implicit conflicts might occur (if a device is offline for instance). But committing to the same CRDT on different peers in general is not supposed to be the best way to organize distributed writes. Instead, explicit pulling or merging between branches or users allows for supervised pulls or merges under each user's control, e.g. through pull-hooks or supervised on stage.

** Twisting CAP

Having distributed writes in any system puts it under the restrictions of the [[https://en.wikipedia.org/wiki/CAP_theorem][CAP theorem]]. Similar to `git` there is no design-level decision of how to deal with breaks of consistency and how to modulate convergence. So feel free to organize different write schemes, from a singular writer like Datomic to a totally distributed landscape of non-consistent always available repositories (like git) are possible. Ideally some preconfigurable schemes should emerge.

*** Scheme 0: Personal applications

For "high-level", low write-throughput data (like a port of a classical desktop application for personal data management) which is not immediately synchronized in a global state between several users by your application, everything is fine and you don't need to worry about CAP. An example would be a personal address book manager, a personal todo app, ... All you need to do is cover conflict resolution.

*** Scheme 1: Tree of coordinators

The currently supposed coordination around writes is a Linux kernel-development inspired tree like structure of synching groups consisting of one central user (e.g. user corresponding to the state of the application/database on the server) we call the `coordinator`.

The **coordinator**:

1. tracks changes in all authenticated users clones
2. checks for integrity
3. pulls and hence decides on a new upstream value
4. and propagates it back to all peers
5. users pull *and* merge any changes

Latency differences between users together with a high volume of writes can cause the network to diverge, because high latency peers have no chance anymore to be pulled from and diverge from the coordinator. To avoid a runaway effect in this scenario we introduce a delay cost to merge gradually rising with the ratio of merges vs. normal commits in the repository on user-side. In CAP terms we reduce availability, but do not directly gain consistency, only limit divergence.
In this scenario the application is supposed to notify each user about the diverged state and if this persists, recommend joining a lower write-intensive coordinator. Coordinators then form a tree around the central coordinator themselves being users. This reassignment can be done automatically on server side (but has not been worked out yet) corresponding to load-balancing, a P2P load-balancer is also conceivable.

** JavaScript

It is supposed to work from JavaScript as well, ping me and I will have a look what is necessary to make interop more painfree if you have problems.

*Any help or patches are very welcome :-)*

** TODOs for a first release

- Define CRDT Algebra for synching and repo. Use downstream ops of INRIA techreport [DONE]
- Allow dual op-based vs. state-based representation of a CRDT for constant time synching [DONE]
- Give message exchanges unique id to track pub-sub exchanges without network topology. [DONE]
- Refactor core replication to break apart from repository CRDT [MOSTLY DONE]
- Handle tag-table for messaging (transit?).

- Rename all messaging: remove ambiguous "meta" terminology :meta-pub -> :crdt/pub, :metas->:pubs, :transactions -> :prepared (?) ...
- Reactivate cljs port

- Visualize repo state.

** Roadmap

- Atomic cross-CRDT updates.
- Partially propagate updates and allow them to be delayed and reassembled again to stay atomic?
- Make usage from JavaScript straightforward (including JSON values). Browser and nodejs.
- Passwordless authentication (and authorisation) based on email verification or password and inter-peer trust network as p2p middleware.
- Implement useful CRDTs from techreview and other papers and ship by default.
- Allow management of subscriptions of peers.
- Limit inline value size, avoid pulling huge fetched values in memory. Distribute bandwidth between CRDTs.
- Negotiate middlewares with versioning.
- Build extendable command and control interface for peers (middleware?).
- Encryption of transaction with repo key encrypted by userkeys, public key schema, explore pub/private key solutions. Maybe metadata signing can work (slowly) on a DHT?
- Add a basic web toolbar for applications to communicate their synching state to the user in a uniform way.
- Provide example for durable undo and redo for `react`-like applications.
- Make peers and stage records(?).
- Implement diverse prototypes, from real-time to "big-data".
- Evaluate lowest-common-ancestor algorithms if merging becomes too expansive.
  See also [[http://slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search#btnNext][lca in haskell (including repository monad)]]

*** TODOs
**** TODO fix geschichte example 					:bug:
    :PROPERTIES:
    :Assigned_to: kordano
    :END:
**** TODO go macros 						    :feature:
    :PROPERTIES:
    :Assigned_to: whilo
    :END:
    - Note taken on [2015-06-17 Mi 13:07] \\
      see full-async
**** TODO build cljs repl 					    :feature:
    DEADLINE: <2015-07-04 Sa>
    :PROPERTIES:
    :Assigned_to: kordano 
    :END:
**** TODO fix pull-hooks 						:bug:
    :PROPERTIES:
    :Assigned_to: whilo
    :END:
**** TODO create crdt bibliography 				     :theory:
    DEADLINE: <2015-07-05 So>
    :PROPERTIES:
    :Assigned_to: whilo
    :END:
** License

Copyright © 2013-2015 <NAME> & <NAME>

Distributed under the Eclipse Public License, the same as Clojure.
{'fraction_non_alphanumeric': 0.06460674157303371, 'fraction_numerical': 0.005726015557476232, 'mean_word_length': 4.446601941747573, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 17, 'https://': 12, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3971235', 'n_tokens_mistral': 4883, 'n_tokens_neox': 4628, 'n_words': 2505}