Profiling Particular person Queries in a Concurrent System

A great CPU profiler is price its weight in gold. Measuring efficiency in-situ often means utilizing a sampling profile. They supply a variety of info whereas having very low overhead. In a concurrent system, nonetheless, it’s laborious to make use of the ensuing information to extract high-level insights. Samples don’t embody context like question IDs and application-level statistics; they present you what code was run, however not why.

This weblog introduces trampoline histories, a method Rockset has developed to effectively connect application-level info (question IDs) to the samples of a CPU profile. This lets us use profiles to grasp the efficiency of particular person queries, even when a number of queries are executing concurrently throughout the identical set of employee threads.

Primer on Rockset

Rockset is a cloud-native search and analytics database. SQL queries from a buyer are executed in a distributed vogue throughout a set of servers within the cloud. We use inverted indexes, approximate vector indexes, and columnar layouts to effectively execute queries, whereas additionally processing streaming updates. Nearly all of Rockset’s performance-critical code is C++.

Most Rockset clients have their very own devoted compute sources known as digital cases. Inside that devoted set of compute sources, nonetheless, a number of queries can execute on the similar time. Queries are executed in a distributed vogue throughout the entire nodes, so because of this a number of queries are lively on the similar time in the identical course of. This concurrent question execution poses a problem when attempting to measure efficiency.

Concurrent question processing improves utilization by permitting computation, I/O, and communication to be overlapped. This overlapping is very necessary for top QPS workloads and quick queries, which have extra coordination relative to their basic work. Concurrent execution can also be necessary for decreasing head-of-line blocking and latency outliers; it prevents an occasional heavy question from blocking completion of the queries that comply with it.

We handle concurrency by breaking work into micro-tasks which might be run by a set set of thread swimming pools. This considerably reduces the necessity for locks, as a result of we are able to handle synchronization by way of process dependencies, and it additionally minimizes context switching overheads. Sadly, this micro-task structure makes it troublesome to profile particular person queries. Callchain samples (stack backtraces) might need come from any lively question, so the ensuing profile exhibits solely the sum of the CPU work.

Profiles that mix the entire lively queries are higher than nothing, however a variety of guide experience is required to interpret the noisy outcomes. Trampoline histories allow us to assign many of the CPU work in our execution engine to particular person question IDs, each for steady profiles and on-demand profiles. It is a very highly effective instrument when tuning queries or debugging anomalies.

DynamicLabel

The API we’ve constructed for including application-level metadata to the CPU samples is known as DynamicLabel. Its public interface could be very easy:

class DynamicLabel {
  public:
    DynamicLabel(std::string key, std::string worth);
    ~DynamicLabel();

    template <typename Func>
    std::invoke_result_t<Func> apply(Func&& func) const;
};

DynamicLabel::apply invokes func. Profile samples taken throughout that invocation could have the label hooked up.

Every question wants just one DynamicLabel. Each time a micro-task from the question is run it’s invoked by way of DynamicLabel::apply.

Some of the necessary properties of sampling profilers is that their overhead is proportional to their sampling price; that is what lets their overhead be made arbitrarily small. In distinction, DynamicLabel::apply should do some work for each process whatever the sampling price. In some circumstances our micro-tasks may be fairly micro, so it can be crucial that apply has very low overhead.

apply‘s efficiency is the first design constraint. DynamicLabel‘s different operations (building, destruction, and label lookup throughout sampling) occur orders of magnitude much less incessantly.

Let’s work via some methods we’d attempt to implement the DynamicLabel performance. We’ll consider and refine them with the aim of constructing apply as quick as doable. If you wish to skip the journey and bounce straight to the vacation spot, go to the “Trampoline Histories” part.

Implementation Concepts

Thought #1: Resolve dynamic labels at pattern assortment time

The obvious technique to affiliate utility metadata with a pattern is to place it there from the start. The profiler would search for dynamic labels on the similar time that it’s capturing the stack backtrace, bundling a duplicate of them with the callchain.

Rockset’s profiling makes use of Linux’s perf_event, the subsystem that powers the perf command line instrument. perf_event has many benefits over signal-based profilers (reminiscent of gperftools). It has decrease bias, decrease skew, decrease overhead, entry to {hardware} efficiency counters, visibility into each userspace and kernel callchains, and the flexibility to measure interference from different processes. These benefits come from its structure, during which system-wide profile samples are taken by the kernel and asynchronously handed to userspace via a lock-free ring buffer.

Though perf_event has a variety of benefits, we are able to’t use it for thought #1 as a result of it might probably’t learn arbitrary userspace information at sampling time. eBPF profilers have the same limitation.

Thought #2: Document a perf pattern when the metadata modifications

If it’s not doable to tug dynamic labels from userspace to the kernel at sampling time, then what about push? We may add an occasion to the profile each time that the thread→label mapping modifications, then post-process the profiles to match up the labels.

A technique to do that could be to make use of perf uprobes. Userspace probes can file operate invocations, together with operate arguments. Sadly, uprobes are too sluggish to make use of on this vogue for us. Thread pool overhead for us is about 110 nanoseconds per process. Even a single crossing from the userspace into the kernel (uprobe or syscall) would multiply this overhead.

Avoiding syscalls throughout DynamicLabel::apply additionally prevents an eBPF answer, the place we replace an eBPF map in apply after which modify an eBPF profiler like BCC to fetch the labels when sampling.

edit: eBPF can be utilized to tug from userspace when amassing a pattern, studying fsbase after which utilizing bpfprobelearnconsumer() to stroll a userspace information construction that’s hooked up to a threadnative. If in case you have BPF permissions enabled in your manufacturing setting and are utilizing a BPF-based profiler then this different generally is a good one. The engineering and deployment points are extra advanced however the end result doesn’t require in-process profile processing. Because of Jason Rahman for pointing this out.

Thought #3: Merge profiles with a userspace label historical past

If it is too costly to file modifications to the thread→label mapping within the kernel, what if we do it within the userspace? We may file a historical past of calls to DynamicLabel::apply, then be part of it to the profile samples throughout post-processing. perf_event samples can embody timestamps and Linux’s CLOCK_MONOTONIC clock has sufficient precision to look strictly monotonic (a minimum of on the x86_64 or arm64 cases we’d use), so the be part of could be precise. A name to clock_gettime utilizing the VDSO mechanism is quite a bit sooner than a kernel transition, so the overhead could be a lot decrease than that for thought #2.

The problem with this strategy is the information footprint. DynamicLabel histories could be a number of orders of magnitude bigger than the profiles themselves, even after making use of some easy compression. Profiling is enabled constantly on all of our servers at a low sampling price, so attempting to persist a historical past of each micro-task invocation would shortly overload our monitoring infrastructure.

Thought #4: In-memory historical past merging

The sooner we be part of samples and label histories, the much less historical past we have to retailer. If we may be part of the samples and the historical past in near-realtime (maybe each second) then we wouldn’t want to jot down the histories to disk in any respect.

The commonest means to make use of Linux’s perf_event subsystem is by way of the perf command line instrument, however the entire deep kernel magic is obtainable to any course of by way of the perf_event_open syscall. There are a variety of configuration choices (perf_event_open(2) is the longest manpage of any system name), however when you get it arrange you’ll be able to learn profile samples from a lock-free ring buffer as quickly as they’re gathered by the kernel.

To keep away from competition, we may preserve the historical past as a set of thread-local queues that file the timestamp of each DynamicLabel::apply entry and exit. For every pattern we might search the corresponding historical past utilizing the pattern’s timestamp.

This strategy has possible efficiency, however can we do higher?

Thought #5: Use the callchains to optimize the historical past of calls to `apply`

We will use the truth that apply exhibits up within the recorded callchains to cut back the historical past dimension. If we block inlining in order that we are able to discover DynamicLabel::apply within the name stacks, then we are able to use the backtrace to detect exit. Because of this apply solely wants to jot down the entry data, which file the time that an affiliation was created. Halving the variety of data halves the CPU and information footprint (of the a part of the work that isn’t sampled).

This technique is one of the best one but, however we are able to do even higher! The historical past entry data a spread of time for which apply was sure to a selected label, so we solely have to make a file when the binding modifications, somewhat than per-invocation. This optimization may be very efficient if now we have a number of variations of apply to search for within the name stack. This leads us to trampoline histories, the design that now we have carried out and deployed.

Trampoline Histories

If the stack has sufficient info to search out the correct DynamicLabel , then the one factor that apply must do is depart a body on the stack. Since there are a number of lively labels, we’ll want a number of addresses.

A operate that instantly invokes one other operate is a trampoline. In C++ it’d appear like this:

__attribute__((__noinline__))
void trampoline(std::move_only_function<void()> func) {
    func();
    asm unstable (""); // stop tailcall optimization
}

Word that we have to stop compiler optimizations that will trigger the operate to not be current within the stack, particularly inlining and tailcall elimination.

The trampoline compiles to solely 5 directions, 2 to arrange the body pointer, 1 to invoke func(), and a couple of to wash up and return. Together with padding that is 32 bytes of code.

C++ templates allow us to simply generate an entire household of trampolines, every of which has a novel deal with.

utilizing Trampoline = __attribute__((__noinline__)) void (*)(
        std::move_only_function<void()>);

constexpr size_t kNumTrampolines = ...;

template <size_t N>
__attribute__((__noinline__))
void trampoline(std::move_only_function<void()> func) {
    func();
    asm unstable (""); // stop tailcall optimization
}

template <size_t... Is>
constexpr std::array<Trampoline, sizeof...(Is)> makeTrampolines(
        std::index_sequence<Is...>) {
    return {&trampoline<Is>...};
}

Trampoline getTrampoline(unsigned idx) {
    static constexpr auto kTrampolines =
            makeTrampolines(std::make_index_sequence<kNumTrampolines>{});
    return kTrampolines.at(idx);
}

We’ve now bought the entire low-level items we have to implement DynamicLabel:

• DynamicLabel building → discover a trampoline that isn’t at the moment in use, append the label and present timestamp to that trampoline’s historical past
• DynamicLabel::apply → invoke the code utilizing the trampoline
• DynamicLabel destruction → return the trampoline to a pool of unused trampolines
• Stack body symbolization → if the trampoline’s deal with is present in a callchain, lookup the label within the trampoline’s historical past

Efficiency Affect

Our aim is to make DynamicLabel::apply quick, in order that we are able to use it to wrap even small items of labor. We measured it by extending our current dynamic thread pool microbenchmark, including a layer of indirection by way of apply.

{
    DynamicThreadPool executor({.maxThreads = 1});
    for (size_t i = 0; i < kNumTasks; ++i) {
        executor.add([&]() {
            label.apply([&] { ++depend; }); });
    }
    // ~DynamicThreadPool waits for all duties
}
EXPECT_EQ(kNumTasks, depend);

Maybe surprisingly, this benchmark exhibits zero efficiency affect from the additional degree of indirection, when measured utilizing both wall clock time or cycle counts. How can this be?

It seems we’re benefiting from a few years of analysis into department prediction for oblique jumps. The within of our trampoline seems like a digital methodology name to the CPU. That is extraordinarily widespread, so processor distributors have put a variety of effort into optimizing it.

If we use perf to measure the variety of directions within the benchmark we observe that including label.apply causes about three dozen further directions to be executed per loop. This may sluggish issues down if the CPU was front-end sure or if the vacation spot was unpredictable, however on this case we’re reminiscence sure. There are many execution sources for the additional directions, in order that they don’t truly improve this system’s latency. Rockset is mostly reminiscence sure when executing queries; the zero-latency end result holds in our manufacturing setting as nicely.

A Few Implementation Particulars

There are some things we have executed to enhance the ergonomics of our profile ecosystem:

• The perf.information format emitted by perf is optimized for CPU-efficient writing, not for simplicity or ease of use. Although Rockset’s perf_event_open-based profiler pulls information from perf_event_open, now we have chosen to emit the identical protobuf-based pprof format utilized by gperftools. Importantly, the pprof format helps arbitrary labels on samples and the pprof visualizer already has the flexibility to filter on these tags, so it was simple so as to add and use the knowledge from DynamicLabel.
• We subtract one from most callchain addresses earlier than symbolizing, as a result of the return deal with is definitely the primary instruction that will probably be run after returning. That is particularly necessary when utilizing inline frames, since neighboring directions are sometimes not from the identical supply operate.
• We rewrite trampoline<i> to trampoline<0> in order that now we have the choice of ignoring the tags and rendering an everyday flame graph.
• When simplifying demangled constructor names, we use one thing like Foo::copy_construct and Foo::move_construct somewhat than simplifying each to Foo::Foo. Differentiating constructor varieties makes it a lot simpler to seek for pointless copies. (Should you implement this be sure to can deal with demangled names with unbalanced < and >, reminiscent of std::enable_if<sizeof(Foo) > 4, void>::sort.)
• We compile with -fno-omit-frame-pointer and use body tips to construct our callchains, however some necessary glibc features like memcpy are written in meeting and don’t contact the stack in any respect. For these features, the backtrace captured by perf_event_open‘s PERF_SAMPLE_CALLCHAIN mode omits the operate that calls the meeting operate. We discover it through the use of PERF_SAMPLE_STACK_USER to file the highest 8 bytes of the stack, splicing it into the callchain when the leaf is in a type of features. That is a lot much less overhead than attempting to seize your complete backtrace with PERF_SAMPLE_STACK_USER.

Conclusion

Dynamic labels let Rockset tag CPU profile samples with the question whose work was lively at that second. This potential lets us use profiles to get insights about particular person queries, though Rockset makes use of concurrent question execution to enhance CPU utilization.

Trampoline histories are a means of encoding the lively work within the callchain, the place the present profiling infrastructure can simply seize it. By making the DynamicLabel ↔ trampoline binding comparatively long-lived (milliseconds, somewhat than microseconds), the overhead of including the labels is stored extraordinarily low. The method applies to any system that desires to enhance sampled callchains with utility state.

Rockset is hiring engineers in its Boston, San Mateo, London and Madrid places of work. Apply to open engineering positions right now.