Datagram builder as a C extension

[methodmissing]

Why?

The datagram builder is heavy on allocation (and reallocation) when coercing both metric names and tags into normalized and valid statsd wire protocol components.

This extension is also implemented as a wrapped struct without any global state as @hkdsun and @bmansoob expressed interest in how to do that.

• A simple struct with mixed native type and VALUE (Ruby object reference) members

• GC mark callback invoked during the GC tracing phase (we need to let the GC know about Ruby object references we hold on to)

• GC free callback invoked during the sweep phase if this object was deemed to not be referenced by any other, the stack etc. . We free the symbol tables for caches and the struct itself.

• It's a good practice to add an object size accumulator callback to accurately reflect the size of this object via Objspace.memsize_of

• A data type declaration defines the shape of the wrapped object and callbacks for the GC

• An unboxing function coerces a VALUE reference back to a builder struct as per the type definition above

• The allocator function prepares the struct for use by initializing members to their appropriate types, caches conditionally etc. and returns a VALUE reference to the allocated struct on the heap

Points of attack

• The prefix is constant, initialized once yet merged into the output buffer from offset 0 to it's length for every builder call. We can instead seed the builder buffer with it and advance the buffer low water mark to the end of prefix on every call

• Name normalization is expensive as it involves a regex match for the fast path and an additional function call for the slow path. For the fast path it's more efficient to walk to string from start to end , and for the slow path implement a bounded size normalized names cache to save on String#tr function calls for invalid metric names.

• Tags normalization is expensive and especially with the hybrid Hash and Array tags API allocates additional objects for the Hash based API. This method is not optimized in C as it's mostly iterators and method calls which can become EXTREMELY ugly rewriting in a C extension. Instead another bounded size normalized tags cache was introduced to bypass this Ruby method for tags collections with a contents hash we've seen before.

• There's always a new tags Array spawned in the generate_generic_datagram method. This is wasteful even for cases which don't have any default tags defined. This was flattened out into a zero alloc append only pattern instead.

• Sample rate values appended to the buffer is zero alloc for Fixnum and Float types, but has a fallback path for other object types which would allocate a ruby String. This pattern likely works well for the value argument too, but would prefer to get runtime feedback first and consider it as a later optimisation.

• Remove a repeated ivar lookup and size check for default tags in favor of caching it on the builder struct instead on init.

• Reduce method dispatch overhead by calling the builder directly from the various metric helper methods.

Configurables

• The buffer size can be changed compile time

• Normalized caches are compile time features that can easily be disabled or changed

Resiliency issues covered

• Strict overflow checks that finalize the buffer prior to overflow

• Test suite run with GC.stress = true

Wrapped builder struct layout

Fits within 1 cache line (46 of 64 bytes) with the buffer as the last member. 4kb is very generous, but in reality the vast majority of statsd datagrams would only reach into 1 or 2 more cache lines.

The struct is passed around by reference as it's heap allocated anyways and few things are as bad as large structs passed by value.

lourens@CarbonX1:~/src/statsd-instrument/lib/statsd/instrument/ext$ pahole -C datagram_builder ./statsd.so
struct datagram_builder {
    st_table *                 normalized_tags_cache; /*     0     8 */
    st_table *                 normalized_names_cache; /*     8     8 */
    VALUE                      str_normalize_chars;  /*    16     8 */
    VALUE                      str_normalize_replacement; /*    24     8 */
    VALUE                      default_tags;         /*    32     8 */
    _Bool                      empty_default_tags;   /*    40     1 */

    /* XXX 3 bytes hole, try to pack */

    int                        prefix_len;           /*    44     4 */
    int                        len;                  /*    48     4 */
    char                       datagram[4096];       /*    52  4096 */

    /* size: 4152, cachelines: 65, members: 9 */
    /* sum members: 4145, holes: 1, sum holes: 3 */
    /* padding: 4 */
    /* last cacheline: 56 bytes */
};

Future TODO

• Remove the String allocation for the value argument
• Evaluate the hashing function used for the tags cache (Hash and Array specific are not directly exposed through the extension API)

Downsides

• This library now becomes dependent of a C compiler and ruby development headers - need to think about decoupling so that is optional.

Other ideas

• Willem mentioned more Stricter mode linters that can catch invalid metric names and tags enabled for example during CI could work wonders too.

@csfrancis @wvanbergen

[methodmissing]

... and some CI massaging required

[wvanbergen]

This library now becomes dependent of a C compiler and ruby development headers - need to think about decoupling so that is optional.

In think there are two ways to address this:

1. The datagram builder is already configurable. We could ship this as a separate datagram builder class (potentially as a different gem). The client can then configure to use this different datagram builder class, maybe using an environment variable.
2. We create a separate gem that when loaded, will overwrite the datagram builder class with this native implementation.

[methodmissing]

Yeah that makes sense - like the sequel model

[methodmissing]

@wvanbergen objections to spawning statsd-instrument-c (blocked on a better name, patches welcome :smile:)? That would also introduce some other issues to think about:

• What happens with test coverage in light of the extracted extension?
• Running the main test suite with and without the C extensions (gems become a CI dependency)