gomathi

package voldemort.hashtrees;

import java.util.BitSet;
import java.util.concurrent.atomic.AtomicIntegerArray;

import voldemort.annotations.concurrency.Threadsafe;

/**
 * Default {@link BitSet} provided in java is not thread safe. This class
 * provides a minimalistic thread safe version of BitSet.

gomathi

This document describes the Merkle tree(Hash tree) design for voldemort.

Merkle tree is a data structure using which two nodes can synch up quickly by exchanging little information. For more information, refer, dynamo paper [1]. As a fun project, I am working on implementing merkle tree for voldemort. I would like to get the review from other voldemort developers.

Quick summary of Hash-Tree structure:

Each node will maintain a binary tree structure(disk based). Number of leaf nodes are fixed. It is configurable. Each leaf node corresponds to a segment. When a (key,value) comes to voldemort, (key,digest(value)) will be added to one of the segment. Keys are distributed among the segment based on hash function. 

For example, a segment looks like as following

gomathi

package test;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

gomathi

package com.yahoo.mail.force.asyncf.consumer;

import java.net.InetSocketAddress;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentSkipListMap;

gomathi

  546  git pull --rebase origin dev
  547  git log
  548  git rebase -i f3785c732bf93ad1ede6fa7ffd6981fe79b5a2c4
  549  git rebase -i f3785c732bf93ad1ede6fa7ffd6981fe79b5a2c4
  550  git log
  551  git push -f origin limit-wf-results

gomathi

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <random>


using namespace std;