blob: dbd1c871933b4b8fec38ea5ce7dd3774ff889bed [file]
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading;
namespace DubboNet.Clients.Helper
{
/// <summary>一致性 Hash 环;更新原子发布,读取使用不可变快照。EN: Consistent hash ring with atomically published immutable snapshots.</summary>
public class ConsistentHash<T>
{
private sealed class Ring
{
internal readonly int[] Keys;
internal readonly T[] Values;
internal Ring(SortedDictionary<int, T> points)
{ Keys = points.Keys.ToArray(); Values = points.Values.ToArray(); }
}
private readonly object _sync = new();
private List<T> _nodes = new();
private int _replicate;
private Ring _ring = new(new SortedDictionary<int, T>());
public ConsistentHash(int replicate = 100)
{
if (replicate <= 0) throw new ArgumentOutOfRangeException(nameof(replicate));
_replicate = replicate;
}
public void Init(IEnumerable<T> nodes = null)
{
lock (_sync) Init(nodes, _replicate);
}
public void Init(IEnumerable<T> nodes, int replicate)
{
if (replicate <= 0) throw new ArgumentOutOfRangeException(nameof(replicate));
lock (_sync)
{
var snapshot = nodes?.Distinct().ToList() ?? new List<T>();
Publish(snapshot, replicate);
}
}
public void Add(T node)
{
if (node is null) throw new ArgumentNullException(nameof(node));
lock (_sync)
{
if (_nodes.Contains(node)) return;
var nodes = new List<T>(_nodes) { node };
Publish(nodes, _replicate);
}
}
public void Remove(T node)
{
lock (_sync)
{
var nodes = new List<T>(_nodes);
if (!nodes.Remove(node)) throw new InvalidOperationException("Cannot remove a node that was not added.");
// Rebuild from logical nodes: hash collisions must not remove another node's points.
Publish(nodes, _replicate);
}
}
private void Publish(List<T> nodes, int replicate)
{
var points = new SortedDictionary<int, T>();
foreach (T node in nodes)
{
if (node is null) throw new ArgumentException("Hash nodes cannot contain null.", nameof(nodes));
for (int i = 0; i < replicate; i++) points[AddNodeHash(node, i)] = node;
}
var ring = new Ring(points);
_nodes = nodes;
_replicate = replicate;
Volatile.Write(ref _ring, ring);
}
/// <summary>获取 key 对应的节点。EN: Resolves the node owning a key.</summary>
public T GetNode(string key)
{
Guard.ThrowIfNull(key, nameof(key));
Ring ring = Volatile.Read(ref _ring);
if (ring.Keys.Length == 0) throw new InvalidOperationException("The consistent hash ring is empty.");
int index = Array.BinarySearch(ring.Keys, GetNodeHash(key));
if (index < 0) index = ~index;
if (index == ring.Keys.Length) index = 0;
return ring.Values[index];
}
// Override with a stable node identity when cross-process determinism is required.
public virtual int AddNodeHash(T node, int replicateIndex) => BetterHash(
node.GetHashCode().ToString(CultureInfo.InvariantCulture) + "#" + replicateIndex.ToString(CultureInfo.InvariantCulture));
public virtual int GetNodeHash(string key) => BetterHash(key);
public static int BetterHash(string key)
{
Guard.ThrowIfNull(key, nameof(key));
return unchecked((int)MyCommonHelper.EncryptionHelper.MyHash.GetMurmurHash2(Encoding.UTF8.GetBytes(key)));
}
}
}