def crc16(s: bytes) -> int:
    """Redis 使用的 CRC16 算法"""
    crc = 0
    for byte in s:
        crc ^= byte << 8
        for _ in range(8):
            if crc & 0x8000:
                crc = (crc << 1) ^ 0x1021
            else:
                crc <<= 1
            crc &= 0xFFFF
    return crc

def hash_slot(key: str) -> int:
    """计算 key 的哈希槽"""
    # 处理 hash tag {}
    start = key.find('{')
    if start != -1:
        end = key.find('}', start + 1)
        if end != -1 and end != start + 1:
            key = key[start + 1:end]

    return crc16(key.encode()) % 16384

import socket
import re

class ClusterClient:
    def __init__(self, startup_nodes):
        """startup_nodes: 初始节点列表 [(host, port), ...]"""
        self.nodes = {addr: self._connect(*addr) for addr in startup_nodes}
        self.slot_map = {}  # slot → (host, port)
        self._refresh_slots()

    def _connect(self, host, port):
        return socket.create_connection((host, port))

    def _refresh_slots(self):
        """刷新槽位映射"""
        for addr, sock in self.nodes.items():
            try:
                sock.sendall(b"*2\r\n$7\r\nCLUSTER\r\n$9\r\nSLOTS\r\n\r\n")
                resp = self._read_response(sock)
                # 解析 CLUSTER SLOTS 响应
                # [[0, 5460, ["127.0.0.1", 6379]], ...]
                for slot_range in resp:
                    start_slot = slot_range[0]
                    end_slot = slot_range[1]
                    node_info = slot_range[2]
                    node_addr = (node_info[0], node_info[1])
                    for slot in range(start_slot, end_slot + 1):
                        self.slot_map[slot] = node_addr
                return
            except:
                continue

    def execute(self, *args):
        """执行命令，处理 MOVED 重定向"""
        for attempt in range(3):
            # 计算槽位
            key = args[1] if len(args) > 1 else None
            slot = hash_slot(key) if key else 0

            # 获取目标节点
            target = self.slot_map.get(slot)
            if target is None:
                self._refresh_slots()
                target = self.slot_map.get(slot)

            sock = self.nodes.get(target)
            # 发送命令
            cmd = encode_command(*args)
            sock.sendall(cmd)

            # 读取响应
            resp = self._read_response(sock)

            # 检查 MOVED
            if isinstance(resp, Exception) and str(resp).startswith("MOVED"):
                parts = str(resp).split()
                new_host, new_port = parts[2].split(":")
                new_addr = (new_host, int(new_port))

                # 更新槽位映射
                self.slot_map[slot] = new_addr

                # 连接到新节点
                if new_addr not in self.nodes:
                    self.nodes[new_addr] = self._connect(*new_addr)

                continue  # 重试

            return resp

        raise RuntimeError("Max retries exceeded")

def handle_ask(self, slot, new_addr, original_args):
    """处理 ASK 重定向"""
    # 1. 连接到新节点
    sock = self._get_or_connect(new_addr)

    # 2. 发送 ASKING
    sock.sendall(b"*1\r\n$6\r\nASKING\r\n")
    self._read_response(sock)  # +OK

    # 3. 重新发送原始命令
    cmd = encode_command(*original_args)
    sock.sendall(cmd)
    resp = self._read_response(sock)

    # 注意：不更新 slot_map，因为槽位还在迁移中
    return resp

def make_keys(user_id, *fields):
    """生成使用 hash tag 的 key 列表"""
    return [f"{{{user_id}}}:{field}" for field in fields]

keys = make_keys("user:1000", "name", "email", "age")
# ["{user:1000}:name", "{user:1000}:email", "{user:1000}:age"]

# 所有 key 都在同一个槽
assert all(hash_slot(keys[0]) == hash_slot(k) for k in keys)

def cluster_pipeline(self, commands):
    """集群模式的 Pipeline"""
    # 按槽位分组
    slot_groups = {}
    for cmd_args in commands:
        key = cmd_args[1]
        slot = hash_slot(key)
        if slot not in slot_groups:
            slot_groups[slot] = []
        slot_groups[slot].append(cmd_args)

    # 每个槽位一组 Pipeline
    results = []
    for slot, cmds in slot_groups.items():
        node = self.slot_map[slot]
        sock = self.nodes[node]

        # 发送 Pipeline
        buf = b""
        for cmd_args in cmds:
            buf += encode_command(*cmd_args)
        sock.sendall(buf)

        # 读取响应
        for _ in cmds:
            resp = self._read_response(sock)
            if isinstance(resp, Exception) and str(resp).startswith("MOVED"):
                # 需要重新路由
                pass
            results.append(resp)

    return results

import time
import random

def execute_with_retry(self, *args, max_retries=5):
    """带指数退避的重试策略"""
    for attempt in range(max_retries):
        try:
            return self._execute(*args)
        except (MOVED, ASK) as e:
            # 重定向，立即重试
            continue
        except ConnectionError:
            # 连接失败，退避重试
            if attempt < max_retries - 1:
                delay = min(0.1 * (2 ** attempt), 2.0)
                delay += random.uniform(0, delay * 0.1)  # 抖动
                time.sleep(delay)
    raise RuntimeError("Max retries exceeded")