45
Usando Map/Reduce e o Aggregation Framework para análise e modelagem de dados Luciano Ramalho [email protected] @ramalhoorg Open Library no MongoDB Tuesday, July 17, 12

Open Library no Mongodb

Embed Size (px)

DESCRIPTION

Uso de map/reduce e do framework de agregação do MongoDB para análise de uma grande base de dados bibliográfica

Citation preview

Page 1: Open Library no Mongodb

Usando Map/Reduce e o Aggregation Frameworkpara análise e modelagem de dados

Luciano [email protected]

@ramalhoorg

Open Library no MongoDB

Tuesday, July 17, 12

Page 2: Open Library no Mongodb

@ramalhoorg

Temas• Sobre o projeto Open Library

• Conversão e importação da massa de dados

• Análise dos dados com o framework de agregação

• Análise dos dados com Map /Reduce

• Refatoração do modelo de dados para o MongoDB

• Encerramento

Tuesday, July 17, 12

Page 3: Open Library no Mongodb

@ramalhoorg

Sobre o projetoOpen Library

Tuesday, July 17, 12

Page 4: Open Library no Mongodb

@ramalhoorg

Sobre a Open Library

• Missão:

• Um projeto do Internet Archive

• 117.439.126 registros bibliográficos em jun/2012

• Mais de 1.000.000 de e-books gratuitos para baixar (livres, CC, domínio público etc.)

“One web page for every book”

Tuesday, July 17, 12

Page 5: Open Library no Mongodb

@ramalhoorg

A Tecnologia da Open Library• Infobase: uma API Python para bases de dados

semi-estruturadas sobre tabelas normalizadas

• também conhecida como ThingDB

• Inclui versionamento de registros

• Muitos join para recuperar uma entidade conceitual

• Fortemente depenente do SOLR/Lucene para exibir suas páginas

Tuesday, July 17, 12

Page 6: Open Library no Mongodb

@ramalhoorg

Modelo de dados semi-estruturado• Base teórica existe!

• Palavras-chave para pesquisa: semistructured ou semi-structured database

“The semi­structured data model is designed as an evolution of the relational data model that allows the

representation of data with a flexible structure. ”

SUCIU, Dan. Semi­Structured Data Model. In: LIU, L. Encyclopedia of Database Systems

Tuesday, July 17, 12

Page 7: Open Library no Mongodb

@ramalhoorg

Data on theWeb (1999)• From Relations to

Semistructured Data and XML

• Autores: Abiteboul, Buneman & Suciu

• Notação apresentada: semelhante a JSON

Tuesday, July 17, 12

Page 8: Open Library no Mongodb

@ramalhoorg

SemistructuredDatabase Design(2004)• Autores: Ling, Lee & Dobbie

• Algoritmos de normalização sem a 1ª Forma Normal (N1NF = Non First Normal Form)

Tuesday, July 17, 12

Page 9: Open Library no Mongodb

@ramalhoorg

Conversão e importação da massa de dados

Tuesday, July 17, 12

Page 10: Open Library no Mongodb

@ramalhoorg

Massa de dados

• OL Complete Dump: ol_cdump_latest.txt.gz*

• 118.598.056 linhas em 1/jun/2012

• 16 GB comprimidos (.gz), 91 GB sem compressão

• 32 tipos diferentes de registros

• 1.158.930 (~1%) não são registros bibliográficos

• Inclui todas as revisões de todos os registros

* http://openlibrary.org/developers/dumpsTuesday, July 17, 12

Page 11: Open Library no Mongodb

@ramalhoorg

Converter para carregar

• Escolha de uma chave primária (campo _id)

• Chave composta: key+"-"+revision

• /books/OL1656964M-1

• Opção adotada: a conversão mais simples possível

• Usar JSON do dump, acrescido de campo _id

Tuesday, July 17, 12

Page 12: Open Library no Mongodb

@ramalhoorg

Carga: conversor_ol.pyimport sysimport jsonimport io

def conv_linha(lin, indent=None): rec_type, rec_key, rec_revision, rec_modified, rec_json = lin.split(u'\t') rec = json.loads(rec_json) rec[u'_id'] = rec_key + u'-' + rec_revision return json.dumps(rec, indent=indent)

def conv_arquivo(nome_arq, max_lin=sys.maxsize, indent=None): with io.open(nome_arq, encoding='utf-8') as arq: for num_lin, lin in enumerate(arq, 1): if not lin.strip(): continue saida = conv_linha(lin, indent) print saida.encode('utf-8') if num_lin >= max_lin: break

if __name__=='__main__': if len(sys.argv) == 2: converte_arquivo(sys.argv[1]) else: print 'Modo de usar: %s <ol_dump_file>' % __name__

* https://github.com/ramalho/mongospTuesday, July 17, 12

Page 13: Open Library no Mongodb

@ramalhoorg

Usando mongoimport

• -d: database

• -c: collection

• --stopOnError: interromper se houver erro

• --upsert: sobrescrever ao importar _id duplicado (default: ignorar o novo registro)

• --file: arquivo a inserir (default: stdin)

python conversor_ol.py $1 | \ mongoimport -d openlibrary -c complete --stopOnError

Tuesday, July 17, 12

Page 14: Open Library no Mongodb

@ramalhoorg

Análise dos dados usando o framework de agregação

Tuesday, July 17, 12

Page 15: Open Library no Mongodb

@ramalhoorg

Indexação para análise

• Criar índices esparsos para:

• key

• revision

• type

• outros...

Tuesday, July 17, 12

Page 16: Open Library no Mongodb

@ramalhoorg

Aggregation Framework:o básico• Novidade no MongoDB 2.1/2.2

• Alternativa ao Map/Reduce

• Mais fácil de usar

• Melhor desempenho

• implementado em C++, usa threads (Map/Reduce depende do interpretador JavaScript Spidermonkey, mono-thread)

Tuesday, July 17, 12

Page 17: Open Library no Mongodb

@ramalhoorg

Exemplo: group_types.js

• $group

• $sort

db = db.getMongo().getDB('openlibrary');db.complete.ensureIndex({"type.key":1});

var res = db.complete.aggregate( { "$group" : { ! "_id" : "$type.key", ! "qt" : { "$sum" : 1 } }}, { "$sort" : { "qt" : -1 }});

res.result.forEach(function (r) { print(r.qt+"\t"+r._id);});

* https://github.com/ramalho/mongospTuesday, July 17, 12

Page 18: Open Library no Mongodb

@ramalhoorg

• O primeiro lote de 1.000.000 de registros tem 9 tipos diferentes

• Os três primeiros são os mais importantes: edition, author, work

$ time mongo2.1 group_types.js MongoDB shell version: 2.1.2connecting to: test605781! /type/edition382428! /type/author9211!/type/work1935!/type/redirect623! /type/delete7! /type/template7! /type/page5! /type/doc3! /type/macro

real!0m23.658suser!0m0.030ssys! 0m0.004s

Exemplo: group_types.js

Tuesday, July 17, 12

Page 19: Open Library no Mongodb

@ramalhoorg

Agregação em estágios

• Estágios: etapas em um fluxo (steps in a pipeline)

• Estágios são executados em ordem, na ordem dos parâmetros da invocação de mapReduce

• Cada estágio aplica um operador especial

• O mesmo operador pode ser usado várias vezes em estágios diferentes

Tuesday, July 17, 12

Page 20: Open Library no Mongodb

@ramalhoorg

Operadores de estágios

• $match

• $project

• $limit

• $skip

• $group

• $sort

• $unwind

Tuesday, July 17, 12

Page 21: Open Library no Mongodb

@ramalhoorg

var res = db.complete.aggregate( { $match : {"type.key" : "/type/edition"} }, { $project : { languages : 1} }, { $unwind : "$languages" }, { $group : { _id : "$languages.key", qt : { $sum : 1 } }}, { $sort : { qt : -1, _id : 1 }});

Exemplo 2a* https://github.com/ramalho/mongosp

• $match

• $project

• $unwind

• $group

• $sortTuesday, July 17, 12

Page 22: Open Library no Mongodb

@ramalhoorg

Exemplo 2b

• $group

• $sort

* https://github.com/ramalho/mongosp

db = db.getMongo().getDB('openlibrary');db.complete.ensureIndex({"revision":1});var res = db.complete.aggregate( { $match : {"type.key" : "/type/edition"} }, { $project : { languages : 1} }, { $unwind : "$languages" }, { $group : { _id : "$languages.key", qt : { $sum : 1 } }}, { $sort : { qt : -1, _id : 1 }});res.result.forEach(function (r) { print(r.qt+"\t"+r._id);});

Tuesday, July 17, 12

Page 23: Open Library no Mongodb

@ramalhoorg

O que não dá para fazer (atualmente)• Conjunto limitado de operadores

• Para lidar com strings, por exemplo:

• $substr, $toLower, $toUpper, $strcasecmp

• não tem length, regex, startswith, etc.

• O framework foi feito para ser extensível

• Mas não tem uma arquitetura de plug-ins

Tuesday, July 17, 12

Page 24: Open Library no Mongodb

@ramalhoorg

Análise dos dados comMap/Reduce

Tuesday, July 17, 12

Page 25: Open Library no Mongodb

@ramalhoorg

O problema do“schema after”• Conceito: “schema before” x “schema after”

• Michael Stonebraker (criou Ingres, VoltDB etc):

• MongoDB é “schema after”

• Em uma base “schema after” em produção, o esquema real quase nunca é exatamente o planejado

Tuesday, July 17, 12

Page 26: Open Library no Mongodb

@ramalhoorg

Análise profundados dados• Estatísticas sobre a estrutura dos registros

• para cada tipo de registro, quais campos ocorrem, e em qual frequência

• Estatísticas sobre estrutura dos campos

• valores simples, arrays e documentos aninhados (objetos)

Tuesday, July 17, 12

Page 27: Open Library no Mongodb

@ramalhoorg

Map/Reduce: o básico

• Executado através do método mapReduce:

db.complete.mapReduce(map, reduce, {out: { inline : 1}, jsMode: true})

• Função map deve processar cada item (this) e emitir um par de chave: valor

• Função reduce deve aceitar chave e um array de valores, e devolver apenas um valor agregado

Tuesday, July 17, 12

Page 28: Open Library no Mongodb

@ramalhoorg

Map/Reduce

Tuesday, July 17, 12

Page 29: Open Library no Mongodb

@ramalhoorg

Map/Reduce me lembra Pacman• Jogador faz reduce

dos pontinhos

• Resultado do reduce é o score

Tuesday, July 17, 12

Page 30: Open Library no Mongodb

@ramalhoorg

Exemplo

• Obter lista de todos os campos e quantas vezes cada um ocorre nos registros de edition

284396! subtitle251678! subject_place592707! lc_classifications264695! contributions605777! title604455! languages475865! subjects598671! publish_country193955! series113818! title_prefix605781! type538357! by_statement605781! revision600934! publishers605781! last_modified605781! key

Tuesday, July 17, 12

Page 31: Open Library no Mongodb

@ramalhoorg

Map

• Se o registro é do tipo edition, emitir um par de («nome_do_campo», 1) para cada campo

var map = function () { if (this.type.key === "/type/edition") { for (field_name in this) { emit(field_name, 1); } }}

Tuesday, July 17, 12

Page 32: Open Library no Mongodb

@ramalhoorg

Reduce• Todos os pares de («chave», «valor»)

são agrupados em pares pela «chave»:(«chave»: [«valor0», «valor1», «valor2»])

• A função reduce deve reduzir cada «array_de_valores» a um único valor

var reduce = function (key, values) { var total = 0; values.forEach(function(n) { total += n; }); return total;}

Tuesday, July 17, 12

Page 33: Open Library no Mongodb

@ramalhoorg

Executar mapReducevar res = db.complete.mapReduce(map, reduce, { "out": { "inline" : 1}, "jsMode": true});

//exibir resultadores.results.forEach(function (r) { print(r.value+"\t"+r._id);});print("-----");for (var chave in res.counts) { if (chave !== "_id") { print(chave+"\t"+res.counts[chave]); }}print("-----");print("tempo (s)\t"+res.timeMillis/1000);

Tuesday, July 17, 12

Page 34: Open Library no Mongodb

@ramalhoorg

Resultado de mapReduce

[...]! ! {! ! ! "_id" : "works",! ! ! "value" : 4415! ! }! ],! "timeMillis" : 156659,! "counts" : {! ! "input" : 1000000,! ! "emit" : 13196408,! ! "reduce" : 363448,! ! "output" : 61! },! "ok" : 1,}real! 2m36.696suser! 0m0.028ssys!0m0.005s

> var res = db.complete.mapReduce(map,... reduce, {"out": { "inline" : 1}, ... "jsMode": true });{"results" : [! ! {! ! ! "_id" : "_id",! ! ! "value" : 605781! ! },! ! {! ! ! "_id" : "authors",! ! ! "value" : 469305! ! },! ! {! ! ! "_id" : "by_statement",! ! ! "value" : 538357! ! },! ! {! ! ! "_id" : "classifications",! ! ! "value" : 3! ! },

• Usando{"out": { "inline" : 1}}

Tuesday, July 17, 12

Page 35: Open Library no Mongodb

@ramalhoorg

Executar mapReduce

210! ! coverimage16!! ! isbn_odd_length3! ! ! classifications1! ! ! collections5! ! ! copyright_date4! ! ! download_url3! ! ! purchase_url1! ! ! language_code-----input!! 1000000emit!! 13196408reduce! 363448output! 61-----tempo (s)!102.13

$ mongo2.1 mr_fields.js MongoDB shell version: 2.1.2connecting to: test284396! subtitle251678! subject_place592707! lc_classifications264695! contributions605777! title604455! languages475865! subjects598671! publish_country193955! series113818! title_prefix605781! type

* https://github.com/ramalho/mongosp

Tuesday, July 17, 12

Page 36: Open Library no Mongodb

@ramalhoorg

Campose tipos

$ mongo2.1 mr_fieldtypes_sort.js MongoDB shell version: 2.1.2connecting to: test_id:string!605781authors:array! 469305by_statement:string! 538357classifications:object!3collections:array!1contributions:array! 264695copyright_date:string! 5coverimage:string!210covers:array!3648created:object!10086description:object! 33040dewey_decimal_class:array!325519download_url:array! 4edition_name:string! 124615first_sentence:object! 682first_sentence:string! 2

* https://github.com/ramalho/mongosp

• Identificar tipo do dado em cada ocorrência

• Detectar inconsistências

Tuesday, July 17, 12

Page 37: Open Library no Mongodb

@ramalhoorg

Refatorando o esquema para o MongoDB

Tuesday, July 17, 12

Page 38: Open Library no Mongodb

@ramalhoorg

Um registro

• 25 campos neste registro

{ "subtitle": "Ausbau und Planung der petrochemischen und energieintensiven Industrien zum Zeitpunkt des zweiten Golfkriegs", "subject_place": [ "Middle East." ], "lc_classifications": [ "HD9579.C33 M6284 1991" ], "contributions": [ "Helmschrott, Helmut." ], "title": "Industrialisierung der arabischen OPEC-La\u0308nder und des Iran", "languages": [ { "key": "/languages/ger" } ], "subjects": [ "Petroleum chemicals industry -- Middle East.", "Petroleum industry and trade -- Middle East.", "Gas industry -- Middle East." ], "publish_country": "gw ", "series": [ "Ifo Forschungsberichte der Abteilung Entwicklungsla\u0308nder ;", "Nr. 74", "Ifo Forschungsberichte der Abteilung Entwicklungsla\u0308nder ;", "74." ], "title_prefix": "Die ", "type": { "key": "/type/edition" }, "by_statement": "von Axel J. Halbach, Helmut Helmschrott.", "revision": 1, "publishers": [ "Ifo Institut fu\u0308r Wirtschaftsforschung", "Weltforum Verlag" ], "last_modified": { "type": "/type/datetime", "value": "2008-04-01T03:28:50.625462" }, "key": "/books/OL1656964M", "authors": [ { "key": "/authors/OL45038A" } ], "publish_places": [ "Mu\u0308nchen" ], "pagination": "viii, 270 p. :", "lccn": [ "91218377" ], "notes": { "type": "/type/text", "value": "Includes bibliographical references (p. 268-270)." }, "number_of_pages": 270, "isbn_10": [ "3803903955" ], "publish_date": "1991", "_id": "/books/OL1656964M-1"}

Tuesday, July 17, 12

Page 39: Open Library no Mongodb

@ramalhoorg

"title": "Industrialisierung der arabischen...", "revision": 1, "publishers": [ "Ifo Institut fu\u0308r Wirtschaftsforschung", "Weltforum Verlag" ], "last_modified": { "type": "/type/datetime", "value": "2008-04-01T03:28:50.625462" }, "key": "/books/OL1656964M", "authors": [ { "key": "/authors/OL45038A" } ], "publish_places": [ "Mu\u0308nchen" ],

Chave estrangeira

Tuesday, July 17, 12

Page 40: Open Library no Mongodb

@ramalhoorg

Refatoração do esquema

• Usar key+revision como chave primária _id

• Manter campos key e revision separados

• Para fazer pseudo-auto join recuperando o histórico de um registro bibliográfico

• Embutir (embed) campo nome do autor no documento

"authors": [ { "key": "/authors/OL45038A", "name": "W. A. Mozart" } ],

Tuesday, July 17, 12

Page 41: Open Library no Mongodb

@ramalhoorg

Representação do histórico de versões• Embutir pode ser uma boa opção para os tipos de

registros que são raramente atualizados

• Versões antigas embutidas

• Para registros que sofrem muitas atualizações, a melhor opção é uma sequência de referências (“chaves estrangeiras”)

• Um “pseudo self-join” pode ser feito pelo atributo key para recuperar o histórico

Tuesday, July 17, 12

Page 42: Open Library no Mongodb

@ramalhoorg

Integridade referencial

• Identificação de problemas atuais

• Ferramentas de suporte

• Índices

• Uso de um framework com ODM (object-document mapper)

• Tarefas de monitoração assíncrona

Tuesday, July 17, 12

Page 43: Open Library no Mongodb

@ramalhoorg

Algumas dicas

• Todo registro deve ter campos identificando:

• seu tipo

• a versão do esquema usada naquele registro

• Mudanças no esquema podem ser feitas de modo incremental, quando um documento é alterado

• Use um ODM (Object-Document Mapper) para aumentar a consistência dos dados armazenados

Tuesday, July 17, 12

Page 44: Open Library no Mongodb

Tuesday, July 17, 12

Page 45: Open Library no Mongodb

Excelente opção para hospedagem de MongoDB.

Pequenas instâncias gratuitas, instâncias maiores por preços acessíveis, sem você precisar gerenciar o servidor, sistema

operacional, storage etc.Tuesday, July 17, 12