Forem: Bharghava Varun Ayada

Context Cancellation in Go

Bharghava Varun Ayada — Tue, 04 Jan 2022 08:28:28 +0000

Originally published at ayada.dev

In Go, we can use context to send cancellation signals to goroutines that is doing some work. The Done method in context returns a channel that acts as a cancellation signal to goroutines using the given context. When the channel is closed, it indicates to the goroutines that they should stop the work they are doing. We can use WithCancel context function to obtain a new context along with the cancel function that can be used to close the channel.

Here we have two examples of WithCancel function. In the first example, we will run two functions, runTicker and anotherTicker, in separate goroutines. The ticker functions periodically prints a string to the console and it will run indefinitely. Only way to stop the goroutines is to cancel the context. In the ticker functions, we wait for the channel returned by ctx.Done() to be closed by running the cancelFunc function that WithCancel provides.


package main

import (
    "context"
    "fmt"
    "sync"
    "time"
)

func exampleOne() {
    ctx, cancelFunc := context.WithCancel(context.Background())

    wg := new(sync.WaitGroup)
    wg.Add(2) // we will start two ticker goroutines.

    go func() {
        // start the two ticker functions in separate goroutines.
        go runTicker(ctx, wg)
        go anotherTicker(ctx, wg)

        // sleep for 10s for ticker functions to print something to the console.
        time.Sleep(10 * time.Second)

        // after 10s, cancel the context.
        cancelFunc()
    }()

    // wait for the ticker functions to complete.
    wg.Wait()
}

func anotherTicker(ctx context.Context, wg *sync.WaitGroup) {
    defer wg.Done()
    for {
        select {
        case <-time.After(2 * time.Second):
            sleepContext(ctx, time.Minute) // sleep here indicates some work.
            fmt.Println(time.Now(), "another ticker executed")
        case <-ctx.Done(): // will execute if cancel func is called.
            return
        }
    }

}

func runTicker(ctx context.Context, wg *sync.WaitGroup) {
    defer wg.Done()
    for {
        select {
        case <-time.After(2 * time.Second):
            fmt.Println(time.Now(), "ticker executed")
        case <-ctx.Done(): // will execute if cancel func is called.
            return
        }
    }
}

// a sleep function that honors context cancellation.
func sleepContext(ctx context.Context, delay time.Duration) {
    select {
    case <-ctx.Done(): // will execute if cancel func is called.
    case <-time.After(delay):
    }
}

In the second example, we will see that once the context is cancelled, even though execute function is run multiple times, it will return immediately without any sleep. This is because the channel returned by ctx.Done() in sleepContext function is already closed.


package main

import (
    "context"
    "fmt"
    "time"
)

func exampleTwo() {
    ctx, cancelFunc := context.WithCancel(context.Background())
    cancelFunc() // cancel the context immediately.

    for i := 0; i < 5; i++ {
        execute(ctx) // execute function 5 times, each time there is no sleep.
    }
}

func execute(ctx context.Context) {
    fmt.Println(time.Now(), "executing func")

    // since ctx was cancelled immediately, sleepContext will return immediately without any sleep.
    sleepContext(ctx, 5*time.Second)
}


package main

import (
    "flag"
    "fmt"
)

func main() {
    example := flag.Int("example", 1, "the example to run")
    flag.Parse()

    switch *example {
    case 1:
        fmt.Printf("===== Running example 1 =====\n\n")
        exampleOne()

    case 2:
        fmt.Printf("===== Running example 2 =====\n\n")
        exampleTwo()
    }
}

The output for both exampleOne and exampleTwo will look like this:

$ go build -o bin .

$ ./bin -example 1
===== Running example 1 =====

2021-12-29 16:25:26.166643 +0530 IST m=+2.001564014 ticker executed
2021-12-29 16:25:28.168533 +0530 IST m=+4.003442497 ticker executed
2021-12-29 16:25:30.169012 +0530 IST m=+6.003912087 ticker executed
2021-12-29 16:25:32.169898 +0530 IST m=+8.004789488 ticker executed
2021-12-29 16:25:34.167073 +0530 IST m=+10.001956888 another ticker executed

$ ./bin -example 2
===== Running example 2 =====

2021-12-29 16:25:42.014868 +0530 IST m=+0.000194393 executing func
2021-12-29 16:25:42.015062 +0530 IST m=+0.000387651 executing func
2021-12-29 16:25:42.015068 +0530 IST m=+0.000393697 executing func
2021-12-29 16:25:42.015071 +0530 IST m=+0.000397068 executing func
2021-12-29 16:25:42.015074 +0530 IST m=+0.000400107 executing func

Union Find in Python

Bharghava Varun Ayada — Tue, 07 Dec 2021 00:00:00 +0000

Originally published at ayada.dev

Introduction

According to Wikipedia, dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a tree. Once the the dynamic connectivity structure is built, it should adapt itself such that it can give quick answers to queries of the form "is there a path between x and y?". The Union-Find algorithm is one approach build this connectivity structure. There are multiple approaches the Union-Find algorithm, the most optimal approach is the Weighted Quick Union algorithm. In this algorithm, we maintain an array id[] to determine whether two indexes are connected. The connections between elements (or nodes) can be considered to be a tree. Now let's define how we use the array id[] to solve the Quick-Union problem:

For the element i, id[i] gives the immediate parent of i in the tree.

For the element i, follow the parent of i until id[x] == x. Here, x is considered the root of i.

A path exists between x and y if root of x and root of y is the same.

In Quick-Union algorithm, we have two methods:

Union(p, q): This method will establish a connection between elements p and q in the tree, i.e., it will set q as the parent of p in the array id[]
Find(p): This method will find the root of the element p

In order to implement this algorithm, let's consider a real problem where you want to merge email accounts that might belong to the same person. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name. The input to this problem will look this:

[
    ['Alice', 'alice@example.com', 'alice_wonderland@example.com'],
    ['Bob', 'bob@example.com', 'bob_marley@example.com'],
    ['Alice', 'alice@mail.com', 'alice@example.com'],
    ['Alice', 'alice@mail.com'],
]

The solution expected is to merge the email accounts that belong to the same person, which means, the output for the above example is:

[
    ['Alice', 'alice@example.com', 'alice@mail.com', 'alice_wonderland@example.com'],
    ['Bob', 'bob@example.com', 'bob_marley@example.com'],
]

We can use the weighted Quick-Union algorithm here to solve the problem. We can establish a dynamic connectivity structure between the email accounts and figure out what accounts belong to the same person. The Union and Find method both have a run time complexity of logn where n is the number of elements or nodes in the structure.

In order to optimize the Quick-Union algorithm, when using Union method, always put the smaller tree (with lesser size or weight) lower than the larger tree. This ensures that the tree doesn't get too tall, thereby reducing the depth of the tree. Note that size of the tree here indicates the number of nodes in the tree.

A second optimization is in Find method, where we flatten the tree using path compression, every node we visit can be made to point to its grandparent.

Here is the complete code, with comments, that implements Weighted Quick Union algorithm to solve merging of email accounts problem:

# quick_union/main.py

class MergeAccounts:
    def __init__(self, accounts):
        self.id = {} # the id dict that holds the dynamic connectivity structure
        self.owner = {}  # tells us the owner (name) of an email account
        self.size = {} # stores the size or weight of the tree
        self.accounts = accounts

        # We initialize the id, owner and the size dicts here
        for account in accounts:
            name = account[0]
            for email_id in account[1:]:
                self.owner[email_id] = name
                self.id[email_id] = email_id
                self.size[email_id] = 1

    def merge_accounts(self):
        for account in self.accounts:
            p = account[1]
            for q in account[2:]:
                self.Union(p, q)

        temp = {}
        for k in self.id:
            v = self.Find(k)
            temp.setdefault(v, []).append(k)

        merged = []
        for k, v in temp.items():
            name = self.owner[k]
            merged.append([name] + sorted(v))

        return merged

    def Find(self, i):
        while i != self.id[i]:
            # optimization: path compression, i.e. point node to its grandparent.
            # keeps the tree completely flat.
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]
        return i

    def Union(self, p, q):
        i = self.Find(p)
        j = self.Find(q)
        if i == j:
            return
        # optimization: always put the smaller tree lower, i.e. root of smaller tree is bigger tree.
        if self.size[i] < self.size[j]:
            self.id[i] = j
            self.size[j] += self.size[i]
        else:
            self.id[j] = i
            self.size[i] += self.size[j]

if __name__ == '__main__':
    accounts = [
        ["Alice", "alice@example.com", "alice_wonderland@example.com"],
        ["Bob", "bob@example.com", "bob_marley@example.com"],
        ["Alice", "alice@mail.com", "alice@example.com"],
        ["Alice", "alice@mail.com"],
    ]
    m = MergeAccounts(accounts)
    print(m.merge_accounts())

The output from the above code is:

$ python3 quick_union/main.py
[['Alice', 'alice@example.com', 'alice@mail.com', 'alice_wonderland@example.com'], ['Bob', 'bob@example.com', 'bob_marley@example.com']]

The full source code is available in the Github repository

I hope this was helpful and if you find any errors or issues in this post, please do let me know in the comments section below.

Ways to Rate Limit Requests in Go

Bharghava Varun Ayada — Tue, 12 Jan 2021 12:56:36 +0000

Originally published at ayada.dev

Introduction

Layer 7 DDoS attacks are quite common these days. With a simple script, any one can send thousands of requests to services to exhaust server resources. They can easily take down services and cause disruptions to a business. It is wise to implement strategies to mitigate such attacks using techniques that limit the number of requests a person can send to the service. It is possible to rate limit the user requests by IP address or a user ID, if available, although the former is more popular.

Basically, a service keeps track of the number of requests that have been originating from a single IP address in a given time window. If it exceeds a limit, the subsequent requests will be rejected by the service with an HTTP status code of 429 Too Many Requests. But in order to implement a rate limit feature, there are different algorithms that can be used. In this article, we will look at the different algorithms that one can consider.

Fixed window algorithm

In fixed-window algorithm, limits are set per time frame, such as 1,000 requests per hour or 10 requests per minute and so on. It is easy to implement and does quite well at rate limiting requests, but as the available quota resets, they are subject to spikes at the edges of the window. For example, let’s consider a limit of 1,000 requests per hour. This algorithm allows for a spike of all 1000 requests in the very first minute of the hour and thus overwhelm the service that this algorithm is protecting.

In Go, there are multiple packages available that uses this algorithm:

Sliding window algorithm

In sliding window algorithm, along with the benefits of fixed-window algorithm, the rolling window of time smooths out bursts of requests to the service by adding a weighted count in previous window to the count in current window.

In Go, there are multiple packages available that uses this algorithm:

Token bucket algorithm

The token bucket algorithm maintains a fixed capacity bucket where a tokens are added at a fixed rate. The tokens in most cases is a single request or in some cases, it can be network packets. When the bucket is full, the service is considered to have reached its limit and responds with backpressure. This algorithm is used when there is a case where not all inputs correspond to 1:1 with requests. For instance, a request to a service can make multiple database calls and then return a result. Each database call may take one token.

In Go, there are multiple packages available that uses this algorithm:

Leaky-bucket algorithm

A leaky bucket is similar to a token bucket, but the rate is limited by the amount that can drip or leak out of the bucket. This technique recognises that the system has some degree of finite capacity to hold a request until the service can act on it; any extra simply spills over the edge and is discarded. It is normally used to rate limit requests to load balancers and disk I/O buffers. It is also used in packet-switched computer networks and telecommunications networks in both the traffic policing and traffic shaping of data transmissions.

In Go, there are multiple packages available that uses this algorithm:

I hope this was helpful and if you find any errors or issues in this post, please do let me know in the comments section below.

Implement tail command in Python

Bharghava Varun Ayada — Mon, 11 Jan 2021 20:40:49 +0000

Originally published at ayada.dev

Introduction

In this article, we will write a simple implementation of the tail command from Linux. This program will take a file and an integer n as input and print the last n lines from the file. Also, the goal of the program is to not read the entire file into memory at once. This will make the program memory efficient when dealing with very large files.

Implementation Details

In order to implement this program, we will use queue data structure. We will read the file line by line and push each line into the queue. Every iteration, we will check the size of the queue. When the size of the queue is greater than or equal to n, we will remove the element that was first inserted in the queue. Since queue is a FIFO data structure, the element that was first inserted into the queue will be the first element that will be removed from the queue. This will ensure that the queue contains only last n lines from the file.

As a bonus, I have used argparse to handle the input from cli. Let's look at the implementation of this program.

import argparse
import queue


def tail(filename, n):
    q = queue.Queue()
    size = 0

    with open(filename) as fh:
        for line in fh:
            q.put(line.strip())
            if size >= n:
                q.get()
            else:
                size += 1      

    for i in range(size):
        print(q.get())

if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Print last n lines from a file.')
    parser.add_argument('file', type=str, help='File to read from')
    parser.add_argument('-n', type=int, default=10, help='The last n lines to be printed')
    args = parser.parse_args()

    tail(args.file, args.n)

Caching records by tags in Go

Bharghava Varun Ayada — Mon, 28 Dec 2020 20:39:37 +0000

Introduction

Caching has an important role to play in a system design. It is primarily used to speed up information retrieval from a service and reduce the load on a database engine, the primary source of truth for a service. Data that is frequently requested by users are stored in a in-memory key-value store, like Redis, to speed up subsequent look up of the same data. In this post, I want to specifically talk about cache invalidation and provide an implementation in Go for invalidating cache using tags.

Cache Invalidation

When frequently accessed data which is stored in a cache is updated, it is necessary for the application to evict the stale data from the cache. So when subsequent requests for the same data is received by the application, it will retrieve fresh data from the database and store it in the cache. This way, users will never receive stale data from the application. The process of cache invalidation can be made easier by tagging data with specific tags when storing in the cache. This way, when the data needs to be invalidated, we can use the tag names to evict them from the cache.

Here is an implementation of caching records by tags. We will use Redis and github.com/go-redis/redis package.

import (
    "github.com/go-redis/redis/v7"
)

type cache struct {
    client redis.Client
}

func (c *cache) SetByTags(ctx context.Context, key string, val interface{}, tags []string, expiry time.Duration) error {
    pipe := c.client.TxPipeline()
    for _, tag := range tags {
        pipe.SAdd(tag, key)
        pipe.Expire(tag, expiry)
    }

    pipe.Set(key, b, expiry)

    _, errExec := pipe.Exec()
    return errExec
}

func (c *cache) Invalidate(ctx context.Context, tags []string) {
    keys := make([]string, 0)
    for _, tag := range tags {
        k, _ := c.client.SMembers(tag).Result()
        keys = append(keys, tag)
        keys = append(keys, k...)
    }
    c.client.Del(keys...)
}

In SetByTags method, we maintain a set data structure for each tag provided. We then add the given cache key into these sets. When invalidating cache by tags, we get all the members, i.e. cache keys, for the given tags and delete them from Redis.

Example usage:

tags := []string{"post1", "post2"}
value := "blog data"

key1 := "blog:one:post1"
key2 := "blog:one:post2"

// Set cache by tags here:
cache.SetByTags(ctx, key1, value, tags, 24 * time.Hour)
cache.SetByTags(ctx, key2, value, tags, 24 * time.Hour)


// Invalidate cache by tag "post1" here.
// Both key1 and key2 will be evicted, since both were tagged with "post1".
cache.Invalidate(ctx, []string{"post1"})

References

If you find any issues or errors in the content, please do let me know in the comments below.

In case you like to read more articles related to software development and programming, check out my blog.

Strings in Go

Bharghava Varun Ayada — Mon, 28 Dec 2020 19:41:13 +0000

String Types

In Go, a string value is a sequence of bytes. A string value could be empty and the number of bytes is called the length of the string and is never negative. Strings are immutable: once created, it is impossible to change the contents of a string.

The predeclared string type is string; it is a defined type.

Normally, the length of a string s can be discovered using the built-in function len. This function returns the number of bytes in a string, not the number of characters. This is distinction is important because strings in Go support unicode encoding. So a character in a UTF-8 string can be more than one byte. For instance, this is a valid string in Go. Some of the characters here are not even valid UTF-8.

const sample = "\xbd\xb2\x3d\xbc\x20\xe2\x8c\x98"

Printing this string to stdout will produce the following output.

��=� ⌘

Length of a string

Like we discussed in the previous section, the built-in function len returns the number of bytes in a string. So, for instance, if our sample string is Well done 👍🏼, then len will return 18.

s := "Well done 👍🏼"
fmt.Printf("len(s) = %d\n", len(s))

The output is:

len(s) = 18

Now, instead of number of bytes, if we wanted to know the number of characters in the string, then we would need to use a different function. May be the standard RuneCountInString function from utf8 might come in handy. Let's try that here:

s := "Well done 👍🏼"
fmt.Printf("# of characters in s = %d\n", utf8.RuneCountInString(s))

The output is:

# of characters in s = 12

This function here returned 12 as the output, but we have only 11 characters in the string s. This is because the function RuneCountInString returns the number of runes in the string. Each unicode code point in a string is represented as a rune literal. Let's see what the rune literals are here:

s := "Well done 👍🏼"
for _, i := range []rune(s) {
    fmt.Printf("%v ", i)
}

The output is:

87 101 108 108 32 100 111 110 101 32 128077 127996

As expected, we have 12 rune literals in the string s. Note that each english alphabet is a single rune literal, which is equivalent to it's respective ASCII value, but the emoji character requires two rune literals 128077 and 127996. This is because the emoji used here requires a separate rune or byte to represent the skin tone. So then, how do we actually figure out the number of characters?

There is an open source library github.com/rivo/uniseg that provides a function to do just this. It provides a function GraphemeClusterCount that returns the number of characters that is present in this string. Check out the source code on Github for details about the author and the implementation.

Now let's try this library and see if we can get the actual number of characters in the given string.

import "github.com/rivo/uniseg"

s := "Well done 👍🏼"
fmt.Printf("uniseg.GraphemeClusterCount(s) = %d\n", uniseg.GraphemeClusterCount(s3))

The output is:

uniseg.GraphemeClusterCount(s3) = 11

Finally, we have a function that provides the right value for the number of the characters in the given string. This works in almost all cases that I have tested. Please do run your own tests before using this.

String Conversion

Before we end this article, let's look at a common mistake that beginners to Go might encounter when working with strings. Let's look at a snippet here.

s1 := string(65)
fmt.Printf("length of s1 = %d\n", len(s1))

s2 := strconv.FormatInt(65, 10)
fmt.Printf("length of s2 = %d\n", len(s2))

Here the output would look like this:

length of s1 = 1
length of s2 = 2

This is because the string(65) returns the character that is represented by integer 65 in unicode. In this case, that value is character A. So the length of s1 is 1. To actually convert the integer to string, use the function FormatInt from strconv package. Here strconv.FormatInt(65, 10) converts base 10 representation of 65 to a string. Hence the variable s2 is set to "65" and the length of s2 is 2.

References:

Strings, bytes, runes and characters in Go https://blog.golang.org/strings
String types https://golang.org/ref/spec#String_types
rivo/uniseg package https://github.com/rivo/uniseg
strconv package https://pkg.go.dev/strconv

In case you like to read more articles related to software development and programming, check out my blog.