Download pdf - OOP 2013 NoSQL Suche

Datensuche mit NoSQL

Kai Spichale

27.01.2013

Über mich

► Kai Spichale

► Softwarearchitekt und -entwickler bei adesso AG

► Schwerpunkt: Java-Technologien

► Autor verschiedener Fachartikel, Sprecher auf Konferenzen

27.01.2013 OOP 2013 Kai Spichale 1

► adesso gehört zu den führenden IT-Dienstleistern im deutschsprachigen Raum

► Beratung und individuelle Softwareentwicklung

► Mehr als 1000 Mitarbeiter

► Zu den wichtigsten Kunden zählen die Allianz, Hannover Rück, Union Investment, Westdeutsche Lotterie, Zurich Versicherung, DEVK und DAK

Motivation

NoSQL

► Exponentielles Datenwachstum

► Semistrukturierte Daten

► Stärker vernetzt

► 80% der unternehmensrelevanten Informationen in unstrukturierter Form, hauptsächlich Text

Suche

► Datenzugriff ändert sich:

> Volltextsuche wird wichtiger

> Benutzererwartungen steigen

► Suche über bekannte Schlüsselbegriffe oder über ein Katalogsystem sind für große Datenbestände unpraktisch


Agenda

► Lucene Volltextsuchen

► NoSQL:

> Architekturtreiber

> MongoDB

> Neo4j

> Apache Cassandra

> Apache Hadoop

► Schlussbemerkung


Volltextsuchen

► Aufgabe: Auffinden von Texten in einer Vielzahl von Dateien oder Datensätzen

► Naiver Ansatz mit linearer Suche à la grep:

> O(n), langsam

> Negation ist schwierig

> Fehlende Unterscheidung von Phrasen und Schlüsselwörtern

► Invertierter Index:

> Term Dokument

> Jedem Term werden Informationen über das Vorkommen des Terms in den Dokumenten zugeordnet


Apache Lucene

► Java-Bibliothek für Volltextsuchen

► De-facto-Standard im Bereich Open-Source-Suchlösungen

► Merkmale:

> Anwendungsneutral

> Gute Performance

► Funktionalität:

> Bewertete und nach Rang sortierte Suchen

> Viele Abfragetypen, Facettennavigation

> Suche nach einzelnen Feldern

> Sortierung

> Multi-Index-Suchen

> Parallele Suche und Update


Textanalyse


Extrahieren,

Parsen

Character

Filter

Tokenizer

Token Filter

Dokumente

de.GermanAnalyzer:

StandardTokenizer > StandardFilter

> LowerCaseFilter > StopFilter > GermanStemFilter

Invertierter

Index

Textanalyse


ID Term Document

1 come 2

2 dog 1

3 eat 1

4 exception 3

5 first 2

5 food 1

6 own 1

7 prove 3

8 rule 3

9 serve 2

10 your 1

Eat your

own dog

food.

First

come,

first

served.

The

exception

proves the

rule.

a

and

around

every

for

from

in

is

it

not

on

one

the

to

under

Stopword List

Abfragetypen

Abfrage Beispiel

Termsuche

(MUST, MUST_NOT, SHOULD)

+dog –snoopy

Phrasensuche „foo bar“

Wildcard fo*a?

Fuzzy fobar~

Range [A TO Z]


NoSQL und Datensuche

„One size fits all“-Ansatz

► Welche NoSQL-Datenbank erfüllt die Anforderungen am besten?

► Wird Volltextsuche unterstützt?


Datenstruktur Datenzugriff

Volumen Performance

Verfügbarkeit Änderungen

Konsistenz

NoSQL und Datensuche


Was bieten diese Datenbanken?

► MongoDB

► Neo4j

► Apache Cassandra

► Apache Hadoop

Dokumentenorientierte Datenbanken

{ "_id" : ObjectId(„42"),

"firstname" : "John",

"lastname" : "Lennon",

"address" : { "city" : "Liverpool",

"street" : "251 Menlove Avenue“ }

}


► Speichern Daten in Form von Dokumenten

► Semistrukturierte Inhalte

► JSON, YAML, XML

MongoDB

► Ad-hoc-Abfragen für Dokumente oder einzelne Felder

db.things.find({firstname:"John"})

► Abfragen mit serverseitig ausgeführten JavaScript-Funktionen

► Aggregationen, MapReduce

► Einfache Textsuchen

> Mit Multikeys können Werte eines Arrays indiziert werden


{ article : “some long text",

_keywords : [ “some" , “long" , “text“]

}

MongoDB

► Mongo-Connector synchronisiert Daten aus MongoDB mit einem Zielsystem (z.B.: Solr, Elastic Search)

► Architektur mit separaten Suchserver möglich


MongoDB SolrMongo

Connector

1 2 3 4 5

update syncDocerstellen indizieren suchen

MongoDB

MongoDB MongoDB + Lucene Lucene

Kein Ergebnis-Mergen

Komplexe Queries mit

Aggregationen

Nur einfache

Textsuchen

Volltextsuchen mit

Stemming, Faceting

Komplexe Queries mit

Aggregationen

Mergen notwendig

Erhöhte Komplexität

(Entwicklung, Betrieb)

Kein Ergebnis-Mergen

Volltextsuchen mit

Stemming, Faceting

Keine Transaktion

Keine partiellen

Dokumentupdates

Verwendet Schema


Graphendatenbanken

► Informationen werden als Graphen modelliert

> Knoten

> Kanten (auch Relationships)

> Eigenschaften (auch Properties)

► Universelles Datenmodell

► Traversierung

► Beispiel: Neo4j


id=1

name=“John“

id=2

name=“George“

id=3

name=“Paul“

friend friend

Neo4j

► Traversierung:

> Tiefensuche, Breitensuche

> Gremlin, Cypher

Ergebnis = George


START person=node:peoplesearch(name=‘John’)

MATCH person<-[:friends]->afriend RETURN afriend

Neo4j

► Ganze Datenbank ist natürlicher Index bestehend aus Knoten oder Beziehungen

> Beispiele: „name“, „city“

► Auto-Indexing verfolgt alle Property-Änderungen


personRepository.findByPropertyValue("name", "John");

Neo4j

► Unterstützt Lucene-basierte Volltextindizes


Index<PropertyContainer> index = template.getIndex("peoplesearch");

index.query("name", "Jo*");

@NodeEntity class Person {

@Indexed(indexName="peoplesearch", indexType=IndexType.FULLTEXT) private String name;

..

}

Wide Column Store

► Google BigTable: „a sparse, distributed multi-dimensional sorted map“

► Daten organisiert in Zeilen, Spaltenfamilien und Spalten

► Ideal für zeilenweises Sharding (horizontale Skalierung)


jlennon

pmccart

gharris

name

„Lennon“

name

„McCartney“

name

„Harrison“

state

„UK“

address

„Liverpool ..“

address

„Liverpool ..“

Unterschiedliche Spalten

pro Zeile möglich

Eindeutige

Zeilenschlüssel

Apache Cassandra

► BigTable-Klon

► Distributed Hash Table (Amazon Dynamo)

► Schlussendlich konsistent, konfigurierbar

► Datenabfrage:

> Cassandra Query Language (CQL) = SQL-Dialekt ohne Joins

> Hadoop-Integration


SELECT name FROM user WHERE firstname=„John“;

Apache Cassandra

► Solandra: Solr mit Cassandra als Backend statt Dateisystem

► DataStax Enterprise Search

> Daten in Cassandra werden lokal in Solr indiziert und umgekehrt

> Integration durch Secondary Index API

> CQL unterstützt Solr-Queries

> Dokumentenweise werden die Daten im Cluster verteilt

> Nutzt Cassandra Ringinformationen für Solr Distributed Search Query


Cassandra Solr

Column Family Core

Row Document

Row Key Unique

Column Field

Node Shard

SELECT title FROM solr WHERE solr_query=‘name:jo*';

Apache Hadoop

► Open Source Projekt zur Verarbeitung von großen Datenmengen (BigData) im Computercluster

► Skalierbar, ausfallsicher

► Umfangreiches Hadoop Ökosystem

► Hadoop Distributed File System, Hadoop MapReduce


Hadoop MapReduce

27.01.2013 23

Persistente Daten

Map Map Map Map

Transiente Daten

Persistente Daten

Reduce Reduce Reduce

► Map Phase:

> Datensätze werden in Map-Funktion verarbeitet

► Shuffle/Combine Phase:

> Verteilte Sortierung und Gruppierung

► Reduce Phase:

> Verarbeitung des Zwischenergebnisses in Reduce-Funktion

OOP 2013 Kai Spichale

Hadoop MapReduce

► Allgemeine Funktionsweise eines MapReduce-Jobs


map(k, v) -> [(K1,V1), (K2,V2), ... ]

reduce(Kn, [Vi, Vj, …]) ->

(Km, R)

Daten

Mapper

Shuffle Reducer Ergebnis

Wie löst man Probleme mit MapReduce?

► Problemklassen ohne Reduce-Phase

> Suchen

> Massenkonvertierung

> Sortieren

> Map-Side Join

► Problemklassen mit Reduce-Phase

> Gruppieren und Aggregieren

> Reduce-Side Join


Hadoop MapReduce: Suchen

► Suche nach „A“


1

2 1

Daten

1: A,B,C

3

4

5

Mapper emittiert nur Records

mit Suchkriterium

4

5

2: D,E

3: B,E

4: A,D

5: A,C,E

Ergebnis = 1, 4, 5

Hadoop MapReduce: Indizieren


HDFS

MapReduce

Job

Lucene Lucene

Index

► HDFS speichert Rohdaten

► Mapper indiziert Daten mit Lucene

> SolrInputDocument erzeugen und StreamingUpdateSolrServer aufrufen

Hadoop MapReduce: Indizieren


1

2

Daten

1: text

3

4

5

2: text

3: text

4: text

5: text

Ergebnis

ist null

Mapper

@Override public void map( LongWritable key, Text val, OutputCollector<NullWritable, NullWritable> output, Reporter reporter) throws IOException { st = new StringTokenizer(val.toString()); lineCounter = 0; while (st.hasMoreTokens()) { doc= new SolrInputDocument(); doc.addField("id", fileName + key.toString() + lineCounter++); doc.addField("txt", st.nextToken()); try { server.add(doc); } catch (Exception exp) { … } }}

Apache Tika


HDFS

MapReduce

Job

Lucene Lucene

Index

Tika

► Extrahiert Metadaten und strukturierten Text aus Dokumenten:

> HTML, MS Office Dokumente, PDF, etc.

► Stream-Parser auch für große Dokumente geeignet

Apache Solr


HDFS

MapReduce

Job

Lucene Lucene

Index

Tika

Solr

► Lucene ist eine Programmbibliothek, kein Suchserver

► Suchserver:

> Solr

> ElasticSearch

Apache Flume


HDFS

MapReduce

Job

Lucene Lucene

Index

Tika

Solr

Flume

Web Server,Applikationen

► Verteilter Dienst zum Sammeln, Aggregieren und Kopieren großen Datenmengen

► Streaming-Techniken

► Fehlertolerant

Alternativen


HDFS

MapReduce

Job

Lucene Lucene

Index

Tika

Solr

Flume

Web Server,Apps, DBs

Crawler DistCp Sqoop

► Nutch Crawler erzeugt einen Datensatz pro URL in CrawlDB

► Hadoop DistCp kopiert Daten innerhalb/ zwischen Hadoop-Clustern

► Apache Sqoop transferiert Bulk-Daten zwischen Hadoop und RDBMS

Apache Hadoop


Web Content,Intranet

Loading

Werkzeug

Hadoop

Suche Analyse Export Visualisierung

► Fundamentaler Mismatch:

> MapReduce ideal für Batch-Verarbeitung

> Lucene für interaktive Suchen

► MapReduce zum Indizieren von großen Datenmengen

► Geeignet für (offline) Big-Data-Lösung

Zusammenfassung

► Mehr semistrukturierte Daten

► Bedeutung von Volltextsuchen wächst

► Kombination von NoSQL-Store und Lucene:

> MongoDB: Integration mit Mongo Connector

> Neo4j: native Integration

> Cassandra: „Online BigData“

> Hadoop: „Offline BigData“

► Alternative: Suchserver als dokumentenorientierte Datenbank
