ORA_HASH函数使用的算法是什么?

17
我在工作中遇到了一些代码,仅仅是因为需要调用 UUID 字符串上的 ORA_HASH 函数 (文档) 来进行数据库调用。它这样做的原因是因为它需要该值来向另一个系统进行服务调用,该系统似乎使用 ORA_HASH 进行分区。
我想知道 ORA_HASH 使用的算法,以便我可以重新实现它,以便为一个应用程序进行类似的服务调用,该应用程序甚至无法访问真正的数据库,更不用说 Oracle 了。到目前为止,我只能找到相当于 Oracle API 文档的东西。
为了非常清楚,我需要克隆 ORA_HASH,因为那是我无法控制的另一个系统使用的方法,并且我需要与该系统集成。是的,如果可以使用 MD5 等真正标准的算法,那将是很好的,但我不能,除非 ORA_HASH 在其底层就是这个算法。
提出除 ORA_HASH 以外的哈希算法的答案或评论是没有帮助的。这个问题特别涉及 ORA_HASH,而不是哈希或分区。

1
@mathguy 我认为这不是完全重复,尽管这是有争议的。对我来说,那个问题更多地涉及如何创建一个类似于ORA_HASH概念的东西。并不一定需要精确使用ORA_HASH算法来回答那个问题。 - Jon Heller
1
只需实现一个标准的哈希算法,比如MD5,大多数编程语言都原生支持。这样你所有的“系统”就可以保持一致了。不要自己编写算法。 - tbone
2
https://chessprogramming.wikispaces.com/Bob+Jenkins 看起来是一个不错的选择。(但 burble 可以被修改和种子化) - wildplasser
3
据我所知,目前并不清楚ora_hash的确切实现方式。ora_hash被用作分桶函数,因此将数据分成x部分是有意义的。然而,为什么这个服务需要ora_hash的值才能发起调用呢?如果需要ora_hash,那么这个服务在我看来就是有问题的。请修复这个服务。(我知道,你会告诉我你不能操作这个服务;-)) - tbone
2
不是答案,但是...你能通过存储过程连接到Oracle并让数据库为你执行吗?虽然不是最优雅的方式,但是它已经100%实现了。 - DvTr
显示剩余17条评论
2个回答

24

另一个似乎使用ORA_HASH的系统。

如果它“似乎使用”ORA_HASH,那么进行一些反向工程并检查确切调用的内容以及函数的反汇编代码是有意义的。

然而,如果你想深入了解Oracle内部,则以下内容可能会有所帮助。

首先,你必须弄清楚调用了哪个内部C函数。为此,你可以在一个会话中执行一些长时间运行的代码。我运行了以下代码:

select avg(ora_hash(rownum)) id from
(select rownum from dual connect by rownum <= 1e4),
(select rownum from dual connect by rownum <= 1e4);

它也可以是PL/SQL代码,你只需要确保不断调用 ora_hash。
当程序运行时: 我在Windows上进行了测试,看起来ora_hash是...->evaopn2()->evahash()->...。
现在让我们搜索evahash。我们非常幸运,因为官方网站上有一个标题文件https://oss.oracle.com/projects/ocfs-tools/src/branches/new-dir-format/libocfs/Linux/inc/ocfshash.h带有evahash的链接。
最后,这里是实际的C代码页面:http://burtleburtle.net/bob/hash/evahash.html
到目前为止一切都很顺利,我们记得如果我们将其构建为库(在Windows上是DLL),则可以在Oracle中使用外部C函数。例如,在我的Win x64上,如果我更改函数签名:
extern "C" ub4 hash( ub1 *k, ub4 length, ub4 initval)

这个函数可以在Oracle中成功执行。但是,正如你所见,它与Oracle中的ora_hash略有不同。这个函数接受值、其长度和initval(可以是种子),而Oracle中的signature是ora_hash(expr,max_bucket,seed_value)。

让我们来尝试测试Oracle

SQL> select ora_hash(utl_raw.cast_to_raw('0'), power(2, 32) - 1, 0) oh1,
  2         ora_hash('0', power(2, 32) - 1, 0) oh2,
  3         ora_hash(0, power(2, 32) - 1, 0) oh3,
  4         ora_hash(chr(0), power(2, 32) - 1, 0) oh4
  5    from dual;

       OH1        OH2        OH3        OH4
---------- ---------- ---------- ----------
3517341953 3517341953 1475158189 4056412421

C

int main()
{
    ub1 ta[] = {0};
    ub1* t = ta;
    cout << hash(t, 1, 0) << endl;
    ub1 ta0[] = {'0'};
    ub1* t0 = ta0;
    cout << hash(t0, 1, 0) << endl;
    return 0;
}

1843378377
4052366646

没有任何一个数字匹配。

那么问题是什么呢?

ora_hash接受几乎任何类型的参数(例如select ora_hash(sys.odcinumberlist(1,2,3)) from dual),而C函数接受字节数组的值。这意味着在函数调用之前会发生一些转换。

因此,在使用上述C哈希函数之前,您必须弄清楚实际值在传递给它之前如何转换。

您可以使用IDA PRO + hex rays对Oracle二进制文件进行反向工程,但这可能需要数天时间。更不用说特定于平台的细节。

因此,如果您想模仿ora_hash,最简单的方法是安装Oracle Express Edition并使用它来调用ora_hash。

我希望这很有趣。祝你好运。

更新

ora_hash和dbms_utility.get_hash_value可以相互映射(请参见https://jonathanlewis.wordpress.com/2009/11/21/ora_hash-function/)。

SQL> select dbms_utility.get_hash_value('0', 0 + 1, 1e6 + 1) ha1,
  2         ora_hash('0', 1e6, 0) + 1 ha2
  3    from dual;

       HA1        HA2
---------- ----------
    338437     338437

如果我们展开dbms_utility的包体,我们会看到以下声明。
  function get_hash_value(name varchar2, base number, hash_size number)
    return number is
  begin
    return(icd_hash(name, base, hash_size));
  end;

并且

  function icd_hash(name      varchar2,
                    base      binary_integer,
                    hash_size binary_integer) return binary_integer;
  pragma interface(c, icd_hash);

让我们搜索icd_hash,我们可以发现它被映射到_psdhsh (https://yurichev.com/blog/50/)。现在是时候反汇编oracle.exe并从中提取_psdhsh的代码了。也许我明年会花一些时间在这上面。


我相信我可以使用这个来更快地构建答案。一定有一种格式可以传递进去,不会被过多转换。 - Dylan Brams
@DylanB 加油。如果超过悬赏期限,别担心,我会再创建一个500点的悬赏,并授予给你或任何其他首先构建它的人。(假设代码是PL/SQL或可从PL/SQL调用并匹配ORA_HASH。) - Jon Heller
@Dylan B,我相信如果你至少弄清楚varchar2参数的工作原理就足够了。我使用一字节值进行测试,以使其尽可能简单,并避免出现大端/小端和其他问题。Oracle可能会向值添加一个“服务”字节或反转所有字节的位。它可能是更复杂的东西,如果没有对Oracle二进制文件进行逆向工程,很难弄清楚。 - Dr Y Wit
@Jon Heller,逆向工程更多地是针对C/汇编开发人员的。因此,您可能希望添加这些标签以吸引受众。虽然我认为与这个人http://burtleburtle.net/bob/index.html联系会更容易。如果他提供有关转换为“unsigned char”数组的答案,请告诉我。 - Dr Y Wit
虽然您没有完全回答我的问题,但是您的回答对于这个卑微的企业开发者来说仍然非常令人印象深刻,也是朝着正确方向迈出的一大步。谢谢。 - Kaypro II

1
这并没有回答有关ora_hash背后实际算法的问题。这只是一个在PL/SQL中使用ora_hash的示例(回答@JonHeller的评论):
该函数:
SQL> create or replace function get_ora_hash(i_str in varchar2, i_max_bucket in number default 4294967295, i_seed number default 0)
return number deterministic
parallel_enable
as
  rv number:= 0;
begin

select ORA_HASH(i_str, i_max_bucket, i_seed) 
into rv 
from dual;

return rv;

end;
Function created.

并使用它:

SQL> declare
  l_val number;
begin
  l_val := get_ora_hash('test');
  dbms_output.put_line(l_val);
end;
 PL/SQL procedure successfully completed.

Dbms Output:
2662839991

你还可以尝试使用RESULT_CACHE或其他技术来进一步提高速度。

它已经非常快了。例如,在大表上调用该函数100万次:

SQL> set serveroutput on
SQL> declare
  l_val number;
  l_start_dte timestamp;
  l_end_dte timestamp;
  l_interval INTERVAL DAY(9) TO SECOND(9);
  l_cnt number := 0;
begin
  l_start_dte:= systimestamp;
  --for rec in (select object_name from dba_objects)
  for rec in (select name from my_big_table where rownum <= 1000000)
  loop
    l_cnt := l_cnt + 1;
    l_val := get_ora_hash(rec.name);
  end loop;
  l_end_dte:= systimestamp;
  l_interval := l_end_dte - l_start_dte;
  dbms_output.put_line('Rows processed: ' || l_cnt 
    || ', Start: ' || l_start_dte  
    || ', End: ' || l_end_dte 
    || ', Interval: ' || l_interval);
end;
Rows processed: 1000000, Start: 14-DEC-17 02.48.31.138212 PM, End: 14-DEC-17 02.48.41.148884 PM, Interval: +000000000 00:00:10.010672000
 PL/SQL procedure successfully completed.

基本上每秒100k行,这还包括您可能担心的任何上下文切换。
如果由于性能原因需要重现ORA_HASH,我建议您的性能瓶颈可能在其他地方。

我正在使用的遮罩产品已经可以做到这一点。从“select ora_hash ... from dual”的上下文切换非常缓慢。如果代码能够执行return ora_hash...,那么速度会快得多,但是这是不允许的。因此,了解ORA_HASH算法可能很有用,因为我们可以在纯PL/SQL中重新创建它。 - Jon Heller
@JonHeller 我更新了我的答案。它实际上非常快。 - tbone
很不幸,我们的数据脱敏产品在处理每一行中的每一列时都会多次调用ORA_HASH函数,而我们需要处理数十亿行数据。因此,寻找替代方案仍然是非常有必要的。 - Jon Heller
@JonHeller 我认为即使你找到了一个产生相同结果的替代实现,它也不会更快。如果可以的话,请发布您的数据屏蔽实现,我敢打赌您的缓慢是由此过程中的其他因素引起的。 - tbone
2
我认为这个问题应该拆分成另一个问题(即“如何从PL / SQL调用ora_hash?”)。 - Kaypro II
@KayproII 也许是这样,但 JonHellers 的问题实际上是关于 ora_hash 性能的担忧,这可能是为什么有些人想知道确切的算法,以便他们可以采用另一种方式实现。我意识到其他人只是想避免使用 Oracle(和许可问题)而已。 - tbone

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接