Spark and HyperLogLog: distributed cardinality estimation

It’s been a few weeks since I have started playing with Apache Spark, and as I am getting more serious with it, I will probably use it more in my daily job routine too. However, I have decided to write down a few examples while I learn the basics (as well as learning the Scala syntax).

The first example is a simple cardinality estimator using HyperLogLog. It is a very simple application of the combineByKey( ) function of a PairRDD on Spark.

combineByKey(
  v => {
    val hll = new HyperLogLog(16)
    hll.offer(v.getBytes)
    hll
  },
  (acc: HyperLogLog, v) => {
    acc.offer(v.getBytes)
    acc
  },
  (acc1: HyperLogLog, acc2: HyperLogLog) =>
  {
    acc1.addAll(acc2)
    acc1
  })

I have wrote a simple Python script to generate some sample data and I have run the code using spark-submit. For a 450Mb file, it takes 16 seconds on my MacBook Pro.

Davides-MacBook-Pro:TestSpark davideanastasia$ time ./scripts/launch-hll.sh ./data/dataset.txt ./output-7
Spark assembly has been built with Hive, including Datanucleus jars on classpath
2015-03-29 17:12:23.713 java[17560:1903] Unable to load realm info from SCDynamicStore
15/03/29 17:12:23 WARN NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where applicable
                                                                                                                                                                               
real	0m16.247s
user	0m20.922s
sys	0m0.984s

On the other hand, if I perform the same operation using awk, it does take 36 seconds (for ONE key, not all of them!)

Davides-MacBook-Pro:TestSpark davideanastasia$ time ./scripts/validate-hll.sh ./data/dataset.txt 10 
  192545

real	0m37.445s
user	0m36.937s
sys	0m0.358s

Of course HyperLogLog is an estimator, and in my case I have sized it to only 16 bits. Tuning for the right dataset will actually make the estimation more accurate.

All the code is available at: https://github.com/davideanastasia/spark-experiments
I hope I can add more examples soon.

A new life for this blog

It’s been a long time since my last post on this blog and many things have changed in my life in the meanwhile (I’ll make sure I update my “about” page as soon as possible). I would like to write a lot and talk about all the interesting things that I have done in the past two years. So I think the new phase of this blog will be mostly about coding and photography, even though I expect to talk about politics and other personal matters here and there (with the care that is necessary to avoid problem in the “real life”, because after all everybody can read these pages).

Hence keep an eye on the blog, because I might write something soon… :)

Indignazione. Disperazione. Rabbia.

Update (27 Luglio 2012)

Non credo che serva aggiungere molto a quello che sta succedendo a Taranto in questi giorni. Dopo il sequestro e la misura di custodia cautelare in carcere per 8 dirigenti ed ex dirigenti, si sta tristemente avverando la solita guerra tra poveri: da una parte i lavoratori, che giustamente combattono per il loro posto di lavoro, dall’altra la citta’ (e non solo), che dopo quasi 50 anni di abusi ambientali, vogliono liberarsi del mostro. Ed ho come l’impressione che nei prossimi giorni si parlera’ molto di questa vicenda (anche se La Repubblica, dopo solo un giorno, ha gia’ declassato la notizia a trafiletto sul proprio internet). Ad ogni modo, molte volte e’ difficile per chi non conosce Taranto capire quanto l’Ilva rappresenti un visibile contrasto tra opportunita’ lavorative e sostenibilita’ ambientale. E’ per questo che porto di nuovo in prima pagina questo posto sul mio blog, sperando che i video che ho aggiunto possano essere uno spunto di riflessione.

Salute-lavoro, baratto assurdo: l’amara lezione di Taranto [Videoinchiesta]

Update (30 Giugno 2010)

La procura di Taranto apre un fascicolo per Disastro Ambientale contro i quattro piu’ importanti dirigenti dell’ILVA. E la mia domanda e': quanti anni sono serviti?

Post originale

All’inizio mi disperavo. Ma non ho scritto di getto. Mi sono contenuto, frenato. Poi alla disperazione, come sempre accade, è subentrata la rabbia. La rabbia verso chi non ha rispetto. La rabbia verso il profitto. La rabbia verso il maledetto vile denaro.
Penso a mio padre. Penso che ha lavorato nell’impianto siderurgico di Taranto (adesso ILVA) per quasi 30 anni (o forse più). E chissà cosa ha respirato. Penso a mia madre e mia sorella, che vivono sotto quelle ciminiere e chissà cosa respirano. E chissà cosa mangiano. Poi penso a tutti quelli che stanno male, che hanno avuto un tumore. Che sono morti. E sanno a chi dare la colpa!

Che l’ILVA fosse un’azienda pericolosa si sapeva. Almeno, chi vive in quella zona lo sa bene. Perché basta passarci vicino per vedere i fumi che escono dalle ciminiere con dei colori assolutamente raccapriccianti. Che nessuno volesse occuparsi della questione era anche palesemente evidente, visto che dieci anni fa lo stabilimento di Taranto e di Genova erano confrontabili ed adesso invece viaggiano su due dimensioni assolutamente separate. Per buona pace della salute dei genovesi (beati voi!).

Quando vivi lontano però… lontano dagli occhi, lontano dal cuore. E così avevo “dimenticato” il problema. Poi qualche giorno fa mi passa davanti questo articolo: A 13 anni ha il tumore da fumo. «E’ la diossina». Ed il problema mi ritorna agli occhi in tutta la sua importanza. Non mi era chiaro come mai un bambino potesse avere un tumore da fumo. Poi, come spesso accade, alla conoscenza dei problemi si arriva per gradi. E così LA7, l’unica TV ancora non controllata dai politici fa un bellissimo report di un’ora e mezza su Taranto (nella trasmissione “Malpelo”). Ed alla indignazione subbentra la disperazione. La disperazione di vedere questi meccanismi assolutamente lontani dal buon senso prendere il sopravento ed ammazzare la gente.

Vi consiglio di vederlo. Anzi, non ve lo consiglio. Dovete vederlo e basta! Una ricerca su YouTube dovrebbe portarvi velocemente al video.

Poi oggi apro La Repubblica è leggo che Vendola si sta interessando al problema. E negli ultimi anni dov’era? Quando le parti civili si ritiravano dal processo, lui cosa faceva? Sembra quasi che il suo interesse sia solo politico, visto la presa di posizione pro Riva presa dal governo (o pro CAI?).

Luminance HDR

Not many of you know that I’m a developer of Luminance HDR since this summer. Luminance HDR is a cross-platform software for HDR imaging, with a large number of users and an active flickr group.
Why am I working on it? There are several reasons:

  • I’m an user of Luminance HDR (and the previous version, also known as Qtpfsgui), but I really didn’t like its limitations (slowness, memory leaks, unstable UI, …).
  • I’ve got a little passion for the High Performance Computing (and the vectorization in particular). So I decided to use these knowledge into the project in order to improve the code.
  • I’ve got a Mac and there was no release for Luminance HDR running on OS X until few weeks ago (when I made it!).
  • Using a Mac, I work mainly with XCode. But I also had chance to put my hands on Shark (a performance profiler), Instruments (a memory/function call profiler) and MallocDebug (a memory allocator profiler). These tools are absolutely useful in many fields (and in my PhD as well), so I’m really interested in learning and using them effectively.

Give a try to Luminance HDR and let me know what you think of it. If you like it, you can also consider to make me a donation! :)

U2, Zurich, CH – September 12th, 2010

Almost a month has passed since this concert (the 4th U2′ concert in a bit more than an year for me) and a lot of thing have gone through my life. This concert has been different from the ones I’ve been before. Probably the rain, probably a smaller stadium, probably a different setlist, probably Bono in a great shape, but the concert has been somewhat different. This concert has seen the live debut of “Mercy” and I also had chance to listen a bunch of songs I haven’t listen before. Unfortunately, because of the heavy rain, the Encore was shorter and With or Without You and Ultraviolet/Hold Me Thrill Me Kiss Me Kill Me were not played. I wish they did, but unfortunately the weather was so terrible.

This is the set list of the concert in Zurich, September 12th 2010:

  • Return Of The Stingray Guitar
  • Beautiful Day
  • I Will Follow
  • Get On Your Boots
  • Magnificent
  • Mysterious Ways
  • Elevation
  • Until The End Of The World
  • I Still Haven’t Found What I’m Looking For
  • North Star
  • Mercy (live debut)
  • In A Little While
  • Miss Sarajevo
  • City Of Blinding Lights
  • Vertigo
  • I’ll Go Crazy If I Don’t Go Crazy Tonight
  • Sunday Bloody Sunday
  • Mothers Of The Disappeared
  • Walk On

Encore

  • One
  • Where The Streets Have No Name
  • Moment of Surrender

 I’ve put some pictures of this concert in a gallery and I’ve also published a couple of shot on flickr.
I’m going to talk about Zurich soon, promise!