基于hash算法的分片机制

这段时间学习了一些有关 基于hash算法的分片机制 的知识，并且自己也上手写了几个测试代码做了测试

首先是 哈希取模分片测试，这是比较简单的一种，局限性也比较大，个人感觉如果不做优化的话，这种方法就像个傻子，不管喂的是什么都只会啊吧啊吧。

实现代码是用 rust 写的，没有什么别的意思，就是好玩。
当然，用 python 写一点问题的都没有，不用担心转换的过程中有什么问题，python 的生态也是很让人满意的。

哈希取模分片测试 和 一致性哈希算法测试+虚拟节点 两部分的代码并没有加额外的包，如果有我会给出提醒 #点头

哈希取模分片测试

// 哈希取模分片测试
use std::collections::hash_map::DefaultHasher;
use std::fs;
use std::hash::{Hash, Hasher};
use std::path::Path;

//功能函数
fn hash_mod_shard(key: &str, shard_count: u64) -> u64 {
    let mut hasher = DefaultHasher::new();
    // 计算key的哈希值
    key.hash(&mut hasher);
    // 获取哈希值
    let hash_value = hasher.finish();
    // 取模运算，确定分片编号
    let shard_id = hash_value % shard_count;
    shard_id
}

//主函数
fn main() {
    let shard_count = 4;
    let file_path = Path::new("keys.txt");
    let mut shard_array = [0,0,0,0];

    if !file_path.exists() {
        eprintln!("文件 {} 不存在", file_path.display());
        return;
    }

    match fs::read_to_string(file_path) {
        Ok(content) => {
            for key in content.lines() {
                let shard_id = hash_mod_shard(key, shard_count);
                println!("Key '{}' 应该存储在分片 {}", key, shard_id);
                match shard_id {
                    0 => shard_array[0] += 1,
                    1 => shard_array[1] += 1,
                    2 => shard_array[2] += 1,
                    3 => shard_array[3] += 1,
                    _ => println!("分片编号错误"),
                }
            }
        }
        Err(e) => {
            eprintln!("读取文件 {} 时出错: {}", file_path.display(), e);
        }
    }
    println!("Count array: {:?}", shard_array);
}

接下来我对代码进行测试，为了保证数据的可靠性，我对数据进行了简单的清洗。不过去重功能还没写，之后会提上日程

简单数据清洗的代码实现如下（python实现）
注意：需要在同目录下存在 input.txt 和 output.txt
除此之外，还可以手动设定要提取字符串的长度

def extract_and_write(input_file, output_file, length):
    """
    input_file (str): 输入文件路径
    output_file (str): 输出文件路径
    length (int): 要提取的字符串长度
    """
    try:
        with open(input_file, 'r', encoding='utf-8') as infile, open(output_file, 'w', encoding='utf-8') as outfile:
            for line in infile:
                # 去除行末的换行符
                line = line.strip()
                # 如果行长度大于等于指定长度，则提取指定长度的字符串
                if len(line) >= length:
                    extracted_str = line[:length]
                    outfile.write(extracted_str + '\n')
    except Exception as e:
        print(f"发生错误: {e}")

# 示例调用
input_file = 'input.txt'
output_file = 'output.txt'
length = 9  # 提取长度为10的字符串
extract_and_write(input_file, output_file, length)

通过这种方法，我轻松获得了以下两个数据集：

395个 长度为9 的随机字符串 keys9-395.txt
46074个 长度为13 的随机字符串 key13-46074

带入数据，得到如下结果：

keys9-395.txt >> [96, 96, 95, 108]
key13-46074 >> [11620, 11418, 11620, 11416]

总体来看符合预期，预期的4块分片平均分配，这是比较正常的结果。那么接着说说局限性吧，我在测试的时候发现了一个严重的问题。

首先假设我是一个黑客。

这段代码是通过取模来获得希望的数值的，这会大大降低分片的安全性，因为同一个输入字符串，输出的结果是始终相同的，所以如果不加以改进，我完全可以通过大量输入字符串在预设的代码中，拿到分片一致的那部分字符串，当积攒到数量可观时，我会把他们全部投放，这样，我就获得了某个分片的掌控权。

哦莫，完蛋。

我想这并不难进行改进，我在这里先提出我的预想：

首先要想办法打乱分片的分配，我最开始的思考是通过映射+加密进行分配，这样做安全性确实会小幅度提高，但感觉还是稍有欠缺。一方面，这样做加大了计算量，另一方面，有加密就有解密。还有一种方法，即字符串拼接，就像区块链的实现一样，把时间戳，区块号或是其它与零知识相关的内容拼接在一起，进行分块运算之后验证，我觉得这是理论上具有可实现性的。

其次是对于区块划分的动态调整，这部分我会在之后的章节里提到，接下来继续 基于hash算法的分片机制 的另一小块

一致性哈希算法测试+虚拟节点

//一致性哈希算法测试+虚拟节点
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
use std::fs;
use std::path::Path;

struct ConsistentHash {
    nodes: HashMap<u64, String>,       //一个 HashMap，存储哈希值到节点名称的映射
    replicas: usize,    //每个节点的虚拟节点数量
}

impl ConsistentHash {
    fn new(replicas: usize) -> Self {
        ConsistentHash {
            nodes: HashMap::new(),
            replicas,
        }
    }

    //添加节点
    fn add_node(&mut self, node: &str) {
        for i in 0..self.replicas {
            let hash = self.hash(&format!("{}_{}", node, i));
            self.nodes.insert(hash, node.to_string());
        }
    }

    //计算字符串的哈希值，使用 DefaultHasher
    fn hash(&self, value: &str) -> u64 {
        let mut hasher = DefaultHasher::new();
        value.hash(&mut hasher);
        hasher.finish()
    }
}

接下来这一段看起来可能比较晦涩，所以我把它单独拎出来，分条讲解

//根据 key 计算哈希值，并返回对应的节点名称
fn get_node(&self, key: &str) -> Option<&String> {
    let hash = self.hash(key);
    self.nodes.iter()   //获取哈希环中所有节点的哈希值和节点名称
        .filter(|(&k, _)| k >= hash)
        //过滤出哈希大于或等于给定值的节点
        .min_by_key(|(&k, _)| k)
        //从过滤后的节点中，获取最小哈希值的节点
        .map(|(_, v)| v)
        //使用 map 将节点（键值对）映射到节点名称
        .or_else(|| self.nodes.iter().next().map(|(_, v)| v))
        //在一致性哈希中，哈希环是环形的，如果找不到大于或等于给定键哈希值的节点，则应返回环中的第一个节点
}

//主函数
fn main() {
    let mut shard_array = [0,0,0,0];
    let mut ch = ConsistentHash::new(3);
    ch.add_node("1");
    ch.add_node("2");
    ch.add_node("3");
    ch.add_node("4");

    let file_path = Path::new("keys13-46074.txt");
    if !file_path.exists() {
        eprintln!("文件 {} 不存在", file_path.display());
        return;
    }

    match fs::read_to_string(file_path) {
        Ok(content) => {
            for key in content.lines() {
                if let Some(node) = ch.get_node(key) {
                    println!("Key '{}' maps to node '{}'", key, node);
                    let num:u32 = match node.parse(){
                        Ok(n) => n,
                        Err(_) => 7
                    };
                    println!("Shard count: {}", num);
                    match num {
                        1 => shard_array[0] += 1,
                        2 => shard_array[1] += 1,
                        3 => shard_array[2] += 1,
                        4 => shard_array[3] += 1,
                        _ => println!("分片编号错误"),
                    }
                } else {
                    println!("No node found for key '{}'", key);
                }
            }
        }
        Err(e) => {
            eprintln!("读取文件 {} 时出错: {}", file_path.display(), e);
        }
    }
    println!("Count array: {:?}", shard_array);
}

跑了两个同样的数据集，出现了意料之外的效果：

keys9-395.txt >> [96, 96, 95, 108]
key13-46074 >> [2941, 6483, 13533, 23117]

分布不符合预期，但是存在一定规律，经过一定排查，发现原因出在节点分配的代码上，因为设定的节点值不合理，导致实验结果出现偏差。经过多组实验，节点分配很难控制，风险较大，需要谨慎使用

不过这组实验后面还补了一个要求，即虚拟节点数量应远大于实际节点，这样分配会使节点变得均衡，符合预期