Anantha Kumaran

Dark Mode Toggle

2020-05-09T00:00:00+00:00

I switch a lot between dark and light themes based on the ambiance. The addition of dark mode in macOS helped a lot. But to toggle the theme, one still has to do a lot of clicks. So I decided to spend some time and automate the whole process. Now with a single command, I can switch the theme of all the applications I care about.

System Dark Mode

The most important one is the OS Dark Mode. Most of the applications automatically switch themes based on the Dark Mode. The Applescript code below enables Dark Mode, to disable Dark Mode use set dark mode to false.

tell application "System Events"
    tell appearance preferences
        set dark mode to true
    end tell
end tell

Terminal

The terminal app comes with its own theme preference. The following AppleScript switches the theme across all windows and tabs within.

tell application "Terminal"
    repeat with w from 1 to count windows
        repeat with t from 1 to count tabs of window w
            set current settings of tab t of window w to (first settings set whose name is "Solarized_Dark")
        end repeat
    end repeat
end tell

Tmux

I use the powerline plugin to manage the tmux status line theme and content. Overwriting the powerline config and reloading the tmux conf would switch the theme.

cp ~/.config/powerline/colorschemes/tmux/solarized-dark.json ~/.config/powerline/colorschemes/tmux/solarized.json
tmux source-file ~/.tmux.conf

Emacs

Emacs has a client-server model builtin. The GUI will act as a server that can be controlled by clients from the command line. To enable the server, call (server-start) on initialization.

function emacs-running() {
    if pgrep Emacs > /dev/null
    then
        return 0
    else
        return 1
    fi
}

if emacs-running
then
    emacsclient --eval "(load-theme 'solarized-dark)" > /dev/null
fi

Generate XLSX with unlimited rows

2019-08-17T00:00:00+00:00

In my previous post I have talked about Elixir stream. In this post I am going to talk about a particular use case. How would one approach the problem of generating a Excel spreadsheet with unlimited number of rows. The main constrain is that we only have a limited memory available.

The first part of the problem is to understand the XLSX file format. I won’t get into the details here, but there is a nice article about the anatomy of the XLSX file. In essence, XLSX is just a zip file with different file extension.

$ unzip -q -d spreadsheet spreadsheet.xlsx
$ tree -C spreadsheet/
spreadsheet/
├── [Content_Types].xml
├── _rels
├── docProps
│   ├── app.xml
│   └── core.xml
└── xl
    ├── _rels
    │   └── workbook.xml.rels
    ├── sharedStrings.xml
    ├── styles.xml
    ├── workbook.xml
    └── worksheets
        └── sheet1.xml

Except sheet1.xml, other xml files are just made of static contents that will be nearly the same size regardless of the number of rows.

Now we have two smaller problems

1) can we generate xml using stream.

2) can we combine multiple xml stream and generate a zip stream.

Let’s start with the xml problem. In abstract sense, xml document is a tree structure. To print a xml document, we have to first print the open tag <tag> and all its children and the close tag </tag>. Let’s say we do a pre-order like traversal, at any point in time, we have to keep the list of parent nodes in a stack like data structure. Essentially at minimum we would need memory proportional to the depth of the tree. Fortunately, most of the xml documents we deal in real world won’t have much depth. In our case with spreadsheet, the max depth would be less than 10.

Let’s take the example of generating html table. Consider the case of generating table with unlimited rows and unlimited cells within each row.

import XmlStream

rows = Stream.map(1..1000_000, fn row ->
  Stream.map(1..1000, fn cell ->
    {row, cell}
  end)
end)

element(
  "table",
  Stream.map(rows, fn row ->
    element(
      "tr",
      Stream.map(row, fn {row_index, cell_index} ->
        element("td", content("row #{row_index} cell #{cell_index}"))
      end)
    )
  end)
)
|> XmlStream.stream!

We have a nested stream called rows and a xml document constructed based on that stream using primitives like element and content. element takes tag name as the first argument. The second argument represents the children, it could be a either a stream or a text generated using content.

XmlStream.stream! is the one which does the real work. It takes a xml document and returns a byte stream. Essentially it does a pre-order traversal of the xml nodes and emits the required tags whenever it enters and exists a node.

Even though the approach makes sense, we haven’t explained how to do a pre-order traversal using Stream module. There is no Stream.traverse function, but it’s quite trivial to implement a traverse function on top of Stream.flat_map

def traverse(stream, leaf?) do
  Stream.flat_map(stream, fn node ->
    if leaf?.(node) do
      [:leaf, node]
    else
      Stream.concat([
          [:node_start],
          traverse(node, leaf?),
          [:node_end]
      ])
    end
  end)
end

traverse(rows, &is_tuple/1)
|> Stream.each(&IO.inspect/1)
|> Stream.run

The important part is the recursive call. The callback function passed to Stream.flat_map can return either normal list or another stream. In case of stream, it will be forced which will trigger another Stream.flat_map and so on. At any point in time, we will have at max only one active stream per level of depth. A full implementation of XmlStream can be found at activesphere/xml_stream. Even though the code might look complicated, the essential principle is the same.

Now that we have solved the first problem, how could we combine these xml streams and generate a zip file.

If we look at the overview of the zip file format in the specification, we can find two important headers: local file header and central directory header.

[local file header 1] ────────────────────
[encryption header 1]
[file data 1]
[data descriptor 1]
.
.
.
[local file header n]
[encryption header n]
[file data n]
[data descriptor n]
[archive decryption header]
[archive extra data record]
[central directory header 1] ─────────────
.
.
.
[central directory header n]
[zip64 end of central directory record]
[zip64 end of central directory locator]
[end of central directory record]

local file header signature     4 bytes  (0x04034b50)
version needed to extract       2 bytes
general purpose bit flag        2 bytes
compression method              2 bytes
last mod file time              2 bytes
last mod file date              2 bytes
crc-32                          4 bytes
compressed size                 4 bytes
uncompressed size               4 bytes
file name length                2 bytes
extra field length              2 bytes
file name (variable size)
extra field (variable size)

central file header signature   4 bytes  (0x02014b50)
version made by                 2 bytes
version needed to extract       2 bytes
general purpose bit flag        2 bytes
compression method              2 bytes
last mod file time              2 bytes
last mod file date              2 bytes
crc-32                          4 bytes
compressed size                 4 bytes
uncompressed size               4 bytes
file name length                2 bytes
extra field length              2 bytes
file comment length             2 bytes
disk number start               2 bytes
internal file attributes        2 bytes
external file attributes        4 bytes
relative offset of local header 4 bytes
file name (variable size)
extra field (variable size)
file comment (variable size)

Both local file header and central directory header contain fields like crc-32 and compressed and uncompressed file size, which can’t be calculated beforehand in our case. Fortunately, these fields are optional in the local file header and could be set to 0. The irony with zip format is that, if we write it in a streaming way, we can’t read it back in a streaming way.

Zstream.zip([
  Zstream.entry("xl/worksheets/sheet1.xml", sheet1_stream),
  Zstream.entry("xl/worksheets/workbook.xml", workbook)
])
|> Stream.into(File.stream!("spreadsheet.xlsx"))
|> Stream.run

Assume we expose an interface like the above, we could use a combination of Stream.flat_map and Stream.transform.

def zip(entries) do
  Stream.concat([
    [{:start}],
    Stream.flat_map(entries,
      fn %{stream: stream, name: name, options: options} ->
        Stream.concat(
          [{:head, %{name: name, options: options}}],
          stream
        )
      end),
    [{:end}]
  ])
  |> Stream.transform(fn -> %State{} end, &construct/2, &free_resource/1)
end

The entries are flat mapped and extra annotations are added, so we know when a file stream starts and when it ends. The construct function will then just emit correct zip headers and keep track of the list of files and their size in the state.

defp construct({:start}, state) do
defp construct({:end}, state) do
defp construct({:head, header}, state) do
defp construct(chunk, state) do

When all the streams are emitted and it hits the :end annotation, the central directory headers will be emitted based on the data in the state.

The only time we need to use unbounded memory is for the state where we keep track of the central directory headers. But as we use very small amount of memory per file, this should not be an issue in real world. The full source code of the library can be found at ananthakumaran/zstream

Grouping Elasticsearch slow log queries

2019-06-12T00:00:00+00:00

Elasticsearch provides the ability to log slow search queries that exceed a certain threshold. When enabled, all the search queries that exceed the given threshold are written to /var/log/elasticsearch/${cluster_name}_index_search_slowlog.log. A typical line in the slow log file looks like

[2017-09-10T12:35:53,355][WARN ][index.search.slowlog.fetch] [GOgO9TD]
[testindex-slowlogs][0] took[150.6micros], took_millis[0], types[],
stats[], search_type[QUERY_THEN_FETCH], total_shards[5],
source[{\"query\":{\"match\":{\"name\":{\"query\":\"Nariko\",\"operator\":\"OR\",\"prefix_length\":0,\"max_expansions\":50,\"fuzzy_transpositions\":true,\"lenient\":false,\"zero_terms_query\":\"NONE\",\"boost\":1.0}}},\"sort\":[{\"price\":{\"order\":\"desc\"}}]}]

This information might be enough for simple use cases. But if one operates at scale and if the system is used by multiple teams with wildly different queries, then manually going through every line is not possible.

A simple solution is to parse the text into structured data which can be then ingested into a centralized logging system like Graylog or ELK.

{
                 "node" => "GOgO9TD",
                "shard" => 0,
               "source" => '{"query":{"match":{"name":{"query":"Nariko","operator":"OR","prefix_length":0,"max_expansions":50,"fuzzy_transpositions":true,"lenient":false,"zero_terms_query":"NONE","boost":1.0}}},"sort":[{"price":{"order":"desc"}}]}',
                 "took" => "150.6micros",
                "stats" => "",
                "level" => "WARN",
             "@version" => "1",
                "index" => "testindex-slowlogs",
      "local_timestamp" => "2017-09-10T12:35:53",
           "@timestamp" => 2017-09-10T05:35:53.000Z,
                 "host" => "Ananthas-MacBook-Pro.local",
         "total_shards" => 5,
                "types" => "",
          "search_type" => "QUERY_THEN_FETCH",
          "took_millis" => 0
}

Now we can find queries that took more than 500 ms or group the logs based on a field like level, etc. But there are still some cases where this is not sufficient. Let say we want to see the top 10 slow queries based on the count, we can’t simply group based on the source field. Even though the query structure will be the same, the argument of each query operator might differ for each slow log. What we might find useful is something like parameterized sql query, where all the variables are represented as ?

{
    "source_normalized" => '{"query":{"match":{"name":{"boost":1.0,"fuzzy_transpositions":true,"lenient":false,"max_expansions":50,"operator":"OR","prefix_length":0,"query":"?","zero_terms_query":"NONE"}}},"sort":[{"price":{"order":"desc"}}]}'
    "source_id"         => "289972b28"
}

Once we have that, we could just take the hash of the source_normalized field and group based on it. source_id is just the first 8 characters of md5(source_normalized).

We have written a logstash plugin which does exactly this. All you need to do is install the plugin and add the filter configuration for slow log files.

filter {
  elasticsearchslowlog {
  }

  date {
    match => ["local_timestamp", "ISO8601"]
    timezone => "Asia/Kolkata"
  }
}

Country flags rendered using shaders

2019-02-17T00:00:00+00:00

precision mediump float;

void main() {
  gl_FragColor = vec4(0.0196, 0.4706, 0.2471, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  float y = xy.y;
  vec3 color = vec3(0.0039, 0.5765, 0.3333) * flip(0.666, 1.0, y) +
               vec3(0.9882, 0.7922, 0.0902) * flip(0.333, 0.666, y) +
               vec3(0.1961, 0.4157, 0.7373) * flip(0.000, 0.333, y);
  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  float x = xy.x;
  vec3 color = vec3(0.0000, 0.1255, 0.5412) * flip(0.000, 0.333, x) +
               vec3(1.0, 1.0, 1.0) * flip(0.333, 0.666, x) +
               vec3(0.9176, 0.1412, 0.1961) * flip(0.666, 1.0, x);
  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  vec3 color = vec3(0.0039, 0.4863, 0.2784) * flip(0.000, 0.4, xy.x) +
               vec3(0.8980, 0.0627, 0.1569) *
                   flip(0.00001, 0.5, flip(0.4, 1.0, xy.x) * xy.y) +
               vec3(0.9882, 0.7922, 0.0902) *
                   flip(0.5, 1.0, flip(0.4, 1.0, xy.x) * xy.y);
  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  vec3 color =
      vec3(0.8353, 0.0980, 0.1412) * flip(0.0001, min(0.5, xy.x), xy.y) +
      vec3(1.0, 1.0, 1.0) * flip(max(0.5, 1.0 - xy.x), 1.0, xy.y) +
      vec3(0.0824, 0.2745, 0.4863) *
          flip(xy.x, 1.0 - xy.x, xy.y * flip(0.0, 0.5, xy.x));
  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  vec3 color =
      vec3(1.0, 1.0, 1.0) *
          flip(0.001, 2.0 / 5.0, flip(0.0, 2.0 / 8.0, xy.x) * xy.y) +
      vec3(1.0, 1.0, 1.0) *
          flip(0.001, 2.0 / 5.0, flip(3.0 / 8.0, 1.0, xy.x) * xy.y) +
      vec3(1.0, 1.0, 1.0) *
          flip(3.0 / 5.0, 1.0, flip(0.0, 2.0 / 8.0, xy.x) * xy.y) +
      vec3(1.0, 1.0, 1.0) *
          flip(3.0 / 5.0, 1.0, flip(3.0 / 8.0, 1.0, xy.x) * xy.y) +
      vec3(0.0196, 0.2157, 0.4941) * flip(2.0 / 5.0, 3.0 / 5.0, xy.y) +
      vec3(0.0196, 0.2157, 0.4941) * flip(2.0 / 8.0, 3.0 / 8.0, xy.x) -
      vec3(0.0196, 0.2157, 0.4941) *
          flip(2.0 / 8.0, 3.0 / 8.0, xy.x * flip(2.0 / 5.0, 3.0 / 5.0, xy.y));
  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

vec3 overlay(vec3 background, float t, vec3 foreground, float u) {
  return background * t + foreground * u - background * u;
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  vec3 blue = vec3(0.0235, 0.2314, 0.5843);
  vec3 white = vec3(1.0, 1.0, 10);
  vec3 red = vec3(0.8353, 0.1686, 0.1843);
  vec3 color =
      overlay(overlay(overlay(overlay(blue, 1.0, white,
                                      flip(2.0 / 5.0, 3.0 / 5.0, xy.y)),
                              1.0, white, flip(2.0 / 8.0, 3.0 / 8.0, xy.x)),
                      1.0, red, flip(2.25 / 5.0, 2.75 / 5.0, xy.y)),
              1.0, red, flip(2.25 / 8.0, 2.75 / 8.0, xy.x));
  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}
void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  vec3 green = vec3(0.0784, 0.5804, 0.2784);
  vec3 yellow = vec3(0.9804, 0.8667, 0.3451);
  vec3 red = vec3(0.8549, 0.1529, 0.1569);
  vec3 color =
      green * flip(xy.x * 3.0 / 2.0, 1.0, xy.y * flip(0.0, 2.0 / 3.0, xy.x)) +
      red * flip(0.0001, max((xy.x - 1.0 / 3.0) * 3.0 / 2.0, 0.0001),
                 xy.y * flip(1.0 / 3.0, 1.0, xy.x)) +
      yellow * flip(max((xy.x - 1.0 / 3.0) * 3.0 / 2.0, 0.0001),
                    min(1.0, xy.x * 3.0 / 2.0), xy.y);

  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

vec3 overlay(vec3 background, vec3 foreground, float u) {
  return background * 1.0 + foreground * u - background * u;
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  vec3 blue = vec3(0.0000, 0.2157, 0.4863);
  vec3 green = vec3(0.0039, 0.4353, 0.2078);
  vec3 yellow = vec3(0.9882, 0.8235, 0.2980);
  vec3 red = vec3(0.8157, 0.1373, 0.1412);
  vec3 white = vec3(1.0, 1.0, 1.0);

  vec3 color = overlay(
      overlay(overlay(overlay(blue, yellow, flip(0.0, 2.5 * xy.x, xy.y)), red,
                      flip(0.0, 1.2 * xy.x, xy.y)),
              white, flip(0.0, 0.7 * xy.x, xy.y)),
      green, flip(0.0, 0.3 * xy.x, xy.y));

  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

float flip(vec2 from, vec2 to, vec2 x) {
  vec2 result = step(from, x) - step(to, x);
  return result.x * result.y;
}

vec3 overlay(vec3 background, vec3 foreground, float u) {
  return background * 1.0 + foreground * u - background * u;
}

void main() {
  vec2 xy = gl_FragCoord.xy / u_resolution;
  vec3 green = vec3(0.0078, 0.5647, 0.2000);
  vec3 yellow = vec3(0.9961, 0.7922, 0.0118);
  vec3 black = vec3(0.0, 0.0, 0.0);
  float width = 1.0 / 10.0;
  vec3 color = overlay(
      overlay(
          overlay(overlay(green, black,
                          flip(vec2(0.0, xy.x), vec2(0.5, (1.0 - xy.x)), xy)),
                  black, flip(vec2(0.5, (1.0 - xy.x)), vec2(1.0, xy.x), xy)),
          yellow, flip(xy.x - width, xy.x + width, xy.y)),
      yellow, flip(1.0 - xy.x - width, 1.0 - xy.x + width, xy.y));

  gl_FragColor = vec4(color, 1.0);
}

precision mediump float;
uniform vec2 u_resolution;

float flip(float from, float to, float x) {
  return step(from, x) - step(to, x);
}

vec3 overlay(vec3 background, vec3 foreground, float u) {
  return background * 1.0 + foreground * u - background * u;
}

void main() {
  vec2 st = gl_FragCoord.xy - (u_resolution * 0.5);
  st = st / u_resolution.y;
  vec3 red = vec3(0.7059, 0.0000, 0.1569);

  vec3 color =
      overlay(vec3(1.0), red, flip(0.0, 0.25, distance(vec2(0.0, 0.0), st)));

  gl_FragColor = vec4(color, 1.0);
}

Rich Hickey’s Clojure Bookshelf

2018-11-07T00:00:00+00:00

This is a copy of the list shared by Rich Hickey, as the original link http://bit.ly/RlXiw no longer works.

Personal Finance

2018-10-18T00:00:00+00:00

This is a tutorial on how to manage personal finance using ledger. The reader is assumed to have a good knowledge about how to use the command line. The basic idea is that you write down all the transactions in a file named personal.ledger and then use the command line program ledger to generate various kinds of reports.

Double-entry accounting

Ledger follows the double-entry accounting system. In simple terms, it is a journal which tracks the movement of money from debit account to credit account. Let’s assume you are a salaried employee and make 100,000 INR every month. In ledger, a transaction is represented as

2018/01/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                             100,000 INR

Here Income:Salary is the debit account and Account:Savings is the credit account. The date at which the transaction took place and a description of the transaction is written in the first line followed by the list of credit or debit entry. Account name could be anything. The : in the account name represents hierarchy. Its use will become more clear when we look at the reports generated by ledger. The sum of the balance of all the accounts must be zero.

~/finance $ ledger -f personal.ledger balance
         100,000 INR  Account:Savings
        -100,000 INR  Income:Salary
--------------------
                   0

We now know enough basics to get started. For simplicity, I am going to just show entries for 3 months.

2018/01/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                             100,000 INR

2018/02/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                             100,000 INR

2018/03/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                             100,000 INR

The total balance in the savings account can be reported by

~/finance $ ledger -f personal.ledger balance Account:Savings
         300,000 INR  Account:Savings

Asset

A person’s net worth is calculated by the formula

Net worth = Assets - Liablities

In a ledger file, each of these assets should be represented by a separate account. Let say 12,000 INR of your salary goes to EPF, we could represent it as follows.

2018/01/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                              88,000 INR
    Asset:Debt:EPF                               12,000 INR

2018/02/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                              88,000 INR
    Asset:Debt:EPF                               12,000 INR

2018/03/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                              88,000 INR
    Asset:Debt:EPF                               12,000 INR

There can be multiple credit entries in a transaction as long as the credit and debit sum up to zero. Let’s say you invest 5,000 INR every month in the PPF account, it could be represented as follows.

2018/01/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                              88,000 INR
    Asset:Debt:EPF                               12,000 INR

2018/01/01 Investment
    Account:Savings                              -5,000 INR
    Asset:Debt:PPF                                5,000 INR

2018/02/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                              88,000 INR
    Asset:Debt:EPF                               12,000 INR

2018/02/01 Investment
    Account:Savings                              -5,000 INR
    Asset:Debt:PPF                                5,000 INR

2018/03/01 Salary
    Income:Salary                              -100,000 INR
    Account:Savings                              88,000 INR
    Asset:Debt:EPF                               12,000 INR

2018/03/01 Investment
    Account:Savings                              -5,000 INR
    Asset:Debt:PPF                                5,000 INR

The money moves from your savings account to ppf account. Your current net worth could be reported by

~/finance $ ledger -f personal.ledger balance Asset
          51,000 INR  Asset:Debt
          36,000 INR    EPF
          15,000 INR    PPF
--------------------
          51,000 INR

Interest

The interest credited by the bank could be represented as another transaction. If the bank credits the interest at the end of the financial year, it could be represented as

2018/03/31 Interest
    Income:Interest                              -15,000 INR
    Asset:Debt:PPF                                 5,000 INR
    Asset:Debt:EPF                                10,000 INR

~/finance $ ledger -f personal.ledger balance Asset
          66,000 INR  Asset:Debt
          46,000 INR    EPF
          20,000 INR    PPF
--------------------
          66,000 INR

Commodity

Let’s say you are also investing 10,000 INR on UTI Nifty Index Fund and 10,000 INR on ICICI Nifty Next 50 Index Fund every month. Mutual Fund can be considered as a commodity which could be converted to currency.

2018/01/01 Investment
    Account:Savings                              -25,000 INR
    Asset:Debt:PPF                                 5,000 INR
    Asset:Equity:NIFTY          148.0865 NIFTY @ 67.5281 INR
    Asset:Equity:NIFTY_JR    358.6659 NIFTY_JR @ 27.8811 INR

2018/02/01 Investment
    Account:Savings                              -25,000 INR
    Asset:Debt:PPF                                 5,000 INR
    Asset:Equity:NIFTY          140.2870 NIFTY @ 71.2824 INR
    Asset:Equity:NIFTY_JR    363.2242 NIFTY_JR @ 27.5312 INR

2018/03/01 Investment
    Account:Savings                              -25,000 INR
    Asset:Debt:PPF                                 5,000 INR
    Asset:Equity:NIFTY          147.5908 NIFTY @ 67.7549 INR
    Asset:Equity:NIFTY_JR    378.4323 NIFTY_JR @ 26.4248 INR

Let’s consider 148.0865 NIFTY @ 67.5281 INR. Here NIFTY is the name of the commodity and we have bought 148.0865 units at 67.5281 INR per unit.

ledger by default reports the commodity without conversion.

~/finance $ ledger -f personal.ledger balance Asset
          66,000 INR
      435.9643 NIFTY
  1100.3224 NIFTY_JR  Asset
          66,000 INR    Debt
          46,000 INR      EPF
          20,000 INR      PPF
      435.9643 NIFTY
  1100.3224 NIFTY_JR    Equity
      435.9643 NIFTY      NIFTY
  1100.3224 NIFTY_JR      NIFTY_JR
--------------------
          66,000 INR
      435.9643 NIFTY
  1100.3224 NIFTY_JR

To convert the commodity to current market value, we have to supply the current price of the commodity. AMFI publishes the latest NAV values. Save the following text in a file named price.db

P 2018/10/26 00:00:00 NIFTY 65.6193 INR
P 2018/10/26 00:00:00 NIFTY_JR 23.0733 INR

~/finance $ ledger -f personal.ledger --price-db price.db balance --market Asset
         119,996 INR  Asset
          66,000 INR    Debt
          46,000 INR      EPF
          20,000 INR      PPF
          53,996 INR    Equity
          28,608 INR      NIFTY
          25,388 INR      NIFTY_JR
--------------------
         119,996 INR

The same approach could be used for other commodities like gold, stocks etc.

Gain

Gain or loss based on the commodity value in the price.db can be calculated as follows.

~/finance $ ledger -f personal.ledger --price-db price.db balance --gain Asset
          -6,004 INR  Asset:Equity
          -1,392 INR    NIFTY
          -4,612 INR    NIFTY_JR
--------------------
          -6,004 INR

Register

The list of all the transactions related to an account and it’s running total could be reported by the register command.

~/finance $ ledger -f personal.ledger --price-db price.db register --market Asset:Equity
18-Jan-01 Investment   Asset:Equity:NIFTY       10,000 INR  10,000 INR
                       Asset:Equity:NIFTY_JR    10,000 INR  20,000 INR
18-Feb-01              <Revalued>                  430 INR  20,430 INR
18-Feb-01 Investment   Asset:Equity:NIFTY       10,000 INR  30,430 INR
                       Asset:Equity:NIFTY_JR    10,000 INR  40,430 INR
18-Mar-01              <Revalued>               -1,816 INR  38,615 INR
18-Mar-01 Investment   Asset:Equity:NIFTY       10,000 INR  48,615 INR
                       Asset:Equity:NIFTY_JR    10,000 INR  58,615 INR
18-Oct-26              <Revalued>               -4,619 INR  53,996 INR

Allocation

The allocation of money across different assets could be reported as follows.

~/finance $ ledger -f personal.ledger --price-db price.db balance --market --percent Asset
             100.00%  Asset
              55.00%    Debt
              69.70%      EPF
              30.30%      PPF
              45.00%    Equity
              52.98%      NIFTY
              47.02%      NIFTY_JR

This is just the tip of the iceberg. Checkout out the ledger manual for further details.

Sort order preserving serialization

2018-08-17T00:00:00+00:00

FoundationDB is a distributed key-value store. From the database perspective, both keys and values are just bytes. Keys are sorted lexicographically and different chunks are assigned to different servers. Because of this locality property, the range read operation is efficient as most of the time the client would be able to fetch the data from a single server.

As the keys are just bytes, the application must serialize the keys and more importantly if we need to use range operation, then the serialization should preserve the order of the keys. Fortunately, all the clients implement the tuple layer which has this property. This post attempts to explain how various data types are encoded in a way that preserves their natural sort order.

I will represent bytes using their hex format for the rest of the blog post. Each data type is tagged with an identifier which uniquely identifies the type.

NUll

Null is encoded with the tag 00

Byte String

Tag 01 is used for byte string. 00 is used as the terminator and 00 inside the byte string are escaped by replacing them with 00FF. For example the byte string ABCDEF would be encoded as 01ABCDEF00.

It’s clear that order would be preserved for byte strings without 00 because the same constant values are prefixed and suffixed for all the byte strings. Let’s consider all the possible cases of byte strings with 00.

AB00DD

01AB00FFDD00

AB01DD

01AB01DD00

AB00BC

01AB00FFBC00

AB00DD

01AB00FFDD00

AB00DD

01AB00FFDD00

AB01

01AB0100

AB00

01AB00FF00

AB01DD

01AB01DD00

01AB00

AB00

01AB00FF00

Because the terminator 00 has the lowest byte value and if the compared byte string has any value other than 00 in the same position then there is no need to consider the rest of the bytes. The last case shown is a bit tricky and there is a reason for choosing FF as the escape value and it will become more apparent when we consider Tuple types.

Integer

Integers upto 8 bytes are supported. Integers get encoded into variable size which depends on minium bytes required to represent the integer. Tags 0C to 13 are used for negative numbers and tag 14 for zero and tags 15 to 1C are used for positive number.

For positive integers, big-endian byte order is used which naturally preserves the sort order. For negative integers, the sign is removed and bit complement of big-endian byte order is used bit-complement(big-endian(abs(n))). The bit complement operation reverses the sort order. If two integers get encoded into different sized bytes, then the order would be preserved by tag values. The tag value increases as the integer value increases.

-98344948949494949

0CFEA29BCA3C69535A

-303040404040

0FB9716265B7

-20404

12B04B

-42

13D5

42

152A

20404

164FB4

303040404040

19468E9D9A48

98344948949494949

1C015D6435C396ACA5

Float

Tags 20 (32 bits) and 21 (64 bits) are used for floating point numbers.

def transform(<<sign::big-integer-size(8), rest::binary>> = full) do
  if (sign &&& 0x80) != 0x00 do
    :binary.bin_to_list(full)
    |> Enum.map(fn e -> 0xFF ^^^ e end)
    |> IO.iodata_to_binary()
  else
    <<0x80 ^^^ sign>> <> rest
  end
end

The value is first encoded in IEEE 754 binary format. For positive numbers just the sign bit should be flipped and for negative numbers all the bits should be flipped. This should provide total order as per the IEEE specification.

Tuple

Because of the way other values are encoded, a tuple can be encoded just by concatenating the encoded values. Note that the sort order is preserved only between values of same types. Specially comparison between types like Float and Integer won’t work.

(AB, 42)

01AB00152A

(AB00, 42)

01AB00FF00152A

This example illustrates why FF is chosen as the escape character. As long as we don’t use FF as the tag for any type, the byte string value 00 and the terminator value 00 would not conflict and break the sort order. Other types don’t introduce these kinds of behaviors because they are either of fixed size or in case of Integer, the tag will determine the order of the values if they are of different size.

Nested Tuple

Tuple type can’t be nested as there is no difference between (1, (2, 3)) and (1, 2, (3)). Both values would get encoded as the same as the flattened tuple (1, 2, 3). Nested tuple, as the name implies supports arbitrary nesting. [ is used to represent nested tuple.

Tag 05 and terminator 00 are used for nested tuple. Encoded values are concatenated and any Null values are escaped as 00FF.

[1, [2, 3]]

05150105150215030000

[1, 2, [3]]

05150115020515030000

There are other data types like unicode string, arbitrary precision number, UUID, boolean etc, but all of them follow similar principles discussed so far. As such, they are not considered here.

High contention allocator

2018-08-05T00:00:00+00:00

FoundationDB is a distributed key-value store. The whole database can be considered as a giant sorted map where keys and values are bytes. FoundationDB client libraries provide two means for handling namespaces.

Subspace - Raw bytes like users:friends or users:profile is prefixed to keys before they get stored and stripped from the keys when they are retrieved.

alias FDB.Coder.{Subspace, Integer, ByteString}
alias FDB.Transaction

coder =
  Transaction.Coder.new(
    # key encoding
    Subspace.new("users:friends", Integer.new()),
    # value encoding
    ByteString.new()
  )
user = Transaction.get(tr, 42, %{coder: coder})

The key is encoded as users:friends\x21\x42. The primary disadvantage is the size of prefix, which increases as the level of nesting increases.

Directory - The size problem is solved by converting the namespace to a short unique prefix. There is an extra cost involved when a directory is created or opened compared to the subspace, but this will get amortized over time if the number of directories used is small enough compared to other requests.

alias FDB.Directory

root = Directory.new()
coder =
  Transaction.Coder.new(
    Subspace.new(
      Directory.create_or_open(root, tr, ["users", "friends"]),
      Integer.new()
    ),
    ByteString.new()
  )
user = Transaction.get(tr, 42, %{coder: coder})

The key will get encoded something like \x21\x8\x21\x42. Internally a mapping from ["users", "friends"] to the prefix \x21\x8 is stored. This has the added advantage that renaming the namespace for example from ["users", "friends"] to ["v1", "users", "friends"] could be done without changing all the keys. Only the internal mapping has to be updated.

This blog post attempts to explain the algorithm used to create short unique prefixes in the FoundationDB client libraries. To understand the issues involved, a naive implementation is presented first and then its performance characteristics are contrasted with the algorithm used in the client libraries.

defmodule NaiveHCA do
  alias FDB.{Database, Transaction}

  def allocate(transaction) do
    <<counter::integer-64>> = Transaction.get(t, "counter") || <<0::integer-64>>
    counter = counter + 1
    :ok = Transaction.set(t, "counter", <<counter::integer-64>>)
    encoded = :binary.encode_unsigned(counter)
    <<byte_size(encoded)>> <> encoded
  end
end

A single 64 bit counter is used to store the state and numbers are encoded with minimum required bytes – without leading zeros. To avoid prefix clash between numbers of different byte sizes like 0x05 and 0x0501, the byte size is also added as a prefix.

Why does the allocations per second seem to max out at about 300?. FoundationDB uses multi-version concurrency control (MVCC) for reads and optimistic concurrency for writes. As a result, neither reads nor writes are blocked by other readers or writers. Instead, conflicting transactions will fail at commit time and should be retried by the client. The common idiom is to use Database.transact which will retry until the commit succeeds.

FDB.Database.transact(database, fn t ->
  NaiveHCA.allocate(t)
end)

In the naive implementation, the number of conflicts increases as the concurrency increases. The major focus of the algorithm is to reduce the number of conflicts.

Instead of using a single counter a window is used. Each process tries to acquire a random value within the current window. Once the current window is half filled, the window is advanced. The number of conflicting transactions will be small if the window size is big enough compared to the number of concurrent processes.

defmodule HCA do
  alias FDB.Coder.{Tuple, Integer, Subspace}
  alias FDB.Transaction
  alias FDB.KeySelectorRange
  alias FDB.KeyRange
  alias FDB.Option

  @counter 0
  @reserve 1

  def allocate(t) do
    hca_coder =
      Transaction.Coder.new(
        Subspace.new("hca", Tuple.new({Integer.new(), Integer.new()})),
        LittleEndianInteger.new(64)
      )

    t = Transaction.set_coder(t, hca_coder)
    prefix = search(t)
    encoded = :binary.encode_unsigned(prefix)
    <<byte_size(encoded)>> <> encoded
  end

How the keys and values should be encoded is defined using the hca_coder. The actual work is delegated to the search function.

  defp search(t) do
    candidate_range = range(t, current_start(t), false)
    search_candidate(t, candidate_range)
  end

The search function calculates the current window and calls search_candidate to find a candidate within the window.

  defp current_start(t) do
    result =
      Transaction.get_range(t, KeySelectorRange.starts_with({@counter}), %{
        limit: 1,
        reverse: true,
        snapshot: true
      })
      |> Enum.to_list()

    case result do
      [] -> 0
      [{{@counter, start}, _}] -> start
    end
  end

The current window’s start and the number of values so far allocated within that window are stored in the following format.

{@counter, start} => allocated_count

This function returns the latest window start value

  defp range(t, start, window_advanced) do
    if window_advanced do
      clear_previous_window(t, start)
    end

    Transaction.atomic_op(t, {@counter, start}, Option.mutation_type_add(), 1)
    count = Transaction.get(t, {@counter, start}, %{snapshot: true}) || 0
    window = window_size(start)

    if count * 2 < window do
      start..(start + window - 1)
    else
      range(t, start + window, true)
    end
  end

  defp window_size(start) do
    cond do
      start < 255 -> 64
      start < 65535 -> 1024
      true -> 8192
    end
  end

range is responsible for calculating the current window range. The allocated count is incremented beforehand and the window is advanced if half filled.

Conflict range

By default any read or write inside a transaction creates a read or write conflict range for the corresponding key range. When the transaction is committed these conflict ranges are used to make sure transactions are serializable.

If every process reads and mutates the same key, then we are back to the same problem as the naive implementation. FoundationDB provides means to disable the generation of conflicts, but the responsibility is on the user to make sure it doesn’t compromise the consistency. Here snapshot reads and atomic updates are used to avoid the creation of unnecessary conflict ranges. More on conflicts will be explained later.

  defp search_candidate(t, search_range) do
    candidate = Enum.random(search_range)
    candidate_value = Transaction.get(t, {@reserve, candidate})
    Transaction.set_option(t, Option.transaction_option_next_write_no_write_conflict_range())
    Transaction.set(t, {@reserve, candidate}, 1)

    if is_nil(candidate_value) do
      Transaction.add_conflict_key(
        t,
        {@reserve, candidate},
        Option.conflict_range_type_write()
      )

      candidate
    else
      search_candidate(t, search_range)
    end
  end

search_candidate repeatedly tries to reserve a random value within the given window. The write conflict is only added if the value is not already reserved by some other process.

  defp clear_previous_window(t, start) do
    Transaction.clear_range(
      t,
      KeyRange.range({@counter}, {@counter, start}, %{begin_key_prefix: :first})
    )

    Transaction.set_option(t, Option.transaction_option_next_write_no_write_conflict_range())

    Transaction.clear_range(
      t,
      KeyRange.range({@reserve}, {@reserve, start}, %{begin_key_prefix: :first})
    )
  end
end

There are two main aspects for any algorithm: correctness and performance

Correctness

What is correctness? From the algorithm perspective same prefix value shouldn’t get allocated to two different processes. In a typical scenario the atomicity and serializable isolation provided by the database will make the job easy. We can assume that operations of different transactions won’t get interleaved. But as we mentioned earlier, to reduce the number of conflicts we are explicitly instructing the database to not consider the conflicts produced by some of the reads and writes. So the burden is now on us to make sure we haven’t compromised the correctness for performance.

Instead of proving the correctness in a rigorous way, I am going to reason in a semi-formal way.

At any point in time, the algorithm would be in two state

There are enough unfilled values within in the current window. All the processes would be able to allocate without advancing the window. As the conflict range is set on the reserved candidate, only one of the processes would succeed.
There are not enough unfilled values within in the current window. One or more processes might try to advance the current window.

Let’s think of a scenario which might break the correctness

Process 1	Process 2	Process 3
init	init
allocate x (window 1)
commit
		init
		clear window 1
		allocate y (window 2)
		commit
	allocate x (window 1)
	commit

Process 1 and 2 both starts at the same time, and x is allocated to process 1. Process 3 finds the window half filled and advances the window by clearing the current one. Process 2 tries to allocate the same value x as Process 1.

Let’s look at the exact call sequence before trying to reason why it would not work. FoundationDB client has options to trace transactions. An edited version of the xml trace file is shown below.

{OP: 'GetVersion', ID: 'process 1'}
{OP: 'GetVersion', ID: 'process 2'}
{OP: 'GetRange', ID: 'process 1', RangeSizeBytes: '0', StartKey: 'hcax14x00', EndKey: 'hcax14xffx00'}
{OP: 'GetRange', ID: 'process 2', RangeSizeBytes: '0', StartKey: 'hcax14x00', EndKey: 'hcax14xffx00'}
{OP: 'Get', ID: 'process 1', ValueSizeBytes: '0', Key: 'hcax15x01x14'}
{OP: 'Commit_ReadConflictRange', ID: 'process 1', Begin: 'hcax15x01x14', End: 'hcax15x01x14x00'}
{OP: 'Commit_WriteConflictRange', ID: 'process 1', Begin: 'hcax14x14', End: 'hcax14x14x00'}
>>>>>>{OP: 'Commit_WriteConflictRange', ID: 'process 1', Begin: 'hcax15x01x14', End: 'hcax15x01x14x00'}
{OP: 'Commit_Mutation', ID: 'process 1', Mutation: 'code: AddValue param1: hcax14x14 param2: x01x00x00x00x00x00x00x00'}
{OP: 'Commit_Mutation', ID: 'process 1', Mutation: 'code: SetValue param1: hcax15x01x14 param2: x01x00x00x00x00x00x00x00'}
{OP: 'Commit', ID: 'process 1', NumMutations: '2'}
{OP: 'GetVersion', ID: 'process 3'}
{OP: 'GetRange', ID: 'process 3', RangeSizeBytes: '13', StartKey: 'hcax14x00', EndKey: 'hcax14xffx00'}
{OP: 'Get', ID: 'process 3', ValueSizeBytes: '0', Key: 'hcax15x01x15@'}
{OP: 'Commit_ReadConflictRange', ID: 'process 3', Begin: 'hcax15x01x15@', End: 'hcax15x01x15@x00'}
{OP: 'Commit_WriteConflictRange', ID: 'process 3', Begin: 'hcax14x14', End: 'hcax14x14x00'}
{OP: 'Commit_WriteConflictRange', ID: 'process 3', Begin: 'hcax14x15@', End: 'hcax14x15@x00'}
{OP: 'Commit_WriteConflictRange', ID: 'process 3', Begin: 'hcax15x01x15@', End: 'hcax15x01x15@x00'}
{OP: 'Commit_Mutation', ID: 'process 3', Mutation: 'code: ClearRange param1: hcax14x00 param2: hcax14x15@'}
{OP: 'Commit_Mutation', ID: 'process 3', Mutation: 'code: ClearRange param1: hcax15x01x00 param2: hcax15x01x15@'}
{OP: 'Commit_Mutation', ID: 'process 3', Mutation: 'code: AddValue param1: hcax14x15@ param2: x01x00x00x00x00x00x00x00'}
{OP: 'Commit_Mutation', ID: 'process 3', Mutation: 'code: SetValue param1: hcax15x01x15@ param2: x01x00x00x00x00x00x00x00'}
{OP: 'Commit', ID: 'process 3', NumMutations: '4'}
{OP: 'Get', ID: 'process 2', ValueSizeBytes: '0', Key: 'hcax15x01x14'}
>>>>>>{OP: 'CommitError_ReadConflictRange', ID: 'process 2', Begin: 'hcax15x01x14', End: 'hcax15x01x14x00'}
{OP: 'CommitError_WriteConflictRange', ID: 'process 2', Begin: 'hcax14x14', End: 'hcax14x14x00'}
{OP: 'CommitError_WriteConflictRange', ID: 'process 2', Begin: 'hcax15x01x14', End: 'hcax15x01x14x00'}
{OP: 'CommitError_Mutation', ID: 'process 2', Mutation: 'code: AddValue param1: hcax14x14 param2: x01x00x00x00x00x00x00x00'}
{OP: 'CommitError_Mutation', ID: 'process 2', Mutation: 'code: SetValue param1: hcax15x01x14 param2: x01x00x00x00x00x00x00x00'}
{OP: 'CommitError', ID: 'process 2', Err: 'Transaction not committed due to conflict with another transaction'}

FoundationDB uses multi version concurrency control for reads. Internally it stores multiple versions of the same key – for a short period of time. When a transaction starts, the first read will get the current version of the database as the read version of the transaction. This is indicated by the {OP: 'GetVersion'} in the trace. Any further reads from the transaction will not observe any writes that happens after that.

A transaction conflicts if it reads a key that has been written between the transaction’s read version and commit version. Because Process 1 has committed before Process 2 is commited, Process 2’s read on {@reserve, candidate} key conflicts with Process 1’s write on the same key. The commit by Process 2 would get cancelled and it should retry the whole process again. This is indicated by the last entry {OP: 'CommitError'... in the trace log. Once a transaction gets the read version, it can’t observe any other concurrent writes by other processes. If Process 2 has started after Process 1 had committed, then the read on {@reserve, candidate} would return non nil even if Process 3 has cleared the key range concurrently.

This effectively means concurrent clear won’t cause problem.

The transactions that have started before the commit of Process 3 would try to allocate within the last window. They will not observe the clear range operation.
The transactions that have started after the commit of Process 3 would try to allocate within the new window

Multiple processes trying to advance the window concurrently is not a problem from correctness perspective. They would still conflict with each other if they try to allocate the same candidate. Because of the serlizable isolation, we can assume there would be a total order across all commits, ie commit won’t happen concurrently.

Performance

From the graphs it’s clear that the high contention allocator algorithm scales linearly without any problem.

Mastering Elixir

2017-12-31T00:00:00+00:00

This is written for someone who is already a programmer and familiar with two or three programming languages. For someone new to programming, the route proposed here might not work.

Do I need to learn Erlang?

Yes, Although you might not write lot of Erlang code, you need to be able to read Erlang code and browse through the Erlang documentation to figure out the details.

Elixir differs from the mainstream languages in three main aspects.

Immutability

Values in Elixir are immutable, it can’t be changed in-place. This kind of trips up a lot of programmers who are used to c or Java where the predominant style is to mutate values in-place.

Concurrency

Most of the languages support shared state concurrency. Multiple threads will share a common state and they communicate with each other by mutating the state in-place. The actor model approach taken by Elixir is completely different from this model.

Macro

None of the mainstream languages supports macro. Unless you already know any Lisp-like language, you might not have much idea about what is macro and how it’s useful.

Trying to learn all the three aspects of the language at the same time might not work out for everyone. The easy way is to learn them one by one.

The getting started guide provides a nice introduction to the language tools and syntax. Read the first 22 chapters. Depending on your background, by the time you finish this, you would be able to write useful programs in Elixir.

Learn You Some Erlang is a great book. The first part of the book focus on the functional aspect of the language, the rest of the book focus on the concurrency part.

Elixir in Action is another great book. Most of the material covered here is already covered by Learn You Some Erlang, but it’s nice to go through them once again and understand how the Erlang code maps to Elixir code.

Macro is something which you would not use in everyday programming. But it’s invaluable in some situations. I could not find any good introductory book on macros in Elixir. The best way I could find is to read On Lisp or Let Over Lambda. Once you understood it’s use cases, you can read the Meta Programming section in getting started guide and also read the Metaprogramming Elixir book.

Making reliable distributed systems in the presence of software errors is written by Joe Armstrong. It explains the reason for some of the language design decisions and provides advice on how to organize large-scale projects.

Erlang in Anger is written by the same guy who wrote Learn You Some Erlang. It explains how to debug or find problems in production systems. It’s worth a skim through.

Hunger

2017-12-08T00:00:00+00:00

Writing is a powerful medium, which when controlled by a skillful writer could evoke a captivating world in the mind of the reader – something the reader couldn’t have come up by himself. Knut Hansum takes it to the next level in the book Hunger. Instead of creating a world which could be observed by the reader as an omnipresent God, he chooses to place the reader inside the world as a character, make the reader go through the same sensations of the protagonist in the story, make him feel how it would be to be hungry and delirious.