Running fast and slow: experiments with BPF programs performance

1. Introduction

My own personal white spot regarding BPF subsystem in Linux kernel was always programs performance and an overall introspection. Or to formulate it more specifically, I wasn’t sure if there is any difference in how we reason about an abstract program performance versus a BPF program? Could we use the same technics and approaches?

You may wonder why even bother when BPF programs are so small and fast? Generally speaking you would be right, but there are cases when BPF programs are not small any more and placed on the hot execution path, e.g. if we talk about a security system monitoring syscalls. In such situations even small overhead is drastically multiplied and accumulated, and it only makes sense to fully understand the system performance to avoid nasty surprises.

It seems many other people also would like to know more about this topic, thus want to share results of my investigation.

• Introduction
• Current state of things
• BPF Instruction Set
• Batching of map operations
• Bloom filter map
• Task local storage
• BPF program pack allocator
• BPF 2 BPF
• How to analyze BPF performance?
• Talking to the compiler
• Aggregated counters
• Manual instrumentation
• Top-down approach
• Profiling of BPF programs
• Modeling of BPF programs

PSquare: practical quantiles

0. Motivation

Recently I’ve started to notice an interesting pattern. When you take something you thought was simple and look deep inside with a magnifying glass, it usually opens the whole new world of fascinating discoveries. It could be one of the principles of the universe, or just me overreacting on simple things. In any case one of such examples I wanted to share in this blog post, I hope it will bring the same joy to the readers as it did to me. Let’s talk about quantiles!

How many engineers does it take to make subscripting work?

Are you tired of this syntax in PostgreSQL?

SELECT jsonb_column->'key' FROM table;
UPDATE table SET jsonb_column =
            jsonb_set(jsonb_column, '{"key"}', '"value"');

The select part is actually fine. But for updates, especially for complex updates, it could be pretty verbose and far from being ergonomic. What would you say to this syntax instead?

SELECT jsonb_column['key'] FROM table;
UPDATE table SET jsonb_column['key'] = '"value"';

Evolution of tree data structures for indexing: more exciting than it sounds

0. How to read me?

I have to admit, my research blog posts are getting longer and longer. From one side I find it genuinely encouraging, because if one gets so much information just by scratching the topic, imagine what’s hidden beneath the surface! One university professor once said “what could be interesting in databases?”, and it turns out freaking a lot! On the other side it certainly poses problems for potential readers. To overcome them I would suggest an interesting approach: print this blog post out, or open it on your tablet/e-reader, where you can make notes with a pencil or markers. Now while reading it try to spot ideas particularly exciting for you and mark them. Along the way there would be definitely some obscure parts or questions, write them on the sides as well. You can experiment with the diagrams, changing or extending them, or just drawing funny faces. But do not read everything at once, have no fear of putting it aside for a while, and read in chunks that are convenient for you. Some parts could be skipped as the text is build out of relatively independent topics. The table of contents can help and guide you. Having said that we’re ready to embark on the journey.

• Introduction
• RUM conjecture
• B-tree basics
• Beyond the hard leavers of basics
  • Key normalization
  • Prefix truncation
  • Dynamic prefix truncation
  • Suffix truncation
  • Indirection vector
  • SB-tree
• Why is it not enough?
  • Partitioned B-tree
  • Hybrid indexes
  • Bw-Tree
  • DPTree
• Trie
• Learned indexes
• Is that all?
• References

1. Introduction

Whenever we speak about indexes, especially in PostgreSQL context, there is a lot to talk about: B-tree, Hash, GiST, SP-GiST, GIN, BRIN, RUM. But what if I tell you that even the first item in this list alone hiding astonishing number of interesting details and years of research? In this blog post I’ll try to prove this statement, and we will be concerned mostly with B-tree as a data structure.