About this talk
In this talk, Nikolay Mihaylov introduces his development of the HM HM4, an in-memory database designed for high performance and efficiency. He discusses the evolution of databases, from early record-keeping methods to relational databases, and highlights the trade-offs between speed and convenience in modern software. The speaker provides insights into the architectural design of HM HM4, explaining how it uses sorted data structures like AVL trees and skip lists for efficient data retrieval. He demonstrates the capabilities of his database by showcasing various features, including vector search and unique count algorithms, while also drawing comparisons to established systems like Redis. Throughout the presentation, Mihaylov addresses the challenges faced by traditional databases and illustrates how his solution overcomes these limitations.
Full transcript
Today we will start the day with Nikolay Mihaylov, who will present his personal development of the HM HM4 in memory database. Please, applause. Oh, hello, I said Nikolay. Ah, I've been programming since 1985, to put it bluntly, on Pravets 82. Otherwise, since around 2000, December 1999, I've been programming professionally, and here we can see that on a tablet or tablet from Mesopotamia, some financial transaction is recorded,
and then around 1800, someone decided that they needed to enter all such financial data into some kind of table. This is an invoice from 1800 and something from there and then someone decided that databases should be relational. And the author of Postgres said that when and that what Postgres needs to learn from SQL is that users should be allowed, if it's okay with them, to trade some
things in the database, that is, speed for something else or convenience for something else and so on. And this is Golden X. I don't know if you've played it. There are three characters in it, and the difference is that when you play with the dwarf, for example, the dwarf's attack is very strong, but the magic is very weak, and vice versa, if you are with the woman,
the attack is weak, but the magic is strong, and it is strong. And depending on how you play, you can choose to play with. Now the other interesting thing is what Jim Gray said. Memory is the new disk and disk is the new tape. That is, he said it, when tape was used, it is not used now, but still, as for memory, if its speed is one,
and the price is €20. And the SSD's speed is slower, but its price is lower, and the spinning hard drive's speed is quite slow, but its price is quite low. So these are the trades in modern software, so to speak. Oh, right. We 'll skip that. And now I'm going to show you a demo. As long as I have the internet, because that's the only thing I
didn't open. So here we are writing some kind of server. Let's write it for example, so it's not cloud FL. And here we see all the domains that have name servers that are on this top domain. That is, YouTube is with NS1, Google Chrome, NS2, and so on. I purposely didn't show you this thing on Cloud Flare, and here there are 13,000 domains, but if we go
to here we will see that there are 26,000. That is, this is the DNS in the whole world with the most domains hosted on it. That is, this is a domain. And if we take this moment for example this is already the only DNS that is on CloudFR, and this particular one has 63 thousand. We don't know what it's working on behind the scenes at the moment
, but you'll see in a moment. The other demo I'm going to show you is a Bulgarian site flagman.bg, which has various news on it, and what we use for it is a statistics system that a guy was supposed to redesign, but never did. And here we can see all the statistics for today so far. And here we can see how many visits we have in total,
how many are unique. Here we can see the IPs that are most visited. So this IP is probably some kind of hacker's IP, or maybe it's some kind of IP that's pumping up the site. And here we see from other search engines, that is, we can see here from BH. this also works so well that it doesn't slow down the website itself and this system is almost
open source. I wrote it, but if it's not made open source, that is, if someone is interested, I can give it to them. And all of this runs on a database that I wrote, which I'm going to show you now. Oh, here are some statistics. So this DNS has about 900 million records. It has 100 GB on the disk and is currently on an SSD, but it
was originally on the hard drive and so we upgraded and that's why it's on an SSD, but otherwise it achieves more or less the same speed with the hard drive. And now a little history. When we were making this site Complete DNS, meaning there and the data, to put it into MySQL initially took us a day. And I had a computer in the middle of my bedroom
and it worked, that is, two computers and one fed into the other and this thing was over in 20 days. In this database, which I'll show in a moment, this same data is loaded in 20 hours. And to be honest, 2020, because we had a crash, we had to reinstall MySQL - and that happened in about 30 hours, only then it was on a more powerful server.
showed you that. I assume you know about relational databases. They are not very easy to learn, but we learn them in school and we all know them and think that it is very easy to write select count asterisk from users where city equals equal to five. But this is actually very difficult to learn. If we didn't teach them in school, this would be terribly difficult. I don't
know if you agree with me or not, but let's assume that you do and the data has to fit into some model that you have come up with in advance. On the other hand, the most basic database has two commands: set, get, and del. And that's super easy to explain. It works super fast. However, when you start doing it, it turns out to be the same as
if you were writing in assembler or in SI, which means it's not that convenient for work what's the problem with all databases right now, regardless of whether they're value or relational, is when you have some data collected in a bucket and you want to, for example, count how much data is in that bucket. Ah, that is, what I gave here with users to 5. That is, this
means that the database, if it does not have an index, must go through all the data and through each data, if it is five, to collect it. And now the pointer is gone, but it can be seen from what is written that it is one. In this case, the data is scattered throughout the file itself and generally all of it must be read. In what is written
three, it is the same there, only the data is collected in one place and then the passage is known from where to where. You just have to read them. What is two, that is, the third in this case, is what myl does in most cases and that is that it has an index and instead of reading from the file itself it reads from the index and then
the transfer is quite fast. And the four is what supports Oracle or Sequal server, Microsoft sequ server. Then there is something like a sorted copy, but then the update is in both places and then when we run this QR, it is searched in this sorted copy, which Oracle calls index strength, I don't know what it calls it. Oh, so here are some examples, you obviously know them.
And why do we need another database? It was launched as a test project. But then different people started using it and I continued to do it. So what do we have? We have a sorted one, you could think of it as a sort of sorted array. That is, all the data we enter is sorted. They enter this array. When it is full, they are written to the
disk and when searching, both the disk and the memory are searched. And the interface is redis. Any language that supports reds can be hooked. Oh, there is an expiration. And this thing is similar to Cassandra, if you know how it worked a lot back in the day when the data was sorted, which they then abandoned. And in this model, when you update in memory, and write to
disk only when the memory is full, all writes to the database take up a single bit, and all reads from the database are zero and there's an asterisk, because actually this is from, how should we put it, from a higher level, it looks like this. In reality, to write them to memory, we obviously do some operations, and to read them from disk, there are also quite a
few operations, but in general, this can be said. The deletion is with a tombstones. That's it. And instead of erasing the record that's on the disk, we write a record that says that it's no longer there, that is, empty. And all the data on the disk is read only, which means you can grab it and copy it at any time That means backups are very easy. It's
not like MySQL, for example. Let's clean up the entire database now, because we want a backup and something might have changed. . We'll skip this because I've prepared a demo for you. And before, by the way, before it was called HM4, I had written it in C and it was HM2, which means Hmmap 2. And here, if you've seen Metropolis, this is a movie from 27, it
turns out that they use my base there. That is, this is not AI, it is not generated. That's from the movie itself. Apparently in '27 they had computers and they had the means to compile it. And what does it support? We only support 64 bits. It works on MacOS, including Max Silicon. I haven't compiled Freebsd recently, it should work. I haven't compiled it on ARM either ,
but it should work. And what do we have as specifications? The key could be 1b. Same as in MySQL. The maximum is 256 MB. It's less than the number 512, but I don't know of anyone who has put 512. Expiration is 136 years in the future. And a Time Stamp is used, that is, in 2040 there will be a problem in 2040. And for the list that
is in memory, an AVL tree or Skiplist is used But AVL turned out to be much faster. I'll show you in a moment. So the skiplist can be compiled with it, but I have n't done it in a long time. how does the whole thing work? And when there is a new record, that is, a new key, it is written to the list. If the memlist is
full, and this thing is in one line, it is written to disk in the background. When reading, it first from memory, then from the data on disk. This whole thing is being moved around and the newest thing is being given. And here, since I say that the memory is full, when is the memory full? Well, when there is a certain memory, if it goes over it, it
is written to the disk. And do you know the skiplist well? If you don't know it, this will be useful for you. Skipst was invented in 1989 and works very well. Ah, it's about 10% slower than a binary tree. And the really cool thing is that it can be written correctly, nicely, qualitatively, and very easily, without copying from anyone's code. and it runs, again, about 10% slower
than a binary tree, which runs mega fast. is the 62nd in the Soviet Union. And with it, you can search very quickly, insert very quickly , but delete very slowly, but our database doesn't hide anything and that's great and that's why we use it. But the big problem is that in my opinion, this thing cannot be written correctly and qualitatively from scratch. That is, you should always
take, if you start writing it, you should take it from the person who wrote it and copy their code and then do some optimizations or some things that you want, because there are many such subtle moments, there are some codes that are symmetrical. When you go watch it, if you go watch it, you'll see what it's all about . you mix up a plus with a minus
and it no longer works. On the other hand, in the other branch, the minus is a plus and so on. Now the question is that in the 90s and 2000s, mainly from Microsoft, there were various optimizations, and Microsoft even made something called Week AVL3, which is even And the most surprising thing is that on new hardware, which is for example after the year 2000, the EVO tree
works faster than the red-black tree, and do you know what it is or don't you? Okay. Okay. So it works better than this wood that is used everywhere. That is, all software, commercial or not, uses another algorithm that works worse than this one. Why do they use it? Because in the 90s this algorithm worked slower. Okay, we'll skip that. And we skip that. we're skipping that too.
Ah, readys, have you worked? So this database of mine is almost a drop-name of redis, meaning 90% of the commands are the same, but not 100%. Redis is in memory and is limited to how much memory you have given it. Mine is on disk and is limited by how big your disk is. And since you haven't worked, I'll show you various commands in the demo in a
moment. We'll skip that. I will only say that I have gelhshing. This thing is, if you have a database of some places that are located, for example restaurants in Sofia, and you say: "I am located at these coordinates, you can find the closest one." And the other thing that's interesting here is hyperclick. This is one thing that can count unique things in about 10 20 bytes .
For example, what I showed you about analyzing traffic, unique visits, and the rest are just IPs, and you assume that for the entire day, one IP is a unique visit, and you put a lot of IPs inside. Let's just bring it back here to show. So today there are 178,000 IPs, or rather, not, I apologize, 36,900. This thing, instead of storing all the typos, is kept in
20 bytes. It works very well. Of course, the more there are, the greater the error, but here the error is no more than 10%. a, that is, here each one of those that you see, a is held in about 20 bytes, that is, the part that is for the unique ones. Take a look at this algorithm. It's even relatively easy to write, but you have to write
in some language like Python or CC+. For example, it would be more complicated to write in PHP Oh, another thing I have written is, oh, so heavy hitters is also a miss. These are algorithms that you put in some data and it counts the data that is the most. So this is where we come back to. those IPs common, that is, here's the one that we didn't
block on purpose, but in principle deserves to be blocked, and this one was found this way. So in this Heavy Hitters structure, you add this IP many times and it ends up at the top. The same thing is done here using a different algorithm, here using a third one, here using a fourth one. The numbers, as you can see, differ. The first one is actually correct. The
first one we do with a real count, so that you can see how they differ more or less, but in reality in all cases this one comes out on top and this second one comes out on top and even the third one, as I look, it came out too. It cannot be guaranteed any further down. And the good thing is that when you create this structure, it's
in, that is, in our case, the good thing is that the structure is in the database and you actually just hook into the application and say add this one. So this is the same as if you did it with MySQL and selected max, except that it's not very good for performance, it's the same. That is, the data is not in the one that connects to the server.
on the server and anyone who joins can download them. Ah well, apparently we'll have to get over this now. And do you know what vector search is? Okay, you don't know. I didn't know either. This is one of the few things I researched with GPT chat. Oh, I mean, nowadays you can give him, for example, an article or a person's name or something and tell him to
make me a vector. And he gives you some fractional numbers, that is, fleet numbers, which are, for example, 300 or 600 numbers, and then you give him, for example, another thing or another picture, and he gives you other numbers. And now I haven't drawn the vectors, because if I do draw it, all such drawings are with two-dimensional vectors, but the vectors are, if there is, say, a
laptop drawn on both pictures or one is a photo, the other is drawn. If the AI has figured out that this is a laptop, the vectors themselves are close. So now I 'll show you this. If one vector is here, the other one is right here. But these vectors have about 500 elements and now it has become fashionable for all databases to do vector search. That is,
the things you take from AI, you put into the database. Then one element, calculate it again through this vector and look for the vector. How do you search? Because this is not an exact search, but you need to find something that is And there are two algorithms, actually three. One is to go through everything and search. The other one is a very nice one, very strong, which
only happens in memory, very fast and it says, now I'll tell you that I forgot something. Okay, I'll tell you in a moment. And if you have a normal ready, the latest version supports it very well, but you need to have memory there. For example, a friend uses vector for what, aa he has a search engine with some people and when he writes the name, for example
instead of Nikolay with a Y, he can write it with a at the end, and through vector his heart comes up with all Nikolay, Nikola, Nikolaos and so on. And that works very well. Ah, in my case, this search was done with Brot Force. Because when the data is on disk, there is no other way and it is a bit slow. I'll show you an example in
a moment. so the data on this server that I wrote may be read only, it may And I showed you what's wrong with DNS. It is read only. Every month at the beginning of the month we poll the base. How did we make the base? We made the database offline with one thing that builds it in about, say, an hour. Oh, right. This is a vector algorithm,
which we will skip. Oh, here's the thing about vectors that I said. And now let's do a this is actually the RedIS console. Here it is . We're slapping it and what we can do is, for example, we can take what this is in A, we can remember it, and now when we take it, it's five here. Oh, so instead of a five here you can write
down Jsn, you can some strings, you can write down whatever you want . And now another interesting thing, if you have radish, if you have some kind of site, for example this news site, on this site, for example, you count how many times an article has been viewed, and instead of writing something to MySQL and MySQL getting stuck or slow, you can do this command. And here
I deleted the a and here a means give me one, so a is now one. The other client like doing 2 3 four and this happens very quickly, including on redis and this gives you the final value. Otherwise you can always do a get. you can delete it, you can set an And for example, we say that after 2 seconds A should disappear. And here he disappeared.
But now we'll do it like this. Here it is. It's here. And now it will disappear in a moment. It's not gone yet, but it will. okay. It has to disappear. You saw from the beginning that it disappeared. Now maybe we have to wait longer. Oh, and that's very nice. You can use radish or my base to make a trot, I don't know if that's what it's
called. the people. That is, if someone constantly F5s you on the site, you can troll the IP for example with incr and then with OK, I don't know why it doesn't work. I'll see him later. It could be a bug, but I don't believe it. And you can throttle the person, that is, you do the inker, inker, but then you also do the expire. So, basically, I
might give you a lecture about radishes next year, because it's super useful. And the other thing I'm going to show you as a demo is that my database supports some commands like this. As strange as this may seem, this thing means give me all the keys that are called mushroom 150. And give me the default number of keys, which is 10, make sure all the prefixes are
back 150. This thing is not supported by distro and with ready, this command that does something similar does it super slowly, but with us, because the data is done, sorted, so to speak, this is a super fast command. And the other thing, which is, here's a vector command. Oh, here I have it. So what does this mean? This means Give me all of A GF 300. This
is a set of vectors that I've added and named in a bucket. and which I have named GF 300 and they say the vectors I have put in are 300 dimensional. And here we'll skip this and say: "Give me all those that are similar to this one. This thing is the vector itself that is encoded. And so that you don't write 300 numbers, anyway this is returned
to you by AI, it can sit like this. Nobody expects this to be done by hand. This is done with PHP, for example, I did it and it says give me 10 of these. And this is actually the vector that is responsible for frog, for the word frog. And it returns here various words that are close to frog. But here the last thing means now continue searching
from this key, which if you run it as a program and the result is this. That is, we are searching for the word frock. It comes up with this is how far one species is from the other vector and finds Frocks. Frog with a capital letter tot amphibian bullfrog. And of course, down here some nonsense starts. For example, it is closer than with a capital letter. can
search for absolutely everything, but I don't have vectors at hand, but maybe, if you want, we can test it. There is time. Ah, but in any case, you should have the vector. So from here I can show you something, if you want something else or any questions. Maybe I forgot to say that this thing is located here. Here is the repo. If someone decides to test it,
rather the repo is here. If someone decides to screen, please full screen. Well, it's still the same. It won't get much bigger. Well, I'm trying, but I can't figure it out. Ah, here it is if you decide to test it, I can help. Of course, I forgot to say, this is used in several places. So on this site with DNS it is used. It is used on
four or five sites. It is used as a replacement for Redis, because their database there became about 70 GB and they had to upgrade their servers or switch to this and it is used on seven or eight sites the part for which Also, if anyone is interested, they can call me and I will help them. The problem is that it can't be installed on some shared hosting,
for example , because you have to run your and the database requires a slightly more expensive server. That is, it won't work on some cheap VPS either. It has to be something more expensive, for example $10 per month. That's all. If you have any questions, you can do it now, maybe later or something, if you are interested in a question. And because I somehow missed the booklet,
what type of objects can this database work with? In the sense of only text or text metadata, photos, videos of the key. Yes, I will answer right away. You can put any string you want in the key, it can be a blob, it can contain zeros inside, that is, it is not limited to not having a zero. Only for some of the commands is it forbidden to
have a tilde inside. That is, the server will accept your tilde, but then it may not, and when you make requests after that, something may go wrong. It is only text objects, right? No, You can do anything you want. You can take a picture, make it into a banner and run it. Of course, you can't do it through the console, but you can do it through a
script and if you do it, as long as it's 256 MB it will work and the same problem will happen as if people keep their pictures That is, it might work a little better, in the end everything will be broken, but you can put everything in. Vectors are encoded. I 'll show you again. Here's a vector that's made in hex. Just like it's made in hex, it
can also be made in Bry. It 's just a hack so you can play it from here from the console. That is, this thing is some kind of binary object, in which there is no problem with zeros. Of course, how you will use these objects is up to you. And is there a limit to the size of the database itself the bigger your disk is, the bigger
it can be, let's say, a terabyte. Yes. How fast it will be depends, but there's no problem with not works. Any questions? You can ask me later. Okay, if there are no other questions, you can always contact Nikolay Mihaylov outside the hall. In that case, I ask for applause for the presentation. [applause] Thank you too.
