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.