‫Filters are one of those concepts that always confused me for the longest time in computer science.
‫I'm going to take a few minutes to actually explain it to you guys and not what are they, but why do
‫they exist.
‫So I'm going to flip that question a little bit, if you're interested.
‫Stay tuned.
‫So here is our problem.
‫Forget about balloon.
‫Here's a problem today that we know how to solve, but we can do a better.
‫I'm going to ride a service, a Web service, express, no gas ride that essentially check if my username
‫exists or not.
‫And if you think about it a little bit, this this this capability, this feature is very simple to
‫build.
‫Right.
‫Build a database with all the user names as you start writing user names.
‫If you want to build this interface, you make a good request.
‫Does Paul exist?
‫You make a request to the server, express Jango, anything, and then you execute a query against your
‫database, selects user name from the stable.
‫Hopefully you have an index there.
‫And if the of the record comes back, that means that username exists.
‫If not, then it doesn't exist.
‫Right.
‫Probably this is very slow.
‫Right.
‫And this feature is going to be very popular.
‫Ride all these users going to this web page and timing.
‫Hey, does test one, two or three exist, does whatever.
‫Everybody wants a fancy nickname.
‫Right.
‫So here's the problem.
‫Right.
‫This is very slow.
‫So what do we do?
‫Well, I heard about this Redus thing, right?
‫That is actually in memory database.
‫So let's take it from disk and put it in right as well.
‫That's fine.
‫Or you're going to do the same thing, execute the same giedd request.
‫But this time I'm going to have the database.
‫Right.
‫And if it's not there, OK, I might sometimes need to go to the actual database because these two can
‫get out of sync.
‫So you created some inefficiency and you actually doubled your memory footprint because you're storing
‫data here and storing data here just to solve this simple problem.
‫OK, so you we know how to solve this thing, but some smart people, computer science professors came
‫up with a solution, very efficient solution, and they called it Bloem Filters.
‫So let's explain what these things are.
‫OK, so.
‫With Bloom Fulcher.
‫We're going to use some in-memory representation.
‫Usually it's very tiny.
‫I'm using 64 bit in this case, OK?
‫And this 64 bit magically have some numbers, right?
‫And this gets the bit zeros not set to zero.
‫This is one this is zero zero zero zero.
‫And this is one.
‫Right.
‫So how does it come up?
‫Will come to that.
‫But here's the thing.
‫If we're going to make a request, hey, does you does Paula exist?
‫We will make a request to the server and the server will write a function.
‫We will hash the string Paul and Maudet 64.
‫And if you know mod, what will happen is this result will only come back with the result from zero
‫to 63.
‫Right.
‫And just like that out of the box.
‫You're going to get collision all the time, but that's fine.
‫So in this case, Paul is bet number three, right.
‫And we if we go ahead and check in my integer in my 64 bit integer, this is the filter that we build.
‫Does this bit exist?
‫Is it set?
‫No.
‫If it's not set, then you can absolutely 100 percent guarantee say that Paul does not exist in the
‫database because it's not set here.
‫And we're going to show how that that happened.
‫OK, so Paul doesn't exist, so I didn't have to even query the database.
‫Let's take another example right where I'm going to check if Jack exists.
‫I'm going to make a get request to the server and I'm going to mod that string.
‫Jack, I wish first of all, we're going to hash the string, Jack, get a bunch of big number, right.
‫And then Mod 64, I'm going to get a value from zero and 63.
‫It happened to be 63.
‫I think that bit a 60.
‫Oh, a said.
‫And if it's said here's the thing.
‫If it's if that bit said that means Jack.
‫Maybe they're.
‫And why maybe maybe because there might be another strike that matched hash and Mod 64 that resulted
‫in 63 and was not necessary Jack himself.
‫Right, but some other strength that matched it.
‫But that is actually enough for us.
‫If it's set, then, well, it said I'm going to take the hit and hit the database.
‫So I kind of saved myself some queries that there is this perfect.
‫No, but it's a very efficient thing to actually query.
‫Right, to prevent unnecessary querying.
‫By the way, Cassandra uses this in their implementation of that consistent caching all the time.
‫Right.
‫There is stables and all that stuff.
‫They use this internally.
‫Right.
‫Because anything any time you want to avoid an expensive query to check if something exists or not or
‫if you want to do this query, but you're not sure if you're going to get a result or not.
‫Blue filters are very useful.
‫Yes, there are some of disadvantages to this.
‫But let's look at actually how to create a Blum filter.
‫I have a brand spanking new bit set here, 64 bit.
‫Right.
‫And I'm going to create user Jack for the first time.
‫It's a it's a blank database, right?
‫There is nothing.
‫And I'm going to create Jack.
‫So if I'm going to create Jack, I am going obviously to make a post request the server to the express
‫server and I'm going to hash Jack more.
‫Sixty four.
‫I am going to get 63 in this case.
‫And what do you do before writing to the database, the user name Jack, as you sit this bit niceties,
‫isn't it?
‫And then you obviously right at the levels.
‫So this is how we start building this in-memory representation of blah filter.
‫Right.
‫And then let's try Paul.
‫Hey, I'm going to create a user.
‫Paul Proof Post Paul Ryan Mod 64.
‫What do we get?
‫All three.
‫Let's start with number three.
‫All right.
‫So far, so far, so good.
‫Let's try.
‫And obviously we related to the database.
‫Let's try some other user.
‫Tim.
‫Well, I'm going to take Tim and hash it more.
‫64, guess what?
‫I got number 63 again.
‫And that's absolutely perfect.
‫That's OK.
‫Because you're going to get you only have 63, 64 bits, obviously all the strings and names in the
‫war.
‫You will fill between these things.
‫Right.
‫And obviously, when you say 63, it's already said so.
‫You don't have to even bother yourself setting it because it's already said, but you always have to
‫had the database and write it.
‫Right.
‫So that's how it's actually made.
‫Let's take another user, Ali.
‫All right.
‫So Ali, hash Ali and get six more.
‫Sixty four.
‫You're going to have big before in this case and you're going to set that bit.
‫All right.
‫And then obviously right there.
‫That is all right, guys.
‫So that's essentially Bloomfield's are in a nutshell.
‫I know the actual implementation of Bloom filters are a little bit fancier.
‫They use like three locations and all that stuff.
‫Right.
‫Sometimes they have they have more bits.
‫Right.
‫They use three hash functions just to make the odds harder to get right.
‫But and that's that's just to me, that's just an implementation.
‫But if you if you understand how it works, that's how it works and that's why it exists.
‫Right.
‫So some limitation of Blum filter.
‫You can get into a case where all of these puppies become one one one one one, one one.
‫And in this case, you will your blue filter is essentially useless.
‫You you became the first case where you're always going to head the database.
‫It's not really harmful.
‫It's not going to there is not going to slow you down, but it's not going to give you any benefits
‫per say.
‫Right.
‫So are you going to have to think about this?
‫Like the bigger you make this thing right, then you kind of interfere with your memory footprint.
‫But I mean, it depends how big it is, right?
‫Really.
‫But the shorter it is, then you're going to get all these false positive cases.
‫Where you going to always hit the database regardless.
‫I'm all right, guys.
‫That's it for me today.
‫I hope you enjoyed this video.
‫I'm going to see in the next one.
‫You guys.
‫They are.