Return to Job offers

Master’s internship: Generating efficient concurrency control for geo-replicated storage

Background

Reasoning about concurrent updates in a replicated database is a difficult task because operations might execute in different orders at different replicas. We have developed a tool, called CISE, that verifies whether a given program will maintain its specific correctness invariants under concurrent execution [Balegas]. If not, the tool provides a counter-example, which the program developer can examine, in order to understand which concurrent executions should be disallowed. We call these abstract concurrency control points tokens.

Abstractly, a token is similar to a lock. A possible (but inefficient) implementation would be the following: before a process can execute an operation, it acquires the corresponding locks; when the operation returns, it immediately releases the locks. This is formally correct, but is unlikely to perform well, because of the high cost of acquiring and releasing locks. Alternatively, a process could acquire all the locks it will ever need initially, and never release them. This would be highly efficient and safe, but also inefficient, because other processes would never be able to do any work. A good protocol lies somewhere between these two extremes.

Problem statement

Although the CISE tool is automatic, the later steps of identifying the appropriate tokens, and then to translate this into an efficient concurrency control protocol, are currently manual. This is tedious and error-prone.

A first level of improvement would be to automate the analysis of counter-examples, in order to suggest a correct token assignment. A second level will be to automate the translation of the above token assignment into an efficient concrete protocol.

There are different ways to optimize a lock implementation, each with own cost and complexity. Examples include multi-level locks [Lomet], lock coarsening [Kulkarni], and early lock release [Johnson]. As suggested above, each operation may be protected by its own fine-grain lock, at the cost of constant acquire{\slash}release cycles. A well-known optimization is to coarsen, replacing several fine-grain locks with a single coarse-grain one. Although a coarser lock reduces the synchronization cost, it also delays concurrent updates, which costs performance too.

From a performance perspective, there is no single best locking protocol, since this will depend on dynamic characteristics of the workload, namely on how often updates are blocked (contention) vs. how often locks are acquired (overhead).

Internship topic

The internship topic is to address the above issues. Its specific goals may include the following:

  • Automating the analysis of counter-examples, to derive an appropriate token assignment.
  • Using heuristics to automatically generate an efficient concurrency control protocol, based on assumptions about the workload. Consider alternatives to locking when appropriate, e.g., leveraging causality, or using escrow. Compare different possible protocols for the same application, quantifying the lock optimization benefits against costs.
  • Develop profiling or monitoring tools to measure the efficiency of the concurrency control protocol under different workloads, and heuristics to improve it.
  • Ensuring that the concurrency control protocol does not deadlock, through analysis, heuristics, and{\slash}or automated testing.

The approach is likely to combine both static analysis, extending the CISE tool with token assignment and concurrency control generation, and dynamic analysis to evaluate performance, and to ensure absence of deadlock under real conditions.

Requirements and application

The intern must:

  • Be enrolled in a Masters’ in Computer Science / Informatics or a related field.
  • Have an excellent academic record.
  • Be strongly interested in, and have good knowledge of, distributed systems, distributed algorithms, distributed databases, or static and dynamic analysis.
  • Be motivated by experimental research.

The internship is fully funded, and will take place in the Delys group, at Laboratoire d’Informatique de Paris-6 (LIP6), in Paris. It will be advised by Sreeja Nair and Dr. Marc Shapiro. A successful intern will be invited to apply for a PhD.

To apply, contact Sreeja Nair <sreeja.nair@lip6.fr>, with the following information:

  • A resume or Curriculum Vitæ.
  • A list of courses and grades of the last two years of study (an informal transcript is OK).
  • Names and contact details of two references (people who can recommend you), whom we will contact directly.

Bibliography

[Balegas] Valter Balegas, Nuno Preguiça, Rodrigo Rodrigues, Sérgio Duarte, Carla Ferreira, Mahsa Najafzadeh, and Marc Shapiro. Putting consistency back into eventual consistency. In Euro. Conf. on Comp. Sys. (EuroSys), pages 6:1–6:16, Bordeaux, France, April 2015. DOI: 10.1145/2741948.2741972.

[Johnson] Ryan Johnson, Ippokratis Pandis, Radu Stoica, Manos Athanassoulis, and Anastasia Ailamaki. Aether: A scalable approach to logging. Proc. VLDB Endow., 3(1-2):681–692, September 2010. DOI: 10.14778/1920841.1920928.

[Kulkarni] Milind Kulkarni, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Kavita Bala, and L. Paul Chew. Optimistic parallelism benefits from data partitioning. In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XIII, pages 233–243, New York, NY, USA, 2008. DOI: 10.1145/1346281.1346311.

[Lomet] David B. Lomet. Multi-level locking with deadlock avoidance. In Proceedings of the 1978 Annual Conference – Volume 2, ACM ’78, pages 862–867, New York, NY, USA, 1978. DOI: 10.1145/800178.810155.