[00:01] structures for Big Data System design interviews typically aren't getting into the implementation of algorithms but certain problems require approximations or clever approaches knowing about some of these data structures enables you to
[00:14] solve some otherwise intractable problems and your interviewer is likely to give you points for using them appropriately before I dive in I want to offer a caveat for newer Engineers it's better to focus on doing the basics well
[00:27] than to for example pull a blue filter into your design incorrectly or inappropriately aim for Simplicity and solve for the bottlenecks when you can justify them I.E when you have those estimates rather than
[00:42] solving imaginary scaling problems with that let's get into three data structures for Big Data our first data structure is the ever popular Bloom filter Bloom filters approximate sets if you recall sets allow us to add items
[00:56] and test their membership in constant time Bloom filters do basically the same thing but Bloom filters are dramatically more space efficient requiring an order of magnitude or more less space than a simple hashset this space Advantage
[01:11] comes with a curse Bloom filters are probabilistic and they can't answer with the same certainty as the hash set specifically Bloom filters allow me to add items and they can answer in one of two ways either the item is likely in
[01:25] the set with some configurable probability or the element is definitely not in the set this sounds a little goofy so let's build up some intuition about how this works before we dive into the system design applications let's
[01:39] pretend that we want to keep track of the names of people who have attended a meeting if we've got Infinite Space then our ideal strategy is to assign each name and identifier maybe an index so Albert gets zero Brian gets one
[01:56] Albert gets zero Brian gets one Christina gets two Zed gets 25 then we can have is an array of bits which are either zero or one you can think of this like booleans and then when Albert attends we can change his value to one
[02:10] it's really easy for us to figure out now who's attended the meeting and who hasn't on the other hand if we want to save some space we may not have all of
[02:22] these slots so what can we do now well maybe instead of assigning these sequential identifiers we can hash them we can their input so we can hash Albert and take a modulo in this case we will modulo four that would give us some
[02:37] random value so Albert might get three Brian might get two Christina might get three and Zed might get one what happens now well when we add Albert to our set we get three here and when we add Brian to our set we want to change the bit for
[02:54] two now when we analyze our resulting data structure something surprising is happening here we can say that for instance Zed did not attend this meeting
[03:07] if Zed had attended that bit would have been flipped on the other hand we can't say for sure that Christina attended the meeting because both Albert and Christina share the same value so we've saved on Space here but we've
[03:22] compromised on our ability to say with certainty who is in the set now in practice a bloom filter is going to be a little bit more comp licated first we little bit more comp licated first we can choose the modulo here which governs
[03:35] basically how many bits are going to be required for that hash in this case I chose four I basically limited myself to four bits but if I wanted less collisions I can just add more bits that's pretty straightforward another
[03:49] thing that I can do in order to handle collisions and this is essential to bloom filters is I can have multiple hashes so instead of having just a singular hash where Alber Al Bert and Christina both have the same value I can
[04:03] have a second hash where now maybe Albert and Christina aren't colliding and what this will allow me to do is distinguish the two unfortunately by having a separate hash I also need more bits so rather than just m bits now I
[04:18] bits so rather than just m bits now I need M * K bits the choice of M and K can actually be derived based on some formulas they're Linked In the choosing here here is the likelihood of a collision which is also the likelihood
[04:34] that we are going to answer yes to a query about set membership when actually about situations where you might want to use a bloom filter the first one is in a
[04:46] WebCrawler in a WebCrawler what we're going to do is we're going to be continually picking up new web pages finding new links basically discovering Pages we haven't crawled yet and then
[04:58] we're crawling one of the big bottlenecks of this system is this database of crawled Pages that's going to be constantly queried by our workers to make sure that they're not recrawling the same pages over and over both to
[05:13] check for cycles and then also to make use of good resources now if we had for instance a billion URLs in this crawled Pages database and each of these URLs was up to a kilobyte of data then we've
[05:27] got a lot of data let's see billion so Mega is million Giga is billion and then we add another thousand so we've got a terabyte of data specifically just
[05:40] storing URLs that's kind of a waste so what we can do instead is we can use a bloom filter when workers are crawling a page they can insert into the bloom filter that URL we're not going to be
[05:54] able to recall that URL later the bloom filter is only going to tell us whether we crawled it or not but that's okay if we recrawl a page every once in a while probabilistically that's not a big deal and instead of storing a terabyte of
[06:08] data Maybe we store a gigabyte of data this is a huge savings for a small performance loss on the tail end to do the math right Mega another example that we can talk about is caching usually we put a cash in front of an expensive
[06:23] operation and the goal here is both to make it quicker when we've done it before but also to reduce the load on that expensive operation so what often happens is the service checks the cash if the cash has the value we're going to
[06:38] doesn't have the value we've got to go conduct that expensive operation and then we can return that back to the user one problem with this is it means additional latency for those instances where we miss on the cash or where we
[06:51] have to do the expensive operation and this is a great place for us to potentially use a bloom filter as an example if every every time we insert something into the cache we also add it to our Bloom filter then our Bloom
[07:05] filter tells us whether something is likely or not to be in the cash we can skip the cash check for those things that we know they're not going to be present and move straight to the expensive operation now this doesn't
[07:19] work in certain circumstances as an example if we expect other people to be populating the cash or if the cash has a TTL and it's evicting items but you kind of get the gist here we're looking for those places where a mistake is not
[07:33] going to be super costly but we can benefit in the majority case where we can be mostly right with a bloom filter so just to summarize here Bloom filters are a special data structure that approximate a set and they can answer in
[07:48] one of two ways either the item might be in the set or the item is definitely not be in the set we can configure that probability by governing how big or basically how much space the bloom
[08:02] filter utilizes there's three things to keep in mind kind of three pitfalls that of all you obviously need to be quering for a set membership boom filters aren't that the second thing is you need to be space constrained otherwise you can just
[08:16] use a hash table memory is actually relatively cheap a lot of use cases for a bloom filter aren't strictly necessary anymore but don't be sloppy and then lastly you need to be able to tolerate that false positive rate if you can't
[08:29] where it might be in the set you're probably better off using a different approach our next data structure is Count B sketch it's basically Bloom filters with integers instead of bits the idea behind cman sketch is we
[08:44] basically allow ourselves to count up the number of instances or the number of times we've seen a specific item it allows us to increment an item and then also to query the upper bound kind of like a bloom filter can't tell us for
[08:59] sure whether an item has come through cman sketch can't tell us the exact number of times it's seen an item it could only tell us the upper bound but in a lot of cases this can actually be pretty useful before we get into that
[09:14] then we'll dive into some use cases so the way that cman sketch works is very similar to the bloom filter we're going to have K hashes and then for each of
[09:26] those hashes we're going to have a certain modulo or width this is basically how many integers we choose to incorporate into our data structure this data structure is actually called the
[09:38] scet so the array of integers that we're using to store the counts and then the using to store the counts and then the count Min comes from how we query it to our sketch and then we'll talk a little bit about how we query it so
[09:55] let's pretend just like before that Albert has added one item to our sketch so we're going to go to our hash one at index 3 and we're going to increment that and we're going to look at hash two at index one we're going to increment
[10:09] that now let's go ahead and add Brian so Brian is at hh1 index 2 # 2 index0 and let's add two for Christina so Christina # 1 index 3 and then # 2 index 2 so this
[10:25] is my resulting sketch after adding Albert once Bri ran once and Christina Albert once Bri ran once and Christina twice how do we query this well we query it much the same way that we do a bloom filter except what we're going to do is
[10:39] we're going to take the minimum value that we find at any of these hash indexes so for example if I wanted to find out how often Zed has been added to the sketch I'll look in hash one at index one which is a zero and hash two
[10:55] at index two which is a two so I have zero and two and I'm going to take the minimum of those values so in this case the upper bound on the number of times Zed has been added to this sketch is zero which is actually the number of
[11:09] times he was added similarly with Christina we're going to look at item Christina we're going to look at item three in hash one which is three and three in hash one which is three and index two in hash two which is two three
[11:21] and two we're going to take the minimum the minimum here is actually two that means that Christina has been added at most twice into the sketch now there are going to be instances where we might have collisions that basically
[11:34] accumulate and so it's possible that this number was actually higher than the number of times we actually added Christina to the sketch but it will never be lower because we are always incrementing the values and just like
[11:48] the bloom filter we can choose the width and number of hashes to basically choose a Precision for our count Min sketch or a variance on the S estimate of the
[12:00] number of times an item has been added a typical pattern for using cman sketch in production is a need to keep track of the top or the highest count items in a
[12:13] particular set sometimes this is referred to as a Heavy Hitters problem referred to as a Heavy Hitters problem and the idea here is every time we get an event an instance of something we're going to write into the cman sketch and
[12:26] then retrieve the resulting estimate for the count we'll then update a priority queue with a list of those items so in most cases if this isn't the most viewed
[12:38] or most accessed item that priority queue will be unchanged If instead we are writing an item that actually is in that set then we are going to update our priority queue and what this allows us to do is query at any time for an
[12:54] to do is query at any time for an estimate of those top items but doing so in a way that is very space efficient this Q length can be bounded by the number of things that we might want to retrieve and the cman sketch has a
[13:07] constant memory usage it just degrades in accuracy the more we go and so this can be used in a number of different situations we might use it in a security context to keep track of ips that are producing unusual traffic we don't want
[13:20] to have to maintain counters for every IP given there's only going to be a small number of ips that are actually going to be producing those problems we that are happening on social media where again the tail is long and the counts at
[13:34] the high end are at the head are very high another place that we might use this is in database query optimization where we want to figure out what are the where we want to figure out what are the most common values or maybe whether a
[13:48] selection criteria in a query hits something that we expect to be in many rows or few rows and finally you'll see this a lot in fraud and anti-scrape thing where we're trying to protect against those instances where the system
[14:03] is being abused and what we're going to be looking for are anomalies and instances where basically the statistics are out of whack with what we might expect from a typical user or a fraudulent user cman sketch can seem
[14:19] going to find less uses for it than you might imagine because of the constraints obviously we need a situation where we're counting items and querying those counts but we also have three harder to satisfy constraints first we need to be
[14:33] querying against a set of known items cman sketch doesn't know which items have been added so they need to be tracked separately in the heavy hitter priority cue in many cases if we need to track them separately or exhaustively
[14:46] we've eliminated the memory benefit of the sketch so we need to be careful here dealing with heavy space constraints you see this in two places in interviews either a your interviewer has invented an imaginary problem like the one
[15:00] recently asked at meta to build a web crawler out of raspberry pies or B you need a constant space data structure for predictable performance which is common in real-time systems databases and operating systems both will jump out at
[15:15] situation where you can deal with the approximation you'll see two patterns here a for performance optimizations like our previous caching example where if we're wrong we just lose some performance we're not delivering an
[15:29] incorrect ex an answer to our users and B in domains where we're already outside B in domains where we're already outside of binary correctness fraud and security or machine learning and AI applications often deal with risks and probabilities
[15:44] and are in constant trade-offs cman sketch can apply beautifully here all told cman sketch is a useful tool for your toolkit but be careful about applying it unnecessarily this is easily a situation where your interviewer can
[15:59] the final data structure that we're going to talk about today is hyper log log I love how all these names are are so fancy and Hyper log log is used for cardinality estimation or basically estimating the number of unique items
[16:16] places for instance websites are constantly concerned with the number of constantly concerned with the number of unique users this is the heart of daily number of page views I want to know how many people are active on my site that
[16:31] is in some sense a cardinality problem and Hyper log log provides an estimation much like cman sketch and Bloom filters provide estimations on their underlying
[16:43] the intuition behind hyper log log comes from the Rarity of sequences if I'm flipping a coin I can either get heads or tails with equal probability 50% if
[16:56] I'm flipping two coins I've got four options I can get heads heads Heads Tails Tails heads Tails Tails each of those are 25% likely if you walked past me and I told you I had gotten Tales tales three times a good guess for you
[17:11] tales three times a good guess for you is that I had flipped those two coins 12 times now if we were keeping track of this very rare sequence of I don't know how many coins and I had gotten this many heads if I walked by or if you
[17:25] walked by and I had told you that I had gotten this sequence you might guess that I had either been there for a very long time flipping many many coins or that I was cheating that former interpretation is kind of at the
[17:39] heart of hyper log log what we notice is that the more times we're flipping the more elements we're adding the more likely it is that I start to see these rarer sequences let's pretend I want to count the number of unique visitors to
[17:52] my site I might have an impression stream and kind of a listing of all the times that users have visited and what I want to do is find the number of unique visitors not the total number of views and so a naive way that I might do this
[18:06] is every time a visit comes in I will add that user to a hash set and then at the end of the day I can go and look at the size of that hashset to know the exact number of unique visitors this works great and it gives me a precise
[18:20] number but it has two problems one is I have to store each of my users in that hashset it's basically a pretty large represent a and secondly it grows unbounded as if I have a higher number of users a higher estimate that means
[18:36] the memory of this is going to continue to grow so how can we estimate and do this in a much more efficient way this is where hyper log log comes in so with Impressions we're going to take that username and we're going to Hash it and
[18:52] what we're going to try to do is keep track of the maximum number of trailing zeros in those hashes so when Albert comes in we see that we have one trailing zero when Dan comes through he has zero so we don't change our number
[19:08] Brian similarly Fred has three so we'll increment this to three Christina has two that doesn't change our maximum Brian we see Fred again and he has three which is quite convenient because Fred visiting many many times shouldn't
[19:24] change our estimate of number of unique users so what can we say if we observe a users so what can we say if we observe a maximum of three trailing zeros well we can come back to probability on this but this basically gives us an estimate we
[19:37] can basically assume that there was eight unique users that were coming through that's not a particularly accurate estimate if you recall back we had five actual unique users visiting the site but it is an estimate and it's
[19:51] the essence of how hyper log log works if we kept going through this process and saw a user which had 15 zeros our estimate gets quite large we don't expect that to happen very often but it
[20:05] also demonstrates a flaw here if somebody just happens to have 15 zeros in their hash we don't want to blow up our estimate just because that person happened to come through so how can we solve that problem the answer to this
[20:18] problem is we're going to do it multiple times with Hyper log log we're going to maintain multiple registers which are basically those counters or maximums of the number of trailing zeros let's walk through this in practice and I'll show
[20:32] you what this looks like so when you write or add an item to your hyper log log you're first going to Hash it and we're going to split that hash into two parts the first is going to determine the bucket or basically the partition of
[20:46] the hyper log log and then the latter part will be used to calculate those number of trailing zeros that bucket effectively indexes a register so if we partition all of our ID space we're going to maintain separate counters for
[21:02] all of the IDS in that bucket and so in this particular instance we are in bucket number one and at bucket number one we want to update our register so that so that it reflects our Max trailing zeros of one now if you think
[21:18] about this partitioning if we were to randomly do that we would expect all of these registers to be approximately equal and if you can imagine the free Gap accident where I had 15 trailing zeros in my hash that's only going to
[21:34] appear in one of the registers and it's not going to appear in the rest so what does this look like when we read well when we read instead of just grabbing that one register and doing some math on it we're going to take the harmonic mean
[21:47] of all of the registers apply some corrections on top and return that to the user and this has two benefits one that freak accident hash isn't going to in part because it still needs to average with all the other registers
[22:02] which are going to be lower there's not going to be multiple freak accidents here the second thing is that this averaging process allows us to smoothly interpolate so whereas previously we can estimate powers of two now we can
[22:17] estimate any value because we have this averaging that's going on so where does hyper log logs show up in system design interviews you're going to see this centered a lot around analytics work workloads where I need to determine the
[22:30] number of unique users to the number of unique posts that I saw but you'll also see this in a few other places in database systems I can use hyper log log to estimate the cardinality of a column it turns out that I may want to treat my
[22:44] execution differently if there's only two unique elements versus if there's millions of unique elements another place that I might see this is in Cache analysis where I want to understand from all of the incoming queries how many are
[22:58] there how many keys do I need in order to cach this effectively the key things to keep in mind is hyper log log is used in this places where we're counting the number of unique items in a large data set if your data set is small use a
[23:12] hashset there's no point in bringing in hyperlock log you need to have limited about hyper log log is it's bounded you choose it in advance but it also means that you know generally speaking if you've got more memory you can probably
[23:26] use it successfully and then the last thing like all of our other prior data structures we need to be able to tolerate some small estimation errors if we're not okay with errors we have to go with a more exact solution all right
[23:38] let's wrap things up so we covered a lot of ground today we talked about Bloom filters cman sketch and Hyper log log Bloom filters allow me to test for set membership in an approximate way that scales really well and save space count
[23:52] Min sketch allows me to count elements in a way that similarly saves space and Hyper log log allows me to estimate the number of unique items in a stream of data or a large data set all of these are going to apply in situations where
[24:07] are going to apply in situations where either a I have limited memory or B I things that you should be on the lookout for that might imply that you're going to use these are places where either a Your Design can tolerate a bit of error
[24:22] or approximation or B you have a ton of mentioned mentioned earlier about having to run on Raspberry pies or embedded systems is kind of a nod that maybe these things will apply now be careful
[24:38] it doesn't make sense to go and bring Bloom filters or cman sketch in cases where the data is small and it would actually be easier both from a development perspective and then also from a debugging perspective to just use
[24:51] a a proper precise data structure that's going to give you an exact answer there's no need to bring in approxim unnecessarily but in those cases where you do have some flexibility and it's good to ask your interviewer whether you
[25:06] have it these provide you a way to solve problems that are otherwise intractable if you run an estimate and you need a hash table and it turns out that the size of that hash table is intractable maybe it's terabytes of data for some
[25:20] small part of your system maybe you need a bloom filter or count in sketch in that particular instance I hope that this was useful as always leave comments if you've got questions or suggestions or hey Stefan that wasn't very clear
[25:35] I've also included in the links a reference to a written version of this which goes into greater detail for our premium users of hello interview uh anything was unclear really enjoyed this and until next time talk to you then