[입 개발] Scala 의 App Trait는 어떻게 동작하는가?

요새 스칼라 스터디를 하고 있는데…(스칼라 어려워요 흑흑흑, 전 스맹 T.T) 아주 여러가지 기능들이 있습니다. 그런데 첫 부분에 나오는 예제부터 머리속을 땡땡 때리는 경우가 있습니다. 간단한 예를 들자면, tuple의 파라매터가 22개 밖에 안되는 것은 실제로 tuple1 ~ tuple22 까지의 클래스가 있어서 처리된다는 것(tuple 은 다시 product 이라는 것을 상속받는…)

보통 우리가 언어를 처음 배울때 쓰는 첫 예제는… 반가워 세상입니다. 즉 Hello World! 를 출력하는 것이죠.

 object HelloWorld {
    def main(args: Array[String]) {
      println("Hello, world!")
    }
  }

그런데 App 이라는 trait 를 상속받으면 다음과 같은 형태로 똑같이 동작이 됩니다.

object HelloWorld extends App {
  println("Hello, world!")
}

사실 스칼라를 공부하는 사람이야 그냥 당연하게 넘어갈 수 있지만, 두 번째 예의 경우는 println 코드가 있는 부분은 생성자입니다. 그런데 “어떻게 저게 자동으로 실행이 되는거지?” 라는 의문이 생기게 됩니다.(안생기면 500원…), 그리고 args 도 사용할 수 있습니다.

그래서 안을 조금 파보니…

App Trait 는 다시 DelayedInit 라는 Trait를 상속받습니다. 먼저 App Trait 부터 살짝 보도록 하겠습니다.

trait App extends DelayedInit {

  /** The time when the execution of this program started, in milliseconds since 1
    * January 1970 UTC. */
  @deprecatedOverriding("executionStart should not be overridden", "2.11.0")
  val executionStart: Long = currentTime

  /** The command line arguments passed to the application's `main` method.
   */
  @deprecatedOverriding("args should not be overridden", "2.11.0")
  protected def args: Array[String] = _args

  private var _args: Array[String] = _

  private val initCode = new ListBuffer[() => Unit]

  /** The init hook. This saves all initialization code for execution within `main`.
   *  This method is normally never called directly from user code.
   *  Instead it is called as compiler-generated code for those classes and objects
   *  (but not traits) that inherit from the `DelayedInit` trait and that do not
   *  themselves define a `delayedInit` method.
   *  @param body the initialization code to be stored for later execution
   */
  @deprecated("The delayedInit mechanism will disappear.", "2.11.0")
  override def delayedInit(body: => Unit) {
    initCode += (() => body)
  }

    /** The main method.
   *  This stores all arguments so that they can be retrieved with `args`
   *  and then executes all initialization code segments in the order in which
   *  they were passed to `delayedInit`.
   *  @param args the arguments passed to the main method
   */
  @deprecatedOverriding("main should not be overridden", "2.11.0")
  def main(args: Array[String]) = {
    this._args = args
    for (proc <- initCode) proc()
    if (util.Properties.propIsSet("scala.time")) {
      val total = currentTime - executionStart
      Console.println("[total " + total + "ms]")
    }
  }
}

젤 아래의 main을 보면, 아 여기서 실행되겠구나 할것입니다. 쉽네하고 보다보면, 다시 이상해집니다. 분명히 main이 보통 entrypoint 일텐데…(실제로는 object이니 이것을 실행하는 부분이 있긴하겠죠.) 뭔가 initCode 라는 것에서 proc를 가져와서 이걸 실행시킵니다.

그 위의 delayedInit 함수를 보니, body가 넘어와서 initCode에 저장됩니다.(여기서 body는 람다라고 보시면 될듯합니다.)

그럼 다시 처음으로 여기서 main이 실행되는 건 알겠는데… App Trait를 상속받은 object의 생성자를 실행을 시켜주는 걸로 봐서 아마도 위의 proc 가 App Trait를 상속받은 object의 생성자일꺼라는 예상을 할 수 있게 됩니다. 그러나, 여전히 delayedInit을 호출해주는 녀석은 보이지 않습니다. 다시 App Trait 가 DelayedInit Trait를 상속받으니, 이걸 살펴보도록 하겠습니다.

trait DelayedInit {
  def delayedInit(x: => Unit): Unit
}

악!!! 살펴볼 내용이 없습니다. 그냥 인터페이스만 정의가 되어있습니다. 그럼 뭔가 언어적으로 뭔가 해주지 않을까 싶습니다. 소스를 까보면 src/reflect/scala/reflect/internal/Definitions.scala 에서 다음 코드를 발견할 수 있습니다.

def delayedInitMethod = getMemberMethod(DelayedInitClass, nme.delayedInit)

해당 클래스에서 delayedInit를 뽑아내는 것 같습니다.

그리고 src/compiler/scala/tools/nsc/transform/Constructors.scala 를 보면 다음 코드가 있습니다.

    private def delayedInitCall(closure: Tree) = localTyper.typedPos(impl.pos) {
      gen.mkMethodCall(This(clazz), delayedInitMethod, Nil, List(New(closure.symbol.tpe, This(clazz))))
    }

그리고 위의 delayedInitCall은 rewriteDelayedInit() 에서 사용하고 있습니다. delayedInitCall을 실제로
호출하게 됩니다. 즉 여기서 아까 delayedInit가 호출되면서 App Trait 의 initCode 쪽에 생성자를 넣어주는 것입니다. 그래서 실제로 App Trait 의 main에서 그걸 호출하게 되는거죠.

    def rewriteDelayedInit() {
      /* XXX This is not corect: remainingConstrStats.nonEmpty excludes too much,
       * but excluding it includes too much.  The constructor sequence being mimicked
       * needs to be reproduced with total fidelity.
       *
       * See test case files/run/bug4680.scala, the output of which is wrong in many
       * particulars.
       */
      val needsDelayedInit = (isDelayedInitSubclass && remainingConstrStats.nonEmpty)

      if (needsDelayedInit) {
        val delayedHook: DefDef = delayedEndpointDef(remainingConstrStats)
        defBuf += delayedHook
        val hookCallerClass = {
          // transform to make the closure-class' default constructor assign the the outer instance to its pa>
          val drillDown = new ConstructorTransformer(unit)
          drillDown transform delayedInitClosure(delayedHook.symbol.asInstanceOf[MethodSymbol])
        }
        defBuf += hookCallerClass
        remainingConstrStats = delayedInitCall(hookCallerClass) :: Nil
      }
    }

마지막으로 Constructors.scala 안에서 다시 rewriteDelayedInit를 실행합니다. 그래서 App Trait를 상속받을 경우 생성자에만 코드를 넣어두면 실행이 되는 것입니다.

뭐, 이게 맞는 플로우인지는 정확하게 보증은 못합니다. 저도 이제 막 스칼라를 공부하는 중이고, 아무리 봐도, 스칼라를 편안하게 쓰지는 못할듯 하네요 T.T 흑흑흑

[입 개발] mosquitto build

mosquitto를 빌드하려고 하면 다음과 같은 에러가 발생할 수 있다.


In file included from /home/charsyam/mosquitto-1.3.5/lib/logging_mosq.c:34:0:
/home/charsyam/mosquitto-1.3.5/lib/mosquitto_internal.h:51:20: fatal error: ares.h: No such file or directory

이유는 ares.h가 없다는 것인데, DNS Lookup의 SRV랑 연관이 있다는데 이것이 무엇인지는 잘 모른다는 ㅋㅋㅋ

빌드를 손쉽게 하는 방법은 두가지가 있다.

1.  config.mk 에서 WITH_SRV를 찾아서 yes -> no로 바꾼다. 그리고 make

2. ares.h를 채워주면 된다. 우분투라면 apt-get install libc-ares2 libc-ares-dev로 간단하게 설치 가능 그리고 빌드하면 됨.

[입개발] Redis Scan은 어떻게 동작할까? PART #3(결)

PART #1, PART #2를 보면 결국 Redis Scan에서의 Cursor는 bucket 을 검색해야할 다음 index 값이라고 볼 수 있습니다. 그런데 실제로 실행시켜보면, 0, 1, 2 이렇게 증가하지 않고…

그 이유중에 하나는… 실제 Cursor 값이 다음 index의 reverse 값을 취하고 있기 때문입니다. 이걸 보기 전에 먼저 다시 한번 Scan의 핵심 함수인 distScan을 살펴보도록 하겠습니다.(젤 뒤만 보면 됩니다.)

unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       void *privdata)
{
    dictht *t0, *t1;
    const dictEntry *de;
    unsigned long m0, m1;

    if (dictSize(d) == 0) return 0;

    if (!dictIsRehashing(d)) {
        t0 = &(d->ht[0]);
        m0 = t0->sizemask;

        /* Emit entries at cursor */
        de = t0->table[v & m0];
        while (de) {
            fn(privdata, de);
            de = de->next;
        }

    } else {
      ......    
    }

    /* Set unmasked bits so incrementing the reversed cursor
     * operates on the masked bits of the smaller table */
    v |= ~m0;

    /* Increment the reverse cursor */
    v = rev(v);
    v++;
    v = rev(v);

    return v;
}

한 이터레이션이 끝나고 나면 m0 의 bitwise NOT을 or 하고 reverse를 취한 다음 1을 더하고 다시 reverse를 취합니다. 일단 bucket이 4개만 있다고 가정하고, rehashing은 빼고 생각해보도록 합니다. 먼저 여기서 reverse는 비트를 쭈욱 세워놓고, 그걸 거꾸로 뒤집는 것입니다.
그래서 0의 rev(0) 은 그대로 0이고, rev(1)은 8000000000000000(16진수), rev(2)는 4000000000000000(16진수) 가 됩니다.(아 이걸 출력을 64bit 라 64bit hex로 찍어야 하는데 32bit로 찍었다가… 잘못된 이해를 ㅋㅋㅋ)

처음에는 v(cursor) 가 0입니다. scan이 끝나고 (0 |= ~3) = -4, 그 뒤에 rev(-4)는 3fffffffffffffff(16진수) 가 됩니다. 여기에 1을 더하면 4000000000000000 여기서 다시 rev(4000000000000000)가 되면 2가 나오게 됩니다.

/* Function to reverse bits. Algorithm from:
 * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {
    unsigned long s = 8 * sizeof(v); // bit size; must be power of 2
    unsigned long mask = ~0;
    while ((s >>= 1) > 0) {
        mask ^= (mask << s);
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    return v;
}

그런데 왜 reverse를 취하는 것일까요? 이것은 실제 적으로 1씩 증가하는 형태라면… cursor가 언제 끝나는지 알려주기가 애매해서 입니다. 즉 끝났다는 값을 다시 줘야 하는데, 그것보다는 0으로 시작해서 다시 0으로 끝날 수 있도록 reverse 형태를 취하는 것이죠.

PART #1, PART #2, PART #3 의 이유로 해서 SCAN은 다음과 같은 제약 사항을 가집니다.
1. count 값을 줄 수 있지만, 딱 그 개수를 보장하지 않는다.
2. 이미 scan 이 지나간 인덱스에 있는 index 에 나중에 추가된 아이템은 iteration 중에 데이터가 나오지 못한다.(Cursor가 이미 지나갔으므로…)
3. 해당 코드의 설명을 보면… 몇몇 데이터가 중복 될 수 있다는데… 이 부분은 저도 잘 이해가 안가는… 코멘트에 보면… hash table이 확장될때, 줄어들 때, rehashing 할 때 다시 스캔하지 않는다고 되어있는데… 이 부분은 잘 모르겠네요. ㅎㅎㅎ

그럼 Redis Scan 에 대한 부분은 마치도록 하겠습니다.

[입개발] Redis Scan은 어떻게 동작할까? PART #2

지난 Part #1 에서는 기본적인 Redis 의 Scan 동작과 테이블에 대해서 알아보았습니다. 이번에는 Redis Scan의 동작을 더 분석하기 위해서 기본적으로 Redis Hash Table의 Rehash 과 그 상황에서 Scan이 어떻게 동작하는지 알아보도록 하겠습니다.

먼저, Redis Hash Table의 Rehashing에 대해서 알아보도록 하겠습니다. 전 편에서도 간단하게 언급했지만 Redis Hash Table은 보통 Dynamic Bucket 에 충돌은 list 로 처리하는 방식입니다.

redis_hash_1

처음에는 4개의 Bucket으로 진행하면 Hash 값에 bitmask를 씌워서 Hash Table 내의 index를 결정합니다. 그런데, 이대로 계속 데이터가 증가하면, 당연히 충돌이 많고, List가 길어지므로, 탐색 시간이 오래걸리게 되어서 문제가 발생합니다. Redis는 이를 해결하기 위해서 hash table의 사이즈를 2배로 늘리는 정책을 취합니다.

redis_hash_expand

2배로 테이블이 늘어나면서, bitmask는 하나더 사용하도록 됩니다. 이렇게 테이블이 확장되면 Rehash를 하게 됩니다. 그래야만 검색시에 제대로 찾을 수 있기 때문입니다. 먼저 Table을 확장할 때 사용하는 것이 _dictExpandIfNeeded 합수입니다. dictIsRehashing는 이미 Rehash 중인지를 알려주는 함수이므로, Rehashing 중이면 이미 테이블이 확장된 상태이므로 그냥 DICT_OK를 리턴합니다.

먼저 hash table에서 hash table의 사용 정도가 dict_force_resize_ratio 값 보다 높으면 2배로 확장하게 됩니다.

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

실제로 _dictExpandIfNeeded 는 _dictKeyIndex 함수에서 호출하게 됩니다. 이렇게 테이블이 확장되면 Rehash를 해야 합니다. Rehash 라는 것은 테이블의 Bucket 크기가 커졌고 bitmask 가 달라졌으니… mask 0011이 전부 3번째 index였다면 이중에서 111은 7번째로, 011은 3번째로 옮기는 것입니다. 여기서 Redis의 특징이 하나 있습니다. 한꺼번에 모든 테이블을 Rehashing 해야 하면 당연히 시간이 많이 걸립니다. O(n)의 시간이 필요합니다. 그래서 Redis는 rehash flag와 rehashidx라는 변수를 이용해서, hash table에서 하나씩 Rehash하게 됩니다. 즉, 확장된 크기가 8이라면 이전 크기 총 4번의 Rehash 스텝을 통해서 Rehashing이 일어나게 됩니다. (이로 인해서 뒤에서 설명하는 특별한 현상이 생깁니다.)

그리고 현재 rehashing 중인것을 체크하는 함수가 dictIsRehashing 함수입니다. rehashidx 가 -1이 아니면 Rehashing 중인 상태입니다.

#define dictIsRehashing(d) ((d)->rehashidx != -1)

그리고 위의 _dictExpandIfNeeded 에서 호출하는 실제 hash table의 크기를 증가시키는 dictExpand 함수에서 rehashidx를 0으로 설정합니다.

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

위의 함수를 잘 살펴보면 dict 구조체 안의 ht[1] = n으로 할당하는 코드가 있습니다. 이 얘기는 hash table이 두 개라는 것입니다. 먼저 dict 구조체를 살펴보면 다음과 같습니다.

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

실제로, redis의 rehashing 중에는 Hash Table이 두개가 존재합니다. 이것은 앞에 설명했듯이… 한번에 rehash step이 끝나지 않고, 매번 하나의 bucket 별로 rehashing을 하기 때문입니다. 즉 hash table의 확장이 일어나면 다음과 같이 두 개의 hash table 이 생깁니다.

redis_hash_expand_1

그리고 한스텝이 자나갈 때 마다 하나의 Bucket 단위로 해싱이 됩니다. 즉 첫번째 rehash step에서는 다음과 같이 ht[0]에 있던 데이터들이 ht[1]으로 나뉘어서 들어가게 됩니다.

redis_hash_rehash_1

두 번째, 세 번째, 네 번째 rehash 스텝이 끝나면 완료되게 됩니다.

redis_hash_rehash_2

그럼 의문이 생깁니다. Rehashing 중에 추가 되는 데이터는? 또는 삭제나 업데이트는? 추가 되는 데이터는 이 때는 무조건 ht[1]으로 들어가게 됩니다.(또 해싱 안해도 되게…), 두 번째로, 검색이나, 업데이트는, 이 때 ht[0], ht[1]을 모두 탐색하게 됩니다.(어쩔 수 없겠죠?)

dictRehash 함수에서 이 rehash step을 처리하게 됩니다. dictRehash 함수의 파라매터 n은 이 스텝을 몇번이나 할 것인가 이고, 실제로 수행할 hash table의 index는 함수중에서 ht[0]의 table이 NULL인 부분을 스킵하면서 찾게 됩니다. 그리고 ht[0]의 used 값이 0이면 rehash가 모두 끝난것이므로 ht[1]을 ht[0]로 변경하고 rehashidx를 다시 -1로 셋팅하면서 종료하게 됩니다.

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table. */
int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        if (d->ht[0].used == 0) {
            zfree(d->ht[0].table);
            d->ht[0] = d->ht[1];
            _dictReset(&d->ht[1]);
            d->rehashidx = -1;
            return 0;
        }

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    return 1;
}

이제 다시 scan으로 돌아오면… Rehashing 중의 dictScan 함수는 다음과 같습니다.

    } else {
        t0 = &d->ht[0];
        t1 = &d->ht[1];

        /* Make sure t0 is the smaller and t1 is the bigger table */
        if (t0->size > t1->size) {
            t0 = &d->ht[1];
            t1 = &d->ht[0];
        }

        m0 = t0->sizemask;
        m1 = t1->sizemask;

        /* Emit entries at cursor */
        de = t0->table[v & m0];
        while (de) {
            fn(privdata, de);
            de = de->next;
        }

        /* Iterate over indices in larger table that are the expansion
         * of the index pointed to by the cursor in the smaller table */
        do {
            /* Emit entries at cursor */
            de = t1->table[v & m1];
            while (de) {
                fn(privdata, de);
                de = de->next;
            }

            /* Increment bits not covered by the smaller mask */
            v = (((v | m0) + 1) & ~m0) | (v & m0);

            /* Continue while bits covered by mask difference is non-zero */
        } while (v & (m0 ^ m1));
    }

실제로 이미 Rehashing이 된 bucket의 경우는 ht[0] 작은 hash table에는 이미 index의 값이 NULL이므로 실제로 돌지 않지만, 아직 rehash되지 않은 bucket의 경우는 ht[0] 와 ht[1] 의 두 군데, 즉 총 세 군데에 데이터가 존재할 수 있습니다. 그래서 먼저 ht[0]의 bucket을 돌고 나서, ht[1]을 찾게 됩니다. 여기서 당연히 ht[1]에서는 두 군데를 검색해야 하므로 두 번 돌게 됩니다.

v = (((v | m0) + 1) & ~m0) | (v & m0);

즉 위의 식은 만약 v가 0이고 m0 = 3, m1 = 7이라고 하면… (((0 | 3) + 1) & ~3) | (0 & 3) 이 되게 됩니다. ~3은 Bitwise NOT 3이 되므로 -4 가 나오고, (4 & -4) | 0 이므로 결론은 4 & -4 입니다. 3은 00000011, bitwise NOT하면 11111100 이 되므로, 즉 다시 풀면, 00000100 & 11111100 해서 00000100 즉 4가 나오게됩니다. 처음에는 index 0, 두번째는 index 4 가 되는 거죠. 그래서 첫 루프를 돌게 됩니다. 다시 4 & (m0 ^ m1) == 4 이므로 …

이제 두 번째 루프에서 다시 (((4 | 3) + 1) & -4) | (4 & 3) 이므로… 4 | 3 = 7, 4 & 3 = 0 이므로… 다시 한번 정리하면 ((7+1) & -4) | 0 이므로 결론은 8 & -4 = 4 가 되므로 00001000 & 111111100 이 되므로 v 는 이번에는 00001000 즉 8이 됩니다. 즉 한번 돌 때 마다, ht[0]의 size 만큼 증가하게 됩니다.(다들 한방에 이해하실 텐데… 이걸 설명한다고…) 그래서 그 다음번에는 8 & 4 가 되므로 루프가 끝나게 됩니다. 즉, 0, 4 이렇게 ht[1]에서 두 번 읽어야 하니, 두 번 읽는 코드를 만들어둔거죠.

이제 다음편에는 cursor 가 어떻게 만들어지는가에 대해서 간단하게 설명하도록 하겠습니다. (다음편은 짧을듯…)

[입 개발] Redis Scan은 어떻게 동작할까? PART #1

처음부터 꾸준히 입만 놀리는 입개발(or 혀로그래머) CharSyam입니다. Redis의 기능중에 사람들이 쓰면 안되지만, 그 단맛에 끌려 어쩔 수 없이 치게 되는 명령이 KEYS 입니다. KEYS를 쓰는 순간, Redis는 이 명령을 처리하기 위해서 멈춰버립니다. 특히 트래픽이 많은 서버는… 이 KEYS 명령 하나에 많은 장애를 내게 됩니다. 그런데… 어느 순간… Redis에 Scan이라는 명령이 생겼습니다. KEYS의 단점을 없애면서도, 느리지 않은… 그렇다면, Redis에서는 어떻게 Scan 이 동작하게 될까요?

Scan의 내부 동작을 알기 전에… 먼저 Redis가 어떻게 데이터를 저장하는지 부터 다시 한번 집고 넘어가야 합니다. Redis 의 가장 기초적인 자료구조는 KV 즉 Key/Value 형태를 저장하는 것입니다.(String 타입이라고도 합니다.) 이를 위해 Redis는 Bucket을 활용한 Chained Linked List 구조를 사용합니다. 최초에는 4개의 Bucket에서 사용하여… 같은 Bucket에 들어가는 Key는 링크드 리스트 형태로 저장하는 거죠. 즉 다음 그림과 같습니다.

redis_hash_1

이 Chained Linked List에는 다음과 같은 약점이 있습니다. 즉 한 Bucket 안에 데이터가 많아지면 결국 탐색 속도가 느려집니다. 이를 위해서 Redis는 특정 사이즈가 넘을때마다 Bucket을 두 배로 확장하고, Key들을 rehash 하게 됩니다. 먼저 이 때 Key의 Hash로 사용하는 해시함수는 다음과 같습니다. MurmurHash2를 사용합니다.

/* MurmurHash2, by Austin Appleby
 * Note - This code makes a few assumptions about how your machine behaves -
 * 1. We can read a 4-byte value from any address without crashing
 * 2. sizeof(int) == 4
 *
 * And it has a few limitations -
 *
 * 1. It will not work incrementally.
 * 2. It will not produce the same results on little-endian and big-endian
 *    machines.
 */
unsigned int dictGenHashFunction(const void *key, int len) {
    /* 'm' and 'r' are mixing constants generated offline.
     They're not really 'magic', they just happen to work well.  */
    uint32_t seed = dict_hash_function_seed;
    const uint32_t m = 0x5bd1e995;
    const int r = 24;

    /* Initialize the hash to a 'random' value */
    uint32_t h = seed ^ len;

    /* Mix 4 bytes at a time into the hash */
    const unsigned char *data = (const unsigned char *)key;

    while(len >= 4) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    /* Handle the last few bytes of the input array  */
    switch(len) {
    case 3: h ^= data[2] << 16;
    case 2: h ^= data[1] << 8;
    case 1: h ^= data[0]; h *= m;
    };

    /* Do a few final mixes of the hash to ensure the last few
     * bytes are well-incorporated. */
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return (unsigned int)h;
}

그리고 hash 값이 들어가야 할 hash table 내의 index를 결정하는 방법은 다음과 같습니다.

/* Returns the index of a free slot that can be populated with
 * a hash entry for the given 'key'.
 * If the key already exists, -1 is returned.
 *
 * Note that if we are in the process of rehashing the hash table, the
 * index is always returned in the context of the second (new) hash table. */
static int _dictKeyIndex(dict *d, const void *key)
{
    ......
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        ......
    }
    return idx;
}

table에는 Key를 찾기위해 비트 연산을 하기 위한 sizemask가 들어가 있습니다. 초기에는 table의 bucket이 4개 이므로 sizemask는
이진수로 11 즉 3의 값이 셋팅됩니다. 즉 해시된 결과 & 11의 연산결과로 들어가야 하는 Bucket이 결정되게 됩니다.

여기서 Key 가 많아지면 Redis는 Table의 사이즈를 2배로 늘리게 됩니다. 그러면 당연히 sizemask도 커지게 됩니다. Table size가 8이면 sizemask는 7이 됩니다.

먼저 간단하게 말하자면, Scan의 원리는 이 Bucket을 한 턴에 하나씩 순회하는 것입니다. 그래서 아래 그림과 같이 처음에는 Bucket Index 0를 읽고 데이터를 던져주는 것입니다.

redis_scan_0

        t0 = &(d->ht[0]);
        m0 = t0->sizemask;

        /* Emit entries at cursor */
        de = t0->table[v & m0];
        while (de) {
            fn(privdata, de);
            de = de->next;
        }

다음 편에서는 실제 사용되는 cursor 가 어떤 식으로 만들어지는 지, 그 외의 예외 케이스는 어떤 것이 있는지… 그리고 scan 을 사용할 때 주의사항에는 어떤 것이 있는지 알아보도록 하겠습니다.(이거 적고, 안 쓸지도 ㅎㅎㅎ)

2014 year review…

2014년을 돌이켜보면… 역시 가장 먼저 생각나고… 가장 중요한 건… 저희집의 새로운 식구이자, 축복이된 2세의 탄생입니다. 작년에는 뱃속에 생긴것이 최고의 일이었는데… 올해는 태어나고, 내년에는 잘 키우는 가장 큰 숙제이지 않을까 싶네요.

일단 올해의 키워드를 뽑아보자면, 애기를 제외하고… “애아빠의 삶”, “어떻게 애를 쉽게 보나?” 이런것들이 있겠지만… 근엄한 모드로 돌아와서… “오픈소스” 와 “일” 이 아닐까 싶습니다.

먼저 “일” 이라는 키워드를 뽑은 이유는… 올해 초에 “카카오 스토리” 서버 개발자로 보직이 바뀌었는데, 서비스를 다시 하다보니… 재미난 것들이 많습니다. 타이밍이 좋았다고 해야할지… 나쁘다고 해야할지… Ruby -> Java 로 언어 전환을 하는 시기로 들어가서, 실제 전환으로 인한 장단점을 느끼게 되었고, Ruby를 조금 배우게 된것과, 배포 시스템, Rspec을 이용한 리그레이션 테스트 구축이라든지… “Redis”, “Arcus” 등으로, 조금 더 성능 이슈를 만나봤다든지… 장단점을 더 잘 느껴본… 자바 1.7 -> 1.8로의 변환으로 성능 개선(자바는 모르지만…)과, 또 장애도 만나게 되고, 그러면서, 장애 대응이나 발견을 어떻게 해볼 것인가에 대해서도 고민을 해볼 수 있는 시간이었네요. 뭐, 다 제가 한것도 아니고, 팀 분들이 하신걸 그냥 주워 듣거나, 옆에서 하는 걸 끼어서 도와주기만 했지만… 나름 많이 공부한 한해이네요. 역시, 회사를 다녀야 배우는게 늘어나는듯 합니다.

지금 있는 곳이, 여러가지를 해볼 수 있는 환경과 지원이 있는 회사라, 2015년에는 지금까지 했던 것들 위주로, 하나씩 개선시켜 본다거나 하는걸 해봐야 하지않을까 싶습니다.(잉여가 남는다면…)

두번째는 “오픈 소스”입니다. 이것저것 많이 건드리는 오픈소스계의 하이에나로서, 이것 저것 많이 건드린것 같지만… 연말에 집중하게 된건 “twemproxy”, “tajo” 두 가지 입니다. 뭐, 꼭 그러려고 하는 건 아니지만, 주로 관심을 두는게 Data Storage Layer쪽이라… 아마 내년에는 지금 보고 있는 것들에 postgresql를 좀 보지 않을까 싶습니다.(mysql 에 비해서는 확실히 코드가 깔끔한 ㅋㅋㅋ) 뭐, 일단 말은 이렇게 하지만… 워낙 그때 그때 바뀌어서, 딴걸 볼지도…

다시 개인적으로 돌아가자면, “건강”과 “영어”를 다시 뽑아봅니다. 애도 생겼으니… 건강에 신경을 써야 하는데, 제가 워낙 몸이 불량품인지라… 운동을 해서 건강을 좀 찾아야 할듯 합니다. 흑흑흑 일찍 일어나서 운동을… T.T

그리고 영어는… 올해 짧게 외국인과 얘기할 기회가 있었는데… 뭐라고 하는지 한마디도 못알아듣겠더라는… 흑흑흑, 뭔가 제대로 읽고 이해하고, 떠듬 떠듬 질문하고 이해할 수 있는 영어실력이 되면 좋겠네요.

흑흑흑, 리뷰라기 보다는… 그냥 올 한해를 보고, 내년 한해의 희망을 적었습니다. 흑흑흑… 잘 되기를…

[입 개발] Java.net.InetAddress 의 getLocalHost() 버그…

모 오픈소스를 실행시키다가 이상한 일이 생겨서, 버그인가 하고 보다가… 재미난 현상을 발견했습니다. Java.net.InetAddress 가 뭔가 이상한 결과를 넘겨주는 것입니다. 먼저… 간단한 소스를 보시죠. 테스트 프로그램은 다음과 같습니다.(결론부터 말하자면… 자바의 버그라고 할 수는 없습니다. ㅋㅋㅋ, DNS 변경으로 일단 원하는 결과가 나오는 ㅎㅎㅎ)

* 결론적으로는 U+등이 디지털 네임스랑 계약을 맺고, 분석이 되지 않는 도메인을 디지털네임스로 질의하고, 이를 디지털 네임스에서 키워드로 등록되었거나, 등록되지 않은 주소를 자신의 ip등으로 돌려줘서 발생하는 이슈로 추측되고 있습니다.)

import java.io.*;
import java.util.*;
import java.net.InetAddress;
import java.net.UnknownHostException;

public class Test {
  public static void main(String [] args) {
    try {
      System.out.println(InetAddress.getLocalHost());
    } catch(UnknownHostException var1) {
      System.out.println(&quot;Exception : &quot; + var1);
    }
  }
}

그런데 그 결과가 다음과 같습니다. -_-

charsyam ~/works/test $ java Test
charsyam.local/218.38.137.28
charsyam ~/works/test $ java Test
charsyam.local/218.38.137.28
charsyam ~/works/test $ java Test
charsyam.local/192.168.1.7
charsyam ~/works/test $ java Test
charsyam.local/192.168.1.7

네, getLocalHost()를 호출한 결과가 218.38.137.28 이거나 192.168.1.7이 나옵니다. 실제 저희 집의 네트웍은 공유기 밑에 접속이 되는 것이라, 192.168.1.7이 기대한 값입니다. 혹시나 외부 아이피인가 해서 확인해도 제 공유기가 가진 아이피도, 위의 218.38.137.28 값은 아니었습니다. 전혀 상관 없는 값이죠.

그런데 재미있는 것은 이 것은 단순히 자바의 문제는 아니라는 것입니다.
dig/nslookup 으로 해본 결과입니다.

nslookup 결과

charsyam ~ $ nslookup Macintosh-7.local
Server:		192.168.1.1
Address:	192.168.1.1#53

Name:	Macintosh-7.local
Address: 218.38.137.28

dig 결과

charsyam ~ $ dig Macintosh-7.local

; &lt;&lt;&gt;&gt; DiG 9.8.3-P1 &lt;&lt;&gt;&gt; Macintosh-7.local
;; global options: +cmd
;; Got answer:
;; -&gt;&gt;HEADER&lt;&lt;- opcode: QUERY, status: NOERROR, id: 40380
;; flags: qr aa rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0

;; QUESTION SECTION:
;Macintosh-7.local.		IN	A

;; ANSWER SECTION:
Macintosh-7.local.	3600	IN	A	218.38.137.28

;; Query time: 5 msec
;; SERVER: 192.168.1.1#53(192.168.1.1)
;; WHEN: Sun Dec 28 23:44:09 2014
;; MSG SIZE  rcvd: 51

네 DNS 결과가 이상합니다. 흑흑흑, 일단 네임서버가 뭔가 이상한 결과를 던져주는 건 일단 확실한데… 제가 보기엔 여기에 설정된 네임서버가 이상하고, 여기서 질의도 이상한데, 거기에 대해서 이상한 결과를 주는 듯 합니다.

그럼 왜 위의 getLocalHost()의 결과가 저럴까요? 이름만 보면 localhost를 줘야 할 것 같은데… 그게 아닙니다.
이제 Java 소스를 까보도록 하겠습니다. 저부분만…

코드를 해석하면 처음에 LocalHostName을 가져옵니다. 저의 경우는 Macintosh-7.local 이겠죠.
그리고 위의 값이 localhost면 그냥 루프백 주소를 줍니다. 즉 이러면 127.0.0.1 이나 정상적인 값이 갈듯 합니다.
그리고 그 호스트네임을 이용해서 InetAddress.getAddressesFromNameService 을 이용해서 InetAddress를 가져오는데, 여기서 뭔가 해당 도메인 파싱이 잘못되고, 도메인 네임서버로 가서 이상한 결과가 오는게 아닌가 싶습니다.

    public static InetAddress getLocalHost() throws UnknownHostException {

        SecurityManager security = System.getSecurityManager();
        try {
            String local = impl.getLocalHostName();

            if (security != null) {
                security.checkConnect(local, -1);
            }

            if (local.equals(&quot;localhost&quot;)) {
                return impl.loopbackAddress();
            }

            InetAddress ret = null;
            synchronized (cacheLock) {
                long now = System.currentTimeMillis();
                if (cachedLocalHost != null) {
                    if ((now - cacheTime) &lt; maxCacheTime) // Less than 5s old?
                        ret = cachedLocalHost;
                    else
                        cachedLocalHost = null;
                }

                // we are calling getAddressesFromNameService directly
                // to avoid getting localHost from cache
                if (ret == null) {
                    InetAddress[] localAddrs;
                    try {
                        localAddrs =
                            InetAddress.getAddressesFromNameService(local, null);
                    } catch (UnknownHostException uhe) {
                        // Rethrow with a more informative error message.
                        UnknownHostException uhe2 =
                            new UnknownHostException(local + &quot;: &quot; +
                                                     uhe.getMessage());
                        uhe2.initCause(uhe);
                        throw uhe2;
                    }
                    cachedLocalHost = localAddrs[0];
                    cacheTime = now;
                    ret = localAddrs[0];
                }
            }
            return ret;
        } catch (java.lang.SecurityException e) {
            return impl.loopbackAddress();
        }
    }

참고로 getAddressesFromNameService 는 다음과 같이 DNS 프로바인더를 이용해서 실제 DNS쿼리를 하게 됩니다.

    private static InetAddress[] getAddressesFromNameService(String host, InetAddress reqAddr)
        throws UnknownHostException
    {
        InetAddress[] addresses = null;
        boolean success = false;
        UnknownHostException ex = null;

        // Check whether the host is in the lookupTable.
        // 1) If the host isn't in the lookupTable when
        //    checkLookupTable() is called, checkLookupTable()
        //    would add the host in the lookupTable and
        //    return null. So we will do the lookup.
        // 2) If the host is in the lookupTable when
        //    checkLookupTable() is called, the current thread
        //    would be blocked until the host is removed
        //    from the lookupTable. Then this thread
        //    should try to look up the addressCache.
        //     i) if it found the addresses in the
        //        addressCache, checkLookupTable()  would
        //        return the addresses.
        //     ii) if it didn't find the addresses in the
        //         addressCache for any reason,
        //         it should add the host in the
        //         lookupTable and return null so the
        //         following code would do  a lookup itself.
        if ((addresses = checkLookupTable(host)) == null) {
            try {
                // This is the first thread which looks up the addresses
                // this host or the cache entry for this host has been
                // expired so this thread should do the lookup.
                for (NameService nameService : nameServices) {
                    try {
                        /*
                         * Do not put the call to lookup() inside the
                         * constructor.  if you do you will still be
                         * allocating space when the lookup fails.
                         */

                        addresses = nameService.lookupAllHostAddr(host);
                        success = true;
                        break;
                    } catch (UnknownHostException uhe) {
                        if (host.equalsIgnoreCase(&quot;localhost&quot;)) {
                            InetAddress[] local = new InetAddress[] { impl.loopbackAddress() };
                            addresses = local;
                            success = true;
                            break;
                        }
                        else {
                            addresses = unknown_array;
                            success = false;
                            ex = uhe;
                        }
                    }
                }

                // More to do?
                if (reqAddr != null &amp;&amp; addresses.length &gt; 1 &amp;&amp; !addresses[0].equals(reqAddr)) {
                    // Find it?
                    int i = 1;
                    for (; i &lt; addresses.length; i++) {
                        if (addresses[i].equals(reqAddr)) {
                            break;
                        }
                    }
                    // Rotate
                    if (i &lt; addresses.length) {
                        InetAddress tmp, tmp2 = reqAddr;
                        for (int j = 0; j &lt; i; j++) {
                            tmp = addresses[j];
                            addresses[j] = tmp2;
                            tmp2 = tmp;
                        }
                        addresses[i] = tmp2;
                    }
                }
                // Cache the address.
                cacheAddresses(host, addresses, success);

                if (!success &amp;&amp; ex != null)
                    throw ex;

            } finally {
                // Delete host from the lookupTable and notify
                // all threads waiting on the lookupTable monitor.
                updateLookupTable(host);
            }
        }

        return addresses;
    }