前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >vppinfra----hash结构简单介绍

vppinfra----hash结构简单介绍

作者头像
dpdk-vpp源码解读
发布2023-03-07 16:58:21
4130
发布2023-03-07 16:58:21
举报
文章被收录于专栏:DPDK VPP源码分析DPDK VPP源码分析

下图是工业级散列表设计需要考虑的到问题:我们也围绕下面几项来讲解讲解一下 vpp hash表的处理逻辑。可以帮助我们在业务开发中选择合适的存储结构。

  • hash结构管理头及键值对结构体
代码语言:javascript
复制
/* Vector header for hash tables. */
typedef struct hash_header
{
  /* hash结构中当前已存储d的元素个数*/
  uword elts;
  /*Bit 1和bit2 表是否支持动态扩容调整哈希*/
  u32 flags;
  /* Set if user does not want table to auto-resize when sufficiently full. */
#define HASH_FLAG_NO_AUTO_GROW    (1 << 0)
  /* Set if user does not want table to auto-resize when sufficiently empty. */
#define HASH_FLAG_NO_AUTO_SHRINK  (1 << 1)
  /* Set when hash_next is in the process of iterating through this hash table. */
#define HASH_FLAG_HASH_NEXT_IN_PROGRESS (1 << 2)
  /*占有sizeof(hash_pair_t) 空间大小的个数的2的次幂数:
     h->log2_pair_size = max_log2(x)
     比如x=8 = 2的3次方(_size = 3);
      x=9 :2的3次方不够(_size=3+1) 
     为0时,说明当前不存储value,只存储key。*/
  u32 log2_pair_size;

  /* 计算散列键的函数指针。哈希函数是哈希表素数大小的模等于(vec_len (v))。*/
  hash_key_sum_function_t *key_sum;

  /* Special values for key_sum "function". */
#define KEY_FUNC_NONE    (0)  /*< sum = key */
#define KEY_FUNC_POINTER_UWORD  (1)  /*< sum = *(uword *) key */
#define KEY_FUNC_POINTER_U32  (2)  /*< sum = *(u32 *) key */
#define KEY_FUNC_STRING         (3)  /*< sum = string_key_sum, etc. */
#define KEY_FUNC_MEM    (4)  /*< sum = mem_key_sum */
  /* key比较函数,不同的key类型对比不同的比较函数 */
  hash_key_equal_function_t *key_equal;
  /* 用户数据的勾子函数,在mhash结构中使用Hook for user's data.  Used to parameterize sum/equal functions. */
  any user;
  /* Format a (k,v) pair */
  format_function_t *format_pair;
  /* 格式化输出函数 的参数*/
  void *format_pair_arg;
  /* 哈希函数获得的键值的bitmap位2层意思:
   * 0是:是当前未存储数据或者当前已经存储数据但有hash冲突
   * 1:当前键值对应位置已存储数据*/
  uword is_user[0];
} hash_t;

/* 键值对结构体 */
typedef struct
{
  /*默认key是8字节*/
  uword key;
  /* 数值. Length is 2^log2_pair_size - 1. */
  uword value[0];
} hash_pair_t;

通过上面的键值对结构,可以看出key是uword类型,最多存储8个字节。所以这里key一般存储的是key的指针。

  • hash函数内存分布

hash结构分为了3部分:hash 头结构、hash元素bitmap、hash键值对区域;

具体内存分布图如下,通过内存分布此hash是一个数组方式存储。

  • hash函数冲突解决及hash表扩容问题。

hash哈希实现必须要考虑的2个问题:哈希冲突解决方式及hash表扩容问题。

vpp 的hash在解决冲突时存在2中情况的:

  1. hash表值存储key,不记录value时。 hash结构体中log2_pair_size= 0时,表述只存储key。 存储的是指针hash_pair_t*,变成vec_head_t结构存储。如下图所示:
  1. hash表存储<key-value>时, hash结构体中log2_pair_size 非0时,存储的是hash_pair_indirect_t结构。使用alloc_len保存hash_pair_t结构数量。

增加的2中结构体,如下:

代码语言:javascript
复制
/* 哈希间接存储结构:当log2_pair_size >0 时使用
*/
typedef struct
{
  /* pair vector */
  hash_pair_t *pairs;
  /* padding */
  u8 pad[sizeof (uword) - sizeof (hash_pair_t *)];
  /* allocated length */
  uword alloc_len;
}
hash_pair_indirect_t;
/* Direct / Indirect pair union */
typedef union
{
  hash_pair_t direct;
  hash_pair_indirect_t indirect;
} hash_pair_union_t;

疑问:为什么记录value和不记录value处理不一样:

hash_pair_t 结构大小是是8字节,value是可变长的。所以在存储value时,每个hash对的大小是不确定的,所以不能使用hash_pair_t

hash资源不足,如何进行扩容的:

当装载因子大于0.75时,hash表中flag标识如果设置自动扩容标识,会进行hash 2倍的扩容。而扩容的方式也是比较原始的,直接申请一块2倍数据存储大小的新的hash表。遍历旧的hash表,重新set到新的hash表中。释放旧的hash表并返回新的hash表。

代码语言:javascript
复制
void *
_hash_set3 (void *v, uword key, void *value, void *old_value)
{
  hash_t *h;

  if (!v)
    v = hash_create (0, sizeof (uword));

  h = hash_header (v);
  (void) lookup (v, key, SET, value, old_value);

  if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
    {
      /* 当哈希因子大于0.75时,hash设置自动扩容标识,
       会进行hash 2倍的扩容. */
      if (4 * (h->elts + 1) > 3 * vec_len (v))
  v = hash_resize (v, 2 * vec_len (v));
    }
  return v;
}
static void *
hash_resize_internal (void *old, uword new_size, uword free_old)
{
  void *new;
  hash_pair_t *p;

  new = 0;
  if (new_size > 0)
    {
      hash_t *h = old ? hash_header (old) : 0;
      new = _hash_create (new_size, h);
      /* *INDENT-OFF* */
      hash_foreach_pair (p, old, {
  new = _hash_set3 (new, p->key, &p->value[0], 0);
      });
      /* *INDENT-ON* */
    }

  if (free_old)
    hash_free (old);
  return new;
}

从hash表冲突的处理方式及hash扩容的方法,可以看出hash不太适合大规格数据的存储,并且hash是不支持多线程的。上万级别的存储数据建议使用bihash。

  • hash结构的创建和操作函数

hash函数创建全都是调用hash_create2来实现的,只是hash函数及hash比较函数不同。具体分为了下面6类:

代码语言:javascript
复制
hash_create2((elts),0,(value_bytes),
               (hash_key_sum_function_t *) KEY_FUNC_NONE,
               (hash_key_equal_function_t *) KEY_FUNC_NONE,
               0,0)
  • 总结 hash函数底层实现也依赖于vec结构。这里需要注意hash函数是不支持多线程的。所以vpp在使用一般用来存储配置表项,都是在main核中完成的。在配置下发时,会启动同步机制将worker线程锁住。所以不存在多线程并发的问题。存储量比较小时,会选择使用hash结构。当Key的大小大于8字节时,需要额外内存(比如pool结构)保存key的内容,以便于对管理hash数据。
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-09-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 DPDK VPP源码分析 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档