Forem: Junxiao Shi

Deep Atlantic Storage: Rewriting in Rust

Junxiao Shi — Mon, 25 May 2026 04:00:00 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2026/das-rust/

I have been coding in C++, Go, and TypeScript for many years, but recently I started learning the Rust Programming Language.

Why Rust

I choose to study the Rust programming language because:

Rust is one of the major system languages that I do not know.
Rust, just like Go, is a memory safe language, apparently now a national security issue.
Rust, unlike Go, does not have a garbage collector.
Rust, unlike Go, does not have a nil pointer.

The last point is particularly important.
In Go, I often find myself writing a method with pointer receiver:

type Counter struct {
    V int
}

func (cnt *Counter) Increment() {
    cnt.V += 1
}

The pointer receiver is required, if the method needs to modify a field on its receiver.
However, more often than not, I forget to check whether the receiver itself is a nil pointer, even in production code.
If the above function was called like this:

var cnt *Counter
cnt.Increment()

It would experience a panic at runtime:

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x46f383]

In contrast, Rust's rigid rules can prevent writing such careless code.
A function/method is allowed to modify its arguments, including self, only if the argument is passed as a mutable borrow, signified with the mut keyword.
Moreover, a borrow can only be created from a real value, allocated in either the stack or the heap.
It is generally impossible to have a nil or NULL pointer, or a borrow that points to invalid memory.
This different, as I perceive, elevates Rust to have a higher level of memory safety.

The Book

The official Learn Rust webpage gives three options:

The Rust Programming Language, "the book" that covers the language principles and some small exercises.
Rust By Examples, a bunch of code with minimal explanation.
Rustlings, an interactive tutorial of the Rust syntax in my environment.

Two decades ago, I learned HTML and CSS from the official W3C specifications.
While I would not go as deep as learning from the language and compiler specifications, I chose the deepest option among the three, "the book".

During the 43-day government shutdown, I studied the book on each weekday.
I setup my local environment, pasted the sample snippets, and made small changes to see what would happen.

I feel that, Rust is a difficult language to learn.
Not in a university taking programming class, I don't have a professor and teaching assistants to assign my homework, grade my code, and answer my questions.
I am mostly on my own, against the Visual Studio Code console, judged by the compiler output when I invoke the cargo run command.

The last chapter of the book is building a multithreaded web server.
I immediately noted that, the exercise is making me handle the network traffic at TCP level.
In contrast, Go has a built-in net/http package, and I used Win32 HTTP Server API for my hProxyN project in college.
I'm surprised that Rust, being a modern programming language, lacks an HTTP server in its standard library.

Here I learned a different philosophy: Rust is designed with a minimal standard library that only contains the essentials.
Most "batteries" are provided as crates, including random number generation, command line parsing, Async I/O, HTTP server, and many others.

Re-build the Deep Atlantic Storage app

As I finish the book, I wanted to build something real.
While I had a few new project ideas, I decided against building a completely new project, using a language that I barely know, because it would be too complicated to architect the software, design the protocols, and deal with an unfamiliar language, all at the same time.
Instead, I wanted to re-build something existing, but better.

Many learners would choose a tutorial project, often seen on DEV #clone tag.
However, I feel wasteful building these projects, because I do not see myself ever deploy and operating the resulting program, which means the code would be written once and never used again.
Instead, I wanted to build something that I would deploy, but with low stakes.

Looking over my website, now in its 20th year, I found the perfect candidate: Deep Atlantic Storage, a wacky webpage I made on July 4th holiday in 2021.
It has fewer than 300 lines of code, originally written in JavaScript and Go, encompassing many aspects of system programming: file access, stdio usage, byte slices, bit operators, HTTP servers.
I shall re-build this application, in Rust.

The Process and What I Learned

The codebase is hosted on GitHub: yoursunny/summer-host-storage.
It took me four days to build the initial version.

On my first day, I established the package structure and enabled GitHub Actions, even before writing any code logic.
Then, I wrote these functions along with unit tests:

use std::io;

// Download a file from the Atlantic Ocean.
pub fn download<T: io::Write>(mut w: T, counts: &BitCounts) -> Result<(), io::Error> {}

// Upload a file to the Atlantic Ocean.
pub fn upload<T: io::Read>(r: T) -> Result<BitCounts, io::Error> {}

I tried a few command line parsing crates on my second day and picked clap.
I wrote the necessary declarations, to make the download and upload functionality available on the command line.

I spent the third day researching HTTP server crates.
I initially used hyper but was very confused on its body concept and had great difficulty writing a test case.
Then I switched to axum, which seems to have more natural APIs similar to what I used in Go, Node.js, and Arduino.

However, I hit a snag when I tried to integrated my download and upload functions: I wrote these as synchronous functions, so that the HTTP server must buffer the entire file in memory during each download or upload.
The io::Write and io::Read traits feel like streams, but they are not the same streams as Node.js or Go.

On my fourth day, I transformed the core functions to be asynchronous:

use tokio::io::{self, AsyncRead, AsyncWrite};

// Download a file from the Atlantic Ocean.
pub async fn download<T: AsyncWrite + Unpin>(w: T, counts: &BitCounts) -> Result<(), io::Error> {}

// Upload a file to the Atlantic Ocean.
pub async fn upload<T: AsyncRead + Unpin>(r: T) -> Result<BitCounts, io::Error> {}

This refactoring enabled me to unclog the HTTP pipes and realized request and response streaming, finishing the build.

My main takeaway from this process is that, for network applications, I should use the industry standard tokio crate and build as asynchronous APIs, which would perform better than the standard library traits.

Final Words

I attended Rust DC meetup and briefly introduced my app.
Audience was interested.
During the same meetup, I learned about another command line parsing library bpaf and decided to make the switch.
The code became a few lines shorter as its syntax is less verbose.

I haven't deployed the app yet, because it still lacks a few important features such as the gzip compression that is available in the Deep Atlantic Storage app written in Go.
I shall further refine my first Rust application and get it read for deployment.

New Avatar

Junxiao Shi — Fri, 22 May 2026 03:14:06 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2026/avatar/

In computing, an avatar is a graphical representation of a user, the user's character, or persona.
An avatar can be a two-dimensional picture, also known as a profile picture or userpic, or a three-dimensional digital representation, often used in games.

My existing avatar has been in use since 2010.
It was created from a selfie taken at Expo 2010 Shanghai, where I proudly visited every pavilion.
I stood in front of the Expo Axis, placed my Canon E1000D atop a trash can near the Hong Kong pavilion, and used the self-timer feature of the DSLR camera to capture the selfie.
The picture depicts me wearing a white sleeveless shirt and a black backpack, in front of background of trees, people, and the Expo Axis.
Subsequently, I cropped the image with Adobe Photoshop, blurred the background, and produced the final image.

Over the years, as I expanded my online presence, readers from dozens of social media websites and forums have seen my avatar.
It has become part of my online identity, my personal brand.

In 2016, I realized that I still have the same shirt as shown in my avatar.
On the 6-year anniversary of the original picture, I took a new photo of me in the same outfit, in front of a cactus behind the university.
In 2020, I did it again for the 10-year anniversary, but indoors due to COVID-19 pandemic.
Nevertheless, I did not adopt either picture as my avatar, because they have drastically different backgrounds and would make me unrecognizable online.

By 2025, I grew unhappy with my avatar.
Firstly, the 2010 avatar was produced as 750x750 image resolution, which is insufficient by today's standards.
Secondly, my real life appearance has changed over the years, and I wanted to showcase my more recent look.
I wanted to remake my avatar, but in the same style so that it remains recognizable.

On a cool summer day, I put on the shirt (yes, the same one) and a black backpack, and set out to find the perfect background for my new avatar.
I took a bus to Rock Creek Park in Washington DC, hiked the north floodplain area, and found a patch of woods with enough trees that resembled my 2010 avatar.
I placed my iPhone 16e on a fence post, turned on the Portrait mode, and captured the perfect image after multiple tries waiting for the perfect sunlight.
It depicts me wearing the same white sleeveless shirt and a similar black backpack, in front of some trees but no people or building.
Apple Intelligence has already blurred the background for me, so that I do not need to use Photoshop again.

After the trip, I quickly forgot that I took the new picture for my avatar, so that it wasn't uploaded.
Today, as I worked on archiving my photos by moving out from Dropbox, I re-discovered this image, and decided to finish the effort.
I cropped the image with PicPick application, optimized the file with Ezgif, and then uploaded the final result to Gravatar so that it would appear in all the forums where I have a presence.
With that, my new avatar is launched.

Note: the original article contains a CSS slider that compares 2010 and 2025 avatars.

Today I Learned: openat()

Junxiao Shi — Sat, 28 Aug 2021 17:53:27 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/openat/

fopen and open

In C programming language, the <stdio.h> header supplies functions for file input and output.
To open a file, we usually use the fopen function.
It is defined by the C language standard and works in every operating system.

Working at a lower level, there's also the open function.
It is a system call provided by the Linux kernel and exposed through glibc.

Both fopen and open have an input parameter: the file pathname, as a NUL-terminated string.
These two functions are declared like this:

FILE* fopen(const char* filename, const char* mode);

int open(const char* pathname, int flags);

If the file we want to access is in the current working directory, or we have the full pathname of the file as a string, this is easy to use.
However, sometimes we want to access a file relative to another directory, and the above API isn't so easy to use.

Directory Path + Filename

One such occasion is in my NDNph library: I wanted to use a directory in the filesystem as a persistent key-value store, where object keys are used as filenames, and object value is written as file content.
The API for this key-value store looks like this:

typedef struct KV KV;

/**
 * @brief Open a key-value store at specified path
 * @param[out] kv key-value store object
 * @param dir directory pathname
 * @return whether success
 */
bool KV_Open(KV* kv, const char* dir);

/**
 * @brief Write @p value to file @p dir "/" @p key
 * @param kv key-value store object
 * @param key filename
 * @param value file content
 * @param size size of file content
 * @return whether success
 */
bool KV_Save(KV* kv, const char* key, const uint8_t* value, size_t size);

Since fopen and open want the file pathname as a single string, I have to concatenate dir and key in KV_Save.
This in turn requires saving a copy of dir in KV_Open function.

typedef struct KV
{
  char* dir;
} KV;

bool KV_Open(KV* kv, const char* dir)
{
  struct stat st;
  if (stat(dir, &st) != 0 || !S_ISDIR(st.st_mode)) {
    return false;
  }
  kv->dir = strdup(dir);
  return true;
}

bool KV_Save(KV* kv, const char* key, const uint8_t* value, size_t size)
{
  char pathname[PATH_MAX];
  int res = snprintf(pathname, sizeof(pathname), "%s/%s", kv->dir, key);
  if (res < 0 || res >= sizeof(pathname)) {
    return false;
  }

  int fd = open(pathname, O_WRONLY | O_CREAT, 0644);
  if (fd < 0) {
    return false;
  }

  // TODO write and close file
}

openat

This week, I came across a new function: openat.
It operates in the same way as open, except that it supports specifying a relative pathname interpreted relative to another directory, which is represented by a file descriptor.

The function signature of openat is:

int openat(int dirfd, const char* pathname, int flags);

This allows me to simplify the key-value store:

typedef struct KV
{
  int dirfd;
} KV;

bool KV_Open(KV* kv, const char* dir)
{
  kv->dirfd = open(dir, O_RDONLY | O_DIRECTORY);
  return kv->dirfd >= 0;
}

bool KV_Save(KV* kv, const char* key, const uint8_t* value, size_t size)
{
  int fd = openat(kv->dirfd, key, O_WRONLY | O_CREAT, 0644);
  if (fd < 0) {
    return false;
  }

  // TODO write and close file
}

KV_Open opens the directory as a file descriptor with the open function.
The O_DIRECTORY flag ensures we are opening a directory instead of a regular file.
It's no longer necessary to save a copy of the directory path.

KV_Save calls openat with the directory file descriptor and the filename key.
It's no longer necessary to perform string concatenation.
The code is 5 lines shorter than the open-based solution.

Conclusion and Code Download

This article introduces Linux openat syscall that I recently discovered.
The openat function enables resolving a filename or relative path, relative to another directory that is not the current working directory.
It can do so without requiring manual string concatenation.

Code samples (whole program including load/save/delete functions):

open.c: key-value store implemented with open
openat.c: key-value store implemented with openat
view on GitHub Gist

Caution: this proof-of-concept code assumes that key is a valid filename.
It cannot safely handle untrusted and potentially malicious input.

Deep Atlantic Storage: Streaming Bits

Junxiao Shi — Sun, 11 Jul 2021 19:42:27 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/das-stream-bits/

I'm bored on 4th of July holiday, so I made a wacky webpage: Deep Atlantic Storage.
It is described as a free file storage service, where you can upload any file to be stored deep in the Atlantic Ocean, with no size limit and content restriction whatsoever.
How does it work, and how can I afford to provide it?

This article is the third of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
The first part revealed that the uploaded file is sorted which drastically reduces its storage demand, and introduced the bit sorting algorithm.
The second part covered how to process the upload in the browser using Web Workers.
Now I'd continue from there, and explain where I store the files and how I offer downloads with reasonable costs.

Storage in the URL

Deep Atlantic Storage sorts the bits in every uploaded file.
After sorting, each file can be represented by two numbers: the number of 0 bits, the number of 1 bits.
Given these two numbers, the sorted file can be reconstructed.

I could make a database or use one of those fancy NoSQL thingy to store those numbers that represent the files, but I prefer my websites stateless so that I don't need to take backups.
Therefore, I decided to encode those numbers in the URI.

Each URI created by the Deep Atlantic Storage looks like this:

https://summer-host-storage.yoursunny.dev/6705fb/18fa05/%E2%98%80%EF%B8%8F.bin
                                          ^        ^          ^
                                          zeros    ones       filename
                                          (in hexadecimal)    (URI encoded)

Whenever someone requests this URI, the server program can extract the number of 0 bits and 1 bits from the URI, and reconstruct the sorted file accordingly.
By having all the information in the URI itself, I can run a storage service without maintaining any server-side storage.

Bit Counts » Byte Array

Given the number of 0 bits and 1 bits in a file, how to generate a file with those bits?
The naive way is:

Generate a string of "0" and "1" repeated for requested length.
Parse the string into an array of bytes.
Write those bytes to a file.

The code looks like this:

def makeFileFromBitCounts(filename: str, cnt0: int, cnt1: int) -> None:
    bitString = '0' * cnt0 + '1' * cnt1
    byteCount = (cnt0 + cnt1) // 8
    arrayOfBytes = int(bitString, base=2).to_bytes(byteCount, byteorder='big')
    with open(filename, mode='wb') as f:
        f.write(arrayOfBytes)

However, this approach is vastly inefficient in memory usage:

The array of bytes has the length of the entire file, and it is allocated in memory.
Even worse, the bit string has 8x the file size, demanding even more memory.

Bit Counts » Stream

Instead of reconstructing the file as a byte array in the memory, I can write the bits to an output stream (which could be a file or a network socket) as I generate them.
However, there's one little problem: in most programming languages, the stream I/O functions are byte-oriented, not bit-oriented.
In other words, I can only write bytes, not bits, to the stream.

Looking at the structure of a sorted file in bytes, it has three parts:

A consecutive run of 0x00 bytes.
Possibly, one byte that is neither 0x00 nor 0xFF.
A consecutive run of 0xFF bytes.

In order to write the file to a stream using byte-oriented API, I need to calculate three things:

The number of 0x00 bytes.
Whether the middle byte exists, and its value.
The number of 0xFF bytes.

Since each byte has 8 bits, suppose there are cnt0 zero bits and cnt1 one bits:

The number of 0x00 bytes should be cnt0 ÷ 8, rounded down.
The number of 0xFF bytes should be cnt1 ÷ 8, rounded down.
If the whole bytes did not cover all the bits, there would be a middle byte.
- This byte should contain cnt0 mod 8 zeros and cnt1 mod 8 ones.
- Since cnt0 + cnt1 is divisible by 8, (cnt0 mod 8) + (cnt1 mod 8) is expected to equal 8.
- Bit numbering within a byte can go either direction, but I picked "Most Significant Bit first" order.

The following code does the calculations and writes the bits to an output stream (try on Coliru):

void
streamFileFromBitCounts(std::ostream& os, size_t cnt0, size_t cnt1)
{
  assert((cnt0 + cnt1) % 8 == 0);

  size_t bytes0 = cnt0 / 8;
  size_t bytes1 = cnt1 / 8;

  std::optional<uint8_t> middleByte;
  size_t middle0 = cnt0 % 8;
  size_t middle1 = cnt1 % 8;
  if (middle0 + middle1 > 0) {
    assert(middle0 + middle1 == 8);
    middleByte = 0xFF >> middle0;
  }

  for (size_t i = 0; i < bytes0; ++i) {
    os.put(static_cast<uint8_t>(0x00));
  }
  if (middleByte.has_value()) {
    os.put(middleByte.value());
  }
  for (size_t i = 0; i < bytes1; ++i) {
    os.put(static_cast<uint8_t>(0xFF));
  }
}

Deep Atlantic Storage runs this logic on a server rather than in the browser.
While Blob API and URL.createObjectURL() allow generating a downloadable file from JavaScript, the entire file must be allocated in memory.
Browser support for streaming from JavaScript is still at an early stage.

Stream » HTTP Server

Deep Atlantic Storage offers file downloads from an HTTP server.
The server, dubbed Deep Atlantic Storage app, is built upon the logic above, with a few improvements:

The response is piped through a gzip compressor, in order to save network egress from my server.
For long runs of 0x00 and 0xFF bytes, instead of writing one byte at a time, the program writes them in pages of 1MB each.
A small delay is added after writing each page to throttle the downloads and avoid consuming too much CPU.
If the client has disconnected, stop writing and return right away.

This is the HTTP handler implementation:

var (
  buf0 = make([]byte, 1048576)               // create 1MB page filled with 0x00 bytes
  buf1 = bytes.Repeat([]byte{0xFF}, 1048576) // create 1MB page filled with 0xFF bytes
)

func handler(w http.ResponseWriter, req *http.Request) {
  // parse URI and extract number of zeros and ones
  var cnt0, cnt1 int
  var name string
  if _, e := fmt.Sscanf(req.URL.Path, "/%x/%x/%s", &cnt0, &cnt1, &name); e != nil {
    w.WriteHeader(http.StatusNotFound)
    return
  }

  // tell browser/client that:
  // (1) the response is binary file, not text or HTML
  // (2) the response is gzip compressed
  // (3) browser should prompt for a download instead of display the file
  w.Header().Set("Content-Type", "application/octet-stream")
  w.Header().Set("Content-Encoding", "gzip")
  w.Header().Set("Content-Disposition", "attachment")

  // calculate number of 0x00 and 0xFF pages and leftover bytes, and the middle byte
  bytes0, bytes1 := cnt0/8, cnt1/8
  middle0, middle1 := cnt0%8, cnt1%8
  pages0, pages1 := bytes0/len(buf0), bytes1/len(buf1)
  bytes0 -= pages0 * len(buf0)
  bytes1 -= pages1 * len(buf1)

  z, _ := gzip.NewWriterLevel(w, 1) // make gzip compressor, fastest mode
  defer z.Close()                   // close and flush when it's done

  writePages := func(page []byte, count int) error { // subroutine to write some pages
    ctx := req.Context()
    for i := 0; i < count; i++ {
      z.Write(page) // pipe one page to the gzip compressor
      select {
      case <-ctx.Done(): // client disconnected
        return ctx.Err() // return non-nil error
      case <-time.After(time.Millisecond): // delay 1ms and continue writing
      }
    }
    return nil
  }

  if e := writePages(buf0, pages0); e != nil { // write 0x00 pages
    return // stop if client has disconnected
  }
  z.Write(buf0[:bytes0]) // write leftover 0x00 bytes
  if middle0+middle1 > 0 { // write the middle byte, if there is one
    z.Write([]byte{0xFF >> middle0})
  }
  z.Write(buf1[:bytes1]) // write leftover 0xFF bytes
  writePages(buf1, pages1) // write 0xFF pages
}

The actual server has some additional logic for verifying the HTTP request verb and Accept-Encoding: gzip header.
You can see its source code in this Gist.

HTTP Server » HTTPS Server

It's 2021 and every website is expected to have HTTPS.
Moreover, the .dev domain I'm using is designated as a "secure namespace" such that most browsers won't even connect to it over plain HTTP.
Therefore, I need to deploy Deep Atlantic Storage app over HTTPS.

I turned to my favorite TLS termination solution, Caddy server, for this task.
The Caddyfile uses a reverse_proxy directive to the HTTP server:

https://summer-host-storage.yoursunny.dev {
  reverse_proxy http://127.0.0.1:3333 {
    flush_interval 1s
    transport http {
      compression off
    }
  }
}

Caddy by default would make request to the HTTP backend server with Accept-Encoding: gzip request header, and then decompress the response if the incoming request does not accept gzip compression.
This is undesirable for Deep Atlantic Storage because my server can possibly send large responses, consuming too much egress bandwidth.
Therefore, I explicitly disabled HTTP transport compression, so that the incoming request is served only if the client accepts gzip compression, and the outgoing response is always compressed.

Conclusion

This article is the final installment of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
Given the bit counts generated by Web Workers, I built and deployed a server that reconstructs the file as gzip'ed HTTP response.

While Deep Atlantic Storage started as a joke, it is a nice exercise to learn the algorithms and APIs around bits, bytes, and blobs.
I enjoyed building the app, and I hope you learned something from these articles.

Deep Atlantic Storage: Reading File Upload in Web Workers

Junxiao Shi — Sun, 11 Jul 2021 19:39:30 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/das-file-worker/

This article is the second of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
The previous part introduced the algorithm I use to sort all the bits in a Uint8Array.
Now I'd continue from there, and explain how the webpage accepts and processes file uploads.

File Upload

File upload has always been a part of HTML standard as long as I remembered:

<form action="upload.php" method="POST" enctype="multipart/form-data">
  <input type="file" name="file">
  <input type="submit" value="upload">
</form>

This would create a Browse button that allows the user to select a local file.
When the form is submitted, the file name and content are sent to the server, and a server-side script can process the upload.

It's straightforward, but not ideal for Deep Atlantic Storage.
As explained in the last article, regardless of how large a file is, the result of sorting all the bits could be represented by just two numbers: how many 0 bits and 1 bits are in the file.
It is unnecessary to send the whole file to the server; instead, counting in the browser would be a lot faster.

File and Blob

Fast forward to 2021, JavaScript can do everything.

In JavaScript, given the DOM object corresponding to the <input type="file"> element, I can access the (first) selected file via .files[0] property.
Using files from web applications has further explanation of these APIs.

.files[0] returns a File object, which is a subclass of Blob.
Then, Blob.prototype.arrayBuffer() function asynchronously reads the entire file into an ArrayBuffer, providing access to its content.

<form id="demo_form">
<input id="demo_upload" type="file" required>
<input type="submit">
</form>
<script>
document.querySelector("#demo_form").addEventListener("submit", async (evt) => {
  evt.preventDefault();
  const file = document.querySelector("#demo_upload").files[0];
  console.log(`file size ${file.size} bytes`);
  const payload = new Uint8Array(await file.arrayBuffer());
  const [cnt0, cnt1] = countBits(payload); // from the previous article
  console.log(`file has ${cnt0} zeros and ${cnt1} ones`);
});
</script>

This code adds an event listener to the <form>.
When the form is submitted, the callback function reads the file into an ArrayBuffer and passes it as a Uint8Array to the bit counting function (countBits from the previous article).

ReadableStream

file.arrayBuffer() works, but there's a problem: if the user selects a huge file, the entire file has to be read into the memory all at once, causing considerable memory stress.
To solve this problem, I can use Streams API to read the file in smaller chunks, and process each chunk before reading the next.

From a Blob object (such as the file in the snippet above), I can call .stream().getReader() to create a ReadableStreamDefaultReader.
Then, I can repeatedly call reader.read(), which returns a Promise that resolves to either a chunk of data or an end-of-file (EOF) indication.

To process the file chunk by chunk and count how many 1 bits are there, my strategy is:

Call reader.read() in a loop to obtain the next chunk.
If done is true, indicating EOF has been reached, break the loop.
Add the number of 1 bits in each byte of the chunk into the overall counter.
Finally, calculate how many 0 bits are there from the file size, accessible via blob.size property.

async function countBitsBlob(blob: Blob): Promise<[cnt0: number, cnt1: number]> {
  const reader = (blob.stream() as ReadableStream<Uint8Array>).getReader();
  let cnt = 0;
  while (true) {
    const { done, value: chunk } = await reader.read();
    if (done) {
      break;
    }
    for (const b of chunk!) {
      cnt += ONES[b];
    }
  }
  return [8 * blob.size - cnt, cnt];
}

Web Worker

In a web application, it's best to execute complex computations on a background thread, so that the main thread can react to user interactions swiftly.
Web Workers are a simple means for web content to run scripts in background threads.
In Deep Atlantic Storage, I delegated the task of sorting or counting bits in the file to a web worker.

When the user selects a file and submits the form, the form event handler creates a Worker (if it has not done so), and calls Worker.prototype.postMessage() to pass the File object to the background thread.

let worker;
document.querySelector("#demo_form").addEventListener("submit", async (evt) => {
  evt.preventDefault();
  const file = document.querySelector("#demo_upload").files[0];
  worker ??= new Worker("worker.js");
  worker.onmessage = handleWorkerMessage; // described later
  worker.postMessage(file);
});

The worker.js runs in the background.
It receives the message (a MessageEvent enclosing a File object) in a function assigned to the global onmessage variable.
This function then calls countBitsBlob to count how many zeros and ones are in the file, then calls the global postMessage function to pass the result back to the webpage main thread.
It also catches any errors that might have been thrown, and passes those to the main thread as well.
I've included type: "result" and type: "error" in these two types of messages, so that the main thread can distinguish between them.

onmessage = async (evt) => {
  const file = evt.data;
  try {
    const result = await countBitsBlob(file);
    postMessage({ type: "result", result });
  } catch (err) {
    postMessage({ type: "error", error: `${err}` });
  }
};

Notice that in the catch clause, the Error object is converted to a string before being passed to postMessage.
This is necessary because only a handful of types can pass through postMessage, but Error is not one of them.

Back in the main thread, the handleWorkerMessage function, which was assigned to worker.onmessage property, receives messages from the worker thread.

function handleWorkerMessage(evt) {
  const response = evt.data;
  switch (response.type) {
    case "result": {
      const [cnt0, cnt1] = response.result;
      console.log(`file has ${cnt0} zeros and ${cnt1} ones`);
      break;
    }
    case "error": {
      console.error("worker error", response.error);
      break;
    }
  }
}

Combined with some user interface magic (not described in this article, but you can look at the webpage source code), this makes up the Deep Atlantic Storage webpage.

Summary

This article is the second of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
Building upon the bit counting algorithm designed in the previous article, I turned it into a web application that reads an uploaded file chunk by chunk via Streams API, and moved the heavy lifting to a background thread via Web Workers.
The next part in this series will explain how I made a server to reconstruct the file from the bit counts.

Deep Atlantic Storage: Sorting Bits

Junxiao Shi — Sun, 11 Jul 2021 19:34:11 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/das-sort-bits/

I'm bored on 4th of July holiday, so I made a wacky webpage: Deep Atlantic Storage.
It is described as a free file storage service, where you can upload any file to be stored deep in the Atlantic Ocean, with no size limit and content restriction whatsoever.
Since Chia currency farming became popular in May, hard drive prices went up significantly.
How can I afford to operate an unlimited free storage service?

"Advanced Sorting Technology"

One of the benefits listed on Deep Atlantic Storage webpage is:

Advanced sorting technology keeps your data neatly ordered.

What this means is that, content in the uploaded file would be sorted before being stored.

A sorting algorithm is an algorithm that puts elements of a list in a certain order, such as numerical order or lexicographical order.
Every coder knows a few sorting algorithms, such as:

quick sort
bubble sort
merge sort
insertion sort
selection sort

Most sorting algorithms are comparison sorts that rely on a comparison function to determine the relative order between two elements.
For example, the program below (try on Compiler Explorer) sorts a list of points on a two-dimensional Euclidean plane by its distance from the origin.
It uses std::sort function from the C++ standard library, passing a custom comparison function that returns true if the first point is closer to the origin point (0,0) than the second point, or false otherwise.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>

struct Point
{
  double x;
  double y;
};

int main() {
  std::vector<Point> points{
    {  1.0,  2.0 },
    {  2.0,  0.9 },
    {  0.9, -2.0 },
    {  0.0,  0.0 },
    { -1.4,  0.0 },
    { -1.4, -0.7 },
  };
  std::sort(points.begin(), points.end(), [] (const Point& a, const Point& b) {
    return std::sqrt(a.x * a.x + a.y * a.y) < std::sqrt(b.x * b.x + b.y * b.y);
  });
  for (const Point& point : points) {
    std::printf("%+0.1f, %+0.1f\n", point.x, point.y);
  }
}

The input and output of a sorting algorithm are both a list of elements.
Deep Atlantic Storage deals with files.
A file must first be turned into a list of elements before it can be sorted.

There are many ways to interpret a file as a list of elements.
If the file is a database, following the database structure, each table in the database is a list of rows that can be sorted.
If the file is plain text, the Unix sort command can read it as a list of text lines that can be sorted.

In Deep Atlantic Storage, I decided to use the most basic unit of information: bit.
When you upload a file to my unlimited storage service, the bits contained in the file are sorted in ascending order.
For example, suppose the file has the text:

@yoursunny

In binary form it is:

@        y        o        u        r        s        n        n        n        y
01000000 01111001 01101111 01110101 01110010 01110011 01110101 01101110 01101110 01111001

If I sort all the bits, it becomes:

00000000 00000000 00000000 00000000 00111111 11111111 11111111 11111111 11111111 11111111

Sorting Bits » Counting Bits

Naively, I can collect every bit in the input file into a list of bits, and sort them using a "normal" sort algorithm (try on RunKit):

const input = Buffer.from("@yoursunny");
const bits = [];
for (const b of input) {
  for (let s = 0; s < 8; ++s) {
    bits.push((b >> s) & 0x01);
  }
}
let compares = 0;
bits.sort((a, b) => {
  ++compares;
  return a - b;
});
console.log(
  `${bits.length} elements`,
  `${compares} compares`,
  JSON.stringify(bits),
);

Array.prototype.sort() is a comparison sort algorithm.
Theoretically, a comparison sort algorithm cannot perform better than O(n log n) comparisons, where n is the number of elements in the input list.
For my 80-bit input, Node.js v16.3.0 invoked the comparison function 322 times.
If the input was longer, considerably more comparisons would be needed.

Since there are only two possible values, 0 and 1, for each bit, there is a better algorithm: counting sort.
Counting sort is an integer sorting algorithm suitable for a list of small non-negative integers.
It does not use a comparison function and hence is a non-comparison sorting algorithm.
Instead, counting sort first counts how many elements possess each distinct key value, then uses these counts to determine the positions of each key value in the output list.
Its time complexity is O(n+k), where n is the number of elements and k is the maximum integer key value in the list.

A counting sort on the same input can be written as (try on Go Playground):

package main

import (
    "fmt"
)

func sortBits(bits []int) (sorted []int) {
    m := make(map[int]int)
    for _, bit := range bits {
        m[bit]++
    }
    for bit := 0; bit <= 1; bit++ {
        for i, n := 0, m[bit]; i < n; i++ {
            sorted = append(sorted, bit)
        }
    }
    return sorted
}

func main() {
    var bits []int
    for _, b := range []byte("@yoursunny") {
        for s := uint(0); s < 8; s++ {
            bit := (b >> s) & 0x01
            bits = append(bits, int(bit))
        }
    }

    sorted := sortBits(bits)
    fmt.Println(sorted)
}

Sorted Bits » Bit Counts

A sorting algorithm does not change the size of the list being sorted.
Suppose a 1GB file is uploaded to Deep Atlantic Storage, there are 8589934592 bits in this file before sorting, and there would be still 8589934592 bits after sorting.
Storing a sorted file takes as much disk space as storing the original unsorted file.

Looking at the sorted bits, there is an important observation:
after sorting, all the 0 bits are together, and all the 1 bits are together!

00000000 00000000 00000000 00000000 00111111 11111111 11111111 11111111 11111111 11111111
\_____________ 34 zeros _____________/\____________________ 46 ones ____________________/

Instead of storing the same bit repeatedly, I only need to remember: "there are 34 zeros followed by 46 ones".
This allows Deep Atlantic Storage to store sorted large files with considerably less disk space than the original files: any file, regardless of its size, can be represented by two numbers.

Given a list of sorted bits, I can iterate over the list and count the number of consecutive zeros and ones:

from itertools import groupby

bits = "00000000000000000000000000000000001111111111111111111111111111111111111111111111"
for bit, g in groupby(bits):
    print(bit, len(list(g)))

This is, in fact, the basic idea of run-length encoding, a lossless data compression method.

However, it's unnecessary to run a sorting algorithm followed by a compression algorithm.
Instead, I can let the counting sort algorithm return the counters for zeros and ones directly, skipping the unnecessary step of constructing a sorted list of bits.

Well, actually I don't even need to count both zeros and ones.
Since there are 8 bits in every byte, it suffices to only count the 1 bits, and I can calculate the number 0 bits to be 8 * bytes - ones.

With that, our bit ~~sorting~~ counting algorithm becomes:

function countBits(input: Uint8Array): [cnt0: number, cnt1: number] {
  let cnt = 0;
  for (const b of input) {
    for (let s = 0; s < 8; ++s) {
      if ((b >> s) % 2 === 1) {
        ++cnt;
      }
    }
  }
  return [8 * input.length - cnt, cnt];
}

Bit Counting » Byte Counting

Looking at the bit counting algorithm, the inner loop that iterates over the bits within a byte would be executed once for every byte, which is a hot spot worth optimization.
To optimize this code, I aim at eliminating the loop.

In a byte, there are 256 possible values between 0x00 and 0xFF.
The number of zeros and ones in each byte value never changes.
Therefore, it is unnecessary to loop over the bits every time.
Instead, I can build a lookup table that maps a byte value into the number of ~~zeros and~~ ones in that byte.

This code, executed during initialization, prepares the lookup table:

const ONES = [];
for (let b = 0x00; b <= 0xFF; ++b) {
  let cnt = 0;
  for (let s = 0; s < 8; ++s) {
    if ((b >> s) % 2 === 1) {
      ++cnt;
    }
  }
  ONES.push(cnt);
}

Using this lookup table, I can count bits in a file more efficiently:

function countBits(input: Uint8Array): [cnt0: number, cnt1: number] {
  let cnt = 0;
  for (const b of input) {
    cnt += ONES[b];
  }
  return [8 * input.length - cnt, cnt];
}

As measured on JSBEN.CH, the lookup table approach is 3~5x faster than the previous algorithm.

Summary

In this article, I reviewed commonly used sorting algorithms, explained why counting sort is more efficient on a list of bits where each bit is either 0 or 1, explored how to compactly store sorted bits as two numbers, and finally optimized the algorithm using a lookup table.

This article is the first of a 3-part series that reveals the secrets behind Deep Atlantic Storage.
The next part in this series will explain how the bit sorting aka byte counting algorithm is used in a web application.

Google Code Jam 2021 is Coming

Junxiao Shi — Fri, 26 Mar 2021 12:31:10 +0000

Code Jam is an annual programming competition organized by Google, with a focus on algorithms.

The Qualifications Round of Code Jam 2021 starts today, and continues for 30 hours.
You can register and participate at the Code Jam website: https://g.co/codejam

How Many Servers Do You Need for a Crucial Website?

Junxiao Shi — Fri, 19 Mar 2021 04:55:30 +0000

A crucial website ought to have:

a primary server: Ryzen CPU, NVMe storage.
a secondary standby: Xeon CPU, SSD storage.
a third replica: Atom CPU, spinning rust storage.
a fourth backup: ARMv5 CPU, VHS tape.
a system to automatically perform failover.
a cat to look over this system.
a robot to feed the cat.
an engineer to repair the robot.

These can get your data 99.99% secure.

Now add some cold storage:

punch cards kept in California.
microfilm buried in Antarctica.
vinyl record launched to Jupiter.

If all four online servers are lost, you are looking at a lengthy downtime, but your data would be 99.9999% secure by recovering from the cold storage.

To finally reach 100%, transmit your data as radio waves toward a black hole.
If California fells into the ocean, Antarctica melts, and the sun explodes taking out Jupiter, you can travel to the black hole and access your data.

According to physics, information cannot be destroyed by a black hole.
It's the ultimate storage with infinite space.
Once you enter the black hole, you won't be able to come back, but you are with your data forever.

OVH Strasbourg: Halt and Catch Fire, Data Uploaded to the Cloud

Junxiao Shi — Sat, 13 Mar 2021 01:21:15 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/OVH-halt-and-catch-fire/

2021-03-10, an OVH Cloud data center in Strasbourg, France caught on fire.
Thousands of servers have been destroyed by fire.
Thousands more are currently unavailable due to power cut, and will remain offline for several more days.

Data stored in those servers have been uploaded to the cloud via black smoke.

According to Hacker News, a Dev mistakenly invoked the Halt and Catch Fire instruction on an Uninterrupted Power Supply unit, causing this incident.

Chairman of OVH cloud advised clients to activate their disaster recovery plans, such as restoring off-site backups to a new cloud server.
Some clients are crying because they did not have backups, or they stored their backups on another machine in the same data center.
Other clients experienced no downtime because they designed their systems for datacenter scale redundancy.

Rename WiFi Interface on Ubuntu 20.04

Junxiao Shi — Fri, 05 Mar 2021 01:43:47 +0000

This post is originally published on yoursunny.com blog https://yoursunny.com/t/2021/WiFi-rename/

During an experiment, I need to use three WiFi interfaces on a Raspberry Pi running Ubuntu 20.04.
In addition to Raspberry Pi's internal WiFi interface, I added two USB WiFi adapters.
Three network interfaces showed up in the system (ip link command), and they are named wlan0, wlan1, and wlan2 by default.

I often need to capture packets with tcpdump, and I often have to be type these interface names manually.
It isn't easy to remember the purpose of each network interface, so I wanted to rename the interfaces to reflect their role in my application.
However, this isn't as easy as it sounds.

🚫 Netplan

Ubuntu 20.04 configures network interfaces using Netplan, so my first thought was: I can write a Netplan configuration that matches network interfaces with their MAC addresses, and assigns the desired name to each network interface.

The config file would look like this:

network:
  version: 2
  wifis:
    uplink:
      optional: true
      match:
        macaddress: ba:fe:de:f0:b9:e4
      set-name: uplink
      access-points:
        home:
          password: rP8jKHJ64
      dhcp4: true
      dhcp6: true
      accept-ra: true

However, this method would not work:

$ sudo netplan apply
ERROR: uplink: networkd backend does not support wifi with match:, only by interface name

🚫 70-persistent-net.rules

Many online guides refer to a file /etc/udev/rules.d/70-persistent-net.rules, which is processed by udev during boot.
The file should have been created automatically by the system upon discovery of the network interfaces, and I just need to modify the interface names to the desired names.

However, this file does not exist in Ubuntu 20.04, so it's another dead end.

✔️ systemd.link

After carefully reading Debian's NetworkInterfaceNames guide, I found the correct way: systemd.link.

To rename WiFi interfaces, I can create a systemd configuration file for each network interface:

echo '[Match]
MACAddress=ba:fe:de:f0:b9:e4
[Link]
Name=uplink' | sudo tee /etc/systemd/network/10-uplink.link

After rebooting, the network interface is renamed to what I wanted.

What would you need 64GB of RAM for?

Junxiao Shi — Sat, 27 Feb 2021 06:09:19 +0000

This post is originally published on Quora, with code links at the end

I used 58GB of RAM once. NodeJS refuses to use more memory and I had to rewrite the program in C++.

It's in a research project. I captured a packet trace from Network File System (NFS) server, and I want to reconstruct the complete pathnames accessed in each command. The way NFS works is that, every command only carries a component of the name (like a directory name or a filename within a directory), along with a handle that represents the directory in which the file resides. To get the complete pathname, I need a lookup table of all known handles and their corresponding pathnames. Then, for each new command that has a handle and one more name component, I can query this lookup table to find out the pathname of that handle, and append the new component to get the complete pathname. Finally, I'd insert the new pathname along with the new handle into the table.

I have 24 hours of packet trace with millions of these handles. It shouldn't take so much memory, but I somehow decided to write the program in NodeJS. NodeJS struggled to allocate more and more memory as it reads the input, until it reaches 58GB after several hours. The machine has 96GB but NodeJS won't use more memory. I can tell that it's no longer making progress, because records in /proc/*/fdinfo indicates that the cursor in input file isn't moving anymore.

I spent four hours rewriting this part of the program in C++. More specifically, I hosted the lookup table in a C++ program, and had the NodeJS program communicate with C++ process via Unix socket. The program completed in 15 minutes with no more than 1GB of memory.

Conclusion: if you need 64GB of memory just for data structures, you probably need a better programming language.

source code links

https://github.com/yoursunny/nfsdump

pathtree/fullpath.js is the Node.js edition, for Node.js v0.6 on Ubuntu 12.04.
pathtree/fullpath.cc is the C++ edition implementing same functionality.

highlighted Quora comments

Michael Johnson-Moore
Conclusion 2: If you need something to be fast, don't use an interpreted language.

Alex Bujorianu
Many more developers should heed this lesson! ... I really don’t understand why a cloud desktop client, a text editor (!) etc. need 100MB of memory per instance.

Ubeyde Mavus
Or you need to know your way around C++ better than your way around NodeJS.

Hacktoberfest 2020 shirt arrived

Junxiao Shi — Sat, 20 Feb 2021 03:49:05 +0000

I managed to finish the challenge despite that the rules changed 3 times during the month. Most of my contributions went to DefinitelyTyped, a collection of TypeScript definitions that make my own life easier.

I picked the dark-colored shirt, so that it wouldn't get ruined if I decide to roll around in the mud. Yes I still do that, because it relieves stress.