This article analyzes TokuDB’s index structure—the fractal tree—from an engineering implementation perspective. It describes the on-disk storage layout of ft-index in detail, how ft-index implements point queries, range queries, and insert/delete/update operations, and throughout the discussion attempts a detailed comparison with InnoDB’s B+ tree from multiple angles. Introduction to the Fractal Tree The fractal tree is a write-optimized on-disk index data structure. In general, fractal trees offer good write performance (insert/update/delete) while still providing read performance close to that of a B+ tree....

Online version: PPT This is a technical talk on Vitess I gave internally at my company. The main topics are: Vitess feature modules, capabilities, and system architecture Vitess sharding approach SQL syntax supported by Vitess How Vitess resharding works Vitess data backup internals Pros and cons of Vitess compared with traditional relational databases and NoSQL A side note To try building an online PPT with Markdown, I experimented with a few options....

I took Google’s online campus hiring written test yesterday. Skip algorithms for a day and your skills slide right back down. Problem A. Password Attacker Description How many passwords of length M can be formed from N distinct characters, such that every password uses all N characters at least once? Solution 1: Brute Force For each solution to the equation below, add the number of distinct permutations. If one solution is X1, …, Xn, that group contributes M!...

Basic LevelDB constraints With the default options, LevelDB follows these basic constraints: LevelDB has 7 levels: 0, 1, 2, 3, 4, 5, and 6. SSTables on level 0 are about 4 MB each. On level i (i > 0), each SSTable is at most 2 MB. Level 0 ideally has 4 SSTables, should stay within 8, and must not exceed 12. The total storage used by all SSTables on level i (i > 0) should stay around 10^i MB....

After grinding LeetCode for several days, I finally finished. Code is here. Reverse Words in a String Simulation on strings Evaluate Reverse Polish Notation Simulation — evaluate postfix expressions Max Points on a Line Given N points in the plane, find a line that passes through the most points. Enumerate each point as the origin, compute relative coordinates, then compute y/x and use a hash table to count duplicates and find the maximum....

Zookeeper hardly needs an introduction — it is a distributed coordination service. A few questions I was curious about: How does ZooKeeper implement asynchronous watcher callbacks? (code-level details) How does ZooKeeper implement distributed locks? How do Queue, barrier, and similar recipes work? I read the Python client kazoo and got the general picture. A simple client example #!/usr/bin/python import logging from time import sleep from kazoo.client import KazooClient # print log to console logging....

Source code and related articles are available here. This article discusses the K-th largest or K-th smallest element in a sequence. Since the K-th largest can be reduced to finding the (N−K+1)-th smallest (where N is the sequence length), we focus on the K-th smallest element. Problems covered in this article: Given an integer sequence, find the K-th smallest element. Given an integer sequence that supports dynamic updates, answer queries for the K-th smallest element....

Hash Table A hash table is an array of size buckets, table[0...size-1]. Hashing an object yields an index; we store the object in table[value]. When a bucket holds multiple objects, they are chained into a linked list. This collision strategy is called separate chaining. Load Factor If a hash table has size buckets and used stored elements, used / size is the load factor. When loadFactor <= 1, expected lookup cost is O(1)....

Abstract: Plane sweep is widely used in computational geometry, computer graphics, grid computing, and related areas. Many classic algorithms use plane sweep to greatly reduce time complexity — e.g. segment intersection, union of axis-aligned rectangle perimeters, rectangle intersection, spatial collision detection, Voronoi diagram construction, closest pair of points, and more. This article introduces several plane sweep algorithms commonly used in ACM programming contests. By purpose, they fall into: Data aggregation; Detecting geometric positional relationships; Closest pair of points....

2021.01.08 Flink Forward Asia 2021 Beijing: The Best Practice of Integrating Apache Flink with Apache Iceberg 2021.04.25 Flink+Iceberg Shanghai Meetup: How Flink and Iceberg Solve the Challenges of Data Lake Ingestion 2020.12.15 Flink Forward Asia 2020 Beijing: How to Analyze CDC Data in Iceberg Data Lake Using Flink, Blog 2019.07.20 HBaseConAsia 2019 Beijing: Further GC optimization for HBase 2.x: Reading HFileBlock into offheap directly. 2018.10.18 Internal Xiaomi talk on the HBase read path PDF 2018....