Ian O'Connell, Algebird: SF Scala @Twitter 20150106
Recording: Ian O'Connell, Algebird: SF Scala @Twitter 20150106
um so mostly what i'm going to talk about i'm just going to see if we can bump the volume up a little bit okay uh so what i'm mostly going to talk about here is algebraic which oscar referred to and really kind of talking from two real world use cases which are somewhat anonymized from exactly we do on twitter mostly for simplification purposes um and then how we use things in algebra to allow those things to scale so both of the things i talk about we will do we do in about real time and batch so it is uh they both run in something bird or something birdlike systems here at twitter so i basically uh work a lot with oscar basically he dumps all his toys on me when he goes on to new things and i write lots of code to keep them alive that's generally what i do here um basically so as i discussed we'll talk to hyperlog log which is approximate sets and count sketch with effectively approximate maps for long values with certain restrictions on it but and then basically briefly it'll be just exactly how easy it is oscar covered some of this but discussing you know the fact that some of these things are relatively complicated and writing them as a pain optimizing is all a pain but now that it's all done for you generally people drop these things in on twitter and at this point no one notices or cares exactly how complicated they are they just treat them like a map it just magically works so people compose these up into very big systems and we have no idea one of the kind of very interesting things is like i have no idea where most of my code's gone on twitter and you know occasionally you get pinged by someone in a very distant department that somehow is end levels deep relying on our stuff which is kind of nice about like the fundamental things like bijection algebra that have just leaked all over twitter stack which is quite nice and then lastly one of the things we often get pushback from is exact um so and kind of like why that's not really a thing so i'll kind of cover that at the end which is um one of the big questions with everything to approximate data structures is a lot of people say like well i want the exact number and i'll cover that at the end but basically the answer is most time you can never answer an exact number anyway so this was uh obama's tweet uh we got reelected um so this got retweeted almost a million times um so pretty popular and then take another one which was uh ellen's selfie from the oscars which you know completely destroyed obama and retweets there so apparently you can tell what the world cares more about so standard problems we have for internal dashboards and some things that make it into product that people come up with is like as is mentioned how many unique people viewed this tweet so you know kind of a very standard thing like if anyone views it 100 times or a bot does it you clearly want to like wipe those things out so certain things would spam for bots but in general unique users per tweet and then often a common one is how many people look at boat tweets so this allows you to identify like core users more casual and then overlaps with popular versus different types of categories of tweets so standard naive approach of course would just be used sets you know set of longs for every user and then you know you start getting down to the numbers and starts getting very painful very quickly which is basically you know broad strokes 10 to the 8th of both clearly that's you know take a lot of data and be extremely slow you know try to have a set that's 10 to the 8 elements and gonna be tough fitting in any memory so but basically all you want for most of these answers is approximate set cardinality often times these numbers are so big so approximate is like you can actually be reasonably fuzzy and it's fine so hyperloglog is associated and commutative which is very useful to allow enable us to do all these algebraic data structures so uh a common thing of everything in algebra that we do generally is at least associative which allows us to slot in so the semi group oscar referred to pretty much everything extends semi-group ultimately which allows us to do these sorts of things just like drop it in so like most of the methods we have in for instance summing bird and scalding and a few other places all they do is they look for semi groups they don't care what it is they send a group of type t once they have a semigroup they know how to combine it and that's the important thing uh in this case the error is proportional to one over the square root of size so it's got like kind of like nice scaling properties um so just kind of go through like an update step for it so if you take it that your hyperlog log is a kind of an array of uh bytes so we want to update for a value x so start out just hash it then you're going to split into two things you have an array of these various fields so first thing up we just hash pretty much all of these things involve hashing in one or several times so here you're going to split it two times so two ways you're going to use this then are in the first half of it you basically pick your bucket with the first side of it so you know you're gonna take the hash you're gonna and then just uh treat that as a number module it down for the number of fields you have and then you just use the number of leading zeros in the second half and then max that into that bucket and you update the bucket that's pretty much just the update cycle so we just do lots of these uh when these things come in and then the read side is pretty simple it's a harmonic mean of all this sort of stuff so this gives you an approximate of the totalized uh cardinality of this set um so this kind of gives you a notion of the errors that are involved the errors here at two percent um for a 10 to the nine set is 1.5 kilobytes of space which is tiny so in our case that means we can do this for like every tweet um and it only works out to be about 150 gigs per day roughly uncompressed which is tiny and grand scheme of things so the other main example as i'm probably bringing through these things too quickly so um is if we just take spokane just a random geo taking like a popular thing house cards tweeting away and then the problem in this case would be these sorts of questions so these come up quite a lot which is and you want to know these generally quickly because they're using a dashboard and someone wants it for a report which is standard things of like um how many times did someone view this tweet but then start adding an extra constraints like between certain hours when do they view it okay that's not so bad but then you start going to geo so there's another dimension tossed in there so how many um views in spokane that we had expanding that out is like so you throw in another dimension how many are using uh iphone sixes and then you end up with something like this which is just our tuple there where we have a tweet id a geographic location of some sort a device id and the minute if we want it per minute for accuracy so when you start working that out for just looking at one month of storage presuming you didn't have to go back too far for this you start getting out of like about ten to the nine tweets per month roughly you've ten to the five geos ten to two devices only about a hundred those you need to care about and then ten the four minutely buckets so you start getting up to pretty large numbers very quickly which starts becoming a pain to both like store query update and everything else to like do those aggregations make them accessible and most of them are not going to be very interesting anyway so common sketch is the ways to approximately look at sorry uh it's really a way to approximate look at that where your key is that tuple we looked at and we basically want to know that value but for the most part um we're allowing some fuzziness as a standard thing but it means that we can look this up extremely quickly and that's the kind of trade-off like countment sketch so we use count miss sketch extremely heavily because these properties generally be very good you want to know some number so you can keep it in memory and access a lot of data with a degree of fuzziness so common sketch the data structure is basically stored as a matrix of longs generally and basically what you do is so here you would be updating for x and y where x is an arbitrary type and generally y is a long something you want to increment by so standard kind of increment operation here it's a little different in that you have for every row in that matrix you have a separate hash function and they don't need to be cryptographically secure they just need to be separate hashes so for each uh hash function um on each row we will use the value of that hash function modulo your wit to pick your cell pick which column it should be so pretty simple and sorry and then finally all you really do is you add y to each cell right so you will have to make for every so the expensive part here is you're doing a hash so the more deeper your count switch goes the more expensive it is so the more rows you have the more hash functions you have to do and the more updates you have to do so it's kind of a trade-off whereas the width on the other hand you're only updating one of those at a time reading is really just the exact same process you find all your locations to pull out and then you just get the min of them all so the constraint here of what it gives you is this it's the minimum value it's going to be so accurately so as you can see from that update step because we always add it in and we're taking the minimum of all these things we're guaranteed it can never be lower than our minimum it may be higher so hence the name so it can never be lower which is kind of a reasonable constraint most of the time so just kind of looking at the error here presuming that we have looking at an estimate x just because there's a few algebraic things in here so it makes sense to just kind of lay them out which is like we do next estimate for our account for particular x um and the estimates x unfortunately um total count of the whole thing so important one here is that the error is often um is proportional to the total count which is the total number of things you've put into this count sketch in total so if you very little things in there your error is very low if you've really overloaded this common sketch with a lot of data then your errors will start spiking so it's an important consideration as to how you size these things or sometimes when you cycle them out so often a lot of our cases we will put a countman sketch as the value and your key could be for instance the hour of the day you can combine these things up because they all have semi groups so you can share all this data as well so you can combine just standard um cubic data cubing with these sorts of approximate structures so that you can compound these errors in various cases so the upper bound um sorry the yeah so we we have the um the lower bound that should be regime um basically unfortunate but there you go uh some math forms but basically you have this kind of fuzziness around that thing it's pretty low you've got a reason probability was in that thing so in theory so all you really got you're getting a probability that it's within a confidence interval around there so it could be much above it in a very extreme case which is unfortunate when that occurs but so we do have certain cases where these things matter where people will use these things as a fuzziness and then we'll look up the exact and another data structure when it matters so sometimes so for instance if you have dashboards that involve revenue these things can provide you a very fast means to try to find the interesting things and then we have secondary lookups that will go via slower paths and get you more accurate results when is required so it's important to kind of notice the trade-offs and people have been adding more alerts and people have been burned here twitter like approximate's brilliant until it isn't and then so it's one of the things you have to always be careful of your the audience for your data and what the presumptions they make are if someone presumes it's exact and it's not you can run into problems and then yeah question about the scaling this data structure because as you have more hash functions you move away from your optimal um lower bound for the the error right uh the increasing number of hash functions uh gives you an increased confidence it will be within your error bounds so the number of hash functions is for it controls like the number of um uh the kind of you're confident your probability would being within your upper and lower bound right is the number of hash functions how big that bound is is then is based on the width so the number of columns for each hash function controls the error and then your probability of being within those bounds is based on the number of hash functions will have correlation between the bucks that they choose and the number of pairs you have is exponential number of punctures that you have so with each bucket that you add those two actually increase yeah so that's exactly you take them in so when you're actually reading they're all like effectively independent you will only ever take one so if you have if you collide across half of them so in a very common case for instance you will most the time in a big one of these you will collide in action nearly all of them right and on a certain number of one of those you may collide with very big things which would throw your results way out but as long as you don't collide with something much bigger new on some of your results so only on one row in fact if if there's one row so this is the problem if you look for something which is extremely low frequency this thing is like not a good great data structure for that things that are like very much in the tail with very low frequencies you run into a lot of noise there so if things are all like you know um normal distribution it's pretty good for so because you only take the minimum though it doesn't actually matter if you collide so a very um what would be there like if you uh ellen's tweet for instance do you collide with that the probability is you'll only collide with it once even if you collided with it twice it wouldn't matter as long as there is a row where you're not colliding with something that will completely shroud your answer but do you guys have a way of creating these hash functions that make it so that you don't for each incremental additional hash function that you guys generate you don't actually um increase the chances of having more collisions so like the hash functions are independent which is fine not cryptographically secure but collisions don't actually matter for that purpose is in like you may increase the probability so let's presume like they're not um you the more hash functions the more likely you are of more collisions but because you only ever actually use the value from one row that doesn't actually matter as long as you didn't collide on every single one so increasing the number of hash functions will never actually like increase your probability overall of complete colliding it might increase like obviously if you increase it like in infinitely you will start colliding but because you only pick out one row you know when you increase your number of rows so your overall probability of having collision won't go up you're probably sorry your your probability of having collision will go up but your probability of having at least one non-collision won't change ian this may help i'm not sure if this is clear each hash function only writes to its own row right so you never have collisions between cache functions you only have collisions between different keys make sense okay so in this case so we do a lot of kind of interesting things in this case here this would make 160 gig cms without any compression to store all of this data which you can actually just store on a laptop so sometimes for tech demos or various other things it can be useful to actually just stick a very large cms in there and you can like fake out a big data backend sitting on your laptop and be offline so we've done like various projects of just sticking huge volumes of data in and then you can do real-time exploration just sitting on a laptop which allows you to like super slice in various means which is kind of nice but in general i mean how we normally use these things is we will stick these things in the value somewhere so you're sub slicing different ways and this gives you an extra degree of resolution that is not practical to count normally and you can see the so the most important thing really here is just exactly how easy it is to use all of these things and they all report their errors when you use them which is kind of useful but the most important thing is then when you get down to it so monoit's oscar talked about so we won't really cover that um or creativity too much unless anyone's any questions scalding was good some by key oscar uh alluded to this but he showed group and some some by key is in all our projects now which is actually one of the nicest things going so as oscar alluded to you have this sum by key which looks for an ordering but the important thing is it requires a semi group and v so whatever v is so often in our cases v is a combination of hyperloglogs countment sketches inside a scala tuple possibly with a map a set and a lot of other stuff in there so you have these huge things and you just layer them all up and then just call somebody key so these jobs end up looking kind of like very trivial where thankfully all of this stuff is entirely gone away from the user so um the the person who has to run the job that actually is producing that dashboard for someone doesn't ever need to care um how these things should be aggregated or how it should be wired into one aggregation system or another it's kind of the nice property of exposing semi group everywhere has just meant that in both like online and offline terms and like so if you have a real-time query system system that has to do some calculations and return a result back to a user those sorts of things like all the same operations can just be picked up everywhere because they all have this nice semi-group thing so hopefully the spire stuff will all kick in there too we get on to that so to kind of give an example so this is an actual um tutorial thing we have sitting around somewhere and this is doing a countment sketch so the first line is obviously an import venue was familiar with scala wildcard import and then we create an implicit monologue to make it available in scope so often we do a lot of these things is we'll build up various implicits in scope for monoids and semi groups that are available and then the the bulk of the code that's in there is generating just all the fake data so this is actually just runnable as is um and so the important thing really is the map as oscar was talking about and you just basically map so with an aggregator you wouldn't actually need this map step often you could just use the aggregator and it would auto pick it up from the value in this case you do need it or if you're using map if you're using some by key you would need it so this is all you pretty much have to use to use a cms and that's it at the end of it the value will be this countment sketch that you can do lookups and then this is kind of ones we run into a lot less so over time which is the desire to have it exact uh most time the less over time is because the cost function of exactly how much this costs to twitter to run these things is so much drastically lower that people like are willing to take approximate there's a whole bunch of cases where you can't do it or certain algorithms don't work well in certain cases but where you can it's significantly cheaper faster and scales better but also like a big thing that comes down to it is is that true various pipelines from what gets off your device from ios so anyone who's done ios or android knows that basically there's huge amount of loss generally you're not going to get all the events you're going to get them multiple times or you're going to get a lot of stuff coming off those devices and that's even before it reaches your system now you're going to have outages in your luck logging pipelines your services what they do or don't write eventually you reach hadoop you end up with corruption at a certain scale you start having corruption and ldl starts kicking in your various compression serialization the whole world so basically you end up with you know up to about five percent of your data is just corrupted or gone so you may be getting repeats you get all these various things so at the end of the day you don't really have an exact number so trying to get an exact number out of hadoop when your data input is not exact is kind of nonsensical well it's totally nonsensical so where the approximates can actually have a lower error bound than your inbound data pipeline it makes no sense to just not use the approximate for the most part um so one huge aspect for us at twitter is with the cms um so the cs cms algorithm comes with heavy hitters which attempts to give you items that are in the cms above let's some arbitrary thresholds like one percent of the data it's like a ratio of the data so it's kind of so it's bounded but often what we want is top end top end unfortunately is not actually associative but it's close enough this one's used a huge amount for us so one of the big ones is if you go to a tweet on twitter that's been linked to so the ellen selfie and the obama ones will both have this property so that they're linked in by like a lot of news sites so we can use these sketch maps to keep track of how many times we got referrers from these external sites so this sketch map gives you an approximate means of do that that because it's so cheap to do we actually can just do it for every tweet we have no notion of saying when a tweet's created we don't know if it'll end up in all various news media but a huge amount of the sites that will be a refer to anything we will never see again and they won't be very interesting we'll see one or two or three so even though it's not associative it will give you your top end where you know um these are reasonably large so if you want to look at inbound new sites for referrers or similar things like that it works extremely well first and that's actually what powers our related headlines system is a something bird topology that uses this um so that's kind of like one of the associated things one of the more recent things we did in our storehouse abstraction was in memory caching um from our caches be able to just use a cms with these heavy hitters sitting around the place to decide what to cache and what to not so one thing if you start to get into like the minutia of mapreduce is with these long tails keeping them in the jvm in your cache um if it's very infrequent is actually quite expensive for gc because it might make it tenure when it shouldn't and so but basically knowing that these percentage of things are like much more common means as you're streaming two huge amounts of data in your mappers you can just discard things so the same thing applies in like our stores and whatever else which is that if i know this thing in map side combina combinators is very rare i would definitely not want to cache it i want to write it out immediately because i know there's not many of them but the only thing that is like very common we will cache heavily and attempt to not flush till the end of the mapper runs as much as possible so these are kind of like various things we stick in so we have these in various different systems and different forms but just kind of using this approximate nature where most time you do not care about exact and best efforts good enough so in summary we like our approximate data structures we do them a lot and we generally wire them into everything they're not suitable for everything and it's important to know when you start getting up if you're presenting it an important way sort of a dashboard generally where are the weak points for some of these algorithms because if you hit them it can be like very misleading and kind of frustrating for your users but they're easy and we use them in scalding something word and spark in fact internally as well so it kind of works every well and everything that's about it any questions are there any big oscar would probably won't have to know that i've never ran minhash maybe avi knows i i we generally don't run code to be honest we we build libraries um it's like one of those like distinctions that our size is like where possible we just avoid running it i mean we keep talking about this issue it comes up over and over again i don't know i don't want to push the spot you want me to say something about it okay so um so intersections are really super hard i think they're actually an open research problem for approximate data structures so if you want to get the intersection there's a i don't remember what this rule is called but there's some rule of like you know it's like logic or so it comes up in a lot of ways but you can compute the intersection if you compute the inner if you have two sets and if you know their size and you know the size of their union you can compute the intersection and so algebra gives you a method to do this now the problem with this is the error compounds very fast unlike the error does not compound very fast between unions so unions compose really nicely with a lot of these methods intersection not so much now back to intersections minhash doesn't give you the intersection it gives you the ratio of the intersection over the union so it gives you that jaccard similarity so you can combine a hyperlog log and a min hash and multiply you know do this kind of trick um i think there's some interesting academic work that can be done on like how is the error scale there but since we're all practitioners and maybe we maybe maybe a lot of us got phds but now we disavow them um we could just like run into some simulations and see what the error is you know it would probably be fine you know probably just work and uh but there probably is a nice algorithm to get the intersections that people probably just have not found yet there's one that i speculated about but i couldn't prove anything about and it's sitting in an open pull request on algebra but i don't know it's like it's a good question other questions my name nanoski okay great thanks you