komamitsu

# Wormhole4j v0.3.0: Adding Multi-threaded Concurrency

## 1. Introduction

- Quick recap of Wormhole4j
- What changed in v0.3.0 (real multi-thread support)
- Why this matters

---

komamitsu

### Blog Post Structure: "Scaling Wormhole4j: Lock-Free Concurrency and Verified Correctness"

#### 1. Introduction: The Evolution
* **The Mission:** Briefly recap the original *Wormhole* paper (EuroSys '19) goal: a fast $O(\log L)$ ordered index.
* **The Problem:** While the original was a performance breakthrough, it was strictly single-threaded. Real-world infrastructure requires concurrency.
* **The Announcement:** Introduce v0.3.0, the culmination of adding multi-threaded support while preserving the core performance advantages.

#### 2. The Architecture of Concurrency
* **The Structural Conflict:** Explain why concurrent ordered indexes are difficult—modifications like splits/merges ripple through both the `LeafList` and the `MetaTrieHT`, creating a bottleneck.
* **The Three-Layer Strategy:** Explain the concurrency model:

komamitsu

# Wormhole4j 0.3: Thread-Safe Concurrent Access

## 1. Introduction
- Recap of Wormhole4j: fast ordered map, O(log L) lookups, EuroSys '19 paper
- The gap: single-threaded only until now
- What this post covers: design, correctness verification, benchmarks

## 2. Why Concurrent Ordered Indexes Are Hard
- Maintaining order + range scans rules out simple approaches
- The specific problem: splits/merges modify both the LeafList

komamitsu

Execute xremap as root user

Create /etc/systemd/system/xremap.service file

[Unit]
Description=xremap service
After=default.target

[Service]

komamitsu

package org.komamitsu.foobar;

import org.graalvm.nativeimage.IsolateThread;
import org.graalvm.nativeimage.c.function.CEntryPoint;
import org.graalvm.nativeimage.c.type.CCharPointer;
import org.graalvm.nativeimage.c.type.CTypeConversion;

public class SharedStringMethod
{
    @CEntryPoint(name = "add")

komamitsu

    <uses-permission android:name="android.permission.ACCESS_WIFI_STATE"></uses-permission>
    <uses-permission android:name="android.permission.INTERNET"></uses-permission>

komamitsu

package com.komamitsu;

import java.io.IOException;
import java.net.InetSocketAddress;
import java.nio.ByteBuffer;
import java.nio.channels.SelectionKey;
import java.nio.channels.Selector;
import java.nio.channels.ServerSocketChannel;
import java.nio.channels.SocketChannel;
import java.util.Iterator;

komamitsu

Goal

• Make Muhenkan key a left Control key
• Make Hiragana Katakana key an Escape key
• Make Capslock key a Zenkaku Hankaku key

Options

• xmodmap: Easy, but my laptop's suspend/resume resets xmodmap configuration
• xkb: Let's try this

komamitsu

import com.fasterxml.jackson.annotation.JsonCreator;
import com.fasterxml.jackson.annotation.JsonProperty;
import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.apache.fury.Fury;
import org.apache.fury.config.Language;
import org.msgpack.jackson.dataformat.MessagePackMapper;

import java.io.IOException;
import java.util.*;

komamitsu

with recursive r(a, b) as (
  select 0::int, 1::int
  union all
  select b, a + b from r where b < 1000
)
select a from r;

  a  
-----
   0