go - 如何在仅最后几个字节发生变化的golang数据中有效地散列(SHA 256)

Question

假设您有80个字节的数据并且只有最后4个字节在不断变化，那么如何使用Go高效地哈希80个字节。本质上，前76个字节是相同的，而后4个字节则在不断变化。理想情况下，您希望保留前76个字节的哈希摘要的副本，而只需更改后4个字节即可。

Answer 1

您可以在Go Playground上尝试以下示例。基准结果在最后。

注意:以下实现不能安全地并发使用；我故意使它们像这样变得更简单，更快。

仅使用公共(public)API时最快(始终对所有输入进行哈希处理)

Go的哈希算法的一般概念和接口(interface)是 hash.Hash 接口(interface)。这不允许您保存哈希器的状态以及返回或倒带到保存的状态。因此，使用Go标准库的公共(public)哈希API，您始终必须从头开始计算哈希。

公共(public)API提供的是使用Hash.Reset()方法重用已经构造的哈希器来计算新输入的哈希值。这样很好，因此不需要(内存)分配即可计算多个哈希值。另外，您还可以利用可传递给Hash.Sum()的可选片段，该片段用于将当前哈希附加到该片段。这很好，因此不需要分配就可以接收哈希结果。

这是一个利用这些优势的示例:

type Cached1 struct {
    hasher hash.Hash
    result [sha256.Size]byte
}

func NewCached1() *Cached1 {
    return &Cached1{hasher: sha256.New()}
}

func (c *Cached1) Sum(data []byte) []byte {
    c.hasher.Reset()
    c.hasher.Write(data)
    return c.hasher.Sum(c.result[:0])
}

测试数据

我们将使用以下测试数据:

var fixed = bytes.Repeat([]byte{1}, 76)
var variantA = []byte{1, 1, 1, 1}
var variantB = []byte{2, 2, 2, 2}

var data = append(append([]byte{}, fixed...), variantA...)
var data2 = append(append([]byte{}, fixed...), variantB...)

var c1 = NewCached1()

首先，让我们获得真实的结果(以验证我们的哈希器是否正常工作):

fmt.Printf("%x\n", sha256.Sum256(data))
fmt.Printf("%x\n", sha256.Sum256(data2))

输出:

fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c

现在，让我们检查Cached1哈希器:

fmt.Printf("%x\n", c1.Sum(data))
fmt.Printf("%x\n", c1.Sum(data2))

输出是相同的:

fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c

甚至更快，但可能会中断(在以后的Go版本中):仅对最后4个字节进行哈希处理

现在，让我们来看一个不太灵活的解决方案，该解决方案只真正计算一次前76个固定部分的哈希值。

crypto/sha256 软件包的哈希器是未导出的sha256.digest类型(更准确地说是指向该类型的指针):

// digest represents the partial evaluation of a checksum.
type digest struct {
    h     [8]uint32
    x     [chunk]byte
    nx    int
    len   uint64
    is224 bool // mark if this digest is SHA-224
}

digest结构类型的值基本上可以保存哈希器的当前状态。

我们可能要做的是将固定的前76个字节送入哈希器，然后保存此struct值。当我们需要计算前80个字节相同的约80个字节数据的哈希值时，我们将使用此保存的值作为起点，然后输入变化的后4个字节。

注意，仅保存此结构值就足够了，因为它不包含指针，也没有描述符类型，例如 slice 和映射。否则，我们也必须复制这些副本，但是我们很“幸运”。因此，如果将来的crypto/sha256实现会添加一个指针或 slice 字段，则需要对该解决方案进行调整。

由于未导出sha256.digest，因此我们只能使用反射( reflect 程序包)来实现我们的目标，这必然会增加一些计算延迟。

执行此操作的示例实现:

type Cached2 struct {
    origv   reflect.Value
    hasherv reflect.Value
    hasher  hash.Hash

    result [sha256.Size]byte
}

func NewCached2(fixed []byte) *Cached2 {
    h := sha256.New()
    h.Write(fixed)

    c := &Cached2{origv: reflect.ValueOf(h).Elem()}
    hasherv := reflect.New(c.origv.Type())
    c.hasher = hasherv.Interface().(hash.Hash)
    c.hasherv = hasherv.Elem()

    return c
}

func (c *Cached2) Sum(data []byte) []byte {
    // Set state of the fixed hash:
    c.hasherv.Set(c.origv)

    c.hasher.Write(data)
    return c.hasher.Sum(c.result[:0])
}

测试它:

var c2 = NewCached2(fixed)
fmt.Printf("%x\n", c2.Sum(variantA))
fmt.Printf("%x\n", c2.Sum(variantB))

输出再次相同:

fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c

这样就行了。

“终极”，最快的解决方案

如果不涉及反射，Cached2可能会更快。如果我们想要一个更快的解决方案，只需将sha256.digest类型及其方法复制到我们的程序包中，这样我们就可以直接使用它，而不必求助于反射。

如果这样做，我们将可以访问digest struct值，我们可以像下面这样简单地制作一个副本:

var d digest
// init d
saved := d

恢复它就像:

d = saved

我只是简单地将crypto/sha256包“克隆”到了我的工作区，然后将digest类型更改/导出为Digest只是为了进行演示。然后使用这种mysha256.Digest类型，我实现了Cached3，如下所示:

type Cached3 struct {
    orig   mysha256.Digest
    result [sha256.Size]byte
}

func NewCached3(fixed []byte) *Cached3 {
    var d mysha256.Digest
    d.Reset()
    d.Write(fixed)

    return &Cached3{orig: d}
}

func (c *Cached3) Sum(data []byte) []byte {
    // Make a copy of the fixed hash:
    d := c.orig
    d.Write(data)
    return d.Sum(c.result[:0])
}

测试它:

var c3 = NewCached3(fixed)

fmt.Printf("%x\n", c3.Sum(variantA))
fmt.Printf("%x\n", c3.Sum(variantB))

再次输出是相同的。因此，这也适用。

基准测试

我们可以使用以下代码对性能进行基准测试:

func BenchmarkCached1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        c1.Sum(data)
        c1.Sum(data2)
    }
}

func BenchmarkCached2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        c2.Sum(variantA)
        c2.Sum(variantB)
    }
}

func BenchmarkCached3(b *testing.B) {
    for i := 0; i < b.N; i++ {
        c3.Sum(variantA)
        c3.Sum(variantB)
    }
}

基准测试结果(go test -bench . -benchmem):

BenchmarkCached1-4   1000000     1569 ns/op     0 B/op    0 allocs/op
BenchmarkCached2-4   2000000      926 ns/op     0 B/op    0 allocs/op
BenchmarkCached3-4   2000000      872 ns/op     0 B/op    0 allocs/op

Cached2比Cached1快约 41％，这非常引人注目且美观。与Cached3相比，Cached2仅提供了“很少”的性能提升，后者是 6％。 Cached3的比Cached1的快44％。

还要注意，所有解决方案都没有使用任何分配，这也是不错的选择。

结论

对于那额外的40％或44％，我可能不会选择Cached2或Cached3解决方案。当然，这实际上取决于性能对您的重要性。如果重要的话，我认为Cached2解决方案可以在最小的复杂度和明显的性能提升之间找到一个很好的折衷方案。它确实构成了威胁，因为将来的Go实现可能会破坏它。如果有问题，Cached3通过复制当前实现来解决此问题(并稍微提高其性能)。