How databases store and transmit integers efficiently using varint encoding

System Design for SDE-2 and above: arpitbhayani.me/masterclass
System Design for Beginners: arpitbhayani.me/sys-design
Redis Internals: arpitbhayani.me/redis
Build Your Own Redis / DNS / BitTorrent / SQLite - with CodeCrafters.
Sign up and get 40% off - app.codecrafters.io/join?via=...
In this video, I discussed the inefficiency of using standard 32-bit or 64-bit integers to store smaller values frequently. I explained the concept of variable-length integer encoding used by databases like Redis to efficiently store and transmit integers. By converting integers into arrays of bytes and packing them efficiently, we can save space and bandwidth. I detailed the implementation of variable-length integers using a continuation bit-based approach, highlighting the trade-offs of storage efficiency versus CPU processing. Check out the source code and consider implementing this efficient encoding method in your projects. Thank you for watching!
Recommended videos and playlists
If you liked this video, you will find the following videos and playlists helpful
System Design: • PostgreSQL connection ...
Designing Microservices: • Advantages of adopting...
Database Engineering: • How nested loop, hash,...
Concurrency In-depth: • How to write efficient...
Research paper dissections: • The Google File System...
Outage Dissections: • Dissecting GitHub Outa...
Hash Table Internals: • Internal Structure of ...
Bittorrent Internals: • Introduction to BitTor...
Things you will find amusing
Knowledge Base: arpitbhayani.me/knowledge-base
Bookshelf: arpitbhayani.me/bookshelf
Papershelf: arpitbhayani.me/papershelf
Other socials
I keep writing and sharing my practical experience and learnings every day, so if you resonate then follow along. I keep it no fluff.
LinkedIn: / arpitbhayani
Twitter: / arpit_bhayani
Weekly Newsletter: arpit.substack.com
Thank you for watching and supporting! it means a ton.
I am on a mission to bring out the best engineering stories from around the world and make you all fall in
love with engineering. If you resonate with this then follow along, I always keep it no-fluff.

[@tiyabansal9568]

Definitely an underrated one! This was a great learning. Thanks so much, Arpit for explaining + implementing it in a very thorough yet highly understandable way. Great watch!

[@AsliEngineering]

Thanks Tiya!

[@harshildoshi3299]

This was a great learning. One question I have is that, who actually does this Encoding/Decoding? Is it performed by Query optimizer?

[@adityakumarsingh648]

Hi Arpit, The explanation was quite thorough, got to understand a new thing that dbs transmit varint data using byte array. BTW, which VS Code theme extension you use?

[@backendengineering007]

(Thinking out loud)If we know that an int is max of some bytes like 8 bytes in this video case. Don’t check for the continuation bit in the last byte by that in case where all bits are 1s we can suffice in 9 bytes as opposed to one extra byte for the overflowing 1bit in the last?? Am I missing something here?

[@aanurraj]

Thanks for the video Arpit, now I am having a strong urge to implement it :P

[@AsliEngineering]

Go for it. It is worth the time. Plus I have linked the repo for reference.

[@KaushalKumar087]

Which app do you use write all the text?

[@AsliEngineering]

GoodNotes

[@vivekdhir77]

Could you please explain why did you take an array of 11?

[@AsliEngineering]

Because that's the max number of bytes we can have for an 8 byte long integer when encoded as varint.

[@KunalKumar-kc1bw]

64 bits number = ( 7 bits of number + 1 continuation bits) x 9 + ( (1+6) bits of number + 1 continuation bits ) = 80 bits or 10 bytes Is it correct?

[@jasvinjames5773]

​@@KunalKumar-kc1bwthanks for the explanation Kunal

[@uzairshaikh6733]

So does it mean, varint is not space efficient if an integer completely occupies the required space? i.e. for a 64/32 bit integer if all bits are used then varint will require 10 bytes/5 bytes, were as if varint encoding was not used space required will be 8/4 bytes

[@AsliEngineering]

@@uzairshaikh6733 for large values it is not. But how often do you use large integers?

[@da5m0n]

Database folks taking internal fragmentation quite seriously