-
Notifications
You must be signed in to change notification settings - Fork 1k
/
GCounter.cs
213 lines (178 loc) · 7.96 KB
/
GCounter.cs
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
//-----------------------------------------------------------------------
// <copyright file="GCounter.cs" company="Akka.NET Project">
// Copyright (C) 2009-2023 Lightbend Inc. <http://www.lightbend.com>
// Copyright (C) 2013-2023 .NET Foundation <https://github.com/akkadotnet/akka.net>
// </copyright>
//-----------------------------------------------------------------------
using Akka.Cluster;
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using System.Numerics;
namespace Akka.DistributedData
{
/// <summary>
/// A typed key for <see cref="GCounter"/> CRDT. Can be used to perform read/upsert/delete
/// operations on correlated data type.
/// </summary>
[Serializable]
public sealed class GCounterKey : Key<GCounter>
{
/// <summary>
/// Creates a new instance of <see cref="GCounterKey"/> class.
/// </summary>
/// <param name="id">TBD</param>
public GCounterKey(string id) : base(id) { }
}
/// <summary>
/// Implements a 'Growing Counter' CRDT, also called a 'G-Counter'.
///
/// It is described in the paper
/// <a href="http://hal.upmc.fr/file/index/docid/555588/filename/techreport.pdf">A comprehensive study of Convergent and Commutative Replicated Data Types</a>.
///
/// A G-Counter is a increment-only counter (inspired by vector clocks) in
/// which only increment and merge are possible. Incrementing the counter
/// adds 1 to the count for the current node. Divergent histories are
/// resolved by taking the maximum count for each node (like a vector
/// clock merge). The value of the counter is the sum of all node counts.
///
/// This class is immutable, i.e. "modifying" methods return a new instance.
/// </summary>
[Serializable]
public sealed class GCounter :
FastMerge<GCounter>,
IRemovedNodePruning<GCounter>,
IEquatable<GCounter>,
IReplicatedDataSerialization,
IDeltaReplicatedData<GCounter, GCounter>,
IReplicatedDelta
{
private static readonly ulong Zero = 0UL;
/// <summary>
/// TBD
/// </summary>
public ImmutableDictionary<UniqueAddress, ulong> State { get; }
/// <summary>
/// TBD
/// </summary>
public static GCounter Empty => new();
/// <summary>
/// Current total value of the counter.
/// </summary>
public ulong Value { get; }
[NonSerialized]
private readonly GCounter _syncRoot; //HACK: we need to ignore this field during serialization. This is the only way to do so on Hyperion on .NET Core
public GCounter Delta => _syncRoot;
/// <summary>
/// TBD
/// </summary>
public GCounter() : this(ImmutableDictionary<UniqueAddress, ulong>.Empty) { }
/// <summary>
/// TBD
/// </summary>
/// <param name="state">TBD</param>
/// <param name="delta">TBD</param>
internal GCounter(ImmutableDictionary<UniqueAddress, ulong> state, GCounter delta = null)
{
_syncRoot = delta;
State = state;
Value = State.Aggregate(Zero, (v, acc) => v + acc.Value);
}
public ImmutableHashSet<UniqueAddress> ModifiedByNodes => State.Keys.ToImmutableHashSet();
/// <summary>
/// Increment the counter with the delta specified. The delta must be zero or positive.
/// </summary>
public GCounter Increment(Cluster.Cluster node, ulong delta = 1) => Increment(node.SelfUniqueAddress, delta);
/// <summary>
/// Increment the counter with the delta specified. The delta must be zero or positive.
/// </summary>
/// <param name="node">TBD</param>
/// <param name="n">TBD</param>
/// <exception cref="ArgumentException">
/// This exception is thrown when the specified <paramref name="n"/> is less than zero.
/// </exception>
/// <returns>TBD</returns>
public GCounter Increment(UniqueAddress node, ulong n = 1)
{
if (n == 0) return this;
var nextValue = State.GetValueOrDefault(node, 0UL) + n;
var newDelta = Delta == null
? new GCounter(
ImmutableDictionary.CreateRange(new[] { new KeyValuePair<UniqueAddress, ulong>(node, nextValue) }))
: new GCounter(Delta.State.SetItem(node, nextValue));
return AssignAncestor(new GCounter(State.SetItem(node, nextValue), newDelta));
}
/// <summary>
/// TBD
/// </summary>
/// <param name="other">TBD</param>
/// <returns>TBD</returns>
public override GCounter Merge(GCounter other)
{
if (ReferenceEquals(this, other) || other.IsAncestorOf(this)) return ClearAncestor();
else if (IsAncestorOf(other)) return other.ClearAncestor();
else
{
var merged = other.State;
foreach (var kvp in State)
{
var otherValue = merged.GetValueOrDefault(kvp.Key, Zero);
if (kvp.Value > otherValue)
{
merged = merged.SetItem(kvp.Key, kvp.Value);
}
}
ClearAncestor();
return new GCounter(merged);
}
}
public GCounter MergeDelta(GCounter delta) => Merge(delta);
IReplicatedDelta IDeltaReplicatedData.Delta => Delta;
IReplicatedData IDeltaReplicatedData.MergeDelta(IReplicatedDelta delta) => MergeDelta((GCounter)delta);
IReplicatedData IDeltaReplicatedData.ResetDelta() => ResetDelta();
public GCounter ResetDelta() => Delta == null ? this : AssignAncestor(new GCounter(State));
/// <summary>
/// TBD
/// </summary>
/// <param name="removedNode">TBD</param>
/// <returns>TBD</returns>
public bool NeedPruningFrom(UniqueAddress removedNode) => State.ContainsKey(removedNode);
IReplicatedData IRemovedNodePruning.PruningCleanup(UniqueAddress removedNode) => PruningCleanup(removedNode);
IReplicatedData IRemovedNodePruning.Prune(UniqueAddress removedNode, UniqueAddress collapseInto) => Prune(removedNode, collapseInto);
/// <summary>
/// TBD
/// </summary>
/// <param name="removedNode">TBD</param>
/// <param name="collapseInto">TBD</param>
/// <returns>TBD</returns>
public GCounter Prune(UniqueAddress removedNode, UniqueAddress collapseInto)
{
return State.TryGetValue(removedNode, out var prunedNodeValue)
? new GCounter(State.Remove(removedNode)).Increment(collapseInto, prunedNodeValue)
: this;
}
/// <summary>
/// TBD
/// </summary>
/// <param name="removedNode">TBD</param>
/// <returns>TBD</returns>
public GCounter PruningCleanup(UniqueAddress removedNode) => new(State.Remove(removedNode));
public override int GetHashCode() => State.GetHashCode();
public bool Equals(GCounter other)
{
if (ReferenceEquals(other, null)) return false;
if (ReferenceEquals(this, other)) return true;
return State.SequenceEqual(other.State);
}
public override bool Equals(object obj) => obj is GCounter counter && Equals(counter);
public override string ToString() => $"GCounter({Value})";
/// <summary>
/// Performs an implicit conversion from <see cref="GCounter" /> to <see cref="ulong" />.
/// </summary>
/// <param name="counter">The counter to convert</param>
/// <returns>The result of the conversion</returns>
public static implicit operator ulong(GCounter counter) => counter.Value;
IDeltaReplicatedData IReplicatedDelta.Zero => GCounter.Empty;
}
}