1 简介

本文实现无第三方依赖、可直接运行 的版本管理示例。

特点：

	FlatTree 用 map[string][32]byte 存“路径→blob sha256”。

提供：Put/Get/Delete/ListPrefix/RenameDir。

提供：MerkleRoot() 计算目录树的哈希（自底向上，目录条目采用确定序：先按名字排序，数据格式 “blob <name>\n<hex>\n” / “tree <name>\n<hex>\n”）。

内部做了路径规范化（统一 /、去掉 .、不允许空/…）。

该示例为简化实现，但它里面的很多算法思想其实和版本管理系统（Git、Mercurial 等）的核心设计非常接近，可以给版本管理服务借鉴。我们可以从几个层面来分析：

2 功能规划

• 1. 内容寻址（Content Addressing）

用 sha256.Sum256 来生成 BlobID，即：文件内容 → Hash → 唯一标识。

优点：

  相同内容必然有相同 ID（去重存储）。

  可以快速判断文件是否被修改。

  方便做缓存和分布式同步。

Git 也是基于 内容哈希寻址（对象名就是 SHA-1/2 的哈希）。

• 2. 扁平化树（FlatTree）模型

用 map[string]BlobID 维护路径和内容的映射。

这里没有显式的树节点结构，而是通过路径字符串来表示树。

好处：

  简化实现（不需要复杂树结构）。

  很适合做 快照，因为直接拷贝 map 就能表示一个版本。

  和 Git 的 "树对象" 类似，树就是一堆 (path → blob) 的映射。

版本管理服务可以用 FlatTree 快照 + 哈希引用 的方式来高效存储不同版本。

• 3. 路径规范化（Path Normalization）

normalizePath 保证路径统一（去掉 .、禁止 …、消除 \ 和冗余 /）。

避免歧义路径引发安全漏洞或数据重复。

在多平台（Linux/Windows）下尤为重要。

类似 Git 会强制用 POSIX 风格的路径，并拒绝非法路径。

• 4. 前缀匹配与目录操作

ListPrefix 支持按目录前缀递归列出文件，等价于目录树遍历。

RenameDir 通过前缀替换实现整目录重命名/移动。

先收集受影响的文件 (aff)。

再预检查是否有路径冲突。

最后批量更新。

这种“批量原子操作”思路很像 Git 的 树对象重写（修改目录会生成新的树对象，但原子替换）。

• 5. 并发控制

使用 sync.RWMutex：

读操作 (Get, ListPrefix) 支持并发。

写操作 (Put, Delete, RenameDir) 独占。

保证一致性，同时避免不必要的性能损耗。

对于多用户协作的版本管理服务，非常关键。

• 6. 冲突检测

RenameDir 里对新路径做了预检测，防止覆盖已有文件。

避免了不可恢复的数据丢失。

类似于版本管理里的 冲突检测，避免在合并/重命名时覆盖用户数据。

3 代码示例

    package main

    import (
        "bytes"
        "crypto/sha256"
        "encoding/hex"
        "errors"
        "fmt"
        "path"
        "sort"
        "strings"
        "sync"
    )

    // BlobID 用 sha256 演示，真实系统可以是任意长度的内容哈希。
    type BlobID [32]byte

    func BlobFromBytes(b []byte) BlobID { return sha256.Sum256(b) }
    func BlobFromHex(s string) (BlobID, error) {
        var z BlobID
        b, err := hex.DecodeString(strings.TrimSpace(s))
        if err != nil || len(b) != len(z) {
            return z, fmt.Errorf("invalid hex length: %v", err)
        }
        copy(z[:], b)
        return z, nil
    }
    func (h BlobID) Hex() string { return hex.EncodeToString(h[:]) }

    // ---------------- FlatTree ----------------

    type FlatTree struct {
        mu sync.RWMutex
        m  map[string]BlobID // path -> blob hash
    }

    func NewFlatTree() *FlatTree {
        return &FlatTree{m: make(map[string]BlobID)}
    }

    // 统一把路径转为 posix 风格、去掉 "."，禁止空段与 ".."
    func normalizePath(p string) (string, error) {
        p = strings.TrimSpace(p)
        p = strings.ReplaceAll(p, "\\", "/")
        p = path.Clean(p)
        if p == "." {
            p = "" // 用空串表示根
        }
        if p == "" {
            return "", errors.New("empty path is not a file path")
        }
        if strings.HasPrefix(p, "/") {
            p = strings.TrimPrefix(p, "/")
        }
        if strings.Contains(p, "..") {
            return "", fmt.Errorf("path contains '..': %q", p)
        }
        // 禁止以 "/" 结尾（那是目录）
        if strings.HasSuffix(p, "/") {
            return "", fmt.Errorf("path ends with '/': %q", p)
        }
        return p, nil
    }

    func (t *FlatTree) Put(p string, blob BlobID) error {
        np, err := normalizePath(p)
        if err != nil { return err }
        t.mu.Lock()
        t.m[np] = blob
        t.mu.Unlock()
        return nil
    }

    func (t *FlatTree) Get(p string) (BlobID, bool) {
        np, err := normalizePath(p)
        if err != nil { return BlobID{}, false }
        t.mu.RLock()
        defer t.mu.RUnlock()
        h, ok := t.m[np]
        return h, ok
    }

    func (t *FlatTree) Delete(p string) error {
        np, err := normalizePath(p)
        if err != nil { return err }
        t.mu.Lock()
        delete(t.m, np)
        t.mu.Unlock()
        return nil
    }

    // ListPrefix 列出前缀（目录）下所有文件的完整路径与哈希（递归）
    func (t *FlatTree) ListPrefix(prefix string) map[string]BlobID {
        prefix = strings.TrimSpace(prefix)
        prefix = strings.ReplaceAll(prefix, "\\", "/")
        prefix = path.Clean(prefix)
        if prefix == "." || prefix == "/" { prefix = "" }
        if prefix != "" && !strings.HasSuffix(prefix, "/") {
            prefix += "/"
        }
        out := make(map[string]BlobID)
        t.mu.RLock()
        defer t.mu.RUnlock()
        for p, h := range t.m {
            if prefix == "" || strings.HasPrefix(p, prefix) {
                out[p] = h
            }
        }
        return out
    }

    // RenameDir 把 old 前缀（目录）整体重命名为 new（可能是移动）
    // 例如: RenameDir("docs", "site/docs")。要求 new 不能与现有路径冲突。
    func (t *FlatTree) RenameDir(oldPrefix, newPrefix string) error {
        clean := func(s string) (string, error) {
            s = strings.TrimSpace(s)
            s = strings.ReplaceAll(s, "\\", "/")
            s = strings.TrimPrefix(s, "/")
            if s == "" { return "", fmt.Errorf("empty dir not allowed") }
            if strings.Contains(s, "..") { return "", fmt.Errorf("bad dir: %q", s) }
            return path.Clean(s), nil
        }
        oldP, err := clean(oldPrefix); if err != nil { return err }
        newP, err := clean(newPrefix); if err != nil { return err }

        t.mu.Lock()
        defer t.mu.Unlock()

        // 收集受影响的键
        aff := make(map[string]BlobID)
        oldWithSlash := oldP + "/"
        for p, h := range t.m {
            if p == oldP || strings.HasPrefix(p, oldWithSlash) {
                aff[p] = h
            }
        }
        if len(aff) == 0 {
            return fmt.Errorf("no entries under %q", oldP)
        }
        // 预检测冲突
        for p := range aff {
            suffix := p[len(oldP):] // 包含可能的 "" 或 "/xxx"
            if strings.HasPrefix(suffix, "/") {
                suffix = suffix[1:]
            }
            newKey := newP
            if suffix != "" { newKey += "/" + suffix }
            if _, exists := t.m[newKey]; exists && aff[newKey] == (BlobID{}) {
                return fmt.Errorf("target path exists: %q", newKey)
            }
        }
        // 执行重命名
        for p := range aff {
            delete(t.m, p)
        }
        for p, h := range aff {
            suffix := p[len(oldP):]
            if strings.HasPrefix(suffix, "/") { suffix = suffix[1:] }
            newKey := newP
            if suffix != "" { newKey += "/" + suffix }
            t.m[newKey] = h
        }
        return nil
    }

4 小结

版本管理服务可借鉴的算法思想

内容寻址（BlobID 哈希） → 高效去重、快速比对。

扁平快照存储（FlatTree） → 简单但功能完整，适合实现版本树。

路径规范化 → 保证一致性与安全性。

基于前缀的目录操作 → 高效实现递归遍历与目录重命名。

并发读写锁 → 支撑多用户高并发操作。

冲突检测机制 → 确保修改/合并的正确性。