VoltDB and its related links

There has been lots of buzz about VoltDB (academic name is H-Store [5]) since a week ago. VoltDB is lead by M. Stonebraker, and it is an open source OLTP DBMS. There are some interesting points:

  • Running on shared-nothing clusters of commodity hardware
  • In-memory database
  • SQL support
  • ACID
  • Linear Scalability
  • Released as an Open Source software

Actually, there have already been some OLTP databases running on shared-nothing clusters. However, they cannot take advantage from the scalability of shared-nothing architecture due to their implementation’s natures, such as complex distributed locking and commit protocols [1]. In addition, according to [3], traditional RDBMSs have four overhead components, which are logging, locking, latching, and buffer management. However, M. Stonebraker claims that VoltDB eliminated these legacy overheads.

Among many features, especially I have interest in its linear scalability with ACID and performance. It is meaningful in that today’s web applications have another alternative to NoSQL data stores. Although VoltDB is under heavy development, the above features and the next benchmark result show its promising.

Cassandra is a remarkable key-value store and an open source project developed by apache committers. Now, it is well known as the most performant one in existing NoSQL stores. According to this benchmark result, however, in all cases VoltDB dominates Cassandra although the fairness of experiments is controversial.

It’s future plan is also expected. I wonder how much attention VoltDB will be getting from communities and industrials.

See Also:

  1. Data Management in the Cloud: Limitations and Opportunities
  2. Comparing VoltDB vs Postgresql
  3. OLTP through the looking glass, and what we found there, ACM SIGMOD 2008
  4. http://voltdb.com/product
  5. H-Store: A Next Generation OLTP DBMS

HDFS Scalability 향상을 위한 시도들 (1)


얼마전 Yahoo!의 HDFS 팀에서 Multiple nodes를 사용하여 HDFS namenode의 Horizontal Scalability를 향상 시키는 방법을 제안 했었습니다 (HDFS-1052). 그런데 그 뒤로는 Dhruba Borthakur라는 Hadoop 커미터가 Vertical Scalability 개선 방법을 제안했습니다(The Curse of Singletons! The Vertical Scalability of Hadoop NameNode, HDFS-1093, HADOOP-6713). Borthakur에 대해 LinkedIn 에서 찾아보니 현재 Facebook에서 근무하는 Hadoop 엔지니어라고 나오는군요.

위 두 제안을 보면 Vertical Scalability과 Horizontal Scalability라는 용어가 나옵니다. Vertical Scalability는 시스템의 사양을 향상 시켰을 때 얻는 확장성을 의미합니다. 주로 CPU, Memory, Hard disk 등의 향상을 의미합니다. Hadoop과 같은 분산 시스템에서는 시스템 코어의 수가 늘어나는 것도 Vertical Scalability의 범주로 포함됩니다. 반면 Horizontal Scalability는 시스템의 개수를 늘렸을 때 얻는 확장성을 의미합니다. 예를 들면 노드의 수가 10대에서 20개로 늘어났을 때 얻는 확장성을 의미합니다. scale-up과 scale-out도 각각 같은 의미로 통용됩니다.

본 포스트에서는 위 두 가지 제안 중에서 Dhruba Borthaku가 제안한 vertical scalability 향상을 위한 제안을 소개합니다. 우선 Dhruba Borthakur라는 해커가 지적한 Hadoop Namenode (현재 Hadoop 0.21)의 병목현상은 다음과 같습니다.

  • Network: Facebook에서 자신이 사용하는 클러스터는 약 2000개의 노드로 구성되어 있으며 MapReduce 프로그램 동작 시 각 서버들은 9개의 mapper와 6개의 reducer가 동작하도록 설정되어 있다고 합니다. 이 구성의 클러스터에서 MapReduce를 동작하면 클라이언트들은 동시에 약 30k 의 request를 NameNode 에게 요청한다고 합니다. 그러나 singleton으로 구현된 Hadoop RPCServer의 Listener 스레드가 모든 메시지를 처리하므로 상당히 많은 지연이 발생하고 CPU core의 수가 증가해도 효과가 없었다고 합니다.
  • CPU: FSNamesystem lock 메카니즘으로 인해 namenode는 실제로는 8개의 core를 가진 시스템이지만 보통 2개의 코어밖에 활용되지 않는다고 합니다. Borthakur에 의하면 FSNamesystem에서 사용하는 locking 메커니즘이 너무 단순 하고 HADOOP-1269 를 통해 문제를 개선 시켰음에도 여전히 개선의 여지가 있다고 합니다.
  • Memory: Hadoop의 NameNode는 논문 내용에 충실하게 모든 메타 데이터를 메모리에 유지합니다. 그런데 Borthakur가 사용하는 클러스터의 HDFS에는 6천만개의 파일과 8천만개의 블럭들이 유지하고 있는데 이 파일들의 메타데이터를 유지하기 위해 무려 58GB의 힙공간이 필요했다고 합니다.

Borthakur가 이 문제를 해결하기 위해 제안했던 방법은 다음과 같습니다.

  • RPC Server: singleton으로 구현되었던 Listener 스레드에 Reader 스레프 풀을 붙였다고 합니다. 그래서 Listener 스레드는 connection 요청에 대한 accept 만 해주고 Reader 스레드 중 하나가 RPC를 직접 처리하도록 개선했다고 합니다. 결과적으로 다량의 RPC 요청에 대해 더 많은 CPU core들을 활용할 수 있게 되었다고 합니다(HADOOP-6713).
  • FSNamesystem lock: Borthakur는 파일에 대한 어떤 operation이 있을 때 lock이 걸리는지 통계를 내고 그 결과로 파일과 디렉토리의 상태를 얻을 때와 읽기 위해 파일을 열 때 걸리는 lock이 전체 lock의 90%를 차지 한다는 것을 밝힙니다. 그리고 저 두 파일 operation들은 오직 read-only operation 이기 때문에 read-write lock 으로 바꾸어 성능을 향상 시켰다고 합니다(HADOOP-1093). 이 부분은 MapReduce 논문(The Google File System) 4.1절 Namespace Management and Locking 에도 설명이 잘 되어 있습니다. 이미 MapReduce에서는 namespace의 자료구조에서 상위 디렉토리에 해당하는 데이터에는 read lock을 걸고 작업 디렉토리 또는 작업 파일에는 read 또는 write lock을 걸어 가능한 동시에 다수의 operation들이 공유 데이터에 접근하게 하면서도 consistency를 유지하는 방법을 설명하고 있습니다. 아마도 file 에 대한 append가 Hadoop 0.20 버전에 추가 된 것 처럼 논문에 설명이 있음에도 구현이 되지 않은 부분이었나 봅니다. 자세한건 소스를 분석해 봐야 알 수 있을 것 같습니다.

그러나 메모리에 대한 문제는 아직 해결하지 못했다고 합니다. 그래도 Borthakur에 의하면 위 두 가지 문제점을 해결한 것만으로 무려 8배나 scalability를 향상 시켰다고 합니다.

얼마전 부터 HDFS scalability 향상에 대한 시도들이 눈에 띄고 재미있어 보여 ‘여유 있을 때 블로그에 한번 정리해 봐야 겠다’라고 한달전에 맘 먹었는데 겨우 하나를 마쳤네요. 요즘 시간이 잘 안나서 이 포스트를 시작해서 완성하는데 약 3주나 걸렸습니다. 그 사이 Usenix의 매거진인 ;login:에 Hadoop Namenode의 scalability에 대한 article인 HDFS Scalability: The Limits to Growth가 실렸습니다. 또 야후 개발자 네트워크 블로그에서 article을 소개하는 글 (Scalability of the Hadoop Distributed File System)이 실렸네요. 시간날 때 마다 마저 정리해 보겠습니다.


A Brief Summary of Independent Set in Graph Theory

Graph Basics

Let G be a undirected graph. G=(V,E), where V is a set of vertices and E is a set of edges.  Every edge e in E consists of two vertices in V of G. It is said to connect, join, or link the two vertices (or end points).

Independent Set

An independent set S is a subset of V in G such that no two vertices in S are adjacent. I suppose that its name is meaning that vertices in an independent set S is independent on a set of edges in a graph G. Like other vertex sets in graph theory, independent set has maximal and maximum sets as follows:

The independent set S is maximal if S is not a proper subset of any independent set of G.

The independent set S is maximum if there is no other independent set has more vertices than S.

That is, a largest maximal independent set is called a maximum independent set. The maximum independent set problem is an NP-hard optimization problem.

All graphs has independent sets. For a graph G having a maximum independent set, the independence number α(G) is determined by the cardinality of a maximum independent set.

Relations to Dominating Sets

  • A dominating set in a graph G is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge.
  • In other words, a vertex set D is a dominating set in G if and if only every vertex in a graph G is contained in (or is adjacent to) a vertex in D.
  • Every maximal independent set S of vertices in a simple graph G has the property that every vertex of the graph either is contained in S or is adjacent to a vertex in S.
    • That is, an independent set is a dominating set if and if only it is a maximal independent set.

Relations to Graph Coloring

  • Independent set problem is related to coloring problem since vertices in an independent set can have the same color.

References


Hadoop RPC를 이용한 서버/클라이언트 구현

Apache Hadoop

Hadoop은 이미 알려질대로 잘 알려진 분산 컴퓨팅 프레임워크입니다. 많은 사람들이 Hadoop 하면 MapReduce 프로그래밍을 주로 떠올리지만 자체적으로 제공하는 Hadoop RPC와 분산 파일 시스템인 HDFS를 가지고도 재미있는 것을 시도해 볼 수 있을 것 같습니다. 본 포스팅에서는 그 중에서 Hadoop RPC를 이용한 간단한 서버 클라이언트 프로그램의 구현방법을 소개합니다.

Hadoop RPC Concept

Hadoop RPC는 일반적으로 하나의 프로토콜 인터페이스(interface)와 하나의 Server 그리고 하나 이상의 Client(들)로 동작합니다. Hadoop RPC 서버의 인스턴스와 클라이언트 프록시의 인스턴스는 org.apache.hadoop.ipc.RPC 라는 클래스를 통해 얻을 수 있는데 내부적으로는 java reflection을 통해 구현되어 있습니다. 그리고 RPC method의 파라메터와 리턴 값은 오직 자바 primitive type들(예: int, long, String 등등)과 Writable 인터페이스를 구현한 구상클래스만 될 수 있습니다. 또한 Hadoop RPC는 자체적으로 서버와 클라이언트에 대한 기본적인 기능을 제공합니다. 따라서 복잡하게 스레드나 소켓 통신을 직접 구현할 필요가 없으며 개발자는 오로지 RPC 프로토콜 인터페이스와 RPC 메소드들에 대한 내용만 채워 넣으면 됩니다.

Implementation of RPC Protocol

RPC Protocol은 인터페이스로 정의되어야 하며 이 인터페이스는 org.apache.hadoop.ipc.VersionedProtocol을 상속하여야 합니다. VersionedProtocol은 자체적으로 getProtocolVersion() 메소드를 가지고 있는데 이 메소드는 프로토콜의 버전이 다양할 경우 서버-클라이언트가 다른 버전의 프로토콜로 통신하는 것을 방지하는 역할을 합니다.

RPC 프로토콜은 다음 예제와 같이 간단히 만들 수 있습니다. 아래 예제는 String 값을 반환하는 heartBeat()라는 하나의 RPC 메소드를 가진 RPC 프로토콜 인터페이스입니다.

import org.apache.hadoop.ipc.VersionedProtocol;

public interface RPCProtocol extends VersionedProtocol {
  public long versionID=0;
  public String heartBeat() throws IOException;
}

Implementation of RPC Server

위에서 설명한 RPC 프로토콜의 서버 역할을 할 구상 클래스를 구현합니다. 서버 클래스는 간단히 위에서 정의한 RPCProtocol 인터페이스를 implements 하면 됩니다 (아래 예제 참조).

import java.io.IOException;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.ipc.RPC;
import org.apache.hadoop.ipc.RPC.Server;

public class TestServer implements RPCProtocol {

  @Override
  public String heartBeat() throws IOException {
    return "Hello";
  }

  @Override
  public long getProtocolVersion(String arg0, long arg1) throws IOException {
    return 0;
  }

  /**
   * @param args
   * @throws IOException
   * @throws InterruptedException
   */
  public static void main(String[] args) throws IOException, InterruptedException {
    TestServer s = new TestServer();
    Configuration conf = new Configuration();
    Server server = RPC.getServer(s, "localhost", 10000, conf);
    server.start();
    server.join();
  }
}

RPCProtocol 인터페이스에서 정의했던 String heartBeat() 메소드 역시 구현되어 있습니다. 반환 값으로 “Hello”가 호출한 RPC 클라이언트에게 전달 될 것입니다.

서버의 시동은 main 메소드에 구현되어 있습니다. 우선 프로토콜의 구상클래스(TestServer)의 인스턴스를 생성하고 RPC.getServer()에 인자로 전달합니다. 또한 getServer 메소드는 추가적으로 서버가 binding할 IP와 port 번호를 인자로 받으며 Server 클래스의 인스턴스를 반환합니다(내부적으로는 TestServer 클래스의 인스턴스에 대한 Listener 스레드를 생성하여 파라메터로 전달된 IP 및 port 번호와 바인딩 시킵니다. 그리고 RPC 콜이 있을 때마다 TestServer의 메소드를 콜하게 됩니다. 처리 결과는 Responder 스레드를 통해 반환하게 됩니다).

RPC.getServer 메소드의 원형은 다음과 같습니다.

static RPC.Server getServer(Object instance, String bindAddress, int port, Configuration conf)

Implementation of RPC Client

클라이언트는 RPC.waitForProxy 메소드를 통해서 간단히 얻을 수 있습니다. 그리고 클라이언트는 반환값으로 받은 proxy 인스턴스를 이용해서 손쉽게 RPC method를 콜하고 서버로부터 응답을 받아 올 수 있습니다.

static VersionedProtocol getProxy(Class<?> protocol, long clientVersion, InetSocketAddress addr, UserGroupInformation ticket,Configuration conf, SocketFactory factory)
import java.io.IOException;
import java.net.InetSocketAddress;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.ipc.RPC;

public class TestClient {

  /**
   * @param args
   * @throws IOException
   * @throws InterruptedException
   */
  public static void main(String[] args) throws IOException, InterruptedException {
    Configuration conf = new Configuration();
    InetSocketAddress addr = new InetSocketAddress(&quot;localhost&quot;, 10000);
    RPCProtocol rpc = (RPCProtocol) RPC.waitForProxy(RPCProtocol.class,
        RPCProtocol.versionID, addr, conf);

    String msg = null;
    while(true) {
      Thread.sleep(1000);
      msg = rpc.heartBeat();
      System.out.println(msg);
    }
  }
}

위 예제는 프록시 인스턴스 변수인 rpc를 통해 손쉽게 rpc.heartBeat() 메소드를 실행하고 서버로 부터 결과를 얻는 내용을 설명합니다.

Test

서버를 먼저 실행하고 클라이언트를 실행하면 됩니다. 사실 순서를 바꿔 실행해도 크게 문제 되지 않습니다. Hadoop RPC의 클라이언트는 먼저 실행되었을 경우 RPC 서버에 접속이 될 때까지 1초 단위로 반복하여 접속 시도를 하게 됩니다.

정상적으로 수행되는 경우 다음과 같은 메시지를 확인할 수 있습니다.

Hello
Hello
Hello
Hello
Hello
...

References


Postgresql로 한글 full text search 시도기

최근 일이 있어 Postgresql을 이용한 full text search (FTS) 를 시도해보았다. Postgresql 자체가 역사가 긴 녀석이라 그런지 full text 검색 다양한 방법들을 제공했다. pgtrgmtsearch2 와 같은 메소드를 제공하고 GIN (Generalized Inverted Index) 나 GiST (Generalized Search Tree) 와 같은 색인들을 제공한다. 일반적으로 100만건 이내에서는 만족할 성능을 보여준다고 말하여진다.

그런데 제목이 ‘시도기’로 그치는 것에는 이유가 있다. 설명을 위해 우선 FTS 대해 조금 설명하면 FTS는 단순하게 SQL의 LIKE와 같이 서브 스트링을 포함하는 ROW를 찾아주는 문제가 아니다. 문서에서 조사와 같은 불용어를 제외하고 단어의 형태소 추출하며 단어간의 edit distance 까지 고려하여 철자가 유사한 단어에 대해서도 검색 결과로 내놓는다. 따라서 불용어와 형태소분석을 위해서는 사전이 필수적인 것이다. Postgresql 메뉴얼을 보니 ispell, myspell, hunspell등의 포맷을 지원한다고 써 있었다.

사전을 찾아보니 데비안 메인테이너 cwryu님이 주도하시는 hunspell-ko 프로젝트가 있었다. 안도… 그러나기쁨도 잠시 postgresql 이 사전을 제대로 읽어 들이지 못한다. IRC에서 cwryu님께 받은 조언으로 문제를 해결했지만 postgresql이 사전이 ASCII로 설정된 옵션(FLAG default) 외에는 받아들이지 않는다. 한글처리를 위해서는 default로는 불가했다.

현재 이 문제에 대해서는 postgresql bug 메일링에 리포트 해 놓은 상태이다. 결론은 postgresql로 제대로 된 full text search는 아직 꿈나라 인듯 싶다. tgtrgm 으로 짧은 문장에 대해서는 가능하기도 하지만 띄어쓰지 않은 5자 정도 이상의 문자들에 대해서는 false negative가 발생한다. false positive 는 성능 상 오버헤드가 있더라고 필터를 한번 더 주면 되지만 이것은 곤란했다.

시간이 좀 걸리더라도 짬을내어 이 문제에 대해 계속 리포트할 심산이다. 중간 중간 진행상황에 대해 포스팅 하도록 하겠다.


Data-Intensive Text Processing with MapReduce Draft Available in Online

Data-Intensive Text Processing with MapReduce, Jimmy Lin and Chris Dyer

Actually, there have never been books that directly deal with MapReduce programming and algorithms. This book addresses from MapReduce algorithm design to EM Algorithms for Text Processing. Although this book is still draft, it seems well-organized and very interesting. In addition, the book contains some basic graph algorithms using MapReduce.


애플 타플릿 IPad 발표 됐군요.

나오기 전부터 시끄럽더니 단순한 언론 플레이는 아니었던 것 같습니다. 아래 두 링크는 발표와 제품 사진, 그리고 동영상입니다. 가격이 $499 부터 시작한다는게 조금 부담이네요.

제가 흥미로웠던 건 발표 시점에 이미 SDK, 프로그래밍 가이드라인, 휴먼 인터페이스 가이드 라인까지 준비가 되어 있었고 곧 바로 홈페이지에 소개가 됐다는 사실입니다. 언플을 밥먹듯 하는 국내 일부 기업들은 좀 배워야 하지 않나 싶습니다.


Follow

Get every new post delivered to your Inbox.

Join 873 other followers