<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Tony Allen on Medium]]></title>
        <description><![CDATA[Stories by Tony Allen on Medium]]></description>
        <link>https://medium.com/@tonya11en?source=rss-f738ce546ad7------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*lB9bR1EdvGCB4WQlaXom9A.png</url>
            <title>Stories by Tony Allen on Medium</title>
            <link>https://medium.com/@tonya11en?source=rss-f738ce546ad7------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 17:50:09 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@tonya11en/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Thoughts on Tenant Isolation and Load Shedding]]></title>
            <link>https://tonya11en.medium.com/thoughts-on-tenant-isolation-and-load-shedding-1fe9369383c0?source=rss-f738ce546ad7------2</link>
            <guid isPermaLink="false">https://medium.com/p/1fe9369383c0</guid>
            <category><![CDATA[software-architecture]]></category>
            <category><![CDATA[networking]]></category>
            <dc:creator><![CDATA[Tony Allen]]></dc:creator>
            <pubDate>Mon, 05 Apr 2021 17:59:50 GMT</pubDate>
            <atom:updated>2021-04-05T17:59:50.518Z</atom:updated>
            <content:encoded><![CDATA[<p>I spend a fair bit of time these days thinking about overloaded servers and one recent problem I’ve wrestled with is how to shed load <em>fairly</em> when a server is overloaded. For example, if there are two separate tenants (users, accounts, clients, etc.) consuming vastly different amounts of resources, should we be treating them the same when shedding load? If one of those tenants is “misbehaving” and flooding the system with traffic, this can begin to affect everyone else sharing the system with this “noisy-neighbor”.</p><p>The different approaches to fairness I see folks taking are to either give each tenant some static limit, shedding the excess traffic, or just ignoring the problem altogether. I think we can do better. In this article, I want to take a look at this tenant fairness problem in a bit more detail, discuss some neat queuing techniques we can use to solve it, and their tradeoffs. This one’s for the nerds.</p><h3>The Noisy Neighbor Problem</h3><p>Let’s say we have a simple one-node service that FIFO enqueues requests to be scheduled on some worker threads. We also have a basic, but super effective load shedding mechanism in the form of queue timeouts — if a request sits in the server queue for too long, we shed it. Each request has an associated tenant ID like a user account, originating microservice, source client, someone’s name — whatever.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/462/0*XyhZSvl6Iv_eWvXF" /><figcaption>Our example service architecture.</figcaption></figure><p>Now, let’s assume that this is an ideal world where each request is identical, uses the same amount of server resources, and has the same latency profile. If each tenant’s request rate is identical, the worker threads, server queue, and traffic shed has the same number of requests from each tenant. Things are peachy!</p><p>But what happens if we start drifting closer to reality and one of those tenants starts to send way more traffic than the others? Well… we’d have a noisy-neighbor problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/483/0*d5xXRC2MhzvsnkcW" /><figcaption>A noisy-neighbor fills our server queue.</figcaption></figure><p>I hacked something together using <a href="https://github.com/tonya11en/bufferbloater">Bufferbloater</a> to illustrate what this would look like. There are two tenants sending the same small amount of traffic and one tenant continuously increasing the amount of traffic it sends. With a queue timeout in place, we get the following result:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*PEy5eIk5r0xLwgm1" /><figcaption>From top to bottom for each tenant: request latencies, rate of requests sent, rate of requests throttled, and request success %.</figcaption></figure><p>Each color (blue, green, and orange) in the graph represents a different tenant. At the top, we have the request latencies — each point is an individual request. This is followed by the requests per second (RPS) for each tenant in the 2nd graph from. The noisy-neighbor tenant (in blue) continuously increases the rate of requests it sends to the server, which results in elevated latencies for everyone. As the noisy-neighbor ramps up its traffic, <em>all </em>of the latencies start to increase due to the queuing delays, but eventually plateau since we’ve put an upper-bound on the delays thanks to the queue timeouts!</p><p>The bottom two graphs are where we can clearly see the problem caused by the noisy-neighbor. The graphs show the number of requests shed per-second followed the client-observed request success rate. Even though the well-behaved tenants have not increased their RPS, <em>their success rates are affected</em> even though they are not the ones responsible here. The server is spending most of its time servicing the noisy-neighbor’s requests. We can hardly call that fair!</p><h3>Don’t Use Fixed Resource Limits</h3><p>One approach I see quite often when tackling these noisy-neighbor problems is to give each tenant some static resource quota and strictly enforce it. It can take the form of something like setting a per-tenant max request rate or a per-tenant request concurrency limit. This is at best an operational nightmare, requiring constant tweaking to get right, and at worst makes things worse than they were before.</p><p>It’s extremely difficult to know the capacity of a server. The maximum concurrency limit or RPS that can be serviced before the server degrades is a moving target. The performance characteristics of the server can change with new commits, the types of requests being sent, CPU thermal throttling, cloud vendor nonsense, heterogeneous environments, etc.</p><h3>Tenant Isolation in the Queue</h3><p>Rather than using a FIFO queuing discipline in our server queue, let’s use a fair or weighted fair queue (WFQ) instead.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/842/0*-xAHv83Tqiys0ppK" /><figcaption>A closer look at a fair queue.</figcaption></figure><p>For each tenant, or “input class”, we can give them their own separate logical queue. These tenant queues can then be scheduled in a fair manner, which provides isolation among the tenants. When it comes to how these fair queues are implemented, the devil is in the scheduling details. A basic approach is to simply round-robin among the tenant queues, which is sometimes referred to as a <a href="https://tools.ietf.org/html/rfc970.html">Nagle fair queue</a>. That’s what we’ll do here for simplicity, but just know that scheduling techniques can get quite interesting and are their own area of research.</p><p>When using a fair queue in the same noisy-neighbor test from before, we get wildly different results:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BRiFKtVukPuNemFL" /><figcaption>A noisy-neighbor test with isolated server queues.</figcaption></figure><p>The first thing to notice is the top-most graph that shows the latency for each request (recall that they are colored by tenant). When we did not have a fair queue in place, all of the tenants’ request latencies suffered, but now you can see that <strong>only the noisy-neighbor</strong> sees the elevated latencies! The bottom two graphs showing the throttled request rate and overall success rate also show us that only the noisy neighbor has its traffic shed, completely eliminating the noisy-neighbor problem.</p><p>One neat property of the WFQ is that while it guarantees tenants get their “fair share” of the resources, it can do so dynamically and only as needed. If there’s a single tenant using more than its share, it may continue to do so as long as the server has resources to accommodate. As the other tenants use more resources, the queuing will adapt.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-P8IhSZY1P9qSqD6" /><figcaption>The WFQ adapts to the request rates of the different tenants.</figcaption></figure><p>Here, the blue tenant’s requests consumed a disproportionate amount of server resources and did so consistently throughout the test. The server could accommodate this for the first half of the test and did not cause any kind of load shedding. Once another tenant increased its request rate halfway through the test, it caused resource contention and the queue timeouts began shedding the blue tenant’s load. Compare this with the same test, but with a simple FIFO queue on the server. This caused all three tenants to begin to shed load and experience queuing delays.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*_UoUShSrdCG5R6Ln" /><figcaption>In the absence of a WFQ, all tenants are throttled.</figcaption></figure><h3>Final Thoughts</h3><p>Hopefully this was an interesting introduction to the idea of tenant-isolated load shedding. There are shortcomings to using a WFQ I didn’t mention. For instance, memory utilization which scales linearly with the number of tenants is a real concern for some workloads. If the number of tenants in the system is unbounded, there is a risk of memory exhaustion. Also, the devil is in the implementation details of the request scheduler, which I didn’t say much about. Many of the shortcomings are mitigated by WFQ variants such as the <a href="https://github.com/facebook/fbthrift/commit/59f5145e2a79740ecab3445ee21b8280276ef51d">stochastic fair queue (SFQ)</a>, which warrants its own article.</p><p>Thanks for reading! Let me know if this was interesting and if there’s interest in a deeper dive into anything I’ve covered.</p><p><em>Special thanks to </em><a href="https://www.linkedin.com/in/daleajackson/"><em>Dale Jackson</em></a><em> for his feedback on earlier drafts of the post.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1fe9369383c0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Who gets invited to the party?]]></title>
            <link>https://tonya11en.medium.com/who-gets-invited-to-the-party-246a1ba6849a?source=rss-f738ce546ad7------2</link>
            <guid isPermaLink="false">https://medium.com/p/246a1ba6849a</guid>
            <category><![CDATA[recruiting]]></category>
            <category><![CDATA[unconscious-bias]]></category>
            <category><![CDATA[hiring]]></category>
            <category><![CDATA[silicon-valley]]></category>
            <dc:creator><![CDATA[Tony Allen]]></dc:creator>
            <pubDate>Wed, 22 Jul 2020 20:53:48 GMT</pubDate>
            <atom:updated>2020-07-22T20:53:48.626Z</atom:updated>
            <content:encoded><![CDATA[<p>It should be obvious to everyone at this point that the tech industry has a diversity problem. Lots of folks have written about this, but one of my favorite blog post on the matter is <a href="https://danluu.com/tech-discrimination/">written by Dan Luu</a>. In it, he links to a <a href="https://twitter.com/rogerdickey/status/1268327765905772546">Twitter thread</a> where Roger Dickey expresses his “unpopular opinion” that hiring women/minorities is hard because there is a <a href="https://www.huffpost.com/entry/tech-pipline-problem_n_57f7f15de4b0b6a43031ee34">pipeline problem</a>. Basically, Roger thinks that there are not enough women or people of color graduating from STEM programs, so there aren’t enough of them starting companies to fund or entering the candidate pool to hire. Here’s my favorite response:</p><figure><img alt="There’s a pervasive bias in who the industry hires, refers, and invites to parties…" src="https://cdn-images-1.medium.com/max/1024/1*3oUas5efjh_hCr9vOi5RlA.png" /></figure><p><em>There’s a pervasive bias in who the industry hires, refers, and invites to parties…</em></p><p>Let me tell you a story.</p><p>I used to work for a company (let’s call it Hooli), where recruiters would go on tour to various universities each fall with the hopes of recruiting some shiny new college grads. At some point they were going to colleges in my home state of North Carolina to do the usual: give some presentations, get the students excited about Hooli’s mission, something about #impact and whatnot. One of the colleges on the itinerary was North Carolina A&amp;T, <a href="https://www.ncpedia.org/north-carolina-agricultural-and-tec">a historically black college/university</a>, and a <a href="https://ripplematch.com/journal/article/the-top-hbcus-with-the-best-computer-science-programs-80fd3f5e/">damn good one</a>. Since I was one of only <strong>3</strong> black engineers in the Hooli office and a Carolina Boy, the recruiting team insisted that I accompany them on this leg of the tour. Free trip to NC? Count me in.</p><p>The first recruiting event was for Duke/UNC students and consisted of a 1-hour presentation which covered life at Hooli, various teams that exist, what the interview process is like, how to prepare for the interview, and then a slide containing the recruiter’s contact info. This was then followed by a 1.5 hour break-out session where the students formed small (~5 person) groups and then had a chance to ask a Hooli engineer at their table anything they want over a <strong><em>catered dinner</em></strong><em>. </em>This was also a way for them to make a good impression before we collected all of their resumes, marked which ones seemed the most impressive, and <em>invited half of them to dinner at a fancy restaurant the next evening</em>. Wow, talk about rolling out the red carpet!</p><p>The second recruiting event was the following afternoon at NC A&amp;T. Recruiters <strong>put out the catering leftovers from the previous night </strong>and rushed through a shortened (30 minute) version of the previous night’s presentation. There were no break-out tables, no resume collection, no recruiter contact details... I personally ordered a bunch of pizzas because nobody thought that this was a problem. I was <em>livid</em>. After the pizzas arrived, recruiters handed out some Hooli swag, encouraged everyone to apply, and packed up so that everyone could make the 2-hour drive back to Durham in time for a <em>second</em> dinner with the other group of students.</p><p>Sit with that for a moment.</p><p>The demographics of the first group of students reflected <a href="https://www.wired.com/story/five-years-tech-diversity-reports-little-progress/">pretty much what you’d expect</a> to find in your typical Silicon Valley tech company. Those were the people that received all of the attention and all of the advantages on this trip.</p><ul><li>The Duke/UNC events were in the evening, so nobody had to miss class to attend. Many of the A&amp;T students couldn’t attend the entire event because it was in the <em>middle of the day and they had class</em>.</li><li>The Duke/UNC students had multiple chances to talk with us in small groups. They received more information about the interview process, what to study, and Hooli via the extended presentation. They also had chances to impress us and elaborate on their backgrounds and experience. The A&amp;T students barely got a chance to introduce themselves before Hooli packed up and left for <em>a second dinner</em> with the other group.</li><li>The A&amp;T students were given <strong>leftover food</strong> from the night before. Fuck. What kind of message do you think this sends? Would you feel encouraged to apply for a job or internship if that’s how a company’s recruiters treated you?</li></ul><p>I’m sure that the NC A&amp;T event was just so Hooli could check some “diversity recruitment” box. It’s apparent that they didn’t actually take those students seriously. By showing more attention to the UNC/Duke students and half-assing the event at NC A&amp;T, those A&amp;T students were put at a disadvantage. Why? Did Hooli recruiters think that they wouldn’t pass the hiring bar?</p><p>This is the kind of nonsense women and people of color are going through. No wonder there’s a lack of diversity when the deck is stacked against them like this. Pipeline problem, my ass.</p><p><em>Racism is real and bias is persistent.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=246a1ba6849a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Local Experimentation with Envoy]]></title>
            <link>https://tonya11en.medium.com/local-experimentation-with-envoy-a069317cb66c?source=rss-f738ce546ad7------2</link>
            <guid isPermaLink="false">https://medium.com/p/a069317cb66c</guid>
            <category><![CDATA[envoy-proxy]]></category>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[Tony Allen]]></dc:creator>
            <pubDate>Tue, 14 Jul 2020 22:48:09 GMT</pubDate>
            <atom:updated>2021-09-20T17:57:51.831Z</atom:updated>
            <content:encoded><![CDATA[<p>I recently helped some colleagues debug an <a href="https://github.com/envoyproxy/envoy/issues/11504">issue with the Envoy fault filter</a>. They remarked that I have a powerful local testing setup, so I thought it would be worthwhile to share it with others who would like to do some local experimentation on Envoy. One can do most of the things in this article via Envoy integration tests, but I find this method faster for quick little tests that I want to run and the only way to run non-trivial amounts of traffic through an Envoy process locally.</p><p>The goal here is to spin up an Envoy process on your local Linux (or maybe Mac) machine, send requests through it, and see what it does via print statements and stats (or gdb if you’d prefer). I’ll show off my HTTP/1 workflow for simplicity’s sake. It consists of just 3 parts: an Envoy process, a client, and a server.</p><h3>An Envoy Process</h3><p>This is pretty straightforward. One can build a debug Envoy binary with symbols via the following:</p><pre>bazel build -c dbg //source/exe:envoy-static</pre><p>Just note that you can look up fancier build options in the <a href="http://bazel build //source/exe:envoy-static">developer quick start guide</a> found in the source tree.</p><p>The binary will be located in bazel-bin/source/exe/envoy-staticrelative to the top of the source tree. I like to copy it somewhere so it doesn’t get blown away by subsequent builds.</p><p>I keep a generic Envoy configuration file lying around that is some variation on the following:</p><pre>static_resources:<br>  listeners:<br>  - address:<br>      socket_address:<br>        address: 0.0.0.0<br>        port_value: 9001<br>    filter_chains:<br>    - filters:<br>      - name: envoy.http_connection_manager<br>        typed_config:<br>          &quot;<a href="http://twitter.com/type">@type</a>&quot;: type.googleapis.com/envoy.config.filter.network.http_connection_manager.v2.HttpConnectionManager<br>          codec_type: auto<br>          stat_prefix: ingress_http<br>          route_config:<br>            name: local_route<br>            virtual_hosts:<br>            - name: service<br>              domains:<br>              - &quot;*&quot;<br>              routes:<br>              - match:<br>                  prefix: &quot;/&quot;<br>                route:<br>                  cluster: local_service<br>          http_filters:<br>          - name: envoy.router<br>            typed_config:<br>              &quot;<a href="http://twitter.com/type">@type</a>&quot;: &quot;type.googleapis.com/envoy.config.filter.http.router.v2.Router&quot;<br>              start_child_span: true<br>  clusters:<br>  - name: local_service<br>    connect_timeout: 0.25s<br>    type: strict_dns<br>    lb_policy: LEAST_REQUEST<br>    load_assignment:<br>      cluster_name: local_service<br>      endpoints:<br>      - lb_endpoints:<br>        - endpoint:<br>            address:<br>              socket_address:<br>                address: 127.0.0.1<br>                port_value: 9002<br>admin:<br>  access_log_path: &quot;/dev/null&quot;<br>  address:<br>    socket_address:<br>      address: 0.0.0.0<br>      port_value: 8081</pre><p>That base config will:</p><ul><li>Listen on port 9001. You send requests there.</li><li>Route everything to your local host on port 9002.</li><li>Allow for admin stuff on port 8081. This is where you’d query stats and do <a href="https://www.envoyproxy.io/docs/envoy/latest/operations/admin">lots of other useful things</a>.</li></ul><p>The greatest hits already exist in that base config, but you can add anything else you find useful on top of it. Think more network/HTTP filters, more endpoints (so you can load balance across multiple “servers”), circuit breaking, outlier detection, etc.</p><p>So now you can spin up an Envoy process by feeding it the config file. To keep things simpler and more predictable, I also like to spin up a single worker thread and just let the logs go to stderr by default:</p><pre>./envoy -c envoy_config.yaml --concurrency 1</pre><p>Don’t forget to restart the process after each config file change!</p><h3>A Local HTTP Server and Client</h3><p>I use different tools depending on my goals. To run reproducible load tests I use <a href="https://github.com/tonya11en/bufferbloater">bufferbloater,</a> but when I just want to send single requests with specific payloads I use the <a href="https://docs.python.org/2/library/simplehttpserver.html">Python SimpleHttpServer</a> and <a href="https://linux.die.net/man/1/curl">curl</a>.</p><p>For example, to send a request with specific headers through an Envoy with the basic config we saw earlier, I’d spin up a local HTTP server via:</p><pre>python3 -m http.server 9002</pre><p>and curl requests with a command that looks like:</p><pre>curl -i -H &quot;x-some-header: some_value&quot; \<br>        -H &quot;x-another-header: another_value&quot; \<br>        localhost:9001</pre><p>This would cause a request to be sent from curl to the Envoy process listening on port 9001. The request would be routed to the HTTP server listening on port 9002 and it would reply through the Envoy process.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ujG5aIoffnKYWakckF_Y8g.png" /><figcaption>An Envoy process (top), a Python HTTP server (middle), and curl (bottom).</figcaption></figure><p>That’s all, folks!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a069317cb66c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Examining Load Balancing Algorithms with Envoy]]></title>
            <link>https://medium.com/envoyproxy/examining-load-balancing-algorithms-with-envoy-1be643ea121c?source=rss-f738ce546ad7------2</link>
            <guid isPermaLink="false">https://medium.com/p/1be643ea121c</guid>
            <category><![CDATA[envoy-proxy]]></category>
            <dc:creator><![CDATA[Tony Allen]]></dc:creator>
            <pubDate>Wed, 13 May 2020 17:01:01 GMT</pubDate>
            <atom:updated>2020-05-13T21:05:24.383Z</atom:updated>
            <content:encoded><![CDATA[<p>If you deal with networked systems you probably care a lot about latency. It’s also likely that you’ll be faced with a decision of which load balancing algorithm to use when fronting a fleet of servers. It can be extremely helpful when making these decisions to build an intuition for what behaviors to expect in different load balancer configurations, so that you can minimize latency in your environment without any surprising behaviors.</p><p>Hopefully we can all agree that a load balancer’s job is to distribute requests across some fleet of servers (occasionally referred to as <a href="https://www.envoyproxy.io/"><em>upstreams</em></a><em> </em>to Envoy folks). The goal is to maximize the efficiency of servicing those requests. Efficiency can mean optimal CPU utilization for the server or minimal wait time for the sender (latency). Typically, where you find latency, you will also find there is a <a href="https://en.wikipedia.org/wiki/Little%27s_law">queue forming somewhere</a>, so I’ll proceed with the goal of investigating load balancer schemes that minimize queueing on the upstreams.</p><p>I’ll present a (non-exhaustive) overview of the various load balancing algorithms found in <a href="https://www.envoyproxy.io/docs/envoy/latest/">Envoy</a> with some simulations to showcase their behaviors. There’s a lot to go over, so I’ll be keeping this as simple and focused as I can. There will be no talk of <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/http/http_routing.html#arch-overview-http-routing-retry">retry policies</a>, <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/circuit_breaking#arch-overview-circuit-break">circuit breaking</a>, <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/panic_threshold.html">panic routing</a>, <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/priority.html">load balancer priorities</a>, and the like or their (non-trivial) effects on load balancing. The effects of those features are non-trivial, so just know that they play a big part in real (not simulated) workloads!</p><h3>Simulating Traffic</h3><p>Each simulation that follows will send HTTP requests with some fixed RPS through an Envoy process to a fleet of 10 HTTP servers. The servers simply accept a request, sleep for some amount of time (we’ll call this a “service time”), and reply with a 200 status.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/0*Yoa9pDy9-PoClpKr" /><figcaption>General topology of the simulations.</figcaption></figure><p>If a specific server is juggling multiple requests simultaneously, it will repeatedly choose one at random and sleep for 100us until the “service time” for that request is met as a hand-wavy approximation of the effects of request concurrency on latency. As a queue forms in each server and it services multiple requests, the latency of each response will increase. Keep in mind that if we did not have each request sleep for identical service times and had an actual distribution of latencies (as we would in real life) queueing on the servers would impact our tail latencies disproportionately.</p><p>The specifics of latency and RPS numbers will be omitted, because we care about the queues that form and the relationship between the queues and the load balancing algorithms. Since I’m controlling the RPS <strong>and </strong>the request latency, only the <a href="https://en.wikipedia.org/wiki/Little%27s_law">relationship between the two</a> matters for the queuing behavior.</p><p>Now let’s get to the good stuff- load balancers!</p><h3>Random Load Balancing</h3><p>The simplest load balancer supported by Envoy is the <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancers.html?highlight=ring%20hash#random">random load balancer</a>, where node/endpoint is chosen via a uniform random selection.</p><p>Uniform random selection is the simplest way to distribute requests to a set of upstream nodes and also the easiest to implement. It’s fair to expect a pool of 10 nodes subjected to a uniform random selection algorithm to have a flat distribution at the end of 1 million selections:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*HbVkSzsyht1vW6eK" /><figcaption>Histogram of node selections using uniform random selection. Looks pretty uniform!</figcaption></figure><blockquote><em>An even distribution of requests! This is what we want… right?</em></blockquote><p>In practice, things are not this simple. Let’s take a look at a scenario where these 10 nodes are given requests distributed via random load balancing.</p><p>Below, we have results where each line represents a different endpoint and the Y-axis is the number of requests outstanding for that endpoint at a particular point in time during the experiment:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*tmwuB4U9-03mVWCK" /><figcaption>The number of active requests per-node for random LB.</figcaption></figure><p>The specific number of active requests for each endpoint is unimportant, but the distribution of requests among the endpoints is worth noting. Some nodes have an order of magnitude more outstanding requests than others at a particular point in time! It appears that even though the asymptotic behavior of uniform random selection yields a uniform distribution, at any point in time an endpoint could be overburdened by too many requests. This could result in increased latency, the formation of a request queue in the service, and eventually cascading failures.</p><p>We can combat this behavior by ensuring each node receives a request in a predictable manner, so let’s introduce round-robin selection.</p><h3>Round Robin Load Balancing</h3><p>Envoy’s round-robin (or “next-in-loop”) load balancing policy will sequentially rotate through each upstream node. This has the benefit of providing us with a predictable distribution of requests not only asymptotically, as in the case of uniform random selection, but also at any point in time. Running the same test, but using a round-robin load balancer policy in the config yields a much tighter distribution of active requests among the upstream nodes compared to the random selection experiment above:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*sB4bX_GJ636GlQz1" /><figcaption>The number of active requests per-node for round-robin LB.</figcaption></figure><p>For the exact same test, let’s also compare the request counts on each node when using round-robin vs. random load balancing. We’ll define a metric called <em>request drift</em> by looking at the gap between the node that received the most requests and the node that received the least requests at each point in time:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*0K9-GCQTo61rNeBo" /><figcaption>The difference between the node with the highest number of requests active and the node with the lowest number of requests active.</figcaption></figure><blockquote><em>It’s settled! Use round-robin load balancing for an even distribution of requests with minimal active request drift! Simple! Elegant!</em></blockquote><p>Not quite!</p><p>Up to this point, all of the upstream nodes have been homogeneous, with the same latency profiles. What if some subset of the upstreams are extremely capable nodes and they go under-utilized or some of the upstreams are potato computers? Below, we have the same round-robin experiment/configuration, but now we have 3 lightning fast nodes completing requests virtually instantaneously and 3 potato nodes completing requests 25% slower than before. As you can see, there are 3 obvious groupings of active request counts:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*N5FiiK2j_KJKtq6r" /><figcaption>Active request counts for high-latency/weaker nodes (A), standard nodes we’re familiar with from previous simulations (B), and blazing-fast nodes (C).</figcaption></figure><p>The issue we have now is that the slower (potato) nodes in group A that are juggling too many requests at a time and experiencing elevated latencies, while the fastest nodes in group C are being under-utilized. Notice that the request queue is growing for the slower nodes (a cascading failure waiting to happen) and there is essentially no queue for the fast nodes.</p><blockquote>It would be nice if the load balancer could take into account the number of outstanding requests destined for each node and bias its forwarding decisions based on the information.</blockquote><p>Conveniently, Envoy has a load balancer that does this!</p><h3>Least Request Load Balancing</h3><p>Envoy’s least request load balancer takes into account the number of outstanding requests destined for each node and biases its forwarding decisions based on the active request count. Our problem of over/underutilized nodes is encountered when discussing the round-robin approach would be resolved by doing this, but the implementation details matter here- what exactly does it mean to “bias” node selections?</p><p>Consider some weight assigned to a node that is inversely proportional to the number of outstanding requests the node has. If we have 100 nodes with weights in the range [0,100), we have a few different options for biasing our selections based on the weights.</p><h3>Weight Proportional Selection</h3><p>The most obvious method of performing weighted selections is simply to have the selection probability of an object be proportional to the weight, similar to spinning a roulette wheel. This is also known as <a href="https://en.wikipedia.org/wiki/Fitness_proportionate_selection">fitness proportionate selection</a>. Simulating this, we can see that the proportions of the selection counts converge on the weights of each object in the selection pool (x-axis is the object’s weight):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*wJ49nFz7CMvJoYi9" /><figcaption>Histogram of selection counts at different points in time for weight-proportional selection. Each object weight on the x-axis represents a separate object with that corresponding weight.</figcaption></figure><blockquote><em>What’s wrong this time…</em></blockquote><p>Predictably, there’s a wrench in the gears. Selection probabilities that are proportional to the object weights can be a double-edged sword. This selection method is great because our load balancer will send more traffic to the nodes with less requests more aggressively and back off more aggressively. However, this can be the source of problems in a scenario where all nodes in the load balancing pool are redlining and we insert a new node into the pool (as you’d see in a scale-up event). It’s not quite the canonical <a href="https://en.wikipedia.org/wiki/Thundering_herd_problem">thundering herd problem</a> some folks are familiar with, but it definitely falls into the same category.</p><p>This behavior can be observed if we have 9 nodes with weights in the range [0,9) and a single node with a weight of ~1000:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*sLguir2l7wGCsRVQ" /><figcaption>Histogram of selection counts at different points in time for weight-proportional selection.</figcaption></figure><p>You’ll notice that the single host with a high weight is overwhelmingly preferred compared to the others. If you squint, you might even see the other 9 hosts! Some might think that this doesn’t matter, since it would result in an immediate queue on the 10th node and the weight would be adjusted accordingly- they would be correct. However, you should keep in mind that these decisions are made across many different load balancers, so the node would receive a flood of traffic from <em>everyone</em>.</p><p>We need a biased selection algorithm that’s resilient to this herding behavior, yet also gives priority to the higher weight hosts. Conveniently, Envoy has implemented one in the least request load balancer.</p><h3>The Power of Two Choices</h3><p>Suppose we just choose two nodes at random and select the one with a higher weight. This surprising, simple, and elegant method of biased selection is commonly referred to as the “power of two choices (P2C),” coined by <a href="https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.pdf">Michael Mitzenmacher’s 2001 dissertation</a>. However, contrary to much of the load balancing documentation that references this selection method, we should be calling out Azar et. al. for <a href="https://homes.cs.washington.edu/~karlin/papers/AzarBKU99.pdf">publishing seminal work on this</a> in 1999!</p><p>Let’s take a look at the two previous simulations, but now using P2C selection. You’ll notice that we still bias towards the higher weight nodes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*bKHt-B9zec_6ULge" /><figcaption>Histogram of selection counts at different points in time for P2C selection. Each object weight on the x-axis represents a separate object with that corresponding weight.</figcaption></figure><p>More importantly, P2C doesn’t exhibit the herding behavior observed using weight proportional selection! You don’t have to squint to see the other objects in the pool:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*qyNjZjUC0mqUnB8i" /><figcaption>Histogram of selection counts at different points in time for P2C selection.</figcaption></figure><p>For the application of Envoy’s least request load balancer, this is along the lines of what we would want. We simply want to send more requests to nodes with less active requests and rely on the increased RPS to those nodes to create queues that are in line with the other nodes in the cluster. In addition, the time complexity of P2C is constant as opposed to the linear (or logarithmic, depending on the fanciness of your implementation) time complexity of weight proportional selection.</p><p>Envoy’s implementation of P2C allows for a configurable number of choices, so in theory, we would be able to have the load balancer perform a full sweep of the nodes and select the one with the least amount of requests every time. While there are <a href="https://github.com/envoyproxy/envoy/issues/4481">some applications</a> where this would be useful, one of the key insights of the Azar et. al. paper is that there is little additional benefit to performing more than two choices. We would also creep closer to herding behavior with each additional selection we perform, so Envoy’s default configuration of the least request load balancer performs two choices.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*w6gnMKhnmJIJ5JiI" /><figcaption>Active request count for high-latency nodes, normal nodes, and blazing fast nodes.</figcaption></figure><p>What a difference! We have a much more even distribution of active requests across different nodes with different latency characteristics. Where round robin sends the same number of requests to all nodes, you’ll see that the least request load balancer is sending different amounts of requests to the different groups of nodes. This is all based purely on the number of active requests on each node and attempting to keep them all in the same range:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*_2Q9rN1XeYWt4DzZ" /><figcaption>The number of requests received by each node.</figcaption></figure><blockquote>…one load balancer to rule them all?</blockquote><p>If your goal is to have consistent latencies across all nodes in your clusters when load balancing requests, it’s pretty safe to reach for Envoy’s least request load balancer. That’s not to say it’s <em>always</em> a good idea- there’s no magic bullet here. Scenarios exist where least request load balancing is not effective. In this article, I present a simplified client/server simulation environment with minimal additional Envoy configuration and uncomplicated server behavior. Problems that arise from these additional complexities never had a chance to manifest themselves like the queuing problems did with random and round-robin load balancing.</p><blockquote>What problems?!</blockquote><p>What if some applications care more about even distribution of requests over predictable latencies? What about request stickiness concerns or specific behaviors when doing weighted load balancing? Least request load balancing won’t always fit the bill in these cases (especially when considering more complicated interactions with <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/http/http_routing.html#arch-overview-http-routing-retry">retry policies</a>, <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/circuit_breaking#arch-overview-circuit-break">circuit breaking</a>, <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/panic_threshold.html">panic routing</a>, <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/priority.html">load balancer priorities</a>, etc.). We should also call out that if there are a very, very large number of clients slowly trickling requests to a small number of upstreams, there wouldn’t be enough information about load on the upstreams to select them properly- we’d devolve into random load balancing!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/416/1*gsTAIl8uElAzjIOBoeKWXQ.png" /><figcaption>A reader reacts.</figcaption></figure><p>I‘ll admit I presented a pathological example, but an environment with those characteristics wouldn’t raise too many eyebrows. One can even imagine a scenario where a single bad node fails requests faster than other nodes would be able to service it, so the least request load balancer would favor that bad node and destroy your success rate (in practice, <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/outlier">outlier detection</a> would stop this one in its tracks).</p><h3>Final Thoughts</h3><p>Hopefully this article has been helpful and provided some insight into basic behaviors and motivations for using a few of Envoy’s configurable load balancers. There are other load balancers that were not discussed here, so I’d recommend taking a look at <a href="https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancing">the docs</a> to see what’s available. I’d also encourage you to jump in the Envoy <a href="https://envoyslack.cncf.io/">Slack channel</a>, <a href="https://groups.google.com/forum/#!forum/envoy-users">Google Group</a>, and <a href="https://github.com/envoyproxy/envoy">Github</a> to learn more about this awesome project. The community is full of very smart, very friendly folks!</p><p><strong>HUGE</strong> thanks to my eagle-eyed colleagues who helped edit and review this article: <em>Snow Pettersen, Lita Cho, Tom Wanielista, Ryan Cox, Daniel Hochman, and Matt Klein.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1be643ea121c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/envoyproxy/examining-load-balancing-algorithms-with-envoy-1be643ea121c">Examining Load Balancing Algorithms with Envoy</a> was originally published in <a href="https://medium.com/envoyproxy">Envoy Proxy</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[It Matters How You Initialize C Arrays]]></title>
            <link>https://tonya11en.medium.com/it-matters-how-you-initialize-c-arrays-f5181b91e67?source=rss-f738ce546ad7------2</link>
            <guid isPermaLink="false">https://medium.com/p/f5181b91e67</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[gdb]]></category>
            <category><![CDATA[debugging]]></category>
            <category><![CDATA[c]]></category>
            <dc:creator><![CDATA[Tony Allen]]></dc:creator>
            <pubDate>Thu, 19 Sep 2019 06:37:36 GMT</pubDate>
            <atom:updated>2019-09-19T06:37:36.660Z</atom:updated>
            <content:encoded><![CDATA[<h3>It Matters How You Initialize C-Strings</h3><p>I’ll start this off by saying I’m not a C developer. I mostly use C++. However, this did not stop me from zealously offering to help a friend debug his <a href="https://cs50.harvard.edu/college/">CS50</a> homework. My beard should be grey enough for that…</p><p>The problem can be distilled down to something like this:</p><pre>int main() {<br> char *foo = “lol, sup”;<br> foo[0] = ‘x’; <br> return 0;<br>}</pre><p>Seems straightforward. However, I was a bit vexed to find that it exploded:</p><pre>[tallen@legion tmp]$ ./test<br>Segmentation fault (core dumped)</pre><p>I’ve been coddled by std::string and forgotten how C-strings work. Why can’t we modify the string? Queue the 90s hacker montage.</p><p>We rip the binary open and learn its secrets. Using objdump --full-contents, we can see all non-empty sections of the object file. Here’s something interesting:</p><pre>Contents of section .rodata:<br> 2000 01000200 6c6f6c2c 20737570 00        ....lol, sup.</pre><p>The string literal is right there in the read-only data segment. But that’s only for static constants! Wait a minute… let’s hack something up to figure out where that variable sits in relation to the heap.</p><p>Using sbrk we can get some insight to where the heap pointer sits. Maybe. On some platforms. Whatever, it works on my computer.</p><pre>#include &lt;unistd.h&gt;</pre><pre>int main() {<br> void *heap = sbrk(0);<br> char *foo = “lol, sup”;<br> foo[0] = ‘x’;<br> return 0;<br>}</pre><p>I put on my robe and wizard hat, then open the binary in gdb .</p><pre>(gdb) run<br>Starting program: /tmp/test</pre><pre>Program received signal SIGSEGV, Segmentation fault.<br>0x000055555555516d in main () at test.c:6<br>6 foo[0] = ‘x’;<br>(gdb) p heap<br>$1 = (void *) 0x555555559000<br>(gdb) p foo<br>$2 = 0x555555556004 “lol, sup”<br>(gdb)</pre><p>The heap grows up, so foo is below the heap, it’s a pointer to the read-only data section! How? Maybe if I check StackOverflow…</p><p><a href="https://stackoverflow.com/questions/1011455/is-it-possible-to-modify-a-string-of-char-in-c">Oh, I guess that makes sense.</a></p><pre>#include &lt;unistd.h&gt;</pre><pre>int main() {<br> void *heap = sbrk(0);<br> char foo[] = “lol, sup”; <br> foo[0] = ‘x’;<br> return 0;<br>}</pre><p>I sit in my high-chair and tear open a lunchable, then open the binary in gdb.</p><pre>(gdb) b 6<br>Breakpoint 1 at 0x118b: file test.c, line 6.<br>(gdb) run<br>Starting program: /tmp/test</pre><pre>Breakpoint 1, main () at test.c:6<br>6 foo[0] = ‘x’;<br>(gdb) p heap<br>$1 = (void *) 0x555555559000<br>(gdb) p &amp;foo<br>$2 = (char (*)[9]) 0x7fffffffdfb8</pre><p>Huh…</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f5181b91e67" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Technically Speaking: We Can do Better]]></title>
            <link>https://tonya11en.medium.com/technically-speaking-we-can-do-better-1afc52d3b5a0?source=rss-f738ce546ad7------2</link>
            <guid isPermaLink="false">https://medium.com/p/1afc52d3b5a0</guid>
            <category><![CDATA[technical-support]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[communication]]></category>
            <category><![CDATA[debugging]]></category>
            <category><![CDATA[productivity]]></category>
            <dc:creator><![CDATA[Tony Allen]]></dc:creator>
            <pubDate>Sun, 21 Jul 2019 00:08:04 GMT</pubDate>
            <atom:updated>2019-12-08T02:49:44.708Z</atom:updated>
            <content:encoded><![CDATA[<h3>Technically Speaking: We Can Do Better</h3><p>As engineers, we place a lot of emphasis on the efficiency of the things we build. That’s great, really, there’s nothing like reading through highly efficient code and knowing that our precious CPU cycles are not going to waste. However, I’ve observed that on the whole, we don’t approach our technical communications with the same regard. Support-related communication seems to suffer from this the most. I’m not claiming to be some expert on communication within large engineering organizations, but I do think I’ve given this topic more thought than the median engineer that’s shoveling coal in the fire.</p><p>The cross-team support model of the organizations I’ve been a part of seem to bias toward engaging people synchronously via Slack. While this model might work fine for smaller engineering orgs, as they grow larger (around the time I show up) it’s unscalable and the mental burden of these engagements is too much if lots of teams need to interact with your service. One can spend a great deal of time massaging every question into something actionable via follow-up questions.</p><p>I don’t think anyone would argue against removing friction from support-related engagements. After all, efficient engagements between teams allows everyone to spend less time on back-and-forth clarifications and more time on what we do best: building things.</p><h3>Engaging other teams</h3><p>When engaging another engineering team (we’ll call them our partners) for support, we typically need either information, a design or code review of some kind, or help with some engineering problem we are facing. What we want in these engagements is to get whatever we need from our partners as quickly as possible and to <em>minimize the mental burden of the engagement</em>. Sometimes the desire for immediate help eclipses the desire to reduce the mental burden on our partners, so our initial engagement looks something like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/0*TRE8OV66iGirGD5_" /><figcaption>An engineer asks for assistance.</figcaption></figure><p>Technically correct, but not exactly actionable. We can do better- I think it’s possible to get assistance quickly, while also reducing the burden of the inevitable follow-up questions on our partners.</p><h3>A Contrived Example</h3><p>When reaching out for help debugging an issue, we should seek to give as much information as possible in our initial engagement. This reduces the need for multiple round-trips in the form of follow-up questions. Here is an extreme example of a sub-optimal initial engagement:</p><pre><em>DankMemeService has high CPU:</em></pre><pre><em>&lt;link to some dashboard&gt;</em></pre><p>Cool story. Your partner will immediately have questions that in one way or another attempt to answer ​<em>what, where, when, the extent, the expected behavior, the observed behavior, and what steps you have taken to debug.</em>​ Reframe the question to include all of this information. Remember, we’re trying to reduce the mental burden on your partner, and one way to do that is to make your question immediately actionable.</p><p>Let’s see what other info we can provide:</p><p><strong>What: <br></strong>DankMemeService</p><p><strong>Where: <br></strong>Instances in the staging environment.</p><p><strong>When: <br></strong>From 12:05pm 03/14/2019 to present time.</p><p><strong>The extent: <br></strong>Every host in the staging environment is affected.</p><p><strong>Expected behavior: <br></strong>The instances should hover at ~25% CPU utilization.</p><p><strong>Observed behavior: <br></strong>The instances abruptly spiked to 100% CPU utilization and stayed there.</p><p><strong>Steps taken:<br></strong>Ran ‘top’ and found that DankMemeService is redlining CPU. When looking at CPU traces, something seems to be happening in InteractWithCatGifService(). Peeked in CatGifService and DankMemeService runbooks and there is no entry for this scenario.</p><p>We can now morph our sub-optimal and not-really-actionable statement into something… <em>wonderful</em>:</p><pre>All staging instances of DankMemeService abruptly spiked CPU to 100% utilization at 12:05pm 03/14/2019 and has continued this behavior ever since. This service’s steady-state CPU utilization typically hovers at ~25%. I looked at CPU traces on the DankMemeService process and found that something fishy is happening when interacting with CatGifService. I peeked in both the CatGifService and DankMemeService runbooks and there is no entry for this behavior. Can somebody assist in debugging this from the CatGifService side? See graphs X, Y, and Z:</pre><pre>&lt;relevant links&gt;</pre><p>Look at that! It’s clear why there’s a problem; there’s a deviation from expected behavior. We know why the partner is being engaged and what is needed from the partner. We even know exactly what graphs they should look at to see evidence of the problem.</p><h3>TL; DR</h3><p>Your initial engagement should contain detailed answers to what, where, when, extent, expected behavior, observed behavior, and steps taken so far. Providing this information will reduce the need for follow-up questions, allow your partners to begin helping right away, and make engineering orgs more efficient.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1afc52d3b5a0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Counting Bloom Filter in C++]]></title>
            <link>https://medium.com/hackernoon/counting-bloom-filter-in-c-9672ec25b3ec?source=rss-f738ce546ad7------2</link>
            <guid isPermaLink="false">https://medium.com/p/9672ec25b3ec</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Tony Allen]]></dc:creator>
            <pubDate>Wed, 05 Jul 2017 09:43:03 GMT</pubDate>
            <atom:updated>2019-04-27T10:25:17.991Z</atom:updated>
            <content:encoded><![CDATA[<p>I recently ran across <a href="http://blog.michaelschmatz.com/2016/04/11/how-to-write-a-bloom-filter-cpp/">this bloom filter post by Michael Schmatz</a> and it inspired me to write about a neat variation on <a href="https://en.wikipedia.org/wiki/Bloom_filter">the bloom filter</a> that I’ve found useful in my work. Quick refresher: a bloom filter is a probabilistic <a href="https://hackernoon.com/tagged/data-structure">data structure</a> that tests if an element is <a href="https://hackernoon.com/tagged/potentially">potentially</a> in a set. False positives are possible when testing if an element is in the set, but negatives mean an element is definitely not in the set. Got it? Cool.</p><p>A counting filter is essentially a bloom filter that’s had its single-bit booleans replaced with n-bit integers. This makes the filter take up much more space than a standard bloom filter, but in return we get an upper-bound count for insertions of a particular element and can remove elements from the filter. Though removal of elements can be pretty neat, we expose ourselves to the possibility of false negatives if we remove an element that was never inserted into the counting filter. Just be careful with that- <a href="https://pdfs.semanticscholar.org/b0cd/0a280b1c54fb218c1ca37b8f77b634fb6f45.pdf">Deke Guo has more to say about this than I do.</a></p><h4>Implementation</h4><p>I designed my counting filter class with the following interface:</p><pre>// Adds an element to the counting filter.<br>void Add(const T *key, int size = sizeof(T));</pre><pre>// Removes an element from the counting filter.<br>void Remove(const T *key, int size = sizeof(T));</pre><pre>// Test whether the element has been added. If false, the element <br>// is definitely not in the set. If true, the element could be in<br>// the set or it is a false positive as described above.<br>bool MaybeContains(const T *key, int size = sizeof(T)) const;</pre><pre>// Get the upper bound on the number of times an element could<br>// have been inserted into the counting filter.<br>int CountUpperBound(const T *key, int size = sizeof(T)) const;</pre><p>The counters are stored in a std::vector like so:</p><pre>std::vector&lt;uint8&gt; counters_;</pre><p>I initially implemented this with the counters stored in a std::array object. Using the array, the filter benchmarked at ~1.35x the runtime of a std::unordered_set insertion on my machine. With the vector, it’s benchmarking at ~2.05x std::unordered_set insertions. I settled on the slower option because the code looks cleaner and it allows us to specify the size and number of hashes in the bloom filter during instantiation without needing to use template arguments (std::arrays must have a size known at compile time).</p><p>The constructor is pretty simple. Simply an up-front allocation of the counters_ vector via a call to resize() and perhaps just fill the vector with zeros, so I should start with showing how I use hashes to get index pairs:</p><pre>template &lt;typename T, int64_t kSize, int32_t kNumHashPairs&gt;<br>void CountingFilter&lt;T, kSize, kNumHashPairs&gt;::IdxFromKey(<br>  const T *key,<br>  const int size,<br>  const uint32_t seed,<br>  int64_t *idx1,<br>  int64_t *idx2) const {<br><br>  array&lt;uint64_t, 2&gt; results;<br>  MurmurHash3_x64_128(key, size, seed, results.data());<br>  *idx1 = results[0] % counters_.size();<br>  *idx2 = results[1] % counters_.size();<br>  assert(*idx1 &lt; counters_.size());<br>  assert(*idx2 &lt; counters_.size());<br>}</pre><p>Note that this limits the implementation to even-numbers of hashes, but I like the fact that we’re getting a 2-for-1 deal with the 64-bit hashes.</p><p>The Add() function has to account for the possibility of the count potentially exceeding the maximum counter value. In this case, there’s not much we can do except avoid an increment and flag the filter data as potentially erroneous.</p><pre>template &lt;typename T, int64_t kSize, int32_t kNumHashPairs&gt;<br>void CountingFilter&lt;T, kSize, kNumHashPairs&gt;::Add(<br>  const T *key, const int size) {</pre><pre>for (int32_t xx = 0; xx &lt; kNumHashPairs; ++xx) {<br>    int64_t idx1, idx2;<br>    IdxFromKey(key, size, xx, &amp;idx1, &amp;idx2);<br>    // It&#39;s possible that the count can exceed the maximum uint8<br>    // value, so we&#39;ll just leave it be. After many removals,<br>    // this could result in a false negative, but this is very<br>    // unlikely. Let&#39;s just assert for this case.<br>    assert(counters_[idx1] &lt;= numeric_limits&lt;uint8_t&gt;::max());<br>    assert(counters_[idx2] &lt;= numeric_limits&lt;uint8_t&gt;::max());<br>    counters_[idx1] += 1;<br>    counters_[idx2] += 1;<br>  }<br>  ++num_insertions_;<br>}</pre><p>Removal is much simpler since we just decrement the counters. In this case, it’s up to you whether to add an assertion that the counters is nonzero prior to decrementing the counters:</p><pre>template &lt;typename T, int64_t kSize, int32_t kNumHashPairs&gt;<br>void CountingFilter&lt;T, kSize, kNumHashPairs&gt;::Remove(<br>  const T *key, const int size) {<br><br>  for (int32_t xx = 0; xx &lt; kNumHashPairs; ++xx) {<br>    int64_t idx1, idx2;<br>    IdxFromKey(key, size, xx, &amp;idx1, &amp;idx2);<br>    assert(counters_[idx1] &gt; 0);<br>    assert(counters_[idx2] &gt; 0);<br>    counters_[idx1] -= 1;<br>    counters_[idx2] -= 1;<br>  }<br>  --num_insertions_;<br>}</pre><p>Checking whether elements exist in the filter is just a check for all counters to be nonzero. Getting an upper-bound on the number of insertions an element has had into the filter requires us to just find the minimum counter. This is an upper-bound because collisions can potentially throw our calculation off.</p><pre>template &lt;typename T, int64_t kSize, int32_t kNumHashPairs&gt;<br>int CountingFilter&lt;T, kSize, kNumHashPairs&gt;::CountUpperBound(<br>  const T *key, const int size) const {<br><br>  int count_ub = numeric_limits&lt;uint8_t&gt;::max() + 1;<br><br>  for (int32_t xx = 0; xx &lt; kNumHashPairs; ++xx) {<br>    int64_t idx1, idx2;<br>    IdxFromKey(key, size, xx, &amp;idx1, &amp;idx2);<br>    count_ub = min(static_cast&lt;int&gt;(counters_[idx1]), count_ub);<br>    count_ub = min(static_cast&lt;int&gt;(counters_[idx2]), count_ub);<br>  }<br>  return count_ub;<br>}</pre><h4>Wrapping up</h4><p>This data structure is a fun variation on a vanilla bloom filter. My implementation is currently benchmarking at ~2.05x the insertion time of a pre-reserved std::unordered_set. I’ve mainly used it to be pickier about cache insertions when the working set of data is very large, but I’d love to find more applications for this.</p><blockquote><a href="http://bit.ly/Hackernoon">Hacker Noon</a> is how hackers start their afternoons. We’re a part of the <a href="http://bit.ly/atAMIatAMI">@AMI</a>family. We are now <a href="http://bit.ly/hackernoonsubmission">accepting submissions</a> and happy to <a href="/service/mailto:partners@amipublications.com">discuss advertising &amp; sponsorship</a> opportunities.</blockquote><blockquote>To learn more, <a href="https://goo.gl/4ofytp">read our about page</a>, <a href="http://bit.ly/HackernoonFB">like/message us on Facebook</a>, or simply, <a href="https://goo.gl/k7XYbx">tweet/DM @HackerNoon.</a></blockquote><blockquote>If you enjoyed this story, we recommend reading our <a href="http://bit.ly/hackernoonlatestt">latest tech stories</a> and <a href="https://hackernoon.com/trending">trending tech stories</a>. Until next time, don’t take the realities of the world for granted!</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fupscri.be%2Fdde502%3Fas_embed%3Dtrue&amp;dntp=1&amp;url=https%3A%2F%2Fupscri.be%2Fhackernoon%2F&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=upscri" width="800" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/3c851dac986ab6dbb2d1aaa91205a8eb/href">https://medium.com/media/3c851dac986ab6dbb2d1aaa91205a8eb/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9672ec25b3ec" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/counting-bloom-filter-in-c-9672ec25b3ec">Counting Bloom Filter in C++</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>