Data blocs

• Un data block est l’unité de gestion de l’espace disque

• Il est la plus petite unité d’E/S
• Géré indépendamment de son contenu (table, index …)
Tuples (row data)
Entête Espace libre (PCTFREE, PCTUSED)
Répertoire de tuples (row directory)
Répertoire de table (table directory)
5 6
PCTFREE et PCTUSED Utilisation de PCTFREE et PCTUSED
• Paramètre PCTFREE PCTFREE=20, PCTUSED=40
– Pourcentage d’un bloc réservé aux mises à jour futures
– Quand PCTFREE est atteint : le bloc est retiré de la freelist (liste des blocs dans
lesquels il est possible d’insérer de nouvelles données)
INSERTION (Max 80% du bloc)
• Paramètre PCTUSED
– Pourcentage d’occupation minimum d’un bloc en dessous duquel des données
peuvent à nouveau être insérées
– Quand PCTUSED est atteint : le bloc est remis dans la freelist
– 40%, par défaut
Pourquoi si faible ? La taille Mise à jour
moyenne d’un tuple suffirait…
Si Oracle remet les bloc dans la liste des blocs libre alors que ces blocs disposent de
peu d’espace libre, le coût des insertions nombreuses (de plusieurs tuples) sera très
élevé (jusqu’à 1 E/S par tuple inséré)
SUPPRESSION
• Réglage
– Par le DBA (paramètre du CREATE TABLE)
– Par l’ASS = Automatic Segment Space Management (>Oracle 8i) Si PCTUSED<40, alors des insertions peuvent à
7
nouveau être effectuées 8
2
Stockage et indexation dans
Mise en œuvre dans les SGBD
les gestionnaires de données traditionnels :
Relationnels
l’exemple d’Oracle
et NoSQL
Support partiellement emprunté à Pascale Borla Salamet – Oracle France
1 2
Organisation des données sur disque
Logique Physique
Base de données Database
Récipient logique pour
regrouper des objets applicatifs Tablespace Datafiles
liés et administrés ensemble
Lieu de stockage d’une Segment
structure :
Table, index, partition de table …
Granule d’allocation = Extent
Ensemble de blocs contigus
Granule d’I/O Block Bloc OS
Idéalement multiple d’un Bloc OS
3 4
1
 13 14
Partitionnement des tables (1)
• 3 méthodes de partitionnement de base
Exemple
CREATE TABLE sales_hash
(salesman_id NUMBER(5),
salesman_name VARCHAR2(30),
sales_amount NUMBER(10),
week_no NUMBER(2))
• Et de nombreuses extensions PARTITION BY HASH(salesman_id)
PARTITIONS 4
– Reference partitioning STORE IN (ts1, ts2, ts3, ts4);
– Virtual column partitioning (expression sur clé)
tablespaces
– System partitioning (App dependent)
15 16
4
Cluster d’index = index plaçant (multi-tables) de type Arbre-B+
Cluster de hash = index plaçant (multi-tables) de type hachage
• Table index-organized = index plaçant
• les tuples entiers sont stockés dans les feuilles plutôt que leur Rowid
9 10
11 12
3
 Objective: Enabling The Real-Time World Ce que change l’optique grande mémoire
Authorization,
Online Charging,
Market Data,
Market Events, Real-Time Analytics -
eCommerce,
Personalization, • Disparition du coût d’E/S disque
Order Matching, Interactive Dashboard Real-Time Ad
Location-Based
Services Trading Data Mart, Scorecard Serving – La localité des données n’est plus requise  modèles basés
pointeurs
– Plus de duplication de valeurs  index plus petits, plus
simples
– Index primaires/secondaires ont des performances voisines
Real-Time Applications  tout indexer
Instantly Responsive / Highly Scalable / Always-On
– L’optimisation de requêtes devient très simple
– Les transactions sont plus rapides et bloquent les données
Mainstream 64-bit Fast Large Capacity
Processors Networks RAM moins longtemps
• La reprise après panne devient un goulot
Key Enabling Technology
d’étranglement
21 Copyright © 2012, Oracle and/or its affiliates. All rights reserved.
– Restaurer en priorité les données en fonction des demandes
d’accès en attente 22
Impact sur les méthodes d'accès et de What is Oracle TimesTen In-Memory Database
stockage Memory Optimized Relational Database
Modèle pointer-based Client-Server
Domaine 1 Application
• Extremely fast
Index TimesTen
B-Tree de pointeurs pt Client Lib – Entire database in memory
lg1 valeur 1
Table R
– Microsecond response time
Client/ Direct-Linked
pt
lg2 valeur 2
Server Application
• Deployed in the middle tier, close to
•
the application (shared libraries)
• TimesTen Libraries
•
•
• • •
•

•
pt
lg5 valeur 5 JDBC / ODBC / ADO.NET / OCI / PLSQL
• Compatible with Oracle Database
•
– Standard SQL and PL/SQL, Datatypes
Table S Domaine 2
Fast – JDBC, ODBC, ODP.NET, OCI, Pro*C
Checkpoint
data
• Persistent and Recoverable
Files
pt access
lg3 valeur 3
•
• • – Transactional logging and checkpointing
 •
lg4

Transaction
Log Files • Easy to use and deploy
valeur 4
Memory-Resident
Database
Identifiez les sources d’optimisation ! 24 Copyright © 2012, Oracle and/or its affiliates. All rights reserved.
23
6
Partitionnement des tables (2) Partitionnement des index
• Possibilité de combiner les modes (partitionnement Index partitionné local Index partitionné global
composite)
• Index global non partitionné sur une table partitionnée
CREATE TABLE sales_composite
(salesman_id NUMBER(5),
salesman_name VARCHAR2(30),
…
PARTITION BY RANGE(sales_date)
SUBPARTITION BY HASH(salesman_id)
SUBPARTITION TEMPLATE(
SUBPARTITION sp1 TABLESPACE ts1,
SUBPARTITION sp2 TABLESPACE ts2, …
PARTITION sales_jan2000 VALUES LESS THAN(TO_DATE('02/01/2000','DD/MM/YYYY'))
PARTITION sales_feb2000 VALUES LESS THAN(TO_DATE('03/01/2000','DD/MM/YYYY'))
… Quelle solution pour quelles applications (OLTP/OLAP) ?
17 18
Intérêts du partitionnement
• Bien sûr, accélérer les requêtes grâce au parallélisme intra-
Mise en œuvre dans les SGBD
opérateur ou inter-requêtes In-Memory (IMDS) :
• Mais quels bénéfices en termes d’administration ?
– Sauvegarde/restauration par partition (en cas de panne, les partitions
les plus ‘chaudes’ sont restaurées en premier pour minimizer le
downtime
l’exemple de TimesTen
– Suppression de données obsolètes par partition (si organisées par
date)
– Les partitions froides peuvent être compressées et placées sur des autres exemples d’IMDS :
supports low-cost
– Les partitions ‘chaudes’ et ‘read-only’ peuvent être placées sur SSD
Hekaton (SQL Server In-Memory OLTP),
Apache Ignite,
SQLite,
SAP HANA, …
19 20
5
 Cassandra: modèle de données
• Column et Row
• CASSANDRA (Facebook  Apache) – Column : paire (Name: byte[], Value: byte[]) associé à un timestamp utilisé pour
– Fortement inspiré de BigTable (Google) pour le stockage et de la synchronisation
DynamoDB (Amazon) pour la distribution • Name, Value : chaînes d’octets sans limite de taille
– Utilisé par Apple, eBay, Netflix, Spotify … – Row : <clé primaire: byte[], liste de columns>
• Column-Store hautement distribué, ‘scalable’ et disponible Column family
– Développé initialement pour gérer les Inbox Facebook
– Milliards d’écritures par jour  index de type OLTP/NoSQL
• Basé sur
– Architecture Pair-à-Pair (P2P)
– Distribution = DHT (Distributed Hash Table) • Super-column
– Réplication : Eventual consistency, pas de Single Point of Failure – Column dans laquelle la valeur est elle-même une liste de colonnes
– Langage CQL (SQL restreint, sans join) • Column family
– Similaire à une table (i.e., ensemble de tuples)
• Pas d’objectif de normalisation, donc pas d’impératif de Join
29 30
Modèle de données Cassandra Modélisation NoSQL vs Relationnelle
• Données regroupées dans un • Données normalisées
Column  Attribut même document / Row – Evite la redondance
– Maximise la localité – Facilite le maintien de la
Super Column 
– Facilite la réplication cohérence
Attribut structuré
– Minimise les cas de jointure
Row  Tuple 
Document
Column Family
 Table
Keyspace
 Database
Cluster
 grappe de serveurs
organisée en DHT
31 32
8
In-Memory Database Cache In-Memory Database Caching
Flexible Cache Group Configurations Data Synchronization  voir cours sur les transactions
Application
Transactions Cache Groups
• Cache Group describes the data in the Oracle
Reads/Write
transactions Read-Write caching
database to cache Reads/Write
transactions
Reads/Write • Transactions committed in TimesTen
transactions
• Collection of related tables Application cache
– All or subset of rows and columns Application Application
• Parallel write-through of committed
– Defined via SQL clause transactions to Oracle Database
CREATE CACHE GROUP name
FROM owner.tab1 (col1, col2), Read-only caching
owner.tab2 (col1, col4)
… • Transactions committed in Oracle
Automatic
WHERE <predicate>
Data
Database
Automatic Data
• Cache tables are regular database tables in Synchronization • Multi-stream refresh of committed
Synchronization TimesTen transactions to TimesTen
– Joins/search, insert/update/delete
25 Copyright © 2012, Oracle and/or its affiliates. All rights reserved. 26 Copyright © 2012, Oracle and/or its affiliates. All rights reserved.
Transactions Response Time
Transactions Response Time
Response Time in Microseconds

12,000
Oracle
10114
Mise en œuvre
10,000 Oracle + TimesTen
8,000
dans les systèmes NoSQL
6487
6104 5836
6,000
4,000
1848 1850 2105
2,000
168 44 65 86 201 128 100
0
d a a t d r n
w at at es w ib
e
tio
lF D D D lF cr ca
al es
s
as
e
ew al bs
C N C Lo
et
e cc tB ct rt Su at
e
el
A ec le se at
e
ec
t l
Se In pd
D l Se pd U
Se U
27 Copyright © 2012, Oracle and/or its affiliates. All rights reserved.
28
7
 Distribution / partitionnement = DHT Distribution / partitionnement = DHT
• L’espace de clés géré par un nœud est déterminé par la
fonction de hachage (i.e., aléatoire)
• Possibilité d’allouer plusieurs emplacements (tokens) dans la
DHT au même nœud physique pour mieux distribuer la charge
(paramètre num_token du fichier de configuration)
MD5 hashing
L’administrateur peut choisir la position d’un nœud dans le ring ou laisser
Cassandra le faire
37 38
Mise à jour des index locaux Mise à jour des index locaux
Index B-Tree en RAM et log séquentiel sur disque
• Un index local par nœud (B-Tree)
• Objectif = supporter des ‘milliards’ de modifications
par jour MemTable
• Solution
– pas de mise à jour en place sur disque pour éviter les I/O random
– I/O séquentielle  50 fois plus rapide qu’I/O random
– Log-Structured Merge-Tree (également utilisé dans BigTable, Hbase,
MongoDB …)
CommitLog
39 40
10
CQL: Cassandra Query Language Indexation des données
• Partitionnement des rows entre les noeuds d’une DHT par hachage de
la clé primaire
– Clé primaire mono-column ou multi-column
• Chaque noeud maintient un index local trié sur les rows qu’il stocke
– Possibilité de trier sur plusieurs columns mais l’ordre à son importance (B-Tree)
– Les requêtes CQL doivent respecter cet ordre
• Ex: Create Table … Primary key ((A), B, C) with clustering order (B,C)
• Select … Where A=‘xx’ and B > ‘yy’ and C < ‘zz’ est possible
• Select … Where A=‘xx’ and C < ‘zz’ est impossible
• Le choix de la clé primaire est guidé par le type de requête à optimiser
– Distribuer les données uniformément sur les noeuds
– Minimiser le nombre de partitions à lire
– Prendre en compte le ratio entre requêtes de Select et Update
33 34
Exemple Exercice
Primary key ((album_title, year), number)
• Film(Titre, Réalisateur, DateSortie, Genre, Descriptif)
Partition key Clustering
column
On veut répondre à des requêtes point sur le Genre et range sur
la Date de sortie de films et récupérer le Titre de ces films.
Comment doit-on constituer la primary key de la table ?
1. Primary key ((Genre, DateSortie), Titre)
2. Primary key ((Genre), DateSortie, Titre)
3. Primary key ((DateSortie), Genre)
4. Primary key ((Genre), DateSortie)
5. Primary key ((Titre, Genre), DateSortie)
6. Primary key ((Titre), Genre, DateSortie)
7. Primary key ((Genre), Titre, DateSortie)
35 Primary_key ((Partition key), clustering key) 36
9
 Lecture dans l’index local (2) Fusion des index locaux (1)
Fusion des SSTables quand leur nb devient trop grand.
Fusion par Sort-merge d’index triés  I/O séquentielles
… …
00001001000110 00001001000110 00001001000110
Bloom filter
45 46
Quiz Cassandra Impact sur la modélisation de la BD
• Exemple d’une application de Vidéos
• Dans une structure de partitionnement, quelles opérations ne
• Point de départ = application workflow (plutôt que
sollicitent qu’un seul serveur ?
schéma conceptuel)
• Comment l’administrateur peut-il influencer la qualité du
partitionnement ?
• La clé de partitionnement est-elle toujours discriminante (i.e.,
unique) ?
• Peut-on facilement changer cette clé de partitionnement ?
• La clé primaire est-elle toujours discriminante (i.e., unique) ?
47 48
12
Mise à jour des index locaux (2) Mise à jour des index locaux (2)
L’index est flushé par morceau quand la RAM est saturée On continue à insérer …
SSTable = B-Tree SSTable
41 42
Mise à jour des index locaux (3) Mise à jour des index locaux (3)
Encore et encore … Ajout d’un Bloom Filter / SSTable pour minimiser le nombre de sous-index à tester
… …
00001001000110 00001001000110 00001001000110
Bloom filter
43 44
11
 Architecture MongoDB Partionnement par ‘intervalle’
• Fragment = sous-ensemble d’une collection de documents stocké sur un
nœud
• 1 fragment = 1 feuille du B-Tree
• Quand la feuille de B-Tree éclate, un nouveau fragment (chunk) est créé
et affecté au nœud le moins chargé (sharding)
Source Philippe Rigaux
53 54
MongoDB
• Les nœuds de stockage sont répliqués (voir cours sur la réplication)
• Un nœud ‘configurateur’ (également répliqué) stocke le B-Tree (hors • Moteur analytique distribué et temps-réel
feuilles)
• Les nœuds ‘routeur’ font des requêtes (lecture/écriture) sur le B-Tree pour – Architecture en cluster
router les requêtes des clients – Index découpés en shards, chaque fragment d’index
pouvant être répliqué
• Open source
• Supporte des requêtes ‘full-text’ dans des documents
• Basé sur le moteur Lucene (Apache) pour l’indexation
et la recherche de documents
– Utilisé par LinkedIn, Twitter et beaucoup d’autres
55 56
14
Identification des requêtes Création des tables
Pourquoi yyyymmdd plutôt que added_date ?
49 50
Impact de la dénormalisation MongoDB
• Document Store open source
• Documents au format JSON, regroupés en Collections,
regroupées en Databases
• Des index primaires et secondaires classiques, mono ou multi-
attributs, peuvent être créés sur chaque collection
• Quand MongoDB est déployé sur un cluster de machines, une
collection peut être distribuée sur ce cluster par un mécanisme
de sharding
– Tous les documents de la collection sont alors stockées dans un index (B-Tree)
– Par défaut, la clé du B-Tree est l’id du document mais il est possible de définir
une clé quelconque, mono ou multi-attributs (shard key)
– Le B-Tree sert à accélérer les recherches et à partitionner les données entre les
nœuds d’un cluster
51 52
13
 Score d’un document : tf-idf indexation
• tf (term frequency) = nombre d’occurrences d’un terme t dans • B-tree triant tous les termes de tous les documents indexés
un document d, noté nt,d • Récupération des termes de la requête dans le B-Tree
– Qualifie l’importance du terme dans le document
• Parcours séquentiel en parallèle des listes inversées de ces
– 𝑑4 : Spider Cochon, Spider Cochon, il peut marcher au plafond
termes pour calculer le score global de chaque document vis-à-
– n‘Cochon’, d4 = 2
vis de la requête
• Idf (inverse document frequency) = rareté du terme dans
l’ensemble des documents
Index B-Tree terme
– Le log module la très grande taille habituelle de D
• tf-idf : poids d’un terme t dans un document d  maximal pour les termes
peu fréquents apparaissant beaucoup dans un document particulier
61 62
Why embedding Data Management techniques?
Edge Computing : manage data locally instead
of sending raw data to servers
smart secure devices
devices Secure devices on which
Mise en œuvre a GB flash chip
is superposed
dans les SGBD embarqués
Or embed data management techniques directly
in applications
63 64
16
Exemples de requêtes full-text Les étapes de l’indexation
• GET /bookdb_index/book/_search?q=guide
• Tokenization
– Cherche tous les documents contenant le mot ‘guide’
– découpage du texte en “mots”
• GET /bookdb_index/book/_search?q=title:guide
– Cherche tous les documents contenant le mot ‘guide’ dans le champ ‘title’ • Normalisation
• Requête booléenne (« must » = AND, « should »=OR, « must_not = NOT) – majuscules ? acronymes ? apostrophes ? accents ?
– Exemple : Windows et window, U.S.A vs USA, l’étudiant vs les étudiants.
• Stemming (“racinisation”), lemmatization
– Prendre la racine des mots pour éviter le biais des variations (étudier,
étudiant, étude, etc.)
• Stop words, quels mots garder ?
– Suppression des mots très courants peu informatifs (le, un à, de).
• Indexation
– Indexer les mots résultats des étapes précédentes dans une structure
permettant de retrouver rapidement les documents ayant le ‘meilleur
• Wilcards, fuzzy queries, etc score’ pour une requête textuelle donnée
57 58
Exemple Rappels sur la recherche textuelle
Ensemble de (petits) documents à indexer : Faux positifs : documents non pertinents inclus dans le résultat
𝑑1 : Le loup est dans la bergerie. Faux négatifs : documents pertinents non inclus dans le résultat
𝑑2 : Le loup et le trois petits cochons 2 indicateurs de qualité : Précision et Recall
𝑑3 : Les moutons sont dans la bergerie.
𝑑4 : Spider Cochon, Spider Cochon, il peut marcher au plafond.
𝑑5 : Un loup a mangé un mouton, les autres loups sont restés dans la bergerie.
𝑑6 : Il y a trois moutons dans le pré, et un mouton dans la gueule du loup.
𝑑7 : Le cochon est à 12 le Kg, le mouton à 10 E/Kg
𝑑8 : Les trois petits loups et le grand méchant cochon
Résultat possible :
Source : Philippe Rigaux 59 60
15
 PBFilter Indexing Scheme PBFilter : Bloom Filter Summaries
An optimal scenario for Flash and RAM
 To organize the complete database as
a set of sequential data structures…
 Records stored sequentially in a
Record Area (RA)
 Updates = deletion followed by
insertion of the new record value
 Deletion registered in a Delete Area (DA)
 Queries are compensated by removing
deleted records afterwards
 Only sequential I/O !!
But how to maintain acceptable query performance without • Each page is summarized by a Bloom filter
breaking the sequential organization? • BF are read and written in sequential order
• Only the relevant pages are accessed !
69 70
18
• SGBDR open-source • Key-Value Store open-source
• Se présente comme une librairie, pas • Se présente comme une librairie SQLite XML doc mgr
comme un serveur distinct (comme SQLite)
– Code footprint inférieure à 500KB – Code footprint inférieure à 350KB
– Consommation RAM dépend des operations – Ne supporte que des requêtes clé-valeur
et de la taille de la BD et ne peut être bornée – Consommation RAM : min = 1MB mais difficile
de façon certaine à borner
– Supporte une grande partie de SQL2 (SQL – Type d’index : B-Tree, hachage
text compile en bytecode) – Transactions full ACID
– Type d’index : B-Tree uniquement – Pas de contrôle d’accès (à faire dans l’App)
– Transactions ACI D
• Utilisé par
– Pas de contrôle d’accès (à faire dans l’App)
– OpenLDAP, Subversion, Bitcoin core,
• Utilisé par SendMail, …
– Firefox, Chrome, Opera
– Smartphones Android
– Airbus, …
65 66
PlugDB Embedded Data management challenge
A combination of hardware constraints (wrt. data mgt)
• SGBD column-store au dessus d’un core relationnel
• Microcontroller constraints
• Spécialement étudié pour être embarqué sur microcontrôleur o Tiny RAM
– Code footprint inférieure à 350KB • Stable Storage constraints (NAND Flash)
– Consommation RAM bornable (min 128KB) o erase-before-rewrite, limited erase cycles, FTL unpredictability, cost of
– Requêtes Select/Join/Project MCU random (re)writes
– Type d’index : bloom-filter

BUS
Queries + tiny RAM
– Transactions full ACID o A vicious circle
– Contrôle d’accès RBAC & LBAC NAND
FLASH
Known
• Développé par Inria-UVSQ optimizations
Massive
Indexing
consume RAM
• Transfert technologique vers La Poste
– Coffre-fort de données personnelles
– PlugDB = Trusted Computed Base Massive fine-grain
sécurisée par hardware random writes in Flash
67
17