Introduction

Redis Stack has supported a new probabilistic data structure t-dgest.

In KvRocks, we should make an implementation to support t-digest as well.

Basic about T-Digest

The original paper is Computing Extremely Accurate Quantiles Using t-Digests [1].

Thanks to the blog T-Digest in Python [7] and the slide [8], I have a better understanding of t-digest.

The main idea of t-digest is to divide the data into small bins and store the mean and count of each bin aka centroids.

This action compressed ranges of data into a single centroids with just mean and weight. The mean is the average of the data in the bin and the weight is the number of data compressed in the bin.

This behavior is called as sketch. Sketch is necessary when we need to deal with plenty of data.

We use these centroids with interpolation to estimate the quantile of the data.

We lost some precisions of the original data and get the ability to easily merge them and calculate the quantile.

We use the potential function k to control the distribution of the bins.

Inside the function we provide a delta to control the error of the distribution.

Implementation

In original implementation [2], the implementation contains a MergingDigest and an AVLTreeDigest.

Since we leverage from rocksdb, we should map the internal structure to rocksdb.

After reading the implementation of apache arrow [5], I think that we can follow its implementation and use rocksdb to store the internal states.

metadata

In metadata, we should store the compression ($1/\delta$), total_weight, minimum and maximum of t-digest.

Plus, for compaliancy with redis, we should store merged_nodes, total_observations and merge_times for TDIGEST.INFO command.

For temporary input buffer, we should have a buffer left space for merging trigger.
When one item is pushed, unmerged_nodes will be increased. When the buffer size reaches the capacity, we should merge the buffer to the centroids and reset the buffer along with unmerged_nodes.

        +----------+------------+-----------+----------------+----------------+-----------------+-----------------+---------------+----------------+----------------+--------------------+--------------+
key =>  |  flags   |  expire    |  version  |  compression   |  capacity      |  unmerged_nodes |  merged_nodes   | total_weight  |   minimum      |   maximum      | total_observations | merge_times  |
        | (1byte)  | (Ebyte)    |  (8byte)  |  uint32(4byte) |  uint32(4byte) |  uint64(8byte)  |  uint64(8byte)  | uint64(8byte) | double(8byte)  | double(8byte)  |   uint64(8byte)    | uint64(8byte)|
        +----------+------------+-----------+----------------+----------------+-----------------+-----------------+---------------+----------------+----------------+--------------------+--------------+

centroids

Each centroid should be sorted by mean and have a weight. The mean and weight are both double precision numbers.
So, if the we try to keep the order of mean, we should design a way to serialize double and keep its order same before serialization.
Here is one encoding format of duckdb [9] to keep the original order of double and convert to a 8-byte uint64.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

inline uint64_t EncodeDouble(double x) {
  uint64_t buff;
  //! zero
  if (x == 0) {
   buff = 0;
   buff += (1ULL << 63);
   return buff;
  }
  // nan
  if (Value::IsNan(x)) {
   return ULLONG_MAX;
  }
  //! infinity
  if (x > DBL_MAX) {
   return ULLONG_MAX - 1;
  }
  //! -infinity
  if (x < -DBL_MAX) {
   return 0;
  }
  buff = Load<uint64_t>(const_data_ptr_cast(&x));
  if (buff < (1ULL << 63)) { //! +0 and positive numbers
   buff += (1ULL << 63);
  } else {          //! negative numbers
   buff = ~buff; //! complement 1
  }
  return buff;
 }

Here is the subkey of centroid.

‘centroid’ is an enum for the centroid subkey.
‘mean’ is a serialized double with order.

                              +----------------+
key|version|centroid|mean =>  |      weight    |
                              | (8byte) double |
                              +----------------+

temparory buffer

Temp buffer is just a list of doubles, we should control the limit of whole buffer’s size and should acuiqre a lock when try to merge it to the centroids.

Since we have a way to serialize the double to a ordered one, we can use same way to encode the temparory double buffer.

To avoid collisions with same value, we should add an unique identifier for each item. It can be a uint64 millisecond timestamp for simplicity.

‘buffer’ is a enum for buffer subtype.
‘value’ is serialized double for data to be inserted with order.
‘id’ is a unique identifier for collision.

  key|version|buffer|value|id => NULL

concurrency safety

The pushing to temporary list action should have acquire the lock for updating the metadata.

The merge action should acquire a lock. It includes the buffer merging and merging with other digests.

When we try to calculate the perncetile or CDF, we should merge the buffer and make a snapshot.

Then the calculation should have no lock.

References

[1]Computing Extremely Accurate Quantiles Using t-Digests

[2]https://github.com/tdunning/t-digest

[3]https://issues.apache.org/jira/browse/ARROW-11367

[4]https://github.com/apache/arrow/pull/9310

[5]https://github.com/apache/arrow/blob/main/cpp/src/arrow/util/tdigest.cc

[6]https://redis.io/docs/latest/develop/data-types/probabilistic/t-digest/

[7]T-Digest in Python

[8]https://blog.bcmeng.com/pdf/TDigest.pdf

[9]https://github.com/duckdb/duckdb

In recent days, I tried to contribute to the Kong ingress controller project.
During the development, I faced some challenges and learned a lot about the controller development in Kubernetes.
Here are some experience of how to build the environment for testing and debugging the Kong ingress controller.

Background

This issue is a task for migrating the integration test to the isolated test with kube-e2e test framework.

Environment

The first problem that I faced is how to create a Kubernetes cluster for local testing.

At first time I thought that I need to prepare a Kubernetes cluster by myself.
But after reading the GitHub Actions workflow of the Kong ingress controller project, I found that they have already integrated the bootstrap of the Kubernetes cluster in the unit test framework.

Here is related code

1
2
3
4
5
6
7
8
9
10
11
12
13

switch clusterType {
case string(kind.KindClusterType):
 cluster, err := kind.NewFromExisting(clusterName)
 helpers.ExitOnErr(ctx, err)
 builder.WithExistingCluster(cluster)
 builder.WithAddons(metallb.New())
case string(gke.GKEClusterType):
 cluster, err := gke.NewFromExistingWithEnv(ctx, clusterName)
 helpers.ExitOnErr(ctx, err)
 builder.WithExistingCluster(cluster)
default:
 helpers.ExitOnErrWithCode(ctx, fmt.Errorf("unknown cluster type: %s", clusterType), consts.ExitCodeCantUseExistingCluster)
}

And in the isolated package, they also have test suite for bootstrapping.

Dependencies

Make sure that you ahve read the contribution document and testing document before startup.

After I read the workflows’ configurations and makefile, I found that many information about development and testing are already available in these files.

Mise

The bootstrapping have some dependencies, we can find it in the makefile.

Remember that each workflow which need to be executed in the CI/CD has a workflow file and generally you will find that it invoked the makefile.

1
2
3
4

MISE := $(shell which mise)
.PHONY: mise
mise:
 @mise -V >/dev/null || (echo "mise - https://github.com/jdx/mise - not found. Please install it." && exit 1

They use a tool called “mise” which is a tool for managing environments.

So you should follow the instructions to install mise first.

ja and yq

They dependes on jq and yq to parse yaml and json files.

So, install the latest version of jq and yq by following the instructions in the official website.

Docker Engine

They use the kind to create a “Kubernetes in Docker” cluster for testing.

So, you don’t have to install a cluster ahead of time, just install the kind and you will be able to run the tests.

You should install depenecies list in the contribution guidances.

Conclusion

These are engough for local development during my experience.

Notice:

I faced some problem with WSL and use my rocky linux server instead.

Maybe a vm on hyperv/virtualbox is better than WSL.

Before run the tests, cleanup current kind clusters will be better.

Testing

I modified the makefile for local testing, but after reading the testing document I find that the makefile has provide the ability to run specific tests.

Firstly, you should find your testing command line in makefile or workflow file.

Running all testing cases will take a long time, so I suggest that you run the specific test case that you want to test.

Here is an sample.

1

make test.integration.dbless GOTESTFLAGS="-count 1 -run TestUDPRouteEssentials"

Just pass the test to the make command with GOTESTFLAGS variable.

Tips for refactoring tests

If you want to migrate the integration tests to isolated package, remember the way of assert package.

It increments the failures rather than exit on failure.
So you should make sure the previous failure won’t effect next process.

Debugging

The robust way of debugging is log.

Leverage the t.Log to generate debug logs and remove them before committing to upstream.

Keep monitoring the Kubernetes status and use related commands to get status and logs of different components such as the kong ingress deployment.

I love the k9s because it provides interactive and live status of different components.
Native kubectl or any tools you like is ok. 😊

About break points if you really wnat to debug the process

If you really really want to debug the process in an interactive IDE way, after you run the makefile, you will find the output like below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

KONG_CLUSTER_VERSION="v1.28.0" \
        TEST_KONG_HELM_CHART_VERSION="2.40.0" \
        TEST_DATABASE_MODE="off" \
        GOFLAGS="-tags=integration_tests" \
        KONG_CONTROLLER_FEATURE_GATES="GatewayAlpha=true" \
        go test  \
        -v \
        -timeout "45m" \
        -parallel 12 \
        -race \
        -ldflags="" \
        -covermode=atomic \
        -coverpkg=./pkg/...,./internal/... \
        -coverprofile=coverage.dbless.out \
        ./test/integration/isolated -run 'TestTCPRouteReferenceGrant' -args --parallel

Use the configuration of this command line to configure your IDE and you will be able to attach to the running process.

Summary

Here is a brief introduction of my contribution experience with the Kong ingress controller project.

I hope this article can help you to get started with the Kong ingress controller project.

Plus, during my development, I find the way Kong using is efficient and I have the plan to apply the e2e testing framework to my project in CI.

References

[1] https://github.com/Kong/kubernetes-ingress-controller/blob/main/CONTRIBUTING.md

[2] https://github.com/Kong/kubernetes-ingress-controller/blob/main/TESTING.md

[3] https://github.com/kubernetes-sigs/e2e-framework

[4] https://github.com/Kong/kubernetes-ingress-controller/pull/6450

RVO (Return Value Optimization) and NRVO (Named Return Value Optimization) (also called copy elision)

some small questions

• Q: order of local variable desctruction and returning value copy/move
  A: return statement
• Q: will right-reference value return to caller when call move ctor in return statement?

definition of RVO

in a return statement in a function with a class return type, when the expression is the name of a non-volatile automatic object (other than a function or catch-clause parameter) with the same cv-unqualified type as the function return type, the copy/move operation can be omitted by constructing the automatic object directly into the function’s return value

example

cpp98/03 NVRO

detail introduction

RVO is a optimization techonology that effects constrcution behavior and changes stack’s return value layout.
Here is a blog about this.

1. Before RVO, function stack’s layout is like below.
   

2. With RVO, function stack’s layout is like below.
   

move semantics and rvalue

Question

1. Why do we need move semantics since we have RVO?
2. How does move semantics effect code behavior?

lvaue and rvalue

lvaue is short for left-reference value and rvalue is for right-reference.
Here is an example.

1
2
3
4
5

auto i = std::string{"value categories"};  
// `i` is an lvalue  
// `std::move(i)` is an xvalue  
// `static_cast<std::string&&>(i)` is an xvalue  
// `std::string{"value categories"}` is a prvalue (pure rvalue)

• must be aware that rvalue is always a compile time concept.
• rvalue is a un-named value, cpp only have named variables, thus it means that each memory can be reached and destructed correctly.
• cv rvalue can’t move to a value directly. Its behavior will be same as normal cv lvaue after compiling. foo(source_const_rvalue_ref()); // #1

detail binding rules

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

struct A {};
 
void foo(const A&);  // #1
void foo(A&&);       // #2
 
A   source_rvalue();
A&  source_ref();
A&& source_rvalue_ref();
 
const A   source_const_rvalue();
const A&  source_const_ref();
const A&& source_const_rvalue_ref();
 
int main()
{
    A a;
    A&  ra = a;
    A&& rra = a;
    const A ca;
    const A& rca = ca;
    const A&& rrca = ca;
 
    foo(a);      // #1
    foo(ra);     // #1
    foo(rra);    // #1
 
    foo(ca);     // #1
    foo(rca);    // #1
    foo(rrca);   // #1
 
    foo(source_rvalue());     // #2
    foo(source_ref());        // #1
    foo(source_rvalue_ref()); // #2
 
    foo(source_const_rvalue());     // #1
    foo(source_const_ref());        // #1
    foo(source_const_rvalue_ref()); // #1
}

lvalues, both const and non-const bind to foo(const A&). Named references, both lvalue and rvalue, all bind to foo(const A&). Non-const rvalues and unnamed rvalue references bind to foo(A&&). Const rvalues and const rvalue references bind to foo(const A&). Had there been a foo(const A&&) available, they would have bound to that. The lvalue references bind to foo(const A&).

Caution

move will become a normal rvalue or copy with bind it with a const name.

std::move

what is std::move?

std::move is just a type cast annotation in compile time and exactly has no effect in runtime. (including std::forward)
std::move casts an object to a rvalue. It has no other effect.

• If left value is only a reference, rvalue will be bind to it.
• If left named value is not a reference and has move ctor, compile will make it call move-ctor.
• If doesn’t have a move-ctor(be deleted), copy-ctor will happen.

Move doesn’t move anything!

1
2
3
4
5
6
7
8
9

/**
 *  @brief  Convert a value to an rvalue.
 *  @param  __t  A thing of arbitrary type.
 *  @return The parameter cast to an rvalue-reference to allow moving it.
*/
template<typename _Tp>
  constexpr typename std::remove_reference<_Tp>::type&&
  move(_Tp&& __t) noexcept
  { return static_cast<typename std::remove_reference<_Tp>::type&&>(__t); }

move ctor

Question

1. is move behavior always safe and don’t need us to pay any more attention on it?

move ctor syntax

1
2
3
4
5
6
7
8
9

class A {
public:

// move ctor
A(A&&) {}

// move operator
A& oprerator=(A&&){}
}

use move ctor

be patient that cpp’s move semantics is non-destructive

1. Rust move semantics is destructive
2. Cpp is value passing based language but Rust is move passing based
3. Comparing with Rust‘s variable lifetime and Cpp’s, you will have a deeper understanding about cpp’s RAII and move semantics

how to write a clean move-ctor? example

remind that you must clean stealed object’s resource. On the other hand, any object could be moved can be safely resource-less.

some potential problems with move-ctor

when to disable move-ctor? std::enable_shared_from_this

Some small examples

• both lvalue
• both universal reference
• suprise when combining RVO and move

move semantcis

Question

1. Is move is as effective as we expect?
2. Compare move with RVO?

   SSO (small string optimization)

   small strings will use stack space rather than heap space.
   move doesn’t reduce cost and remove RVO optimization.

Some more questions

• Before you see cpp’s move semantics, what should a move look like in your mind?
• Do cpp move semantics has runtime cost?

Some personal opinions

• Currently programming language can be divided into several categories:
  • pass by value
  • pass by reference (mostly are reference pointer copy and its behavior is pass-by-value. real pass-by-reference is not a sugar of pointer copy, it should be just alias during compile time. Thus, it will cause confliction between original value’s and alias’ lifetime)
  • pass by move
• RVO is real move and rvalue is just a simulation. It’s not real zero-cost.
• do not use std::move just for an intuition when you return. It’s final behavior is more complex than expected.

Universal reference

introduction

Universal reference can match any kind of input argument.
Here is a samle.

1
2
3
4

template <typename T>
void foo(T&& t) {
 // do something you like
}

perfect forward

Question: Why we need perfect forward?

Here is a example of boost::compressed_pair. By the way, it’s a very good example for template SFINAE.

1
2
3
4

compressed_pair<T1, T2>::compressed_pair(compressed_pair&& x)
    : first_ (static_cast<T1&&>(x.first_)),
      second_(static_cast<T2&&>(x.second_))
{}

This just solve reference and right-reference without cv constraint.
If we want to both support const , N-argument case would require 2N overloads.

So be aware that perfect forward does nothing in runtime. It just forwards arguments with original type to next function.

It looks like below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void foo(Arg1&, Arg2&&)
void foo(const Arg1&, Arg2&&);
void foo(Arg1&, const Arg2&&);
void foo(const Arg1&, const Arg2&&);

template <typename T1, typename T2>
decltype(auto) forward_foo(T1&& arg1, T2&& arg2) {
	return foo(std::forward<T1>(arg1), std::forward<T1>(arg2));
}

typename <typename... Args>
decltype(auto) forward_list_foo(Args&&... args) {
   return foo(std::forward<Args>(args)...);
}

auto cpp_20_auto_forward_foo(auto&&... args) // since C++20
{
    return foo(std::forward<decltype(args)>(args)...);
}

implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 *  @brief  Forward an lvalue.
 *  @return The parameter cast to the specified type.
 *
 *  This function is used to implement "perfect forwarding".
 */
template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type& __t) noexcept
  { return static_cast<_Tp&&>(__t); }

/**
 *  @brief  Forward an rvalue.
 *  @return The parameter cast to the specified type.
 *
 *  This function is used to implement "perfect forwarding".
 */
template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
  {
    static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
      " substituting _Tp is an lvalue reference type");
    return static_cast<_Tp&&>(__t);
  }

when should use it

Perfect forward and universal reference are all only for generics.
When you have multiple implements(count can be fixed or not) and need an universal entry, you can use it.

Let’s use std::make_unique as an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

template<typename _Tp>
    struct _MakeUniq
    { typedef unique_ptr<_Tp> __single_object; };
  
template<typename _Tp>
    struct _MakeUniq<_Tp[]>
    { typedef unique_ptr<_Tp[]> __array; };

template<typename _Tp, size_t _Bound>
    struct _MakeUniq<_Tp[_Bound]>
    { struct __invalid_type { }; };

/// std::make_unique for single objects
template<typename _Tp, typename... _Args>
inline typename _MakeUniq<_Tp>::__single_object
	make_unique(_Args&&... __args)
	{ return unique_ptr<_Tp>(new _Tp(std::forward<_Args>(__args)...)); }

/// std::make_unique for arrays of unknown bound
template<typename _Tp>
inline typename _MakeUniq<_Tp>::__array
    make_unique(size_t __num)
    { return unique_ptr<_Tp>(new remove_extent_t<_Tp>[__num]()); }

/// Disable std::make_unique for arrays of known bound
template<typename _Tp, typename... _Args>
inline typename _MakeUniq<_Tp>::__invalid_type
    make_unique(_Args&&...) = delete;

Some interesting questions

1. what is reference’s semantics? (don’t bind to a specfic language)
2. do reference in cpp really zero-cost?
3. why does cpp need reference semantics and c does not?
4. why previous cpp doesn’t allow reference of a reference?
5. what’s a dangling reference?
6. what is a real move semantics in your mind? (not bind to any language)
7. how should behavior be when move between stack and heap?
8. when can a move action be absolutely safe?
9. which pass-by type do you think for c, cpp, java, go, python, perl .etc?

move behavior in Rust

Move constructors are meaningless in Rust because we don’t enable types to “care” about their location in memory. Every type must be ready for it to be blindly memcopied to somewhere else in memory. This means pure on-the-stack-but- still-movable intrusive linked lists are simply not happening in Rust (safely).

Here is document link.

references

https://reuk.github.io/page-fault/emcpp/chapter_5.html

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm

https://community.ibm.com/community/user/power/blogs/archive-user/2020/05/28/rvo-vs-stdmove

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1385.htm

https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers