DEV Community: Justin Ethier

Troubleshooting a ZigBee PAN ID Conflict

Justin Ethier — Fri, 10 Nov 2023 15:12:30 +0000

ZigBee is a network protocol that allows for home and building automation using low power wireless controllers.

Last year I spent time troubleshooting a series of building networks which tore themselves apart shortly after being commissioned. In each case the network coordinator was raising a PAN ID conflict error and re-forming the network with a new PAN, causing devices to be stranded or split apart on two separate networks.

The Typical Cause of PAN ID Conflicts

This article explains how corrupt packets can cause a conflict. The suggested workaround on the SiLabs EmberZNet stack is to set a threshold to ensure the coordinator only takes corrective action if more than 63 conflicts are reported in a minute.

This threshold was in place on our building network, making packet corruption an extremely unlikely source of the problem.

Packet Captures to the Rescue

After taking several captures with the Simplicity Studio Network Analyzer a colleague found an inconsistency in ZigBee Beacon frames from various devices.

Consider the following frames from two different devices:

ZigBee Beacon [15 bytes]
   - Protocol Id: ZigBee Pro (0x00)
   -    .... 0010 = Stack Profile: ZigBee Pro (2)
   -    0010 .... = Network Protocol Version: 0x02
   -    .... .1.. = Router Capacity: true
   -    .000 1... = Depth: 0x01
   -    1... .... = End Device Capacity: true
   - Extended PAN ID: 0123456789ABCDEF
   - Tx Offset: 0xFFFFFF
   - NWK Update ID: 0x01

ZigBee Beacon [15 bytes]
   - Protocol Id: ZigBee Pro (0x00)
   -    .... 0010 = Stack Profile: ZigBee Pro (2)
   -    0010 .... = Network Protocol Version: 0x02
   -    .... .1.. = Router Capacity: true
   -    .111 1... = Depth: 0x0F
   -    1... .... = End Device Capacity: true
   - Extended PAN ID: FEDCBA9876543210
   - Tx Offset: 0xFFFFFF
   - NWK Update ID: 0x00

Based on these captures it became clear the root cause was due to an extended PAN ID that was reversed on some number of devices.

The ZigBee 3.0 Specification explains why this would be a problem:

3.6.1.13.1 Detecting a PAN Id Conflict
Any device that is operational on a network and receives an MLME-BEACON-NOTIFY.indication in which the PAN identifier of the beacon frame matches its own PAN identifier but the EPID value contained in the beacon payload is either not present or not equal to nwkExtendedPANID, shall be considered to have detected a PAN Identifier conflict.

This is exactly what was happening on the network! Everything would continue to operate normally but the mismatched EPID values were causing conflicts to be reported at a higher rate than our threshold value.

Once the threshold for these errors is exceeded (63 in a minute) the coordinator will select a new PAN ID and broadcast a network update to ask nodes to move to the new PAN. This is problematic because it often has the effect of splitting the network.

This also would only be a problem when devices on the network are sending beacon requests, such as when a device is searching for a network. Typically once a network is commissioned the EPID is not included in packets to save space since ZigBee is designed for low power consumption and low data rate applications:

Other than the scanning and joining processes, the EPID rarely appears in transmitted ZigBee packets due to its large overhead (8 bytes) in the header.

Conclusion

Fortunately for our team we were able to quickly identify a software bug that was the source of the reversed EPID and patch the system.

But this represents an important consideration for ZigBee networks. Sometimes issues only become apparent when deploying a large-scale distributed network, such as during a customer deployment. For example, the commissioning procedure that led us to the conflict was tested in-house. However despite having dozens of devices on the test system the number of conflicts being raised was not large enough to exceed the 63 per minute threshold. To an end user the network continued to operate as if nothing was wrong.

Perhaps more exhaustive testing would catch this before it hit the field. But that is often the case! With any large distributed system there will be some level of unintended behavior that - despite our best efforts - only manifests itself in a real-world application. We need to be prepared to deal with these unexpected issues when they do arise, and take the proper precautions to catch as many as possible before customers and production systems are affected.

A Git Branch and Release Strategy for Product Teams

Justin Ethier — Thu, 09 Mar 2023 01:28:55 +0000

This post presents a git branch/release strategy intended for use by a team providing long-term development and support for a software product.

The goal is to provide dedicated branches for QA and customer releases while isolating those branches from bleeding-edge development changes.

The Strategy

In this model the repository consists of three types of branches:

dev for all development.
qa to create pre-production builds for the test team.
release to create production builds for release to customers.

All code is merged from dev to qa to release by a team lead or other responsible party, as development and testing progresses.

The dev branch could just as well be main or whatever the repository's default branch is called.

There will typically be several pairs of QA and Release branches, each with their own version string appended. For example qa-1.0, release-1.1, etc.

The dev branch could be versioned as well if there is a need for long-term support of an older version of the software. For example dev-2. Its best if that can be avoided but for mature products there may be a need to support multiple major versions at the same time.

In summary, here is the graph of a set of branches to handle the 1.0 and 1.1 releases of an example project:

In each case there is more than one merge from dev to qa before we identify the final release build.

Code Reviews

An optional approach to lock down dev and only allow changes into it via merge request. That gives the team an opportunity to perform a code review prior to code landing in dev.

Such a policy would be team-dependent. It probably makes more sense on a larger team and/or for an established product where it is important to control code quality and limit risk.

In this model the actual development would take place on feature branches. For example dev-feature-1.

Continuous Integration and Deployment

Automated building and deployment is convenient to have for dev in almost all cases.

QA and Release merges are going to happen much less frequently than pushes to dev but when they do we are going to want a build ASAP. So continuous integration is going to be essential for these branches to ensure builds happen automatically.

Automated deployment may be useful as well depending on your product.

Tagging of Builds

Most teams are going to want their continuous integration script to apply a tag to QA and Release builds. That way there is full traceability into what went into each build as well as the ability to branch directly from the tag in case a hotfix or emergency patch is required.

Development builds are expected to be created frequently and tagging of them is probably not desirable.

Conclusion

This strategy is not a one-size-fits-all solution. But it can work well in practice for products requiring a formal development and release process.

How do you handle branches and releases for your products?

Using Backticks as Syntactic Sugar in JavaScript and Scheme

Justin Ethier — Thu, 23 Feb 2023 14:42:53 +0000

ECMAScript 6 introduced the concept of template literals to provide a convenient way to build up strings in JavaScript.

For example:

> let h = "Hello", w = "World";
> `${h} ${w}!
  ${h} ${w} from line 2`

"Hello World!
Hello World from line 2"

This is reminiscent of using backticks in Scheme to construct lists using quasiquotation:

> (let ((h 'hello)
      (w 'world))
  `(,h ,w !))

(hello world !)

Maybe its not a coincidence that template literals were called quasi-literals when originally proposed:

This scheme extends EcmaScript syntax with syntactic sugar to allow libraries to provide DSLs that easily produce, query, and manipulate content from other languages that are immune or resistant to injection attacks such as XSS, SQL Injection, etc.

Especially since there are no other commonly-used languages that use backticks for string interpolation.

Anyway, thought this was an interesting observation on the evolution of the JavaScript language.

How to Detect a Cycle in a Linked List

Justin Ethier — Sat, 11 Feb 2023 21:21:44 +0000

When developing Cyclone Scheme I discovered the latest R⁷RS Scheme language specification requires that several procedures handle circular lists.

For example when comparing objects for equality:

Even if its arguments are circular data structures, equal?
must always terminate.

We can't make a simple loop over the list because our code will keep running forever if one of the nodes points back to an earlier node.

So what to do?

Floyd's Tortoise and Hare Algorithm

Well, it turns out there is an elegantly simple solution:

Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values.

Let's demonstrate how it works.

We start with a linked list of 5 nodes, A through E. Each one is linked in alphabetical order except node E which links back to A, forming a cycle.

We will use two pointers to traverse the list. A slow pointer starting at the first node in the list, A, and a fast pointer starting at B:

Now we can make several iterations, each time advancing the slow pointer ahead one node and the fast pointer ahead by two nodes:

As you can see the fast pointer reaches E and starts back around at the front of the list. After four iterations it caches up to the slow pointer and both now point to E.

Since the pointers are moving at different speeds they can only point to the same node if there is a cycle.

A JavaScript Implementation

To implement a solution in JavaScript we start with the definition for each node in a singly-linked list:

class Node {
  constructor (val) {
     this.val = val;
     this.next = null;
  }
}

And here is our cycle detection algorithm. By having a fast and slow pointer traverse the list we can find cycles efficiently with only a small amount of code:

/**
 * @param {Node} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head === null) { return false; }

    var slow = head, fast = head.next;

    while (fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) return true;
    }

    return false;    
};

There is no need to check for slow === null because fast will always reach the end of the list first.

Also, we must ensure fast.next is not null before accessing fast.next.next.

Implementation in the Cyclone Scheme Runtime

Going back to my original problem, perhaps it would be interesting to briefly discuss a real-world application of this algorithm.

In Scheme lists are a fundamental data construct similar to linked lists in other languages. Their definition as a C structure is equivalent to Node above with a value stored in pair_car and pair_cdr pointing to the next pair_type object:

typedef void *object;
typedef struct {
  ... // Omit object header fields
  object pair_car;
  object pair_cdr;
} pair_type;

For various reasons the Cyclone runtime's implementation is more complicated than the JavaScript code above. Here is Cyclone's function to determine if a list contains a cycle.

Conclusion

And there you have it. Thanks for reading!

Note this problem is also popular now as a LeetCode interview question.

Career Development by Planting Acorns

Justin Ethier — Fri, 10 Feb 2023 16:32:41 +0000

Richard Hamming gave a famous talk called "You and Your Research" in which he had many great insights on doing world-class work, including this gem:

The great scientists often make this error. They fail to continue to plant the little acorns from which the mighty oak trees grow. They try to get the big thing right off. And that isn't the way things go.

Something to think about when moving to a new project, new role, or an unfamiliar tech stack. Take the time to learn the little things, put in the work, and give those seeds the proper time to grow...

Tail Call Optimization by Base Jumping off the Stack

Justin Ethier — Mon, 09 Jan 2023 21:13:38 +0000

Tail calls are the only means of iteration in most functional languages. So implementation support is absolutely critical.

For example, Scheme requires tail call optimization as part of its language specification (PDF):

3.5 Proper tail recursion

Implementations of Scheme are required to be properly tail-recursive. A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure might still return.

Over the years various solutions have been developed to meet this requirement such as trampolines, goto's, compiler optimizations, etc. One of the most unusual was proposed by Henry Baker in his paper CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. (PDF).

Cheney on the M.T.A.

Cheney on the M.T.A. requires writing a compiler and runtime. Code is converted into continuation passing style and compiled into a series of C functions. When the program runs these functions are called like normal C functions but they never return. The stack keeps growing and growing...

The program periodically checks to see if a stack size limit is reached. When that happens a Cheney copying garbage collector is used to copy live data from the stack to the heap. Once all the live objects on the stack are copied the program calls longjmp to go back to the bottom of the stack, calls into the next function, and keep going.

One way to think of this is that instead of using a trampoline we are going to BASE jump off the stack every so often:

On the one hand this is kind of insane 😮. Programs are not supposed to work this way!

Then again, recursive calls are guaranteed to never cause a stack overflow because everything is periodically cleared from the stack. Thus Cheney on the M.T.A guarantees tail call optimization.

In fact this approach provides all the "hard" stuff that a functional programming language runtime needs - tail call optimization, generational garbage collection, and continuations.

Implementation

Here are code examples from Cyclone Scheme demonstrating how Cheney on the M.T.A works in practice.

Cyclone's runtime uses the following function to set up a new trampoline. The bottom of the stack is explicitly marked using setjmp. After a garbage collection code will resume execution on the next line after setjmp. At that point the code finds the next function - gc->cont, our continuation - and calls into it:

void Cyc_start_trampoline(gc_thread_data * thd)
{
  // Tank, load the jump program
  setjmp(*(thd->jmp_start));

  if (obj_is_not_closure(thd->gc_cont)) {
    Cyc_apply_from_buf(thd, thd->gc_num_args, thd->gc_cont, thd->gc_args);
  } else {
    closure clo = thd->gc_cont;
   (clo->fn)(thd, clo, thd->gc_num_args, thd->gc_args);
  }

  fprintf(stderr, "Internal error: should never have reached this line\n");
  exit(1);
}

The snippet below demonstrates how C functions may be written using Baker's approach. All compiler-generated and primitive functions that call into other functions must be written in this style:

object Cyc_make_vector(object cont, object len, object fill) {
  object v = NULL;
  int i;
  Cyc_check_int(len);

  // Memory for vector can be allocated directly on the stack
  v = alloca(sizeof(vector_type));

  // Populate vector object
  ((vector)v)->tag = vector_tag;
  ... 

  // Check if GC is needed, then call into
  // continuation with the new vector
  return_closcall1(cont, v);
}

A macro return_closcall1 is used to check if the stack limit has been reached - if so a minor collection is triggered via GC(). Otherwise another macro closcall1 is used to call into the next function:

#define return_closcall1(td, clo, a1) {
 char top;
 object buf[1]; buf[0] = a1;
 if (stack_overflow(&top, (((gc_thread_data *)data)->stack_limit))) {
     GC(td, clo, buf, 1);
     return; // Never reached
 } else {
     closcall1(td, (closure) (clo), buf);                                      
     return; // Never reached
 }
}

And here is GC, the wrapper for Cyclone's minor garbage collector. The code retrieves locations of the top/bottom of the stack, calls into gc_minor to collect objects using Cheney's algorithm, and the calls longjmp to base jump back to the start of the trampoline:

void GC(void *data, closure cont, object * args, int num_args)
{
  char tmp;
  object low_limit = &tmp;      // This is one end of the stack...
  object high_limit = ((gc_thread_data *) data)->stack_start;

  int alloci = gc_minor(data, low_limit, high_limit, cont, args, num_args);
  ...

  // Let it all go, Neo...
  longjmp(*(((gc_thread_data *) data)->jmp_start), 1);
}

There is enough going on it gc_minor that it is outside the scope of this article. But the code is available on GitHub if you are curious.

Wrapping Up

That's all for now. Thanks for reading! 🎉

Tail Call Optimization in JavaScript using Trampolines

Justin Ethier — Thu, 29 Dec 2022 19:51:30 +0000

Continuing on the previous article in this series. With some preparation and slight modifications to our existing code we can perform tail call optimization (TCO) to make an unlimited number of recursive function calls in JavaScript!

Below is the full solution based on this example from Stack Overflow. We'll break everything down in a moment:

class Tco {        
  constructor(func) {
    this.func = func;
  }
  execute() {
    let value = this;
    while (value instanceof Tco)
      value = value.func(); 
    return value;  
  }
}

const tco = (f) => new Tco(f);

function adder(n) {
  const loop = (i) => tco(() => {
    if (i == n) {
      return n;
    }     
    return loop(i + 1);
  });

  return loop(0).execute();
};

console.log(adder(10)); 
console.log(adder(1000));
console.log(adder(100000));
console.log(adder(10000000));

pi@raspberrypi:~/Documents $ node adder.js 
10
1000
100000
10000000

Trampolines

The Tco class defines an object with an execute function that does the heavy lifting:

    let value = this;
    while (value instanceof Tco)
      value = value.func(); 
    return value;

This is an example of a trampoline. Sadly, there is no trampoline emoji or I would throw one in here. Anyhow, this while loop calls a function value.func() that returns either:

A Tco instance to indicate execution is still active. The trampoline will call into that instance again to make another recursive call, or
A different type of object indicating recursion is complete. This value is returned as the final result

Helper Function

A tco function is defined as a helper to make the syntax cleaner:

const tco = (f) => new Tco(f);

Modifying our Existing JavaScript Code

The adder function's inner loop is modified to return an instance of Tco via our helper function.

When we say return loop we are returning that instance to the caller rather than calling into loop directly!

Note the return n returns our final integer value, terminating the loop:

  const loop = (i) => tco(() => {
    if (i == n) {
      return n;
    } 
    return loop(i + 1);
  });

Finally, we begin our loop by instantiating a loop object and calling into its execute function to start the Tco object's while loop:

  return loop(0).execute();

Wrapping Up

While this pattern might not be a good idea for writing day to day code it can be a useful tool. Interpreters written in an imperative language such as JavaScript often use a trampoline to implement tail call optimization for the language that they are hosting. For example this would be an excellent start to the core of a Lisp interpreter in JavaScript.

And that's it! Thanks for reading 👍

What is Tail Call Optimization?

Justin Ethier — Tue, 27 Dec 2022 16:30:08 +0000

Recursive Calls in JavaScript

Programming languages often limit the number of nested calls a recursive function is allowed to make.

Consider this simple example in JavaScript. An adder function recursively calls an inner function loop exactly n times and returns n as the result:

function adder(n) {
  function loop (i) {
    if (i == n) {
      return n;
    }
    return loop(i + 1);
  }

  return loop(0);
}

console.log(adder(10));
console.log(adder(1000));
console.log(adder(100000));

This code works fine for small values of n. But with larger values eventually we run out of stack space and crash 💥

pi@raspberrypi:~/Documents $ node adder.js
10
1000

/home/pi/Documents/adder.js:2
  function loop (i) {
                ^
RangeError: Maximum call stack size exceeded

The problem is that loop keeps getting added to the call stack for subsequent i values:

adder(10)
loop(0)
loop(1)
loop(2)
loop(3)
...

Once we reach the end of the stack we are done. And there is only 492 Kb of stack space on our test system:

pi@raspberrypi:~/Documents $ node --v8-options | grep -B0 -A1 stack_size
  --stack_size (default size of stack region v8 is allowed to use (in kBytes))
        type: int  default: 492

Tail Call Optimization

This is where we leave off with JavaScript (for now).

But there is more to the story. Some other languages and tooling support a concept called tail call optimization (TCO) that prevents the call stack from growing indefinitely.

In a language with TCO the call stack grows no larger than:

adder(10)
loop(...)

Subsequent calls to loop are not added to the stack. Or at least conceptually we can view it this way - the actual implementation details can vary from language to language. But the point is that the stack no longer grows indefinitely, so we can make unlimited use of recursive functions.

Recursive Calls in Scheme

For example, adder works just fine when implemented in Scheme, which requires TCO as part of its language specification:

(import (scheme base) 
        (scheme write))

(define (adder n) 
  (define (loop i)
    (if (= i n)
        n
        (loop (+ i 1))))
  (loop 0))

(write (adder 10)) (newline)
(write (adder 1000)) (newline)
(write (adder 100000)) (newline)
(write (adder 10000000)) (newline)

pi@raspberrypi:~/Documents $ cyclone adder.scm
pi@raspberrypi:~/Documents $ ./adder
10
1000
100000
10000000

The code runs fine even for a massive value such as 10,000,000.

Conclusion

So, does tail call optimization make Scheme "better" than JavaScript? Not at all! Each language just emphasizes a different coding style. Functional languages such as Scheme, Haskell, and Erlang typically use recursion for looping. Without TCO they would be useless.

In contrast imperative languages such as JavaScript, Go, and C use iteration for looping with for, foreach, while, and friends. Since this is the widely accepted style there just isn't a need to optimize for recursion in these languages.

Alright, that's all for now.
Cheers! 🎉

Building a Log-Structured Merge Tree in Go

Justin Ethier — Thu, 15 Dec 2022 22:08:22 +0000

Introduction

Last year I read more challenging projects every programmer should try and decided to take a deep dive into researching solutions for a key-value data store.

There are two major technologies used in this space. Relational databases typically use B-trees to persistently store data. Alternatively many newer storage solutions use the log-structured merge tree (LSM tree).

LSM trees are specifically designed to handle write-heavy workloads. They are used in many popular NoSQL databases including Apache Cassandra, Elasticsearch, Google Bigtable, Apache HBase, and InfluxDB. As well as embedded data stores such as LevelDB and RocksDB.

This article provides implementation details for the LSM tree based project keyva that I wrote to better understand how all of this works. The details are generic and cover concepts applicable to other LSM tree implementations.

High-Level Design

Data is always added to an LSM tree using sequential writes. This append-only approach allows for blazingly fast write operations but does require subsequent compaction to free extra records written when a key is updated or deleted.

The MemTable, a data structure stored entirely in memory, is initially used to store new data. Operations here are very fast but space is limited and the data cannot be retained if the process is restarted.

In order to recover data across restarts, the same data is also appended to a Write Ahead Log (WAL). The WAL is a simple append-only log that contains a single record for each operation made to the LSM tree.

Eventually the MemTable will become too large to efficiently hold in memory and the data is flushed to a Sorted String Table (SST) file on disk. SST files are indexed and immutable, allowing fast concurrent data access. Eventually when enough SST files are generated a background job will compact them and merge the data into a new "level" of SST files. This gives the tree a chance to remove redundant records and efficiently re-organize data.

SST files can efficiently serve large data sets. For example, Google Bigtable uses log-structured storage and is designed to scale to the petabyte range across a cluster of servers.

Data Model

Records

Keyva uses a LSM tree to store data in terms of key/value pairs. Each key is an UTF-8 encoded string and each value is a sequence of bytes.

Inserts and Updates

A new key/value is inserted into the LSM tree by first being added to the MemTable and WAL, as depicted in the high level design.

You may be surprised to learn that an update is added to the LSM tree in the exact same manner as an insert!

The only difference for an update is that if the key already resides in the MemTable it will be overwritten with the new value. But if an existing key has already been flushed to disk as part of an SST file the old data will remain on disk for some time until the new key/value from the update is eventually merged into that SST level.

So, both insert and update operations are incredibly efficient but their simplicity makes read a bit more complicated. Let's look at that next.

Reads

So, when reading data an LSM tree must find the most recent value for a given key. Thus any read operation must start with the MemTable before moving to SST level 0, level 1, etc.

Once read finds a key it will return with that first value that it has found. So in the case of an update it will simply ignore any previous values for a key that still reside in higher SST levels.

Deletes

Data cannot be deleted directly from an SST. Instead the key is flagged as deleted and the data is deleted later when the SST is compacted. These flagged records are called tombstones.

You can see the Deleted flag used in our implementation:

type SstEntry struct {
    Key     string
    Value   []byte
    Deleted bool
}

Value may be stored as an empty array for a deleted record, so at least we save a bit of space there.

Unfortunately a tombstone cannot be immediately removed when its SST is compacted. In order to guarantee all of the old records for a key are removed the tombstone must reach the highest SST level in the tree. At that point it can be safely removed along with any corresponding value(s) for the key.

Write Amplification

Write amplification is the ratio of the amount of data written to the LSM tree versus the amount of data written to disk. The same data may be written to disk multiple times as a key/value is promoted from one level of the SST to another. To increase performance an important consideration is to minimize the number of repeated disk writes.

Data Structures

MemTable

All data added to the LSM tree is initially stored in Memtable, essentially an in-memory cache.

Data in the MemTable needs to be arranged for fast access and ideally for low-cost concurrent read/write operations. A self-balanced tree such as a red-black tree can work well for this purpose. Our implementation uses a skip list.

If a key already exists in the table when a request is received the value will be updated directly. This is different than the other data structures employed by the LSM tree, which are immutable.

Deletes must be retained in the table as well. It is important to store a tombstone in case the key still contains data in the SST. The deletion will be resolved later when we compact SST files.

Finally, when the MemTable reaches a certain threshold it must be flushed to disk. A potential optimization here is to allocate a new MemTable and designate the current MemTable as read-only. The old table can then be set off to the side for a background job to write it to disk.

Write Ahead Log

The WAL is a plain-text file containing a dump of all operations on the table. Essentially a transaction log of all operations on the MemTable.

This allows reconstructing the in-memory portion of the tree in the event of service restart for data that has not been flushed to SST yet.

In our implementation a separate WAL file is used for each MemTable. After a MemTable is written to disk its WAL file is purged, as the data is now retained in persistent storage by an SST. This prevents infinite growth of the WAL.

Finally, data is not organized efficiently within the WAL. So we only want to use it as a means of data recovery for the MemTable.

Sorted String Table

SST files are the primary data representation for storing an LSM tree on disk. Each one contains a series of key/values sorted by key:

Each file is immutable, making it easier to access data concurrently.

Sparse Index

A sparse index may be used to find data contained in an SST file. The index does not need to contain all keys since data is sorted. Instead it may include every Nth key.

Bloom Filter

A bloom filter is used to determine if an SST might contain a key before we check the SST. If the bloom filter cannot find a key then we know the key cannot be contained in the corresponding SST.

This helps speed up read operations by reducing the amount of disk accesses when reading data:

Data Layout

Level

SST files are organized into a series of multiple levels starting at level 0. Each level contains more data than the last and the maximum number of levels is configurable. Each level also contains multiple SST files. For example consider the following SST files in level 0:

As shown above files at level 0 may contain overlapping data. For example, observe how the first file contains a key for "Tucson" while the first key in the second file is "Atlanta".

This ordering is necessary as files are added on-demand as the MemTable reaches capacity. The problem is that in order to find the most recent value for a key in level 0 each SST file must be checked. We need to start from the most recent file and work back to the oldest file.

Higher levels are arranged more efficiently. Consider the same data after being merged to level 1:

As you can see data is guaranteed to be in sorted order across all files in this level. A single binary search may be used to find the SST file containing a given key.

As a result we probably want to minimize the amount of data in level 0, especially for a large dataset.

Each subsequent SST level will contain more data than the previous. However if each subsequent level contains an order of magnitude more data than the previous there do not need to be many levels.

Segment

Data is divided into segments on disk, one per SST file.

Each segment also contains a header (sequence number) and an index.

Block

Data within an SST is divided into blocks. There is one sparse index per block.

SST files may be binary files that are optionally compressed to save space.

Merge

A k-way merge algorithm is used to combine data from many SST files into a new series of SST files. Or alternatively to compact data within a single SST level.

In keyva, sst.Compact implements a streaming merge algorithm intended to scale up to large datasets. For each SST file a single record containing the latest string and a file handle are added to a min heap. The next record for the output file is then taken from the top of the heap and written to the current output SST file. A new record from the source SST is added back to the heap, and the process continues until all SST data is merged.

By using a min heap we can efficiently write new SST data in sorted order even if we are merging data from a large number of source SST files.

Data can be merged at regular intervals or at certain thresholds. For example a time series database might merge data at certain time intervals (daily, hourly, etc).

Conclusion

And there you have it. Thanks for reading!

The full source code for my sample implementation is available on pkg.go.dev.

References

Key-value database (Wikipedia)
B-tree data structure (Wikipedia)
How I built a key value store in Go (web)
Badger: Fast key-value DB in Go (GitHub)
Awesome Go Storage (GitHub)
LSM tree paper (PDF)
SSTable and Log Structured Storage: LevelDB (web)
Log Structured Merge Trees (web)

Porting a simple Mark-Sweep Garbage Collector to Zig

Justin Ethier — Fri, 20 May 2022 18:21:42 +0000

I recently completed my first Zig project - a port of Bob Nystrom's simple mark-sweep garbage collector (a modern classic!) from C to Zig.

Since Zig is a relatively new language I thought it would be helpful to give an overview of the experience and talk about the tooling.

This post explains a few parts of the program but I can't do justice to Bob's original article which I highly recommend reading. His C implementation is included in the project repo and is also available on GitHub.

Anyway, off we go...

Installing Zig

The installation process is very simple. Just download the latest version from the Releases page, extract to a folder, and add to your path.

For example here is how Zig is installed for this project's continuous integration:

wget https://ziglang.org/download/0.9.1/zig-linux-x86_64-0.9.1.tar.xz
tar xf zig-linux*.tar.xz
echo "`pwd`/zig-linux-x86_64-0.9.1" >> $GITHUB_PATH

A real installation would put the files somewhere more appropriate but this works just fine for our CI.

zig comes as a large statically-linked executable. No dependencies required 👍.

Vim Plugin

Out of the box Vim works well enough as an editor for Zig but the experience is a bit underwhelming. So I installed the Vim configuration for Zig plugin get syntax highlighting.

As an unexpected bonus:

This plugin enables automatic code formatting on save by default using zig fmt.

Much like with Go its super handy to be able to just not worry about code formatting. On top of that zig fmt also catches basic syntax errors:

I tend to save frequently when coding so this provides constant feedback on the state of the code.

Printing

I just used debug printing to write output:

const print = @import("std").debug.print;
print("Collected {} objects, {} remaining.\n", .{ numObjects - self.numObjects, self.numObjects });

An interesting observation is that instead of C varargs Zig uses an anonymous struct.

While Loops, If's, Optionals, and More

Zig has many improvements over standard C syntax.

Increment as part of the loop:

while (i < self.stack_size) : (i += 1) {

Unbox optionals:

while (object.*) |obj| {
if (object.data.pair.head) |head| {

Handle error unions:

var a = vm.pushPair() catch unreachable;

Other miscellaneous improvements over C include standard naming conventions (underscores in names for non-callable variables) and a cleaner boolean type.

It is also helpful to define functions as part of a struct type, allowing a more natural organization of code. Though this has been a standard feature in most languages for a long time now. Including C++.

Pointers

The sweep function uses a pointer-to-pointer to walk the linked list of all objects and unlink unused objects:

void sweep(VM* vm)
{
  Object** object = &vm->firstObject;
  while (*object) {
    if (!(*object)->marked) {
      /* This object wasn't reached, so remove it from the list and free it. */
      Object* unreached = *object;

      *object = unreached->next;
      free(unreached);

      vm->numObjects--;
    } else {
      /* This object was reached, so unmark it (for the next GC) and move on to
       the next. */
      (*object)->marked = 0;
      object = &(*object)->next;
    }
  }
}

Perhaps surprisingly, this function can be expressed line for line in Zig, just with a fresh new syntax.

fn sweep(self: *VM) void {
    var object = &(self.first_object);
    while (object.*) |obj| {
        if (!obj.marked) {
            // This object wasn't reached, so remove it from the list and free it.
            var unreached = obj;

            object.* = obj.next;
            self.allocator.destroy(unreached);

            self.num_objects -= 1;
        } else {
            // This object was reached, so unmark it (for the next GC) and move on to
            // the next.
            obj.marked = false;
            object = &(obj.next);
        }
    }
}

Testing

All of the tests were ported over to test declarations. These can be invoked via zig test mark-sweep.zig:

test "test 1" {
    const allocator = std.testing.allocator;
    print("Test 1: Objects on stack are preserved.\n", .{});

    var _vm = try VM.init(allocator);
    var vm = &_vm;
    try vm.pushInt(1);
    try vm.pushInt(2);

    vm.gc();

    try std.testing.expect(vm.num_objects == 2);
    vm.deinit();
}

Another important point! In Zig one does not call malloc to allocate memory. Instead one of many allocators is used to allocate memory in the way that is most appropriate for the situation at hand. Our code is organized like a typical library where any allocator may be passed in and retained for memory allocations over the life of a VM instance.

For testing we use testing.allocator which fails the test case if any memory is leaked. This enhances our test as vm.deinit() removes all of the root objects and performs a collection. If our code is working properly all allocated memory will be freed.

Debugging with gdb

Having debugged C extensively gdb I was shocked that it Just Works for debugging Zig code:

justin@ubuntu:~/Documents/zig-mark-sweep-gc$ make
zig build-exe mark-sweep.zig
justin@ubuntu:~/Documents/zig-mark-sweep-gc$ ./mark-sweep 
Performance Test.
Collected 20000 objects, 0 remaining.
justin@ubuntu:~/Documents/zig-mark-sweep-gc$ gdb mark-sweep 
GNU gdb (Ubuntu 9.1-0ubuntu1) 9.1
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from mark-sweep...
(gdb) break VM.sweep
Breakpoint 1 at 0x23091c: file /home/justin/Documents/zig-mark-sweep-gc/mark-sweep.zig, line 91.
(gdb) run
Starting program: /home/justin/Documents/zig-mark-sweep-gc/mark-sweep 
Performance Test.

Breakpoint 1, VM.sweep (self=0x7fffffffd938) at /home/justin/Documents/zig-mark-sweep-gc/mark-sweep.zig:91
91              var object = &(self.first_object);
(gdb) n
92              while (object.*) |obj| {
(gdb)

Conclusion

That's it for now. All in all this was a great first experience with Zig and I look forward to writing more Zig in the near future.

Useful links:

Kaprekar's Constant in JavaScript

Justin Ethier — Sat, 07 May 2022 23:33:18 +0000

So I was scrolling TikTok's the other day, as one does, when I saw the number 6174 featured in one of the videos. Turns out this is a special number called Kaprekar's constant, named after Indian mathematician D. R. Kaprekar.

Start with a four-digit number with at least two different digits. If a number has less than four digits we can pad it with zeros. For example, 42 becomes 0042.

Arrange the digits from largest to smallest and again from smallest to largest to get maximum and minimum values.
Subtract minimum from maximum.
Repeat these steps.

The result will always converge to 6174 after a small number of iterations.

For example,

628
8620 - 268 = 8352
8532 - 2358 = 6174

It's tedious to do this work by hand, though. Let's write some code to explore Kaprekar's algorithm further!

From Concept to Code

The core algorithm may be implemented in JavaScript as follows.

First we convert a given number to a string padded with leading zeros:

> var num = 423;
> num.toString().padStart(4, '0');
'0423'

Then we split the digits into an array so we can arrange them into our minimum and maximum numbers. The array operations are performed in-place, so a new array is created for each value:

> var min = num.split('').sort()
[ '0', '2', '3', '4' ]
> var max = num.split('').sort().reverse()
[ '4', '3', '2', '0' ]

Finally we use join to convert each array back into a string and parseInt to convert those back to numbers so we can subtract the values:

> parseInt(min.join(''))
234
> parseInt(max.join(''))
4320

JavaScript Implementation

The final code incorporates a validate function to reject numbers without multiple digits and runs our algorithm automatically using a random four-digit number:


    
validate = function (num) {
  for (var i = 0; i < 10000; i += 1111) {
    if (num == i) {
      return false;
    }
  }
  return true;
}

kaprekar = function (num) {
  if (!validate(num)) {
    console.log("Invalid number " + num);
    return;
  }
  console.log(num);
  while (num != 6174) {
    var str = num.toString().padStart(4, '0');
    var max = parseInt(str.split('').sort().reverse().join(''));
    var min = parseInt(str.split('').sort().join(''));
    num = max - min;
    console.log(num);
  }
}

var n = Math.random() * 10000 | 0; // from https://stackoverflow.com/a/61696576
kaprekar(n);

But wait, there's more!

Here is a variation of the program that generates a histogram of many iterations it takes to reach 6174 for all four-digit numbers.


    
counts = {};

validate = function(num) {
  for (var i = 0; i < 10000; i += 1111) {
    if (num == i) {
      return false;
    }
  }
  return true;
}

kaprekar = function(num) {
  var count = 0;
  if (!validate(num)) {
    return;
  }
  while(num != 6174) {
    str = num.toString().padStart(4, '0');
    max = parseInt(str.split('').sort().reverse().join(''));
    min = parseInt(str.split('').sort().join(''));
    num = max - min;
    count++;
  }
  counts[count] = counts[count] || 0;
  counts[count]++;
}

for (var i = 1; i < 10000; i++) {
  kaprekar(i); 
}
console.log(counts);

Running this code you can see we reach 6174 after at most seven iterations:

{ '0': 1,
  '1': 383,
  '2': 576,
  '3': 2400,
  '4': 1272,
  '5': 1518,
  '6': 1656,
  '7': 2184 }

Conclusion

And that's it! Hope you enjoyed this fun little tidbit.

Please feel free to leave your thoughts in the comments ☀️ 😄 👍

How to use jQuery CSS selectors in vanilla JavaScript ?

Justin Ethier — Fri, 06 May 2022 21:27:43 +0000

One of the best features of jQuery is the use of CSS selectors to reference elements, EG: $('#my-id').

How can I use selectors when writing vanilla JavaScript?