일단 써보기

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에 저장하여 디스크 접근시간으로 인한 성능저하를 개선할 수 있습니다. 하지만 이경우에도 거짓 양성으로인한 불필요한 디스크 접근이 발생할 수 있습니다.

LSM-Tree와 B-Tree는 현대 Key-value 저장소의 스토리지 엔진으로 주로 사용되는 자료구조입니다. LSM-Tree의 경우 updata 쿼리에서, B-Tree는 좁은 범위의 lookups에서 좋은 성능을 보입니다.

B-Trees

B-tree는 디스크에서 사용하기위해 설계된 인덱스 구조로 R. Bayer 와 E. McCreight가 1970년 7월 발표한 논문 "Organization and Maintenance of Large Ordered Indexes"에서 처음 발표되었습니다.

인덱스구조
데이터베이스에서 탐색속도를 높이는데 사용되는 자료구조입니다.
인덱스 구조를 생성하고 유지하기 위해서는 추가적인 스토리지 공간과 쓰기작업과 관련된 비용이 발생합니다. 하지만 인덱스를 사용하여 쿼리하는것이 데이터베이스의 모든 행을 탐색하는것보다 훨씬 빠르기 때문에 이러한 비용은 큰문제가 되지 않습니다.

B-tree를 사용하는 가장 큰 이유는 디스크 접근시간을 줄일 수 있기 때문입니다. B-tree는 2개 이상의 차수를 가진 트리구조로 비교적 적은 읽기 횟수로 데이터의 저장 위치를 알아낼 수 있습니다.

LSM-Trees

Log-Structured Merge Tree는 Patrick O’Neil이 1996년 발표한 논문 The Log-Structured Merge-Tree (LSM-Tree)에서 처음 발표되었습니다. LSM-tree는 우수한 업데이트 성능과 space amplification특성때문에 많은 key-value store 데이터베이스에서 차용되었습니다.

Space amplification

LSM-tree의 update는 디스크 I/O를 최소화하기위해 메모리의 버퍼에 log를 남깁니다. 그리고 버퍼는 주기적으로 정렬되어 디스크에 쓰여지는데 이를 flush라고 하며, 정렬된 일련의 배열을 run이라고 합니다.

LRU

LRU는 Least Recently Used의 약자로 페이지 폴트가 발생하게 되면 가장 오래전에 접근했던 페이지를 퇴출시켜 공간을 확보합니다.

버퍼에 존재하는 페이지에 접근하는 경우 리스트의 head로 페이지를 이동시킵니다. 이러한 방식으로 최근에 접근한 페이지 일수록 head에 가깝게, 오래전에 접근한 페이지일수록 tail에 가까이 위치하게 됩니다. 새로운 페이지를 위한 공간이 필요할 경우 tail에 존재하는 페이지를 퇴출시킵니다.

LRU는 주로 이중 연결리스트와 해시테이블을 통해 구현합니다. 구현이 간단하고, 알고리즘의 효율성 때문에 80년대 초반까지 대부분의 시스템에서 차용되었던 알고리즘입니다. 하지만, 이러한 장점들에도 불구하고 특정 상황에서 최악의 성능을 보입니다.

Sub-Optimality during DB scans

데이터베이스 테이블이 LRU 캐시보다 큰 경우, 테이블을 스캔할 때 DB 프로세스는 전체 LRU 캐시를 삭제하고 스캔한 테이블의 페이지들로 채우게 됩니다. 이러한 페이지들이 다시 참조되지 않는다면 데이터 베이스의 성능을 크게 저하시킬 수 있습니다.

2Q

LRU의 이러한 단점을 보완하기 위해 2Q는 추가적인 대기열을 통해 실제로 Hot한 페이지가 LRU캐시에 위치할 수 있도록 합니다. 즉, 2Q는 접근 빈도 뿐만 아니라, 페이지의 Hot여부도 판단합니다.

Simplified 2Q

2Q 알고리즘은 기본 LRU버퍼 Am과 보조 FIFO버퍼 A1으로 구성됩니다. Page Fault가 발생하면 먼저 A1버퍼에 페이지를 push합니다. 이후 페이지가 다시 참조되면 LRU버퍼 Am으로 페이지를 push합니다. 이를통해 Am버퍼에 있는 페이지의 hot함을 보장할 수 있습니다.

만약 A1버퍼의 page가 다시 참조되지 않으면 A1버퍼의 fifo정책에 따라 퇴출됩니다.
이는 해당 페이지가 cold하며, 캐시될 필요가 없음을 암시합니다.

def access_page(X: page):
    # if the page already exists in the LRU cache
    # in buffer Am
    if X in Am:
         Am.move_front(X)

    # if the page exists in secondary storage
    # and not it gets access.
    # since the page is accessed again, indicating interest
    # and long-term need, move it to Am.
    elif X in A1:
         A1.remove(X)
         Am.add_front(X)

    # page X is accessed for the first time
    else:
         # if A1 is full then free a slot.
         if A1.is_full():
             A1.pop()

         # add X to the front of the FIFO A1 queue
         A1.add_front(X)

A1버퍼의 크기가 너무 작다면, hot의 기준이 너무 높아지게 되며, A1버퍼의 크기가 너무 커지게 되면 메모리의 한계로 인해 Am버퍼의 크기를 줄이게 되고 이는 데이터 베이스의 성능을 저하시킬 수 있습니다.

2Q Full Version

일반적인 데이터베이스 접근 패턴에서 페이지는 짧은 시간동안 많은 참조를 받은 다음, 오랜시간 동안 참조되지 않습니다. 만약 캐시를 해야한다면, 짧은 시간의 많은 참조 이후에도 정기적으로 참조되는 페이지가 캐시되야 할 것입니다.

이러한 데이터 베이스 접근패턴에서 2Q를 활용하기 위해, 2Q Full Version은 보조 버퍼 A1을 A1-in, A1-out으로 나눕니다.

새로운 페이지는 항상 A1-in에 저장이 되고 페이지가 다시 참조될때까지 A1에 머무릅니다.
만약 페이지가 오래되어 퇴출되는 경우 메모리에서는 페이지가 삭제되지만, A1-out에 디스크 참조를 저장합니다. A1-out의 페이지가 다시 액세스 되는 경우 Am버퍼로 이동합니다.

References

• 2Q Cache Management Algorithm - Arpit's Newsletter
• LRU - Wikipedia
• The Saga of the ARC Algorithm and Patent
• 2Q: A low overhead high-performance buffer management replacement algorithm