[go: up one dir, main page]

CN110036381B - 存储器内数据搜索技术 - Google Patents

存储器内数据搜索技术 Download PDF

Info

Publication number
CN110036381B
CN110036381B CN201680090880.3A CN201680090880A CN110036381B CN 110036381 B CN110036381 B CN 110036381B CN 201680090880 A CN201680090880 A CN 201680090880A CN 110036381 B CN110036381 B CN 110036381B
Authority
CN
China
Prior art keywords
key
hash
transaction processing
index
processing data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201680090880.3A
Other languages
English (en)
Other versions
CN110036381A (zh
Inventor
N·皮什
A·S·T·帕勒拉穆迪
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Visa International Service Association
Original Assignee
Visa International Service Association
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Visa International Service Association filed Critical Visa International Service Association
Publication of CN110036381A publication Critical patent/CN110036381A/zh
Application granted granted Critical
Publication of CN110036381B publication Critical patent/CN110036381B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/23—Updating
    • G06F16/2379—Updates performed during online database operations; commit processing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/27—Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2255—Hash tables
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Computing Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明的实施例涉及一种用于在分布式计算系统中执行高效数据搜索的方法。所述方法可包括接收第一密钥。所述方法还可包括从多个散列映射当中确定与所述第一密钥相关联的散列映射。在一些实例中，所获得的散列映射将一组密钥的分区映射到特定索引值。所述方法还可包括使用所确定的散列映射确定与第二密钥相关联的索引值。所述方法还可包括使用所确定的索引值确定与所述第一密钥相关联的交易处理数据并且提供所述交易处理数据。所述多个散列映射的利用可使得能够使用所述分布式计算系统的电子装置的板载存储器执行数据搜索。

Description

存储器内数据搜索技术
背景
分布式计算系统通常用于管理和处理大型数据集。分布式计算系统可将数据库分布在若干计算机上，所述计算机通过高速网络等各种通信介质彼此通信。分布式数据库系统可由单个逻辑数据库组成，所述逻辑数据库可拆分为不同片段，每个片段存储在分布式计算系统的单个计算机(例如，节点)上。分布式计算系统可能会面临如何管理和/或访问大型数据集的挑战。例如，协调计算机之间的任务所需的信息交换和额外计算是一种在集中式系统中不会出现的开销。另外，分布式计算系统可能容易出现错误，因为当数据集在分布式计算系统的许多计算机上扩散时，更加难以确保算法的正确性。另外，在分布式计算系统中搜索数据集的特定部分可能在计算上代价较大，且可能产生变化的搜索时间。因此，可对数据集和分布式计算系统进行改进，以提供更高效的搜索时间。
用于执行密钥搜索的当前技术可包含为密钥构建搜索树。然而，维持一大组密钥的搜索树的存储器开销可能不切实际，甚至是禁止的。搜索树(以及其它容器，例如散列映射)还有可能受制于特定存储器约束条件，从而使得大数据集的存储无效。例如，当将条目插入到搜索树中时，可能需要对树进行排序或重新生成以保留搜索功能。在添加、删除和/或修改条目时重构建或重排大数据集的搜索树可能导致资源的大量利用，且可能提供不准确的搜索结果或延迟的处理。一些技术可利用散列表或其它容器以用于执行密钥搜索。然而，这些容器具有类似的开销问题。另外，当前技术的利用可能存在由搜索冲突导致的缺点，因为许多装置可能在相同时间访问容器。为了避免冲突，可能连续执行请求，这会导致更长的计算时间。另外，搜索树、散列映射或其它容器可能过大(例如，5TB)而无法加载到分布式计算系统中的节点的存储器(例如，128GB的随机存取存储器(RAM))中，因此它们通常存储在集中位置。因此，在这些情境中搜索密钥可能需要大规模计算，且可能产生变化的搜索时间，因为搜索的数据大小很大，且许多系统可能在相同时间尝试访问数据。因此，可对数据集和分布式计算系统进行改进，以提供更高效的搜索时间。
本发明的实施例单独地以及共同地解决这些问题和其它问题。
发明内容
本发明的一个实施例涉及一种包括接收第一密钥的方法。所述方法还可包括从多个散列映射当中确定与第一密钥相关联的散列映射，个别散列映射将一组密钥的分区映射到特定索引值，其中与第一密钥相关联的散列映射被配置成加载到电子装置的板载存储器中。所述方法还可包括使用所确定的散列映射确定与第二密钥相关联的索引值。所述方法还可包括使用所确定的索引值确定与第一密钥相关联的交易处理数据，其中利用多个散列映射使得能够使用电子装置的板载存储器执行查找。所述方法还可包括提供所确定的交易处理数据。
本发明的另一实施例涉及一种包括一个或多个管理器节点和多个工作节点的系统一个或多个管理器节点个别地包括第一处理器和耦合到第一处理器的第一计算机可读介质，所述第一计算机可读介质包括可由第一处理器执行以实施第一方法的代码。第一方法可包括接收请求消息，所述请求消息包括第一密钥。第一方法还可包括将请求消息的至少一部分传输到多个工作节点中的一个或多个工作节点。第一方法还可包括接收与请求消息相关联的响应消息。第一方法还可包括传输响应消息。多个工作节点中的工作节点可个别地包括第二处理器和耦合到第二处理器的第二计算机可读介质，所述第二计算机可读介质包括可由第二处理器执行以实施第二方法的代码。第二方法可包括获得包括第一密钥的第一散列映射，其中第一散列映射被配置成存储在多个工作节点的板载存储器中。第二方法还可包括利用第一密钥和第一散列映射确定第二散列映射，其中利用第二散列映射使得能够用工作节点的板载存储器确定索引值。第二方法还可包括获得与第一密钥相关联的第二散列映射，所述第二散列映射将一组密钥映射到特定索引值。第二方法还可包括使用第二散列映射确定与第一密钥相关联的索引值。第二方法还可包括使用所确定的索引值来获得与第一密钥相关联的交易处理数据，其中利用第二散列映射使得能够使用工作节点的板载存储器确定索引值。第二方法还可包括提供所确定的交易处理数据。
本发明的另一实施例涉及一种包括一个或多个管理器节点、多个工作节点和集中式数据存储区的系统。一个或多个管理器节点个别地包括第一处理器和耦合到第一处理器的第一计算机可读介质，所述第一计算机可读介质包括可由第一处理器执行以实施第一方法的代码。第一方法可包括接收请求消息，所述请求消息包括第一密钥。第一方法还可包括获得包括第一密钥的第一散列映射，其中所述第一散列映射被配置成存储在管理器节点的板载存储器上。第一方法还可包括利用第一密钥和第一散列映射确定第二散列映射。第一方法还可包括向多个工作节点中的工作节点发送信息，所述信息包括第一密钥，所述工作节点对应于所确定的第二散列映射。第一方法还可包括接收与请求消息相关联的响应消息。第一方法还可包括传输响应消息。多个工作节点中的工作节点可个别地包括第二处理器和耦合到第二处理器的第二计算机可读介质，所述第二计算机可读介质包括可由第二处理器执行以实施第二方法的代码。第二方法可包括获得与第一密钥相关联的第二散列映射，所述第二散列映射将一组密钥映射到特定索引值。第二方法还可包括使用第二散列映射确定与第一密钥相关联的索引值。第二方法还可包括使用所确定的索引值来获得与第一密钥相关联的交易处理数据，其中利用第二散列映射使得能够使用工作节点的板载存储器确定索引值。第二方法还可包括提供所确定的交易处理数据。集中式数据存储区可供所述一个或多个管理器节点和所述多个工作节点访问。集中式数据存储区可存储索引列表，所述索引列表包括交易处理数据。
本发明的另一实施例涉及一种电子装置，所述电子装置包括处理器和耦合到处理器的计算机可读介质，所述计算机可读介质包括可由处理器执行以实施方法的代码。所述方法可包括接收与数据集相关联的标识符。所述方法还可包括生成对应于数据集的数据子集的索引列表。所述方法还可包括存储索引列表。对于索引列表的每个条目，所述方法还可包括确定与索引列表的条目相关联的第一密钥。所述方法还可包括用第一密钥和与索引列表的条目相关联的索引值更新第一散列映射。所述方法还可包括用第一密钥和第一散列映射的标识符更新第二散列映射。
本发明的另一实施例涉及一种电子装置，所述电子装置包括处理器和耦合到处理器的计算机可读介质，所述计算机可读介质包括可由处理器执行以实施方法的代码。所述方法可包括接收与数据集相关联的标识符。所述方法还可包括生成对应于数据集的数据子集的索引列表。所述方法还可包括存储索引列表。对于索引列表的每个条目，所述方法还可包括确定与索引列表的条目相关联的第一密钥。所述方法还可包括发送包括第一密钥的散列映射更新请求消息，其中请求消息的接收使第一散列映射通过第一密钥和与索引列表的条目相关联的索引值被更新。所述方法还可包括用第二密钥和第一散列映射的标识符更新第二散列映射。
下文进一步详细描述本发明的这些和其它实施例。
附图说明
图1描绘根据至少一些实施例的实例分布式计算环境。
图2描绘能够实施分布式计算系统的管理器节点的至少一些实施例的实例计算机架构。
图3示出能够实施分布式计算系统的工作节点的至少一些实施例的实例计算机架构。
图4示出描绘数个算法效率的实例图。
图5示出可由根据至少一个实施例的分布式计算系统利用的第一实例数据结构。
图6示出可由根据至少一个实施例的分布式计算系统利用的第二实例数据结构。
图7示出可由根据至少一个实施例的分布式计算系统利用的第三实例数据结构。
图8示出流程图，所述流程图示出根据至少一个实施例的用于将数据集的部分分布在一组节点当中的实例过程。
图9示出流程图，所述流程图示出根据至少一个实施例的利用图5到7的数据结构进行搜索的实例过程。
具体实施方式
在以下描述中，将描述各种实施例。出于解释的目的，阐述特定配置和细节以便提供对实施例的透彻理解。然而，所属领域的技术人员还应清楚，可在无所述特定细节的情况下实践实施例。此外，可能省略或简化众所周知的特征以免使描述的实施例模糊不清。
在论述本发明的一些实施例的细节之前，对一些术语的描述可有助于理解各种实施例。
“分布式计算系统”可指以通信方式彼此耦合的电子装置的集合。在一些实施例中，较大数据集的子集可分布在分布式计算系统当中(例如在系统的节点内的存储器上)。电子装置的集合可用于执行各种功能(例如任务)。在一些实例中，电子装置的集合可包含一个或多个管理器节点、一个或多个工作节点和/或一个或多个数据库。
“管理器节点”可以是可用于管理分布式计算系统中的其它节点(例如工作节点)的电子装置。在一些实例中，管理器节点可负责将工作(例如任务)分派给分布式计算系统中的一个或多个其它节点(例如工作节点)。在一些实例中，管理器节点可维持映射(例如散列映射)，所述映射将密钥(例如账户标识符、社会保障号或另一合适的文字数字标识符)映射到值(例如另一散列映射或另一散列映射的位置)。例如，管理器节点可维持散列映射，所述散列映射利用文字数字标识符作为输入并输出另一散列映射的标识符(或在一些情况下，另一散列映射自身)。管理器节点可负责确定对应于密钥(例如账户标识符)的所识别的散列映射的所在之处(例如分布式计算系统中的特定节点)。管理器节点可将信息(例如请求消息)传输到分布式计算系统中的各个节点，且可在对应的任务完成时或在另一合适的时间从各个节点接收信息(例如响应消息)。
“工作节点”可以是可用于处理分布式计算系统中的数据(例如任务)的电子装置。在一些实例中，工作节点可从管理器节点接收信息(例如请求消息)。工作节点可负责执行各种操作以便执行功能(例如查找数据)。在处理请求时或在另一合适的时间，工作节点可向分布式计算系统中的另一节点(例如管理器节点)传输信息(例如响应消息)。在至少一些实例中，工作节点可包含其在处理期间可利用的一些量(例如，128千兆字节(GB)、1太字节(TB)等)的板载存储器(例如RAM)。
“交易处理数据”可包含与交易相关联的数据。此数据可指与密钥相关联的任何合适的数据。在一些实施例中，交易处理数据可以是与用户相关联的支付账户数据。在一些实施例中，交易处理数据可包含配送地址、开单地址或与消费者相关联的其它相关信息。在一些实例中，交易处理数据可包含一个或多个账户标识符。在一些实施例中，账户标识符可以是支付卡号(PAN)和/或主账号。PAN可以是14、16或18位的。交易处理数据还可包含与账户相关联的有效期，以及服务代码和/或验证值(例如，CVV、CVV2、dCVV和dCVV2值)。另外或替代地，交易处理数据可包含过去的购买信息、与网站使用相关的导航信息、与账户相关联的欺诈交易规则，或可能与可借以进行搜索的密钥相关联的任何合适的数据。此类数据可能或可能不会涉及消费者账户/交易。
“协议集”可以是指示允许和/或应当执行一个或多个动作的规则或配置设置的集合。在一些情况下，协议集可包含要执行那些动作所基于的条件。在一些实施例中，协议集可包含条件语句，例如“如果x_condition发生，则执行y_action”。在一些实施例中，协议集可包含策略，所述策略用于指定涉及检测到欺诈交易时应何时执行特定动作和/或应执行何种特定动作。在一些实例中，所述协议集可与其它协议集一起存储在协议集存储容器中。
“请求消息”是可包含请求数据(例如交易处理数据、欺诈交易协议集等)时所必要的任何合适的信息的电子消息。在一些实施例中，请求消息可被引导到分布式计算系统的管理器节点和/或分布式计算系统的节点之间(例如，管理器与工作器之间、工作器与工作器之间等)在一些实施例中，请求消息可包含要用以搜索所请求的数据的一个或多个密钥(例如账户标识符、卡号、社会保障号、文字数字标识符等)。
“响应消息”可包含提供与请求消息相关的数据所必要的任何合适的信息。例如，响应消息可包含请求的数据(例如交易处理数据、欺诈交易协议集等)。
“散列映射”可包含可用于实施关联阵列的数据结构，是可将密钥映射到值的数据结构。“密钥”可包含可与值相关联的任何合适的数据(例如，账户标识符、文字数字标识符、数据对象、社会保障号、名称等)。散列映射可利用散列函数将索引计算成密钥阵列，从所述阵列中可找到所要值(例如与特定密钥相关联的值)。在至少一个实例中，散列映射可在用于执行搜索时提供O(1)算法复杂度。
“算法复杂度”是指特定算法执行的快慢程度。例如，算法的平均情况运行时复杂度是由在大小为x的任何实例上取得的集的平均数定义的函数。如果不论输入大小都需要相同的时间量，则将算法称为以恒定时间运行。例如，访问阵列中的元素是以恒定时间运行的(另外标示为“O(1)”)，因为访问阵列的元素并不取决于阵列中存储多少元素。下文相对于图4进一步论述算法复杂度。
由O(x)表示的“大O记法”表示算法的性能或复杂度。具体地说，大O记法描述最坏情况情境，且可用于描述算法所需的执行时间或所用的空间(例如，存储器内或磁盘上)。换句话说，大O记法描述函数在变量参数趋向于特定值或无穷大时的限制行为。大O记法通常用于根据算法对输入大小改变的响应方式，例如算法的处理时间在问题大小变得极其大时的改变方式，来对算法进行分类。
“散列映射更新请求消息”可包含关于散列映射的创建和/或修改的信息。例如，散列映射更新请求消息可包含可存储在分布式计算环境中的工作节点上的散列映射中的密钥(例如，账户标识符)和值(例如，索引)。
“散列映射更新响应消息”可包含关于散列映射更新请求的成功性的指示。例如，散列映射更新响应消息可指示更新成功或是不成功。在一些实例中，如果更新不成功，则散列映射更新响应消息可包含关于更新为何不成功的指示(例如存储器已满、密钥已经存在等)。
“索引列表”可以是将密钥(例如，索引值)映射到值的数据结构。在至少一个实例中，索引列表可以是将索引值映射到交易处理数据的阵列。在至少一个实例中，索引列表可在用于执行搜索时提供O(1)算法复杂度。
“用户装置”可以是由用户操作的电子装置。用户装置的实例可包含移动电话、智能电话、个人数字助理(PDA)、笔记本电脑、台式计算机、服务器计算机、例如汽车的车辆、精简客户端装置、平板PC等。另外，用户装置可以是任何类型的可穿戴技术装置，例如手表、耳机、眼镜等。用户装置可包含能够处理用户输入的一个或多个处理器。用户装置还可包含用于接收用户输入的一个或多个输入传感器。用户装置可包括可由用户操作的任何电子装置，所述电子装置还可提供与网络的远程通信能力。远程通信能力的实例包含使用移动电话(无线)网络、无线数据网络(例如3G、4G或类似网络)、Wi-Fi、Wi-Max，或可提供对互联网或私用网络等网络的访问的任何其它通信介质。
“服务器计算机”可包含功能强大的计算机或计算机集群。例如，服务器计算机可以是大型主机、小型计算机集群或作为一个单元运作的一组服务器。在一个实例中，服务器计算机可以是耦合到网络服务器的数据库服务器。服务器计算机可耦合到数据库，且可包含用于服务来自一个或多个客户端计算机的请求的任何硬件、软件、其它逻辑或前述内容的组合。服务器计算机可包括一个或多个计算设备，且可使用各种计算结构、布置和编译中的任一种来服务来自一个或多个客户端计算机的请求。
“处理器”可指任何合适的一个或多个数据计算装置。处理器可包括一起工作以实现所要功能的一个或多个微处理器。处理器可包含CPU，所述CPU包括足以执行用于执行用户和/或系统生成的请求的程序组件的至少一个高速数据处理器。所述CPU可以是微处理器，例如AMD的速龙(Athlon)、钻龙(Duron)和/或皓龙(Opteron)；IBM和/或摩托罗拉(Motorola)的PowerPC；IBM和索尼(Sony)的Cell处理器；英特尔(Intel)的赛扬(Celeron)、安腾(Itanium)、奔腾(Pentium)、至强(Xeon)和/或XScale；和/或类似处理器。
“存储器”可以是可存储电子数据的任何合适的一个或多个装置。合适的存储器可包括非暂时性计算机可读介质，其存储可由处理器执行以实现所要方法的指令。存储器的实例可包括一个或多个存储器芯片、磁盘驱动器等等。此类存储器可使用任何合适的电、光和/或磁操作模式来操作。
现在将描述本发明的一些实施例的细节。
由于分布式计算系统被广泛用于管理大型数据集，因此执行高效搜索的能力是相当重要的。在当前系统中，主数据库可由分布式计算系统的每个节点访问。此类方式会带来挑战。例如，维持磁盘上的主数据库可能产生变化的搜索时间，因为数据集较大且难以搜索。另外，归因于容器的存储约束条件，数据集可能过大而无法存储在容器(例如散列映射、索引列表)中。需要的是一种更高效的搜索解决方案。虽然对于金融交易处理尤其有用，但本发明广泛适用于使用可与密钥相关联的大型数据集的应用。例如，虽然本文所描述的实例将账号用作密钥，但可使用其它值，例如社会保障号、名称、地址、文字数字标识符或任何合适的密钥值。
本发明的实施例涉及可用于管理分布式计算系统的一组节点上的数个数据结构的方法和系统。本文所描述的数据结构的利用使分布式计算系统能够将数据集分布在一组节点当中，以便在执行数据搜索时提供恒定O(1)算法效率。在一些实施例中，系统可接收数据集标识信息，其指定要分布的数据集和/或数据集的位置。系统可将数据集分成更小部分以存储在一组节点上的自定义数据结构中。在一些实例中，系统可确定一组节点(例如，分布式计算系统的某一部分节点)中的每个节点上的可用存储空间，且根据每个节点上的可用存储空间生成本文所描述的数据结构。在至少一个实施例中，系统可使提供索引列表(例如阵列)的数据结构被创建，所述索引列表将索引值映射到交易处理数据(例如所请求的数据)。另外，系统可使得在一组节点(例如，工作节点)上维持一组散列映射，所述一组散列映射中的个别散列映射提供密钥(例如，账户标识符)到索引值(例如索引列表中的索引值)的映射。系统可使所述一组节点中的每个节点上的处理器维持密钥(例如，账户标识符)到索引值(例如0、1、2、3、……等)的一个或多个散列映射，所述索引值对应于与每个密钥相关联的特定交易处理数据。系统还可使相同或不同组节点(例如一个或多个管理器节点)上的处理器维持散列映射，所述散列映射将密钥(例如账户标识符、文字数字值等)映射到另一散列映射(例如将密钥映射到索引值的所述一组散列映射中的散列映射)。
在至少一个实施例中，系统(例如，分布式计算系统)可接收交易处理数据的请求消息，所述交易处理数据与密钥(例如账户标识符、文字数字值等)相关联。请求消息可由分布式系统的管理器节点接收。管理器节点可将请求消息转发到分布式系统的工作节点。工作节点可利用散列函数对密钥进行散列化以确定散列化密钥。散列化密钥可结合第一散列映射用以返回第二散列映射的位置或对应于密钥的散列映射标识符。工作节点可利用密钥(例如，账户标识符)和相同或不同散列函数生成散列化密钥。散列化密钥可由工作节点用以执行第二散列映射的查找以返回索引值。接着，工作节点可利用返回的索引值，以便执行索引列表中的查找。索引列表中的查找可返回与索引值相关联的交易处理数据。可将返回的交易处理数据提供到管理器节点，且最终提供到发起请求消息的用户装置。
在至少一个实施例中，系统(例如，分布式计算系统)可接收交易处理数据的请求消息，所述交易处理数据与密钥(例如账户标识符、文字数字值等)相关联。请求消息可由分布式系统的管理器节点接收。管理器节点可利用散列函数对密钥进行散列化以确定散列化密钥。散列化密钥可用于返回第二散列映射的位置或对应于密钥的散列映射标识符。管理器节点可利用返回的位置或标识符将请求消息提供到分布式计算系统的特定工作节点。在接收到请求消息时或在另一合适的时间，工作节点可利用密钥(例如，账户标识符)和相同或不同散列函数生成散列化密钥。散列化密钥可由工作节点用以执行(存储在工作节点的板载存储器中的)第二散列映射的查找以返回索引值。接着，工作节点可利用返回的索引值，以便执行索引列表(板载或在集中位置中存储的索引列表)中的查找。索引列表中的查找可返回与索引值相关联的交易处理数据。可将返回的交易处理数据提供到管理器节点，且最终提供到发起请求消息的用户装置。
图1描绘根据至少一些实施例的实例分布式计算环境100。分布式计算环境100可包括由用户104操作的一个或多个用户装置102(1)到102(N)(以下称作用户装置102)。用户装置102还可通过网络106与分布式计算系统108通信。用户装置102可由用户104中的一个或多个用户操作，以通过网络106访问分布式计算系统108。用户装置102可以是能够与网络106通信的任何合适的装置。例如，用户装置102可以是任何合适的计算装置，例如但不限于移动电话、智能电话、个人数字助理(PDA)、笔记本电脑、精简客户端装置、平板PC、台式计算机、机顶盒或其它计算装置。
分布式计算系统108可具有任何合适的特性。分布式计算系统108可包含一个或多个管理器节点(例如管理器节点110)、一个或多个工作节点(例如工作节点112)以及一个或多个集中式数据存储区(例如集中式数据存储区122)，以用于执行本文所描述的功能。管理器节点110和工作节点112彼此可通信耦合。结合数据处理，管理器节点110可包含管理模块114，所述管理模块被配置成执行包含以下各项的功能：接收/处理/传输请求消息；接收/处理/传输响应消息；接收/处理/传输散列映射更新请求/响应消息；维持一个或多个数据结构；以及使一个或多个其它数据结构存储在分布式数据存储区120和/或集中式数据存储区122中。管理器节点110还可包含分布式数据存储区116，其被配置成存储一个或多个数据结构。例如，在一些情况下，分布式数据存储区116可被配置成存储将密钥(例如账户标识符、文字数字标识符等)映射到散列映射(例如存储在工作节点112的分布式数据存储区120上的散列映射，下文进一步论述)的散列映射。在至少一个实例中，分布式数据存储区116可以是管理器节点110的随机存取存储器(RAM)。
结合数据处理，工作节点112可包含执行模块118。执行模块118可被配置成执行包含以下各项的功能：接收和处理请求消息；传输响应消息；接收散列映射更新请求消息；传输散列映射更新响应消息；以及维持与较大数据集相关联的一个或多个数据结构。工作节点112还可包含分布式数据存储区120。分布式数据存储区120可被配置成存储与较大数据集和/或任何合适的信息相关联的一个或多个数据结构。例如，分布式数据存储区120可被配置成存储将密钥(例如，账户标识符)映射到其它散列映射的位置/标识符的一个或多个散列映射、将密钥(例如，账户标识符)映射到索引值的一个或多个散列映射以及一个或多个索引列表(例如，将索引值映射到交易处理数据的索引列表)。在至少一个实例中，分布式数据存储区120可以是工作节点112的随机存取存储器(RAM)。
分布式计算系统108还可包含集中式数据存储区(例如，集中式数据存储区122)。集中式数据存储区可被配置成存储与较大数据集相关联的一个或多个数据结构。例如，集中式数据存储区122可被配置成存储将密钥(例如，以及索引值)映射到值(例如，交易处理数据、欺诈交易协议集或任何合适的数据)的索引列表。在至少一个实施例中，集中式数据存储区122可以由管理器节点110和/或工作节点112访问。
图1中的计算机、网络和装置之间的消息可使用安全通信协议来传输，所述安全通信协议例如但不限于：文件传输协议(FTP)；超文本传输协议(HTTP)；安全超文本传输协议(HTTPS)；安全套接层(SSL)；ISO(例如，ISO 8583)和/或其类似者。
图1中的每个实体可通过任何合适的通信信道或通信网络(例如，网络106)通信。合适的通信网络可以是下列中的任一个和/或其组合：直接互连；互联网；局域网(LAN)；城域网(MAN)；作为互联网上节点的运行任务(OMNI)；安全自定义连接；广域网(WAN)；无线网络(例如，采用例如但不限于无线应用协议(WAP)、I-模式和/或其类似者的协议)；和/或其类似者。
图2描绘能够实施图1的分布式计算系统108的管理器节点(例如，图1的管理器节点110)的至少一些实施例的实例计算机架构200。管理器节点110可个别地包含处理器和耦合到处理器的计算机可读介质，所述计算机可读介质包括可由处理器执行以执行本文中描述的功能的代码。应了解，相对于图2的模块描述的任何功能可进行组合以由单个模块执行，或可由管理器节点110外部的模块执行。图2示出以通信方式耦合到集中式数据存储区122的管理器节点110。集中式数据存储区122可如图2中所描绘进行配置，或集中式数据存储区122可完全或部分地被提供为管理器节点110的部分。分布式数据存储区116、集中式数据存储区122(以及本文所描述的任何其它数据库)可以是常规的、容错的、关系的、可扩展的安全数据库，例如OracleTM或SybaseTM。可使用例如阵列、散列映射、(链接)列表、结构化文本文件(例如XML)、表格和/或类似的各种数据结构来实施分布式数据存储区116和/或集中式数据存储区122。此类数据结构可存储在存储器中和/或结构化的文件中。
管理器节点110可包括处理器204，所述处理器可耦合到系统存储器206和外部通信接口208。计算机可读介质210也可操作地耦合到处理器204。
计算机可读介质210可包括数个软件模块，所述软件模块包含分布模块212和搜索处理模块214。可利用更多或更少模块来执行本文所描述的功能。
分布模块212可包括在被执行时使处理器204确定数据集的分布的代码。例如，分布模块212可接收分布数据集的请求。所述请求可包含数据集的标识符。响应于请求，分布模块212可被配置成使处理器204访问所识别的数据集(例如，存储在集中式数据存储区122中)且生成数据结构以存储数据集的一部分。例如，分布模块212可使处理器204执行代码以生成索引列表(例如下文论述的数据结构700)。索引列表可将索引值(例如，0、1、2、3等)映射到值(例如，交易处理数据、欺诈交易协议集等)。例如，分布模块212可使处理器204按交易处理数据创建/接收的次序生成交易处理数据的索引列表。分布模块212可使索引列表存储在存储器中(例如一个或多个工作节点上、集中式数据存储区122上，等)。在至少一个实例中，分布模块212可使多个索引列表被创建并存储在一个或多个工作节点上的存储器中、集中式数据存储区122上或任何合适的存储位置。这多个索引列表可对应于数据的交易处理数据的子部分。在一些实例中，这多个索引列表中的一个列表可与一个或多个散列映射共置于工作节点上，所述一个或多个散列映射涉及与索引列表中所含有的相同的交易处理数据。
在至少一个实例中，分布模块212可被配置成使处理器204确定对应于每个索引值的账户标识符。分布模块212可被配置成使一个或多个散列映射(例如下文论述的数据结构600)被创建，所述一个或多个散列映射个别地将账户标识符的一部分映射到对应的索引值。分布模块212可被配置成使另一散列映射被创建，所述另一散列映射将账户标识符映射到将密钥(账户标识符)映射到对应的索引值的另一散列映射。因此，分布模块212可被配置成使处理器204创建将密钥映射到其它散列映射的第一散列映射、个别地将密钥的子集映射到索引值的多个其它散列映射以及将索引值映射到对应于密钥的交易处理数据的索引列表。在至少一个实施例中，分布模块212可被配置成使一个或多个散列映射和一个或多个索引列表被存储(例如在管理器节点上、在工作节点上或在集中式数据存储区上)。
在非限制性实例中，分布模块212可被配置成使处理器204确定对应于每个索引值的账户标识符。分布模块212可被配置成使处理器204确定分布式计算系统108的至少一个节点(例如，图1的工作节点112)上的可用存储器。分布模块212可被配置成使处理器204向工作节点112传输散列映射更新请求消息，以便使散列映射中的条目在工作节点112上创建/更新。散列映射更新请求消息可包含密钥(例如，账户标识符)和值(例如，索引值)。创建的/更新的散列映射可存储在工作节点112上(例如在工作节点112的RAM中)。在至少一个实例中，分布模块212可被配置成使处理器204从工作节点112接收散列映射更新响应消息。散列映射更新响应消息可指示条目是否成功创建/更新。在至少一个实例中，进一步处理可取决于散列映射更新响应消息的内容(例如，成功/失败指示、原因标识符等)。例如，如果散列映射更新响应消息指示条目未在工作节点112的散列映射中创建/更新，则分布模块212可被配置成使处理器204停止处理数据集的分布，或在一些情况下，停止处理所述条目的分布。根据至少一个实施例，分布模块212可被配置成使处理器204向用户装置(例如图1的用户装置102)提供指示和/或原因。
在一些情况下，分布模块212可被配置成使处理器204向分布式计算系统中的另一工作节点传输散列映射更新请求消息，而在其它实例中，分布模块212可被配置成使处理器204停止处理失败的条目。
在至少一个实例中，分布模块212可被配置成使处理器204在另一散列映射上创建和/或更新条目。此散列映射可将密钥(例如，账户标识符)映射到值(例如，工作节点112上的第一散列映射标识符、第一散列映射的位置等)。分布模块212可被配置成使处理器204将创建的/更新的散列映射存储在本地存储装置(例如分布式数据存储区116)中。如图2中所描绘，可将分布式数据存储区116包含为管理器节点110的部分(例如管理器节点110的RAM)。在至少一个实例中，分布模块212可被配置成使处理器204针对数据集的每个条目或数据集的至少某一部分执行上述功能，以便将关于数据集/部分的信息分布在一个或多个工作节点当中。存储在分布式数据存储区116上的散列映射可充当在分布开始/完成后用于定位特定数据的工具。
搜索处理模块214可包括在被执行时使处理器204接收并处理(例如来自图1的用户装置102的)请求消息的代码。在至少一个实施例中，搜索处理模块214可被配置成使处理器204向图1的分布式计算系统108的一个或多个工作节点(例如工作节点112)传输请求消息。搜索处理模块214还可被配置成使处理器204从工作节点(例如工作节点112)接收并处理响应消息，和/或将响应消息传输到用户装置102。搜索处理模块214还可被配置成使处理器204利用内部存储的数据结构(例如所存储的将账户标识符等密钥映射到其它散列映射/其它散列映射的位置的散列映射)执行查找。搜索处理模块214还可被配置成利用索引值执行集中式数据存储区122中的查找。在至少一个实例中，集中式数据存储区122可被配置成存储数据结构(例如，索引列表)，所述数据结构将密钥(例如，索引值)与返回值(例如，交易处理数据)相关联。
图3描绘能够实施图1的分布式计算系统108的工作节点(例如图1的工作节点112)的至少一些实施例的实例计算机架构300。工作节点112可个别地包含处理器304和耦合到处理器304的计算机可读介质310，计算机可读介质310包括可由处理器执行以执行本文所描述的功能的代码。应了解，相对于图3的模块描述的任何功能可进行组合以由单个模块执行，或可由工作节点112外部的模块执行。图3示出以通信方式耦合到集中式数据存储区122的工作节点112。集中式数据存储区122可如图3中所描绘进行配置，或集中式数据存储区122可完全或部分地被提供为工作节点112的部分。可使用例如阵列、散列映射、(链接)列表、结构化文本文件(例如XML)、表格和/或类似的各种数据结构来实施分布式数据存储区120和/或集中式数据存储区122。此类数据结构可存储在存储器中和/或结构化的文件中。
工作节点112可包括处理器304，所述处理器可耦合到系统存储器306和外部通信接口308。计算机可读介质310也可操作地耦合到处理器304。
计算机可读介质310可包括数个软件模块，所述软件模块包含数据结构管理模块312和搜索处理模块314。可利用更多或更少模块来执行本文所描述的功能。
在至少一个实例中，数据结构管理模块312可包括在被执行时使处理器304接收散列映射和/或索引列表的代码。数据结构管理模块312可被配置成使处理器304将所接收的散列映射/索引列表存储在分布式数据存储区120上。
在一些实施例中，数据结构管理模块312可包括在被执行时使处理器304接收(例如来自图1和2的管理器节点110的)散列映射更新请求消息的代码。散列映射更新请求消息可包含将由工作节点112维持在散列映射内的密钥(例如，账户标识符)和值(例如，索引值)，所述散列映射将被存储或已经存储在分布式数据存储区120上。在接收到散列映射更新请求消息时，数据结构管理模块312可使处理器304创建和/或更新存储在分布式数据存储区120中的散列映射。在至少一个实例中，数据结构管理模块312还可被配置成使处理器304向管理器节点110发送散列映射更新响应消息，其指示散列映射的创建/更新成功或是不成功。散列映射更新响应消息可包含与创建/更新不成功的原因(例如存储器已满、密钥已经存在等)相关联的原因代码。
搜索处理模块314可包括在被执行时使处理器304接收并处理(例如来自图1和2的管理器节点110的)请求消息的代码。在至少一个实施例中，搜索处理模块314可被配置成使处理器304从请求消息中提取密钥(例如，账户标识符)。在一些实例中，搜索处理模块314可使处理器304利用散列函数对提取的密钥进行散列化以产生散列化密钥。搜索处理模块314可使处理器304访问分布式数据存储区120，以便访问存储的散列映射(例如，将密钥映射到其它散列映射的散列映射、将密钥映射到索引值的散列映射)。
在至少一个实施例中，搜索处理模块314可使处理器304利用散列化密钥作为散列映射(将密钥映射到其它散列映射的散列映射，例如下文论述的图5的数据结构500)的输入，以便获得将密钥映射到索引值的另一存储的散列映射。
在至少一个实施例中，搜索处理模块314可使处理器304利用散列化密钥作为存储的散列映射的输入，以便获得与密钥相关联的索引值。搜索处理模块314可使处理器304访问集中式数据存储区122，以便访问存储的索引列表(例如，将索引值映射到交易处理数据的阵列/索引列表)。搜索处理模块314可使处理器304利用索引值作为索引列表的输入，以便获得与索引值(且因此，原始密钥)相关联的交易处理数据。在至少一个实例中，搜索处理模块314还可被配置成使处理器304在响应消息中将所获得的交易处理数据传输到图1和2的管理器节点110。
图4示出描绘数个算法效率的实例图400。如上文所论述，算法的算法复杂度是指算法的平均或最差时间运行时复杂度。算法的算法复杂度指定大小为x的任何实例所花的平均步数。即，算法的平均运行时复杂度是由应用于大小为x的输入并随时间平均化的一系列操作定义的函数。
算法复杂度通常以“大O记法”表示。“O(log n)”是结合大写“O”表示的算法复杂度(log n)的实例。大O记法用于根据算法对输入大小改变的响应方式，例如算法的处理时间在问题大小变得极其大时的改变方式，来对算法进行分类。因此，大O记法根据函数增长大小来表征函数，使得可使用相同的O记法来表示具有相同增长率的不同算法。举例来说，“O(log n)”指示算法的限制行为具有(log n)的阶数。
图400旨在示出若干不同算法复杂度。例如，O(n！)、O(2n)、O(n2)、O(n log n)、O(n)和O(log n)。提供的复杂度仅是可用于对算法效率进行分类/特征化的许多不同复杂度中的几个。未描绘的O(1)也可用于将算法分类为具有恒定时间。具有恒定时间的算法并不基于输入大小而变化。例如，可在恒定时间中执行确定整数是偶数还是奇数。同样，可在恒定时间中执行访问索引列表中的单个元素。
提供了所描绘的复杂度的简要概述。O(log n)也称为“对数时间”，对数通常以2为底数，但不论对数的底数如何，都使用所述记法。以对数时间操作的算法的实例是对分搜索。O(log n)算法被视为高效的，因为每实例所需完成的操作随着每个实例减少。
O(n)也称为“线性时间”。以线性时间运行的算法意指对于足够大的输入大小，运行时间随着输入的大小线性地增大。以线性时间操作的算法的实例是在未排序列表中查找最小或最大项的算法。因此，如图400所描绘，O(log n)处于比O(n)更高效的阶数，因为随着输入变大，完成具有O(log n)复杂度的算法实例所需的操作远低于具有O(n)复杂度的算法所需的操作。
O(n log n)也称为“线性对数时间(linearithmic time)”。以线性对数时间操作的算法的实例是最可能快的比较排序。O(n2)也称为“二次时间”，且以二次时间操作的算法的实例包含冒泡排序(bubble sort)和插入排序。O(2n)也称为“指数时间”，且以指数时间操作的算法的实例是穷举搜索(brute force search)。O(n！)也称为“阶乘时间”，且以阶乘时间操作的算法的实例包含用于解决例如“给定城市列表和每对城市之间的距离，则只访问每个城市一次并返回到原来城市的最短可能路线是什么？”的问题的算法。因此，图4中所描绘的算法复杂度从最低效到最高效为：O(n！)、O(2n)、O(n2)、O(n log n)、O(n)和O(logn)。
图5示出可由根据至少一个实施例的分布式计算系统(例如图1的分布式计算系统108)利用的第一实例数据结构500。在图5中所描绘的实例中，数据结构500是散列映射。所述数据结构可包含数个密钥(例如，密钥502)。每个密钥可与密钥/值对的链接列表相关联。例如，密钥“0”可与包含密钥/值对504的链接列表相关联。与密钥相关联的链接列表中的每个元素可指向链接列表中的下一个元素，除非所述元素是链接列表中的最后一个，在此情况下，指针元素可为空/未赋值。例如，参看图5的链接列表506。
数据结构500可结合散列函数用以将数个密钥/值对分布在数据结构500中的存储桶502上。在至少一个实例中，所利用的散列函数应维持“平衡的散列映射”，因为密钥/值对是均匀分布的(例如每个存储桶502有相同/类似数目的密钥/值对)。因此，可针对很平衡的散列映射以恒定时间(O(1))执行平均时间复杂度，而可能以线性时间(O(n))执行包含不均匀平衡的散列映射的较差情况情境。
举例来说，散列函数可用于对密钥(例如账户标识符，例如“98641222”)进行散列化。散列化密钥可等于“2”，其可对应于存储桶“2”。因此，密钥(“98641222”)和其对应值(例如“散列映射0”，另一散列映射的标识符)可被指派到存储桶“2”，如图5中所描绘。条目508可使其指针元素设置成“空”，前提是所述条目是指派到存储桶“2”的唯一条目。
在至少一个实例中，表510中的每个密钥可通过散列函数散列化以确定数据结构500内合适的存储桶。因此，可根据确定的存储桶将表510中的每个密钥/值对的条目插入到数据结构500中。在至少一个实例中，图1和2的管理器节点110(或管理器节点110的组件，例如，分布模块212、搜索处理模块214等)可执行操作以创建、管理、存储和/或访问数据结构500。在其它实例中，图1和3的工作节点112(或工作节点112的组件)可执行操作以管理、存储和/或访问数据结构500。因此，数据结构500可存储在图1和2的分布式数据存储区116中、图1和3的分布式数据存储区120中和/或任何合适的存储位置中。
图6示出可由根据至少一个实施例的分布式计算系统(例如图1的分布式计算系统108)利用的第二实例数据结构600。在图6中所描绘的实例中，数据结构600是散列映射。数据结构可包含密钥602，每个密钥具有标识符(例如，0、1、2、3或合适的文字数字标识符)。每个密钥可与密钥/值对的链接列表相关联。例如，密钥“0”可与包含密钥/值对604的链接列表相关联。如上文所指示，与密钥相关联的链接列表中的每个元素可指向链接列表中的下一个元素，除非所述元素是链接列表中的最后一个，在此情况下，指针元素可为空/未赋值。
数据结构600可结合散列函数用以将数个密钥/值对分布在数据结构600中的密钥602上。如前所述，在至少一个实例中，所利用的散列函数应维持“平衡的散列映射”，因为密钥/值对是均匀分布的(例如每个密钥602有相同/类似数目的密钥/值对)。
举例来说，散列函数可用于对密钥(例如账户标识符，例如“98641222”)进行散列化。在一些实例中，结合数据结构600利用的密钥可以是与结合图5的数据结构500利用的密钥相同的或不同的密钥。散列化密钥可等于“5”，其可对应于数据结构600的密钥“5”。因此，密钥(“98641222”)和其对应值(例如“6”、索引值)可被指派到数据结构600的密钥“5”，如图6中所描绘。条目608可使其指针元素设置成“空”，前提是所述条目当前是指派到密钥“5”的唯一条目。
在至少一个实例中，(表610中所描绘的)数据的每个密钥可通过散列函数散列化以确定数据结构600内的对应密钥。因此，根据从密钥(例如账户标识符)确定的散列化密钥(例如密钥602中的一个)，可将表610中每个密钥/值对的条目插入到数据结构600中。在至少一个实例中，图1和3的工作节点112(或工作节点112的组件，例如，数据结构管理模块312、搜索处理模块314等)可执行操作以创建、管理、存储和/或访问数据结构600。
图7示出可由根据至少一个实施例的分布式计算系统利用的第三实例数据结构700。在图7中所描绘的实例中，数据结构700是阵列，但其可为任何合适的索引列表。数据结构700可包含以密钥(例如列704的密钥)作索引的数据集(例如交易处理数据，例如包含在列702中的各种账户的账户细节)。
继续看图6的实例，条目706可对应于与账户标识符(“98641222”)相关联的数据。如上文所描述，账户标识符“98641222”与数据结构600中的索引值“6”相关联。因此，交易处理数据(例如账户标识符98641222的账户细节)可与数据结构700中的索引值“6”相关联。数据结构700可例如存储在图1到3的集中式数据存储区122或其它合适的位置中。数据结构700可包含预定义数目的条目，或数据结构700可随着系统接收到更多交易处理数据而动态地增长。
作为非限制性实例，当新账户添加到分布式计算系统时，新条目可添加到对应于每个新账户的交易处理数据(例如账户细节)的数据结构700。当新账户的交易处理数据在数据结构700中被编索引时，索引值可作为密钥/值对中的值存储在数据结构600中(所述密钥是新账户的账户标识符)。类似地，数据结构600的位置和/或标识可作为密钥/值对中的值存储在数据结构500中(所述密钥是新账户的账户标识符)。
在至少一个实施例中，图1和2的管理器节点110可负责维持数据结构700，但可利用其它合适的装置。在至少一个实例中，数据结构700可以是负责维持交易处理数据与索引之间的关联的许多类似数据结构中的一个。数据结构700和/或其它类似数据结构可存储在图1到3的集中式数据存储区122中，或替代地，数据结构700可存储在管理器节点的分布式数据存储区116和/或工作节点的分布式数据存储区120中。
图8示出流程图，所述流程图示出根据至少一个实施例的用于将数据集的部分分布在多个节点当中的实例过程800。过程800可在框802处开始，其中可(例如由图1和2的管理器节点110)接收与数据集相关联的标识符。标识符可以是文字数字标签、地址或用于识别数据集的合适的数据。在框804处，可生成索引列表。索引列表可与数据集的数据子集对应。举例来说，子集可包括数据集的交易处理数据。考虑原始数据集具有与交易处理数据(例如地址信息、用户名/口令、账户持有者信息、过去交易信息等)相关联的账户标识符。可(例如由管理器节点110、由集中式系统的处理器等等)提取交易处理数据以及可生成索引列表。因此，可为个别地对应于账户标识符的交易处理数据的每个条目指派索引值。
在框806处，可(例如由图1的管理器节点110在分布式数据存储区120和/或集中式数据存储区122中)存储索引列表。索引列表可供管理器节点110(和分布式计算系统108的任何其它管理器节点)和工作节点112(和分布式计算系统的任何其它工作节点)访问。
在决策点808处，可确定索引列表的条目(例如第一条目)。条目可与特定账户标识符相关联。在框810处，可确定与索引列表的条目相关联的第一密钥(例如账户标识符)。
在至少一个实施例中，在框812处，可用第一密钥和与索引列表的条目相关联的索引值更新第一散列映射。在替代实施例中，在框812处，可(例如由管理器节点110)发送散列映射更新请求消息。散列映射更新请求消息可包含第一密钥。在其它实例中，散列映射更新请求消息可包含整个散列映射。在一些实例中，散列映射更新请求消息的接收(例如由工作节点112)可使第一散列映射通过第一密钥和与索引列表的条目相关联的索引值被更新和/或创建。在至少一个实例中，管理器节点110可确定一个或多个工作节点(例如工作节点112)的存储器占用率。例如，如果工作节点112具有可用于存储包括第一密钥和索引值的密钥/值对的存储器，则管理器节点110可将工作节点112选择为散列映射更新请求消息的目的地。如果工作节点112不具有可用存储器，则管理器节点110可选择分布式计算系统108中具有可用存储器的其它工作节点并将散列映射更新请求消息引导到具有可用存储器的工作节点。通过此类过程，管理器节点110可确保工作节点的存储器约束条件(工作节点之间约束条件可不同)是第一密钥/索引值对最终得以存储的考虑因素。
在框814处，可用第二密钥和第一散列映射的标识符更新第二散列映射。在至少一个实施例中，第二密钥可与第一密钥相同或不同。在决策点816处，可确定索引列表中是否存在其它未处理条目。如果不存在未处理条目，则方法可在框818处结束。如果存在另外的未处理条目，则过程可返回到决策点808。过程可重复框808到816，直到索引列表中不存在未处理条目，此时过程可在框818处结束。
在完成过程800时，可提供第一散列映射，所述第一散列映射将每个密钥(例如账户标识符)映射到对应的第二散列映射，所述第二散列映射将密钥映射到索引值。第一散列映射(密钥到散列映射/散列映射标识符)可存储在分布式数据存储区116和/或分布式数据存储区120中，而第二散列映射(密钥到索引值)可存储在工作节点112上(例如分布式数据存储区120中)。根据每个工作节点的存储器约束条件，可将其它对应的散列映射(将密钥映射到索引值的散列映射)存储在分布式计算系统的各种其它工作节点上。在一些实施例中，分布式数据存储区120可被配置成存储数据结构500到800的任何合适的组合。在至少一个实例中，本文所论述的每个数据结构(包含数据结构500、600和/或700)的副本可存储在分布式计算系统中的一个或多个工作节点(例如每个工作节点)上。索引列表可存储在任何合适位置(例如管理器节点110的数据存储区中、工作节点112的数据存储区中、每个工作节点112的数据存储区中、集中式数据存储区122中，等等)。
图9示出流程图，所述流程图示出根据至少一个实施例的利用图5到7的数据结构进行搜索的实例过程900。过程900可在框902处开始，其中可(例如由图1和2的管理器节点110)接收第一密钥。在至少一个实例中，第一密钥包括与账户持有者相关联的账户标识符。第一密钥可例如由管理器节点110通过请求消息接收到。
在框904处，可从多个散列映射当中确定与第一密钥相关联的散列映射。多个散列映射中的每个散列映射可将较大数据集的子集密钥映射到特定索引值。多个散列映射中的每个散列映射可被配置成加载到电子装置(例如工作节点112)的板载存储器(例如RAM)上。作为非限制性实例，在接收到第一密钥时，管理器节点110可对第一密钥进行散列化并利用散列化密钥和存储的散列映射(例如将密钥映射到散列映射标识符/位置的散列映射)来确定与密钥相关联的散列映射。在另一实例中，工作节点112可执行此类功能(例如接收密钥、对密钥进行散列化、使用散列化密钥确定存储的散列映射)。在任一实例中，所确定的散列映射可位于特定工作节点(例如工作节点112)上的存储器中。
在框906处，可利用所确定的散列映射确定与第二密钥(例如还有账户标识符)相关联的索引值。例如，可对第二密钥进行散列化，且将散列化密钥输入到所确定的散列映射(将密钥映射到索引值的散列映射)中。此类功能可由工作节点112执行。因此，可返回与第二密钥相关联的索引值。
在框908处，可使用所确定的索引值确定与第一密钥相关联的交易处理数据。例如，工作节点112可利用对应于第一密钥的索引值(利用存储在工作节点112上的散列映射而确定，所述散列映射将账户标识符映射到索引值)来执行索引列表中的查找。索引列表可存储在工作节点112可访问的位置中(例如集中式数据存储区122中、分布式数据存储区120中或任何合适的存储位置)。如上文所论述，索引列表可将索引号映射到与账户相关联的交易处理数据。因此，通过输入索引值，可返回对应于第一密钥的交易处理数据。
在框910处，可提供所确定的交易处理数据。例如，工作节点112可将交易处理数据返回到管理器节点110，所述管理器节点继而可将交易处理数据提供到发起请求消息的电子装置。
技术优势
与当前分布式计算系统中当前所需的操作相比，本发明的实施例可提供更高效地进行数据搜索的能力。具体地说，上文所论述的每个散列映射都能够加载到存储装置(例如管理器节点、工作节点等)的板载存储器(例如RAM)中。在一些实例中，生成的每个数据结构可加载到装置(例如工作节点)的板载存储器中。因此，在一些实例中，可在单个装置上以恒定算法复杂度(例如O(1))来进行搜索。另外，在一些实例中，比分布式计算系统中的单个节点的存储容量(例如64GB、128GB等)更大(例如2TB)的数据集可使其数据的部分被分布到自定义数据结构(例如索引列表和多个散列映射)中。每个数据结构提供恒定算法复杂度O(1)。因此，使用这些自定义数据结构进行的数据搜索能使搜索时间恒定，而不是像先前系统那样具有变化的搜索时间。另外，可在更短的时间内执行搜索，因为管理器节点和工作节点所利用的存储器是RAM，其本质上比存储在磁盘(例如硬盘驱动器)上的数据搜索得更快。
实例计算机系统
本文所描述的各种参与者和元件可操作一个或多个计算机设备以促进本文所描述的功能。上文描述的图1中的任何元件，包含任何服务器或数据库，可使用任何合适数目的子系统来促进文中描述的功能。
以上图中示出的此类子系统或组件的实例可通过系统总线互连。可包含额外的子系统，例如打印机、键盘、固定磁盘(或包括计算机可读介质的其它存储器)、耦合到显示适配器的监视器等等。外围装置和耦合到输入/输出(I/O)控制器(其可为处理器或任何合适的控制器)的I/O装置可通过所属领域中已知的例如串行端口等任何数目的构件连接到计算机系统。例如，串行端口或外部接口可用于将计算机设备连接到例如互联网的广域网、鼠标输入装置或扫描仪。通过系统总线的互连允许中央处理器与每个子系统通信，且控制来自系统存储器或固定磁盘的指令的执行以及子系统之间的信息交换。系统存储器和/或固定磁盘可体现计算机可读介质。
本申请中描述的任何软件组件或功能可使用任何合适的计算机语言实施为由处理器执行的软件代码，所述计算机语言例如使用常规的或面向对象的技术等的Java、C++或Perl。软件代码可作为一系列指令或命令存储在计算机可读介质上，所述计算机可读介质例如随机存取存储器(RAM)、只读存储器(ROM)、硬盘驱动器或软盘等磁性介质或CD-ROM等光学介质。任何此类计算机可读介质可驻存在单个计算设备上或内部，且可存在于系统或网络内的不同计算设备上或内部。
以上描述是说明性的而非限制性的。本发明的许多变化在所属领域的技术人员查阅本公开时可变得显而易见。因此，本发明的范围可以不参考以上描述来确定，而是可参考待决的权利要求以及其完整范围或等同物来确定。
在不脱离本发明的范围的情况下，任何实施例的一个或多个特征可与任何其它实施例的一个或多个特征组合。
除非明确指示有相反的意思，否则“一”或“所述”的叙述旨在表示“一个或多个”。
上文所提及的所有专利、专利申请、公开案和描述都出于所有目的以其全文引用的方式并入本文中。并非承认它们是现有技术。

Claims (9)

1.一种计算机实施的方法，包括：
由分布式计算系统的多个电子装置中的管理器电子装置，从用户操作的用户装置接收对交易处理数据的请求消息，所述请求消息包括多个密钥中的第一密钥，其中所述第一密钥与所述交易处理数据相关联，并且是与所述用户的账户标识符相对应的字母数字标识符；
响应于接收到所述请求消息，由所述管理器电子装置对所述第一密钥进行散列化以获得第一散列化密钥；
由所述管理器电子装置通过将所述第一散列化密钥输入第二散列映射并且获得第一散列映射的标识符，来将各自工作电子装置中的第一工作电子装置识别为多个散列映射中与所述第一密钥相关联的所述第一散列映射的存储位置，所述第一散列映射的所述标识符与所述第一散列化密钥和所述第一密钥相关联地存储在所述第二散列映射中，其中所述多个散列映射被存储在所述多个工作电子装置中的所述各自工作电子装置上，其中所述各自工作电子装置中的每一个存储所述多个散列映射中的一部分，所述一部分对应于所述多个密钥中的对应密钥子集，其中所述多个散列映射中各个散列映射的每一个分别提供所述对应密钥子集中包括的密钥至索引值的映射，其中所述各自工作电子装置中的每一个存储对应的索引列表，在所述对应的索引列表，所述索引值被映射到所述对应密钥子集的交易处理数据的各自段，并且其中与所述第一密钥相关联的所述第一散列映射是被加载到所述第一工作电子装置的板载存储器中的所述多个散列映射中的所述一部分；
由所述管理器电子装置，将包括所述第一密钥的所述请求消息发送给所述第一工作电子装置；
响应于所述请求消息，由所述第一工作电子装置对所述第一密钥进行散列化以产生第二散列化密钥；
由所述第一工作电子装置通过将所述第二散列化密钥输入所述第一散列映射并且从所述第一散列映射获得对应于所述第二散列化密钥的所述索引值，来获得对应于所述第一散列映射中的所述第一密钥的索引值，其中所述索引值与所述第二散列化密钥和所述第一密钥相关联地存储在所述第一散列映射中；
由所述第一工作电子装置通过将从所述第一散列映射获取的所述索引值输入第一索引列表中以从所述第一散列映射获得与对应于来自第一索引列表的所述索引值的所述第一密钥相关联的所述交易处理数据，来在被加载到所述第一工作电子装置的所述板载存储器中的第一索引列表内执行对与所述第一密钥相关联的所述交易处理数据的查找，其中所述第一索引列表提供了索引值至交易处理数据的各自段的阵列映射，其中所述交易处理数据的所述各自段与对应于所述第一散列映射的对应密钥子集的密钥相关联；以及
由所述第一工作电子装置，将包括与所述第一密钥相关联的所述交易处理数据的响应消息发送给所述管理器电子装置，其中所述响应消息是对由所述管理器电子装置发送给所述第一工作电子装置的所述请求消息的响应，
其中，由所述管理器电子装置利用与对应的索引列表一起存储在各自工作电子装置中的所述多个散列映射使得：对于所述交易处理数据的各自段中的每一段，分别获得与所述多个密钥相对应的所述交易处理数据的所述各自段将能够根据恒定O(1)算法复杂度以恒定时间被执行，并且
其中，所述第一索引列表是所述对应的索引列表之一。
2.根据权利要求1所述的计算机实施的方法，其中所述多个散列映射中各个散列映射的每一个对应于数据集的数据子集。
3.根据权利要求2所述的计算机实施的方法，其中与通过在所述数据集中搜索对应于所述第一密钥的所述交易处理数据相比，使用所述多个散列映射会更快确定与所述第一密钥相关联的所述交易处理数据。
4.一种系统，包括：
多个电子装置，包括：
管理器节点；和
多个工作节点，
其中所述管理器节点包括：
第一处理器，和
第一计算机可读介质，其耦合到所述第一处理器，所述第一计算机可读介质包括能由所述第一处理器执行以实施第一方法的代码，所述第一方法包括：
从用户操作的用户装置接收对交易处理数据的请求消息，所述请求消息包括多个密钥中的第一密钥，其中所述第一密钥与所述交易处理数据相关联，并且是与所述用户的账户标识符相对应的字母数字标识符；
响应于接收到所述请求消息，对所述第一密钥进行散列化以获得第一散列化密钥；
通过将所述第一散列化密钥输入第二散列映射并且获得第一散列映射的标识符，来将多个工作节点中的第一工作节点识别为多个散列映射中与所述第一密钥相关联的所述第一散列映射的存储位置，所述第一散列映射的所述标识符述第一散列化密钥和所述第一密钥相关联地存储在所述第二散列映射中，其中所述多个散列映射被分别存储在所述多个工作节点上，其中所述多个工作节点中的每一个存储所述多个散列映射中的一部分，所述一部分对应于所述多个密钥中的对应密钥子集，其中所述多个散列映射中各个散列映射的每一个分别提供所述对应密钥子集中包括的密钥至索引值的映射，其中所述多个工作节点中的每一个存储对应的索引列表，在所述对应的索引列表中，所述索引值被映射到所述对应的密钥子集的交易处理数据的各自段，并且其中与所述第一密钥相关联的所述第一散列映射是被加载到所述第一工作节点的板载存储器中的所述多个散列映射中的所述一部分；以及
将包括所述第一密钥的所述请求消息发送给所述第一工作节点；其中所述第一工作节点包括：
第二处理器，和
第二计算机可读介质，其耦合到所述第二处理器，所述第二计算机可读介质包括能由所述第二处理器执行以实施第二方法的代码，所述第二方法包括：
响应于从所述管理器节点接收到所述请求消息，对所述第一密钥进行散列化以产生第二散列化密钥；
通过将所述第二散列化密钥输入所述第一散列映射并且从所述第一散列映射获得对应于所述第二散列化密钥的所述索引值，来获得对应于所述第一散列映射中的所述第一密钥的索引值，其中所述索引值与所述第二散列化密钥和所述第一密钥相关联地存储在所述第一散列映射；
通过将从所述第一散列映射获取的所述索引值输入第一索引列表中以从所述第一散列映射获得与对应于来自所述第一索引列表的所述索引值的所述第一密钥相关联的所述交易处理数据，来在被加载到所述第一工作节点的所述板载存储器中的第一索引列表内执行对与所述第一密钥相关联的交易处理数据的查找，其中所述第一索引列表提供了索引值至交易处理数据的各自段的阵列映射，其中所述交易处理数据的所述各自段与对应于所述第一散列映射的对应密钥子集的密钥相关联；以及
将包括对应于所述第一密钥的所述交易处理数据的响应消息发送给所述管理器节点，所述响应消息是对由所述管理器节点发送给所述第一工作节点的所述请求消息的响应，
其中，由所述管理器节点利用与对应的索引列表一起存储在所述多个工作节点中的所述多个散列映射使得：对于所述交易处理数据的各自段中的每一段，分别获得与所述多个密钥相对应的所述交易处理数据的所述各自段将能够根据恒定O(1)算法复杂度以恒定时间被执行的，并且
其中，所述第一索引列表是所述对应的索引列表之一。
5.根据权利要求4所述的系统，其中所述多个散列映射中的每一个和所述对应的索引列表中的每一个个别地对应于数据集的数据子集。
6.根据权利要求5所述的系统，其中与通过在所述数据集中搜索对应于所述第一密钥的所述交易处理数据相比，使用所述第一散列映射、所述第二散列映射和所述第一索引列表会更快确定与所述第一密钥相关联的所述交易处理数据。
7.一种管理器电子装置，包括：
处理器，和
耦合到所述处理器的计算机可读介质，所述计算机可读介质包括能由所述处理器执行以实施方法的代码，所述方法包括：
从用户操作的用户装置接收对交易处理数据的请求消息，所述请求消息包括多个密钥中的第一密钥，其中所述管理器电子装置包括在分布式计算系统的多个电子装置中，并且其中所述第一密钥与所述交易处理数据相关联，并且是与所述用户的账户标识符相对应的字母数字标识符；
响应于接收到所述请求消息，对所述第一密钥进行散列化以获得第一散列化密钥；
通过将所述第一散列化密钥输入第二散列映射并且获得第一散列映射的标识符，来将各自工作电子装置中的第一工作电子装置识别为多个散列映射中与所述第一密钥相关联的所述第一散列映射的存储位置，所述第一散列映射的所述标识符与所述第一散列化密钥和所述第一密钥相关联地存储在所述第二散列映射，其中所述多个散列映射被存储在所述多个电子装置中的所述各自工作电子设装置上，其中所述各自工作电子装置中的每一个存储所述多个散列映射中的一部分，所述一部分对应于所述多个密钥中的对应密钥子集，其中所述多个散列映射中各个散列映射的每一个分别提供所述对应密钥子集中包括的密钥至索引值的映射，其中所述各自工作电子装置中的每一个存储对应的索引列表，在所述对应的索引列表，所述索引值被映射到所述对应的密钥子集的交易处理数据的各自段，并且其中与所述第一密钥相关联的所述第一散列映射是被加载到所述第一工作电子装置的板载存储器中的所述多个散列映射中的所述一部分；
将包括所述第一密钥的所述请求消息发送给所述第一工作电子装置；
其中，响应于所述请求消息，所述第一工作电子装置对所述第一密钥进行散列化以产生第二散列化密钥；通过将所述第二散列化密钥输入所述第一散列映射，来获得对应于所述第一散列映射中的所述第一密钥的索引值；从所述第一散列映射获得对应于所述第二散列化密钥的所述索引值，其中所述索引值与所述第二散列化密钥和所述第一密钥相关联地存储在所述第一散列映射中；通过将从所述第一散列映射获取的所述索引值输入第一索引列表中以从所述第一散列映射获得与对应于来自第一索引列表的所述索引值的所述第一密钥相关联的所述交易处理数据，来在被加载到所述第一工作电子装置的所述板载存储器中的第一索引列表内执行对与所述第一密钥相关联的所述交易处理数据的查找，其中所述第一索引列表提供了索引值至交易处理数据的各自段的阵列映射，其中所述交易处理数据的所述各自段与对应于所述第一散列映射的对应密钥子集的密钥相关联；以及将包括对应于所述第一密钥的所述交易处理数据的响应消息发送给所述管理器电子装置，其中所述响应消息是对由所述第一工作电子装置接收到的所述请求消息的响应，
其中，所述方法还包括：从所述第一工作电子装置接收包括与所述第一密钥相关联的所述交易处理数据的响应消息，所述响应消息是对由所述处理器发送给所述第一工作电子装置的所述请求消息的响应，
其中，由所述管理器电子装置利用与对应的索引列表一起存储在各自工作电子装置中的所述多个散列映射使得：对于所述交易处理数据的各自段中的每一段，分别获得与所述多个密钥相对应的所述交易处理数据的所述各自段将能够根据恒定O(1)算法复杂度以恒定时间被执行，并且
其中，所述第一索引列表是所述对应的索引列表之一。
8.根据权利要求7所述的管理器电子装置，其中所述多个散列映射的各个散列映射中的每一个对应于数据集的子集。
9.一种系统，包括：
处理器；和
耦合到所述处理器的计算机可读介质，所述计算机可读介质包括代码，所述代码能由所述处理器执行以实施如权利要求1－3中任何一项所述的计算机实施的方法。
CN201680090880.3A 2016-09-22 2016-09-22 存储器内数据搜索技术 Active CN110036381B (zh)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/US2016/053190 WO2018056993A1 (en) 2016-09-22 2016-09-22 Techniques for in-memory data searching

Publications (2)

Publication Number Publication Date
CN110036381A CN110036381A (zh) 2019-07-19
CN110036381B true CN110036381B (zh) 2024-05-28

Family

ID=61689716

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201680090880.3A Active CN110036381B (zh) 2016-09-22 2016-09-22 存储器内数据搜索技术

Country Status (5)

Country Link
US (2) US11645267B2 (zh)
EP (1) EP3516540B1 (zh)
CN (1) CN110036381B (zh)
SG (1) SG11201811423SA (zh)
WO (1) WO2018056993A1 (zh)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2018056993A1 (en) 2016-09-22 2018-03-29 Visa International Service Association Techniques for in-memory data searching
US10831734B2 (en) * 2018-05-07 2020-11-10 Intel Corporation Update-insert for key-value storage interface
CN110866062B (zh) * 2018-08-09 2023-11-24 菜鸟智能物流控股有限公司 基于分布式集群的数据同步方法以及装置
US11816479B2 (en) * 2020-06-25 2023-11-14 Jpmorgan Chase Bank, N.A. System and method for implementing a code audit tool
US11849039B2 (en) * 2021-11-29 2023-12-19 Circle Internet Financial Limited Parallel block processing in blockchains
US20240289334A1 (en) * 2023-02-28 2024-08-29 Microsoft Technology Licensing, Llc Streaming aggregation queries

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6434662B1 (en) * 1999-11-02 2002-08-13 Juniper Networks, Inc. System and method for searching an associative memory utilizing first and second hash functions
CN101114296A (zh) * 2006-07-28 2008-01-30 三星电子株式会社 管理许可的方法和设备
CN102591947A (zh) * 2010-12-28 2012-07-18 微软公司 用于数据去重复的快速且低ram占用的索引
US8868506B1 (en) * 2010-06-17 2014-10-21 Evolphin Software, Inc. Method and apparatus for digital asset management

Family Cites Families (31)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4925311A (en) * 1986-02-10 1990-05-15 Teradata Corporation Dynamically partitionable parallel processors
EP0381418A3 (en) * 1989-01-31 1991-11-27 International Business Machines Corporation A small fast lookup table for use in a data processing system
US5204958A (en) * 1991-06-27 1993-04-20 Digital Equipment Corporation System and method for efficiently indexing and storing a large database with high data insertion frequency
GB9204450D0 (en) * 1992-03-02 1992-04-15 Ibm Concurrent access to indexed data files
US6035326A (en) * 1997-05-07 2000-03-07 International Business Machines Corporation Mapping table lookup optimization system
US6247014B1 (en) * 1998-07-01 2001-06-12 Nortel Networks Limited Method and apparatus for performing hash lookups using valid bit tables with pointers
US20030018694A1 (en) 2000-09-01 2003-01-23 Shuang Chen System, method, uses, products, program products, and business methods for distributed internet and distributed network services over multi-tiered networks
AU2001288644A1 (en) 2000-09-01 2002-04-08 International Interactive Commerce, Ltd. System, method, uses, products, program products, and business methods for distributed internet and distributed network services
US7287033B2 (en) * 2002-03-06 2007-10-23 Ori Software Development, Ltd. Efficient traversals over hierarchical data and indexing semistructured data
US7058639B1 (en) 2002-04-08 2006-06-06 Oracle International Corporation Use of dynamic multi-level hash table for managing hierarchically structured information
US7370055B1 (en) * 2003-06-04 2008-05-06 Symantec Operating Corporation Efficiently performing deletion of a range of keys in a B+ tree
US7499912B2 (en) * 2003-10-23 2009-03-03 Hywire Ltd. Search method using coded keys
US7941401B2 (en) 2005-05-09 2011-05-10 Gemstone Systems, Inc. Distributed data management system
US7827218B1 (en) * 2006-11-18 2010-11-02 X-Engines, Inc. Deterministic lookup using hashed key in a multi-stride compressed trie structure
US7930547B2 (en) * 2007-06-15 2011-04-19 Alcatel-Lucent Usa Inc. High accuracy bloom filter using partitioned hashing
US8838558B2 (en) * 2007-08-08 2014-09-16 Hewlett-Packard Development Company, L.P. Hash lookup table method and apparatus
US8271564B2 (en) * 2008-07-14 2012-09-18 Symbol Technologies, Inc. Lookup table arrangement and related management method for accommodating concurrent processors
US8397051B2 (en) * 2009-02-23 2013-03-12 Autonomy, Inc. Hybrid hash tables
CN101692651B (zh) * 2009-09-27 2014-12-31 中兴通讯股份有限公司 一种哈希查找表的方法和装置
US9020946B2 (en) * 2010-07-12 2015-04-28 Qvinci Software, Llc System and method for compilation of quickbooks accounts data
WO2012059816A2 (en) 2010-11-04 2012-05-10 Conprox Ab Method and apparatus for handling digital objects in a communication network
US9639575B2 (en) 2012-03-30 2017-05-02 Khalifa University Of Science, Technology And Research Method and system for processing data queries
US9378179B2 (en) * 2012-11-21 2016-06-28 International Business Machines Corporation RDMA-optimized high-performance distributed cache
US9332083B2 (en) 2012-11-21 2016-05-03 International Business Machines Corporation High performance, distributed, shared, data grid for distributed Java virtual machine runtime artifacts
US9009165B2 (en) * 2013-01-10 2015-04-14 Telefonaktiebolaget L M Ericsson (Publ) High performance hash-based lookup for packet processing in a communication network
US9384145B2 (en) * 2013-08-26 2016-07-05 Oracle International Corporation Systems and methods for implementing dynamically configurable perfect hash tables
US9460210B2 (en) * 2014-04-04 2016-10-04 Dropbox, Inc. Enriching contact data based on content sharing history in a content management system
US9847935B2 (en) * 2014-04-29 2017-12-19 Intel Corporation Technologies for distributed routing table lookup
WO2015180125A1 (en) 2014-05-30 2015-12-03 Qualcomm Incorporated Multi-table hash-based lookups for packet processing
JP6549704B2 (ja) 2014-09-25 2019-07-24 オラクル・インターナショナル・コーポレイション 分散コンピューティング環境内でゼロコピー２進基数木をサポートするためのシステムおよび方法
WO2018056993A1 (en) 2016-09-22 2018-03-29 Visa International Service Association Techniques for in-memory data searching

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6434662B1 (en) * 1999-11-02 2002-08-13 Juniper Networks, Inc. System and method for searching an associative memory utilizing first and second hash functions
CN101114296A (zh) * 2006-07-28 2008-01-30 三星电子株式会社 管理许可的方法和设备
US8868506B1 (en) * 2010-06-17 2014-10-21 Evolphin Software, Inc. Method and apparatus for digital asset management
CN102591947A (zh) * 2010-12-28 2012-07-18 微软公司 用于数据去重复的快速且低ram占用的索引

Also Published As

Publication number Publication date
EP3516540A4 (en) 2020-04-15
US20190310974A1 (en) 2019-10-10
CN110036381A (zh) 2019-07-19
SG11201811423SA (en) 2019-01-30
US11645267B2 (en) 2023-05-09
US20230237051A1 (en) 2023-07-27
US11971880B2 (en) 2024-04-30
EP3516540B1 (en) 2024-07-17
WO2018056993A1 (en) 2018-03-29
EP3516540A1 (en) 2019-07-31

Similar Documents

Publication Publication Date Title
US12248487B2 (en) Techniques for in memory key range searches
US11971880B2 (en) Techniques for in-memory data searching
US9996565B2 (en) Managing an index of a table of a database
CN112650759B (zh) 数据查询方法、装置、计算机设备及存储介质
US20150310050A1 (en) Managing a table of a database
US20120224482A1 (en) Credit feedback system for parallel data flow control
WO2022111148A1 (en) Metadata indexing for information management
CN112445873B (zh) 列表显示处理方法、相关装置、设备及介质
US9965558B2 (en) Cross-channel social search
US20150149498A1 (en) Method and System for Performing an Operation Using Map Reduce
CN117472542A (zh) 一种任务处理方法、装置及电子设备
US20230267121A1 (en) Query efficiency using merged columns
US9607029B1 (en) Optimized mapping of documents to candidate duplicate documents in a document corpus
US11687542B2 (en) Techniques for in-memory data searching
CN110889040B (zh) 用于推送信息的方法和装置
WO2023241405A1 (en) Database query processing with database clients
CN112328960B (zh) 数据运算的优化方法、装置、电子设备及存储介质
CN119201932A (zh) 数据索引构建方法、装置及存储介质

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant