XPS: EXPL: SDA: Scalable Concurrency Control Techniques for Distributed Systems

几乎所有分布式计算应用程序，从数据库上的事务到社交媒体平台上的更新，都涉及对数据对象的并发操作。对于这些应用程序，并发控制机制代表了显著的性能开销。这些应用程序通常在数据访问方面表现出强大和持久的模式。由于这个问题的重要性，这个项目研究了分布式计算中动态数据和锁访问模式的使用，以显著提高可扩展系统的并发控制机制的性能，特别是在传统的云环境和键值存储（如BigTable、HBase和Cassandra）中。与将锁与相应数据项并置的传统技术相比，该项目依赖于模块化锁服务，该服务将锁位置与相应数据对象解耦，并在一小组存储节点中维护所有数据项的锁状态。这种设计选择引发了本研究的许多问题：(i)应该在何时何地将锁定状态迁移到锁定服务中？（ii）锁状态何时应返回到数据存储？（iii）锁服务应如何扩展？（iv）这些操作的容错、低开销、无死锁和无活锁协议是什么？(v)如何在这样的系统中利用长寿命的数据访问模式？在初步结果的基础上，该项目展示了该方法的可行性和可观的前景，开发了算法、协议、分析和开源软件，并在各种应用程序的背景下进行了全面验证。该项目将为可扩展分布式系统中的并发控制提供一个新的框架。并发控制服务具有许多理想的特性：(i)模块化——服务可以在运行时实例化，对底层数据存储组织和访问机制的更改最小；（ii）可扩展性？服务动态适应负载和服务需求；（iii）通过使用利用数据和锁定访问模式的高效算法实现高性能。这些特性是通过锁迁移和并置算法、动态锁和数据访问统计模型、锁状态管理协议、正确性和公平性、容错、性能和可伸缩性的相关证明的新颖组合来实现的。并发控制服务在私有云和公共云上都得到了充分的验证，这些云上混合了来自在线事务处理和机器学习的应用程序。该项目通过提供模块化和可扩展的锁服务，直接影响了一类重要的基于云的应用程序。该服务在提供高性能和弹性吞吐量的同时减轻了应用程序程序员的负担。除此之外，该项目还包括一些针对本科和研究生教育的教育倡议，以及旨在提高少数群体代表性的外联努力。这些措施包括编写教学材料、课程、组织讲习班和暑期学校并在其中发表演讲，以及针对代表性不足群体学生的招聘倡议。

Virtually all distributed computing applications, from transactions on databases to updates on social media platforms, involve concurrent operations on data objects. For these applications, concurrency control mechanisms represent significant performance overheads. These applications typically exhibit strong and persistent patterns in data access. Motivated by the importance of the problem, this project investigates the use of dynamic data- and lock-access patterns in distributed computations to significantly improve the performance of concurrency control mechanisms for scalable systems, specifically, in conventional cloud environments and key-value stores such as BigTable, HBase, and Cassandra. In contrast to conventional techniques that collocate locks with corresponding data items, this project relies on a modular lock service that decouples lock locations from corresponding data objects, and maintains lock state of all data items in a small set of storage nodes. This design choice motivates a number of questions for this research: (i) where and when should lock states be migrated into the lock service? (ii) when should lock state be repatriated to the data store? (iii) how should the lock service be scaled out? (iv) what are fault-tolerant, low-overhead, deadlock- and livelock-free protocols for these operations? and (v) how can long-lived data access patterns be leveraged in such systems? Building on preliminary results that demonstrate the feasibility and considerable promise of the approach, the project develops algorithms, protocols, analyses, and open-source software, along with comprehensive validation in the context of a diverse set of applications.The project will result in a novel framework for concurrency control in scalable distributed systems. The concurrency control service has a number of desirable features: (i) modularity -- the service can be instantiated at runtime, with minimal change to underlying data storage organization and access mechanisms; (ii) extensibility ? the service adapts dynamically to load and service requirements; and (iii) high performance through the use of efficient algorithms exploiting data and lock access patterns. These features are achieved through a novel mix of algorithms for lock migration and collocation, statistical models for dynamic lock and data access, protocols for lock state management, associated proofs of correctness and fairness, fault tolerance, performance, and scalability. The concurrency control service is fully validated on private as well as public clouds on a mix of applications drawn from Online Transaction Processing and Machine Learning.The project directly impacts an important class of cloud-based applications by providing a modular and extensible lock service. The service relieves burden on the application programmer while providing high performance and elastic throughput. Beyond this, the project includes a number of educational initiatives aimed at undergraduate and graduate education, along with outreach efforts aimed at enhancing representation of minority groups. These include development of instructional material, curricula, organization of and presentations at workshops and summer schools, and recruitment initiatives aimed at students from under-represented groups.