Internship – Towards a formally specified caching library

Tarides

Tarides is a tech start-up founded in Paris in 2018 by pioneers of programming languages and cloud computing. Tarides develops a software infrastructure platform to deploy secure, distributed applications with strict resource constraints and low-latency performance requirements. Today, Tarides is composed of a diverse team of 35+ people.

Tarides has been part of the Founder program of Station F in 2018 (6% acceptance rate) and has been selected in France within “Concours d’Innovation i-Lab” organized by the French Ministry of Higher Education, Research and Innovation in partnership with Bpifrance (15% acceptance rate). This national contest awards company creation and innovative technologies. Tarides was also recognised during the FIC 2020 fair (International Cybersecurity Forum) which is the leading European event on cybersecurity. These awards acknowledge the innovation of the solutions developed by Tarides and emphasize the interest from the cybersecurity community.”


Internship at Tarides

Tarides internships are an excellent opportunity to participate in open-source functional programming with tangible real-world applications.

Our interns each work on a personal project that will have a meaningful impact on the project and the wider OCaml open-source ecosystem. Each intern is assigned a mentor at Tarides to give advice and guidance when necessary. Below are ideas for potential internship topics. These are intended as suggestions only; if you’re excited about a particular aspect of our work at Tarides, let us know and we’ll do our best to accommodate you.


Context

A cache is a data structure that temporarily stores data to speed up future requests and avoid costly operations such as disk queries or hash computations. These are usually bounded capacity data structures: whenever the cache is full, and you need to add some new data, the cache must discard an existing element to make room for the new one. Choosing which piece of data to discard is called the cache replacement policy.

For instance, a common cache replacement policy is LRU (Least Recently Used): the cache discards the oldest element it contains. The LFU (Least Frequently Used) strategy is also a popular alternative: the least frequently accessed elements in the cache are discarded first. The optimal strategy depends on the particular problem the cache is applied to.

At Tarides, we develop Irmin, a git-like distributed database library. It is a performance-critical application, especially when deployed in the storage layer of the Tezos blockchain. Irmin advantageously uses LRU caches to optimize disk accesses and provide low latency operations. It will be the field of evaluation of the policies implemented during the internship.

Replacement policies can be complex, but since missing entries is part of the caches’ expected behaviour, wrongfully understanding or implementing them often go unnoticed. It can, however, dramatically affect performances or lead to memory leakages. The intern will leverage Gospel, a behavioural specification language for OCaml interfaces, to formalize the replacement strategies and ensure their implementation comply with them.

The goal of this internship is to:

  • Efficiently implement various caching policies (e.g. LFU, LIRS, etc.).
  • Evaluate the performance of the different policies in a real-world setting within Irmin and Tezos.
  • Formalize their behaviour and specify the cache replacement policy using Gospel.

Qualifications


(You don’t have to fill 100% of the qualifications to apply.)

  • Non-trivial functional programming experience
  • Ability to read scientific publications and implement concepts described in them
  • Basic knowledge in algorithmics and data structures
  • Familiarity with formal specification/verification is useful, but not required


What we offer

  • Nice office in Paris (Place de la Contrescarpe, Paris 5)
  • Flexible working hours and possibility to work remotely
  • Supportive team environment with experienced Technical and Team Leads
  • A “ticket restaurant” card
  • 100% of public transportation pass reimbursed
  • Sport perks with ClassPass


Process

If shortlisted, you will have two online interviews starting with a general interview, followed by a technical interview.

We welcome applications from people of all backgrounds. We strive to create a representative, inclusive and friendly team, because we know that different experiences, perspectives and backgrounds make for a better workplace.

Leave a Reply