Just Give Me the Code

Fine... Here you go.

Motivation

Kanali is an extremely efficient Kubernetes ingress controller with robust API management capabilities. Built using native Kubernetes constructs, Kanali gives you all the capabilities you need when exposing services in production without the need for multiple tools to accomplish them.

This will be the first of a few posts that take a deep technical dive into different aspects of Kanali. If you haven't read my blog post, Cloud Native API Management for Kubernetes, I highly recommend you read that first so that you can get acclimated with Kanali. In part 2 of this series, we will examine Kanali's extensible, decoupled, and version controlled plugin framework.

One of the primary design goals when designing Kanali was performance. In this post, we will dissect both Kanali's network and runtime performance and its related implementation.

Analysis

As a middleware component, Kanali needs to be extremely fast. Its total performance is an aggregate of both its network and runtime performance.

For any arbitrary request, Kanali incurs zero network overhead. This means that the only network traffic that occurs, other than the actual request being handled, is the proxy to the upstream service (assuming a mock response is not being used). In order to accomplish this, Kanali maintains a number of efficient, in memory data structures for the different Kubernetes resources it needs information from to dynamically route traffic. To ensure accuracy at all times, these data structures are kept up to date with the latest from the Kubernetes API server.

Kanali will open an HTTP stream on each Kubernetes resource that it uses. When new data is emitted, Kanali will deserialize it add it to the appropriate data structure. If the Kubernetes API server is unavailable, incoming network traffic will not be affected and updates from the Kubernetes API server will resume when it becomes available.

Concerning runtime performance, it is not enough to simply store the Kubernetes resources Kanali receives into memory. We must also ensure that the data structures these resources are stored in is designed in a way that ensures an optimized asymptotic time complexity in the worst case.

Implementation

Let's dive into an implementation overview where we will explore how Kanali accomplishes the above claims.

Every data structure that Kanali implements for each of the Kubernetes resources it relies on implements the following interface. There are six such implementations:

type Store interface {  
    Set(obj interface{}) error
    Get(params ...interface{}) (interface{}, error)
    Delete(obj interface{}) (interface{}, error)
    Clear()
    IsEmpty() bool
}

As an example, let's explore how the ProxyFactory is implemented. Since incoming requests will need to read from the ProxyStore and our Kubernetes watch implementation will need to write to it, we need to use a RWMutex. This will create a mutual exclusion lock that can be held by an arbitrary number of readers or a single writer.

type ProxyFactory struct {  
    mutex     sync.RWMutex
    proxyTree *proxyNode
}

type proxyNode struct {  
    Children map[string]*proxyNode
    Value    *APIProxy
}

var ProxyStore *ProxyFactory  

For each request, it will take Θ(n) time, where n is the number of path segments in the url, to determine whether an APIProxy exists for the given request.

func (s *ProxyFactory) Get(params ...interface{}) (interface{}, error) {  
    s.mutex.RLock()
    defer s.mutex.RUnlock()
    // ...
    rootNode := s.proxyTree
    for _, part := range strings.Split(path, "/") {
        if rootNode.Children[part] == nil {
            break
        }
        rootNode = rootNode.Children[part]
    }
    if rootNode.Value == nil {
        return nil, nil
    }
    return *rootNode.Value, nil
}

It will take Θ(m) time, where m is the number of path segments in the APIProxy path, to insert a new APIProxy in the tree.

func (s *ProxyFactory) Set(obj interface{}) error {  
    s.mutex.Lock()
    defer s.mutex.Unlock()
    // ...
    if p.Spec.Path[0] == '/' {
        s.proxyTree.doSet(strings.Split(p.Spec.Path[1:], "/"), &p)
    } else {
        s.proxyTree.doSet(strings.Split(p.Spec.Path, "/"), &p)
    }
    return nil
}

func (n *proxyNode) doSet(pathSegments []string, v *APIProxy) {  
    if n.Children == nil {
        n.Children = map[string]*proxyNode{}
    }
    if n.Children[pathSegments[0]] == nil {
        n.Children[pathSegments[0]] = &proxyNode{}
    }
    if len(keys) < 2 {
        n.Children[pathSegments[0]].Value = v
    } else {
        n.Children[pathSegments[0]].doSet(pathSegments[1:], v)
    }
}

As each data structure has a different design and implementation so that it is optimized for the way in which Kanali uses it, here is the asymptotic complexity for each of the additional factories referenced above:

KeyFactory

If an APIProxy uses the API key plugin, Kanali must retrieve a matching APIKey resource, if one exists, for a given API key.

Mutations: Θ(1)
Access: Θ(1)

BindingFactory

There is a one to one correlation between an APIProxy resource and an APIKeyBinding resource, Hence, if an APIProxy uses the API key plugin, its associated APIKeyBinding resource must be retrieved.

Mutations: Θ(1)
Access: Θ(1)

If the APIKeyBinding resource defines fine grained permissions for the given API key, a combination of the the url subpath and the HTTP verb is used to find the highest priority ruleset.

Mutations: Θ(nm) where n is the number of fine grained subpaths defined for a given API key and m is the number of url path segments in the current subpath.
Access: Θ(m) where m is the number of url path segments in the requests computed subpath.

MockResponseFactory

If a mock response is defined for a given APIProxy, the mock response, if any, must be retrieved from the referenced ConfigMap.

Mutations: Θ(nm) where n is the number of target mock response url paths and m is the number of url path segments in the current mock response path.
Access: Θ(m) where m is the number of url path segments in the requests computed target path.

SecretFactory

If TLS is defined for a given APIProxy, the Kubernetes secret holding the certificates to be used in the upstream request bust be retrieved.

Mutations: Θ(1)
Access: Θ(1)

ServiceFactory

An APIProxy resource can either statically or dynamically define an upstream Kubernetes service to route traffic to. This service must be retrieved. Currently, the same algorithm is used regardless if the reference service is statuc or dynamic.

Mutations: Θ(1)
Access: Θ(n) where n is the number of services in a given namespace. Note: there is an open issue to improve this performance.

Summary

How does this performance centric implementation affect API response times? Here is a single comparison of an arbitrary API call that is fronted by Kanali (top) and by a vendor product (bottom):

$ ab -n 1000 -c 50 ...
...
Percentage of the requests served within a certain time (ms)  
  50%    497
  66%    514
  75%    524
  80%    531
  90%    569
  95%    597
  98%    642
  99%    644
 100%    674 (longest request)
$ ab -n 1000 -c 50 ...
...
Percentage of the requests served within a certain time (ms)  
  50%   2427
  66%   2609
  75%   2629
  80%   2644
  90%   2847
  95%   2951
  98%   3259
  99%   3267
 100%   3877 (longest request)