• Stars
    star
    497
  • Rank 88,652 (Top 2 %)
  • Language
    Java
  • License
    Apache License 2.0
  • Created over 6 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

A fast, log structured key-value store.

HaloDB

Build Status Download

HaloDB is a fast and simple embedded key-value store written in Java. HaloDB is suitable for IO bound workloads, and is capable of handling high throughput reads and writes at submillisecond latencies.

HaloDB was written for a high-throughput, low latency distributed key-value database that powers multiple ad platforms at Yahoo, therefore all its design choices and optimizations were primarily for this use case.

Basic design principles employed in HaloDB are not new. Refer to this document for more details about the motivation for HaloDB and its inspirations.

HaloDB comprises of two main components: an index in memory which stores all the keys, and append-only log files on the persistent layer which stores all the data. To reduce Java garbage collection pressure the index is allocated in native memory, outside the Java heap.

HaloDB

Basic Operations.

            // Open a db with default options.
            HaloDBOptions options = new HaloDBOptions();
    
            // Size of each data file will be 1GB.
            options.setMaxFileSize(1024 * 1024 * 1024);

            // Size of each tombstone file will be 64MB
            // Large file size mean less file count but will slow down db open time. But if set
            // file size too small, it will result large amount of tombstone files under db folder
            options.setMaxTombstoneFileSize(64 * 1024 * 1024);

            // Set the number of threads used to scan index and tombstone files in parallel
            // to build in-memory index during db open. It must be a positive number which is
            // not greater than Runtime.getRuntime().availableProcessors().
            // It is used to speed up db open time.
            options.setBuildIndexThreads(8);

            // The threshold at which page cache is synced to disk.
            // data will be durable only if it is flushed to disk, therefore
            // more data will be lost if this value is set too high. Setting
            // this value too low might interfere with read and write performance.
            options.setFlushDataSizeBytes(10 * 1024 * 1024);
    
            // The percentage of stale data in a data file at which the file will be compacted.
            // This value helps control write and space amplification. Increasing this value will
            // reduce write amplification but will increase space amplification.
            // This along with the compactionJobRate below is the most important setting
            // for tuning HaloDB performance. If this is set to x then write amplification 
            // will be approximately 1/x. 
            options.setCompactionThresholdPerFile(0.7);
    
            // Controls how fast the compaction job should run.
            // This is the amount of data which will be copied by the compaction thread per second.
            // Optimal value depends on the compactionThresholdPerFile option.
            options.setCompactionJobRate(50 * 1024 * 1024);
    
            // Setting this value is important as it helps to preallocate enough
            // memory for the off-heap cache. If the value is too low the db might
            // need to rehash the cache. For a db of size n set this value to 2*n.
            options.setNumberOfRecords(100_000_000);
            
            // Delete operation for a key will write a tombstone record to a tombstone file.
            // the tombstone record can be removed only when all previous version of that key
            // has been deleted by the compaction job.
            // enabling this option will delete during startup all tombstone records whose previous
            // versions were removed from the data file.
            options.setCleanUpTombstonesDuringOpen(true);
    
            // HaloDB does native memory allocation for the in-memory index.
            // Enabling this option will release all allocated memory back to the kernel when the db is closed.
            // This option is not necessary if the JVM is shutdown when the db is closed, as in that case
            // allocated memory is released automatically by the kernel.
            // If using in-memory index without memory pool this option,
            // depending on the number of records in the database,
            // could be a slow as we need to call _free_ for each record.
            options.setCleanUpInMemoryIndexOnClose(false);
            
            // ** settings for memory pool **
            options.setUseMemoryPool(true);
    
            // Hash table implementation in HaloDB is similar to that of ConcurrentHashMap in Java 7.
            // Hash table is divided into segments and each segment manages its own native memory.
            // The number of segments is twice the number of cores in the machine.
            // A segment's memory is further divided into chunks whose size can be configured here. 
            options.setMemoryPoolChunkSize(2 * 1024 * 1024);
    
            // using a memory pool requires us to declare the size of keys in advance.
            // Any write request with key length greater than the declared value will fail, but it
            // is still possible to store keys smaller than this declared size. 
            options.setFixedKeySize(8);
    
            // Represents a database instance and provides all methods for operating on the database.
            HaloDB db = null;
    
            // The directory will be created if it doesn't exist and all database files will be stored in this directory
            String directory = "directory";
    
            // Open the database. Directory will be created if it doesn't exist.
            // If we are opening an existing database HaloDB needs to scan all the
            // index files to create the in-memory index, which, depending on the db size, might take a few minutes.
            db = HaloDB.open(directory, options);
    
            // key and values are byte arrays. Key size is restricted to 128 bytes.
            byte[] key1 = Ints.toByteArray(200);
            byte[] value1 = "Value for key 1".getBytes();
    
            byte[] key2 = Ints.toByteArray(300);
            byte[] value2 = "Value for key 2".getBytes();
    
            // add the key-value pair to the database.
            db.put(key1, value1);
            db.put(key2, value2);
    
            // read the value from the database.
            value1 = db.get(key1);
            value2 = db.get(key2);
    
            // delete a key from the database.
            db.delete(key1);
    
            // Open an iterator and iterate through all the key-value records.
            HaloDBIterator iterator = db.newIterator();
            while (iterator.hasNext()) {
                Record record = iterator.next();
                System.out.println(Ints.fromByteArray(record.getKey()));
                System.out.println(new String(record.getValue()));
            }
    
            // get stats and print it.
            HaloDBStats stats = db.stats();
            System.out.println(stats.toString());
    
            // reset stats
            db.resetStats();
            
            // pause background compaction thread.
            // if a file is being compacted the thread
            // will block until the compaction is complete.
            db.pauseCompaction();
            
            // resume background compaction thread.
            db.resumeCompaction();
            
            // repeatedly calling pause/resume compaction methods will have no effect.

            // Close the database.
            db.close();

Binaries for HaloDB are hosted on Bintray.

<dependency>
  <groupId>com.oath.halodb</groupId>
  <artifactId>halodb</artifactId>
  <version>x.y.x</version> 
</dependency>

<repository>
  <id>yahoo-bintray</id>
  <name>yahoo-bintray</name>
  <url>https://yahoo.bintray.com/maven</url>
</repository>

Read, Write and Space amplification.

Read amplification in HaloDB is always 1β€”for a read request it needs to do at most one disk lookupβ€”hence it is well suited for read latency critical workloads. HaloDB provides a configuration which can be tuned to control write amplification and space amplification, both of which trade-off with each other; HaloDB has a background compaction thread which removes stale data from the DB. The percentage of stale data at which a file is compacted can be controlled. Increasing this value will increase space amplification but will reduce write amplification. For example if the value is set to 50% then write amplification will be approximately 2

Durability and Crash recovery.

Write Ahead Logs (WAL) are usually used by databases for crash recovery. Since for HaloDB WAL is the database crash recovery is easier and faster.

HaloDB does not flush writes to disk immediately, but, for performance reasons, writes only to the OS page cache. The cache is synced to disk once a configurable size is reached. In the event of a power loss, the data not flushed to disk will be lost. This compromise between performance and durability is a necessary one.

In the event of a power loss and data corruption, HaloDB will scan and discard corrupted records. Since the write thread and compaction thread could be writing to at most two files at a time only those files need to be repaired and hence recovery times are very short.

In the event of a power loss HaloDB offers the following consistency guarantees:

  • Writes are atomic.
  • Inserts and updates are committed to disk in the same order they are received.
  • When inserts/updates and deletes are interleaved total ordering is not guaranteed, but partial ordering is guaranteed for inserts/updates and deletes.

In-memory index.

HaloDB stores all keys and their associated metadata in an index in memory. The size of this index, depending on the number and length of keys, can be quite big. Therefore, storing this in the Java Heap is a non-starter for a performance critical storage engine. HaloDB solves this problem by storing the index in native memory, outside the heap. There are two variants of the index; one with a memory pool and the other without it. Using the memory pool helps to reduce the memory footprint of the index and reduce fragmentation, but requires fixed size keys. A billion 8 byte keys currently takes around 44GB of memory with memory pool and around 64GB without memory pool.

The size of the keys when using a memory pool should be declared in advance, and although this imposes an upper limit on the size of the keys it is still possible to store keys smaller than this declared size.

Without the memory pool, HaloDB needs to allocate native memory for every write request. Therefore, memory fragmentation could be an issue. Using jemalloc is highly recommended as it provides a significant reduction in the cache's memory footprint and fragmentation.

Delete operations.

Delete operation for a key will add a tombstone record to a tombstone file, which is distinct from the data files. This design has the advantage that the tombstone record once written need not be copied again during compaction, but the drawback is that in case of a power loss HaloDB cannot guarantee total ordering when put and delete operations are interleaved (although partial ordering for both is guaranteed).

DB open time

Open db could take a few minutes, depends on number of records and tombstones. If the db open time is critical to your use case, please keep tombstone file size relatively small and increase the number of threads used in building index. See the option setting section in example code above. As best practice, set tombstone file size at 64MB and set build index threads to number of available processors divided by number of dbs being opened simultaneously.

System requirements.

  • HaloDB requires Java 8 to run, but has not yet been tested with newer Java versions.
  • HaloDB has been tested on Linux running on x86 and on MacOS. It may run on other platforms, but this hasn't been verified yet.
  • For performance disable Transparent Huge Pages and swapping (vm.swappiness=0).
  • If a thread is interrupted JVM will close those file channels the thread was operating on. Therefore, don't interrupt threads while they are doing IO operations.

Restrictions.

  • Size of keys is restricted to 128 bytes.
  • HaloDB don't support range scans or ordered access.

Benchmarks.

Benchmarks.

Contributing

Contributions are most welcome. Please refer to the CONTRIBUTING guide

Credits

HaloDB was written by Arjun Mannaly.

License

HaloDB is released under the Apache License, Version 2.0

More Repositories

1

CMAK

CMAK is a tool for managing Apache Kafka clusters
Scala
11,825
star
2

open_nsfw

Not Suitable for Work (NSFW) classification using deep neural network Caffe models.
Python
5,852
star
3

TensorFlowOnSpark

TensorFlowOnSpark brings TensorFlow programs to Apache Spark clusters.
Python
3,873
star
4

serialize-javascript

Serialize JavaScript to a superset of JSON that includes regular expressions and functions.
JavaScript
2,804
star
5

gryffin

Gryffin is a large scale web security scanning platform.
Go
2,075
star
6

fluxible

A pluggable container for universal flux applications.
JavaScript
1,815
star
7

AppDevKit

AppDevKit is an iOS development library that provides developers with useful features to fulfill their everyday iOS app development needs.
Objective-C
1,442
star
8

mysql_perf_analyzer

MySQL performance monitoring and analysis.
Java
1,436
star
9

squidb

SquiDB is a SQLite database library for Android and iOS
Java
1,312
star
10

react-stickynode

A performant and comprehensive React sticky component.
JavaScript
1,266
star
11

CaffeOnSpark

Distributed deep learning on Hadoop and Spark clusters.
Jupyter Notebook
1,266
star
12

blink-diff

A lightweight image comparison tool.
JavaScript
1,191
star
13

egads

A Java package to automatically detect anomalies in large scale time-series data
Java
1,173
star
14

elide

Elide is a Java library that lets you stand up a GraphQL/JSON-API web service with minimal effort.
Java
1,003
star
15

vssh

Go Library to Execute Commands Over SSH at Scale
Go
952
star
16

webseclab

set of web security test cases and a toolkit to construct new ones
Go
915
star
17

kubectl-flame

Kubectl plugin for effortless profiling on kubernetes
Go
784
star
18

streaming-benchmarks

Benchmarks for Low Latency (Streaming) solutions including Apache Storm, Apache Spark, Apache Flink, ...
Jupyter Notebook
630
star
19

redislite

Redis in a python module.
Python
577
star
20

lopq

Training of Locally Optimized Product Quantization (LOPQ) models for approximate nearest neighbor search of high dimensional data in Python and Spark.
Python
563
star
21

hecate

Automagically generate thumbnails, animated GIFs, and summaries from videos
C++
477
star
22

fetchr

Universal data access layer for web applications.
JavaScript
447
star
23

storm-yarn

Storm-yarn enables Storm clusters to be deployed into machines managed by Hadoop YARN.
Java
417
star
24

react-i13n

A performant, scalable and pluggable approach to instrumenting your React application.
JavaScript
382
star
25

FEL

Fast Entity Linker Toolkit for training models to link entities to KnowledgeBase (Wikipedia) in documents and queries.
Java
335
star
26

monitr

A Node.js process monitoring tool.
C++
312
star
27

Oak

A Scalable Concurrent Key-Value Map for Big Data Analytics
Java
267
star
28

TDOAuth

A BSD-licensed single-header-single-source OAuth1 implementation.
Swift
249
star
29

routr

A component that provides router related functionalities for both client and server.
JavaScript
246
star
30

mysql_partition_manager

MySQL Partition Manager
SQLPL
212
star
31

l3dsr

Direct Server Return load balancing across Layer 3 boundaries.
Shell
193
star
32

dnscache

dnscache for Node
JavaScript
184
star
33

object_relation_transformer

Implementation of the Object Relation Transformer for Image Captioning
Python
176
star
34

fili

Easily make RESTful web services for time series reporting with Big Data analytics engines like Druid and SQL Databases.
Java
173
star
35

check-log4j

To determine if a host is vulnerable to log4j CVE‐2021‐44228
Shell
172
star
36

sherlock

Sherlock is an anomaly detection service built on top of Druid
Java
152
star
37

YMTreeMap

High performance Swift treemap layout engine for iOS and macOS.
Swift
134
star
38

maha

A framework for rapid reporting API development; with out of the box support for high cardinality dimension lookups with druid.
Scala
129
star
39

covid-19-data

COVID-19 datasets are constructed entirely from primary (government and public agency) sources
109
star
40

subscribe-ui-event

Subscribe-ui-event provides a cross-browser and performant way to subscribe to browser UI Events.
JavaScript
109
star
41

jafar

🌟!(Just another form application renderer)
JavaScript
109
star
42

panoptes

A Global Scale Network Telemetry Ecosystem
Python
99
star
43

reginabox

Registry In A Box
JavaScript
97
star
44

preceptor

Test runner and aggregator
JavaScript
85
star
45

hive-funnel-udf

Hive UDFs for funnel analysis
Java
85
star
46

graphkit

A lightweight Python module for creating and running ordered graphs of computations.
Python
84
star
47

SparkADMM

Generic Implementation of Consensus ADMM over Spark
Python
83
star
48

react-cartographer

Generic component for displaying Yahoo / Google / Bing maps.
JavaScript
82
star
49

storm-perf-test

A simple storm performance/stress test
Java
76
star
50

UDPing

UDPing measures latency and packet loss across a link.
C++
75
star
51

bgjs

TypeScript
67
star
52

ycb

A multi-dimensional configuration library that builds bundles from resource files describing a variety of values.
JavaScript
66
star
53

ariel

Ariel is an AWS Lambda designed to collect, analyze, and make recommendations about Reserved Instances for EC2.
Python
64
star
54

YMCache

YMCache is a lightweight object caching solution for iOS and Mac OS X that is designed for highly parallel access scenarios.
Objective-C
63
star
55

validatar

Functional testing framework for Big Data pipelines.
Java
58
star
56

imapnio

Java imap nio client that is designed to scale well for thousands of connections per machine and reduce contention when using large number of threads and cpus.
Java
55
star
57

serviceping

A ping like utility for tcp services
Python
52
star
58

proxy-verifier

Proxy Verifier is an HTTP replay tool designed to verify the behavior of HTTP proxies. It builds a verifier-client binary and a verifier-server binary which each read a set of YAML or JSON files that specify the HTTP traffic for the two to exchange.
C++
45
star
59

express-busboy

A simple body-parser like module for express that uses connect-busboy under the hood.
JavaScript
45
star
60

covid-19-api

Yahoo Knowledge COVID-19 API provides JSON-API and GraphQL interfaces to access COVID-19 publicly sourced data
JavaScript
45
star
61

covid-19-dashboard

Source code for the Yahoo Knowledge Graph COVID-19 Dashboard
JavaScript
42
star
62

photo-background-generation

Jupyter Notebook
41
star
63

yql-plus

The YQL+ parser, execution engine, and source SDK.
Java
40
star
64

panoptes-stream

A cloud native distributed streaming network telemetry.
Go
40
star
65

context-parser

A robust HTML5 context parser that parses HTML 5 web pages and reports the execution context of each character.
HTML
40
star
66

FmFM

Python
39
star
67

cocoapods-blocklist

A CocoaPods plugin used to check a project against a list of pods that you do not want included in your build. Security is the primary use, but keeping specific pods that have conflicting licenses is another possible use.
Ruby
39
star
68

ember-gridstack

Ember components to build drag-and-drop multi-column grids powered by gridstack.js
JavaScript
37
star
69

k8s-namespace-guard

K8s - Admission controller for guarding namespace
Go
35
star
70

VerizonVideoPartnerSDK-controls-ios

Public iOS implementation of the OneMobileSDK default custom controls interface... demonstrating how customers can implement their own custom video player controls.
Swift
35
star
71

SubdomainSleuth

Scanner to identify dangling DNS records and subdomain takeovers
Go
34
star
72

fluxible-action-utils

Utility methods to aid in writing actions for fluxible based applications.
JavaScript
34
star
73

parsec

A collection of libraries and utilities to simplify the process of building web service applications.
Java
34
star
74

mod_statuspage

Simple express/connect middleware to provide a status page with following details of the nodejs host.
JavaScript
32
star
75

bftkv

A distributed key-value storage that's tolerant to Byzantine fault.
JavaScript
30
star
76

spivak

Python
30
star
77

protractor-retry

Use protractor features to automatically re-run failed tests with a specific configurable number of attempts.
JavaScript
28
star
78

cubed

Data Mart As A Service
Java
27
star
79

jsx-test

An easy way to test your React Components (`.jsx` files).
JavaScript
27
star
80

ycb-java

YCB Java
Java
27
star
81

fluxible-immutable-utils

A mixin that provides a convenient interface for using Immutable.js inside react components.
JavaScript
25
star
82

maaf

Modality-Agnostic Attention Fusion for visual search with text feedback
Python
25
star
83

node-limits

Simple express/connect middleware to set limit to upload size, set request timeout etc.
JavaScript
24
star
84

GitHub-Security-Alerts-Workflow

Automation to Incorporate GitHub Security Alerts Into your Business Workflow
Python
23
star
85

bandar-log

Monitoring tool to measure flow throughput of data sources and processing components that are part of Data Ingestion and ETL pipelines.
Scala
21
star
86

fumble

Simple error objects in node. Created specifically to be used with https://github.com/yahoo/fetchr and based on https://github.com/hapijs/boom
JavaScript
21
star
87

SongbirdCharts

Allows for other apps to render accessible audio charts
Kotlin
21
star
88

express-csp

Express extension for Content Security Policy
JavaScript
19
star
89

elide-js

Elide is a library that makes it easy to talk to a JSON API compliant backend.
JavaScript
18
star
90

Zake

A python package that works to provide a nice set of testing utilities for the kazoo library.
Python
18
star
91

npm-auto-version

Automatically generate new NPM versions based on Git tags when publishing
JavaScript
18
star
92

httpmi

An HTTP proxy for IPMI commands.
Python
17
star
93

hodman

Selenium object library
JavaScript
17
star
94

elide-spring-boot-example

Spring Boot example using the Elide framework.
Java
17
star
95

cerebro

JavaScript
17
star
96

Override

In app feature flag management
Swift
16
star
97

ychaos

YChaos - The Resilience Framework by Yahoo!
Python
16
star
98

parsec-libraries

Tools to simplify deploying web services with Parsec.
Java
16
star
99

NetCHASM

An Automated health checking and server status verification system.
C++
14
star
100

k8s-ingress-claim

An admission control policy that safeguards against accidental duplicate claiming of Hosts/Domains.
Go
14
star