2013-09-09
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-09-09
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-09-09
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-09-09
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-09-09
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-09-09
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-09-09
“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-09-09
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-09-09
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-09-09
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-09-09
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) Offer • NoSQL (Not ONLY SQL) • Kies verstandig afhankelijk van de situatie • Praktijk: Hybride landschap!
Een partij bied een product aan voor een bepaalde prijs / kwaliteit / levertijd.
11
2013-09-09
Business wens: Sorteren
Soms heel veel offers
2844
Offers sorteren (1/4)
Offers sorteren (2/4)
• De offers: • Klaas: 15 Euro, 2 dagen levertijd • Piet: 10 Euro, 5 dagen levertijd • Jan: 20 Euro, 5 dagen levertijd
• Zet bij elk offer zijn “Array index”: • Klaas: 15 Euro, 2 dagen levertijd 1 • Piet: 10 Euro, 5 dagen levertijd 2 • Jan: 20 Euro, 5 dagen levertijd 3
• De uitdaging: • Sorteer de offers op “Beste koop”
• Gevolg: • Klaas verwijderen alle andere offers worden ook gewijzigd. • Per product alle offers op 1 CPU. • Heel veel updates in het landschap.
Offers sorteren (3/4) • Werkelijk gebruik: • Select
• Where • Order by <Sorteer getal> • Limit
Offers sorteren (4/4) • Zet bij elk offer zijn “Relevantie”: • Klaas: 15 Euro, 2 dagen levertijd 333 • Piet: 10 Euro, 5 dagen levertijd 22 • Jan: 20 Euro, 5 dagen levertijd 1 • Gevolg: • Als we Klaas wijzigen/verwijderen dan hoeven we maar 1 offer aan te passen. • Per offer verwerken op een CPU. • Veel minder load op de systemen.
12
2013-09-09
Unstructured data? Unstructured Data refers to information that either does not have a pre-defined data model and/or does not fit well into relational tables. Unstructured information is typically textheavy, but may contain data such as dates, numbers, and facts as well.
Un-/Semi-/Structured data? • Unstructured • Twitter berichten • Datum + willekeurige text. • Sentiment heel veel rekentijd • Semistructured (non relational) • Webanalytics • Datum, URL, browser, campagne. • Geen transacties, BASE • Structured (relational) • Klanten, Orders, betalingen • Transacties, ACID
[1] : http://en.wikipedia.org/wiki/Unstructured_data
Data horizontaal schalen?
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 Google paper uit 2004 “MapReduce: Simplified Data Processing on Large Clusters”
What did Google do?
What did Google do?
13
2013-09-09
What did Google do?
Is dit betrouwbaar?!?!
Data verspreiden (HDFS)
Map Reduce
Client
Client
Input 1 bestand 2 3
JOB
1 Server 1
Server 2
Server 3
3
Server 1
Replicatie factor =2
1
2
Server 2
2
3
Server 3
Replicatie factor =2
En toen deed het … BOEM!
MapReduce processing model
Client JOB
• • • • •
1
3
Server 1
1
2
Server 2
2
> 30 jaar oud Alleen voor Batch verwerking Eenvoudig Horizontaal schaalbaar Kan in alle programmeer talen
3
Server 3
Replicatie factor =2
14
2013-09-09
MapReduce: basis idee • Map (Transformeren) • 1 Input record omzetten en “groepeerbaar” maken. • Input: “Input regels” • Output: Aantal (“Key”,“Value”) paren
Woorden tellen Map Split
Shuffle/ Sort
Reduce Output
Input
• Reduce (Groeperen en Aggregeren) • Alles met dezelfde “Key” aggregeren • Input: 1 “Key” met een aantal “Values” • Output: De records die gewenst zijn.
Ketens van MR jobs
Zoeksuggesties • Stel we hebben 3 zoek acties: • “Hadoop” • “Harry Potter” • “Harry Potter”
Zoeksuggesties: Map 1 • Input: • “Hadoop” • Map • K: “Hadoop”
V: 1
Zoeksuggesties: Map 1 • Input: • “Harry Potter” • Map • K: “Harry Potter”
V: 1
• Input: • “Harry Potter” • Map • K: “Harry Potter”
V: 1
15
2013-09-09
Zoeksuggesties: Reduce 1 • Input: • K: “Hadoop” V: 1 • Reduce: Totaal scores per term • K: “Hadoop” V: 1
Zoeksuggesties: Map 2 • Input: • K:“Hadoop” V:1 • Map: Knip in stukjes • K:“H” V: “Hadoop”, • K:“Ha” V: “Hadoop”, • K:“Had” V: “Hadoop”, • K:“Hado” V: “Hadoop”, • …
1 1 1 1
Zoeksuggesties: Reduce 2 • Input: • K: “Ha” V: “Hadoop”, 1 • K: “Ha” V: “Harry Potter”, 2 • Reduce: Neem top 10 (Sort by Score) • K: “Ha” V: {“Harry Potter”, “Hadoop”}
Zoeksuggesties: Reduce 1 • Input: • K: “Harry Potter” V: 1 • K: “Harry Potter” V: 1 • Reduce: Totaal scores per term • K: “Harry Potter” V: 2
Zoeksuggesties: Map 2 • Input: • K: “Harry Potter” V: 2 • Map: Knip in stukjes • K: “H” V: “Harry Potter”, • K: “Ha” V: “Harry Potter”, • K: “Har” V: “Harry Potter”, • K: “Harr” V: “Harry Potter”, • …
2 2 2 2
Hadoop MapReduce • 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, …
16
2013-09-09
Hadoop Ecosysteem
Van concept naar praktijk
Klein beginnen
Laat zien dat het schaalt
Laat anderen het proberen
3 weken webdata in 25 minuten!
Job Status: Succeeded
17
2013-09-09
In productie nemen
Waar ligt de grens?
• Het productie cluster • VM Master • 5 Workers systemen • 2 CPU x 4 Core • 8 Disks * 450 GB • 32GiB Ram
Op een paar duizend servers!
Business impact
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.
Echt volledig automatisch! • •
Zondag ochtend 12 feb 2012: Whitney Houston … Maandag ochtend:
• Schaal • 1 jaar data • 5 systemen parallel aan het werk
18
2013-09-09
Business effect
3 jaar later …
• Impliciet filteren tegen de product catalogus • “Slechte” zoek resultaten worden niet mee genomen • Betere dekking van de long tail
De suggesties worden vaker gebruikt
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 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”
Organisatie impact & tips 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
19
2013-09-09
Belangrijkste “BigData” conclusie
Big Data boeken
Overzicht op
www.basjes.nl
Vragen?
20
