Github Link to my code -> RDB File Parser

Please be informed this is my understanding of the topics that I discuss, which may not all be accurate to last detail.

What is a Redis Snapshot, how is that data stored ?

• So, you can take backups of a Redis database. And Redis stores this data in a particular format. Take a look at this link and we can walk through a few topics that are mentioned in it.

Redis creates something that is called Append Only File(AOF) format, which stores all the data along with useful metadata in a binary format.

This articles focuses solely on the topic: if given a Redis RDB file how do you go about parsing this file so that you can retrieve the keys and values stored in it.

Redis has a lot of other features, we are not going to discuss any of that.

What does a parser mean, how do you go about parsing binary data ?

Parser: This is a program or a library or a piece of code that you use to read a particular text or binary file from beginning to end, in order to extract useful information out of that file.

In order to perform these operations you have to know how exactly that data is stored, if it has some static markers, which we can use to distinguish one piece of information from another, like how do you know which series bytes(or alphabets) are a key and which are its corresponding value bytes(or alphabets) in the .rdb snapshot file.

As you might have inferred from the discussion above, the .rdb file stored in binary format and the format is very well documented and known and Redis has a full implementation of parsing this file on thier official Github repository. You are welcome to read the code.

But we will try to understand by ourselves, because we are madmen and I like to reinvent the wheel, because we have a lot of time to kill on weekends. Now that our intentions are clear, please read on.

Parsing the binary data essentially involves knowing exactly what each and every byte means, knowing the layout the file format, knowing if we have used little endian or big endian to represent a certian number. For example : lets say, an intergers is represented using 4 bytes in C, but does .rdb file really use 4 bytes to represent every integer value in the snapshot file, the answer is NO. Creators of the file format are really smart, if a number can be represented comfortably in 1 byte then why write 3 more bytes to the snapshot file and waste storage space. Things like these have been taken care of in this format and we should take such nuances into account before reading any piece of data.

How does winnow work ?

Since I have written this parser in Rust, I will talk about an awesome tool winnow. Winnow is a library that is characterized as a parser-combinator. What does that mean ? In simple terms it lets you do a operations like reading 4 bytes from a file by letting you use a function.

In a difficult life (arguably a fun life), you would reject a tool like winnow and write your own function to read bytes or keeping track of what you did till now while you were parsing the file. But I was not so brave and I settled for winnow.

How does winnow work, you ask ?

• lets create a mental model of parsing anything. I hope we agree on the fact that parsing a file is linear process meaning you parse some part of the file then you move forward and never move backward, like the way you play music, once a paragraph of the song is over you sing the next paragraph not anything that came before it. Its like reading a story, you just move forward, you just move in one direction that is forwards. I hope it sets the stage for you, now look at the picture.

If you have taken a subject name Theory of Computation in undergrad, you will immediately link it to a finite state machine, where it reads an input tape and then the reader reads over the tape. Well you are right, that is what a parser is.

The red part is the reader or the parser, which is sequentially reading the file/tape from left to right or top to bottom, however you want to think about it.

I will do code walkthrough in another blog post, perhaps a part 2. Lets see when I do it.

• Thank you for reading my shennanigans