2013-08-26
Big Data
Big Data Schaalbaar rekenen
Zoek Suggesties
Niels Basjes
[email protected] @nielsbasjes http://github.com/nielsbasjes
TU-Delft Informatica Nyenrode Bedrijfskunde Software ontwikkelaar Onderzoeker (NLR) Infra Architect (NLR) Webanalytics Architect IT Architect Sinds 2008 bij Bol.com
Zoek Suggesties •
Architectuur schets
Basis idee: • Volledig automatisch • Klanten helpen klanten
•
Processing principe • Elke historische zoek actie is een potentiële suggestie. • Sorteren op relevantie. • Bied de 10 meest relevante als suggestie.
•
Razendsnel
Wat is “relevant”? • De zoekactie en het resultaat • Het gedrag na de zoekactie.
Grote batch
Clickstream
1
2013-08-26
Zoek suggesties (versie 1)
Zoek suggesties (versie 1)
• Eerste versie: • Alleen zoekacties tellen • Kwantitatief filteren • Beperkte feedback
1 • • • • • •
• Schaal • 1 week data • 1 systeem om het te berekenen
zoek actie op de term “Hadoop” “H” “Hadoop” : 1 “Ha” “Hadoop” : 1 “Had” “Hadoop” : 1 “Hado” “Hadoop” : 1 “Hadoo” “Hadoop” : 1 “Hadoop” “Hadoop” : 1
Zoek suggesties (versie 1)
Zoek suggesties (versie 1)
2 • • • • • • • •
Combineer die twee • “H” { “Harry Potter”, “Hadoop” } • “Ha” { “Harry Potter”, “Hadoop” } • “Har” { “Harry Potter” } • “Had” { “Hadoop” } • “Harr” { “Harry Potter” } • “Hado” { “Hadoop” } • …
Zoek acties op de term “Harry Potter” “H” “Harry Potter” : 2 “Ha” “Harry Potter” : 2 “Har” “Harry Potter” : 2 “Harr” “Harry Potter” : 2 “Harry” “Harry Potter” : 2 “Harry ” “Harry Potter” : 2 “Harry P” “Harry Potter” : 2 …
Functioneel effect
“nijntje dekbedovertrek” Bezoekers vinden dat een heel interessante suggestie! Alleen hebben we dat niet…
2
2013-08-26
Zoek suggesties (versie 2)
De zoek funnel
Zoeken Vinden
Gebruik meer data en analyseer het gedrag
Kiezen
Kopen
14
Kwalitatief filteren
Dieper = relevanter (Zoeken)
Vinden
Kiezen
Kopen 15
Recenter = relevanter
1 jaar klik historie
Gisteren
Eergisteren
Vorige week
Vorige maand
3
2013-08-26
En dat is best veel data …
Dit wordt te groot! (1/2) • Gemiddeld 3.5 GiB Gzip logfiles per dag • 3.5GiB Gzip ≈ 35GiB text
• Eerste doel: • 12 weken historie (84 dagen) • Dus zo’n 300GiB (≈ 3TiB text) aan input mee laten wegen
• Nu: • 1 jaar historie
• Uiteindelijk: • “Alles wat we hebben liggen”
Dit wordt te groot! (2/2)
Recommendations
• Steeds dieper kijken • Redeneren over alle acties van een bezoeker • Verbanden vinden in veel grotere dataset • Op basis van die verbanden betere relevanties bepalen
• Inschatting aan het begin van het project: • Dit gaat meer rekentijd kosten dan we hebben
Recommendations
Wisdom of the crowd.
Welke andere producten zijn relevant bij dit product?
De klanten stemmen met hun “digitale voeten”
4
2013-08-26
Het gedrag van een klant
Het gedrag van een klant
Bekijkt/Koopt een aantal verschillende producten
Die producten hebben dus een relatie
Het gedrag van een klant
Wat doen veel klanten Klant 1
Trigger
Klant 2
Klant 3
Aanbeveling
Tuple
Elk product beveelt elk ander product aan
Wat doen veel klanten Klant 1
Klant 2
Klant 3
Wat doen veel klanten Klant 1
Klant 2
Klant 3
5
2013-08-26
Heel veel anonieme tuples
De waarde van een tuple? Hoeveel bekeken?
∑ Hoeveel verkocht?
Allemaal een score geven
Groeperen
Allemaal de score ‘1’
Aggregeren
Ruis filteren
Te weinig bezoekers deden dit.
6
2013-08-26
“Group By” trigger, sorteer op score
Veel te groot! Totaal aantal tuples:
12.800.000.000 = 12.8 miljard
Veel te groot! Totale rekentijd welke we elke week verstoken:
400 uur = 16 dagen (exclusief overhead)
Het past niet meer
Te groot voor 1 computer!
7
2013-08-26
BigData
Algemene voorspelling Steeds meer data
Data volume en de wensen om daar iets mee te doen groeien sneller dan de kracht van de computers.
Business Value
Steeds sneller operationeel toepassen
Schaalbaarheid
Verschillende soorten bron gegevens
Continue veranderingen in de data bronnen
Voorbeeld case
Het oogsten van gewassen
Elk begin is klein
Automatiseren
8
2013-08-26
Opschalen naar groter …
En nog groter …
En nog groter …
Tot de grootste
Twee soorten schaalbaar (1/2)
Twee soorten schaalbaar (2/2)
Verticaal: Steeds groter • Voor: • Zolang het kan: Makkelijk. • Korte time-to-market • Tegen: • Wordt snel duur • “Big bang” aankoop • Groter dan de grootste kan niet.
Horizontaal: Steeds meer naast elkaar • Voor: • Veel meer doorgroei potentie. • Incrementeel groter maken • Kosten effectief • Tegen: • Het proces moet ervoor ontworpen worden. Kan ALLEEN als het werk in onafhankelijke delen gesplitst kan worden.
9
2013-08-26
Meer …
Nog meer …
Economische maat
Verschillende modellen
Heel veel meer …
Begin bij het proces ontwerp • Voldoende “brokken” werk. – Anders is het zo lastig verdelen
• De “brokken” zijn onafhankelijk.
Meer performance
– Anders vervalt de schaalbaarheid
Meer systemen
Google: “soybean harvest”
Logistiek
Verkeer
Veel bakjes worden parallel gevuld en onafhankelijk van elkaar ingepakt.
10
2013-08-26
Supermarkten
Website horizontaal schalen
Onafhankelijke data? (1/3)
Onafhankelijke data? (2/3)
• Met relaties in de data (RDBMS / SQL) • Transacties over tabellen heen • Strong consistenticy (ACID) • Atomic, Consistent, Isolation, Durable • Meestal alleen vertikaal schaalbaar.
• Zonder relaties in de data (Geen SQL) • Geen transacties over tabellen heen • Eventual consistency (BASE) • Basically Available, Softstate, Eventually consistent • Horizontaal schaalbaar is mogelijk
Onafhankelijke data? (3/3)
Data horizontaal schalen?
• NoSQL (Not ONLY SQL) • Kies verstandig afhankelijk van de situatie • Praktijk: Hybride landschap!
Google paper uit 2004 “MapReduce: Simplified Data Processing on Large Clusters”
11
2013-08-26
What did Google do?
What did Google do?
Groot aantal computers 1. Data distribueren 2. Processing naar de data sturen. En een processing model om dit herbruikbaar te maken.
MapReduce
What did Google do?
What did Google do?
Is dit betrouwbaar?!?!
Data verspreiden (HDFS) Client Input 1 bestand 2 3
Server 1
Server 2
Server 3
Replicatie factor =2
12
2013-08-26
Map Reduce
1
3
Client
JOB
JOB
1
Server 1
En toen deed het … BOEM!
Client
2
2
Server 2
3
1
Server 3
Replicatie factor =2
1
2
Server 2
2
3
Server 3
Replicatie factor =2
MapReduce processing model • • • • •
3
Server 1
MapReduce: basis idee • Map (Transformeren) • 1 Input record omzetten en “groepeerbaar” maken. • Input: “Input regels” • Output: Aantal (“Key”,“Value”) paren
> 30 jaar oud Alleen voor Batch verwerking Eenvoudig Horizontaal schaalbaar Kan in alle programmeer talen
• Reduce (Groeperen en Aggregeren) • Alles met dezelfde “Key” aggregeren • Input: 1 “Key” met een aantal “Values” • Output: De records die gewenst zijn.
Woorden tellen Map Split
Shuffle/ Sort
Ketens van MR jobs
Reduce Output
Input
13
2013-08-26
Hadoop MapReduce
Hadoop Ecosysteem
• Java implementatie van MapReduce • Een handige toolkit • Kennis beschikbaar • Boeken, Trainingen, Community. • Support beschikbaar • Hortonworks, Cloudera, MapR • Grote spelers • Yahoo, Linkedin, Twitter, Facebook, Amazon, Adobe, …
Van concept naar praktijk
Laat zien dat het schaalt
Klein beginnen
Laat anderen het proberen
14
2013-08-26
3 weken webdata in 25 minuten!
In productie nemen
• Het productie cluster • VM Master • 5 Workers systemen • 2 CPU x 4 Core • 8 Disks * 450 GB • 32GiB Ram
Job Status: Succeeded
Waar ligt de grens?
Business impact
Op een paar duizend servers!
Toepassingen binnen bol.com • Aanbevelingen • • • •
Zoek Suggesties Producten Sorteren op relevantie …
• Vinden van klant voorkeuren • Persoonlijke inspiratie
• (Web)Statistiek • Etc.
Zoek suggesties (nu) • Huidige versie: • Gevolgen van zoek acties • Categorie suggesties • Kwalitatief filteren • Spelling correcties • Spelfouten herkennen • Niet succesvolle termen verwijderen. • Schaal • 1 jaar data • 5 systemen parallel aan het werk
15
2013-08-26
Echt volledig automatisch! • •
Zondag ochtend 12 feb 2012: Whitney Houston … Maandag ochtend:
Business effect • Impliciet filteren tegen de product catalogus • “Slechte” zoek resultaten worden niet mee genomen • Betere dekking van de long tail
De suggesties worden vaker gebruikt
3 jaar later …
Recommendations (nu) • Voor de gehele catalogus • 17M producten • Meerdere soorten aanbevelingen • Product Product • Creator Creator • Schaal • >13 jaar order historie • >2 jaar click stream • Binnen 20 uur klaar (op 4 servers) • Binnenkort meer servers
Organisatie impact & tips
Organisatie impact & tips
IT: • Mindset verschuiving • “Data doe je in Oracle” • Laat de pilot door “flexibele” senior mensen doen. • Het is anders • Training en uitproberen is noodzakelijk • Geef de pioniers een stapeltje “oud ijzer” • Standaard “server grade” hardware • Zoek de balans “kosten/systeem” & “aantal systemen”
Business: • Veel nieuwe mogelijkheden • Het maximale data volume is een (financiële) keuze. • Business case is erg makkelijk • De software is gratis • De hardware is standaard “of the shelf” • In kleine stappen opschalen
16
2013-08-26
Belangrijkste “BigData” conclusie
Big Data boeken
Overzicht op
www.basjes.nl
Vragen?
17
