# distributed-counters

**Repository Path**: mirrors_nicolasff/distributed-counters

## Basic Information

- **Project Name**: distributed-counters
- **Description**: Experiments with distributed counters
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-09-25
- **Last Updated**: 2025-12-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

Experiments with distributed counters
=====================================

This project implements simple distributed counters in Erlang.
Counters are distributed values with custom *merge policies*. A merge policy is a function that takes two existing counters and returns a new one.
In this context, *counters* are not just values that are incremented by an arbitrary amount but any value that might be wrapped in a container and merged with an other.

Several functions can be implemented that way, including:

* SUM (implemented in `ctr_sum.erl`)
* MIN (implemented in `ctr_min.erl`)
* MAX (implemented in `ctr_max.erl`)
* AVG (implemented in `ctr_avg.erl`)
* STDDEV
* Count-Min
* (Hyper)LogLog
* …

Counter definition
------------------

An Erlang “behaviour” is used to implement a few functions per counter, namely:

* `bottom/0` returns a new, *empty* counter (think ⊥).
* `new/1` returns a new counter containing a single value.
* `merge/2` takes two counters and returns a new one.
* `value/1` extracts the value from a counter.
* `is_idempotent/0` `true`/`false` depending on the counter; `MIN` is idempotent, `SUM` is not.
* `gc_info/1` return a data structure used in GC.
* `gc_merge/3` gives the GC data structure to an existing counter with a unique identifier and ask the counter to clean up old (and presumably irrelevant) data.

Idempotent counter types have trivial implementations for `gc_info/1` and `gc_merge/3`.

Distribution
------------

The demo program starts 3 nodes as separate Erlang processes and sends them a few thousand counter updates with a high probability of dropped and duplicate messages. Once all the updates have been sent, each node is asked to give its own opinion about the total count and a merged value of these 3 values is displayed. If needed, a GC process is run to update the nodes.


Running the demo
----------------

Run `make clean all demo` to run the demo.
Here is what you should see:

    ==============================
    Testing ctr_sum on 3 nodes
    Sent 1000 messages
    Sent 2000 messages
    Sent 3000 messages
    Sent 4000 messages
    Sent 5000 messages
    Sent 6000 messages
    Sent 7000 messages
    Sent 8000 messages
    Sent 9000 messages
    Sent 10000 messages
    Expected value is -110836610
    Gettting full counters on all nodes...
    Value of resolved counters: -110836610
    Counter according to each node: [-109582605,-110537717,-112440005]
    Waiting a second before running GC...
    Trigger GC
    Counter according to each node: [-110836610,-110836610,-110836610]
    
    ==============================
    Testing ctr_min on 3 nodes
    Sent 1000 messages
    Sent 2000 messages
    Sent 3000 messages
    Sent 4000 messages
    Sent 5000 messages
    Sent 6000 messages
    Sent 7000 messages
    Sent 8000 messages
    Sent 9000 messages
    Sent 10000 messages
    Expected value is -999999
    Gettting full counters on all nodes...
    Value of resolved counters: -999999
    Counter according to each node: [-999999,-999999,-999999]
    Waiting a second before running GC...
    Trigger GC
    Counter according to each node: [-999999,-999999,-999999]
    
    ==============================
    Testing ctr_max on 3 nodes
    Sent 1000 messages
    Sent 2000 messages
    Sent 3000 messages
    Sent 4000 messages
    Sent 5000 messages
    Sent 6000 messages
    Sent 7000 messages
    Sent 8000 messages
    Sent 9000 messages
    Sent 10000 messages
    Expected value is 999650
    Gettting full counters on all nodes...
    Value of resolved counters: 999650
    Counter according to each node: [999650,999650,999650]
    Waiting a second before running GC...
    Trigger GC
    Counter according to each node: [999650,999650,999650]
    
    ==============================
    Testing ctr_avg on 3 nodes
    Sent 1000 messages
    Sent 2000 messages
    Sent 3000 messages
    Sent 4000 messages
    Sent 5000 messages
    Sent 6000 messages
    Sent 7000 messages
    Sent 8000 messages
    Sent 9000 messages
    Sent 10000 messages
    Expected value is {-99168540,10000}
    Gettting full counters on all nodes...
    Value of resolved counters: {-99168540,10000}
    Counter according to each node: [{-100403932,9985},{-97717578,9991},{-101242460,9984}]
    Waiting a second before running GC...
    Trigger GC
    Counter according to each node: [{-99168540,10000},{-99168540,10000},{-99168540,10000}]


Limitations
-----------

This code is quite inefficient and only intended as an experiment.
The `GcInfo` object should use a more compact representation; Merkle Trees would probably help.

License
-------

Released in the Public Domain.
Originally developed as an internal prototype at [Acunu](http://acunu.com/).