일단 써보기

RAM vs Disk

DRAM과 DISK모두 저장장치의 역할을 하지만 각각이 가지고 있는 특징이 다르기 때문에 서로 다른 용도로 사용이 됩니다.

DRAM의 경우 속도가 뛰어나지만 가격이 높고, 휘발성이 있어 데이터가 영구적으로 저장되지 못한다는 특징이 있습니다. 또 바이트 단위로 데이터에 접근합니다. 때문에 CPU가까이(데이터의 이동이 잦은곳)에서 프로세서가 필요로 하는 데이터를 저장한 후 공급하는 주기억장치의 역할을 합니다.

반면 DISK의 경우 DRAM에 비해 현저하게 느린 데이터 전송속도를 가지지만, 휘발성이 없고 섹터단위로 데이터에 접근합니다. 때문에 데이터를 저장하는 보조기억장치 역할을 합니다.

RAM Disk

RAM을 주 기억 장치가 아니라 보조 기억 장치로 사용하는 개념입니다. 메모리를 기반으로 한 파일시스템이기 때문에 SSD, HDD에 비해 속도면에서 아주 우수하며 caching또는 작업 디렉토리 용도로 사용될수 있습니다. 제 개인적인 경험으로는 DRAM의 휘발성을 생각하고 RAM disk를 윈도우 인터넷 익스플로러의 임시파일 경로로 활용했던 경험이 있습니다.

Create RAM disk

Verify Memory Size

$ free -h
              total        used        free      shared  buff/cache   available
Mem:          6.1Gi       384Mi       5.6Gi       0.0Ki       189Mi       5.5Gi
Swap:         2.0Gi          0B       2.0Gi

제경우 5.6Gi정도의 여유 메모리가 있어 이를 고려하여 램디스크로 사용할 크기를 결정 하였습니다.

ramdisk 설정

먼저 램디스크를 만들 디렉토리를 생성합니다.

$ mkdir /workspace/ramdisk

아래 명령어를 통해 램 디스크를 마운트 합니다.(저는 1G만큼 할당하였습니다.)

$ sudo mount -t tmpfs -o size=1G tmpfs /workspace/ramdisk

램디스크가 성공적으로 마운트 된것을 확인할 수 있습니다.

$ df -h
...
D:\             466G  111M  466G   1% /mnt/d
tmpfs           1.0G     0  1.0G   0% /workspace/ramdisk

램디스크를 사용하고 싶지 않다면 언마운트로 해제합니다.

$ umount /workspace/ramdisk

RAM disk, Disk Performance evaluation

간단하게 dd유틸리티를 사용하여 속도를 테스트 합니다.

on RAM disk

$ dd if=/dev/zero of=/workspace/ramdisk/perf bs=256M count=1; rm -f /workspace/ramdisk/perf

1+0 records in
1+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 0.100249 s, 2.7 GB/s

on disk

$ dd if=/dev/zero of=/workspace/perf bs=256M count=1; rm -f /workspace/perf

1+0 records in
1+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 0.159167 s, 1.7 GB/s

CPU Cache

• 캐시는 용량이 작고, 빠른 특성때문에 자주사용되는 데이터를 주로 저장합니다
  • Temporal locality(시간 지역성)
    • 마지막에 접근한 데이터를 다시 접근하는 특성을 말합니다.
    • stack, for loop
  • Spatial locality(공간 지역성)
    • 접근한 데이터의 주변 데이터를 다시 접근하는 특성을 말합니다.
    • Array, sequential execution ...
• Benefit
  • Cache hit : 캐시에 담아놓은 데이터를 접근하게 되면 Cache hit, 담아놓지 않은 데이터를 접근하면 Cache miss가됩니다. Cache hit하게 되면 메모리보다 훨씬 빠른속도로 데이터에 접근할 수 있습니다.
  • Delayed Write : 쓰기 작업시 바로 메모리에 접근하지 않고, 캐시에 쓰기작업을 한 후 메모리에 접근할 때 한번에 쓰기작업을 합니다.

Cache Affinity

• CPU Cache는 job이 이전에 접근한 메모리를 저장해놓고있는데 Context Switch이후 캐시되어 있는 프로세서가 아닌 다른 프로세서에 스케줄링 되면 Cache miss로 인해 성능저하(Cache miss)가 발생할 수 있습니다.
• 이를 방지하기 위해서 이전에 수행했던 프로세서에 스케줄링하여 Cache hit를 높이는것이 좋습니다.

SQMS(Single Queue Multiprocessor Scheduling)

여러개의 코어를 하나의 큐로 스케줄링

• 장점 : 구현이 간단하다, job이 공평하게 분배됨
• 단점 : 공유자원인 큐에 대한 lock오버헤드 발생

MQMS(Multi Queue Multiprocessor Scheduling)

각 코어마다 큐를 가지고 있음.

• 장점 : Affinity가 좋다, lock으로 인한 오버헤드가 적다.
• 단점 : load balancing을 고려해야 한다.

Load balancing(부하균등)

• 각 CPU의 큐는 독립적이므로 서로의 상태를 알지 못한다.
• 스케줄러는 가장 여유로운 큐를 Source큐로 선택, 임의 선택된 Target큐가 Source큐보다 Busy하면 Source큐는 Target큐의 Job을 Steal(Work stealing, Migration).

운영체제가 관리해야 할 자원은 크게 물리적인 자원과 추상적인 자원으로 구분할 수 있습니다.

운영체제에서 커널의 역할은 CPU나 메모리와 같은 물리적인 자원을 사용자에게 태스크와 세그먼트, 페이지와 같은 추상적인 자원으로 추상화 하여 사용자에게 인터페이스를 제공하는것입니다. 덕분에 우리는 메모리 레이아웃, 스케줄러, 네트워킹 등과 같은 시스템의 세부 구현 사항에 대한 이해 없이도 프로그램을 실행시킬 수 있습니다.

리눅스 커널의 구성요소

Figure 1 : Linux Kernel

그림은 리눅스 커널 내부를 논리적인 구성 요소로 구분하여 그린 것입니다. 커널의 Manager에 해당하는 요소들은 각각 Filesystem Manger는 디스크를 파일로, Memroy Manager는 메모리를 Page또는 Segment로, Task Manger는 CPU를 Task로, Network Manager는 네트워크 장치를 소켓으로, Device Manager는 block 또는 character로 물리적인 자원을 추상적인 자원으로써 제공해 줍니다.

kerenl

kernel 디렉토리에는 Figure 1의 Task Manager에 해당하는 부분이 구현된 디렉터리입니다. Task 생성 및 소멸, 스케줄링, 시그널 처리 등의 기능을 구현하고 있습니다.

arch

arch 디렉토리에는 하드웨어에 종속적인 부분들을 구현한 디렉토리로 cpu의 타입에 따라 하위 디렉토리가 구성다. 대표적인 architecture인 x86, arm등을 여기서 확인할 수 있습니다.

x86을 기준으로 살펴보면 ./arch/x86/boot에는 부팅시 사용하는 부트 스트랩 코드, ./arch/x86/kernel에는 task manager의 문맥교환 및 스레드 관리, ./arch/x86/mm page fault관련 처리 기능 등 하드웨어 종속적인 부분들이 구현되어있음을 확인할 수 있습니다.

fs

fs 디렉토리에는 Figure 1의 Filesystem Manager에 해당하는 부분이 구현된 디렉터리 입니다. 리눅스에서 지원하는 ext2, ext3, ext4, f2fs등의 파일시스템이 구현되어 있으며 open(), read(), write()와 같은 파일관련 시스템 호출이 구현되어 있습니다

mm

Memory Manager가 구현된 디렉토리로물리메모리, 가상메모리 관리, Task마다 할당되는 메모리 객체관리 등의 기능이 구현되어 있습니다.

driver

주변 장치를 추상화 하는 디바이스 드라이버가 구현된 디렉토리로 android, bluetooth, dma등 다양한 주변장치에 대한 드라이버가 구현되어있는것을 확인할 수 있습니다.

net

Network Manager가 구현된 디렉토리로 802, ipv4,6, appletalk, bluetooth등 다양한 통신 프로토콜이 구현되어있는것을 확인할 수 있습니다.

이외에도 프로세스간 통신기능을 구현한 ipc디렉토리, 커널 초기화를 구현한 init디렉토리, 리눅스 커널의 헤더파일을 구현한 inlcude디렉토리, 이외 다양한 기능들을 구현한 others디렉토리가 있습니다.

Process manager(CPU)

커널은 System Call Interface(이하 SCI)를 통해 응용 프로그램에 인터페이스를 제공하여 프로세스 생성(fork(), exec(), ...), 프로세스 종료(kill(), exit()), 프로세스간의 통신 및 동기화(signal(),...)를 수행합니다.

실행중인 스레드들은 CPU를 공유해야 합니다. 리눅스의 경우에는 CFS(Completely Fair Scheduler) 스케줄러를 통해 이를 관리를 합니다. 시스템이 현재 프로세스를 계속 수행할 수 없는 상황이 되면 커널의 schedule()함수가 호출되고 그 내부의 __schedule()함수가 스케줄링의 핵심동작을 수행합니다.

static void __sched notrace __schedule(bool preempt) {
    struct task_struct *prev, *next; // 프로세스의 속성 정보를 표현하는 자료구조
    unsigned long *switch_count;
    struct rq_flags rf;
    struct rq *rq;
    int cpu;

    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr; // 현재 실행중인 프로세스의 태스크 디스크립터 주소를  prev로

...

    next = pick_next_task(rq, prev, &rf); // 다음 실행할 프로세스의 태스크 디스크립터 주소를 next로
    clear_tsk_need_resched(prev);
    clear_preempt_need_resched();

    if (likely(prev != next)) { // prev와 next가 다른경우
        rq->nr_switches++;
        rq->curr = next; // 런큐 curr 필드에 저장합니다.

        ++*switch_count; // context switch 횟수 정보를 담고있습니다.

        trace_sched_switch(preempt, prev, next);

        /* Also unlocks the rq: */
        rq = context_switch(rq, prev, next, &rf); // context switch를 수행합니다.
    } else {
        rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
        rq_unlock_irq(rq, &rf);
    }

    balance_callback(rq);
}

Factory Pattern

• 생성패턴의 한 종류
• 객체를 생성하는 공장(Factory)

interface Animal {
    void speak();
}

class Cat implements Animal {
    @Override
    public void speak() {
        System.out.println("meow!");
    }
}

class Dog implements Animal {
    @Override
    public void speak() {
        System.out.println("bark!");
    }
}

• 위와 같이 Animal을 상속받는 Dog, Cat클래스가 존재한다고 가정합니다.

class AnimalFactory {
    Animal createAnimal(String type) {
        if (type.equals("Dog")) {
            return new Dog();
        } else if (type.equals("Cat")) {
            return new Cat();
        } else {
            return null;
        }
    }
}

public class Main {
    static final AnimalFactory af = new AnimalFactory();

    public static void main(String[] args) {
        Animal dog = af.createAnimal("Dog");
        Animal cat = af.createAnimal("Cat");

        dog.speak(); // bark
        cat.speak(); // meow
    }
}

• createAnimal()함수는 인자로 받은 type에 따라 Cat을 생성해서 반환하거나, Dog를 생성해서 반환해 줍니다.

팩토리 패턴의 장점?

• 어떠한 상황에서는 객체 생성과정이 복잡할 수 있는데, 이러한 팩토리 패턴을 통해 복잡한 객체의 생성과정을 클라이언트가 직접 다룰 필요가 없어집니다.

Factroy Method Pattern

interface AnimalFactory {
    Animal createAnimal();
}

class DogFactory implements AnimalFactory {
    @Override
    public Animal createAnimal() {
        return new Dog();
    }
}

class CatFactory implements AnimalFactory {
    @Override
    public Animal createAnimal() {
        return new Cat();
    }
}

public class Main {
    static final AnimalFactory df = new DogFactory();
    static final AnimalFactory cf = new CatFactory();

    public static void main(String[] args) {
        Animal dog = df.createAnimal();
        Animal cat = cf.createAnimal();

        dog.speak();
        cat.speak();
    }
}

• 꼭 생성할 클래스가 팩토리 클래스와 1 : 1 매칭이 될 필요는 없습니다.
• 객체를 생성하는 메서드가 상속이 되었느냐가 Factroy Method Pattern의 핵심입니다.

Diff (Factory Pattern vs Factory Method Pattern)

Factory패턴은 Factory Method 패턴보다 단순한 형태로 인스턴스화 로직을 클라이언트에게 드러내지 않고, 직접 새로운 객체를 생성하여 제공합니다.

Factory Method Pattern은 객체를 생성하는 인터페이스로, 하위 구상클래스가 객체를 생성하여 제공합니다.

정적 팩터리 메서드와 생성자는 선택적 매개변수가 많을때 적절히 대응하기 어렵다는 제약이 있습니다.

이럴때 프로그래머들은 점층적 생성자 패턴을 즐겨 사용하였습니다.

1. Telescoping constructor pattern

점층적 생성자 패턴은 n개의 매개변수를 가지는 클래스에 대해 선택 매개변수를 1개 받는 생성자, 2개받는 생성자, ... n개 받는 생성자 의 형태로 생성자를 늘려가는 방식입니다.

class NutritionFacts {
    private final int servingSize;     // 필수
    private final int servings;     // 필수
    private final int calories;     // 선택
    private final int fat;            // 선택

    public NutritionFacts(int servingSize, int servings) {
        this(servingSize, servings, 0);
    }

    public NutritionFacts(int servingSize, int servings, int calories) {
        this(servingSize, servings, calories, 0);
    }

    public NutritionFacts(int servingSize, int servings, int calories, int fat) {
        this.servingSize = servingSize;
        this.servings = servings;
        this.calories = calories;
        this.fat = fat;
    }
}

하지만 이러한 점층적 생성자 패턴은 다음과 같은 단점을 가집니다.

• 매개변수의 개수가 많아질수록 코드를 작성하고, 읽기 어려워집니다. (확장성 및 가독성이 떨어집니다)
• 코드를 읽을때 각 값의 의미가 무엇인지 파악하기 어렵습니다.
• 매개변수의 개수가 몇개인지 주의하여 작성하여야 합니다.
• 매개변수의 순서를 헷갈리게 되면, 런타임에 엉뚱한 동작을 하게 됩니다.

2. JavaBeans Pattern

매개변수가 없는 생성자로 객체를 만든 후, 세터 메서드들을 호출하여 원하는 매개변수의 값을 설정하는 방식입니다.

class NutritionFacts {
    private int servingSize = -1;     // 필수
    private int servings    = -1;     // 필수
    private int calories    = 0;     // 선택
    private int fat             = 0;    // 선택

    public NutritionFacts() { }

    public void setServingSize(int val);
    public void setServings(int val);
    public void setCalories(int val);
    public void setFat(int val);
}

점층적 생성자 패턴에 비해 인스턴스를 더 만들기 쉽고 그결과 더 읽기 쉬운 코드가 되었습니다.

하지만 클라이언트는 객체 하나를 만들기 위해 여러 메서드를 호출해야 하고, 객체가 완전히 생성되기 전까지는 일관성이 무너진 상태에 놓이게 됩니다. 때문에 클래스를 불변(final)로 만들수 없게 되고, 스레드 안정성을 얻기위한 추가적업이 필요하게 됩니다.

클래스의 모든 필드를 불변으로 만들면 생성 이후에는 읽기 작업만 가능해 지기 때문에 스레드 안정성을 보장합니다.

[Effective Java] Item 17에서는 클래스가 가변적이여야 하는 합당한 이유가 없다면 모든 필드는 private final이어야 한다고 설명합니다.

3. Builder Pattern

빌더패턴은 점층적 생성자 패턴의 안정성(Immutable class)과 자바 빈즈 패턴의 가독성(setter method)을 겸비합니다.

클라이언트는 필수 매개변수만으로 생성자를 호출하고 빌더 객체가 제공하는 세터 메서드로 선택 매개변수를 설정합니다. 이후 build 메서드를 호출하여 필요한 객체를 얻습니다.

// 코드 2-3 빌더 패턴 - 점층적 생성자 패턴과 자바빈즈 패턴의 장점만 취했다. (17~18쪽)
public class NutritionFacts {
    private final int servingSize;
    private final int servings;
    private final int calories;
    private final int fat;
    private final int sodium;
    private final int carbohydrate;

    public static class Builder {
        // 필수 매개변수
        private final int servingSize;
        private final int servings;

        // 선택 매개변수 - 기본값으로 초기화한다.
        private int calories      = 0;
        private int fat           = 0;
        private int sodium        = 0;
        private int carbohydrate  = 0;

        public Builder(int servingSize, int servings) {
            this.servingSize = servingSize;
            this.servings    = servings;
        }

        public Builder calories(int val)
        { calories = val;      return this; }
        public Builder fat(int val)
        { fat = val;           return this; }
        public Builder sodium(int val)
        { sodium = val;        return this; }
        public Builder carbohydrate(int val)
        { carbohydrate = val;  return this; }

        public NutritionFacts build() {
            return new NutritionFacts(this);
        }
    }

    private NutritionFacts(Builder builder) {
        servingSize  = builder.servingSize;
        servings     = builder.servings;
        calories     = builder.calories;
        fat          = builder.fat;
        sodium       = builder.sodium;
        carbohydrate = builder.carbohydrate;
    }

    public static void main(String[] args) {
        NutritionFacts cocaCola = new NutritionFacts.Builder(240, 8)
                .calories(100).sodium(35).carbohydrate(27).build();
    }
}

NutritionFacts cocaCola = new NutritionFacts.Builder(240, 8).calories(100).sodium(35).carbohydrate(27).build();에서 볼 수 있듯, 빌더의세터 메서드들은 빌더 자신(this)를 반환하기 때문에 연쇄적으로 호출이 가능합니다.

이러한 방식을 메서드 호출이 흐르듯 연결된다는 뜻으로 Fluent API 또는 메서드 연쇄(method chaining)라 합니다.

빌더패턴은 점층적 생성자 패턴에 비해 확장에 유리하고 가독성이 높은 동시에 불변성을 확보하여 자바 빈즈 패턴보다 안정적입니다. 따라서 생성자나 정적 팩터리가 처리해야 할 매개변수가 많다면 빌더 패턴을 선택하는것이 좋습니다.

Reference

• Effective Java 3th Edition

블룸필터란

수많은 양의 정보가 저장된 데이터베이스에서 해당 데이터가 존재하는지 확인하는 작업에는 부하가 뒤따릅니다. 이를 위해 선형탐색을 사용한다면 너무나 오랜 시간이 소요될 것입니다. 이진 탐색도 좋은 방법이지만 더 나은 방법이 있을 것 같습니다.

이렇게 어떤 집합에 특정원소가 있는지 확인하는 작업을 Membership Testing이라고 합니다. 이러한 Membership Test를 위한 자료구조에는 Bloom filter, AVL, red-black tree등이 있습니다. 이중 Bloom filter는 확률적 자료구조로 에러를 허용하는 대신 공간복잡도를 낮추었습니다.

Bloom Filter는 Burtoon H. Bloom이 1970년의 논문 Space/Time Trade-offs in Hash Coding with Allowable Errors에서 제안한 확률적 자료구조입니다.

Working

Bloom Filter는 다음과 같이 m개의 비트로 구성된 bit 배열 자료구조입니다.

Insert

주어진 input값(test, )에 대해 k개의 hash function(h1,h2,h3,...,hk)을 통해 hash를 계산합니다.(3개의 hash function을 사용한다 가정하겠습니다.)

// input : test
h1(test) % 10 = 0
h2(test) % 10 = 3
h3(test) % 10 = 7
// input  : monkey 
h1(monkey) % 10 = 3
h2(monkey) % 10 = 4
h3(monkey) % 10 = 5

)

Lookup(Membership Test)

Membership Test는 동일한 input을 주어 필터에 해당하는 해시값이 모두 1로 설정되어있다면 해당 input값이 존재할 것이라고 판단할 수 있습니다.

False Positive

거짓양성(False Positive)는 값이 존재하지 않음에도 불구하고 해당값이 존재할것이라 판단하는것을 말합니다.

// input  : bloom
h1(bloom) % 10 = 3
h2(bloom) % 10 = 5
h3(bloom) % 10 = 7

예를들어 위와 같이 'bloom'이라는 input을 조회했을때 해시값이 모두 1이므로 해당 값이 존재할 것이라 판단하게 됩니다. 하지만 bloom은 존재하지 않기때문에 이를 거짓양성(False positive)라고 합니다.

이러한 거짓양성의 발생률은 Bloom Filter의 크기를 조절하여 조정할 수 있습니다. 당연히 Bloom Filter를 위해 더많은 공간(hash function, bit array)을 할당할수록 거짓양성률이 낮아집니다.

Space Efficiency

값을 저장하는 배열, 연결리스트, 해시맵, 트리와 같은 자료구조는 실제 값을 저장해야 하지만, Bloom Filter는 실제값을 저장하지 않고 bit array를 통해 표현하기 때문에 공간 복잡도가 낮습니다. 다만 이는 hash collision을 유발합니다.

Hash Collision(해시 충돌)
Hash table의 크기가 충분히 크지 못해 서로다른 입력값이 동일한 hash값을 가지는 상황을 의미합니다.

Bloom Filter의 종류(Classification)

• Standard Bloom Filter(SBF) : 전통적인 블룸필터로 거짓 양성과 거짓음성의 문제를 가지고 있습니다. 거짓양성은 비트 배열의 크기가 충분히 크기 못할때 발생하며, 거짓음성은 원소를 삭제할때 일어납니다. 이러한 문제때문에 SBF는 원소를 삭제할 수 없습니다.
• Counting Bloom Filter(CBF) : SBF의 확장성 문제를 해결하기 위해 등장하였으며, 비트배열에 카운터를 포함합니다. 삽입연산이 발생하면 카운터를 증가시키고 삭제연산이 발생하면 카운터를 감소시켜 삽입/삭제가 가능하도록 구현하였습니다. SBF에 비해 거짓 양성의 비율이 매우 높고, 삭제연산으로 인해 거짓 음성이 발생할 수 있습니다.
• Fingerprint Bloom Filter : CBF기반으로 만들어 졌으며 binary bit를 사용하는 대신 작은 크기의 hash값을 사용하여 CBF의 높은 거짓 양성률을 해결하였습니다. 하지만 이로인해 CBF에 비해 높은 공간복잡도를 보입니다.
• Hierachical Bloom Filter : 트리구조의 Bloom filter로 높은 정확도, 확정성, 그리고 낮은 거짓 양성률을 보입니다. 대표적으로 Forest Structured Bloom filter, Bloom Store가 있습니다.
• Multidimensional Bloom Filter(MDBF) : 다차원의 Bloom filter 배열을 사용합니다.
• Compressed Bloom Filter : 공간 효율적인 Bloom filter이지만 압축률이 높아질수록 거짓양성률이 매우 높아집니다.

활용

그림 출처: 위키피디아 블룸필터 문서

Bloom Filter는 위의 그림과 같이 Filter는 메모리에 두고 실제 데이터는 Storage에 저장하여 디스크 접근시간으로 인한 성능저하를 개선할 수 있습니다. 하지만 이경우에도 거짓 양성으로인한 불필요한 디스크 접근이 발생할 수 있습니다.