Oscar Boykin, Counting Approximately at Scale: SF Scala @Twitter 20150106

Oscar Boykin, Counting Approximately at Scale: SF Scala @Twitter 20150106

Recording: Oscar Boykin, Counting Approximately at Scale: SF Scala @Twitter 20150106

is about um aggregation in general and this concept of aggregators uh both in a specific sense and in the general sense that scalding and summing birth are both aggregators i will talk today about both summing burden scalding what they are what their a little bit about what their history was and uh how they fit together i won't talk as much as i want to thank alexi for organizing this and also travis for doing a lot of work uh to to get us all here tonight i won't talk as much in the slides about the actual mechanics of how we use it at twitter um i'm happy to i'll leave some time for you to ask some questions about it i'll try to talk about that a little bit because i heard there was some interest about it um but i can i give you a little bit of a spoiler alert that the fact is twitter is pretty big now and so i'm getting more and more myopic and so i'm actually like surprised that people actually i didn't know people ran this code we just write it and uh send it out to the ether and like apparently it's occasionally useful so i'm oscar boykin uh pasco i'm at twitter um so first i'm gonna tell you a little bit about what scalding is if you haven't heard of it before and what the history of it was um and um i i think it's interesting if you're starting a new project to uh to to hear maybe what the history of scalding was because it wasn't very ambitious honestly uh in some sense so avi bryant who's here uh uh really hated working with pig okay so uh so he's here at twitter he was acquired uh from another company uh they are forming the the new analytics team at twitter and pig was not expressive enough it's a pain to write uds you have to uh switch lane and the language is just kind of it's it's bad news okay so he was aware of this work uh probably he can talk more of it uh about what he was aware of other than just cascading but there was this project called cascading by chris wenzel and it's you know it's like you know i i don't know how like like kid gloves i'm supposed to be like so first of all i don't like scala as much as alexi does so you know it's just like democracy you know it just like it just sucks less than most of the other options okay so like java like i don't like hate java and love scala it's just that like java is just much worse okay so this was like who would want to program this way there's a number of problems here like there's like mutation going on all the time like it's kind of a weird pattern there are no types anywhere the compiler can't tell you if your your aggregation is correct at all and then you go to run this job and maybe it's going to run for 10 hours and then at the end you're going to get a cast class exception and it's a total bummer you know so like that like that you didn't i didn't like um so it makes you know cascading though it like it works you know it works really well so it has a pretty good optimizer but like i don't really want to write code this way and avi didn't want to write code this way either so so that's a pain not so great we all know that you know java can be verbose i don't know if you've seen like fizzbuzz enterprise edition but this is a real project you can check it out on github and uh you know it's like this is a disaster you know like this is not what you want to be doing i mean you're at work a long time you don't want to be coding this way you know so uh scala has a big fan base within twitter and i would say actually that fan base has been growing but slowly actually a lot of people maybe think that twitter um like really loves scala in this way but at the time that scalding started um there were a lot of factions within twitter people who really liked ruby people who really liked java and there were many people who liked scala i would say that as time has gone on we're doing less and less ruby almost no ruby now virtually no ruby java doesn't grow that is not growing as rapidly as scala so scala is more and more becoming the dominant language at twitter i would say is but you know we have a lot of java okay so i dug this up at one point in time here's the first commit to the the repo that that's called livedin so it started on um well this code at least avi can tell you more about it it's kind of weird that i'm giving this like a little bit of history that avi could just tell you like i i this is two weeks before i showed up um and there's some code there's you know a few hundred lines and that's the sort of scalding so what is scalding all about so this is me and argeris the good old days uh back in ancient 2011 so we joined we worked on scalding and really quickly one thing that was interesting is that we like scalding initially really much pretty much sucked you know it was like we needed to do some quick aggregations and we did something that worked okay and we wanted to use scala because we could use our udfs right in line so if you're new to the scala programming language um i don't know how much you're going to enjoy my talk i just try to like drink more and like maybe make a few more jokes but if you use skal a lot like it's nice that you can use the udfs directly online and not have to switch to another language not have to like write sql and then write c code somewhere else um you have one build system to maintain everything so that was all really nice um we got it working relatively quickly so the first code was in may and then we had a pretty good yes okay i've asked people on both sides and i don't know what it is oh sorry uh user defined function so um imagine so if you're if you're working with databases like if you're if you're used to sql maybe you think like the world like you you know there's integers and then there's like array it's so weird i mean people work with sql now like what's wrong with sql and then it's like what if i tell you in your programming language you can only work with integer strings and like uh yeah i don't know like like floating point numbers you'd be like are you [ __ ] crazy like i i can't get anything done with that but some people like really accept that when it comes to analytics and aggregations they did they weren't looking at it in my view critically enough at that point the idea that you would want objects and aggregate objects rather than aggregating uh just like numbers or strings or even tuples of numbers and strings um like at that time like wasn't really that much done it was like you know just use pig it'll be fine and it can just do these few type data types so in pig it's sql-like sql-ish it's not exactly sql it's not it's not even that close to sql but it's sql-ish but if you want to change some function like maybe you've heard about some cool approximation algorithm that is going to approximately tell you something that would have been very expensive to calculate otherwise if you want to use that within pig you're going to have to drop into java code or some other jvm language and write this code that enter that implements a few of these interfaces that pig sets out for you and that's a total pain because you thought everything was cool and you had this text file and you could just run pig on it but then all of a sudden you have this huge impedance mismatch that as soon as you want to do something slightly custom you've got to fire up an ide and like have java code gin and like scala you know sorry don't do scar uh the the the check styles every everything's going crazy so it's a totally different workflow anyway that's the udif please interrupt me uh with questions so when we released this code it wasn't like like super great but it like worked it worked it did what it like claimed to do so some people like like i think that was really great like later i'll talk about something bird which is like the other end where like perfectionism got the better of us and uh we just like like took way too long so i can be really uh self-critical about like that whole process so scotland was working great everything was awesome it started out as a dsl for cascading and then it evolved into a really you know i'm really happy with the api now it's a very nice type safe distributed collections api so if you know scala collections you can pretty much take your knowledge of scholar collections and put them onto uh hadoop and and and process you know terabytes you know maybe exabytes data and uh it's just it's just gonna work you know it's almost never like it's not gonna out of memory it's not always gonna be the totally fastest thing in the world if it compiles it's almost certainly gonna run uh like uh it might not logically be what you want because you know it's uh you know we don't have some perfect programming language that if it's compiled as correct uh but it's it's it's pretty nice it has a lot of optimizations a lot of the obvious things that you might think should be done it knows about um so at this stage it's really nice so here's you know just a sketch of what it looks like and i'm really this isn't really a scalding tutorial that will tell you much about scalding there's plenty of resources like that on the web if you like but um and even uh even this is like we've added some like little polish that i think it makes it a little nicer but here's the canonical word count example so uh you can write your your your code inside of a class that subclasses job you don't have to do that anymore there's a really nice way to run scalding as a library just at any point in your code and call some scalding function and it'll go out to your hadoop cluster and run but a canonical example is to run it as a subclass of job and uh this is like this kind of very standard kind of java programmers call this the fluent style but it's not uncommon at all in scala code to see this like dot chaining where you're taking one result and feeding on and in this case we're loading a text line which is a source that represents some input data uh we're applying flat map and flat map if you're really i don't know who's like super who's like in the like scholar z like camp of the super functional programmer like i like i kind of like you know yeah so if you're into that like there's like three of us here like i'm actually i'm not in that camp i'm very sympathetic to that camp but i try to be like more zen about life so um uh like flat map is not so if you're into moan ads flat map on the t on in scalding is not the monadic mind okay so um and then the scholars see people like we should have this debate sometimes they're like what that's some [ __ ] but where does it say that in scala that flat map is the magnetic bond it actually doesn't and like plenty of scala apis violate that thing anyways what flatmap does in scalding is what it does on like collections so if i take one thing i can map it to zero or more things this kind of concept if you're into the scholar z world it's cliestly composition on like basically list or stream okay so that kind of operation composes really well and it's a very common thing in analytics so if you imagine that scalding is representing like a type table so you have a you know we you know it doesn't appear here but we have a type that's called typed pipe it's very similar to the rdd type and spark you can imagine each map operation or each flat map operation or filter is creating a new virtual table that not all those tables will be materialized that would be very wasteful but one way that you can make a new table from an old table is line for line changing each row to another type of row right and that's what map does and another way you can make one table into another table is to filter you can say i'll take not all of these rows but some of them but another concept that i think was really like not noticed before scala got into the picture of a mapper of mapreduce with hadoop is that like flatmap is really what hadoop is doing so when they say mapreduce it's really flat map reduce and what flatmap what that means is that with flatmap you could have implemented map you could have implemented filter but you can also implement something else was i can take one row and send it to five rows or this other row is going to go to zero rows so it's a more general concept it's very useful anyways this word count so uh i know like we shouldn't be as a community so down on word count because actually like most of what we do really i'm sure lexi knows like when you're you're trying to be fancy you've got your big data science title but really you're just counting [ __ ] you know like that's all we're doing you know so like let's not be so down on word count so in scalding um there's uh like like this got on my nerves so we actually cleaned that up a bit we added a new thing called some by key but you've got your data you say let's go to the reducers that's the method called group so at this point notice we've got a key and a value in this case it's a word so word count we're going to take each item in our sentence our key is going to be our word and the value is just going to be the number one we're going to group those which means every row that has the same key is going to land up in the same bucket and then we're going to sum so every every operation we do on a group it looks like reduce operations reduce if you're a scholar person we've got fold left we've got scan left we've got um head we've got last we've got men we've got max we've got like almost anything you can think of or you can just plug your own thing in you can give me a function that will take an iterator and return a new iterator and you can do something totally general but this is like the obvious thing and the one of my favorite things you'll hear about later i think in ian's talk is sum is like totally general like like we can sum sets together how would you sum two sets together union totally knows that how would you sum two maps together okay so how would you merge yeah you're like for each key that's the same we bring those together and then we call we merge we do whatever some would be on the values and like this all works recursively and if you're not down with type classes like you should get down with type classes i'm just gonna i'm just that's all i'm gonna say okay so alexis really wanted me to talk about the twitter analytics stack i'm gonna do that here's twitter analytics actually i'm going to totally lie i'm only going to talk about yes i have a quick question about the previous slide yep so you have a bunch of logic processing data in there yeah and then there are two methods that seems to be operational yeah yeah so what's yeah what's going on with that the answer is like i don't know you make these slides and then you like copy and paste some like random like unit test which is what this was and forced to disc uh you would almost nev you you almost never use that but that's a method it's an example of there's a couple of things so when you're working with a high level language a lot of people will say well that sounds pretty good but i don't really know how it's going to work how is it going to run on my cluster how can i control that so there are a few things such as force to disk forced reducers that will at least at that point disable some of the optimizations that we're doing so if you're saying like i know for a fact that this filter is going to filter out almost everything i don't want you to combine it with the following flat map that might expand it back out i want to go ahead and at that point right materialize it to disk users don't usually need to do this but when you're really tuning and you're talking about jobs for twitter where it might be a 10 hour job in some cases or in some cases more the ability giving the user the ability to control the plan if they really need to is nice it's not a great example to put up here because it has too many concepts and it blurs like the simplicity away um that's because i'm a shitty speaker so okay so so what's up with the twitter scholar analytics stack so um i think hearing i'd like to talk about it more he was actually more interested in like the behind the scenes and how the bits actually move around but i totally misunderstood that and i'm going to tell you about our open source stack and how that all fits together um so that's what we're going to do now so scalding as i mentioned that was the history where it's called to come from and it was our first scala big data project okay so it's like scala collections for hadoop and really happy with it it works awesome it is amazingly great if you run with it it's gonna work for you full stop totally battle tested we probably have a thousand jobs in production totally works don't worry about it it works okay anyways moving on from that so sam richie and i uh started working together he was also here at twitter um and we looked at scalding and we started being interested in the problem of real-time streaming so scalding is totally hadoop it's uh i mean you can run it locally not using hadoop but it doesn't really address the like the the the sparks streaming case or storm so at that point in time uh storm uh which is a project which you might be aware of uh was acquired uh by the company back type was acquired by twitter so nathan mars was here and i was interested in storm but i was like you know what those types are awesome and scala while shitty is much much better than like having no types so we should actually have a type safe way to program a storm so this was something that we really wanted to do and after having done scalding we thought we could do this so then we got total ocd and locked ourselves in like a hole for like a year and like polished and like over designed uh but while we were doing this various things came out so the first thing that we we produced was chill which was is a serialization library has nothing to do with scalding you can use it elsewhere people use it with aqua they use it actually spark uses it so it's a serialization library for jvm types it serializes like almost any scala type it's it's really nice it's not type safe serialization so it can so that's both good and bad it can take any data that you hand at it and it will do a usually a very very good job and a lot all our data at twitter goes through this uh when they're passing database mappers and reducers and we almost never have a problem uh very happy with it why am i hedging a little bit because it's not type safe and i'm like sword in the scholars e camp so i'm like it gives me some anxieties but all right it actually it doesn't cause a problem so then there's algebra so that is like so because i'm kind of in scholars ecamp we had to have our own like algebra library but actually so algebra was a library that we built to ac to generalize aggregations so we wanted to model aggregations in an algebraic way that was very nice that we could use from this new project that we were working on which was called something bird so we started to peel these things out so that was really great algebra is amazing you're going to hear more about that later one of my colleagues ian is going to talk about it now the next thing because we had all these ocd complex and we were like staying up late at night not sleeping about like type safety we we had this library bijection and it turns out there are these couple types bijections and injections that are really useful for serialization so basically an injection is a bijection is a function you have a pair of functions that go between two types so you can go from t to u and u back to t and it always works and that's all bijection is and that's what this type gives you but the nice thing about this is that they if you're into the skull of z see i'm not i'm like going off the deep end with it they form a category so you can glue these things together they compose really well if you have a bijection from a to b and a bijection from b to c clearly you can glue the two together and get one from a to c right you can start drawing these diagrams and an injection is almost the same thing except you can always go from a to b but b to c might fail and that's serialization if i have some data object like you know a tweet record that has like an author in the text and like the time stamp i can always turn that into bytes but if you give me some random bytes i can't always go back into a tweet record like some of them might just be like empty bites or there might be like only one bite and it's really not a valid record so that's an injection so we developed that library that became very useful for us ultimately the other day we didn't force type safe serialization on everybody because it turned out they hated it and so we stayed with chill storehouse was a library that we built because we wanted to model we were building this uh summing bird uh which you'll hear about in a second and something bird was again our real time scalding but we didn't want like like hadoop has these output formats so we needed to be able to the real-time output format is like a key value store like i need to be able to update something but like because we're just writing code we don't really like to run it um we just wanted some abstract trait that we could just jam in there and like some other person could go figure out how to actually do that and that's what storehouse was it's like you know it's going to look like this and it can merge and do all these fancy things and then a bunch of people implemented like storehouse hbase storehouse redis storehouse memcache sore house dynamo db so we can easily plug in these kind of key value backhands and again these things compose really well so if i have two key value stores that both have the same key type i can glue them together that makes it look like one virtual key value store and that's what storehouse is all about basically it's all about you know composition combinators we're just wasting our time and lives making combinators so finally when all this was was was built up we were ready to release something burden something bird is a real-time streaming version of uh scalding uh with a really nice way to make sure you don't screw things up when you're running in real time so it's it's it's extremely nice now that having been said avi bryant made the following tweet which i thought was kind of amazingly uh accurate which is that it's kind of uh the apex predator of the data infrastructure world like the the existence of it then like is evidence of this thriving ecosystem underneath so it does all these great things for you but the problem is it like does a lot of things so like at twitter it's like cool because we have the memcache team and the storage team and this storm team and like they're going to manage all this infrastructure for you uh when you're at a smaller company and you have to you you see how many pieces you have to be running to run a real lambda architecture system which i'll describe in a second it's actually a little bit challenging so something bird is a lambda architecture system it's an idea that nathan mars was very excited about and he came to twitter and i heard about it and i wanted to make it more formal so i i thought that he was kind of vague about it and i uh worked with sam to make it very precise using this algebraic library that we had this algebra library but what it allows you to do is something bird you can write these real-time jobs that run both online in storm and offline they can use scalding or hadoop and so you can write the job one time literally like no no joke and like take that same function and render a job that can run in many different platforms we've had like spark platforms that we've implemented like we don't run spark in production very much we just play around with it right now so we haven't like pushed that too much but you can find that on our github project um we had an akka back end um you know there have been some other ideas there's like two in-memory ones one that uses like a few scholar futures one that just like runs in one thread so it's relatively easy to write a planner but the way our data are our real time to alexis question earlier we have these services and they're running and they're serving all the tweets and you're making a tweet you're talking to the service and as an afterthought there's this exhaust of these services and these this exhaust goes and gets pushed onto kafka cues so we use thrift a lot here so the request comes in i've got a thrift object the response goes out i've got a thrift object just jam both of them onto the wire and it's on a queue somewhere and now as far as the service is concerned it's done with life and now analytics load can begin so we take that cue put it onto hdfs every hour here's another file got another uh chunk but also we can consume that queue in real time from we use storm here and so uh we have this we just pull off the kafka queue we take another data record and start pushing it through these these analytics topologies that we have that are really just these big scalding-like functions now what's the lambda architecture have to do so it's really hard to make a transactional real-time system i don't know if you tried to do that so you have data duplication you have data loss it's extremely hard to deal with but you also don't want to like totally give up the idea of correctness so the lambda architecture the idea is is that you try to do something fast you have the speed layer and then you have this transactional like batch layer that's slower and then you like somehow merge them together now that's like sounds kind of hard like how do you do that in general so what something bird allows you to do is it constrains the rules more but if you follow those rules it will merge them together for you and it will get it right so the way that works is that the online portion is going to keep track of like things in like time in like little bounded buckets and one bucket will not talk to the next bucket you control how big those buckets are if one of those buckets gets corrupted it's fine because we're going to come back and replace the total correct data record up to that bucket up to and including that bucket offline and then we have a way using algebraic and storehouse to combine the most recent bucket with the last transactionally correct bucket offline and you don't have to worry about that so that's been a pretty big win we deploy it works well so what it means is when things go down and we lose a little bit of the speed layer it's okay um like in an hour or two we're gonna fix it back up as far as your question like how does this affect uh twitter right now only a few properties that only a few things that you can see from twitter.com would be affected by the analytics pipeline so we're starting to roll out you might have seen some tech crunch articles like some stats that that are related to um aggregations on uh metrics around your tweets there's also a product that ian will talk about a little bit about seeing which news articles pointed to a tweet these are aggregations that are done with something bird but a lot of the aggregations of something bird are really generally powering either feature detection for machine learning so we're building all we're doing word count over and over again we're counting all the things and then we're feeding that into a logistic regression that might be ranking like discover or who to follow or ads so that's more of what it or it might be awareness for us just situational awareness of what's going on with twitter so um so something which is confusing on number levels it has this like it forces you into this one way of thinking like aggregations have to be like algebraic um it's this portable mapreduce streaming mapreduce model so you could be like oh i don't really care about lambda architectures but wait a second i can write one bit of code and run it on spark and hadoop and and storm and also it's that whole land architecture thing so i think it has a little bit of this like uh it's like a it's a hard sales thing to explain so i'm just kind of like telling you my i'm lamenting here that it's hard to sell uh outside of twitter inside of twitter it's been great but uh avi's tweet pretty much describes the situation yeah this end means so yeah i guess that that slide got messed up so it's like a portability layer and this like uh and the uh lambda architecture implementation so that's what it should be so a lot of people say i don't need a lambda architecture implementation therefore i don't use something bird thing or other people say like actually i would love to be able to write my code once and run it on hadoop and and and scalding like that or sorry and uh storm in in hadoop and so like but i don't know if i need you so i don't know when when a project doesn't do one thing it's kind of a hard thing to explain to people i found yes so we're speaking about real time in terms of summing word and twitter what's the actual window we're talking about so that's a that's a good question a lot of people yeah so so yeah it's a question what do you mean by real time so one thing something very different than like like compared to other systems that talk about uh streaming like so something bird is strictly streaming meanings that each data record gets pushed all can you could in principle push it all the way through the topology before you process the next record in principle so some things get really confusing i'm going to have this rolling batch window this batch window is going to do these little things there's no notion of this in summing bird so he's extremely restricted for that so it's like you can only push through one thing at a time at first here's the problem you you talk to systems people they're like let me give you anything you want you want a window sure i'll give you a window what else you want they're going to keep trying to give you what you want but i think there's a real power in constraining the model like we don't give you the window but because we don't give you the window there's a huge amount of optimizations that we can do and we can schedule this these topologies on hadoop and storm and make them consistent between the two and we found that it's not really a barrier people say they want a window generally there's another algorithm that doesn't need the window and we we get by it and it's it's very scalable as a result of that your next question that you might have hinted at was what's the time between the the law the log event being written to the kafka queue and it changing some say memcache store that depends on because this because something bird has a lot of optimization options you can choose how much caching you're going to do on the inter so we don't require like logically there is there's no batching but for caching you might enable some of it along the way so your algorithm doesn't rely on the batching but we might be doing some caching and batching and like like pre-aggregations so the more aggregation pre-aggregation you do and the larger caches you enable the more you're it's a latency throughput trade-off so you lower your through the you you raise the throughput of data you can handle at the expense of greater latency so different people are operating at different points on that curve so i would say the average job maybe is like on you know seconds and some of them might be 10 seconds delayed yeah who who has the knobs for tuning that is it the operation guys or is it the application it's a little bit i mean it's both so the application people can tune it like i would say actually right now there may be too many knobs and one of our goals is to make it more self-tuning but also our our operations people and our sres can look at the jobs and make recommendations and redeploy them relatively relatively easily okay so part two i'm i'm gonna i'm running out what's what's my time looking like okay a lot of time you guys are like oh [ __ ] man he didn't just say like just like calm it down okay so let me talk so i'll talk i'll show you one example of what scalding really looks like actually like let's do the sexy stuff let's not do that so here's a job that like if you so now so that was something ridden scalding history like what our stack looks like now we use it a lot i'm going to show you one example before i go on to like the last part of the talk so uh clustering so you have a bunch of books you want to find out some similar books to each other based on the text corpus or you have a bunch of tweets and or users and they each have some following graph and you want to look at similar users based on their following okay so this is a very very common problem you can use it in ad targeting you can use the recommendations you can just use it in social science maybe you're just interested so here's how this might look in a reasonably idiomatic and nice scalding job i would i would say reasonably because usually when we're in scala we like to avoid some of the type hints and arguis who wrote this uh put in more of the type-ins uh so it's less confusing but uh i don't i don't know i'm into the confusing thing so so this job is going to read some input data and that input data is going to it's i guess in this case it's a as you can see it's a tsv that has in the first column assuring in the next column along okay so you see he as he maps he's going to name what those things are so first he's going to map them over so he's got his first table it's a it's a simple like think of it as sql table with two columns and he's going to map it onto a new new table and that mapping is the first column is he's calling it uh item id uh so that string in this case i guess is like the id let's imagine it's a user it's a it's a amazon product id or it might be a twitter handle like you're following you know user you know x and then there's user id which in this case is represented as a long so here's a user that has an edge to some product okay or some item now we're going to use this fancy algebra stuff uh that avi was excited about this algorithm from the shortly from probably for for a long time but i remember when i interviewed with with twitter almost i remember him talking about this algorithm so he's always been interested in minhash as an algorithm for approximate similarity so uh you take this minhasher and what menhasher is going to do is it's going to represent like it's going to create from your item like a signature that is not a full representation of the data but it's like an approximate set if you will it's sort of like an approximate set and this approximate set will tell you like sets can tell you a lot of things exactly they can tell you how many members are in your set they can tell you if a particular item is in your set but they can also tell you an intersection or union size and what what minhash tells you is the ratio approximately of the intersection of two sets and their union sometimes this this ratio is called the jaccard similarity so if we have two sets that have nothing in common their intersection is zero their union is non-zero therefore their jaccard similarity is zero uh if you have two sets that are identical their intersection is the whole set the union is the same whole set so their jaccard similarity is one so this is a number that goes between zero and one and when it goes to one it's more similar so a minhash object this minhash signature is like an approximate set but it can only answer really one question for you and that's that jacquard similarity so in algebra we have this no need to write this fancy algorithm you can like go get your promotion and tell everybody how you're a big fancy machine learner just by import algebra.minhash you're good to go okay uh you group it up you sum them together remember when i was talking about how like sculpting just know if you add things together what should that mean right and it it means the correct thing so it does that with like if you knew your scala you got your implicit type classes going on boom it just works so we add up all these min hash signatures for all these items so now each item has a like this min hash signature associated with it okay and it's like a union if you will so again with set adding two sets together we said that was union and remember i said minhash signature is like an approximate set right so it's an approximate union it's a it's a union on this approximate set that's what sum is here now what we're going to do is uh this minhash idea it has this notion of like you can get these signatures out so that's a technical detail the algorithm that i don't really have time to go into uh but anyway the idea is like it can give you some signatures that are ids that would be similar to it it's like if you have a hash code i'm sure you're all familiar with a hash table if to put something into a hash table you have to have the hash code what if i give you an algorithm that gives you like five hash codes and i'm gonna put you into five buckets and with high probability anyone you're similar to would be in those buckets very high probability and you can tune the number of buckets to increase that probability so the minhash algorithm does that i don't want to like go into detail on this too much but after we create these buckets and the indices like for each of these hashes we again just add them all up and now what we've got on the value is the set of strings and the minhash signatures that went into each of these buckets so finally we've got we're just going to expand all these things out once we've got them together we've got the uh the bucket id and the index that went in but actually this code disregards it i'm not really sure why our gears chose to write it that way but we have this pair the set of strings and men hash signatures that landed up in those buckets so we have a bunch of buckets and in those buckets we've got little bags of like here's a bunch of approximate sets and the names associated with them and now all we do is we do the brute force check for all the items in those little hashed buckets like they should be similar if they're if they're similar they'd be in they'd be co-located into a hash bucket and all we do is for each of those hash buckets look at all pairs so get everything out for the a 4b let's just brute force and see what the similarity is now this is approximate similarity because remember that's what the min hash does it gives you an approximate jaccard similarity like approximate set union approximate intersection that's what's going on um and if that similarity is good and you're not similar to yourself emit it and this is like the real deal like you can actually run this in like one page of code and you've got like a pretty good like like search now of related items just on an input graph generic input graph really super nice that's what scalding is all about boom so um you're going to hear more about algebra but that's what enables a lot of this and this minhash gives us this approximate set similarity so ian's going to tell you about hyperlog log and countman sketch which can do even more fancy stuff like that all ready to go the last thing that i really wanted to talk about was this because like like like i like to make fun of this called z people but only because i envy them because they get to live in this pure functional world that's so beautiful and so uh this is what i'm excited to tell talk to you about so when all this is going on it's like man there's a lot of patterns here and every time you see a pattern that like if you repeat yourself you start like like wait a second i'm missing something i'm not understanding it i should be able to find some unifying concept and not do it all over and over again and so i'm going to tell you about a pattern that we noticed super early and then avi named it uh and we put it in algebra and it just kind of sat dormant for a while and obviously i take the honestly i think the blame like i was like yeah it's okay it's usable it's not that great but then recently somehow we noticed like man i've really been missing the boat here and this is an amazing beautiful abstraction so i want you to walk away if nothing else then scalding is the most amazing software ever written and you should really try something bird if you take nothing else away from my talk take away this idea that there's this concept called an aggregator which i'm going to tell you about which will work for you regardless if you're using something bird scalding spark in local memory just talking to people at the blackboard because you don't run code you just write it so let's suppose you're faced with the problem of getting the size of this list here's a linked list it's got seven cells it looks like and i just chose some totally meaningless numbers okay now uh the way that we would do this in mapreduce is we would map i want to get the size right so i map each of these items over to the number one so i throw away what's in the list i've got the number one so that's map x to one and then i say reduce by applying you know just take a pair and add them together so the awesome thing about reduction right is that it enables a huge amount of parallelism because the contract of this reduced function should be that it's an associative function that means i could be doing this pair while i'm doing this pair while i'm doing this pair and the late the depth of this tree becomes log of the number of things that i'm aggregating so great i've got the size so i got two here then i got some other node got two here and two here and we combine them we've got the length of this tree is seven great so what if i rather than map reduce as two separate ideas and i like i said we're assuming our reduced functions are associative in this way uh i feel like i talk about associative functions by now like even like my mom's got like a really good handle on it so i don't know if i should really be saying it anymore but like there it is okay they're called semi groups also so just i don't know if you hear the word semi-group it just means there's an associate function so rather than mapreduce what we really want is like an object that talks about map and semigroup in one abstraction and maybe that's what we mean by an aggregator but let's imagine we instead of one of the size we want to get the average of these things so to get the average of this list we might do it this way to get the average we need both the count and the total sum so we need to do two aggregations at the same time but then finally we need to do something with them so we could do it this way again mapreduce we we can map each x onto the tuple of one comma x so now i've done that here one is the count and x is the value and now because the natural sum they just remember how we just like know like the the sum of a tuple would be the point wise sums just like we all just intuitively know the right way to do things um so we reduced the natural way by the way uh algebra knows how to do this so if you have nested tuples of tuples of algebra maps of sets of tuples of whatever and just like call semi group plus it will just magically add all that together it's pretty awesome um so doing this whole tree we get down to the bottom and now the count is 7 but the sum is 58 okay so i want to know the average of all the first seven prime numbers right so that's what this problem is what's the average of the first seven prime numbers so i had mapping reduced but i'm not done yet so what i really need is another map function that will take 7 and 58 and divide 58 by 7 right so that's what i've got up on the board with our awesome scholar programming language so what i really want is map semi-group and a map and if i had an object like this i could really like throw it like use it as a hammer on all kinds of things i could make my like min hash thing that we talked about earlier a aggregator that would do that whole do almost that whole algorithm and just hit it on like lists locally in memory i could go hit it on spark people have definitely done this i could run it natively in scalding i could run it on something bird and that's what we have we have this type which we call aggregator and it looks like this it's a trait it's very simple it's got three types so uh it has the name prepare so that's why i'm getting it ready for aggregation that's preparing phase then i have a semi group that's going to be this associative operation to combine those middle types so that's the reduction that was going on and then finally when i've reduced it down i need to present it to you in some nice way there means the post-processing sometimes the presenting is like identity like in the first example of computing the sum the presenting was like i'll just give you the number why don't i just tell you the value um but uh in the in the second last example it was this division so it's not like they're all that tricky but so what's so cool by the way you can get that amazing four line trait uh at uh twitter algebra on github actually is a lot more than that but that's the core that needs to be done the interesting thing was that this idea was in scalding right at the beginning we noticed that this mapreduce map of having maps reduce and map and actually i think alexi might have organized this um talk back at foursquare's old office like in two like one of the first talks about scalding ever and this is actually a slide from that and i made this joke and josh wheels was there i'm like that's how twitter is totally killing it it's not mapreduce it's mapreduce map uh we can maybe find that somewhere and it was uh it was it was funny at the time but actually the cool thing was that these aggregators compose really well so you remember like if you watched like the graduate and the guy's like you know the future is like plastics you know like i like like the like like with programming i'm telling you like the future is combinators you know like if your [ __ ] is not combined like you know you just like or what is it like dan rosen uh travis you like does not compose is the new is a piece of [ __ ] um i i think that's another thing so like aggregators compose you know they're awesome so i'll tell you about three ways they can pose the first way is the end then present sorry about the names we debated like these names you could have said like this could be called map um and the uh but it's like a little like maybe too esoteric but like i'm gonna do this aggregator and then i'm gonna do more presenting on the end so if you give me a function from the out type to a new out type i can take an old aggregator and turn it into a new aggregator that returns an out two that's very common i want to change the type maybe you i'm going to return along to you but actually you wanted a big end or actually you're going to print it out to the user so you need to convert it to a string so these are the kinds that's one like pretty obvious way to compose so they compose in that nice way there's another one this one for the scott z crowd is you might call this contour map because it's also a contra functor oh so uh you've got your n2 into n and i can take a func an aggregator that went from in middle to out and convert that into n2 to middle to out and it's pretty obvious how i do it i first like prepare it a different way and then i keep preparing it right so that's way that you can compose it too now here's the really fancy amazingly badass way that we really didn't respect enough early on and this is what got me so excited um like when i realized man we were totally under using this you can take two aggregators that maybe both go over like integers one is going to tell you the maximum value one is going to tell you the minimum value but i don't want to have to go through my list twice or my my big data iterator twice i want to join them together and only go through once and aggregators can be joined so if i have an aggregator of type that starts with type n and another one that starts with type n i can glue them together into one that starts with type n but has then forks out in the middle so this join composition is extremely powerful um i'm sure you can like think of examples of it i've heard i'm sure you've heard of the monad right and so monads are extremely popular i think people the next monad is the applicative functor so right under the monad there's another type called applicative functor and what applicatives allow you to do is glue things together in this way if you have a list of type int in a list of type string you can glue them together in some way to make a list of type int comma string like you can think of a lot of examples of that kind of gluing together that makes this two that takes that type into this this pair and it turns out aggregators are applicative functors they're not monads but they're applicative functors you don't you can hear that name and like like i don't know like they could be like you know foo bars or like bobs and some people hear those words and they get turned off i think we should just be like you know like like doing the robot and like saying like they're up like a diphthong doors and then like we could like just laugh at how absurd it sounds and maybe we won't be intimidated by it i think that's a better way to uh to but but i think that's pretty freaking cool so this allows us to do two aggregations with one pass over the data so how does that become awesome and check this out we made this awesome page for you which you can go see on our wiki so what does it look like now suppose you've got some sql up there and what you want to do is you want to select the customer name and the maximum of the order quantity from your order table and you want to group by the customer name right with aggregators you can make a lot of scalding code look quite a lot like sql aggregations so you define what your aggregator is going to be here so first we're going to import the max by aggregator and we have this case class that represents this table which i excluded on this on this slide and what we're going to do is we're going to take the max of the case class by its order quantity like the row we're going to take the maximum by it's just like that line up on the upper right and then actually we're just going to select the ordered pair we're going to throw out the rest of the row that's a little bit of a weird way to write it but okay and now the scalding code looks like from the orders grouped by the customer name that was the last line we had up there apply our aggregator and that's what it's going to print out and this is exactly like what you would expect the sequel to do so these aggregators are super nice there's an aggregate method in scalding on on whole tables you can aggregate them all the way down or you can group by and aggregate and there's a ton of examples right here you can search scalding aggregator and see a lot of great examples to see the power of this composition and keep in mind you can use these aggregators for the low low price um you can use these aggregators on lists on scholar vectors you can use them in spark you will find people who are using it in spark it is not tied in any way algebra has no significant dependencies there's one like bit set dependency so it has virtually no dependencies you can use it anywhere with no problems so that's the story that's all i got scalding kind of kicked off our scala data uh big data platform at twitter before scalding there was not sorry scalding did before scalding we didn't really have any scholarly big data tools um and summing bird was our kind of real time project there it's really great really happy with it a lot more machinery and i want you to take away if nothing else that aggregators are incredibly powerful concept you can go implement them yourself if you don't like our implementation in haskell they're called fold.m it turns out we found that out like it's like it's not it all these ideas are not new i guess um and algebra if you're using scala has a ton of awesome aggregators you're going to hear about some later to do probabilistic data structures maximum men histograms moments averages set union list concatenation vector point wise edition map merge you name it it's all there okay so that's all i got thank you very much i think we can take just a few minutes for questions it adam what's up hey i remember talking to you a while back you're interested in uh spire yes i was just double checking that you've been involved with that uh before i asked the question i noticed you had merged a couple pull requests a couple hours ago can you talk about where you see that going how that might work with algebra down the road yeah okay that's a good question i don't know if i should also speak into that microphone or not so the question was and i i'll say are we using is this only local or does it matter okay um so the question was so algebra is this algebra library for uh like it's really focused on algebra um it scala z is really funky focused on functional programming there's a little few overlaps between scholar z and algebra not that much spire there's a lot more overlap between spire and algebra spire is another algebra library for scala what like eric awesome dude one of the main people eric and um was it uh is it thomas yeah like both superb uh people two of the greatest members of the scala community if you ask me they've done some amazing work on spire inspires a really beautiful project the difference between spire and algebra algebra is really focused on taking algebraic abstractions for like big data or approximation algorithms and putting them into this algebraic framework that we talked about semi-group there's other ones group monoid you might have heard of some of them ring field if you're into the math um and all those concepts they're in math so they're their inspire as well but inspire is really more perform focused on high performance math and scala but also modeling in a rigorous way so it's kind of a shame that these two things existed and they didn't like work together that well so eric and i and avi um and thomas about a year ago i think it was um said wouldn't it be cool if we had a project underneath spire and algebra which we just like like why not just call it algebra it's the algebra package so yes there's this project called algebra so just totally like owning that like nobody's going to have an algebra package anymore like like that tires now um and the goal is to take all of the modeling of abstract algebra that exists in algebra and in inspire and to agree on the type classes and then we will make spire and algebra extend these common type classes so you could write generic code that takes an algebra semi-group and you could use your spire with it or your algebra algebra with it totally fine so our we're very close to getting there we've maybe uh gone off the rails a little bit adding lattice and band and all sorts of mathematical things and debating like what we should call a semi-ring or versus a rig but we're very close to like full agreement and when that's there i would expect in the next like three months at the most both spire and algebra will depend on these traits and so we can kind of start to share more code so that's that story you can find on github github non-slash algebra bird by the way when we said audra bird we thought it was so stupid like a ridiculously like it was me it was a it was a self-deprecating name of like how twitter always names things after birds and it was like like an asinine name and like it's so sad when like an asinine name like that ceases to sound asinine to me anymore and i'm just like yeah algebra that's like normal that's fine one more question um how do you deal in real time with data that requires kind of like oh let's say for example that you can count that with clicks on a tweet but how do you kind of number like unique uh users who have seen a tweet in real time well that's a perfect question for my colleague ian to answer he's going to spend a lot of time talking about that problem on how we would do that within this framework so i don't want to steal any of his thunder so i'm just going to leave that to him and i guess that's our last question i'm going to step aside or do you wanna we might have some more time for questions afterwards but i think sure okay thank you very much for your attention you