使用分块和散列函数加速重复数据删除

摘要

本文将介绍英特尔® 智能存储加速库(英特尔® ISA-L) 中的分块和散列函数。 英特尔 ISA-L 是一种算法库,可满足密钥存储市场的各种需求,包括面向英特尔® 架构 (IA) 的优化和提高效率、数据完整性、安全性/加密、删除码、压缩、CRC,AES 等。

随着云存储中数据的不断激增,对存储空间和数据安全性的要求也越来越高。 一种被称为重复数据删除的技术可减少特定文件中的重复数据,从而有效提升存储空间利用率。 在重复数据删除过程中,可结合使用散列函数生成面向数据块的指纹。 过去,投入生产环境后,这些流程会占用极大的 CPU 资源。 借助英特尔® 处理器,英特尔 ISA-L 可提供工具实现加速目的,加速对象小到小型办公室 NAS 应用,大到企业存储系统。

样本代码

注: 如欲了解有关如何构建可执行文件的更多详情,请参阅英特尔 ISA-L 程序包中的说明。 本文结尾处的资源部分将提供申请表。

为满足云存储的这些特定需求,英特尔 ISA-L 提供了加速的多缓冲散列和滚动散列 (rolling hash) 以支持重复数据删除。 示例代码演示了如何高效组合利用这两种函数。

实施详情

示例代码显示,可变长度分块和多缓冲散列可轻松组合。 组合流程涵盖:

1. 设定参数,包括最小值、最大值和平均数据块大小。

w = 32;				// Set width of rolling hash window
min_chunk = 1024;		// Smallest chunk allowed
mean_chunk = 4 * 1024;		// Target for average chunk size
max_chunk = 32 * 1024;		// Largest allowed chunk size

条件 “hash & mask == trigger” 可明确查找界限时的命中频率。 通常情况下,当窗口化散列 (windowed hash) 满足下列条件后开始设定界限:

hash & mask == trigger

帮助函数可选取通常返回平均数据块大小的掩码值。

mask = rolling_hashx_mask_gen(mean_chunk, 0);
trigger = rand() & mask;

这样每次就可轻松地以数据块形式浏览数据。

while (remain > max_chunk)
{

2. 向前跳到最小数据块。

rolling_hash1_reset(&state, p + min_chunk - w);

3. 从最小数据块开始浏览数据,直到查找到界限或命中最大数据块。

rolling_hash1_run(&state, p + min_chunk, max_chunk - min_chunk,  mask,     trigger, &offset);

4. 在数据块界限上处理数据块。

process_chunk(p, min_chunk + offset);

5. 然后转至下一数据块。

p += offset + min_chunk;
remain -= (offset + min_chunk);
}

流程

确定数据块界限后,下一流程是生成整个数据块的加密散列。 该散列函数是该数据块的独有标识,有助于识别重复数据块。

高性能多缓冲散列采用异步散列提交() 调用。 get_next_job_ctx() 和 put_next_job_ctx() 这两种支持函数有助于维护多缓冲散列任务环境结构池,并提取其旋转和使用。

void process_chunk(uint8_t * buff, int len)
{
      SHA256_HASH_CTX *ctx;

      ctx = get_next_job_ctx();
      ctx = sha256_ctx_mgr_submit(&mb_hash_mgr, ctx, buff, len, HASH_ENTIRE);

      if (ctx) {
            process_finished_hash(ctx);
            put_next_job_ctx(ctx);
      }
}

这样可预先分配环境池,并确保 alloc/free 独立于处理循环。

处理散列的最后一步在已完成的数据块上进行,返回值为 process_finished_hash()。 多缓冲散列接口最适用于队列中的多项任务,并能高效处理多个散列,即使提交的任务长度不同。

步骤 2-5 中的循环处理完成后,大部分数据块界限也已找到和散列,除剩余片段以及少量残留于多缓冲队列中的数据块)。 最后一步是刷新队列并处理最后的数据块。

while ((ctx = sha256_ctx_mgr_flush(&mb_hash_mgr)) != NULL)
     process_finished_hash(ctx);

这时,所有数据块都已处理完。 在重复数据删除(可变长度分块并生成数据块的加密散列)过程中查找到的计算密集型函数均为完整函数。

对于散列环境共用 (pooling) 函数来说,下列函数可提取 mb-hash 结构共用,从而跟踪锁定散列任务。

SHA256_HASH_CTX ctxpool[SHA256_MAX_LANES], *last_ctx;
SHA256_HASH_CTX_MGR mb_hash_mgr;

void setup_chunk_processing(void)
{
      int i;

      sha256_ctx_mgr_init(&mb_hash_mgr);

      for (i = 0; i < HASH_POOL_SIZE; i++)
            hash_ctx_init(&ctxpool[i]);

      last_ctx = &ctxpool[0];
}

SHA256_HASH_CTX *get_next_job_ctx(void)
{
      int i;
      SHA256_HASH_CTX *ctx;

      if (last_ctx && hash_ctx_complete(last_ctx))
            return last_ctx;

      for (i = 0; i < HASH_POOL_SIZE; i++) {
            if (hash_ctx_complete(&ctxpool[i]))
                  return &ctxpool[i];
      }
      ctx = sha256_ctx_mgr_flush(&mb_hash_mgr);
      assert(ctx != NULL);
      return ctx;
}

void put_next_job_ctx(SHA256_HASH_CTX * ctx)
{
      if (ctx && hash_ctx_complete(ctx))
            last_ctx = ctx;
}

结论

有关 C 示例代码的概述表明,我们能够轻松应用英特尔 ISA-L 的分块和散列函数。存储开发人员可利用此处的学习资料,快速将其应用于基于 IA 运行的云存储环境。

相关链接与资源:

关于作者

本文作者向 Greg Tucker 和 Colleen Culberson 对本文所做出的贡献表示感谢。

作者: Quoc-Thai Le 是一名软件工程师,在英特尔工作了 20 多年。 他主要关注软件自动化、服务器能耗与性能分析,以及软件定义存储等领域。

Para obtener información más completa sobre las optimizaciones del compilador, consulte nuestro Aviso de optimización.