Performance of Concurrent Data Algorithms

航空公司、电信、银行等应用， 在不久的将来，实时数据库将需要1000或 每秒处理的事务数，其中事务由 4-6 record通过数据结构访问它们中的大多数。 在这些事务速率和隐含的多处理级别上， 经典的并发数据结构技术可能太慢。 这项工作寻求消除缓慢瓶颈的方法 交易费率。各种各样的算法思想，包括 协作并发和无等待技术，将是 进行评估，以确定并发数据 结构化算法必须具备以实现高性能。 目标是提供一种合理的方法来选择（或 发明）： 1.算法策略（例如自下而上链接技术）; 2.恢复策略（例如，操作日志记录， 物理记录）;以及 3.空间和时间之间的权衡（例如， 半合并与空合并相比）。 除了对高性能数据库的直接好处之外， 管理系统，这项工作将摆脱洞察力的一般 并发和并行计算领域。

Applications such as airlines, telecommunications, banks, and real-time database will in the near future require 1000 or more transactions per second, where a transaction consists of 4-6 record accesses most of them through data structures. At these transaction rates and implied multiprocessing levels, classical concurrent data structure techniques may be too slow. This work seeks methods to eliminate the bottleneck of slow transaction rates. A variety of algorithmic ideas, including cooperative concurrent and wait-free techniques, will be evaluated to determine what features a concurrent data structure algorithm should possess to achieve high performance. The goal is to provide a rational method for choosing (or inventing): 1. algorithmic strategies (e.g. bottom-up link technique); 2. recovery strategies (e.g. operation logging as opposed to physical logging); and 3. tradeoffs between space and time, (e.g. the benefits of merge-at-half compared to merge-at-empty). Besides the direct benefit to high performance database management systems, this work will shed insight on the general area of concurrent and parallel computation.