Big data amikor a probléma az adat mérete maga

„Big data” amikor a probléma az adat mérete maga Benczúr András MTA SZTAKI Informatika kutató laboratórium http://dms.sztaki.hu MTA 2012. május 16.

Big Data – az új divatszó • “big data” is when the size of the data itself becomes part of the problem • “big data” is data that becomes large enough that it cannot be processed using conventional methods • • • •

Google sorts 1PB in 33 minutes (07-09-2011) Amazon S3 store contains 762B objects (31-01-2012) New Relic: 20B+ application metrics/day (18-07-2011) Walmart monitors 100M entities in real time (12-09-2011) Source: The Emerging Big Data slide from the Intelligent Information Management DG INFSO/E2 Objective ICT-2011.4.4 Info day in Luxembourg on 26 September 2011

Benczúr – Big Data – MTA 2012 május 16.

Big Data Rétegek

Big Data Services

Big analytics Fast data


Tudományos és üzleti relevancia • VLDB 2011 (~100 papers): • 6 MapReduce/Hadoop, 10 big data (+keynote), 11 NoSQL architektúra, 6 GPS/szenzor adat cikk • tutorial, demo (Microsoft, SAP, IBM NoSQL eszközök) • session: Big Data Analysis, MapReduce, Scalable Infrastructures

• SIGMOD 2011: 70 cikkből 10 új architektúrákról és analitikai alkalmazásukról • Gartner 2011 trend No. 5: Next Generation Analytics „significant changes to existing operational and business intelligence infrastructures”

• The Economist 2010.02.27: „Monstrous amounts of data … Information is transforming traditional businesses”

•

News special issue on Big Data - április


„Big data”: miért pont most? • A hardver egyre jobb és olcsóbb? • De egyre több adatunk van – éppen az IT fejlődés következtében • Rossz hír a lineárisnál lassabb algoritmusoknak! • Moore törvény (duplázódás 18 havonta) ma már magok száma és nem sebesség! Benczúr – Big Data – MTA 2012 május 16.

„Az algoritmusok rövid története” P, NP

PRAM elméleti modellek

Thinking Machines: hypercube, …

SIMD, MIMD, message passing

Külső táras algortimusok CM-5: sok vektorproc

Cray: vektorprocesszorok

Map-reduce Google Multi-core


Many-core Cloud Flash disk

Őstörténet: P, NP • P: Gráfbejárás; Feszítőfa

15

• NP: Steiner fa

5

15 2

1 2 25

2

1

1

2 1

2

1

1

1 Benczúr – Big Data – MTA 2012 május 16.

1

5

Algoritmus-történelem: párhuzamos fák

• Iteratív minimum feszítőerdő építés • Kezdetben minden csúcs egy fa; minden iterációban fák egyesülnek (Borůvka) Bentley: A parallel algorithm for constructing minimum spanning trees 1980

3

2 1

Harish et al. Fast Minimum Spanning Tree for Large Graphs on the GPU 2009

4 6

5 8

7


Kit érdekel ez még ma?

Képszegmentálás Azonosságfeloldás

name

e-mail

ID

Mary Smith

[email protected]

50071

Mary Doe

[email protected]

50071

M. Doe

[email protected]

79216

M. Smith

[email protected]

34302


1 2

3

Gráfalgoritmusok és elosztott számítási paradigmák

• Distributed Key-Value Store:  



eloszott B-fa index Akár szekvenciális algoritmus pl. Project Voldemort

• MapReduce:  

map → reduce műveletek Google; Apache Hadoop

• Bulk Synchronous Parallel: 



superstep: számítás → kommunikáció → barrier sync Google Pregel; Apache Hama, GraphLab


MapReduce gráfalgoritmusok Map: élsúlyok átadása a végpontoknak

Reduce: minimum élsúly választás

Iteráció, amíg 1 < komponens Benczúr – Big Data – MTA 2012 május... 16.

BSP példa: komponensek címkézése


Kísérletek: azonosság-feloldás Sidló, B, Garzó, Molnár, Infrastructures and bounds for distributed entity resolution. QDB 2011

 

15 öreg szerver, 4GB memory, 3GHz CPU biztosító ügyféladat (személyenként átlag 2 előfordulás) Benczúr – Big Data – MTA 2012 május 16.

Kísérletek: azonosság-feloldás

 


Kísérletek: azonosság-feloldás Összefüggő komponensek HAMA fázisok

Hadoop fázisok

 

Rendezés


Elosztott rendszerek Murphy törvénye Fox&Brewer “CAP Tétel”: C-A-P: kettőt választhatunk!

C

consistency

A Availability

AP: egy replika válaszolhat hibásan

P

Partition-resilience

Végül konzisztenssé válhat – eventual consistency Benczúr – Big Data – MTA 2012 május 16.

Konzisztens hash-elés objektumok n szerveren

pozíció: ax+b mod n új szerver?

pozíció: a’x+b’ mod n+1 ?? szerver Minden objektum a legközelebbi szerverre kerül


Terhelésmegosztás, konzisztens hash

a212: 10.10.10.1 10.10.10.4 10.10.10.3 10.10.10.2 a213: 10.10.10.3 10.10.10.4 10.10.10.2 10.10.10.1 a214: 10.10.10.1 10.10.10.2 10.10.10.3 10.10.10.4 a215: 10.10.10.2 10.10.10.1 10.10.10.4 10.10.10.3

Szerverek véletlen permutációja


Karger, Lehman, Leighton, Panigrahy, Levine, Lewin: Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. STOC 1997

Azonosság-feloldás: erősebb korlátok! 





Halmaz metszet kommunikációs bonyolultsága Θ(n) bit [Kalyanasundaram, Schintger 1992] Következmény: több szerveren elosztott adatok esetén Θ(n) kommunikáció eldönteni, hogy van-e duplikátum! Javasolt módszerek: „Blocking” [Whang, Menestrina, Koutrika, Theobald, Garcia-Molina. ER with Iterative Blocking, 2009, stb.]

 

Legjobb esetben is minden adatot ki kell cserélni Kapcsolódó terület: Locality Sensitive Hashing  

nincs „minimum”, azaz koordináta egyezés LSH hasonló a Donoho Zero „norm” (nem-0 koordináták száma) negatív eredményekhez Sidló, B, Garzó, Molnár, Infrastructures and bounds for distributed entity resolution. QDB 2011


Összefoglalás • Big Data részterületei • Számítógép-architektúrák– processzor tömbök, megfizethető nagyon sok magos eszközök • Algoritmusok – tervezési elvek a 90-es évekből • Adatbázisok – elosztott, oszlop-orientált, NoSQL • Adatbányászat, Keresés, Gépi tanulás, Hálózatok – az alkalmazási területek

• Algoritmikus gondolkodás és szoftvertervezés • Korlátok, hibatűrés, adat és számítás-intenzív feladatok • Sok kiforratlan alternatíva (pl. BSP) Benczúr – Big Data – MTA 2012 május 16.

Kérdések? Benczúr András Laborvezető, Informatika Kutató Labor http://datamining.sztaki.hu/

MTA SZTAKI [email protected]


Big data amikor a probléma az adat mérete maga

Recommend Documents