# Devoir maison de données distribuées

## Partitionnement

Tableau identifiants-valeurs trié par identifiant I

| I | N |
| :-: |:-: |
| 5 | a |
| 9 | b |
| 22 | h |
| 38 | f |
| 42 | c |
| 51 | g |
| 54 | d |
| 666 | e |

### Question 1 - Partionnement horizontal - round-robin

| Disque | Identifiant | Valeur |
| :----- | :---------: | :----: |
| Disque 0 | 5 | a |
|  | 42 | c |
| Disque 1 | 9 | b |
|  | 51 | g |
| Disque 2 | 22 | h |
|  | 54 | d |
| Disque 3 | 38 | f |
|  | 666 | e |

### Question 2 - Partionnement horizontal - hash par modulo

Nous choisissons un modulo 4

| Disque | Identifiant | Valeur |
| :----- | :---------: | :----: |
| Disque 0 |  |  |
| Disque 1 | 5 | a |
|  | 9 | b |
| Disque 2 | 22 | h |
|  | 38 | f |
|  | 42 | c |
|  | 54 | d |
|  | 666 | e |
| Disque 3 | 51 | g |

### Question 3 - Partionnement horizontal - intervalles

| Disque | intervalle | Identifiant | Valeur |
| :----- | :--------- | :---------: | :----: |
| Disque 0 | [0;10[ | 5 | a |
| | | 9 | b |
| Disque 1 | [10;40[ | 22 | h |
| | | 38 | f |
| Disque 2 | [40;52[ | 42 | c |
| | | 51 | g |
| Disque 3 | [52;1000[ | 54 | d |
| | | 666 | e |

### Question 4 - Jeu de données

Mail au prof

### Question 5 - Recherche par identifiant - Tourniquet

Si le partionnement est par tourniquet, il est potentiellement nécessaire d'activer tous les disques pour trouver une valeur de I précise.
Ceci car aucune opération préalable ne permet de déterminer quel disque contient ladite valeur.
Il faut donc faire une recherche séquentielle jusqu'à atteindre l'identifiant voulu.

### Question 6 - Recherche par identifiant - Hash

Si le partionnement est par hachage, un seul disque doit s'activer pour trouver une valeur de I précise.
Il suffit pour cela de recalculer le hash, qui nous indiquera directement le disque à interroger.

### Question 7 - Type de recherche activant tous les disques

Dans le cas d'une recherche sur la valeur et non sur la clé, il faut activer pratiquement tous les disques.
Le hachage ne permet pas de calculer l'emplacement de la clé.


## Jointure

### Question 1 - Algorithme PNL

1. Envoi des données de la partition E1 (disque D1) vers le disque D3
2. Envoi des données de la partition E2 (disque D1) vers le disque D3
3. Concaténation de E1 et E2 sur le disque D3 - Table E3
4. Jointure de E3 et F1 sur le disque D3 - Table EF1
5. Envoi des données de la partition E1 (disque D1) vers le disque D4
6. Envoi des données de la partition E2 (disque D1) vers le disque D4
7. Concaténation de E1 et E2 sur le disque D4 - Table E4
8. Jointure de E4 et F1 sur le disque D3 - Table EF2
9. Concaténation des tables EF1 et EF2

### Question 2 - Gains et pertes

Les gains de temps se font au niveau des jointures du fait d'opérer sur des fragments  plutôt que sur l'ensemble complet (produits cartésiens plus petits), ainsi que sur le fait que plusieurs jointures sont réalisées en même temps.

Les pertes de temps se font au niveau de la réplication des données, ainsi que sur les concaténations.


## MapReduce

### Question 1 - Résultat de la phase Map

| Clé | Valeur |
| :-- | :----: |
| (après, fait) | 1 |
| (après, avoir) | 1 |
| (après, fait) | 1 |
| (avoir, fait) | 1 |
| (avoir, fait) | 1 |

### Question 2 - Résultat de la phase Shuffle

| Clé | Valeur |
| :-- | :----: |
| (après, avoir) | (1) |
| (après, fait) | (1,1) |
| (avoir, fait) | (1,1) |

### Question 3 - Résultat de la phase Reduce

| Clé | Valeur |
| :-- | :----: |
| (après, avoir) | 1 |
| (après, fait) | 2 |
| (avoir, fait) | 2 |

### Question 4 - Explication

Ce programme renvoie, pour chaque ligne, tous les couples de mots disctincts possibles ainsi que le nombre d'occurences de chacun de ces couples.

## NoSQL

### Question 1 - Pig

Pig est une plateforme haut niveau pour la création de programme MapReduce qui offre une syntaxe proche du SQL.

### Question 2 - Spark

Spark possède une syntaxe de type lambda functions et permet d'effectuer des opérations de type MapReduce, sans être limité à cela.

### Question 3 - Type de système

Les données sont très structurées et il y a une nécessité de cohérence forte.
Une solution NoSQL ne semble donc pas adapté, et donc partir sur un SGBD relationnel classique.
Le jeu de données n'est pas si grand, une solution de type Oracle suffit amplement.
Si les performances sont primordiales, il existe la possibilité des "in-memory databases", permettant de conserver les propriétés ACID tout en améliorant drastiquement les temps d'accès.