DEV Community: creativcoder

What is a LSM Tree?

creativcoder — Fri, 05 Feb 2021 16:45:00 +0000

In this post, we'll dive deep into Log Structured Merge Tree aka LSM Tree: the data structure underlying many highly scalable NoSQL distributed key-value type databases such as Amazon's DynamoDB, Cassandra and ScyllaDB. These databases by design are known to support write rates far more than what traditional relational databases can offer. We'll see how LSM Tree enables them to allow the write speeds that they claim, as well as how they facilitate reads.

Target audience: You have heard of NoSQL databases such as Amazon's DynamoDB, Cassandra and embedded key value stores such as LevelDB and RocksDB and want to learn about their internals. You also have a cursory idea of different components in a database management systems (DBMS in short), particularly storage engines.

This post aims to strike a balance in understanding what's written in the LSM Tree paper and what's implemented in real world key-value stores. Even though a lot has been written about LSM Trees before, there are a lot of jargons and details about LSM Trees that are often omitted which can make them inaccessible to newcomers. This was the case with me when I started researching about LSM Trees. My goal of writing this post is to serve as an introductory resource on understanding LSM Trees and then branch off from here.

Disclaimer: This post is an informal documentation of my research and notes for my toy database project and is a living document. I could be wrong. I want you, the readers to correct any misleading information.

Before we begin

First, we need a bit of context. A typical Database Management System (DBMS in short) consists of multiple components, each responsible for handling different aspects of data storage, retrieval and management. One such component is the storage engine which is responsible for providing a reliable interface for reading and writing data efficiently from/to the underlying storage device. It's the component that implements the two among the four big asks of databases i.e., the ACID properties: Atomicity and Durability. In addition to that, the performance of a storage engine matters a lot in the choice of a database as it's the component that's closest to the storage device in use. Two popular data structures for implementing storage engines are B+ Trees and LSM Trees. In this post, we'll cover LSM Trees.

Why learn about LSM Trees?

Almost all NoSQL databases use a variant of LSM Tree as their underlying storage engine, because it allows them to achieve fast write throughput and fast lookups on the primary key. Understanding how LSM Trees work will provide you with a better context in debugging any issues that you run into when using these databases. For example, in-order to tune Cassandra for a specific workload, one needs to understand and choose between different compaction strategies, which is a critical phase in LSM Tree data management lifecycle. (covered later)

Workload

A Workload in a DBMS context refers to the amount of operations that a database system can deliver in a given amount of time against a given set of metric[s] or query patterns. OLTP (Online Transaction Processing) queries and OLAP (Online Analytical Processing) queries are two among the many kinds of workload on which databases are evaluated against.

LSM Trees are also gaining popularity as storage devices advance in their physical design from spinning disks to NAND flash SSDs and recently NVDIMMs such as Intel Optane. Traditional storage engines (based on B+ Trees) are designed for spinning disks, are slow in writes and offer only block based addressing. Today's applications, however, are write intensive and generate high volumes of data. As a result, there's a need to rethink the design of existing storage engines in DBMSs. New storage devices such as Intel Optane and other NVMs offer byte addressibility and are faster than SSDs. This has led to explorations such as Nova which is a log structured file system for persistant memory.

In addition to that, learning about LSM Trees is the fastest way to get into the complicated world of database storage engine internals. They are very simple in design than B+ Tree based storage engines. So if you're someone interested in how NoSQL databases store your data, or are trying to implement a storage engine, continue reading!

Prologue

Design a simple key value database

Not taking the traditional SQL and relational path, if you were asked to design a very simple database from scratch that supports inserting data as key value pairs, how would you go about it? A possible naive implementation would be to use a file as the storage unit. Every time you receive a put request for a key and a value, you append the key value to a file:



k1: v1
k2: v2
...
...
...

/var/local/data.db

On a get request on a given key k, you scan and find the most recent entry in the file and return back the associated value as response or a null if the key does not exist. With such a design, the writes are really fast since it's just an append to the end of the file but reads have a worst case time complexity of O(n). Add a REPL interface over this with a communication protocol such as HTTP or GRPC, and you have a very trivial database server, albeit impractical for real world usage.

Although our simple database doesn't handle tricky cases such as deletes, duplicates and filling up the disk space, this simple design is at the core of many real world NoSQL databases. To make this design of any practical use, real world databases often add support for features such as: transactions, crash recovery, query caching, garbage collection etc. They also use custom data structures which exploit the access latencies along the storage hierachy and uses a mix of in-memory and disk resident structures to support efficient read/write performance.

This idea of an append only file of records is nothing new and there exists file systems for storage devices that use this design as their storage management logic. They are called Log-structured file systems. Log-structured file systems first appeared in the 1990s (paper). It was then discovered that the same ideas and design could be used as a storage engine in databases.

Motivation behind LSM Trees

To understand LSM Trees, it helps to understand why log-structured file systems (hereby LFS) came into existence as LSM Trees are largely inspired from them. LFS were proposed by Rosenblum and Osterhout in 1991. They have not seen wide adoption in the file system space, although the idea has shown up in the database world in the form of LSM Trees.

During the 1990s, disk bandwidth, processor speed and main memory capacity were increasing at a rapid rate.

Disk Bandwidth: It is the total number of bytes transferred divided by the total time between the first request for service and the completion of the last transfer.

With increase in memory capacity, more items could now be cached in memory for reads. As a result, read workloads were mostly absorbed by the operating system page cache. However, disk seek times were still high due to the seek and rotational latency of physical R/W head in a spinning disk. A spinning disk needs to move to a given track and sector to write the data. In the case of random I/O, with frequent read and write operations, the movement of physical disk head becomes more than the time it takes to write the data. From the LFS paper, traditional file systems utilizing a spinning disk, spends only 5-10% of disk's raw bandwidth whereas LFS permits about 65-75% in writing a new data (rest is for compaction). Traditional file systems write data at multiple places: the data block, recovery log and in-place updates to any metadata. The only bottleneck in file systems now, were during writes. As a result, there was a need to reduce writes and do less random I/O in file systems. LFS came with the idea that why not write everythng in a single log (even the metadata) and treat that as a single source of truth.

Log structured file systems treat your whole disk as a log. Data blocks are written to disk in an append only manner along with their metadata (inodes). Before appending them to disk, the writes are buffered in memory to reduce the overhead of disk seeks on every write. On reaching a certain size, they are then appended to disk as a segment (64kB-1MB). A segment contains data blocks containing changes to multitude of files along with their inodes. At the same time on every write, an inode map (imap) is also updated to point to the newly written inode number. The imap is also then appended to the log on every such write so it's a just single seek away.

We're not going too deep on LFS, but you get the idea. LSM Tree steals the idea of append only style updates in a log file and write buffering and has been adopted for use as a storage backend for a lot of write intensive key value database systems. Now that we know of their existence, let's look at them more closely.

LSM Tree deep dive

LSM Tree is a data structure that restricts your datastore to append only operations, where your datastore is simply a log containing totally ordered key value pairs. The sort order is by key which can be any byte sequence. The values too can be any arbitrary byte sequence. For example, in Cassandra's data model, a column family (akin to a table in relational database) contains a row key (the key) and any sequence of arbitrary key values that can vary in cardinality (the value). Being append only, it means that that any kind of modification to the datastore, whether it is write, update or delete, is simply an append to the end of the log. This might sound very un-intuitive but we'll see how such a design is even possible and what challenges it poses.

The actual physical implementation of the log gets more complicated in order to exploit the storage hierarchy and the log is usually segmented across multiple files to allow for more efficient reads.

LSM Tree is not a single data structure as a whole but combines multiple data structures that exploit the response times of different storage devices in the storage hierarchy. Being append only, it provides high rates of writes while still providing low cost reads via indexes maintained in RAM. In contrast to B+ tree based storage engine which performs in-place updates, there are no in-place updates in a LSM Tree and this helps in avoiding random I/Os. Before we delve further, let's expound on the drawbacks of using a B+ tree based database storage engine in a write intensive workload.

Most traditional relational/SQL databases use a B+ Tree based storage engine. In these databases, every write has to perform not only the requested write of the record, but also perform any required metadata updates to the B+ Tree invariants which involves moving/splitting/merging nodes in the B+ Tree structure. As a result, the Write Amplification is more on each write to a B+ Tree structure, thereby resulting in slower writes.

Write amplification (WA)

It is the ratio of the amount of logical data to write vs the actual amount of physical data written to the underlying storage engine. The value is used as an evaluation criteria for choosing a storage device or engine. A less WA value means faster writes.

On spinning disks, the WA will certainly be visible as the write head has to perform a lot of seeks, but not so much in SSDs. But even on an SSD, the increased number of I/O per write will still degrade the lifespan of the SSD as they can only sustain a limited number of writes in their lifetime. SSDs have a copy on write semantics for page updates, and any modification first erases the original block and then rewrites the data in a new block thereafter pointing to the newly written block. The older block is then garbage collected by the SSD flash controller which also adds to the write cost. So sequential writes are beneficial to both spinning disks as well as SSDs.

Note: The above points don't intend to convey that relational databases are bad and should not be used, it's just suited for read heavy workloads. Having said that, a database should always be chosen according to the data model and the workload in your application. It's always a better idea to go with a use case and benchmark driven solution over tech driven solutions.

Dissecting LSM Tree

LSM Trees highlights the problem that random I/O on disk has a lot of write overhead, whereas sequential write is much faster as the disk write head is right next to the place of the last written record and there is minimal rotational and seek latency.

From the paper, LSM Trees are explained more as an abstract data structure and also explains the motivation to use a tiered storage architecture. The term Log-structured means that the data is structured one after other like an append only log. The term merge refers to the algorithm with which data is managed in the structure. The term tree in its name comes from the fact that data is organized into multiple levels similar to devices in the storage hierarchy in a typical computer where the top level device holds smaller subset of data and is faster to access while the lower levels holds larger segments of data and is slow to access. In a barebone setting, a LSM Tree is composed of two data structures using both RAM and and persistant disk to their advantage:

Memtable

This data structure is the first point of contact for every read or write operation received by the LSM Tree. The Memtable is an in-memory structure that buffers incoming data from clients before flushing them to disk. The flush happens when the Memtable reaches a certain size threshold (~4MB in LevelDB). However, the threshold size varies depending on which database the LSM Tree is used for, keeping the RAM usage by other components in mind. What data structure to use for the Memtable typically depends upon the performance requirements but must have a property that it should provide a sorted iteration over its contents. One could naively use a Vector, or the more efficient balanced binary trees such as AVL Trees or Red Black Trees or a Skiplist (used in LevelDB). The amount of data the Memtable can hold is limited by the RAM and on exceeding the set threshold size, all of the contents of Memtable must be written to a file where items are sorted by key and a new Memtable must be created to ingest incoming writes. These persisted files are known as SSTables.

SSTable

The Sorted String table (SSTable), a concept borrowed from Google's BigTable, is the on-disk format (a file) where key value entries from Memtable are flushed in sorted order. An SSTable file is created when the Memtable reaches its capacity or when compaction happens (more on that later). The data in SSTable is stored sorted to facilitate efficient read performance. Over time, there can be multiple SSTables on disk due to frequent writes to the Memtable. These are continuosly re-organized and compacted into different levels which are usually namespaced as Level 0 to Level N. The level right below (logically) the Memtable is Level 0, and can contain SSTables with overlapping keys. This means that there might be two SSTables (say S1 and S2) in level 0 where S1 might contain keys in range [a..f) and S2 might contain [c..h] and the overlapping keys are (c,d,e,f,g,h). This is so because SSTables at Level 0 are plain dump of the contents of Memtable. Any deduplication of keys are deferred as a background task. The SSTable files at Level 1 and above are organized to contain only non-overlapping keys by design. Despite having a very simple structure, the SSTable architecture is capable of holding and serving petabytes of data as evident from Google's usage of them in their distributed database projects. To make them efficient, several enchancements are implemented on top of them by database systems.

SSTable enchancements

In practical implementations, SSTable files are also augmented with a SSTable summary and an index file which acts as a first point of contact when reading data from an SSTable. In this case, the SSTable is split into data files, an index file and a summary file (used in Casssandra and ScyllaDB).

SSTable data file

The SSTable data files are usually encoded in a specific format with any required metadata and the key value entries are stored in chunks called blocks. These blocks may also be compressed to save on disk space. Different levels may use different compression algorithms. They also employ checksums at each block to ensure data integrity.

SSTable index file

The index file lists the keys in the data file in order, giving for each key its position in the data file.

SSTable summary file

The SSTable summary file is held in memory and provides a sample of keys for fast lookup in the index file. Think of it like an index for the SSTable index file. To search for a specific key, the summary file is consulted first to find a short range of position in which the key can be found and the loads up that specific offset in memory.

How SSTable can provide fast read access?

If all we do is combine and merge SSTables, our SSTables would get quite large soon at the lower levels. Reads from those files will have to iterate over many keys to find the requested key. A linear scan at worst at the lowest level SSTables.
To bring down the linear time complexity, an index over the file is an obvious solution here. We can have an in-memory index (a hashmap) which contains a mapping of keys to their byte offset in the file. With this, we are just a O(1) lookup away in the file. But if we keep all the keys in memory, we would end up using a lot of memory. What practical implementations do is that they maintain a Sparse Index of each SSTable which contains only the subset of keys in memory and utilize binary search to quickly skip ranges and narrow the search space. Everytime a compaction process occurs, the sparse indexes are also kept up-to date to allow reads to retrieve the updated data. In terms of implementation in the SSTable format, the sparse index is usually encoded at the end of the file or as a separate index file. When an SSTable is read, the sparse index is loaded into memory and is then used to find the requested key for any read request. Many practical implementations also include a bloom filter over each SSTable along with a sparse index to bail early where the key does not exist. Additionally, implementations may also memory map the SSTables in memory so lookups can happen without touching the disk. There are lot of other optimizations which are done over the SSTable which gives them a comparable performance like B+ Trees.

Now that we know the core architecture of LSM Trees, let's discuss the core operations that a LSM Tree supports and how they work.

Operations on LSM Tree

To be suitable for use in a key value database, a LSM Tree must support the following APIs at minimum:

Writing/Updating data in a LSM Tree

All writes in a LSM Tree are buffered in-memory and goes first to the Memtable. The Memtable is configured with a threshold (usually by size) post which all of the items in the Memtable is written to a file and is marked as part of Level 0 SSTable. The file is then marked immutable and cannot be modified. In practical implementations, the writes are also preceded by appending the entry to a Write Ahead Log (WAL) file to protect from a crash and ensure durability. In cases when the database crashes while still holding key values in Memtable, a WAL enables one to re-build and recover uncommitted entries back in the Memtable on the next restart. On reaching the Memtable threshold, the WAL is also flushed and is replaced with a new one.

Updating a key value is not performed in place for already existing keys. Instead, an update to a given key will just append the new key value to the log. The older value for the data is removed at a later point in time through a phase called compaction (discussed later).

Deleting data in a LSM Tree

It might come off as non-intutive the first time you discover that LSM Tree does not delete your data in-place from the log. This is so because doing so would require random I/Os thereby adding overhead to write performance.
Since LSM Tree must hold the invariant of append only style updates to maintain the write performance, deleting things in a LSM Tree is the same as appending a key value entry to the log, instead a special byte sequence referred to as a "tombstone" is written as the value. It can be any byte sequence that should be unique enough to distinguish from other possible values. The existing older values are later removed by the compaction phase.

Reading data in a LSM Tree

All reads in a LSM Tree is served first from the Memtable. If the key is not found in the Memtable, it is then looked up in the most recent level L0 then L1, L2 and so on till we either find the key or return a null value. Since the SSTables are already sorted, we benefit from the ability to perform a binary search on the files to quickly narrow down the range within which the key may be found.

Usually SSTables files in L0 might span the entire key space. A read will then have to access almost all files in the worst case to serve a read from L0. To keep the number of hops that reads have to do small, files in L0 are combined and moved from L0 to L1 from time to time. This helps reduce multiple I/Os to the file. In practical implementations, a Sparse Index is also used, which keeps only a range of keys in memory for each SSTable and helps reduce the number of scans required for reading a key. In addition to that, a bloom filter is also employed on each SSTable to bail early if the key does not exist in the file. This makes queries which checks if a key does not exist, very fast.

During all of the above operations, our log is bound to grow to a very large size because all we do is append entries and never get rid of older duplicate/deleted entries, which brings us to the next section on compaction.

Enter compaction

Over time, the number of SSTable files on disk will ultimately grow in number as flushes keep happening due to the Memtable getting full. In this case, when reading a given key, the LSM Tree will have to look into multiple SSTable files in the worst case which will result in a lot of random I/O everytime a new file is accessed. For example, in Cassandra, the values stored have many columns in them. An update to key k at time t1, might add 4 column values (k -> (v1, v2, v3, v4)). At a later point in time t2, the same key k might update the 4th column value to some other value and might delete the 2nd column value (k -> (v1, v3, v4_1)). When the same key k is read at a later time t3, cassandra will need to aggregate updates from both of the changes above to build an updated value for k. Now if these changes for the given key k is spread across multiple SSTable files, reads will need to perform a lot of random I/O to retrieve the updated value. This deteriorates the read performance and so there needs to be a way to combine these updates in a single file if possible. This is done by a phase called compaction.

Compaction is a critical phase of LSM Tree data management lifecycle allowing them to be used for extended periods of time in practical systems. Think of it like a garbage collector for the LSM Tree. It keeps the disk usage and read/write performance of the LSM Tree in check. The core algorithm utilized by compaction is the k-way merge sort algorithm adapted to SSTables. I wrote a post on this if you are unfamiliar with the algorithm. In summary, we keep pulling the next key value pair from given k lists of entries (based on whatever the sort order is) and put them one by one in a new SSTable file. During the process, we remove entries which are older or merge them with newer entries and delete older entries which have a tombstone value in the recent entry.

Apart from reducing multiple I/Os, another problem that compaction helps solve is that, there might be multiple old entries for a given key or deleted tombstone entries which ends up taking space on disk. This happens when a delete or an update is performed for an existing key at a later time. It then becomes essential to reclaim disk space for outdated and deleted keys and compaction does this by discarding older or deleted entries when creating a new SSTable file.

In terms of implementation, a dedicated background thread is used to perform compaction. Compaction can either be done manually by calling an API or automatically as a background task when certains conditions are met. The compaction process can be synchronous or asynchronous depending on what consistancy guarantees are configured for the LSM Tree store. The read write performance of a LSM Tree is greatly impacted by how compaction happens. As an optimization, there might be multiple dedicated compactor threads running at a given point in time (as in RocksDB) to compact SSTables files. The compaction thread is also responsible for updating the Sparse Index post any merge, to point to the new offsets of keys in the new SSTable file. Everytime the size of files in level 0 reaches the configured threshold, a file or multiple of them is taken and merged with all overlapping keys of the next level (level 1). The same happens with level 1 to level 2 and likewise when those levels reach their capacity. Now, the metric to determine when levels become full can be different based the compaction strategy. Different compaction strategies are utilized based on the requirements and they determine the shape of the SSTables at all the levels.

Compaction strategies

A compaction strategy must choose which files to compact, and when to compact them. There are a lot of different compaction strategies that impact the read/write performance and the space utilization in the LSM Tree. Some of the popular compaction strategies that are used in production systems are:

Size-tiered compaction stratey - This is write optimized compaction strategy and is the default one used in ScyllaDB and Cassandra. But it has high space amplification, so other compaction strategies such as leveled compaction were developed.
Leveled compaction strategy - Improves over size-tiered and reduces read amplification as well as space amplification. This is the default in LevelDB.
Time windowed compaction strategy - Used for time series databases. In this strategy, a time window is used post which compaction is triggered.

The above are not the only strategies and various systems have developed their own such as the hybrid compaction strategy in ScyllaDB.

Drawbacks of LSM Trees

Any technology introduced, brings with it its own set of tradeoffs. LSM Tree is no different. The main disadvantage of LSM Tree is the cost of compaction which affects read and write performance. Compaction is the most resource intensive phase of LSM Tree due to compression/decompression of data, copying and comparision of keys involved in the process. A chosen compaction strategy must try to minimize read amplification, write amplification and space amplification. Another drawback of LSM Tree is the extra space required to perform compaction. This is certainly visible in size tiered compaction strategy and so other compaction strategies like leveled compaction are used. LSM Tree also makes reads slow in the worst case. Due to the append only nature, reads will have to search in SSTable at the lowest level. There's file I/O involved in seeks which makes reads slow.

Despite their disadvantages, LSM Trees have been in use in quite a lot of database systems and has become the de-facto pluggable storage engine in lot of storage scenarios.

LSM Trees in the wild

LSM trees have been used in many NoSQL databases as their storage engine. They are also used as embedded databases and for any simple but robust data persistance uses cases such as search engine indexes.

One of the first projects to make use of LSM Trees was the Lucene search engine (1999). Google BigTable (2005), a distributed database also uses LSM Tree in their underlying tablet server design and is being used for holding petabytes of data for Google Crawl and analytics. It was then discovered by BigTable authors that the design of BigTable's "tablet" (storage engine node) could be abstracted out and be used as a key value store.

Born off of that, came LevelDB (2011) by the same authors which uses LSM Tree as its underlying data structure. This gave rise to pluggable storage engines and embedded databases. Around the same time in 2007, Amazon came up with DynamoDB which uses the same underlying LSM Tree structure along with a masterless distributed database design.

Dynamo DB inspired the design of Cassandra (2008), which is an open source distributed NoSQL database. Cassandra inspired ScyllaDB (2015) and others. InfluxDB (2015), a time series database also uses LSM Tree based storage engine called Time structured merge tree.

Inspired from LevelDB, Facebook forked LevelDB and created RocksDB (2012), a more concurrent and efficient key value store that uses multi-threaded compaction to improve read and write performance. Recently Bytedance, the company behind TikTok has also released a key value store called terakdb that improves over RocksDB. Sled is another embedded key value store in Rust, that uses a hybrid architecture of B+ Trees and LSM Tree (Bw Trees). These fall under the category of embedded data stores.

I hope by now you have a pretty good idea about LSM Trees. For those who are keen to dig deeper, a few links to original papers are down below. Until next time!

References

LFS paper

LSM Tree paper

As always, you can support this blog by donating on the following links:

Merge k sorted arrays in Rust

creativcoder — Mon, 07 Dec 2020 04:21:10 +0000

Originally posted on creativcoder.dev

The other day, I was reading about LSM Tree based database storage engines (specifically, the LevelDB docs) where I came to know about a phase called compaction. LSM Tree based database storage engines are key-value storage systems where every operation is append only to favour less write amplification and to reduce latency. LevelDB persists data file segments to disk (when the in-memory table hits a threshold) in sorted order to support efficient read queries. Even operations such as deletes or updates appends new entries to the underlying storage and this often leads to keys that are obsolete but still remain on disk and that increases disk usage. To overcome this, they often use a phase called compaction where several sorted files are merged into single file to remove old data records in background. In order to implement a similar compaction strategy in my toy database project, I used the merge sub-routine from merge sort, generalizing it to k sorted arrays. In this post, I write about the implementation the merge k algorithm in Rust. If you know the merge sub-routine from merge sort, you should feel right at home understanding the algorithm.

The problem

Before formalizing the solution, we'll re-state the problem again with examples and reason up from there to come up with an implementation in Rust.

We are given k array of items that are sorted. The problem is to implement a function that given k sorted arrays, merges them and returns an array where all the elements are in sorted order.

For example, If we are given 2 sorted arrays:

a = [3, 5]

b = [2, 7] where k = 2

Then the merged array we get, would be c = [2, 3, 5, 7]

Obvious naive solution

It's always a good idea to start with what you already know as the thinking lends itself to revealing more about the problem at hand. So, the obvious approach to solve this would be to just concatenate the two arrays and sort them. Here's a solution in Rust:

fn main() {
    let a = vec![3, 5];
    let b = vec![2, 7];
    let c = [a, b].concat();
    a.sort();
    dbg!(a);
}

That was quite easy, but it does have a O(n*k * log n*k) worst case time complexity, where n is the size of the resulting vector and k is the number of arrays. Can we do better?

Let's try a different approach. Without thinking about the implementation, how would you normally put these elements in order by hand? Let's distill down the above example and give it a thought with a case by case analysis.

Case 1:

Let's say for example, the arrays have only 1 element in them:

a = [3]
b = [2]

In this case, it's pretty trivial. We just compare the first item with the second and take the smallest of the two, and insert it as first element in the resulting array: [2]. What remains is 3 from a which we then append giving us [2, 3] as the merged sequence.

Case 2:

Now, let's consider if one of the arrays have more than one element:

a = [3]
b = [2, 5]

In this case, we'll start again with the first item in both arrays and pick the smallest of the two items which is 2. The next item to compare is 3 (from a) and 5 (from b), among which 3 is chosen as the next smallest element. At this point in time, we have exhausted all items in array a. Now, whatever remains to be put in the merged array has to be from array b. This is because of the invariant that we always pick the smallest item in each iteration so if all items from array a are exhausted, all remaining elements must be greater than last element in a. So we append 5 from b to our merged array to give us: [2, 3, 5].

From the dry run of the above two cases, you must have already thought of using two variables as indexes over the arrays and walk over them one by one, taking the next smallest element in each iteration until one of them exhausts, and then copy all the items from the remaining array to our merged sequence. Sounds simple? Let's implement that:

Implementation of merge k, where k = 2

To simplify the implementation for readability, we'll limit the items to integer (i32) values. Once we have the implementation in place, one can refactor it easily to make it generic over any T.

Here's how we can implement the above index pointer based solution in Rust:


fn merge(a: &[i32], b: &[i32]) -> Vec<i32> {
    let (mut i, mut j) = (0, 0);
    let mut sorted = vec![];
    let remaining;
    let remaining_idx;
    loop {
        if a[i] < b[j] {
            sorted.push(a[i]);
            i += 1;
            if i == a.len() {remaining = b; remaining_idx = j; break;}
        } else {
            sorted.push(b[j]);
            j += 1;
            if j == b.len() {remaining = a; remaining_idx = i; break;}
        }
    }
    for i in remaining_idx..remaining.len() {
        sorted.push(remaining[i]);
    }

    sorted
}

We have the merge function defined that takes in two slices of integers aka reference to an array of integers and returns a Vec<i32> (a heap allocated value). Within merge, we create two indexes i, j that start with 0. We also create a remaining and remaining_idx to point to the array that gets left after all items from the other array gets exhausted. Next, we run a loop {}, where we pick the smallest item, push it to sorted and increment the respective index. We also do an additional check if we reach the end on one of the arrays and assign remaining and remaining_idx accordingly. After the loop, we loop over the remaining array items and push to sorted.

But, the above solution works only for 2 arrays. We need to generalize the solution to k sorted arrays.

Generalizing to k sorted arrays

How would one extend the above solution to k sorted collection of items?

Well it turns out that now we need to keep k pointers to k arrays and pick the smallest item out of k. It's easy enough to write code to keep track of the pointers, if we have let's say < 10 or < 100 arrays to be merged. Or instead of keeping pointers, we could store an array of indexes into the arrays. That's another solution that works again for smaller values of k. But, it's not a convenient or maintainable code to write when we have very large arrays to be merged. Moreover, the number of comparision increases linearly as k increases.

Following along the same solution, let's think about what we need to find from the k arrays at the first iteration of the loop. That's right, we need to find the minimum from k items. This might give you a hint of using some data structure that supports getting minimum item from the k items. One data structure that comes to my mind is the heap data structure. In particular, a min-heap data structure.

Enter the min heap

A Heap is a complete binary tree (nodes are inserted breadth first left to right) where there's a relation between parent and child nodes. This is the heap property. There are two variants of heap: min heap and max heap. In min heap the every parent node is smaller than the child and conversely for the max heap. At minimum, any implementation supports three key APIs:

inserting - Adds an element to the heap
removing - Removes an element to the heap
heapify - rebalances the tree while maintaining the heap property.

At all times the heap property must be maintained when inserting or removing items from the heap. Internally the heap uses the siftDown and bubbleUp sub-routines to maintain the heap property.

So using a min-heap, we can insert the first k items into the array. Then we keep popping until our heap is empty and keeping the array indexes.

To implement this, we need to modify our solution a bit.

Our merge method now takes in a Vec<Vec<i32>> as a parameter (an array of array of signed integers):


fn merge(arrays: Vec<Vec<i32>>) {

}

Next, let's create an Item struct that will hold references to the k arrays and their respective index as their iteration state. The index will tell us where in our array we are currently at. This Item instance will be the element that goes in our min heap.

#[derive(Debug, Eq)]
struct Item<'a> {
    arr: &'a Vec<i32>,
    idx: usize
}

Now Item doesn't convey how they should be compared, as it's a new data type we've defined. So we need to tell the type system how they should be compared. Doing this is easy and we'll just need to implement a few traits and defer the comparision to the elements of the array using a helper method get_item (we define). On the Item struct we'll implement the required traits (PartialEq, PartialOrd, Ord) so that it can be inserted into min-heap:


impl<'a> PartialEq for Item<'a> {
    fn eq(&self, other: &Self) -> bool {
        self.get_item() == other.get_item()
    }
}

impl<'a> PartialOrd for Item<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.get_item().partial_cmp(&other.get_item())
    }
}

impl<'a> Ord for Item<'a> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.get_item().cmp(&other.get_item())
    }    
}

We also have a few helper methods new and get_item purely for convenience.

impl<'a> Item<'a> {
    fn new(arr: &'a Vec<i32>, idx: usize) -> Self {
        Self {
            arr,
            idx
        }
    }

    fn get_item(&self) -> i32 {
        self.arr[self.idx]
    }
}

Once we have the required traits implemented for Item, we'll then implement the new merge algorithm:

use std::collections::BinaryHeap;
use std::cmp::Reverse;
use std::cmp::Ordering;

fn merge(arrays: Vec<Vec<i32>>) -> Vec<i32> {
    let mut sorted = vec![];

    let mut heap = BinaryHeap::with_capacity(arrays.len());
    for arr in &arrays {
        let item = Item::new(arr, 0);
        heap.push(Reverse(item));
    }

    while !heap.is_empty() {
        let mut it = heap.pop().unwrap();
        sorted.push(it.0.get_item());
        it.0.idx += 1;
        if it.0.idx < it.0.arr.len() {
            heap.push(it)
        }
    }

    sorted
}

We create a Vec that will hold our merged items. We then create a BinaryHeap instance and push all items in arrays as an Item with the start index 0. We then wrap item with Reverse (as it's a max heap by default) and push it to heap.

Next, we run a loop while we still have elements in heap. Within the loop, we get the smallest item by heap.pop() and push it to sorted and increment the item's index by 1. Because we might still have items in the heap, we check for that and push it back in the last line.

Finally once we are done, we return the sorted array.

For this solution our complexity now reduces to O(n*k * Log(k))

Finally let's test this out on a sample dataset:

fn main() {
    let a = vec![1, 5, 7];
    let b = vec![-2, 3, 4];
    let v = vec![a, b];
    dbg!(merge(v));
}

Final code: https://gist.github.com/creativcoder/20fda0f1a947bf2af3b93ab394d6bacb

Taking it a step further

An optimization on top of this would be to stream sorted values as they are processed by exposing an iterator over the k items in heap.

With that said, I am open to suggestions, improvements to the solution and you can do so with comments below. Until next time!

How to setup NextJS with TailwindCSS 🌊

creativcoder — Sun, 06 Dec 2020 18:05:09 +0000

Originally posted on creativcoder.dev

Lately, I've been dabbling with frontend projects and as a result, have been looking for the best out-of-the-box frontend stack. I found NextJS with TailwindCSS checks most of my requirements. As a backend engineer who does not want to dabble much with setting up a website or a project with hundreds of webpack plugins and manual configurations, I think NextJS with TailwindCSS provides a great rapid prototyping experience.

So I thought of putting together an article as a note to self about setting up TailwindCSS with NextJS. Hopefully this will also be helpful to you if you are starting a project with the same stack.

First, a bit of intro to these.

NextJS is a framework built on top of react with all the three lettered jazz (SSR and friends). The website explains it better than I do: https://nextjs.org/

TailwindCSS on the other hand is the next best thing to happen to CSS ecosystem after Bootstrap (in my opinion). It let's one prototype and experiment with UIs quickly without having to switch back and forth between your HTML and CSS files because in TailwindCSS, what you get is lego like blocks of CSS classes which you can mix and mash to create beautiful layouts. Later, when these classes get too big, you can extract the them into their own styled components using the @apply directive. It's like writing a bunch of lines of code and then extracting them out as functions. Quite amazing! As someone who does mostly backend, this is certainly an efficient way to prototype and get feedback on UI design. It reduces the context switch by a lot!

With that introduction out of the way, let's dive right in!

First, we'll create a NextJS app by running:

npx create-next-app next-tailwind

npx allows you to run binary packages from npm directly without installing them locally. Then, we'll cd into the folder and add the tailwindcss package:

cd next-tailwind
yarn add tailwindcss

Once that's added, we move in our styles folder and we'll create a globals.css file (might already be there for you):

touch styles/globals.css

To this file, we'll add the following tailwind directives and remove any existing styles if any:

@tailwind base;
@tailwind components;
@tailwind utilities;

The doc explains what they do: https://tailwindcss.com/docs/functions-and-directives
We'll also add a tailwind configuration file as you might need to customize the built-in style components classes it provides (injected via the above directives). So we'll run:

npx tailwindcss init

This creates a tailwind.config.js file at the root with basic fixtures for all customizable options:

// tailwind.config.js

module.exports = {
  purge: [],
  darkMode: false, // or 'media' or 'class'
  theme: {
    extend: {},
  },
  variants: {
    extend: {},
  },
  plugins: [],
}

One can also pass --full to populate the full list of configurable fields.

The final step is to add a postcss configuration file as we'll need to convert the contents of globals.css and any tailwind classes we write in on our page to plain CSS for our browser to understand. We'll create a configuration file for postcss at root:

touch postcss.config.js

where we'll add the following:

// postcss.config.js

module.exports = {
    plugins: [
        'tailwindcss'
    ]
}

We specify the plugin we want to use which is tailwindcss. With that, our setup is complete. Let's take it up for spin:

yarn dev

To try tailwind, let's clear everything in pages/index.js and paste the following:

// pages/index.js

export default function Home() {
  return (
    <div className="bg-yellow-300 flex h-screen justify-center items-center">
      <button className="bg-white p-5 shadow-lg duration-200 hover:bg-yellow-200 transform hover:-skew-x-12">
        Hello tailwind next
      </button>
    </div>
  )
}

That's a classic centered div example we've just created using a bunch of tailwind classes sprinkled in between.

Our parent div is a flex wrapper "flex" with a yellow background "bg-yellow-300" with screen height "h-screen" where items on main-axis (horizontal) are aligned as "justify-center" and items on cross-axis (vertical) are "items-center".

The button within, has a white background "bg-white" with a shadow "shadow-lg" and a padding "p-5". We also put some styles on the hover state: "hover:bg-yellow-200 transform hover:-skew-x-12 duration-200". Here we are just saying: on hover make the background yellow and skew it clockwise (-12deg) and transition with 200ms.

Let's head over to our browser to see it in effect:

Neat!

As you can see, we did all of this without ever touching any CSS file. Also, these class names are quite intuitive and having worked multiple times with tailwind, I now rarely need to look them up during rapid prototyping, which cuts another chunk of time spent looking at the docs.

It was with tailwind that I was able to quickly create a very simple landing page for avrow.

As an added note: Tailwind playground is an online tailwind playground that you can use to rapidly prototype UIs.

And that's how you setup tailwind with NextJS. Until next time.

Source code for this post is available at: https://github.com/creativcoder/next-tailwind

Cheers!

How to run Rust on Arduino Uno

creativcoder — Thu, 20 Aug 2020 08:11:12 +0000

Originally posted on: creativcoder.dev

At the time of writing this, about a month ago, the rust-avr fork was merged upstream. This means that you can now compile Rust programs for the avr microcontroller board by just running cargo +nightly build, providing a .cargo/config.toml for your target (avr-unknown-unknown). That's huge!

I have always been fascinated with the idea of using code to manipulate and affect physical objects. This is probably going to be a series of blog posts on my adventures with Rust on Arduino and maybe ESP8266 and discovery F3 in future. (I have these lying around too). Kicking off the series with this first post.

Target audience: This post is written with beginner to intermediate folks in mind who want a head start with embedded systems in Rust with Arduino. Once you have gone through this post, you may wanna go through the through the basics on embedded rust book. The code in the post is compiled on a Linux machine (Arch linux) with Rust compiler version: rustc 1.47.0-nightly (22ee68dc5 2020-08-05).

We'll take a whirlwind tour on how to run Rust on the Arduino Uno, which is probably the most widely known and used development board in the hobbyist embedded domain. The Arduino Uno is based on the ATmega328P, which is an 8 bit microcontroller falling under the family AVR. AVR is a family of micro-controllers developed since 1996 by Atmel, which was later acquired by Microchip technology. If you wanna read more about that, head over here: AVR-Rust book

With that brief history aside, let's get into it!

We'll do the hello world of arduino which is blinking an LED. It's a very simple exercise, but there's a lot to learn as a beginner.

Setting up our project

First, we'll create a new cargo project by running:



cargo new rust-arduino-blink

We'll need to cross compile our project for the avr target (target triple:avr-unknown-unknown).
For this we'll need to switch to the nightly toolchain as some of the dependent crates use unstable features to make all of this happen. So we'll run:



rustup override set nightly

The above command overrides the toolchain of choice for only our current directory to be nightly.

Then we'll install the required packages:



pacman -S avr-gcc

The avr-gcc package is required to use the linker.



pacman -S arduino-avr-core

The arduino-avr-core package contains utilities such as avrdude which is a tool to upload and manipulate ROM and EEPROM contents of microcontrollers using the in-system programming technique.

I am on an arch linux distro (endeavour OS) where pacman is our package manager.

Then, under Cargo.toml we'll add the following dependencies:



[dependencies]
# A panic handler is needed.  This is a crate with the most basic one.
panic-halt = "0.2.0"

[dependencies.arduino-uno]
git = "https://github.com/Rahix/avr-hal"
rev = "536c5d"

avr-hal is a cargo workspace that contains a bunch of crates segregated by boards where the arduino-uno crate is one
of them. Thanks to Rahix for putting this together.

We'll also need to add build metadata for cargo for the avr target. We'll create a file avr-atmega328p at our project root with the following contents:



{
    "llvm-target": "avr-unknown-unknown",
    "cpu": "atmega328p",
    "target-endian": "little",
    "target-pointer-width": "16",
    "target-c-int-width": "16",
    "os": "unknown",
    "target-env": "",
    "target-vendor": "unknown",
    "arch": "avr",
    "data-layout": "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8",

    "executables": true,

    "linker": "avr-gcc",
    "linker-flavor": "gcc",
    "pre-link-args": {
      "gcc": ["-Os", "-mmcu=atmega328p"]
    },
    "exe-suffix": ".elf",
    "post-link-args": {
      "gcc": ["-Wl,--gc-sections"]
    },

    "singlethread": false,
    "no-builtins": false,

    "no-default-libraries": false,

    "eh-frame-header": false
  }

and reference it in .cargo/config.toml:



[build]
target = "avr-atmega328p.json"

[unstable]
build-std = ["core"]

With that, our build configuration is complete.

Let's write some code

With the dependencies aside, let's add code under main.rs and go through it incrementally:

(Quick tip: You can run cargo doc --open in your directory and have a documentation of this project along with its dependencies for ready reference)



// main.rs

#![no_std]
#![no_main]

First we need to specify a few global attributes to let the compiler know that we are in a different environment.
We are in an embedded environment which doesn't have functionalities that the standard library crate of Rust depends on such as heap allocation APIs, threads, network APIs etc. So we need to add the #[no_std] attribute at the top. We also need to override the default entry point (fn main()) using #[no_main] because we are going to be providing and defining our own entry point to the program. To define our entry point, we'll use the entry attribute macro from the arduino_uno crate to define a custom entry point. Usually the board crate you use will provide an entry macro to you.

We then add use statements to bring the required items in scope from the dependant crates.



extern crate panic_halt;
use arduino_uno::prelude::*;
use arduino_uno::hal::port::portb::PB5;
use arduino_uno::hal::port::mode::Output;

Notice the panic_halt crate? We need a panic handler because:

In the standard library panicking has a defined behavior: it unwinds the stack of the panicking thread, unless the user opted for aborting the program on panics. In programs without standard library, however, the panicking behavior is left undefined. A behavior can be chosen by declaring a #[panic_handler] function. Source: [embedded rust book]

Let's move on:



#[arduino_uno::entry]
fn main() -> ! {

}

Then we have our main function annotated with the entry attribute macro from the arduino_uno crate. The ! is
the never type which denotes that the function never returns.

To blink the LED, we only need a few lines of code and set the relevant pin high or low. Let's take a look at the pin diagram of the ATmega328P chip on Uno:

In the diagram above, you can notice various pins on the microcontroller. Most microcontrollers, if not all, contain pins that allow the device to both read and write digital values to external circuits. Some of them are categorized as I/O ports.
A port is a group of pins representing a standard interface. These ports are controlled by port registers, which can be thought of as a special byte variable that we can change in our code.

In case of ATmega328P, we have three port registers to work with:

C – for analogue pins 0 to 5
D – for digital pins 0 to 7
B – for digital pins 8 to 13

The details are explained better here: Port Manipulation

If you look at the Uno, we have the digital Pin 13 which is connected to the built-in LED.
We need access to the pin in our code in order to manipulate the LED, i.e., set it high or low.

Let's add more code:



#[arduino_uno::entry]
fn main() -> ! {
    let peripherals = arduino_uno::Peripherals::take().unwrap();

    let mut pins = arduino_uno::Pins::new(
        peripherals.PORTB,
        peripherals.PORTC,
        peripherals.PORTD,
    );

    let mut led = pins.d13.into_output(&mut pins.ddr);

    loop {
        stutter_blink(&mut led, 25);
    }
}

There's a lot going on in the code above!

First, we create an instance of Peripheral which is a list of all peripherals in Uno.
Peripherals are devices that bridge the communication with your chip/cpu with external devices, sensors etc.
Examples of peripherals would be your timers, counters, serial port etc.
An embedded processor interacts with a peripheral device through a set of control and status registers.

We then create a new Pin instance passing in the ports from the peripheral instance peripherals.
We then define a variable led that will hold the pin number that the LED is connected to. This is created by configuring pin 13 as output pin using the into_output method of the d13 pin and passing in a mutable reference to our ddr register.

DDR register determines if pins on a specific port are inputs or outputs. The DDR register is 8 bits long and each bit corresponds to a pin on that I/O port. For example, the first bit (bit 0) of DDRB will determine if PB0 is an input or output, while the last bit (bit 7) will determine if PB7 is an input or output. I still need to do a bit more reading to fully understand DDR registers.

Next, we go into a loop {} and call stutter_blink function providing a mutable reference to our led instance
and number of times (25) that we want to blink.

Here's our stutter_blink function definition:



fn stutter_blink(led: &mut PB5<Output>, times: usize) {
    (0..times).map(|i| i * 10).for_each(|i| {
        led.toggle().void_unwrap();
        arduino_uno::delay_ms(i as u16);
    });
}

All we do in stutter_blink is call toggle on led followed by a delay_ms call from the arduino_uno module. This is all done in an iterator. We create a range (0..times) followed by calling map so that we can progressively delay the LED toggle by a noticeable amount. We could have definitely done this using a for loop and that would be more readable, but I wanted to demonstrate that we can use all the high level APIs and abstractions from Rust. We are writing functional code for an embedded systems where the abstractions are zero cost. That's a thing possible only in Rust as far as I know!

Here's the full code:



// main.rs

#![no_std]
#![no_main]

extern crate panic_halt;
use arduino_uno::prelude::*;
use arduino_uno::hal::port::portb::PB5;
use arduino_uno::hal::port::mode::Output;

fn stutter_blink(led: &mut PB5<Output>, times: usize) {
    (0..times).map(|i| i * 10).for_each(|i| {
        led.toggle().void_unwrap();
        arduino_uno::delay_ms(i as u16);
    });
}

#[arduino_uno::entry]
fn main() -> ! {
    let peripherals = arduino_uno::Peripherals::take().unwrap();

    let mut pins = arduino_uno::Pins::new(
        peripherals.PORTB,
        peripherals.PORTC,
        peripherals.PORTD,
    );

    let mut led = pins.d13.into_output(&mut pins.ddr);

    loop {
        stutter_blink(&mut led, 25);
    }
}

Let's try to build this crate:



cargo build

If all went fine, you should see an elf file rust-arduino-blink.elf generated under target/avr-atmega328p/debug/ directory. That's the binary we need to flash to our Uno. To flash the elf file, we'll use the avrdude utility. Let's create a script at the root directory named flash.sh that does cargo build followed by flashing it our uno:



#! /usr/bin/zsh

set -e

if [ "$1" = "--help" ] || [ "$1" = "-h" ]; then
    echo "usage: $0 <path-to-binary.elf>" >&2
    exit 1
fi

if [ "$#" -lt 1 ]; then
    echo "$0: Expecting a .elf file" >&2
    exit 1
fi

sudo -u creativcoder cargo build
avrdude -q -C/etc/avrdude.conf -patmega328p -carduino -P/dev/ttyACM0 -D "-Uflash:w:$1:e"

With that, we can run now run (make sure your Uno is connected via the USB cable):

./flash.sh target/avr-atmega328p/debug/rust-arduino-blink.elf

and there you go:

Our first blinking program on Arduino running Rust!

If you get a permission denied error when accessing /dev/ttyACM0. You may need to add your user
to a linux user group that has access to the serial interface.
First, we find the group using:

ls -l /dev/ttyACM0

I get the following output on my machine:

crw-rw---- 1 root uucp 166, 0 Aug 19 03:29 /dev/ttyACM0

To add your username to uucp group, we run:

sudo usermod -a -G uucp creativcoder

Suggestions/comments/corrections most welcome.

I have several embedded hobby projects in plan, I will be writing about them in future as they progress. Here's the Github for the code above.
If you want to follow the latest in developement in Rust embedded space, follow the embedded rust working group

Until next time!

How to add comment support on your Gatsby blog using Github utterances

creativcoder — Wed, 29 Jul 2020 08:21:58 +0000

Originally posted on my blog: creativcoder.dev

This post is about integrating comments support in your blog using a free and open source service.

Having a way to engage with your audience is probably the next step you can take if your blog is helping others in some way. Back when I had used hugo as my static site generator, I had used Disqus, which is a comments service/system. But as with ordinary third party services, Disqus is notorious for putting their own ads and can get quite slow. As a fan of open source and code reuse, I knew there had to be some open source comments service out there. After a day of sifting through the interwebs, I found a solution that I think for the time being serves my purpose of engaging with my audience.

What follows is a quick guide on how to integrate Github's utterances comments system into your blog. This also became an excuse for me stay updated with all the recent changes in the web dev space, as I've been mostly doing backend for the last two years.

Utternaces is a lightweight comments widget built on top of Github issues. Some of its highlights are:

Open source. 🙌
No tracking, no ads, always free. 📡
No lock-in. All data stored in GitHub issues. 🔓
Styled with Primer, the css toolkit that powers GitHub. 💅
Dark theme. 🌘
Lightweight. Vanilla TypeScript. No font downloads, JavaScript frameworks or polyfills for evergreen browsers. 🐦🌲

Target audience: You know ReactJS, and you probably know better than me and maybe can provide suggestions on how can we improve the integration.

Disclaimer: This comments system only works if your target audience has a Github account, which in majority of cases are developers. As my blog is mostly oriented towards developers, this aligns perfectly with my blog.

The official guide of utterances mentions integrating the comments widget on a vanilla HTML website. That won't work for my case as I happen to be running a site that is generated by GatsbyJS, which I think is a really efficient static site generator not only in terms of development experience but also in terms of performance of the generated sites compared to my past experiences with static site generators such as Hugo.

Gatsby uses React under the hood which meant that I needed to integrate utterances as a React component.

Note: I am by no means an expert on react or even a frontend expert, but the following steps
is me just sifting through bunch of documentation pages and tying to cobble them together into
a working solution.

So here's how I did it.

Installing utterances

First, I setup a Github repository (has to be a public repository) that will act
as a placeholder for issues to be created within: https://github.com/creativcoder/creativcoder.dev-comments
This is needed if you have a website that is not running as a Github pages site. If you happen to have your website as a Github repository, you can configure the same repository for utterances.

Next, we go to: https://github.com/apps/utterances page. You will see an 'Install' button in green on the right. Clicking that, you will need to provide the repository where you want to install the widget. I chose my comments repository above.

Post installation, you will be redirected to this page. In the 'Enabling Utterances' section, we need to place the following script in a div tag (or any container tag) where we want our comment widget to appear:

<script src="https://utteranc.es/client.js"
        repo="[ENTER REPO HERE]"
        issue-term="pathname"
        theme="github-light"
        crossorigin="anonymous"
        async>
</script>

As you can see, the script tag above has multiple attributes that can be configured. The important ones to look at are:

repo: should point to the repository you installed utterances above section.
issue-term: how utterances should match the issues with posts on a website. In my case, am using the title of the posts. You can refer to 'Blog Post <-> Issue Mapping' section in https://utteranc.es/ for more details and choose as per your preference.

Integrating the comment widget

Now as I said above, the script needs to be put in a container tag for us to render the comments widget. That translates to having a component in react, within which we'll append this script tag programmatically whenever a blog post page is rendered. This will need to happen conditionally as not all pages are about a blog post page, such as the index page and the about page.

To have a container for the widget to be created within, I first created a Comment react component (a functional component) in components/comment.js:

// commment.js

import {useRef, useEffect} from 'react'
import React from 'react';
import { useStaticQuery, graphql } from 'gatsby'

const Comment = ({commentBox}) => (<div ref={commentBox} className="comments"></div>)
export default Comment

It's a very trivial component. The only thing of intereset here is the commentBox react ref. React Refs provide a way to access DOM nodes or React elements created within a component's render method. We'll see how that is used later. It's not really recommended to use refs, as they are sort of an escape hatch but since we only have one use case for it here, we should be fine.

Next, I have a <Posts> component in my blog which renders each blog post. This is where I want the comment widget to appear at the end of each post. I needed a way to render the Comments component conditionally. To achieve that, I relied on the excerpt prop which is true if the rendered page is an index page, where only an excerpt of all blog posts are shown. In other cases it's set to false. We can use that to conditionally render the Comments component like so:

// components/posts.js
{ excerpt? <></>: <Comment commentBox={commentBox} />}

It's the usual ternary operator. The <></> syntax are fragments in react, which is empty in the true branch as we only want to render the widget when the user in on the blog post page. We also see that the comment widget has a commentBox prop being passed. This is how we gain access to the Comment component for use within the Posts component. We'll use this ref to append the comment script tag.

Back in my Posts component, I create a ref that was attached to the commentBox prop on Comment component:

// components/post.js
const commentBox = React.createRef()

Then, I use the useEffect hook to add the script tag to the Comment component via the ref:

  const commentBox = React.createRef()

  useEffect(() => {
    const scriptEl = document.createElement('script')
    scriptEl.async = true
    scriptEl.src = 'https://utteranc.es/client.js'
    scriptEl.setAttribute('repo', 'creativcoder/creativcoder.dev-comments')
    scriptEl.setAttribute('issue-term', 'title')
    scriptEl.setAttribute('id', 'utterances')
    scriptEl.setAttribute('theme', 'github-light')
    scriptEl.setAttribute('crossorigin', 'anonymous')
    if (commentBox && commentBox.current) {
      commentBox.current.appendChild(scriptEl)
    } else {
      console.log(`Error adding utterances comments on: ${commentBox}`)
    }
  }, [])

The code in useEffect will run everytime a Post component is rendered which will then append the comment widget to each blog post page. You can see that set the same script attributes are being added but with javascript. We then finally append it to the commentBox ref via its current property which is active when it is rendered.

With that done, I did just did a yarn deploy and what you see below is our shiny new comment widget 👇.
Hope you find this post helpful. Let me know if you have any issues setting it up in the comments below.

Until next time!