Récit de RSE n ° 5: L'histoire de PebblesDB

Je pensais qu'il était temps que je raconte une histoire à moi. Voici comment notre magasin de valeurs-clés PebblesDB a été créé et publié à SOSP 17. L’histoire implique également mon expérience post-doc chez VMware Research.

Cette histoire commence en 2015, alors que je terminais mon doctorat. J'interviewais à la fois dans l'industrie et dans le monde universitaire: je pensais en fait que je n'allais pas recevoir d'offres universitaires (je ne travaillais pas sur des sujets aussi sexy que le cloud computing ou l'apprentissage automatique), mais je voulais l'essayer avant de partir pour l'industrie. . Je voulais rejoindre un laboratoire de recherche industrielle tel que Microsoft Research.

Fait intéressant, à l'époque où j'étais sur le marché du travail, quelques personnes de Microsoft Research Silicon Valley avaient créé un nouveau laboratoire de recherche dans VMware. Mes mentors de stage, Mahesh Balakrishnan et Marcos Aguilera, étaient dans ce nouveau laboratoire. Ils m'ont donc encouragée à postuler. J'ai interviewé au labo et j'ai passé un excellent séjour. Ils m'ont proposé de rejoindre le poste de chercheur.

J'ai ensuite interviewé dans différentes universités et j'ai été extrêmement chanceux de décrocher une offre à l'Université du Texas à Austin. J’ai appelé Dahlia Malkhi (l’un des membres fondateurs du laboratoire de recherche) pour lui annoncer la nouvelle et lui dire que je ne pouvais pas rejoindre VMware Research (ou VRG, comme on l’appelle). Dans le même appel, Dahlia m'a suggéré de faire un post-doc d'un an avant de rejoindre UT et m'a proposé de m'accueillir à VRG. J'avais déjà entendu parler de post-doctorants réussis d'un an (par exemple, Philip Guo), et je ne voulais pas vraiment me plonger tout de suite dans la vie de professeur, alors j'ai accepté. J'ai parlé avec les gens à UT Austin, qui étaient heureusement d'accord pour reporter ma date d'adhésion d'un an.

Lorsque j'ai rejoint VRG, j'avais pour objectif explicite de créer de nouvelles connexions, et pas seulement de travailler sur les mêmes choses que lors de ma thèse. J'ai parlé à beaucoup de chercheurs de ce sur quoi ils travaillaient et de la façon dont je pouvais aider. C’est la première fois que j’ai parlé à Ittai Abraham, un expert en théorie et structures de données (son expertise couvre beaucoup plus de domaines, mais c’est la façon la plus brève de le décrire). Ittai avait cette idée sur une nouvelle structure de données pour les magasins à valeur clé, et il voulait une personne possédant une expérience des systèmes pour la construire. Je me suis joint à moi en pensant que ce serait un projet rapide d'un à trois mois.

Les premiers jours ont été un peu difficiles, la plupart de ce que disait Ittai me tombait sur la tête. Les gens des systèmes et les gens de la théorie parlent vraiment des langues différentes. Pour mieux comprendre l'intuition derrière le projet, j'ai commencé à construire un prototype rapide en python qui incarne la nouvelle structure de données imaginée par Ittai. Notre prototype a montré que la nouvelle structure de données pouvait considérablement réduire l'amplification en écriture, bien que nos latences soient nettement supérieures à celles des magasins de clés-valeurs C ++ que nous comparions. J'ai présenté la première forme de PebblesDB lors de la conférence VMware RADIO, une conférence interne sur la R & D dans VMware. En réalité, les conférences académiques n’ont rien sur RADIO: la valeur de production de RADIO est plus proche de celle de TED qu’une conférence académique. Vous auriez pu avoir un petit concert sur cette scène et cela n’aurait pas semblé déplacé.

Après avoir reçu des commentaires positifs et utiles sur RADIO, Ittai et moi-même avons décidé de modifier un magasin clé-valeur existant pour utiliser notre nouvelle structure de données. Nous avons choisi LevelDB, car il était considérablement plus simple et plus facile à comprendre que RocksDB, et nous avons commencé à le modifier. Plus précisément, nous avons commencé à modifier HyperLevelDB, un portage de LevelDB par les employés de HyperDex à Cornell (groupe de Emin Gun Sirer).

Nous avons eu plusieurs moments où nos suppositions se sont heurtées à ce que LevelDB faisait réellement: par exemple, nous pensions qu’il y aurait une recherche binaire sur l’ensemble du sstable en faisant une recherche O (logn); s'avère que les sstables ont juste des index faisant la recherche O (1).

C’était la partie la plus amusante du projet, car il fallait passer d’une structure de données théorique à la construction d’un magasin clé-valeur offrant des performances exceptionnelles. PebblesDB a dû être utilisé avec un certain nombre d’astuces d’ingénierie bien connus.

Nous étions à mi-chemin de la mise en œuvre lorsque mon post-doc a pris fin et j'ai rejoint UT. Heureusement, presque immédiatement, Pandian a rejoint mon groupe de recherche et a pris en charge la partie construction du système. Pandian est un constructeur de systèmes incroyable. Nous avons donc bientôt eu un prototype prêt à l'emploi. Nous l'avons évalué par rapport à LevelDB et avons obtenu d'excellents résultats. Nous l'avons donc écrit et envoyé à Euroys.

Nous avons été rejetés chez Eurosys, principalement pour deux raisons: nous n’avions pas évalué contre RocksDB et nous n’avions pas très bien expliqué la conception. Il semblait que cela ressemblait davantage à un paquet de hacks à LevelDB qu'à une nouvelle structure de données. Nous nous sommes donc mis au travail, en évaluant par rapport à RocksDB et en évaluant les performances d'applications telles que HyperDex et MongoDb en plus de PebblesDB. C'est à ce moment que Rohan Kadekodi a rejoint le projet. Rohan est un autre constructeur de systèmes exceptionnel. En l'espace d'un mois, il est passé de ne rien savoir à propos de MongoDB à la modifier pour qu'il fonctionne au-dessus de PebblesDB.

C’est lors de l’analyse comparative des performances des applications que nous avons eu d’autres surprises. Par exemple, dans HyperDex et MongoDB, de nombreuses requêtes put () seraient transformées en requêtes get () + put () afin de vérifier en premier lieu si la clé est déjà présente. Cela a eu un impact significatif sur les performances de PebblesDB, PebblesDB pouvant gérer beaucoup plus de requêtes put () que l’application ne l’envoyait. C'était intéressant de comprendre ces bizarreries d'applications!

Une autre chose que nous avons abordée était l'écriture. J'ai distribué notre brouillon au groupe des systèmes à l'Université de Austin. Nous avons obtenu d’excellents commentaires et j’ai réécrit le document pour préciser que nous agissions de deux manières: l’innovation de la structure de données en termes de structure de données Fragmented Log-Structured Merge Trees (FLSM) et la construction de PebblesDB par-dessus de FLSM avec les astuces d'ingénierie associées). En particulier, les retours d’introduction ont été extrêmement utiles et nous les avons réécrits à plusieurs reprises pour faire passer le message. Nous avons soumis le document à SOSP.

La nouvelle est arrivée en août: nous avons été acceptés avec de bonnes critiques! C'était bon de savoir que tout ce travail a finalement porté ses fruits. Nous avons travaillé avec notre berger, l'incroyable Frans Kaashoek, pour répondre aux commentaires des critiques. Nous avons également travaillé dur pour publier le code en open-source sur Github (où il a suscité beaucoup d'attention: 98 étoiles à partir de maintenant!). Nous avons également travaillé à la publication des modifications apportées à MongoDB afin qu’elle puisse être exécutée en plus de PebblesDB.

Travailler sur PebblesDB m'a fait réfléchir au problème de l'amplification d'écriture sur la pile de stockage, alors j'ai commencé à travailler dessus à UT Austin. Les travaux préliminaires dans cet espace ont conduit à une meilleure affiche chez ApSys et à une subvention NSF CAREER! Donc dans l’ensemble, une expérience post-doc réussie :)

Mes leçons de l'expérience PebblesDB:

  • Ecrire est super important. Je suis fermement convaincu que le temps passé à réécrire le document pour être meilleur rapporte beaucoup plus que le temps consacré à la réalisation d'expériences supplémentaires (bien qu'une évaluation approfondie soit également importante).
  • Travailler avec des théoriciens, c'est très amusant! Si vous trouvez les bons collaborateurs, travailler sur un mélange de théorie et de pratique conduit à une recherche extrêmement satisfaisante et à beaucoup d'impact. Des projets similaires en cours chez VMware Research sont super cool.
  • Si vous souhaitez intégrer le monde universitaire, je vous recommande vivement de suivre un post-doc d'un an après avoir terminé votre doctorat. Le post-doc m'a permis de reprendre mon souffle après le doctorat, d'explorer de nouveaux projets et de nouer de nouvelles relations que je n'aurais jamais eu autrement.
  • Je recommande vivement de faire un post-doctorat chez VMware Research (et non, je ne suis pas payé pour le dire.) Le groupe de recherche compte des chercheurs incroyables possédant une vaste expérience dans un certain nombre de domaines, et la culture est orientée vers la réalisation de grands projets prendre plus de temps mais aura un impact durable.