bigquery的farm_fingerprint不是随机分布的吗？

Question

当我获取有序集（即数字用户 ID）的哈希值时，其 MD5 哈希值的结果分布近似均匀分布：即。如果我将哈希值分为 n 个分位数，则在哈希分位数中找到低编号用户 ID (10001) 的可能性与高编号用户 ID (99999) 相同。另一方面，如果我使用 farm_fingerprint 执行此操作，则生成的哈希存储桶似乎不是均匀分布的：低编号的存储桶具有更多低编号的用户 ID。该文档没有立即提到哈希值的分布属性，我在其他参考文献中找不到它。

我意识到均匀分配用户 ID 的更好方法是为每个用户 ID 分配一个随机数，如此处所述；我的问题特别是关于提到的 FARM_FINGERPRINT 哈希的分布属性。

下面是一个示例查询，说明了分位数的相对偏差：

    SELECT
      avg(n_low) as avg_n_low,
      avg(n_med) as avg_n_med,
      avg(n_high) as avg_n_high
    FROM (
      SELECT bucket_id,
        SUM(CASE WHEN label = 'low' THEN 1 ELSE 0 END) as n_low,
        SUM(CASE WHEN label = 'med' THEN 1 ELSE 0 END) as n_med,
        SUM(CASE WHEN label = 'high' THEN 1 ELSE 0 END) as n_high
      FROM (
        SELECT
          x,
          label,
          ntile(1000) OVER (ORDER by h) as bucket_id 
        FROM (
          SELECT x,
          CASE
            WHEN x BETWEEN 00001 and 20000 THEN 'low' 
            WHEN x BETWEEN 20001 and 40000 THEN 'med'
            WHEN x BETWEEN 40001 and 60000 THEN 'high' 
          END as label,
          --FARM_FINGERPRINT(CAST(x AS STRING)) h
          MD5(CAST(x AS STRING)) h
          FROM UNNEST((SELECT GENERATE_ARRAY(1,60000,10) xs)) AS x
        )
      )
      GROUP BY 1
    )
    WHERE
      bucket_id < 100
      --bucket_id > 900

我将 2000 个“低”、“中”和“高”用户分为 100 个桶。人们可以看到，使用FARM_FINGERPRINT产生的桶平均值的方差高于MD5，即。FARM_FINGERPRINT对于 < 100 的存储桶，似乎比 MD5 具有更高的 avg_n_low ，对于 > 900 的存储桶，似乎具有更高的 avg_n_high 。通过哈希对存储桶的分配并不像 那样均匀分布MD5。

我意识到目前这有点主观，如果我遗漏了某些内容或可以提供更多详细信息，请告诉我。

Answer 1

指纹函数与加密哈希函数不属于同一类。他们并不试图产生接近随机/不可预测的输出。换句话说，该值是否可逆并不重要。指纹函数的要求是简单地为每个唯一输入生成确定性唯一哈希值（避免冲突）。由于要求更简单，它们应该比加密哈希更快，并且对于为大量数据生成代理键非常有用，尤其是在 MMP 平台上。请注意，如果您的自然密钥包含敏感数据，您可能不想使用 farm_fingerprint。如果您确实需要生成一个序列，尤其是密集排列的序列，我使用了序列表（我必须这样做才能将 id 提供给只能采用 32 位整数的下游系统）。通用示例（注意，这是 hive sql，bigquery 分析函数可能有点不同）：

create table entity_seq_xref
(  natural_key string
  ,sequence_id integer
);
insert into entity_seq_xref
select natural_key
    ,coalesce(last_sequence_id,0) + row_number() over (partition by 1) as sequence_id
from (select s.natural_key
            ,x.sequence_id
            ,max(x.sequence_id) over (partition by 1) as last_sequence_id
      from source_entity s
      left join entity_seq_xref x
          on x.natural_key = s.natural_key
) m
where x.sequence_id is null
;