ow let's suppose we have Another application and this application uses two libraries now. It's simply and another league So now we are going into 3d space So we on one axis we have simply on the another axis we have another leap and Then we have actual score. Okay, so let's interpolate these values and what we get is basically a surface Here we can see for example that another leap in these three versions scored really poorly So it's probably best to install software or to install another leap in the specific Versions and on the other hand simply in version 3.5 and another leap in version 2.5 gave the best score We can project just to make sure that The score is the highest and here you can see by projecting into score and simply You can see that the highest value is in version 3.5 Okay, so let's try to generalize it. So let's suppose we have some scoring function and the scoring function has Input n minus one where n is number of all possible packages that can be installed with the given So or when resolving the given software requirements and This scoring function can take into account things like how does the Given library perform like does it perform good bet or how reliable the given library is or how do These three libraries work together. So when you install for example tensorflow in some specific version and then by in another version you can say okay, these are performing better than in comparison to other other versions and If you want to generalize it, you can basically have two types of scores One is solely on package level. So you score the given package like does it have CVE and then you can have cross library score or cross package store and here there is taken into account for example that case with tensorflow and I spoke before Okay, so how to find the best software stack? Well, the answer is that it's nearly impossible for a bigger applications for example tensorflow Resolving tensorflow just having tensorflow in your requirements can lead to 68 billion on possible software stacks and If you add new it just multiplies by number of all possible versions However, we can find a good enough software stack and we can approximate it In the thought so our thoughts is a recommendation engine. We are trying to resolve stack and We are computing basically candidates that are scored based on the scoring function We are trying to provide recommendations like you should use this software stack With reasoning so we for example say don't use this library because we know that The other version performs better We are trying to be as close as possible to source code So we have these bots that automatically open pull requests to your repositories We will try to learn from users behavior So if you for example close pull request and you say, okay, I don't want to use this software that was suggested We try to learn from it and next time come up with with better recon better Request We are trying to be proactive. So once Thought learns that there's something wrong with that particular package We can learn from it and by monitoring other the other repositories we can proactively open new new pull requests and fix issues even before they they happen in Product production besides that we know what you are installing So if you are installing tensorflow we can also suggest how you can deploy your tensorflow in into production This is some kind of vision of thought as of now we provide automatic updates of Dependencies and we cooperate internally with in the redhead with team and we are trying to gather information about updates Whether the given update or whether the new release of the given application broke broke for example CITS or stuff like that We Have implemented server side Resolution so we can find or exclude given package from from software stack and and Resolve to another software stack that does not have the given version of of package that can be possibly wrong We have these boards that operate on the source code and we have checks of provenance Python does not provide things like having to saw package indexes Deployed and for example in one package index that we have provides optimized tensorflow builds and for example running Public IPI index besides that which will have all the rest libraries that you need to Use for your application. So in thought we know this provenance or origin of Artifacts that you are installing and we can say, okay, you are probably not using the given Optimized version of tensorflow you would like to use We can also check runtime environments of application so we analyze images and we can say which packages are present there and which versions and Basically, this is feeding information to our database or knowledge of of packages that we have The next thing that we will do is aggregate more information as I stated we are cooperating with other teams at redhead and we are trying to aggregate informations like okay, these are software software sticks that are not good or information like which what breaks what and Come up with cross library scoring So these things like okay, you have tensorflow in this version Mumbai in that version Basically score that that thing one one possible solution is dependence monkey where we generate stakes and Different stakes and we run for example test suits on on these stakes and we can measure for example performance index and how good For example tensorflow performs So that's from me. Do you have any questions? You mentioned dependency monkey with the hardware, but a tough mostly focusing on software Is there any thought to how some of the package resolution or package recommendations may depend on certain hardware? Yes Basically in the back end we are Saying this is some observation we have for the given runtime environment and this runtime environment can have information like okay, it's for example GPU enabled GPU enabled note in the cluster and in that case If you are using tensorflow in this version or you are using something like that we can measure measure Also information about about it Or keep information about it Hey, Rita You mentioned that a lot of how you have taught integrated right now is in bots in your workflow Are those bot configurations generally available for people to integrate into their repositories as well? We have I can probably show it we have configuration available In our repository. So one of the boats is Quebec heads and Quebec heads is monitoring repositories and aggregating information about these repositories It's it's deployed internally and This is basically configuration for for different repositories we monitor we monitor taught itself and monitor user contentization team and If somebody wants to deploy taught on its own this is basically like configuration a User can can follow and configure it for its deployment Okay, thank you for everything Okay, thank you. It started all right My name is will Benton. I work on and with distributed systems and machine learning at Red Hat I've been at Red Hat for about 10 years currently. I lead a team of data scientists and engineers Focusing on machine learning on open shift. I'll talk a little bit more about that at the end of the talk Thanks so much for joining me for this session today We're gonna talk about what I think are some really cool data structures for scalable computing Basically things that let you get approximate answers to interesting questions And you can run them on streams or in parallel and you only take a constant amount of space But first I sort of want to sort of read the room here and see where people are coming from I'm always interested in why people get interested in things Early last year. I was talking to a colleague about like problems that we realized were interesting You know, you think a problem isn't interesting and then you realize that it is anyone have this experience before Maybe maybe maybe you just are really good at identifying interesting problems right away and you don't have this problem so I had this problem now and If you think about if you think about scalable data processing, of course It's a hot topic today, right? If I if I give a talk today and I'm saying I'm gonna teach you how to do scalable computing Everyone has big data or wants to have big data Everyone needs scalable processing, but it wasn't always obvious that you know for a lot of real-world problems Stream processing and parallel processing were necessary, right? I mean there are people some people have that data that require this some people don't and you could imagine, you know 20 years ago thinking about problems that You could solve a lot faster if you had parallelism or that you could solve a lot with a lot less space If you could do them in streaming problems, but you didn't really necessarily think about problems that you couldn't solve at all Unless you use parallelism or streaming and So I was always convinced of the theoretical benefits of potential speed-ups for running a lot of these algorithms in parallel But the first practical problem where I found them totally necessary wasn't looking at sort of mean and variance estimates Which is pretty basic, right? You probably already know the easiest way to calculate mean and variance estimates You pass over the data once and you sum the samples And then you divide the sum by the number of samples to get the arithmetic mean Which I'm representing in this figure as the height of this shaded box Then you go over the data set again in the second pass and you calculate the difference between each sample and the arithmetic mean So here and it's a little hard to see on the projector because it's a little dim but we have positive differences as red bars from the mean and negative differences as Blue bars, but it winds up not mattering because we're going to square all these anyway And they're all going to be positive and then we're going to add them up together and divide by one less than the sample count And we'll get the variance So you learn this in school. This is a simple technique and it works for You know any data set that you can keep in memory and pass over a few times But for some large data sets that second pass is not going to be feasible it might not even be possible and So I first ran into this problem while running architectural simulations if you're a computer architect and you want to evaluate the impact of a new cash replacement policy on memory access latency or if you're a static analysis designer as I was and you want to evaluate the impact of a particular compiler optimization or on branch predictor performance You're going to be running a simulation and in the sort of stone ages when I was running these Simulations it took like two weeks to simulate a few seconds of wall clock time for an interesting program So you'd be running a bunch of different configurations You'd be using up a whole bunch of people's computers and you'd be producing a stream of values for every memory access Indicating how many cycles it took to get to that memory So you can imagine that if you're taking days or a week or more to run an experiment the prospect of running the experiment again So that you can calculate the variance is probably not something you want to do So you want you want a way to run this in a single pass so Beyond basically understanding how the textbook method worked I hadn't spent a lot of time thinking about this problem at all and the first time someone showed me an algorithm to do this in a Single pass it seemed like magic. It seemed like a superpower and so let's take a look and maybe it'll seem a little less like Magic after we see it in action So instead of looking thinking about our population as a set of values that we can replay as many times as we want We need to think of it as a stream. We need to think I can only see each value once So we'll examine one sample at a time and after we examine a sample will update our estimate So when we've seen one thing the mean is that one thing that we've seen right? That's sort of an easy trivial case We like to look for those where we can get them our variance is undefined because we only have one sample and to calculate the Variance we'd have to divide by zero When we look at the second sample we'll look at our its difference from our sort of running estimate of the mean Which I'm representing here is that blue top of the bar there and we'll update our estimate of the mean to reflect the Contribution of the sample that we're looking at to our mean estimate So we'll say split the difference between what we have and what we've seen and so on and then we can also get an initial estimate of Variance because variances are larger quantities than means Typically, I'm representing that as a as an area rather than just as a line But there's nothing inherently two-dimensional about it When we examine another sample we'll update the mean estimate again This winds up being like a weighted average since we've seen three things now We update by one-third of the difference From our mean estimate to what we're seeing and then we can also update our variance estimate And we can see in this figure how the mean estimate gets updated over time as we examine each sample So each of these samples has a colored bar over it indicating where the mean estimate was Whether we raised or lowered the mean estimate and how much we updated it by after examining each sample So the actual arithmetic mean for the whole stream is Represented by the height of that light gray box and we can see that after the last step We've actually landed on that arithmetic mean for the whole stream that we'd have calculated in the traditional two-pass algorithm on the bottom we have the variance estimate for each sample which I've scaled down so that it will fit on the slide and The height of that dark gray box represents the variance estimate We'd get from actually running the two-pass algorithm now We can notice if you if you sort of have really good eyesight you can see that it's not exactly the same But it's close, but we were able to do this in one pass So maybe that loss of precision is is acceptable So the cool thing about the summary that you get from this online algorithm is that you can combine it with others For example, let's say I have two streams You know, maybe I'm running an experiment in parallel And I'm running different parts of the parts of the binary on different machines And I want to combine the mean and mean latency from each of those Well, here's a stream with its actual arithmetic mean and here are the mean and estimates mean variance estimates that we would get for that stream and If we have another stream with its own mean and variance estimates We can combine the means from these two estimates by treating them as weighted averages So if we've seen, you know, a dozen things in the first one and ten things in the second one We could combine them by taking twelve times the first one and ten times the second one and dividing by 22, right? Pretty pretty straightforward And we can combine the variances in a similar way by taking advantage of the fact that the mean and the variance are independent We don't need to know anything about the mean to say something meaningful about the variance So this means that we can process streams or very large data sets in parallel And we can produce reasonably accurate estimates of their mean and variance just by combining the estimates of Partial streams or subsets. So how many people in here read abstracts before they go to talks? Good good I commend that Some of you may have an objection at this point, which is that this isn't actually a probabilistic structure It's sort of an approximate structure, right? The answer we're getting is close to accurate But it's not but I also said that there would be some code in the talk and I haven't shown any code yet So I'll address those objections in order The first thing I want to say is that this is just a motivating example This is when I discovered the streaming algorithms were interesting a long time ago But it has a few things in common with every other technique. We're gonna look at today The first thing is that it's incremental This means that we can update our summary by looking at a new sample once So we can process a large data set in a single pass. We don't ever need to keep observations around to replay them later the second property this technique has is that it's parallel if I have a Summary for a subset or a partial stream I can combine it with a summary for another subset or partial stream and get a summary of their union This means that I can divide the problem in pieces that are reasonable to process on a single machine and Combine the results it also means that we can scale this processing out by processing subsets of our input on separate machines And we can thus benefit from elastic scale out in the cloud where you have a lot of relatively small compute resources that are cheap and may come and go depending on spot pricing or other availability and The last thing I want to point out about this technique is that it's scalable And that means that whether you process one sample or one trillion your summary is going to use the same amount of space So when you think about something being scalable, how many people think like a linear time or linear space? Algorithm is scalable sound pretty scalable Raise your hand for linear scalable How about logarithmic raise your hand for a log is logarithmic scalable Sounds good, right? So I Always think of those things as sort of scalable myself, but but when we're dealing with truly large amounts of data Any growth in that summary size at all is Ultimately going to lead to problems right if that summary gets bigger for looking at a trillion things We may not be able to deal with it when it gets to 10 trillion, right? So we need something that's going to take a fixed amount of space no matter how many things we look at and we need a way to reason about How much precision we're giving up for using a particular fixed amount of space? So all of the techniques will look at in the rest of this talk have all of these three properties They're incremental they're parallel and they're scalable and just as I was sort of empowered by being able to compute statistics in a single pass I hope that some of these techniques will seem like magic to you if you haven't encountered them before And if you have I hope that you'll at least be inspired to think of new things that you can do with them So the second injection was that I didn't have any code The code for streaming mean invariance estimates fits on a slide It's not particularly interesting. So I'm not gonna talk about it, but I did show you some code for this We'll look at some more code later in the talk But it will all be sort of code that illustrates something and is is actually useful If we step through it So the first problem I want us to look at is set membership for very large sets and Set membership is interesting because it's fundamental to a lot of data processing problems But we'll start with a motivating example If you're running a web cache and you default to caching everything that anyone ever requests You'll get improved performance on the second time someone request something but as you continue to get requests the size of your cache is going to grow and There's a long tail of these web requests so some things will only get requested once now something that's requested more than once Is likely to be requested a third time and maybe even more than that but Most of the things that you see In a web proxy are only ever going to be requested once and no one will ever ask for them again And you're gonna have these things in your cache they're gonna be filling up your cache and They'll have a performance impact on your cache So you can eventually evict those things When they're not ever asked for again, but in the meantime you're using resources in this cache Probably in a very high-performance system. That's expensive to run That you could profitably apply to caching things that might actually be requested in the future Which are only gonna be a subset of the things that you would actually cache if you cached everything So it would be nice to have a way to only cache things the second time that someone requested them right So the things that were only requested once would never land in our cache. They'd never take up space And the problem is we sort of have to keep track of the things that we've seen In order to know whether we've seen them But if we're keeping track of the things that we've seen in order to know whether we've seen them We basically are caching them right so what we want is we want an Incremental parallel and scalable way to model set membership So we'll maintain a approximate set of things we've been asked for when we get a request for something Yeah, we'll check to see if it's in the cache if it's not in the cache It could either be the first time someone's asked for it or the second time someone's asked for it If it's the first time someone's asked for it It's also not going to be in our approximate set that we maintain in parallel to the cache Which is much smaller than the cache and much cheaper to update If it is then we'll put it in the set but not put it in the cache If it isn't rather if it is in this set of things that we've seen once Then we'll put it in the cache and it will stay in the cache until we evicted So because we want our proxy to be scalable We need this set membership Approximation to be a lot smaller than the actual cache We want something that's going to be a fixed amount of size no matter how many random web pages we get requested and so this actually isn't a hypothetical example like Akamai did this like 20 years ago and Saved a lot of money and wasted effort with their content distribution network, but So I want to talk about the approximate technique we can use to solve this problem But first I just want to sort of review how we would solve this problem precisely so that we can think about the trade-offs We have when we go from a precise solution to an approximate solution So the first thing we could do to represent a set Especially a small immutable set is just an array right and if this is less fewer than 20 items You probably don't even need to sort it because it's going to be more effort to keep it sorted Then it's going to be to scan through and see if the thing you want is in the set If we have data that are comparable and admit some kind of natural ordering We can make a set as a tree right where we have We have values and we sort of can search for something to see if it's in the set or not quickly and Then if we have data that we can we can hash we can use a hash table So we can just have the keys be set elements and we can have the value be anything right if we have the key In the hash table the thing is in the set so it'd be true or one or whatever So recall that when you put something into a hash table you look up the hash value of The thing that you want to put into the hash table and you use that to identify a bucket Which is just an element in an array and then we're either going to store We're going to store a linked list of things in that bucket, right? So I mean there are a couple of ways we can do this. We're choosing to store a linked list So I'm putting foo into my hash table. It's not there So I'm going to construct a new linked list that has foo as the first element and no second element So we use that list because we need some way to handle hash collisions where two different values map to the same hash bucket So because we're hashing arbitrary Values to relatively small number of buckets You could take any value in the universe and put it on to you know 10,000 or 20,000 buckets eventually they're gonna there are gonna be two things that land in the same bucket So we're gonna keep this list around so that when we ultimately get that collision we can handle it Let's say we have bar hashing to the same bucket as foo, which is probably a good sign that you need a new hash function, but What we do in that case is we depend it to The linked list there so when we have a collision and a hash table We we pay a time penalty and a space penalty and it's easy to sort of see these in action If we think about a hash table that only has one bucket Right you have a hash table with only one bucket Essentially, you're a linked list Searching for something in the hash table is linear search through everything in the linked list and you have no memory locality So so pretty awful all around For scalable computing we don't want to pay either of these time penalties or these space penalties So we're gonna look at the bloom filter which is very old data structure But it's a hash-based data structure that models set membership and uses a fixed amount of space and constant time and returns an approximate answer to a question is this thing in a set and The answer is approximate because the answer isn't yes or no it's no meaning definitely no or Maybe meaning we can't be sure So let's see how it works We want to handle a large amount of data in a fixed amount of space and a constant amount of time per update So we're gonna have a fixed number of buckets We're never gonna expand our hash table and we're not going to use a linked list to extend it But the values we care about storing are either true indicating that something is in the set or false Indicating that we haven't so we can just use a bit vector for these buckets, which saves us some space right away So we don't know what we've inserted into the bloom filter We just know whether something that has a particular hash value has been put into the bloom filter If we're querying for something That hashes to the same bucket is something we've already put into the bloom filter We'll have to return true even though it might represent a collision and as the number of elements in the bloom filter grows The probability that we'll see a hash collision and return a false positive increases So the bloom filter mitigates this to some extent By using several independent hash functions For insertion and for lookup. So in this case, we're going to insert foo and we're using three different hash functions To identify buckets and we're setting all of those to true If we update again to insert bar, we'll use the same hash functions But they're likely to return different values at least some of them are likely to return different values So in this case the third hash function has collided for foo and bar, but the other two have not And again, if your actual hashes are performing like this seek out a better library So when we look up a value in the bloom filter, we only return true if all of the buckets We've hashed it to are set. So in the case of foo All of those buckets that foo hashes to with the three hash functions are set to true So we'll return true in that case Likewise for bar, we see that all three of those buckets are set to true and we can return true If we look something up that's not in the filter We may have hash collisions for one or more of these hash functions But it's really unlikely that we'll see hash collisions for all of them So in any case if the bucket for any particular key For any of the hash functions is on set we know absolutely that we haven't put something into the filter So this is why our no means absolutely no But in the event that every hash function leads us to a set bucket our lookup function could return true even for an element that we haven't inserted into the bloom filter and in this case the hashes for blah Collide with the hashes for foo and bar together and so we have a we can return true, which means maybe but in this case It's a false positive So we can actually calculate the probability of false positives based on some properties of the filter And we'll talk about that a little more in a second But a really cool thing about the bloom filter is that as you might imagine The implementation fits on a slide, right? You have a bunch of buckets He has a bit vector when you insert you take each of your hash functions and you set the value in the bit vector to true When you look something up you return true if any of the buckets you look up or false or false and So on the other cool thing about so this is you can update this One thing at a time, right? You don't need to see all your elements more than once so it's incremental And we'll see how it's parallel as well so a Really a really cool thing about these is Combine the filter buckets with bitwise or if we have two filters one of which we've inserted foo into and one of Which we've inserted bar into One of we if we combine the two filters using bitwise or We actually get a Filter of the union of these two sets. So this is where we get the parallelism from right? We have a very simple operation That we can do to combine two of these filters and we can estimate whether or not something is in the union of two sets Even if you can't keep both sets in memory at once The other nice thing is that this is exactly the same filter we would get if we took all those elements and put it into a single filter and This also means that we can scale these things out if we process the data structure one partition at a time We can combine the filters for each partition And get a filter for the whole data set So if you're algebraically inclined You might be thinking I can get something interesting with bitwise or Probably also get something interesting with bitwise and So what is to and as union is to or? Intersection right and so actually you can get a bloom filter approximating the intersection of two sets by taking the bitwise and of their buckets so the union of Two bloom filters is precisely equivalent to the bloom filter you get from taking all those elements and just constructing one from scratch But the intersection of two bloom filters may have a higher false positive rate Then the filter you would get by taking the intersection of those two sets first and then calculating it But again, this may be the only way you have to calculate that intersection in the first place So the point is that we can always calculate that intersection. It's useful to have a scalable and parallel approximation so an extension to bloom filters partitions the buckets and Basically the idea here is that each hash has its own partition of the bucket space So that instead of having three hash functions that could write anywhere in your bit vector You have the first part of your bit vector belongs to the first hash function the second part belongs to the second hash function and so on You could also think of this as having a matrix of buckets right where you have one row for each hash function And so the interesting thing about the partition bloom filter is that it has a lower false positive rate under intersection than the the classic bloom filter If any of these partitions is empty, you know for sure that the two filters don't intersect The partition bloom filter is also the basis of the second structure we'll look at today And we'll get to that after we talk about some applications for bloom filters So what are some cases where we might want to be able to answer set membership queries without keeping explicit sets around? Well a motivating example from Bloom's original paper was a hyphenation dictionary So if you ever thought about hyphenation, especially if you speak more than a couple of languages You know that there are enough corner cases in hyphenating natural language text to be extremely frustrating and in Bloom's case The example is a hyphenation program that could use simple heuristics 90% of the time But had to consult a dictionary of rules for the remaining 10% and because this was almost 50 years ago Neither the dictionary nor the set of words That needed this for the dictionary would fit in memory That's hard for me to imagine at this point in history, but maybe it's maybe it's easier for for others to imagine so The problem is though that our thing saying do you need to consult the dictionary or not only fits on disk We really don't want to hit the disc right the disc is super slow So having to hit the disc to decide whether or not we need to hit the disc Turns out to be a really bad deal But if we maintain a bloom filter in memory to see whether or not we need to look something up on disc We can minimize the number of unnecessary disk accesses to the false positive rate of our bloom filter More on that in a minute Second application is bloom join which comes up in distributed databases And if you have a distributed database with two relations that live on separate machines You'd like to get the pairs of tuples where they have some value in common If we're gonna implement this naively there's a whole bunch of communication and unnecessary work To take all the values of x from a and send them over to the machine that has b so that we could sort of figure out which tuples might be involved in one of these joins and vice versa But instead we can construct a bloom filter for the values of x in a and a bloom filter for the values of x in b and Shift those across the network and then we can use those to sort of filter out Records that aren't going to be involved in the join before we do any communication And if we have a relatively low false positive rate We can calculate that final result that we care about for our join Without doing a lot of unnecessary communication The last application I want to talk about is enabled by the fact that bloom filters are so simple You can't just implement them in Python on a single slide. You can implement them in hardware and From 30,000 feet essentially every innovation in computer architecture in the last 50 years has involved exploiting implicit parallelism This parallelism comes in two forms. The first is instruction level parallelism where we sort of identify Instructions that aren't going to interfere and we execute them in parallel or where we Divide instruction execution into many stages so that we can run these stages in parallel And this requires the second the specular instruction level parallelism requires Support for some speculative execution so that we can start executing an instruction before we know whether or not it will interfere with something It's already executing and have a way to roll it back if necessary So hardware speculation is something that if you haven't thought about it You may not realize how important it is But if you pay attention to how fast your computer is Before and after you install security updates and you installed security updates at any time in the last 10 11 months or so you May see that hardware speculation is actually pretty important because of the source of some really critical security bugs in the last year that Turning these features off really impacted performance So the second kind of parallelism that we talk about in hardware is thread level parallelism And if we have some way to speculatively execute functions or loop bodies in separate hardware threads We can really speed up a lot of workloads and this functionality is especially nice because we can speed things up that a compiler wouldn't touch Consider the C function that increments every element in an array If we call this function twice as we're doing in the second function We might think had really love to run these in parallel, but no C compiler is gonna reorder these these code at all, right? Why is that? Anyone know You can't model the side effects So we just have these unrestricted pointers to blocks of memory and the array that v1 points to might Overlap with the array that v2 points to and in fact, they might even be this the same array or they might be you know They might overlap and if they're the same array, it's not necessarily a problem but if they overlap it could be a big could be a big problem, right and so so In general our compiler is not going to prove that these two functions commute and So a way to get around this with hardware support is something called thread-level speculation the basic idea is that you have special support for tracking what memory addresses a Program rights to or a sub-program rights to and then you can roll things back if it turns out they weren't safe to execute and In practice what this means is that we want to detect a case where the orange indication Write something that the blue invocation reads or vice versa If they don't touch the same memory at all then we can run them out of order in parallel because we know that they'll commute and We can actually use a bloom filter in hardware to represent the sets of memory addresses that each speculative thread touches doing execution and then identify whether there's any intersection between these two so if there is any intersection will roll back one of the threads and not or both of the threads that execute them in order so All of these applications can benefit a lot from approximate sets But they all depend on having a reasonable trade-off between the filter size and the false positive rate So we need to choose a good trade-off Fortunately, this isn't very hard in the bloom filter actually has these properties that we can calculate this with a formula and We don't need to run experiments. We can actually just sort of approximate it and this is what the formula looks like I promise this is my only slide with a lot tech math mode. We are in a university I hope I hope it'll slide that this is the only equation in the talk and let's see what's going on here. So we're taking One minus e to this power here and taking that whole thing to the k power K is the number of hashes we have in our bloom filter And this winds up having a big impact on the overall false positive rate because the fewer hashes you have the more likely You are to have a hash collision for all of the hashes n is the size of our filter in bits and M is the actual number of elements in the set we're approximating and as this grows we'll get more false positives so we have a formula and If you're like me you sort of look at this formula and you think I basically have some idea how this works But I don't have a really clear picture of what this actually means for an actual application that I might care about right But what this gives us is this gives us something that we can plug in and think about for a problem We might care about and plot it and figure out where things break down And so that's what we'll do So this is the the false positive rate for a 16,384 bit bloom filter with three hashes as we add unique elements to it So the x-axis is a log scale and it's the number of unique elements We've added to a bloom filter and the y-axis is the false positive rate So the underlying implementation of this is a bit vector that takes up 2048 bytes That's all the space we're using So if you think about it in those terms the false positive rate is actually really great throughout because even when you get close to having more unique elements than Elements in the bit vector you still aren't at a hundred percent yet But where you have 2048 Unique elements, that's one element per byte in the filter you have a false positive rate of three percent Like imagine a imagine a precise hat what it would take to make a precise hash table of any interesting element And how much space that would take versus this 2048 bytes To hold 2048 items with a 3% false positive rate I think that's that's really amazing the bloom filter is a totally remarkable data structure that I think really punches above its weight but sometimes Just knowing whether you've seen something before isn't enough you you want to know how many times you've seen something And so that's what we're going to look at next Let's say you want to identify I mean have you ever looked at like Twitter or Instagram? And what's popular on these social networks these social networks seen an enormous amount of enormous amount of Activity a lot of posts how would you keep track of what the most popular hashtags are on one of these networks? Or say you're Categorizing infrastructure logs or metrics from a data center like you don't need a very large data center You don't need a data center that's running a lot of services before you're talking about tens of millions of records You know per week Or per day, right? So which subsystems are chattiest which subsystems are sure in the most errors for a lot of these problems Actually calculating exact answer would would be a huge pain. You wouldn't be able to do it You wouldn't have enough space you wouldn't have enough time But a lot of these questions don't really depend on having a precise answer either So we can take tolerate some imprecision in exchange for getting a useful answer quickly with a limited amount of space So let's look again as we did with the bloom filter at some precise structures that we could use to support these kinds of queries and It's not surprising that because this is a similar problem We can use structures that look like the structures we use for the bloom filter If we have just a few elements we can use an array of pairs Where the first element is the event type the second element is how many times we've seen that event? If we have more elements and the event types have some kind of ordering We can use a tree of pairs ordered by the key which is the event type and we can update that every time we see a new one and So on with a we can have a hash table of counts instead of a hash table of truth values So again, these are essentially the same structures We'd use to represent set membership precisely and we really want to wait to sort of generalize the bloom filters that we can handle things Other than membership, right? We want to hold counts rather than true or false Just as we can generalize arrays trees or hash tables to hold arbitrary values and not just truth values So the approximate structure we're going to look at next does just that the count men sketch Uses hashing, but it generalizes the bloom filter to hold counts Instead of truth to our false values and here's what it looks like So we start with a partition boom filter, but the buckets are going to contain counters instead of bits When we insert something into the sketch we hash it with several functions and increment the counter for each Just as we do with the bloom filter So this looks pretty familiar so far, right? We've gone from zero to one because we started with an empty filter And it looks a lot like the bloom filter But once we have a structure that's populated with many counts. We might want to look up how many times we've seen a particular kind of event So as with the bloom filter, we're going to use those hash functions to find the appropriate buckets and And also with as with the bloom filter We're going to return the minimum value we get from these lookups as our approximate answer But unlike the bloom filter our minimum is more interesting because these are integers rather than Boolean So instead of just saying if we have any false is our minimum is false We say what's the smallest count we've seen for any of these buckets that we hashed to for this thing So with the bloom filter we over approximate set membership, right? We either return definitively false or maybe true and Hash collisions lead to false positives But with a count min sketch we over approximate event counts So the count we return is not less than the number of times we've seen something But hash collisions can lead to it being more than the number of times we've seen something Again like the bloom filter this basically fits on a slide. It looks a lot like the bloom filter But also like the bloom filter It's an incremental scalable and parallel abstraction for this problem, and it has some very cool properties The parallelism comes because you can just do an element-wise add of two bloom filters to get the bloom filter of their union a Really cool thing that you can do with boom filter up with Count min sketches that you can't do with bloom filters is you can take their inner product as well and Get an estimate of the size of the join Between two streams of events, and I'll show you what that's useful for here We just sum the result of multiplying the counts in corresponding buckets After we do all this we get an estimate of the size of the join Right and sort of stepping through here and this turns out to be useful if we hash the same kind of event in two different sketches So if I have infrastructure logs, and I'm hashing log records in one count min sketch For the subsystem and one count min sketch for the severity I can ask questions like how many times did at CD have an error Because the things that are in both of these will be the log records that were error log records that at CD produced So it's that's a really nice way to efficiently get an answer to that sort of question We can also use the count min sketch as a building block for an interesting problem like these top k queries Which you can think of as like trending topics on Twitter or the most popular wikipedia pages or most popular search queries that you've seen search terms that you've seen in a search engine and Support these top k queries by combining a count min sketch with a priority queue So when we insert an element into the sketch We'll also look up its value and insert that value into the priority queue If the key is already in the queue, we'll update the priority and move it if necessary So after we do this a few times Looking up values and and keeping track of the top few that we've seen We'll have an estimate of the top in this case five elements and Because with the count min sketch Sticks around and has counts for things that we can hash to it Even if we lose this priority queue we can probably reconstruct it as long as the distribution of popular things doesn't change that much in the future So the queue fills up and we get we get an estimate of the top k things For a concrete example if we wanted to track the trending topics in a social network This is actually a really big problem, right? A lot of people are no longer using Twitter because it's frustrating because they turned off support for third-party clients but if you are still using Twitter, you know that Twitter gets more than half a billion tweets per day in scores of different languages And so it would be really expensive to keep explicit counts of all the Topics or even the hashtags you observed in a given day and if you want to understand Sentiment that people have for various topics you've probably even want to get find your grained with that you want to track Trending topics that you can drill down by day or by geographic region And so you need a way to represent summaries of trending topics that was small enough So you could keep one for every hour one for every day and one for every geographic area that you've wanted to track separately In this case if we said we wanted to track find the most popular topics over the weekend I'm sorry Saturday and Sunday should be should be read in this in this figure It's a little hard to see on the projector You could support that for having an account man sketch for every day and then simply adding the sketches for Saturday and Sunday In a similar vein if you're running like a video streaming site And you wanted to identify the most popular videos based on views in a geographic region like the Americas You could do this by building account man sketch and a top case structure for each of the 35 countries in the Americas And then taking the Union of all of them Now the Americas aren't monolithic and you might wonder whether videos that are popular in Boston are also popular in Tulsa Or whether videos that are popular among Francophones in Quebec are also popular among Lucifones in Sao Paulo But you can get approximate answers for all of these queries by looking at the inner product of the count men's sketches for each region And dividing it by the total number of likes that you've observed in both of those regions You can even sort of do more interesting things like our videos that are popular in winter popular in the summer Well, you could make a controlled experiment by looking at count men's sketches for the Northern Hemisphere and the Southern Hemisphere separately and doing comparison with those So another problem that I want to look at is the so-called count distinct problem, which is if you have a Stream of observations and you want to turn it into a set and say what's the cardinality of that set? So if you just wanted to count the number of things you've seen That's trivial, right? But if you want to count the number of distinct things you've seen that's sort of interesting so as before We can use precise approaches, but none of these precise approaches. We've looked at will scale to a set of interesting size Very easy though If we have a bloom filter we can use one of a few different techniques for estimating the cardinality of the set It's approximating and most of these are a function of some of the observable properties of the filter Whether it's the number of buckets the number of hash functions or the number of set bits Here's a Simple implementation on our partition bloom filter this technique works really well for filters that aren't too full But as our false positive rate increases it begins to dramatically overestimate the counts Which is a problem if we want to estimate the cardinality of a really large set So the technique I want to talk about to address this is called hyper log log And it counts the distinct elements in very large collections And I really want to dive into the intuition behind this because it's a little trickier And I think a little less obvious than the first two things we looked at just How many people feel like the bloom filter in the count men sketch makes sense So I'm gonna ask the same question about hyper log log. I think I hope it will make sense after this But it's a little trickier And my hope is that you leave this part of a talk with the sense of why it works how it works and a definite idea What it's useful for So let's say you flip a fair coin and it lands with tails facing up This is this isn't surprising right this doesn't surprise you at all If you continue flipping the coin and you get four tails in a row That might surprise you that would probably surprise me but then I'd think about it and say well I have a one in sixteen chance of this happening It's unusual, but it's not that surprising and if I'm spending enough time flipping coins that I can think about The times that I've flipped a coin and four times in a row One in sixteen is going to come up eventually right Now if I keep flipping the coin and I get 64 tails in a row I may start to suspect that my fair coin is not actually a fair coin Because there's a vanishingly small probability of getting this result by chance right one in two to the 64th one in 18 quintillion. I don't even know what that number looks like. I have no way to have a concept of how small that is But I do know that there's not much chance of getting 64 tails in a row So what do coin tosses have to do with set cardinalities? Well, if we have a source for uniformly distributed n-bit numbers We can think of these numbers as sequences of n coin flips right So every bit in a uniformly distributed number is independent of every other one again assuming you have a good hash function And it's equally likely to be one or zero So the probability of seeing a number that begins with n zeros is one in two to the n Just like the probability of flipping a coin n times and getting n tails in a row Is one in two to the n So we can estimate that if we see a number with n leading zeros That we've probably seen two to the n numbers because the chance of Seeing that many leading zeros is one in two to the n so in this case on the first Uniformly distributed n-bit number we have we have zero leading zeros. We can assume that we've seen one number If the second one comes up, we'd assume that we'd seen 32 right and so on so Every time we have another leading zero The number of numbers that we could have goes in half right and This if you think about binary this sort of it may be intuitively makes sense but if we look at the cumulative distribution of numbers and here i've just taken 4096 Uniformly distributed 32-bit numbers and plotted the cumulative distribution of the number of leading zeros So you can see that as you might imagine half of them have no leading zeros 75 percent have one leading zero 87 and a half percent have two leading zeros and so on and as we move to the right Each bin takes up about half of the remaining population every time we're adding another leading zero We're cutting the number of things we could possibly see in half and the chance of having More than a few leading zeros becomes very very small so we have a technique For estimating the number of distinct uniformly distributed random numbers we've seen by counting the largest number of leading zeros and If we didn't have a hash This would just be a pretty cool trick right like oh i can i can tell you how many uniformly distributed random numbers you've seen That makes me a hit at parties right Like but since we have a hash we have a way to turn An arbitrary object into a uniformly distributed random number So we can use this technique to count Distinct ip addresses or search query terms or or any arbitrary object Just by using a hash So hashes take arbitrary objects they map them to fix size integers And a hash function is always going to return the same value for each input If you have a good hash function the results are going to be uniformly distributed And we can use our insights about how likely it is to get a certain number of coin tosses in a row To estimate how many unique objects we've seen based on the results of that hash function So if the largest number of leading zeros we've seen is one we can estimate that we've seen two objects Now the problem with simply counting zeros though is that it leads to really high variants Right like I don't want my estimate to always be a power of two Because those grow pretty quickly Um, and I don't want my estimates to be that course But there's a technique we can use to smooth out that high variance, and that's what hyper log log does Instead of just tracking one count of the largest number of leading zeros we've seen We'll divide our hashes into several subsets And track the largest number of leading zeros we've seen separately for each subset So in this example, which is just small enough to fit on a slide and is not a structure you use in the real world For anything we're using an eight-bit hash and eight counters For a real world application, you typically use a 32 or 64 bit hash and between 16 and 65,000 small counters That is between two to the to the fourth and two to the sixteenth The largest of these structures will answer queries really accurately, but use up only a few kilobytes of memory So we'll decide which counter to update by taking the first few bits of the hash So in this case We've identified the hash that we care about We'll pick that bucket And then we'll look at the number of leading zeros in the rest of the hash In this case we have two so we'll add that the largest number of leading zeros we've seen is two Taking the maximum of zero and two For the next object we'll select counter six We're starting from the starting from the right here And we have no leading zero so we won't update the counter After adding a few entries to the counter registers, we can estimate a count And we're going to do this by taking the average Of all of the registers So what kind of average do you think we should take here? You take the arithmetic mean of all of these things That just doesn't sound right does it so if you think about a probability as a rate, right? Like i'm going to see this in one to two to the n times What's the right way to average a bunch of rates? Anyone know a harmonic mean is actually the way to average a bunch of rates So if what hyperlog like does is it it takes Two to the values of each of these registers and takes the harmonic mean of these And what this gives us for this example Is that it estimates that for these register values we've seen 16 elements in our set Now if you had 16 elements in the set you wouldn't need a probabilistic structure, but again it fits on the slide So as with the other structures you can add these hyperlog logs together They're composable via commutative and associative binary operation You just take the maximum of each pair of registers at each index As with these again The code fits on a slide Right you can sort of read this and and understand it and it makes sense So Actually using these in production there are some subtleties you need to get as you might imagine You can get much better performance by paying attention to a lot of details I'm not going to talk about those details, but I will show you where to go to learn more And there's a great paper from From google labs in ebt 2013 Basically sort of detailing all of the things that some engineers at google did to make this a really Much better technique than sort of the the stock implementation So before we wrap up, I want to have A couple of sort of brief Look at two problems. We won't talk about in detail today We can think about these almost as advertisements because i'm going to sort of invite you to do some additional things To learn more about stuff in this arena The first problem I want to talk about is finding similar documents Let's say you're a literary agent you're reviewing a manuscript and it starts out with this sort of promising passage It seems like it might be kind of fun. Funny. It's a little clunky But it sounds sort of familiar and you start to wonder have I heard this somewhere before And in fact if you're if you're a literary agent, you probably would think about like well Where have I heard this before and it's a lightly edited copy of the beginning of Jane Austen's Pride and Prejudice But if you didn't already know that You'd probably have trouble figuring it out, right? Maybe you'd search the internet for some phrases see if it see if it came up anywhere So plagiarism detection is a really interesting problem Those of you who've ever taught classes know that plagiarism is a really serious deal And it happens more often than anyone would like to admit And it's an interesting problem both for human language pros and for computer language programs But even if you aren't a literary agent or an instructor There are a lot of interesting natural language problems that are related to this like if I wanted to Filter web page results by grouping similar web pages together Or if I wanted to present a view of news stories and identify news stories that are related So you have the same wire story getting republished in a bunch of different newspapers You don't want to return all of those as separate search results. You want to group them together So let's see how we'd solve this problem precisely and then I'll introduce the technique and show you where to go to learn More about it So the first thing we do is we get a set representation of the document In this case, we represent the document as a set of words There are other representations we could use as well like taking the set of all substrings of a document of a certain length Like all of the five character substrings of a document And once we have that representation we can see how similar it is to the set representation of another document So if we want to see how similar two sets are there's a simple way to measure this called the jacquard index And what we do is we take the size of the intersection of two sets and divide it by the size of their union So if we consider these two sets, which I've represented here as bitmaps They have three elements in common And ten elements in the in their union So the jacquard index of these two is three tenths indicating that they aren't particularly similar Now as you might imagine we can use the jacquard index with larger sets like with document Sets representing documents to identify similar documents The problem is that yeah, you can compute set intersections and unions in linear time And the jacquard index isn't particularly expensive But is linear time really scalable? Yes, who thinks linear time is really scalable? Who thinks linear time is not scalable enough? Who is not willing to raise their hand? Yeah, so so linear time is not scalable enough for the kinds of problems we want to solve with Linear time for the set of all words in a large document or the set of all five character substrings in a large document Adds up really fast and the constant vectors get really big And then if we need to do the pair wise Comparisons of every document we'd see right that that is really where where this problem kills you because it grows Quadratically, so if we have 10 million documents We have to calculate and sort 50 trillion jacquard indexes Just to find the most similar pairs and I don't want to wait around for that and neither do you right? So There's a technique to solve both of these problems. It's called min hash. It's very cool If you combine min hash with something called locality sensitive hashing You can quickly identify things that are likely to be similar and then run an expensive operation on a very few things To identify the things that really are similar. I'd recommend you do that I'm going to have a link to a notebook at the end of the talk where you can learn more about this The last thing I want to talk about is sketching distributions We learned about mean invariance estimates, but sometimes you don't just want a mean invariance estimate, right? Like if you're talking about sort of Inequality and someone tells you what the mean income is in a given community That's that's like totally meaningless, right? You want the median income because the mean is going to be skewed by outliers So if we want to know the median or if we want to know the 90th or 99th percentile Or if we have distributions that might have similar parameters like the uniform distribution Which has a cumulative distribution that looks like this Versus a normal distribution, which looks more like this. We really want a way to say What does the cumulative distribution of the data? I've seen looked at look like And there is a way to calculate these that's incremental scalable and parallel and my colleague Eric is going to be Eric Robinson is going to be talking about this later this afternoon in this room Eric In this room at 450 430 430 so this technique is called the t digest. It's very cool and Eric has a bunch of cool applications for it, too So like I mentioned at the beginning of the talk my daily work involves machine learning And you may be thinking like well, what does this have to do with machine learning? Well, so a lot of these techniques are actually useful in the sort of preliminary stages of the machine learning pipeline, right? If you want to understand your data if you want to visualize it if you're doing feature engineering These are techniques that should be in your toolbox but I also want to encourage everyone to take a broader view of machine learning What is a machine learning model? If it's not a compact sort of fixed-size summary of data that can support queries and predictions and tell you something useful About something you may or may not have seen Right, so by either of those definition by the definition what we've been talking about today is machine learning But again these structures are also things that you can use as building blocks From techniques that you might think of as more sort of traditionally machine learning. Here's what we've looked at The first thing we saw was a technique for calculating mean invariance estimates for a stream of observations And we introduced the ideas of incremental parallel and scalable algorithms The next technique is the bloom filter, which is totally cool because it introduces the concept of hashing It's a very to make these structures scalable It's a very simple Technique that does very useful things And uses very little memory to do so The bloom filter is generalized by the count man sketch which tracks unique event counts rather than Set membership we saw how the count man sketch is Scalable incremental and parallel just like the bloom filter And we can also use it to support top k queries Trending topics and approximate the size of joins between different subsets of our data The last thing we saw was hyper log log a structure that exploits the fact that hashed values are uniformly distributed To support counting the number of distinct elements in very large streams And you can really get precise counts of hundreds of billions of distinct elements with only a few kilobytes of counters Which is also really cool So I hope you've learned a few new tools in today's talk and are inspired to tackle some new problems Here's how you can keep in touch with me. I'm will be on twitter and github You can reach me via email. It will be at red hat dot com I have a web log that I update occasionally at shepo dot free variable dot com If you're interested in developing modern applications that use scalable data processing or machine learning You should also check out red analytics.io, which is a red hat supported community For building intelligent applications on open shift and as I promised there will be code There's a notebook if you scan this qr code You can you'll go to an interactive notebook that you won't need anything It will just sort of let you start running it and experiment with these techniques in your browser Everything we've talked about in the talk except the t digest So, uh, it's great to be a dev conf in the us. Thank you so much for your time and attention and this extra long session and I Take any question that people have now yes For the counting in sketched you is there a bound on how how much the error is on your estimate versus the actual value Yeah, let me I don't have the formula for that in the slides, but let's let's take it offline and we'll we'll find it sure So quick question on the the document sample you're seeing so the bloom filter would contain enough Slots for all the dictionary words. Is that the Size of the filter so in the hyphenation example in the hyphenation example The bloom filter contains just the set of things that you need to look at the dictionary for So if if you can say like I have a heuristic to hyphenate words that works 90 of the time And I have a big dictionary that has the complicated sort of special case rules for 10 of things Then what the bloom filter has is it's basically an index for the dictionary So you look at the bloom filter with a given word If the word is not in the bloom filter, then you use the heuristics because it's okay If the bloom filter is in the dictionary, then you you hit the disc and load the load the load the rules to see Whether the disc is in there whether the word is actually on the disc or not In that case I was wondering if you'd heard anything Uh Any cases where people are using that last algorithm you discussed that text plagiarism to possibly just detect bad literature Well, it's it's just it's just similarity. It's not making value judgments, but Yeah, so I mean This is this is a fun problem. We should talk offline about like some I think there are probably some other nlp techniques You could use to find bad literature Um, I was just wondering how does the min hash perform as compared to something like a word-to-vec model for the document? search so Yeah, I mean sort of sort of apples and oranges. So what word-to-vec does is word-to-vec trains a representation of vectors so that words So that the vectors basically have semantic meaning for the context that words are used in so two words that map to similar vectors Will be used in similar contexts in a document. So there's also this There's there are extensions toward to-vec that you can use with sentences or paragraphs or whole documents that have a distributed vector representation of Documents as well so you can say like what's the similarity between these two things cluster in that space um I don't know of any work comparing min-hash toward to-vec or to doc-to-vec, but I think the It's sort of a different problem that the min-hashes is a simpler technique that would be easier to train And you know, it doesn't depend on sort of building up a corpus and pre-training that model either So it's something you could do in a single pass as well Because my main concern was like because if you're plagiarizing something you're probably not going to just change a few words You're going to take synonyms of the word, right? So min-hash would probably not be able to or would it so depending on where you set the threshold The idea is that if you're plagiarizing, I mean if you've totally rewritten something like min-hash won't detect if you've just stolen someone's idea Right. I mean the thing you're looking for is if if they've actually taken the prose and substantially you're used it So in the in the sort of set of words Model that might not be ideal. You might want to do the set of substrings Instead, but I think depending on where you set the threshold and I mean There are companies that use min-hash to provide plagiarism detection services. So It works well enough, I guess Thanks. Sure I have a question myself So You specified that the bloom filter is going to be fixed size. How do you decide the size of the bloom filter? Yeah, let me let me pull that up here So I said I was only going to have one slide with math mode. I think it doesn't count if I show it again, right? Um, really it's it's just sort of optimizing for a trade-off between how much space you're going to use And what false positive rate you can tolerate Right. So for the for the dictionary on disk example, like I mean that was in the that was in the early 70s so like the memory the gulf between accessing something in memory and accessing something on disk was not as dramatic as it is now right, but if you say like How many false positives can I tolerate for the expensive operation? right In that case you could sort of you could sort of analytically model like well, how expensive is it to hit the disk and how many of these How many of these can I do spuriously before the performance of my application is unacceptable? Then you would use that in conjunction with this formula to pick a filter size That would be likely to give you less than that false positive rate um, so earlier you had a very big cache problem um But later after using the bloom filter and using multiple hashing algorithms Don't you still have a big cache? like you're storing a lot of data by So in the in the webcaching like the akamai webcaching Problem situation so in that in that case you're maintaining a bloom filter in parallel to the to the cache Does that answer your question? So the bloom filter itself is not a cache Okay, okay, but it does um Does it store it in the cache? Does the bloom filter itself stored in the cache? Yeah, I mean it's it's in it's in memory on the servers that are Serving the cache Any more questions? Thank you, will you thank you so much Talk real loud You want to start? Okay So thanks for joining me today. My name is Michael McEwen and uh, I work for red hat and i'm going to be talking about building a patchy spark cloud services in python So to start with What let's talk about what is a cloud service or at the very least what I mean by a cloud service and what I want to talk about today And so I'm kind of relying a lot on definitions that have been put out by the cloud native computing foundation And this is an organization that's like a governance body That is kind of helping to govern projects like kubernetes and prometheus and What they say is that a cloud native application should be something that's containerized So, you know, we're talking about building for containers. We're talking about deploying to kubernetes So this is obviously a strong part of the story They also say that a cloud native application or service should be dynamically orchestrated And so what this means is that you can use the container with a container platform to, you know, migrate between instances It really should be generically useful in those in those situations And then they also say it should be microservice oriented and this is a really nebulous topic. It's a little more Philosophical or ideological, but the way I take it is uh, I kind of look back to the unix philosophy of old That a microservice is an application that kind of does one thing and does it well And so really what you're talking about is building purpose built applications that you're going to put into a container and deploy to the cloud And here's the link to their f aq They've got some great language that kind of talks about what these platforms mean and what these applications are and so I highly recommend checking that out Now since we're talking about the cloud or we're talking about cloud native The platform that i'm using is open shift kubernetes Now how many people here are familiar with kubernetes or open shift? Okay, pretty a pretty good audience. So You know, this is this is like the generic diagram I'm sure many people have seen this, you know, you've got kind of your container network and everything But what I'm most interested in Is this part over here? Because I want to use this as a developer and I'm kind of interested in how does it connect to my Source code repositories and how can I get kind of automated build features in there? So although all this part is really interesting from an infrastructure point of view What i'm kind of curious about is this part and this is what I want to talk about today So uh-oh looks like we've got an image that's out here I'm going to switch browsers quickly because this is Apparently I have a I have an issue here Sorry about this So what I want to talk about is Apache spark and how many people here are familiar with Apache spark Okay, so again a good number of people So this diagram might look familiar to you and this is basically a general outline of what Of what an Apache spark application might look like, you know We have what we call the driver process Which is where all your user code lives and then there are a number of executors that help perform the distributed work And underneath all this is a cluster manager that controls how these pieces interact with each other And so I'll go through some of this a little quickly because it seems like a lot of you guys already know this but Kind of the fundamental abstraction at the base of spark is something called the resilient distributed data set Well, you know, we refer to as the rdd and this is really the the primary or base level abstraction that happens for all the data and what it is is a partition lazy and immutable Homogeneous collection and so what does that kind of mean for the resiliency in the distributed nature of these things? Well, they're partitioned meaning that when the data comes in Spark makes partitions in your data set. This makes it easy to distribute that data Second they're lazy meaning that any calculations that need to be performed on those data sets They don't happen until they actually absolutely need to return a result And finally they're immutable meaning that you can't change the the data set You can make a new one, but you can't modify the one that's being distributed And these pieces together help to build this resiliency into the system So if if one piece falls out it's very easy to recalculate that partition and send it back to do work And this really helps spark to become kind of a stable platform to do these type of calculations So what does this look like in action? Let's say you have an array of numbers and you and you want to do a calculation to say which one of these are even How many of these numbers are even? So the first thing I would do is tell spark to parallelize this this data set And that means it's going to distribute these things and it's going to create the data set for me So you can see this is our rdd of each number in its own partition And then I'm going to say perform this filter operation on my data set And this this will give me a new data set and in this case I'm just looking for any number that has modulo 2 equal to 0 Meaning it's even I want those in my new data set and so I end up with 2 and 4 and I count it Now I know how many even numbers are in my data set So this is a really simplified look at the operations I might do But this is how these these rdd's are built up and how they might be distributed to do work So when we take open shift and we take the model of spark This is what it might start to look like at the infrastructure layers So we have our nodes that are the physical nodes where the cubelets live And inside those nodes we have our container pods and you can see that you know Over here we have a python application and maybe it's got some spark containers You know, maybe these are the executors and this is our master You know, maybe we have more applications a mango database So you can start to see how we can use the platform to distribute the different processes that are occurring for us So what is a spark application? And this is kind of the way that I I generally reduce these things you have Source data that's going to come in you'll perform some sort of processing on it and return results now Source data and results can be very nebulous in many ways, you know source data might be coming from a database It might be coming from a file on a file system It might be coming from a stream It might even be coming from an api call where data is pushed in Likewise results could mean the same thing. So some of these are abstractions that you'll have to deal with And what we're looking at here is a very simple python Spark application and this is going to do Kind of what we just looked at earlier It's going to take in a data set and then it's going to parallelize that data. It's going to run our little You know evens counting function on it and it'll count it and return that And so If I run this on my desktop This is maybe what it would look like I would have the spark submit command which is a tool that comes with spark And I tell it to take my application in this case. I'm going to say for all the numbers zero to a thousand Tell me how many of those are even right? So again, it's a very simple process and it starts to run and the jvm goes and it spits out a bunch of logs Now as an application, this is probably not that useful to me because what you know what just happened What do I have as output how many numbers were even well? You can see You know way up here and spit out some little print and said all right 500 of those are even okay, so How do I use this in a cloud situation? How do I go from using this locally to taking it to the cloud? So again, I start to think about how am I going to design my application in a way where it can become a microservice So I go back to this pattern of ingesting data processing data and then publishing it right Ingest and publish can be very nebulous and they'll depend on this the systems that you're designing for You may have a database that you're reading from to ingest data And publishing might mean sending a call to an api that another service exposes Likewise that could be inverted you might have a service that calls your it calls your microservice on an api And publishes data to a database these these will change depending on what you're doing But in general you'll be operating on this type of model So as you think about building these applications you need to consider the structural needs of what you're building Depending on what cloud you're using it may be kubernetes. It may be mazos. Maybe something else You have to know how will I deploy my application? How will I command that application from the outside and then how will I control it? What tools are provided to me by the platform to do that? And likewise, where is my input and output data going to come from and go to? And these will be dictated by the systems that you're working in there's really not a good way to generically cover all these Except to say that you're going to have to consider these pieces And so what I'd like to talk about is kind of three common architectures that I've come across And I have a feeling that many of you will come across these as well as you build applications So we'll talk about um on-demand batch processing continuous batch processing and then stream processing So first we'll talk about on-demand batch processing and generally what this means is I have some event that occurs Which kicks off processing and then of course I take some data in that I want to process and I create results So this is something that happens every time it's triggered and that could be a cron job. It could be Something that comes in on an api call Maybe a user visits a website and that produces the action, but this is one pattern you're going to see When might you want to use this pattern? So in general These are kind of some of the top things that came up You know to me as I was thinking about this when you have Non-deterministic request windows. So think about a user who visits a website like amazon They're going to be clicking through products And just looking for something that maybe they'd like to buy and every time they click on a product There's going to be returned some sort of ratings some number of stars maybe says I suggest this product for you or I don't suggest this product for you This is the type of area where maybe an on-demand call is what you want to use You know, you may not have these things pre calculated You may have some model that contains this data But you'll need to filter that at the time that a user actually hits it And you won't necessarily know ahead of time that that user is going to do that likewise When you have quick results to calculate something that can be returned very quickly because if if you have a Situation where you don't know when these things are going to happen or you have a user visiting a website They're not going to want to wait a minute for some long processing cycle to happen before results come back So this is another situation where you might think about using this technique And then likewise when you have a lot of situational dependencies So again, think of the example of a user visiting a website If your processing depends on a user entering information before the request can be performed This is a situational dependency. So this is something that you can't pre evaluate or maybe it's very difficult to pre evaluate This is another scenario where on-demand might be what you want So, you know, what does this kind of look like? I'm I'm using an example here that I'm calling the hello world of spark because it's been in the spark code base I looked just the other day at like spark 0.1 alpha and this example was I think one of the only examples that existed in there And it's a Monte Carlo method for estimating a pi, right? So you're talking about throwing darts at a dart board Counting how many land inside a circle versus how many land outside and that ratio will approximate pi for you So this is just a function that does that And you can see, you know this This part here We're doing a similar type of operation that we did before, you know We're paralyzing a range of numbers in this case. This is the the number of random points I'd like to use to to calculate pi Then we're mapping a function onto it and we're reducing that and this is you know, this is the technique for returning pi So now I've got a function that every time I call it can give me that answer for pi And what I might do is I might embed that into an http server So if you're familiar with the uh with the framework called flask for python, this is an http Framework, this is what it might look like if I embed this function into a return So now I've got an http service a rest-based service that can basically take a request and give back pi whenever I need it And this is just one way to look at it You might use grpc. You might use some other kind of remote procedure call mechanism But this is just one way to look at it So let's let's move on from that and talk about continuous batch processing right and and I look at this is uh This is a type of scenario where you have data sitting in some sort of data source Your processing is always occurring There's no need to trigger it with an event because you want this process to always be running and always be producing results to wherever your store is And when might you use this pattern? So if you have data that updates very frequently, let's say you have a database of users who are always giving ratings for example You want to be creating recommendations? Let's say off those user ratings and you want to be doing it continually because that information is always happening So there's probably never a time that I don't want that to be running And one way you might use that is when you're creating machine learning models for evaluation, right? So if we think about a recommendation engine Where users from all your products like amazon for example, they're always rating what they like and what they don't like You want to continuously be creating models so that you can evaluate How those models are performing against what you have in production, right? So you want to say As users add more data are my models getting better? Maybe they're getting fresher in the case of a recommendation system You probably always want it to be fresh because users are continuing to add information And then another way to look at this too or a situation you might use it in is what i'm calling life cycle management processes So think about a lot of the work that gets done in distributed computing is data engineering It's transforming one schema into another schema or taking one format and turning it into another format This is something where you might just want it to be continually running You say i've got users who are putting in data non-stop Maybe it's a text data and i want to make sure that no one's putting in words that are you know on our band list or something Right, so you want this to always be running always be searching for results that are coming out of that Now what what might like this look like so this is a piece of code from a recommendation engine that One of my colleagues who's actually sitting here helped to write rury in the back there And this is part of a model generation service and what it does is you can see at the top there's this Wow true loop and it does some sort of database selection here to pull the ratings out of our database And then you know there's a bunch of calculation going on here And what i really want to highlight Is this part here We see where we've taken the new ratings from our database So since the last time i created a model I want to see all the new ratings that have been added to the database I create an rdd out of that and then i'm going to do some processing here where i create a model from that And so this is just always running and if it sees changes to the source data It creates a new model and it puts that model into my database where i'm kind of storing these models for later usage So the last kind of pattern i want to talk about is the stream processing pattern And this is something that i find very intriguing and i think it's a really cool way to work with data But this is where you have a stream of information that's always occurring So think about Kafka or or amq or those type of uh message bus type applications There's data that's always coming in and my processing This is a little different than the continuous batch my processing is reacting to every time data comes in on that bus You know within some sort of window And then again those results are stored somewhere else Now you probably would want to use this in a situation where you have like real time event processing. So think about An iot situation where you have sensors on maybe public transportation, right? So you want to follow where all the buses in your public transportation system are going are any of them running late Those type of things so you have a continuous stream of information coming in and you always want to be updating on what's happening So that may be one area Another is if you're working with systems that are built on a broadcast messaging system So i like to think about the fedora message bus. How many fedora users we have in the audience here Okay couple fedora Since it's a large community system they have something called the fedora message bus and it's it's a federated message bus system where you have Messages coming in from build systems Maybe for all the different packages that are being created messages coming in from mailing lists, you know all sorts of information being aggregated And this is a situation where well, I would obviously want to build something to that message bus because that's the architecture of the system i'm working on and then likewise Another level to this is what what we call like, you know, what people are calling kappa style architectures And and this is a way to look at stream processing where you have a stream. That's your input data You have processing happening and then your output is always going to be to another stream So you're kind of creating these message bus scenarios where you know one topic might be Your your clean data and then you have a process that runs and maybe changes the schema or pulls out some specific information Lays it to another stream and this allows you to build up really complex hierarchies of applications That don't necessarily need to depend on each other. All they really need to depend on is is the message bus So spark has a really cool api called the structured Streaming api and and this is kind of what it looks like there's multiple ways to do stream processing in spark But I think the structured streaming is really interesting and and what you do is you kind of build up this Set of instructions you tell spark where will my information come from and that's kind of up here I'm telling it a a Kafka broker and then I tell it what to do So I wanted to select, you know in this case, this is real simple It's just taking every value that comes in on the stream and casting it to a string and then Re-broadcasting that so this is just really kind of looking at a simple example And then what happens is all those strings that come in get grouped by the value that they created and counted So what's happening here is this application is doing like a word count on a stream It looks at every string that comes in it groups them by similar and then counts them up, right? So you could say imagine you had a stream of words coming by this is just going to count them And then at the bottom here you could see I'm telling you where I wanted to put the output of that stream And then I just tell it to start in this case. I'm just storing it in sparks in memory Storage and I'm giving it a name so that I can query that so at this point It's doing a bunch of work, but how do I get the results out of this? So what I might have is a function like this That allows me to look at Sparks internal kind of sql in memory representation and then I can I can run a query on it So in this case the query that I'm running is I just want to know the top 10 entries of all the things It's counted so I want to know the top 10 most, you know frequent things that are happening But this I could call this function on demand when I wanted to get information out of it So that kind of brings me to the next way you could do this, right? And this is an example of what you know the kappa style architecture would look like you have a stream coming in You have processing happening and then you have a stream that it lays it out to And if we look at this kind of similar function that we just looked at the top part of it's all the same It's all doing the same work But if we look at the bottom part where it's writing the output of that stream I've told it now just to put it on to another Kafka topic, right? And so what this means is that I don't have to worry about having a routine that pulls that information out using an sql query I could actually have another microservice that just listens On that second topic and then it would It would be automatically giving me all those counts and I could do whatever I needed to there I could aggregate them or you know, I could do something different at that point Okay, so You know, we've talked about some different patterns you might use How do I take these from that desktop example and bring them into the cloud? You know, I want to take it from source code I need to turn it into a container and then I want to push it into my orchestration platform And at the same time I need a way for the user to still get in and out or myself to get in and out of it So the group that I work with at red hat We have a community project called red analytics.io and we've created some tooling a project that we call oshinko And this allows us to use some of the source to image type workflows that are in open shift to say I'm going to take my source code from a git repository I'm going to use the source to image to build that into an image that can run And then when it gets deployed a spark cluster will go with it and be bound to my application's life cycle So in this way, I don't even have to manage spark anymore I can use the workflow that I'm used to in open shift going right from my code Making pushes to my code and that might go through a you know, a ci testing framework And then when it's successful it gets deployed onto open shift and a spark cluster will appear and be bound to it So I'm going to assuming nothing else goes wrong. I'm going to try and demonstrate for this view, you know, real quickly here So I've got a I've got a small github repository here And this is a tutorial that you could find on rad analytics And this is a web micro service that's going to create that spark pie for us, right? So it's going to create an http service that I can on-demand query To get a spark calculation and you can see my repository in this case My repository is pretty simple. You know, I mean, I've got to read me I've got my app file Which is not, you know, not overly long It's just a little flask application and then I've got, you know, the requirements like any python application might have So what we're looking at here is Open shift This is my project and I've already taken the liberty of loading into this The rad analytics templates that I'm going to use and so what I'll do is I'm going to select from my project the template that I'd like to use So I'd like to launch a patchy spark python. So, you know, I select the template that I want Kind of click through the description. You can see now it's asking me for a bunch of information here So maybe I'm going to call my service spark pie and now what it wants is The url from my github repository So I'll just copy this from here Now there's a bunch of other options I could use here Maybe if I wanted to build from a branch or there was a subdirectory I was building from or, you know These options help you control how the application gets deployed But my application is written in a very simple manner So I don't need to fill in most of these and likewise at the bottom I could I could adjust how the spark Cluster gets deployed. I could change the options that go to it So I'll click create what we see now is Open shift this is being built on open shift. And so if I look at the logs for this You can see this is kind of a standard python build process and then it's pushing it to the internal registry Now you can see at this point my pod is up and running But what's happening is the spark cluster is being deployed with my pod. So This is automatically being bound to my application and it's kind of given it a random name Now the last thing I need to do to get to this is just expose a route to it so that I can get uh, I can get to it And now if I click on this, hopefully it'll work Okay, so I hit the root endpoint and it tells me you know the python flask spark pie server is running I need to add this extra thing to get more information. So If I add this extra route See now there's kind of this weight going on this goes back to the quick result side of this right What what's happening all I can see is a little spinner going but eventually it comes back and gives me A really bad estimate of pie. Okay So like don't you know don't go to the moon with this or anything, but it's it's it's fun to play with right And you know something I want to point out here that I talked about before which is Now that my application is linked to this github repository this git repository you can see I've got this thing called a build here and I don't have my webhook setup But if I if I did what I could do is push a change directly to my git repository The webhook would hit open shift and this would actually rebuild automatically for me now in this case You know I could hit start build like if I made a change to the repository I could hit start build and it would run and then deploy it again and attach it to the spark cluster again So as a developer, this is really nice because I can really easily test my changes out and even in a private project I can do this So let me Switch back here Okay So you saw when I made that web request to do the work it took a little while to come back, right And this is where one of the problems you're going to run into when designing these type of services Is kind of the synchronicity issue, right? So I make a request for pi and now that service is off doing something, right? And if I if I tell it to scan, you know to use too large a data set This could take minutes to come back, right? And you don't you don't want that result coming back later You know the user just walking away from the terminal or something so to mitigate this in our designs What we like to do is start to separate You know the api concerns from the actual processing concerns And and this might be a very common way to look at this would be, you know our main process the api Whenever I make a request for a new Pi estimate Maybe instead of giving me back the pi estimate Maybe what it'll do is right away. It'll give me back an id And then I can use that id to query the results of what's happening Or perhaps, uh You know the application on the other end of this uses a web socket, right? So I make the request and now the main processing loop can push the information back to me when it's ready And in the meantime my application can display some message saying this is you know work is happening or whatever So you know depending on what this api is You'll have kind of different ways to mitigate this but in general what you want to start doing with microservices Is is pulling apart these concerns to make it easy to deal with the other ends of them and to address issues like this Synchronicity issue So what might this look like in python? Well, this is like the main process, right? You know got some code here We set up, uh, you know cues for doing the inter-process communication And we start off some other process and send everything going This is pretty compact and I don't want to go into every line of it But what I want you to take away from this is the top line which says import multiprocessing The python multiprocessing package is really powerful And I would say that if you're going to start doing these type of things Read the docs on that package because the primitives in there are very easy to use And so if this is the main process side This is maybe what our processing loop looks like, you know, and so we've got this big thing here where there's You know and this is coming from a service, uh That actually responds to uh incoming requests for recommendations, basically, right? So you have a user who wants to get a recommendation. This will kind of do it for you And you know, it's a big piece of code whatever I've taken out pieces of it But the main thing to look at here Are these areas that are probably really difficult to see because they're in red and there's a lot of light washing it out But you can see these primitives this response Request Response response these are the cues That I use to communicate back with the main process And so whatever i'm doing here i'm using these primitives and again This is coming from the multiprocessing library And you know, I really recommend checking it out Another big thing that you're going to run into especially if you're doing python programming for spark is dependency management So right now spark has some really good features for jvm languages that need to distribute dependencies There's a to that spark submit command. There's an option called packages and you can give it, you know, maven targets and it will Pull all those packages in and send them out to the entire cluster so your applications can use them With python the tooling is a little behind the times So let's say we've got this application And you know the filter this is maybe like let's say we're building another service to tell us how many evens exist In the data set, you know our classic hard problem here Um, and you can see it at the bottom here is where i'm actually doing the work You know, i'm telling it to kind of make the paralyzed data filter it and count it And this filter evens function is doing some sort of database action, right? So what this means is that filter evens function is going to be distributed to the spark cluster And so what that means is each executor is going to need pi mongo in place Because what's going to happen is something like this My main application wants to talk to mongo, but now i've distributed code that also talks to mongo And so that mongo library needs to be on every one of the executor nodes And this is a situation where you might have to manage these dependencies yourself Until the spark community kind of catches up with this and gives us better tooling for doing it So just let's recap a little bit here You know, we talked about This design pattern that i really like to use he ingest publish process This is kind of the the general pattern i like to get into We talked about some different types of uh of architecture patterns you might get into when you're designing your applications We talked about You know the on-demand batch the continuous batch and the stream processing And then we also talked about The oshinko source damage project So this qr code up here is a link to this slide deck, you know, please download it and Your it's it's open source. It's it's just a reveal js project. You're welcome to use what's there Here's my email and my my blog And you know, please check out red analytics.io. We've got a bunch of tutorials there and lots of this material you've seen here Is on that site So at this point, you know, I'll take any questions and you know, thank you for your time So you guys any questions Barma, don't hit me up too hard here. Okay Yeah, I'm talking about the first pattern, uh you the client would call a rest service And the response comes back immediately, right? So That's the code you're describing. So what happens the client continuously pulls That and the second the function that that you showed us, right? It is the multiprocessing package So is the client continuously needs to connect to be The same invocation of that request right for that process to happen Or can there be like another status, you know function independent of the first one that goes back And gets the data directly from the spot. What is that? so You know the first example I showed is a very simple example, right? We just you're hitting it and it's trying to make the request and if you double up on request at that point You're going to break that because that application is really simple But once we start to separate the api Um, you know the first way that I think about it for a rest Application is I say I'm going to make a request to the rest server to start doing work And the rest server gives me back an id and that id number is the work is the the id of the work that's being done, right? So my processing, you know my processing loop there the second process It may have a queue of work requests that have come in and it knows about the id's And so when it does each bit of work it can take that id It can update the status for what's being done and the main process will always be able to see What the statuses are with those id's so my client Could keep requesting or what I make the first request to do work I get an id back and now I just query that id and the main process can tell me no, it's not ready yet No, it's not ready yet. Okay. Now it's ready. Here's the results, right? And so this is really what I mean about separating the concerns Your architecture will dictate How do I want that processing loop to kind of queue up information? And maybe I have several processing loops. Maybe that work gets distributed in a better way But really what I want to do is hide those concerns from what the user is seeing right so so that they can do that They can keep querying to say what's happening and they're not going to overload the spark work that's being done Does that does that kind of make sense? Okay, cool Cool Any other questions Can you tell us more about the oshinko source to image builder process? Sure So what what you saw with the demonstration I did was me exercising the oshinko sourced image tooling, right? so The what the tooling does is it first pulls a source code from your git repository And then it creates a container inside of of an open shift that will do the build process, right? And so that that's that log that I showed it was pulling the code and it was starting to build it, right? Once it builds that code and it's successful it deploys the built container to Open shift and then the oshinko tooling is actually inside your built container and what it will do is it says Did you did you request to use a spark cluster that already exists because you could do that, right? That's one of the options I went by If you didn't request that then what it will do is it will spawn a spark cluster for you And you could specify the configuration for what you wanted to do And then your application will run and when your application exits The oshinko tooling will kind of catch the exit on that and it will delete the cluster that goes with it Right and then your application may go away or something So that's kind of a general look at the steps that happen To do that deployment And it associates, you know, like a service with it and exposes ports So the same behavior you would expect from the other source to image tooling whether you were using You know javascript or java or python or something like that okay So you described oshinko a whole bunch without mentioning like cscd or continuous integration or deployment or anything like that Can you speak up a little bit? You described oshinko without mentioning cscd or sort of but the way you describe it and I don't know that much about it is It's a very similar workflow If like and we do something similar in a janken stack that uses helm charts to deploy stuff to kubernetes clusters What are like why didn't you work that into a more classic cscd platform? How is it better? so The the reason I didn't work it in is because i'm not really diving into the pipelines features that exist with an Open shift, but that would what you've seen here is kind of the lowest level of application development The next level of application that would development that would happen if I were going to take this into a more production situation First I would put testing between you know when my my application gets checked in to get You know, there could be a test running there and if it gets rejected then you know The commit doesn't get merged and it doesn't kick off the new build Another way to look at this is I could use the pipeline functionality that exists with an open shift To create a pipeline that says first check the code out and build it here Then run the tests here in open shift and then if all that works Then deploy it and I could say deploy it to another project or something So part of the reason I didn't get into talking about it today is because those primitives start to exist at a higher level But once you've created your applications in this manner You know, they become very easy to kind of mix and match and I think if you're using Jenkins with helm and kubernetes You're doing something very similar What what open shift kind of adds to that is this You know kind of UX around building the pipeline for you, right? So if you're not a Jenkins expert or even if you're not familiar with Jenkins the pipeline tooling Allows you to specify those things using a language that's a little bit easier than diving into you know Jenkins configuration or a travis configuration or something like that So really that would depend on on what you're doing with your application design But it starts to exist at a higher level than just creating the applications And so the oshinko tooling helps because when we're automating these things We don't need to automate the spark cluster creation. We can just let the tooling take care of it for us So when it runs the tests it actually spawns a cluster dynamically Runs the full integration tests and then can report on whether it succeeded and then you know Deletes the spark cluster after it's all done without having to kind of build it into my jenkins file or something like that I think we're running low on time. So Okay, so if you've got more questions come bug me afterwards, you know, yeah walking for questions after Thank you, michael And you can see that he's curious. He's wondering why we would even care about sketching Which is a good question We like to work with sketches because they basically can represent our data in structures that are very very much smaller than the actual data And because they're smaller, they're also frequently much much faster to operate on But even with both of those efficiencies They still preserve all the essential features of the original data Um, oops I had I actually was going to do a quick vote. Um, how many How many of you have worked with data sketching previously?  I actually I'm going to show you that all you people who did not raise your hand are actually being too hard on yourselves If you've ever taken the mean or variance of some numbers, uh, you've done data sketching You've preserved like the mean and the variance of the data that you were actually working with If you've ever clustered data the Centers of your clusters are a sketch of your raw data Or if you've trained a machine learning model, um You know any any learning model is actually a compression Of the training data that you fed it and so um learning models are also all data sketches and so Data sketching is actually all around us and uh, we do it all the time even if we might not realize it The particular sketch I'm going to be talking about today is called the t digest and it was introduced in this uh paper here Competing extremely accurate quantiles using t digest by ted dunning and olma urtl It now has Implications in most popular languages that you can see here and also scala And there includes a library of integrations for a spark and pie spark which I'll actually be demoing later in the talk So what is it exactly that a t digest is sketching? you give it a series of numbers just raw numeric data and It will take that input and maintain an estimate of the cumulative distribution function Um, so what is that? Um, it's been a while since you've had statistics. So over here on the left you can see we have a Density which represents like a distribution of the data that's coming out of your system And if you take a look at that value x down there in the lower left everything to the left of that x Um has a certain mass and a distribution and you take that mass or area And plot it like over on the right. What you're plotting is the cumulative distribution So you can see as x moves further and further you're You know basically more and more of The distribution is to the left of the x and it keeps going up and up and eventually You've seen basically all of your distribution and the cumulus of the cumulative distribution maxes out at one Having seen all the data essentially So at this point you might be wondering it's like well, it's fine to have a cumulative distribution And if I've sketched that that's great, but um, does that actually allow me to say anything at all about the Real distribution the non cumulative distribution So the good news is if you have one of these cumulative distributions or a t digest sketch You can take the first derivative of that And get back the original distribution And Anybody who's like an enormous calculus geek like me you would recognize this is actually the fundamental theorem of calculus Which you might have been exposed to in college But if you haven't it doesn't really matter the main point is To rest assured that if you have a t digest sketch you can actually get back the original distribution whenever you want to So the t digest has a lot of excellent properties which are common to a lot of data sketching data structures If you have a t digest and you Add another data point into it You just get an updated digest and it has not increased in size and so its size remains constant as you feed it data That's a great property because of course if you have a very large data source Throwing data points at you Which is either too large to work with in one chunk conveniently or is possibly simply not bounded because maybe it's streaming data It means you can use this property of update ability to maintain a Constant size running sketch of your data no matter how much of it there is or how long you try to sketch it So what can we do with this? I'm supposedly running some kind of rest service and we have users making queries against this And we want to keep track of our query latencies um And we have kept track of a you know sketch of the cumulative distribution. What can we do? We can do visualization we can say well, what does this distribution actually look like? What's the shape of it? We can ask questions about quantiles so we can say well are 90 of these latencies under a second or not So you can answer basically service level agreement kinds of questions with that um Another property which is less appreciated is you can take these sketches and use them to simulate More data, so if you want to simulate data that looks like the data you've seen before these sketches can also do that So there's even more payoff You know back on dinosaurs ruled the earth um And I was young the you know data files basically, you know, we're simple It's like you had your data it lived in a single file And you did operations on it and this was all very easy to reason about um But uh today, of course, um, you know data resides frequently across multiple machines The machines may be running in you know clusters like kubernetes like here you can see I've diagrammed a artisanal small batch kube cluster running on apple II ease But if your data is all spread across, you know multiple machines you can still obviously do operations on the individual data partitions, but then You know these open the question is like well what now? And I'll be talking more about that shortly Um So I'm going to return to the t digest sketch and talk about like how it actually represents um the approximation of a cumulative distribution And all it really does is maintain a bunch of clusters and a cluster is nothing but a location And a mass and the mass is just a bunch of you know, however much of the data it has seen that landed on that cluster And so clusters with large mass Basically correspond to areas where the cumulative distribution has got a steep slope Um And at a high level it's really just that simple Um clusters are updated of course as data comes in and the update logic is also actually very simple You have a new piece of data Which has you know value and a mass of its own usually the mass is one And you find the nearest cluster And you add the mass and you update the location In a sense, that's all there is to it a fun fact if The clusters could not be updated with their location what you'd really have here would be essentially a histogram Um So The clusters can have quantiles and if you have a cluster at some location Its quantile is really nothing but the sum of the mass to the left of it Over the sum of all the masses. Um, so it's real simple So One bit of added complexity is that clusters are only allowed to grow so large they have bounds on their mass and The function that bounds their mass is this little expression here in the center And Like my colleague will I try to avoid math in my slides, but I'll be Taking that equation apart and showing you that it's actually not that hard either The bounds force new clusters So you have some new data coming in and it would like to merge with the cluster that it found It as close as to it But this cluster here is close to its boundaries.  It takes as much of the mass as it can up to its bound And the remainder is used to create a new cluster So going back to this equation Um The scariest looking part really is just this expression q times one minus q And really the only purpose of that is to be small at the end points of your data And uh thick in the middle So you can see it's as you get closer to the you know Quantile zero or towards the end of quantile one, which is basically the minimum and the maximum of your data This this function is small And the reason you like that is because it forces you to have more small clusters At the end points of your data and of course if you're Played with distributions, you know, these are usually your distribution tails And this is where you ask a lot of your interesting questions about the distribution of your data. So It's essentially nothing but a heuristic to allow you to have better resolution where you're asking the most questions Um So the other term here is the big m which is nothing but the Total mass it's like it's all the data that you've seen so far And of course recalling that this is a sketch Um, if we didn't allow our bounds to gradually increase as the amount of mass increases It would basically start forcing us to have more and more clusters And our data would start to you know our sketches start to grow Linearly with the data and that's of course not a sketch at all So the nice thing is that the more data we see The higher this bound curve gets and it just allows our clusters to grow larger instead of having more of them And the last term is a term that you the user actually get to play with Just the compression factor And it works in some ways a little bit similar to mass except it never changes And so the idea here is if you have a Small value in compression It's keeping the value of this bound curve low and it's forcing More clusters and so you're basically Allocating more data points for higher resolution at the expense of keeping around a little bit more size in your data sketch If you increase that It allows there to be fewer larger clusters. So you're basically increasing the compression rate on your sketch So t-tigest are mergeable And what that means is if you have Like these two sketches like this orange and green one up here you can take their clusters and Union them together and then merge them Into a final result and the final result is a new sketch which represents Sort of like the data union of what you've seen in the first two um So why does that matter i'm going to go flash back to this slide here with data residing across multiple partitions So suppose you have a bunch of data partitions what it means is you can take each partition and take its sketch Like you see here in the middle But then you can merge all of those And get a final result and so it allows you to Not only operate on data that has been partitioned off in the multiple machines But it allows you to do it in with scale l parallelism So you can do each of those in parallel for you know arbitrary speed up And sketch the entire dataset as if it was a single file There's different ways you can do this You can take those clusters and merge them in randomized order the very Early drafts of the t-digest paper Basically proposed this as the emerge algorithm I implemented this early on I discovered something a little distressing which is that if I looked at The error between my sketch and the truth and I was doing tests. So I actually knew what the truth was As I merged more and more these clusters the thing would diverge further and further from the real distribution So this is not very good behavior for a sketch And I went back to ted dunning and actually engaged him on this and he's like, oh, yeah Well, we actually have a different algorithm now And what they did there's was Take them and order them in spatial order and then merge them that way And meanwhile not knowing that they had done this I had actually created yet a third method of merging these things where I just took the largest to smallest and merged into that order And if you plot all these you can see the random order is As I showed before bad And either the other two going large to small or Doing the spatial merge order are great. They converge closer and closer to the distribution the more of them you merge So it's exactly the kind of behavior you'd like And the main moral of the story is if you're designing these sketches How you define your operations does matter and it's worthy of experimentation So there's an interesting like I don't know algorithmic considerations If you're trying to implement these things the first is of course you have to maintain these things in the you know order of Space you know in the order of the values that they represent You have to be able to query the nearest cluster for pieces of data that are coming in You have to be able to insert and update clusters You have to be able to compute these cluster quantiles and another term for that Which you might see in the algorithm books is maintaining what are called prefix sums And another another constraint I sort of imposed on myself Because I'm a functional programming geek was that I wanted to make these operations immutable so that if you merge two clusters You get the merged results, but you haven't lost the other original two. So it's like you're not losing the arguments to your functions And not only that but of course it all has to be fast and so like operations are ideally sub linear I mean all these things I just described you can do in log time or better And so When I turned the crank on all that I came up with essentially as a balanced immutable tree and here I'm showing Essentially just clusters being stored in spatial order Using a balanced tree. It's hard to draw Maintaining a spatial order with the querying and prefix sums But if you're interested in that kind of thing If you follow this link here on the right There's a blog post where I unpack Basically the last couple slides and I talk some about the actual data structures. I created for that Otherwise feel content just to you know use use the tools So lastly there's a trick you can do with cumulative distribution functions and it's called inverse transform sampling which is a fancy sounding term, but it's actually Pretty easy. All you do is you start by just randomly sampling from uniform distribution on zero to one like this orange point up there And you go find the point on your cumulative distribution You know x q such that q is that value that you just randomly sampled. This is basically the in inversion part And that value x represents A sample from the actual distribution That you've sketched. So essentially these these sketches allow you to do generative synthetic sampling of data which has the same distribution as your As the original data So you can take your raw data and sketch it and then basically invert that process take your sketch and sample Data that looks like your original data So now i'm going to do a brief demo um sketching distributions and of course You to make this work you have to import All your tooling. So I have importing my py spark functions and my t digest package and of course some plotting So I can show some results So i'm going to use that query latency idea Earlier in the talk and so i'm going to just kind of like simulate some query latency. Here's the first few values They look like floating point numbers. So that's what I want And I can look at the shape of this so I use Seaborn's distribution plotting just to kind of like look at what it is i've generated here and You can see that the the data has a peak somewhere to the left of 0.5 seconds um And tails off pretty rapidly from there and if I do the cumulative distribution, it looks like what you would see on the right So Doing uh doing the um Merging and the scale-all parallelism in in spark is done using A tool called uh aggregators and I created a bunch of these aggregators so you can do this with t digests on data In spark easily. So I'll start by creating one of those for my data Seems to be making the little hamsters in my laptop work surprisingly hard But you can see that it basically turn returns a A data set with a single column and a single row and in that row Is the actual t digest sketch of the data. I just showed you and so I have to get that out of the aggregator so i'll just do that and You can see that its type is a python t digest type So now I have a t digest and we'll see what we can do with it. The first thing of course is a visual Visualization and so I can look at what this thing is actually saying about the shape of my data So the blue line is what the sketch um thought about the shape of my data and I plotted it against um the actual raw cumulative distribution and you can see that the fidelity is really excellent. Um, it's tracking Really surprisingly well So what this means is of course if you didn't have the truth like I have you know You just have the blue line you'd have some faith that these things actually perform very well as a high fidelity sketch And so of course as I talked about earlier you can use these things to answer questions about quantiles So the first row here is the median the 0.5 quantile and that's apparently 0.35 seconds or so And uh my 90th quantile my 90 percent quantile um Is 0.95 seconds and so if my service level agreement was that 90 percent of my queries have to be under a second I can tell from this sketch that I've met that requirement And if I start not meeting the requirement I can see that too as I look at the sketch evolving and ask questions And so I'll also show Some synthesized data. So here I basically synthesize 10 000 points Again, they still look like floating point numbers. This is important