slides-stockage-physique-fr.pdf

Stockage physique des données dans un SGBD Contenu du chapitre: -20 20 20 19 Stockage : la mémoire au niveau du hardware Stockage physique (Rappel) Lectures vs Écritures: architecture de stockage B.Groz 1  T...

Stockage physique des données dans un SGBD Contenu du chapitre: -20 20 20 19 Stockage : la mémoire au niveau du hardware Stockage physique (Rappel) Lectures vs Écritures: architecture de stockage B.Groz 1  Table des matières 0 01 9-202 2 Stockage physique des données dans un SGBD Stockage : la mémoire au niveau du hardware Stockage physique (Rappel) Lectures vs Écritures: architecture de stockage B.Groz 2  New DB technologies and trends Data storage and processing evolutions: New hardware (FPGA, GPGPU, SSD, NVRAM) In-memory DB/ Column storage NoSQL: (shared nothing) massively parallel architecture (Map/Reduce, key/value) Trends emphasize supporting both analytical (OLAP, mining) and prediction queries (statistical ML) ACID in distributed data processing trust management – so far, more of an issue for transactions rather than storage/analysis (blockchain) integrating new (external) types of data (text, feeds, images, video...) building data summaries (data too large to be stored): sampling, etc. real-time DW B.Groz 3  Hardware: data storage The hard drive Created in 1956 (IBM). Multiple disks (platters) spinning rapidly together (thousands rpm/min). Ferromagnetic. Multiple tracks per platter. 1 head per platter, on air cushion. u 100€ a few TB 100gr. Main storage device (secondary storage) since 1960. The support for which DBMS were devised. B.Groz 4  Hardware: storage Memory hierarchy: faster access CPU registers volatile CPU Caches Main memory Flash Hard disk tape cheaper, higher storage capacity On early computers, CPU frequency u memory bus and memory access. But CPU became much faster than memory. B.Groz 5  Hardware: storage Memory hierarchy: faster access CPU registers volatile CPU Caches SRAM: 500$/GB Main memory DRAM: 5$/GB NVRAM NVRAM: 1$/GB Flash Flash:.4$/GB Hard disk tape cheaper, higher storage capacity On early computers, CPU frequency u memory bus and memory access. But CPU became much faster than memory. B.Groz 6  Latency numbers every programmer should know (J.Dean) Latency numbers (2012) L1 cache reference......................... 0.5 ns Branch mispredict............................ 5 ns L2 cache reference........................... 7 ns Mutex lock/unlock........................... 25 ns Main memory reference...................... 100 ns Compress 1K bytes with Zippy............. 3,000 ns = 3 µs Send 2K bytes over 1 Gbps network....... 20,000 ns = 20 µs SSD random read........................ 150,000 ns = 150 µs Read 1 MB sequentially from memory..... 250,000 ns = 250 µs Round trip within same datacenter...... 500,000 ns = 0.5 ms Read 1 MB sequentially from SSD*..... 1,000,000 ns = 1 ms Disk seek........................... 10,000,000 ns = 10 ms Read 1 MB sequentially from disk.... 20,000,000 ns = 20 ms Send packet CA->Netherlands->CA.... 150,000,000 ns = 150 ms 2019: for a 4kB block: Latency numbers (2019) Fast NVMe (Optane)........................... 7 µs Fast NVMe (Z-SSD)........................... 12 µs Round trip TCP packet on 10Gb Ethernet... 20-50 µs NVMe Flash SSD.............................. 80 µs B.Groz 7  Throughput numbers on key-value stores [https://www.usenix.org/system/files/fast19-kourtis.pdf] B.Groz 8  Table des matières 0 01 9-202 2 Stockage physique des données dans un SGBD Stockage : la mémoire au niveau du hardware Stockage physique (Rappel) Lectures vs Écritures: architecture de stockage B.Groz 9  3 niveaux de conception Conception Description orientée-utilisateur, indépendante Conceptuelle de l’implémentation E-R, UML Conception Description logique, independante du SGBD Logique Modèle relationnel: schéma des tables Conception Implémentation des structures dans la BD Physique Vues matérialisées, partitions, index B.Groz 10  Accès aux données Données de base R1 R2 MV1 MV2 Vues Matérialisées o n Chemin d’accès logique Partitions Chemin B+ -tree R-tree k-d tree Index d’accès bitmap Z-curve... physique : schéma logique (architecture ANSI SPARC) B.Groz : schéma physique(architecture ANSI SPARC) 11  Stockage physique dans le SGBD (rappel) adresse physique de l’enregistrement fournie par ROWID enregistrements rassemblés en pages=blocs. opérations de Lecture/Écriture imposent de charger la page correspondante. les SGBD efficaces cherchent à minimiser les chargements de pages. Si taille de bloc importante: plus d’enregistrement sont accessible dans une page, mais on peut charger moins de page. B.Groz 12  Stockage Physique: Oracle (1) logical physical E-R diagram of logical storage storage structures [Oracle Database Concepts] B.Groz 13  Stockage Physique: Oracle (2) 1 KB 1 KB 1 KB 1 KB 1 KB 1 KB 8 KB 1 KB 1 KB Bloc de données Oracle Blocs systèmes B.Groz 14  Stockage Physique: blocs PostgreSQL ctid ' row pointers Page Header ItemId ItemId ItemId 8kB Tuple Tuple Tuple Special Page Header General info about the page, including free space pointers. 24 bytes Item Ids Array of (offset,length) pairs pointing to the actual items. 4b/item Free space The unallocated space. New items are allocated from the end Tuples The actual items themselves (row for tables, entry for indexs) Special space Empty in ordinary tables. Used for indexes B.Groz 15  Stockage Physique: en-tête des blocs PostgreSQL typedef struct PageHeaderData { PageXLogRecPtr pd_lsn; uint16 pd_checksum; uint16 pd_flags; LocationIndex pd_lower; LocationIndex pd_upper; LocationIndex pd_special; uint16 pd_pagesize_version; TransactionId pd_prune_xid; ItemIdData pd_linp[FLEXIBLE_ARRAY_MEMBER]; } PageHeaderData; [https://github.com/postgres/postgres/blob/master/src/include/storage/bufpage.h] (commentaires adaptés) CREATE EXTENSION pageinspect; SELECT * FROM page_header(get_raw_page('t',0)); -- page 0 from table t lsn | checksum | flags | lower | upper | special | pagesize | version | prune_xid - - - - - - - - - - -+ - - - - - - - - - -+ - - - - - - -+ - - - - - - -+ - - - - - - -+ - - - - - - - - -+ - - - - - - - - - -+ - - - - - - - - -+ - - - - - - - - - - 6/ D4930A98 | 0 | 0 | 32 | 8128 | 8192 | 8192 | 4 | 0 B.Groz 16  Stockage Physique: tuple PostgreSQL Field Type Length Description t_xmin TransactionId 4 bytes insert XID stamp t_xmax TransactionId 4 bytes delete XID stamp t_cid CommandId 4 bytes insert and/or delete CID stamp (overlays with t_xvac) t_xvac TransactionId 4 bytes XID for VACUUM operation moving a row ver- sion t_ctid ItemPointerData 6 bytes current TID of this or newer row version t_infomask2 uint16 2 bytes number of attributes, plus various flag bits t_infomask uint16 2 bytes various flag bits t_hoff uint8 1 byte offset to user data [https://github.com/postgres/postgres/blob/master/src/include/access/htup_details.h] (pour plus de détails) SELECT * FROM heap_page_items(get_raw_page('t',0)); t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_data - - - - - - -+ - - - - - - - -+ - - - - - - - - - -+ - - - - - - - -+ - - - - - - - - - - - - -+ - - - - - - - - - - - -+ - - - - - - - -+ - - - - - - - - - - - 5856 | 0 | 0 | (0 ,1) | 2 | 2304 | 24 | \ x01000... 5857 | 0 | 0 | (0 ,2) | 2 | 2304 | 24 | \ x02000... B.Groz 17  Bibliographie Oracle Database Concepts https://docs.oracle.com/database/121/CNCPT/logical.htm https://en.wikibooks.org/wiki/Oracle_and_DB2,_Comparison_and_ Compatibility/Storage_Model/Physical_Storage/Summary ftp: //ftp.software.ibm.com/software/data/db2/9/labchats/20110331-slides.pdf (a bit outdated: 2011... ) http://www.postgresql.org/docs/9.4/static/storage-page-layout.html https://www.postgresql.org/docs/11/storage-page-layout.html B.Groz 18  Table des matières 0 01 9-202 2 Stockage physique des données dans un SGBD Stockage : la mémoire au niveau du hardware Stockage physique (Rappel) Lectures vs Écritures: architecture de stockage B.Groz 19  Gestion des écritures dans les SGBD opération d’écriture RAM Buffer de la BD Buffer des logs Bloci wi wi+1 Blocj écritures séquentielle, écritures aléatoire, ±en temps réel asynchrone Logs=journal Base de donnée Bloci HDD B.Groz 20  Types d’architectures (MVCC) en terme de tables O2N : oldest-to-newest N2O : newest-to-oldest http: // www. vldb. org/ pvldb/ vol10/ p781-Wu. pdf (VLDB’17) B.Groz 21  Types d’architectures update-in-place storage: la plupart des BD relationnelles. Limites: historisation conduit à fragmenter. Verrous sur pages durant m-à-j. Stratégie souvent associée au B-tree. Optimise lectures (u1 seek per read/1 per scan if unfragmented). Mettre à jour index est plus lent. log-structured storage: m-à-j ajoutées dans un log (pas de “main”). Écriture +rapide que B-tree (et sans verrou). Mais scans +lent: doit lire tous les logs. Version populaire: LSM-tree (Log-Structured Merge tree). delta with main store: main store optimisé en lecture, updates dans un write-optimized buffer (SAP Hana/Sans Souci, et autres column stores). Buffer fusionné de temps en temps. ,→ Idée du log-structured storage: plutôt qu’écrire une page entière à chaque m-à-j, les différer pour traiter en paquet. Idée de différer les écritures commune avec l’approche delta. B.Groz 22  LSM-tree Famille de structures optimisées pour le débit en écriture ( write-throughput)... comme tout log-structured storage: LSM-tree consiste en 2 niveaux ou plus C0 , C1 (, C2... , Ck ). C0 in-memory: tree, hash table... les autres (C1 ,... ) sont B-trees, stockés sur disque/mémoire +lente. les m-à-j écrites sont seulement dans C0 ∀i quant Ci est plein, on le fusionne avec Ci+1 (Ci est vidé) ,→ ∀i, les versions dans Ci sont +récentes que Ci+1 ,→ au plus r versions des tuples co-existent. ,→ une lecture parcourt les niveaux C0 , C1... jusquà trouver le tuple.... mais il reste à préciser la définition de “plein”: Version d’origine: [O’Neill et al. 1996] recommende d’utiliser progression géometrique: |Ci+1 | = r × |Ci | ,→ nb total de clés uniques: N = O(r k ). résultats récents proposent autres solutions apparemment +efficaces B.Groz 23  LSM-tree: intérêt En différant les écritures (dans le niveau suivant), le LSM va accélérer les écritures (par rapport au B-tree): Avantages: 4 rendre les écritures plus séquentielles (plus efficaces) 4 réduire la fragmentation (requêtes d’intervalles plus efficaces) Faiblessess: 8 accéder à une valeur peut être plus long B.Groz 24  Bibliographie Rappels simples sur le stockage dans les SGBDs - http: // sys. bdpedia. fr/ MVCC storage - http: // www. vldb. org/ pvldb/ vol10/ p781-Wu. pdf LSM trees - http: // www. vldb. org/ pvldb/ vol10/ p1526-bocksrocker. pdf - http: // www. eecs. harvard. edu/ ~margo/ cs165/ papers/ gp-lsm. pdf - https: // www. quora. com/ How-does-the-Log-Structured-Merge-Tree-work B.Groz 25