Pas de la tarte

Jeudi, mai 12, 2016
By David Baffaleuf in Operating System (dbaffaleuf@capdata-osmozium.com) [70 article(s)]

Non vraiment, ça va pas être de la tarte. Et si vous vivez dans une grotte depuis le début de l’année, vous ne savez peut être pas encore que SQL Server doit être porté sur Linux.

D’ailleurs mister Slava Oks, le grand gourou de l’allocation mémoire dans SQLOS, est revenu au bercail pour prêter main-forte à l’énorme chantier près de 10 ans après avoir quitté la dream team du building 35. C’est un signe qui ne trompe pas.

On a une idée relative du quand (mi-2017), on a déjà beaucoup évoqué le pourquoi. Il est encore trop tôt pour parler du comment. Tout ce qu’on peut formuler pour l’instant ce sont des hypothèses. C’est ce qu’on va faire, essayer de voir où peuvent être les grandes difficultés de porter SQL Server sur linux, de notre humble point de vue d’utilisateur – disons - éclairé du produit.

Pourquoi ça semble compliqué:

Parce que globalement le code de SQL Server a une adhérence très forte avec les primitives win32, et le sous-système du même nom (subsystem win32 = kernel32.dll + advapi32.dll + gdi32.dll + user32.dll). Ces primitives exposent à SQL Server tout un framework pour adresser des appels au noyau par exemple :

- Ouvrir, écrire, lire, étendre, réduire un fichier…
- Ouvrir une socket TCP, écouter sur un port TCP.
- Allouer et accéder à des pages en mémoire.
- Synchroniser les accès à des ressources partagées (principalement des listes chaînées de ressources, par exemple les BUFs, mais aussi des IO réseau ou disque…)

La plupart de ces actions ne peuvent pas se faire au niveau utilisateur (en ring 3), donc Windows fournit un ensemble de primitives qui sont ensuite ‘traduites‘ en quelque sorte par ntdll.dll en language noyau. C’est ainsi que WriteFile() qui est exposée par kernel32.dll est linkée à une fonction ZwWriteFile() qui ne peut être exécutée qu’en mode noyau (ring 0), qui contient du code spécifique à l’architecture (x64) et un appel au dispatcher parmi d’autres choses.

On comprend vite que l’ensemble du code est intimement lié à l’implémentation du C sous win32. Typiquement il n’existe pas d’IO Completion Port sous Linux. Pour chaque composant on va trouver un équivalent mais qui ne fonctionne pas tout à fait de la même façon.

Opposition de styles ?

On serait tenté d’imaginer que, même si Linux et Windows partagent aujourd’hui la même plateforme d’exécution qu’est le x86_64, ils sont très différents de conception. En fait ils ne sont pas si différents que ça.

Windows tel qu’on le connait aujourd’hui a été conçu à partir de 1989, principalement par Dave Cutler qui sortait en 1988 d’un projet avorté chez Digital (MICA/Prism) et qui avait déjà une bonne idée de comment devait fonctionner un operating system, dans la mesure où il avait déjà travaillé sur VMS pendant 13 ans. Linux a vu le jour à peu près à la même époque que NT, Linus Torvalds terminant la v0.02 aux alentours de 1991, donc dans le même contexte technologique, avec le monde des PC déjà bien établi. Plus troublant encore, leurs origines respectives sont également alignées sur la même période, le milieu des années 70 (UNIX pour Linux, et VMS pour Windows NT).

Vu du 8ième étage, les services in-core des deux noyaux semblent assez similaires, par exemple :

- Tout le code du noyau est exécuté dans un seul et même espace mémoire (contrairement aux micro-kernels), donc les services (object manager, memory manager, etc…) partagent le même pré carré et n’ont pas besoin de faire transiter de l’information d’un espace à un autre.
- Il y a bien une séparation induite par x86 entre l’espace mémoire réservée au noyau et celui réservé aux applications, même si le découpage est différent.
- Le processus a son propre espace d’adressage.
- Le noyau abstrait le matériel que ce soit SMP, HT, NUMA, etc…

A y regarder d’un peu plus près il existe quand même quelques différences d’implémentation des services systèmes, qu’il faut prendre en considération pour porter le code de SQL Server vers Linux.

Gestion de la mémoire :

La question du 32 bits étant évacuée, que peut-on dire de la gestion de la mémoire ? Là où les choses ont été bien faites dès le départ (et hommage soit rendu à Slava) c’est que la plupart des méthodes d’allocation ont été abstraites via des classes exposées par le framework de SQLOS : cachestores, userstores, pools, etc… Donc ce code-là ne devrait pas bouger. C’est plus ce sur quoi reposent ces classes qui peuvent être revues (HeapAlloc / VirtualAlloc).

Pour ce qui est du support des Locked Pages, qui devient presque un standard de fait sur x64, il y a un équivalent sur Linux dans la famille de fonctions mlock et mlockall, mais il faudrait creuser franchement dans la fonctionnalité car en plus de la garantie de non-pagination, l’intérêt des Locked Pages pour SQL Server est aussi lié au fait qu’il ne nécessite qu’un seul appel au PFN Database lock, c’est donc aussi une question de performance. Il n’est pas certain que le comportement soit similaire sur Linux.

Pour le support des Large Pages sur Windows, il y a l’équivalent Huge Pages sur Linux.

SQLOS / Scheduling:

Là il y a quelques différences notables entre ce que permet Linux par rapport à Windows, notamment sur la notion de process et de thread.

Sous Windows, un processus est concrètement représenté par un espace mémoire et au moins 1 thread, qu’on appelle thread 0. C’est ce thread qui porte l’exécution du code sur le CPU. Un process peut créer plusieurs threads.

Historiquement, sous Linux, c’est le processus qui porte l’exécution du code. Il y a eu un début de support des threads POSIX dans le milieu des années 90 (pThreads / LinuxThreads ) mais l’implémentation fait qu’à chaque pthread sous linux un processus de type LightWeight Process était créé au niveau du noyau. Et c’est ce LWP qui exécutait le code, ce qui fait ressembler le tout davantage aux fibers plutôt qu’aux threads win32. Parmi les limitations principales on peut citer le manque d’utilisation de la mémoire locale au thread (les registres), le fait qu’on soit obligé de créer un thread spécifique pour concentrer la gestion des signaux et respecter la norme POSIX (manager thread) et surtout le manque de primitive de synchronisation qui a fait que toute l’implémentation repose sur les signaux. C’est pourquoi la plupart des éditeurs de bases de données sous Linux n’ont (pratiquement) jamais changé leur modèle multi-processus / mémoire partagée (Oracle jusqu’à la 12c, postgreSQL et Sybase jusqu’à la 15.7, MySQL étant une exception).

Vers 2005, Red Hat (Ulrich Drepper / Ingo Molnar) proposa une alternative appelée Native POSIX Thread Library (NPTL) pour améliorer le support des threads en version 2.5  du noyau, bien plus prometteuse notamment sur la synchronisation, avec l’apparition des futexes (Fast Userspace Mutexes). L’utilisation de NPTL est maintenant généralisée.

Depuis le noyau 2.6, la sémantique se rapproche de Windows dans la mesure où l’unité d’exécution est bien devenue le thread. Un thread a un Thread ID et un Thread Group ID qui correspond grosso-modo au PID. Lorsqu’on appelle clone ou fork depuis un autre thread, soit on va créer un nouveau couple (TGID,TID), donc un nouveau process, soit un nouveau TID en conservant le TGID du cloneur, donc un nouveau thread dans le processus courant. La notion de process est devenue plus un espace mémoire et un ensemble de threads sous le même TGID aujourd’hui.

Si on en revient à SQL Server, on peut se demander quelle sera la stratégie adoptée. J’imagine mal que soient sortis les workers systèmes (CHECKPOINT, LOG MANAGER, SIGNAL HANDLER, RESSOURCE MONITOR, les TASK MANAGERs, etc…), du process address space de l’exécutable principal et discuter via de la mémoire partagée. Ça serait pire qu’un grand coup de pied dans la fourmilière. D’ailleurs, les tâches système dans Sybase ASE par exemple, qui est un peu le faux jumeau de SQL Server, sont intégrés à base de threads. Ce sont les schedulers, les engines dans le jargon, qui avaient été sortis sous forme de processus, mais ils peuvent être réintégrés sous forme de threads depuis la version 15.7.

Donc il y a fort à parier que les workers seront portés sur NPTL qui est la version la plus aboutie du support des threads POSIX sur Linux. Quant aux fibers, ils pourraient être remplacés par des threads POSIX version LinuxThreads mais vu les limitations, ils pourraient carrément ne pas être portés du tout.

Pour ce qui est du scheduler coopératif, tout se passe en usermode donc on ne voit pas bien ce qui pourrait poser problème. La valeur des quantums est presque équivalente entre les 2 OS.

J’ai remarqué un fait intéressant en comparant le quantum interne de SQLOS de 4ms et celui de Sybase ASE (timeslice de  100ms + plus une période de grace de 500 ticks d’horloge par défaut), et la différence est ENORME. Il faut dire que le timeslice sur ASE n’a pas évolué depuis à peu près 10 ans alors que la fréquence des processeurs à continué de progresser. Donc le problème serait-il plutôt côté Sybase ?  On verra bien  si les 4ms de SQL Server  tiennent toujours sur Linux. Je suis d’avis que ça ne changera pas.

On risque de voir quelques différences toutefois sur tout ce qui est préempté. Lorsque l’exécution va échapper à SQLOS sous Linux, le thread va hériter d’une priorité et d’un quantum qui vont fluctuer selon sa consommation CPU. Plus le thread consomme de la CPU, plus sa priorité va baisser par rapport aux autres (decay) et plus son quantum par contre va augmenter (entre 10 et 100ms). C’est là une différence avec Windows car un thread win32 hérite de la priorité de base du processus puis peut augmenter mais ne peut jamais repasser sous sa priorité de départ.

C’est une manière élégante pour Linux de permettre un accès équitable aux ressources entre les différentes applications, en infligeant une pénalité aux threads qui consomment le plus, tout en leur autorisant une plus grande plage de travail lors de leur prochaine exécution. Le martinet et le bonbon, en quelque sorte…

Quelques exemples de primitives à substituer:

Un autre point clé du développement va être de trouver des remplaçants à certaines fonctionnalités du type :

WaitForSingleObject / WaitForMultipleObject :

Sur Windows, un thread peut bloquer sur n’importe quel handle : un fichier, un event, un mutex, un process, un sémaphore, un timer, une notification, etc… Il appelle l’une de ces deux primitives en lui passant le handle de l’objet, plus quelques autres informations comme le timeout par exemple (SQL Server utilise massivement INFINITE pour ce paramètre).  Typiquement un thread est associé à un event par exemple, et l’initialise à False, puis bloque dessus avec un timeout à INFINITE. Un autre thread signale le premier en passant son event à True, et celui-ci peut commencer à travailler. C’est comme ça que fonctionne la yield routine au niveau SQLOS, le worker sortant signale le premier worker en runnable list.

Sous Linux, les processus et les threads utilisent principalement des signaux pour discuter. Les signaux sont de simples interruptions logicielles utilisées pour qu’un programme puisse discuter avec un autre. Par exemple, les processus backends PostgreSQL (qui matérialisent les connexions utilisateur) correspondent avec le processus postmaster (le processus initial) via des signaux, comme SIGINT, équivalent de Ctrl+C, pour annuler une requête en cours d’exécution.

Comme on part du principe que ce ne sera pas du multiprocess mais bien toujours du multithread, à base de NPTL, on suppose que les workers se signaleront entre eux via les futexes, qui vont permettre de se rapprocher de ce que donnent les events sur win32. Les futexes supportent des notions telles que le timeout y compris l’équivalent d’INFINITE (timeout à NULL) et la synchronisation sur plus d’un événement comme WaitForMultipleObjects.

Interlocked :

Les fonctions Interlocked permettent de construire ce qu’on appelle en usermode des spinlocks, des outils de synchronisation entre threads. La différence entre un spinlock et un event par exemple, est qu’un spinlock est une construction purement applicative, et ne fait pas référence à un objet du noyau (donc pas de transition user -> kernel). Donc elle est beaucoup plus légère à exécuter.

Les spinlocks dans SQL Server permettent de protéger principalement des listes chaînées de structures, comme les BUFs, ces structures qui décrivent les pages présentes en Buffer Pool. Il existe tout un tas de listes de structures pour les métadatas, le plan cache, les verrous, les FCB, etc… Faire un select name from sys.dm_os_spinlock_stats pour l’exhaustivité.

Ces ressources sont uniques dans tout l’espace d’adresse de SQL Server, et sont accessibles potentiellement par de multiples workers donc il faut que l’on puisse garantir une séquentialisation des accès. Lorsque l’on sait que la ressource ne va être détenue que pendant un temps très court, il peut être plus intéressant de brûler de la CPU dans une boucle et vérifier à chaque tour si la ressource est disponible plutôt que de bloquer et se mettre en attente. Si la ressource est volatile on a de grandes chances de pouvoir la verrouiller au prochain tour. En revanche, si on bloque, on va devoir attendre d’être reschedulé.

A l’intérieur de la boucle, on va en même temps tester une variable et tenter de modifier sa valeur :

Boucle tant que (teste_et_initialise (a,1) != 1)

Dans la plupart des langages, il existe des fonctions qui font ce travail de manière atomique (en garantissant qu’il n’y a qu’un seul thread sur tous les processeurs capable de modifier la valeur), mais en définitive ces fonctions font toutes référence à une instruction du processeur codée en langage assembleur (CMPXCHG , CMPXCHG8B par exemple pour x86). Dans le monde Windows ce sont les fonctions de la famille Interlocked qui font ce travail. Dans le monde linux, il y a des équivalent comme les fonctions type atomic, ou seqlocks en kernel 2.6.

IOCP :

Là c’est ultra-chaud. Je ne vois qu’un seul endroit ou les IO completion ports sont utilisés, c’est sur la gestion des connexions sur chaque CPU node, ou NUMA node.

L’intérêt d’un IOCP est de permettre de synchroniser des threads sur des IO asynchrones tout en n’autorisant qu’un certain nombre à s’exécuter en parallèle. Si on a 8 CPU et qu’on a 150 demandes de connexions simultanées, on va en traiter 8 en même temps mais les autres seront toutes visibles par le scheduler windows et rien ne va l’empêcher de changer le contexte (context switch) des tâches en exécution pour permettre à chacune de disposer d’une même quantité de temps CPU.

Donc comme pour le scheduling coopératif dans SQLOS, il faut limiter le nombre de connexions visibles par Windows au nombre de CPU disponibles, via un IOCP et une propriété de concurrence: on va dire à l’IOCP que seulement 8 connexions peuvent passer en même temps. La première IO qui est terminée émet un paquet de fin de traitement qui est notifié au thread en attente pendant que le suivant peut enchaîner sur une autre IO, etc… On ne conserve ainsi que le nombre optimal de threads exécutables à un instant donné. L’autre avantage est que l’IOCP gère ses propres mécanismes de notification et est plus scalable qu’un fonctionnement à base de SetEvent / WaitForSingleObject.

Or cet objet du noyau n’existe pas sous Linux. Il y a potentiellement epoll qui peut être étudié, mais il y a plusieurs différences dans le fonctionnement de base:

- Un IOCP fonctionne avec des IO asynchrones : on effectue un appel à une fonction sans être bloqué (asynchrone), puis on reçoit une notification que l’opération est terminée plus tard. Alors que sous Linux, l’approche est différente, on attend qu’une donnée soit disponible en lecture sur par exemple une socket, et on lit le contenu sans avoir à attendre puisqu’il est disponible immédiatement.
- Il n’y a pas de notion de concurrence max comme dans un IOCP. Avec epoll il n’y a qu’un seul thread qui travaille à chaque fois. Il faut alors créer de multiples epoll pour arriver au même principe de concurrence.

Une étude comparative récente montre notamment qu’epoll serait plus consommateur en CPU que IOCP, mais qu’en dehors de ça les capacités de traitement sont comparables.

Entrées / sorties (disque):

Là aussi, compliqué. Il y a plusieurs aspects des entrées / sorties qui sont à vérifier:

La durabilité des écritures:

Il y a plusieurs façons de faire. Par exemple sur Sybase ASE ou MySQL (innodb_flush_method), les fichiers de données et journaux de transactions peuvent être ouverts en O_DSYNC ou en O_DIRECT quand le file system le permet. Sur PostgreSQL, la durabilité est assurée via des appels répétés à fsync(). Au fil des versions des optimisations ont été faites pour limiter le nombre d’appels à fsync dans le code mais il reste toujours des workloads où cette approche est impactante.

Or sur Windows l’ouverture du fichier est faite via un équivalent à O_DIRECT en quelque sorte, via deux flags passés lors du CreateFile(). Donc il y aura nécessairement des préconisations quant aux file systems supportés et aux options à positionner pour avoir un équivalent.

Les entrées / sorties asynchrones :

La plupart des entrées / sorties sont asynchrones dans SQL Server.  Il y a deux implémentations des IO asynchrones sur Linux:

- Les POSIX asynchronous IO: dans ce cas, l’IO est vue non bloquante par celui qui l’initie mais dans les faits il clone un nouveau thread qui lui va bloquer à sa place. Donc bon …

- Les Kernel asynchronous IO (ou libaio) : dans ce cas, il s’agit d’une approche plus comparable avec ce que propose Windows. Elle est supportée depuis la 2.6 et a fait l’objet de tests plutôt concluants notamment chez MySQL AB à l’époque, et qui ont conduit à son implémentation dans InnoDB. La contrainte dans ce cas est que le fichier doit être ouvert en O_DIRECT ce qui semblerait donc orienter le choix sur la question de la durabilité.

WriteFileGather / ReadFileScatter :

Lorsque le checkpoint doit écrire des pages modifiées sur disque, il exécute une routine WriteMultiple dans laquelle il va aller récupérer un certain nombre de pages marquées comme dirty dans le Buffer Pool, puis exécute un appel à WriteFileGather() qui va les écrire sur disque. L’avantage de WriteFileGather par rapport à WriteFile est que l’on n’est pas obligé d’avoir à faire des I/O séparées pour des blocks discontigüs en mémoire. SQL 2014 peut envoyer jusqu’à 32 pages dans une seule opération d’écriture avec cette technique, et SQL 2016 jusqu’à 128 (soit 1Mb). Même chose dans l’autre sens avec ReadFileScatter. On n’est pas obligé d’avoir un segment contigü de 64K de mémoire pour placer un prefetch de 8 pages. C’est comme cela que les pages sont remontées du disque dans le Buffer Pool.

Sur Linux, on va utiliser les IO vectorisées (vectored IO) avec readv et writev. Leur fonctionnement est en apparence semblable à leurs cousines win32, elles passent un tableau de buffers à écrire ou lire (iovec sous Linux, FILE_SEGMENT_ELEMENT sous Windows). Actuellement le nombre de buffers discontigus à passer à readv / writev est limité à 1024 ce qui est toujours au-dessus de ce que transmet SQL Server. (IOV_MAX dans limits.h). Une différence réside dans le fait que sur Windows on indique une quantité d’octets à écrire ou lire  alors que sur Linux, on indique un nombre de segments iovec à traiter.

Autre note intéressante, WriteFileGather / ReadFileScatter déclarent une structure Overlapped dans leur signature, donc les IO sont nécessairement asynchrones. Sur Linux, les Kernel asynchronous IO ont été étendues aux IO vectorisées dans un patch qui daterait de la 2.5, donc aio_write et aio_read ont chacune une signature qui inclue un iovec depuis ce patch.

NTFS vs ext4:

Un certain nombre de fonctionnalités sont également liées aux possibilités offertes par NTFS, parmi lesquelles on peut citer:

- Les sparse files AKA Database Snapshots.
- La possibilité de zéro – initialiser (dans le cas des journaux de transactions) ou non ( dans le cas des fichiers de données) les portions de fichiers allouées sur disque.
- La possibilité de réduire un fichier sur disque.

Il y a peut être des pistes à creuser en regardant ce que font truncate / fallocate par exemple. Truncate doit permettre de créer des sparse files et de réduire des fichiers sur ext4. Fallocate doit permettre de faire l’équivalent de SetEndOfFile pour l’initialisation instantanée.

Pour retrouver l’équivalent du cluster size NTFS à 64K, il existe une option bigalloc qui est utilisée lors du mkfs, attention toutefois l’option n’est disponible qu’à partir des noyaux 3.2, et rencontrerait toujours pas mal de problèmes jusqu’en 3.7. Sachant que les noyaux 3.2 rencontrent eux-mêmes pas mal de problèmes , ça risque donc de ne pas être pour tout de suite.

Il est également possible d’utiliser mkfs.ext4 -T largefile pour le formatage, cela permet de diminuer le nombre d’inodes pour les gros fichiers (1 inode pour 1Mb au lieu de 1 inode pour 16K).

Autres points clés :

D’autres points qui peuvent être compliqués à traduire dans le monde Linux:

  • Ulimits ?
  • Integrated security / ACLs
  • Collations système
  • VDI / VSS
  • Intégration avec Perfmon.
  • MSDTC
  • WMI
  • ETW

Synergies avec les autres projets type Ubuntu in Windows:

L’annonce a été faite il y a quelques semaines, Windows 10 inclut déjà en beta la possibilité de démarrer un shell linux et d’interopérer avec les ressources windows (processes, fichiers, etc…). Un cygwin en mieux car intégré sous la forme d’un nouveau sous-système comme win32, POSIX et feu OS/2, qui exécute directement de l’ELF64.

Alors que dans le cas de cygwin, ls.exe était un exécutable win32, ici /bin/ls sera le même /bin/ls que l’on trouve sur Ubuntu.

Il n’y a toutefois pas de synergie à proprement parler avec le portage de SQL Server sur Linux. On peut entrer dans le délire de dire que l’on pourra exécuter sqlservr en ELF64 sur un windows 10, mais ça n’aurait bien évidemment aucun sens.

En tous cas les deux projets vont clairement dans le sens d’un rapprochement entre les 2 mondes. Et chez CapData, où l’on jongle avec différents SGBD sur différentes plateformes, ça ne peut que nous réjouir davantage :)

Conclusion:

Franchement que retenir de tout ça ?

1) Un peu d’auto-critique ne fait pas de mal : à quoi ça sert de spéculer avant que le produit ne soit sorti ? C’est sûr qu’on aura plus de choses à dire quand il sera là. Et il y aura là de quoi quoi faire un article plus consistant, promis juré.

2) Ensuite est-ce qu’on ne fait pas fausse route en partant du principe qu’il faut traduire le comportement de Windows à Linux ? Est-ce qu’ils (les dev) n’ont pas plus intelligemment oublié Windows et imaginé directement en Linux ?

3) Enfin, après ces quelques recherches, je me rends compte que le fossé prétendument abyssal n’est pas si profond que ça. Et qu’avec une solide équipe, de bonnes idées, de l’aide extérieure peut être parmi la communauté des développeurs kernel, et un regard porté sur les choix qu’ont fait les autres (Oracle / PostgreSQL / Sybase / MySQL), on peut croire qu’on va avoir bientôt entre les mains un nouveau petit bijou de développement.

Après tout, n’est-ce pas un retour aux sources de Shiloh (la 7.0), à l’heure où une équipe de 4 brillants architectes (Spiro / Campbell / Berenson / Flessner) avait décidé de tout péter de la 6.5 et de reconstruire sur des cendres ?

L’histoire le dira.

A+

Continuez votre lecture sur le blog :




Cliquer pour partager cet article sur Viadeo
Cliquer sur "CAPTURER" pour sauvegarder cet article dans Evernote Clip to Evernote

Tags: ,

3 Responses to “Pas de la tarte”

  1. dbaffaleuf

    Je viens de tomber sur cet article de Jonathan Corbet (https://lwn.net/Articles/518329/). Le problème qui touche postgreSQL peut potentiellement toucher d’autres SGBD pour peu que ceux-ci utilisent massivement des spinlocks en usermode (c’est le cas pour Sybase ASE).

    Attention donc côté SQL Server, il faudra tenir compte de ce phénomène qui n’est pas sans rappeler les problèmes d’hyperthreading de la génération d’avant Nehalem, cf ce post de Slava de 2005: https://blogs.msdn.microsoft.com/slavao/2005/11/12/be-aware-to-hyper-or-not-to-hyper/

    #345775
  2. Excellent article David !

    #346074
  3. Ce petit article de Bob Dorr qui est repassé côté obscur du dev, et qui précise ce que j’avançais sur la partie scatter / gather = vectored IO, notamment sur la limite des buffers passés à writev et qui serait de l’ordre de 2048 et pas 1024 comme indiqué dans l’article. https://blogs.msdn.microsoft.com/bobsql/2017/01/31/sql-server-on-linux-scattergather-vectored-io/

    #354667

Leave a Reply