'IT 관련'에 해당되는 글 29건

본 포스팅은 개인적인 공부를 위해 책의 내용을 요약하여 정리하는 글입니다.

작성자는 분산 데이터베이스, 하둡에 대해서 처음 공부해보는 것이니 참고가 된다면 기쁘겠지만 틀린 정보가 있을 수 있습니다.

개발환경 : 우분투 18.04, 하둡 3.0.3

데이터셋의 크기가 한개의 물리적 머신의 저장용량보다 커지면 여러개의 머신에 데이터셋을 분할시킬 필요가 있다.

분산 파일 시스템(Distributed File System)

머신들의 네트워크의 저장소를 관리하는 파일 시스템

(Filesystems that manage the storage across a network of machines are called distributed filesystem)

하둡은 HDFS라는 분산 파일 시스템을 가진다. HDFS는 하둡의 주력 파일 시스템이지만, 사실 하둡은 일반목적 파일시스템에 대한 추상화도 가지고 있다. 이번 장에서는 하둡이 어떻게 다른 저장소 시스템(Storage system)(로컬 파일 시스템, 아마존 S3 등)과 통합되는 지 볼 것이다.

1. HDFS의 디자인(The Design of HDFS)

HDFS는 아주 큰 파일들을 스트리밍 데이터 엑세스 패턴으로 저장하도록 디자인 된 파일시스템으로, 상용 하드웨어들의 클러스터 상에서 돌아간다.

다음 용어들을 보도록 하자.

Very large

"Very large"라는 말은 수백 메가바이트, 기가바이트, 테라바이트의 크기를 말한다. 최근에는 페타바이트 단위의 데이터를 저장하는 하둡 클러스터도 있다.

Streaming data access

HDFS는 write-once, read-many-time(한번 쓰고 여러번 읽기)가 가장 효율적인 데이터 처리 패턴이라는 아이디어를 기반으로 설계되었다.  데이터셋은 생성되거나 복제 된 것이고, 그 데이서 셋에 대한 다양한 분석 작업이 이루어 질 것이다. 각각의 분석작업은 데이터셋의 많은 부분들을 필요로 할 것이므로 전체 데이터셋을 읽는 시간이 첫 번째 레코드를 읽는 대기시간보다 중요하다.

*(Streaming Data Access란 랜덤 탐색 없이 파일의 시작점으로 부터 sequential하게 쭉 읽어나가는 것을 말한다.

https://stackoverflow.com/questions/16260535/streaming-data-access-and-latency-in-hadoop-applications)

Commodity hardware

하둡은 비싸고 신뢰할 수 있는 하드웨어를 필요로하지 않는다.

하둡은 상용 하드웨어(Commodity hardware)(여러 상점에서 구할 수 있는 일반적인 하드웨어들)의 클러스터 상에서 돌아가도록 디자인되었기 때문에 클러스터 상의 노드에 오류가 있을 가능성이 높다. HDFS는 그런 오류에도 크게 방해되지 않고 작동되도록 디자인되었다.

HDFS를 사용하는게 부적합 한 경우도 있다. 이 문제는 미래에는 바뀔 수 있지만, 지금은 HDFS가 취약한 부분이다.

다음의 특성을 가지는 어플리케이션에는 HDFS를 사용하는 것이 부적합 할 수 있다.

짧은 반응시간(Low-latency data access)

수십 밀리세컨드 정도로 데이터 접근에 대해 짧은 응답시간(latency)을 필요로하는 어플리케이션은 HDFS와는 잘 맞지 않다. HDFS는 처리량(throughput)이 높지만 응답시간은 느릴 수 있다. 데이터 접근에 짧은 응답시간을 위해서는 HBase(20장에서 다룬다.)이 더 적합하다.

많은 작은 파일(Lots of small files)

메모리 상에 존재하는 네임노드(namenode)가 파일 시스템의 메타데이터를 가지고 있기 때문에, 파일 시스템 상에 존재 할 수 있는 파일의 수는 네임노드의 크기에 의해 제한된다.

일반적으로(As a rule of thumb) 각 파일, 디렉토리, 블록의 크기는 150바이트다. 그러므로 예를 덜어, 각각 1블록을 차지하는 100만개의 파일이 있다고 하면 적어도 300MB의 메모리를 필요하게 된다. 수백만가지의 파일을 저장하는 것이 가능하긴 해도, 수억개의 파일을 저장하는 것은 현재의 하드웨어 기술력으로는 무리다.

다수의 작성자, 무작위적인 변경(Multiple writers, arbitrary file modifications)

HDFS 상의 파일들은 한 명의 writer에 의해 쓰여지는 것이 좋다. Writer는 항상 append-only 방법으로 파일의 맨 끝에 만들어진다. 그래서 다수의 writer나 파일의 무작위적인 오프셋 변경은 지원되지 않는다.

2. HDFS 컨셉

2.1 Blocks

블록은 데이터를 읽고 쓰는 최소한의 크기단위다. 파일 시스템의 블록은 몇 키로바이트 정도이고, 디스크의 블록은 보통 512 바이트다.

HDFS도 블록의 컨셉을 가지는데, 블록의 크기가 기본 128MB로 아주 크다.

다른 블록 개념들과 같이 HDFS도 블록의 크기보다 큰 파일은 블록의 크기만큼 나눠서 저장하는데(예를 들어 블록의 크기가 128MB이고, 200MB의 파일을 저장해야 한다면 한 블록에 128MB, 다른 블록에 나머지를 저장) 다른 블록 개념들과 다르게 블록의 크기보다 작은 파일은 블록 하나를 완전히 소유하지 않는다.(예를 들어 블록의 크기가 128MB이고 파일의 크기가 1MB이면 파일은 128MB를 다 차지하는 것이 아니라 1MB만 차지한다.)

이제부터 Block이라는 단어가 나오면 HDFS의 블록을 얘기하는 것이다.

HDFS의 블록 크기가 큰 이유

HDFS의 블록이 큰 것은 탐색의 코스트(seek time)를 줄이기 위해서다.

디스크에서 한 블록을 읽는데 걸리는 시간은 seek time + transfer time 이다.(seek time : 데이터의 시작점을 찾는 시간. transfer time : 블록의 크기 / transfer rate). 여기서 transfer rate는 디스크의 물리적인 한계가 있으므로 더 빠르게 만들기는 어려우니 블록의 크기를 크게 만들면 transfer time이 크게 늘어나 한 블록을 읽는 시간에 seek time은 무시해도 될 정도로 작은 값으로 취급할 수 있다.

그러므로 블록을 크게 만들면 대용량 데이터를 읽을 때 seek time의 영향이 줄어들고 디스크의 물리적인 속도인 transfer rate과 데이터를 읽는 속도가 거의 비슷해진다.

분산 파일 시스템에서 블록 개념을 도입하는 이점

같은 파일의 블록들이 반드시 한 디스크 내에 존재해야하는 것은 아니다. 그래서 블록 개념을 도입하면 아주 큰 파일이더라도 네트워크상의 여러 디스크에 나눠서 저장 할 수 있다.

분산 시스템의 경우 고장나는 경우의 수가 다양하기 때문에 간단함(simplicity)이 아주 중요하다. 블록은 크기가 고정되어 있기 때문에 저장소 관리를 쉽게 하고,  블록은 데이터 덩어리일 뿐이니 블록에 대한 접근 권한 등 메타데이터가 불필요하다.

그래서 블록 개념을 도입하는것이 간단함을 유지하는데 도움이 된다.

각 블록은 몇개의 머신들에 중복되어 저장된다.(보통 3개의 머신에 나눠서 저장한다.) 한 블록이 이용불가능한 상황이 되면 다른 머신에 있는 중복 데이터를 가져 올 수 있는데, 이 과정은 클라이언트에게 투명하다(transparent).(클라이언트가 이런 과정은 신경쓰지 않아도 원하는 블록을 얻어 올 수 있다.)

그리고 자주 사용되는 파일의 블록들의 경우 좀 더 여러 곳에 복사 해 두어 클러스터 내의 읽기 부하량(read load)를 분산 시킬 수도 있다.

* HDFS의 fsck 명령어는 블록 개념을 이해하고 있는 명령어다. 다음의 명령어를 입력하면 파일시스템 내의 각 파일을 구성하는 블록들을 리스트화 해 줄 것이다.

# hdfs fsck / -files -blocks

2.2 네임노드와 데이터노드

의문점

레퍼런스

스택 오버플로우. streaming data access에 관한 내용. - https://stackoverflow.com/questions/16260535/streaming-data-access-and-latency-in-hadoop-applications

스택 오버플로우. HDFS의 블록이 큰 이유. - https://stackoverflow.com/questions/22353122/why-is-a-block-in-hdfs-so-large

본 포스팅은 개인적인 공부를 위해 책의 내용을 요약하여 정리하는 글입니다.

작성자는 분산 데이터베이스, 하둡에 대해서 처음 공부해보는 것이니 참고가 된다면 기쁘겠지만 틀린 정보가 있을 수 있습니다.

개발환경 : 우분투 18.04, 하둡 3.0.3

개발환경 구축은 Ssup2 블로그를 참조하였습니다.

(https://ssup2.github.io/record/Hadoop_%EC%84%A4%EC%B9%98_%EC%84%A4%EC%A0%95_Ubuntu_18.04/)

하둡은 여러 언어로 쓰여진 프로그램을 돌릴 수 있다. 이 장에서는 자바, 루비, 파이썬으로 표현된 프로그램을 보도록 하자.

1. A Weather Dataset

예제로 날씨 데이터를 분석하여 각 년도별로 최대 온도가 몇도인지 분석하는 프로그램을 만들어 보자.

1.1 DataFormat

예제 프로그램 작성을 위해 NCDC의 데이터를이용한다.

그리고 문제를 단순화하기 위해 기온 등 기본적인 요소만 사용한다.

* NCDC 데이터 받는 법

이 깃허브 링크로 들어가 전체 프로젝트를 다운받는다.

https://github.com/tomwhite/hadoop-book/

input/ncdc/ 디렉토리의 sample.txt 파일을 이용하면 된다.

2. Unix Tool을 이용한 데이터 분석

Shell Script를 이용한 데이터 분석에 대한 내용.

사실상 하둡과는 무관하므로 생략.

3. Hadoop을 이용한 데이터 분석

하둡의 병렬 처리기능을 이용하려면 쿼리문을 맵리듀스용으로 표현해야한다. 로컬로 소규모 테스트를 마치고 나면 클러스터 머신에서 돌려 볼 수 있다.

3.1 Map and Reduce

맵리듀스 작업은 맵/리듀스 2개의 phase로 구분하여 작동한다. 각 페이즈는 key-value pair를 입출력으로 가지고 그 타입은 프로그래머가 결정한다.

그리고 맵함수와 리듀스함수도 프로그래머가 결정한다.

맵 페이즈의 입력값은 raw NCDC 데이터다. 맵 페이즈에서는 텍스트 입력 포멧을 선택하여 raw 데이터의 각 라인을 텍스트값으로 변형하는데 사용 할 수 있다.

맵 함수는 리듀스 함수가 작업할 수 있게 데이터를 준비하는 단계로, 이번 예제에서 맵 함수는 년도와 온도를 뽑아오는 간단한 함수다.

또한 맵 함수는 빠져있거나, 의심스럽거나, 에러가 있는 베드 레코드(Bad Record)를 걸러내기도 한다.

그리고 리듀스 함수의 역할은 각 년도별로 최대 온도를 찾는 것이다.

데이터 처리 과정

먼저 맵함수는 다음의 입력을 받는다.

맵 함수에서 처리할 때, 데이터는 다음의 key-value pair로 표현된다. 

(*참고로 여기서 key 값은 파일의 시작점으로부터의 offset이다.)

여기서 우리에게 필요한 데이터는 진하게 칠한 년도와 온도 데이터다.

여기서 key 값은 필요없으니 무시하고, 맵 함수는 년도와 기온을 추출하여 결과값으로 내보낸다.

이제 이 결과값을 리듀스함수로 보내기 전에 맵리듀스 프레임워크가 이 결과값을 가공한다.

맵리듀스 프레임워크의 가공 과정에서는 데이터를 key 값을 기준으로 정렬하고 그룹화한다.

각 연도별 기온 리스트는 완성되었으니 리듀스함수에서 이 리스트들을 돌며 최대값을 고르면 완료된다.

3.2 Java MapReduce

이클립스 설정

우선 맵 리듀스 라이브러리 JAR 파일들을 프로젝트에 추가해야한다.

(* 라이브러리가 root 디렉토리에 있는 경우 이클립스를 관리자 권한으로 실행해야 JAR 파일들이 있는 디렉토리에 접근 가능합니다.)

생선한 프로젝트 우클릭-properties-Java Build Path-Libraries 에서 Add External JARs를 클릭하여 필요한 라이브러리들을 모두 추가한다.

이제 이번 예제 구현에 사용된 클래스 코드들을 살펴보도록 하자.

Mapper

import java.io.IOException;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Mapper;


public class TestMapClass extends Mapper<LongWritable, Text, Text, IntWritable>{
    private static final int MISSING = 9999;
    
    @Override
    public void map(LongWritable key, Text value, Context context)
            throws IOException, InterruptedException
    {
        String line = value.toString();
        String year = line.substring(15,19);
        int airTemperature;
        if(line.charAt(87) == '+')
        {
            airTemperature = Integer.parseInt(line.substring(88,92));
        }else{
            airTemperature = Integer.parseInt(line.substring(87,92));
        }
        
        //퀄리티 코드
        String quality = line.substring(92,93);

        //퀄리티 코드 == 01459 : 올바르게 읽어졌음.
        //올바르게 읽어진 데이터만 결과에 적용한다.
        if(airTemperature != MISSING && quality.matches("[01459]")) {
            //map() 메소드는 context를 통해 결과값을 전달한다.
            //결과값은 Hadoop 데이터 타입으로 변환하여 입력한다.
            context.write(new Text(year), new IntWritable(airTemperature));
        }
    }
}

Mapper 클래스는 제네릭 타입이라서 <input key, input value, output key, output value> 4개의 타입 패러미터를 갖는다.

(쉽게 말해서 템플릿을 사용하기 때문에 이 4개의 타입을 결정해줘야 한다.)

여기서 각 타입은 다음과 같다.

input key = Long int = LongWritable

input value = Text Line = Text

output key = Year = Text

output value = Air Temperature = IntWritable

하둡에서는 자바의 기본 타입을 쓰지 않고 새로운 타입을 제공한다.

LongWritable, Text, IntWritable이 각각 Long, String, Integer에 해당되는 하둡의 클래스 타입들이다.

이 하둡 클래스 타입들은 Serialization에 최적화된 클래스 타입들이다.

Reducer

import java.io.IOException;

import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Reducer;

public class MaxTemperatureReducer 
    extends Reducer<Text, IntWritable, Text, IntWritable>{
    @Override
    public void reduce(Text key, Iterable<IntWritable> values, Context context)
        throws IOException, InterruptedException{
        int maxValue = Integer.MIN_VALUE;
        for(IntWritable value : values)    {
            maxValue = Math.max(maxValue, value.get());
        }
        context.write(key, new IntWritable(maxValue));
    }
}

리듀서 클래스도 제네릭 타입이다.

<input key, input value, output key, output value>를 설정해 줘야하는데, 리듀서 함수의 input 타입은 맵 함수의 output 타입과 같아야 하므로 input key는 Text, input value는 IntWritable이다.

리듀서 함수의 output key는 Text, output value는 연도별 최대 온도값을 IntWritable로 내보낸다.

Main Class

import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

public class MaxTemperature {
    public static void main(String[] args)throws Exception{
        if(args.length != 2) {
            System.err.println("Usage: MaxTemperature <input path> <output path>");
            System.exit(-1);
        }
        //버전 업으로 사용법이 바뀜        
        //Job job = new org.apache.hadoop.mapreduce.Job();
        Job job = Job.getInstance();

        job.setJarByClass(MaxTemperature.class);
        job.setJobName("Max Temperature");
        
        //입력 경로, 출력 경로 설정
        FileInputFormat.addInputPath(job, new Path(args[0]));;
        FileOutputFormat.setOutputPath(job,new Path(args[1]));
        
        //매퍼, 리듀서 클래스 설정
        job.setMapperClass(TestMapClass.class);
        job.setReducerClass(MaxTemperatureReducer.class);
        
        //output key, value 타입 설정
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(IntWritable.class);
        
        System.exit(job.waitForCompletion(true) ? 0 : 1);
    }
}

Job 객체는 작업의 세부사항을 정의하고 일이 어떻게 처리되는지에 대한 통제권을 제공하는 객체다.

하둡 클러스터에서 작업을 수행할 때, main 클래스 코드를 JAR 파일로 만들면 하둡이 클러스터 내에서 이 JAR 파일을 분배한다.

Job 클래스의 setJarByClass() 메소드를 사용하여 클래스를 전달하면 하둡이 해당 클래스를 포함한 JAR 파일을 찾아준다.

Job 객체를 생성한 후에는 FileInputFormat 클래스의 addInputPath() 메소드로 input 경로를 정하는데, input 경로는 파일, 디렉토리, 파일 패턴, 무엇이든 될 수  있고, addInputPath() 메소드를 여러번 불러 다양한 경로를 포함시키는 것도 가능하다.

output 경로는 FileOutputFormat 클래스의 setOutputPath() 메소드로 결정한다. 리듀서 함수의 결과가 이 경로에 쓰여지며, 해당 디렉토리는 비어있어야한다.

3.3 A test Run

이제 구현한 코드로 실제 데이터를 처리해 보도록 하자.

JAR 파일로 export

우선 구현한 프로젝트를 JAR 파일로 export 해야한다.

File - Export에서  JAR file을 선택하고 파일 이름을 정한 후 JAR 파일을 만든다.

HDFS에 파일 등록

하둡을 이용해 데이터를 처리하기 위해서는 우선 HDFS(Hadoop Distributed File System)에 데이터 파일을 등록해야한다.

다음 명령어들을 이용하여 이를 수행한다.

# hadoop fs -mkdir '디렉토리 명'
# hadoop fs -put '파일 명' 'HDFS상 디렉토리'
# hadoop fs -ls '디렉토리 명'

mkdir : 디렉토리 생성

put : HDFS에 파일 등록

ls : 디렉토리 내용 출력

분석하기

이제 yarn 명령어를 이용하여 분석을 실행한다.

# yarn '실행시킬 타입' '실행시킬 파일 이름' '실행시킬 클래스 경로' [-옵션]

여기서 우리는 JAR 파일을 실행 할 것이므로 실행시킬 타입은 jar 이다.

실행시킬 파일 이름은 HDFS에 등록된 파일 들 중 입력 파일로 사용할 파일의 이름이다.

실행시킬 클래스 경로는 main 함수를 포함하는 클래스를 (패키지명.클래스명)으로 입력하면 된다.

분석 결과 1949년도 최고 온도는 11.1도, 1950년도 최고 온도는 2.2도로 측정되었다고 한다.

output 디렉토리 입력시 output 디렉토리는 존재하지 않는 디렉토리여야한다.

분석 결과를 출력 할 때 하둡이 입력한 output 디렉토리 이름으로 새 폴더를 만들 것이다.

4. Scaling out

스케일 아웃 작업을 하기 위해서 데이터는 HDFS에 저장되어야 한다.

4.1 데이터 플로우(Data Flow)

* 맵 리듀스 Job 이란 : 클라이언트가 수행되길 원하는 작업들의 묶음이다. 입력 데이터, 맵리듀스 프로그램, 설정 정보로 구성된다.

(A MapReduce job is a unit of work that the client wants to be performed;)

하둡은 맵리듀스 job을 task로 나누어 처리한다.

이 task는 map task와 reduce task로 나뉘고, task들은 YARN에 의해 스케쥴링되고 클러스터상의 노드에서 실행된다.

하둡은 맵 리듀스 job의 input을 input split, 또는 split이라고 불리는 고정크기의 조각들로 나눈다.

하둡은 각 스플릿(split)마다 하나의 태스크를 만들고 각각의 테스크는 사용자 정의 맵함수를 실행시킨다.

이 스플릿의 크기는 너무 작으면 스플릿과 map task를 관리하는 오버헤드가 너무 커지고, 너무 크면 처리하는데 시간이 오래 걸린다.

그래서 적절한 크기로 스플릿을 나누어야 하는데, 일반적으로 HDFS block의 크기인 128MB가 가장 효율적이다.

Data Locality Optimization

하둡은 HDFS 내의 입력 데이터가 있는 노드에서 태스크를 수행할 때 가장 빠르게 작동한다.

이러한 속성을 데이터 지역성 최적화(Data Locality Optimization) 라고 한다.

*Reduce task는 상관없고 Map task에만 영향이 있는 속성이다.

HDFS block의 크기로 스플릿을 나누는 것이 효율적인 이유.

간혹 HDFS 블록 복제본을 호스팅하는 모든 노드들이 이미 다른 맵 태스크를 수행하고 있는 경우 잡 스캐줄러가 같은 랙 장비 내에서 비어있는 맵 슬롯(map slot)을 가진 노드를 찾으려 하게 된다.

더욱 잘 일어나지 않지만, 다른 랙 장비에 있는 노드를 사용해야하는 경우도 있다. 이런 경우는 렉 장비간 네트워크 통신이 필요하게 된다.

이런 상황들에선 성능이 저하된다.

Data Locality Optimization라는 특성도 네트워크 통신으로 인한 성능저하가 발생하기 때문에 생기는 특성이라고 볼 수 있을 것이다.

이제, HDFS Block의 크기(128MB)로 스플릿을 나누는 것이 효율적인 이유에 대해 얘기해보자면, 한개의 노드에 저장 될 수 있는 가장 큰 크기의 데이터가 128MB이기 떄문이다.

128MB보다 큰 데이터를 저장하려고 하면 두개의 블록에 저장하게 될 것이고, 스플릿들 중 일부는 네트워크를 통해 다른 렉 장비에 있는 노드에 저장될 것이다. 네트워크 작업이 늘어나기 때문에 성능이 저하된다.

Map Task는 output을 HDFS에 저장하지 않고 로컬 디스크에 저장한다.

Map Output은 최종결과가 아닌 reduce task에서 입력 데이터로 사용할 중간 결과다. 모든 작업이 끝나면 불필요하기 때문에 HDFS에 저장하지 않는다.

Reduce Task에는 Data Locality 속성의 이점이 없다.

일반적으로 한개의 Reduce Task의 입력은 모든 매퍼들로부터 오기 때문에 Reduce Task가 입력 데이터를 받는 데에는 네트워크 통신이 불가피하기 때문이다.

Reduce ouput의 첫 번째 복사본만 로컬로 저장되고 나머지는 다른 랙 장비에 저장되어 네트워크 대역폭을 소모하는 작업이 된다. 하지만 이는 HDFS 파이프라인이 소모하는 양 만큼만이다.

Reduce Task의 수는 input size와 상관 없이 독립적으로 명시해줘야 한다. 이것에 관해서는 추후에 다루도록 한다.

Reduce Task가 다수일 때에는 Map Task가 output을 partition으로 나누고, 한 파티션당 한 개의 reduce task에 할당된다.

각 파티션에는 다수의 키 값이 존재할 수 있고, 각 키 값들에 대한 레코드는 각 키와 같은 파티션 내에 포함되어야 한다.

Reduce Task가 0개 필요한 경우도 있다. 이는 프로세스가 완전히 평행하게 수행 될 수 있어서 Shuffle 작업이 필요 없는 경우에 유용하다. 이 경우 노드를 벗어나서 데이터를 전송하는 경우는 Map Task가 HDFS에 결과값을 보낼 때 뿐이므로 성능도 괜찮게 나올 수 있다.

4.2 Combiner Function

많은 맵리듀스 job들이 클러스터의 이용가능한 네트워크 대역폭 한계 때문에 성능이 저하된다. 그래서 맵과 리듀스 태스크 사이의 데이터 전송을 최소화하는것이 중요하다.

하둡에서는 개발자가 Combiner function을 정의하게 할 수 있다.

Combiner function은 map의 output을 입력으로 받아서 새로운 output으로 만들고, 그 output을 reduce 함수의 input으로 전달하는 역할을 하는 함수다.

Combiner function은 최적화 함수이므로 몇 번 호출되든 상관 없이 reducer 함수의 output은 동일해야한다.

Combiner function의 contract는 사용될 함수의 타입을 제한한다.

Combiner function에 대한 이해를 돕기 위해, 위에서 봤던 연도별 최고 온도 예제를 생각해 보자.

1950년도의 온도 데이터를 2개의 Mapper가 추출해냈다고 하자.

첫 번째 Mapper 결과:

(1950, 0)

(1950, 20)

(1950, 10)

두 번째 Mapper 결과:

(1950, 25)

(1950, 15)

Combiner function을 따로 정의하지 않으면 Reducer Task는 다음의 데이터를 받는다.

(1950, [0, 20 , 10, 25, 15])

그리고 Reducer Task의 최종 output은 

(1950, 25)

일 것이다.

여기서 Mapper Task의 Output 중 최고 온도만 선별하도록 Combiner Function을 정의하면 Reduce Task에는 다음의 데이터만 전송하면 된다.

(1950, [20, 25])

이렇게 하면 맵과 리듀스 태스크 사이의 데이터 전송량이 최소화 되고, Combiner Function을 몇 번 적용하든지 Reduce Task의 결과값이 변하지 않는다.

MAX(0, 20, 10, 25, 15) = 25

MAX(MAX(0, 20, 10), MAX(25, 15)) =MAX(20, 25) = 25

그리고 이 경우에는 Combiner Function을 몇 번 적용하든지 Reduce Task의 결과값이 변하지 않기 때문에 적용해도 되는데, 그렇지 않은 경우에는 주의해야한다.

예를 들어, 최고 온도가 아닌 평균 온도를 구하는 경우를 생각 해보자.

결과는 다음과 같이 변하게 된다.

mean(0, 20, 10, 25, 15) = 14

mean(mean(0, 20, 10), mean(25, 15)) =mean(10, 20) = 15

Combiner Function 적용

Combiner Function은 Reducer 클래스를 사용하여 정의된다.(Reducer 클래스를 상속하여 구현)

최고 온도 예제에서는 Reducer 함수와 Combiner 함수의 역할이 사실상 똑같기 때문에 MaxTemperatureReducer 클래스를 Combiner로 그대로 사용하면 된다.

Main Class (Combiner 포함)

import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

public class MaxTemperature {
    public static void main(String[] args)throws Exception{
        if(args.length != 2) {
            System.err.println("Usage: MaxTemperature <input path> <output path>");
            System.exit(-1);
        }
        //버전 업으로 사용법이 바뀜        
        //Job job = new org.apache.hadoop.mapreduce.Job();
        Job job = Job.getInstance();

        job.setJarByClass(MaxTemperature.class);
        job.setJobName("Max Temperature");
        
        //입력 경로, 출력 경로 설정
        FileInputFormat.addInputPath(job, new Path(args[0]));;
        FileOutputFormat.setOutputPath(job,new Path(args[1]));
        
        //매퍼, 리듀서, Combiner 클래스 설정
        job.setMapperClass(TestMapClass.class);
        job.setCombinerClass(MaxTemperatureReducer.class);
        job.setReducerClass(MaxTemperatureReducer.class);
        
        //output key, value 타입 설정
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(IntWritable.class);
        
        System.exit(job.waitForCompletion(true) ? 0 : 1);
    }
}

Running a Distributed MapReduce Job

전체 데이터셋에 대해서 동일한 프로그램을 변환하지 않고 사용해서 처리가능하다.

이것에 관해서는 6장에서 다룬다.

5. 하둡 스트리밍

하둡은 자바 이외의 언어로도 맵, 리듀스 함수를 작성 할 수 있는 API를 제공한다. 그러니 표준 입출력을 사용할 수 있는 어떤 언어든 MapReduce 프로그램 개발에 사용할 수 있다.

스트리밍은 원래 텍스트 프로세싱에 가장 적합하다.

맵 입력 데이터는 표준 입력으로 줄별로 전달되고, 줄별로 출력된다.

맵함수의 Output인 key-value pair는 tab으로 구분되고, 이는 리듀스 함수의 입력에도 동일하게 적용된다.

레퍼런스

Hadoop The Definitive Guide 4th Edition(O'REILLY. Tom White)

하둡 설치

(https://ssup2.github.io/record/Hadoop_%EC%84%A4%EC%B9%98_%EC%84%A4%EC%A0%95_Ubuntu_18.04/)

NCDC 예제 데이터

(https://github.com/tomwhite/hadoop-book/)

Kamang's IT Blog

(https://kamang-it.tistory.com/entry/Hadoop-02%EA%B8%B0%EC%B4%88-%EC%98%88%EC%A0%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0SingleFileWirteRead)

1. 퍼사드 패턴이란

1.1 퍼사드 패턴의 정의

퍼사드 패턴은 인터페이스를 단순화시키기 위해서 사용된다.

어떤 작업을 하기 위해서 다수의 인터페이스로 구성된 서브시스템을 사용해야 할 때, 그 서브시스템을 사용하기 쉽게 포괄적인 인터페이스를 정의하는 패턴이다.

여기서 말하는 서브시스템은 실제 구현에서는 표현되지 않았을 수 있고, 전체 시스템 중의 일부분을 묶어서 서브시스템이라고 표현하는 것이다.

UML만으로 설명하면 더 헷갈릴 수 있을 것 같아서 바로 예제로 넘어가도록 하겠다.

2. 예제

Head First Desgin Pattern에 나오는 예제를 수정한 것이다.

한참동안 준비하여 DVD 플레이어, 프로젝터, 자동 스크린, 앰프 오디오, 팝콘기계, 라디오 등을 집에 배치했다.

이를 클래스 다이어그램을 표현하면 다음과 같다.

이제 이 장비들을 이용해 영화를 보고자 한다.

영화를 보려면 몇 가지 일들을 해야한다.

1. 팝콘 기계를 켠다.

2. 팝콘를 튀긴다

3. 프로젝터를 켠다.

4. 프로젝터에 DVD 신호가 입력되게 연결한다.

5. 프로젝터를 와이드 스크린 모드로 전환한다.

6. 앰프 오디오를 켠다.

7. 앰프를 서라운드 음향 모드로 전환한다.

8. 앰프 볼륨을 중간(5)로 설정한다.

9. DVD 플레이어를 켠다.

10. DVD를 재생한다.

이 작업을 하기 위해서 필요한 코드를 보자.

	popcornPopper->on();
	popcornPopper->pop();
	projector->on();
	projector->wideScreenMode();
	amplifier->on();
	amplifier->setDvd(this->dvdPlayer);
	amplifier->setSurroundSound();
	amplifier->setVolume(5);
	dvdPlayer->on();

굉장히 복잡하다.

여기서 끝이 아니라 영화가 끝나고 나면 모든 장비들을 특정 순서대로 꺼야하고, 라디오를 들을 때도 복잡한 과정을 거쳐야한다.

퍼사드 패턴을 적용하면 클라이언트 측에서는 이런 복잡한 과정들을 거치지 않아도 된다.

퍼사드 패턴을 적용하면 어떻게 되는지 보자.

HomeTheaterFacade 클래스가 추가되었다.

이제 영화를 보고, 영화 보기를 끝내는 일련의 작업은 HomeTheaterFacade 클래스에서 처리하고, 클라이언트들은 이 클래스 객체에 대한 레퍼런스를 얻어 watchMoive(), endMovie() 메소드를 호출하면 된다.

watchMoive() 메소드와 endMovie() 메소드는 다음과 같이 구현된다.

//HomeTheaterFacade.cpp

void HomeTheaterFacade::watchMovie()
{
	cout << "영화보기 모드 실행" << endl;
	this->popcornPopper->on();
	this->popcornPopper->pop();
	this->projector->on();
	this->projector->wideScreenMode();
	this->amplifier->on();
	this->amplifier->setDvd(this->dvdPlayer);
	this->amplifier->setSurroundSound();
	this->amplifier->setVolume(5);
	this->dvdPlayer->on();
	this->dvdPlayer->off();
}

void HomeTheaterFacade::endMovie()
{
	cout << "영화 끄기" << endl;
	this->popcornPopper->off();
	this->screen->up();
	this->projector->off();
	this->amplifier->off();
	this->dvdPlayer->stop();
	this->dvdPlayer->eject();
	this->dvdPlayer->off();
}

3. 퍼사드 패턴의 장점

퍼사드 패턴을 이용하면 복잡한 서브시스템을 하나의 인터페이스로 묶을 수 있다.

클라이언트의 구현과 서브시스템이 분리되기 때문에 서브시스템의 구현에 변화가 생겨도 클라이언트 코드는 수정하지 않아도 된다.

퍼사드 클래스로 간단하게 원하는 작업을 수행 할 수 있고, 퍼사드 패턴을 무시하고 서브시스템을 구성하는 클래스들을 그대로 사용 할 수도 있다.

퍼사드 클래스를 적용해도 원래의 시스템에서 아무런 제약이 추가되지 않는 것이다.

4. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- GoF의 디자인 패턴(Pearson Addison Wesley)

본 포스팅은 개인적인 공부를 위해 책의 내용을 요약하여 정리하는 글입니다.

작성자는 분산 데이터베이스, 하둡에 대해서 처음 공부해보는 것이니 참고가 된다면 기쁘겠지만 틀린 정보가 있을 수 있습니다.

사전 지식

- 맵 리듀스(Map Reduce) : 대용량 데이터 처리를 분산 병렬 컴퓨팅에서 처리하기 위해서 제작한 프레임워크

1. Data!

IDC의 예측에 따르면 "디지털 세상"은 4.4 제타바이트에 달한다.(1제타파비트 = 1억테라바이트).

현재는 데이터시데이며 IoT로 인해 생성되는 데이터는 더욱 많아질 것이다.

일부 분야에서는 알고리즘의 퀄리티 보다는 테이터의 양이 더 중요하다.

이런 상황에서 대용량의 데이터를 관리하고, 처리하는 방법에 대한 개발이 매우 중요해졌다.

2. Data Storage and Analysis

기술 발전으로 인해 하드 디스크 등 저장장치의 용량(capacity)은 매년 매우 커지는 중이지만, 드라이브에서 데이터를 읽고 쓰는 접근 속도(access rate)는 크게 발전하지 못하고 있다.

접근 속도를 높이는 방법으로 여러개의 디스크에 데이터를 나눠서 저장해두고 한번에 병렬적으로 읽는 방법이 있다.

다수의 디스크에 병렬적으로 데이터를 저장하는 것의 문제점(어려움)

하드디스크 1개에 데이터를 저장할 때 하드디스크가 고장날 확률보다 하드디스크 100개에 데이터를 저장할 때 고장나는 하드디스크가 생길 확률이 더 높다. 장치가 하나라도 고장나면 데이터 전체를 쓸 수없게 될 수도 있는데, 이 문제는 하나의 데이터를 여러 디스크에 중복(replication)되게 저장하여 어느정도 해결 할 수 있다.

그리고 여러 디스크에 분산 저장된 데이터를 하나로 모으는 작업은 매우 어렵다. 맵 리듀스를 사용하면 디스크 읽고 쓰기의 문제를 키값과 value값에 대한 계산문제로 문제를 추상화기 때문에 이러한 어려움이 해결된다.

3. Querying All Your Data

맵 리듀스는 일괄 쿼리 프로세서(batch query processor)이기 때문에 전체 데이터 집합에 대해 비정형 쿼리(ad hoc query)를 보내는 능력과 그 결과를 빠르게 가져오는 능력이 있다.

하지만 반응형 분석에는 부적합하다.

4. Beyond Batch(일괄처리를 넘어서)

맵 리듀스는 일괄처리 시스템이라서 반응형 분석에는 부적합하다. 

하지만 하둡은 반응형 SQL, 반응형 프로세싱, 스트림 프로세싱, 검색 기능과도 잘 동작한다. 맵 리듀스를 활용하여 개발되었지만, 하둡은 일괄처리 프로세싱의 한계를 뛰어넘은 것이다.

YARN의 등장으로 하둡은 일괄처리 프로세싱 모델 이외에 다른 프로세싱 모델들을 적용할 수 있다.

*YARN : 어떤 분산처리 프로그램이라도 하둡 클러스터의 데이터로 실행가능하게 만드는 클러스터 리소스 관리 프로그램

5. Comparison with Other Systems(다른 시스템과의 비교)

5.1 Relational Database Management Systems(RDBMS)

* schema on read : 데이터의 스키마를 데이터를 읽는 시점에 확인한다.(schema on write는 반대로 쓰는 시점에 확인)

(참조 : http://datacookbook.kr/90)

맵 리듀스 데이터 병렬 처리

맵 리듀스는 데이터를 분할해 병렬적으로 처리하는 것이 가능하다.

Unstructured/Semi-Structured Data

비정형 데이터(Unstructured Data)는 미리 정의된 방식으로 정리되지 않은 데이터, 반정형 데이터(Semi-Structured Data)는 정형구조를 준수하지 않는 정형 데이터를 말한다.

RDBMS는 미리 정의된 형식을 따르는 정형 데이터(Structured)만 처리 할 수 있지만, 하둡은 Scheam-on-read, 즉 데이터를 읽는 시점에 데이터의 스키마를 확인하기 때문에 비정형 데이터, 반정형 데이터도 처리 할 수 있다.

따라서 유연성이 높다고 할 수 있고, RDBMS에서의 데이터 로딩 단계가 필요하지 않다.

Normalization 

관계형 데이터는 무결성(Integrity) 유지와 중복제거를 위해 자주 정규화(normalization)된다.

하둡에서 정규화를 적용하면 특정 레코드를 읽는 작업이 local opeartion이 아닌 non-local opeartion이 되어 문제가 발생 할 수 있다.

그리고 하둡은 빠른 속도로 스트리밍 읽기/쓰기를 수행할 수 있어야 하기 때문에 그 점도 정규화 적용 시 문제가 된다.

로그 파일이 정규화 되지 않은 대표적인 예시이다. (로그파일이 정규화되지 않는 예시로, 로그파일에는 고객의 이름이 여러 로그에 중복되어 나타나는 경우가 많다.) 그래서 로그파일 분석에는 하둡이 적합하다.

풀리지 않은 의문점

5.1에서 하둡에는 RDBMS에서의 데이터 로딩 단계가 필요하지 않은 이유

레퍼런스

Schema-on-read의 이해 - http://datacookbook.kr/90

비정형 데이터 

- https://ko.wikipedia.org/wiki/%EB%B9%84%EC%A0%95%ED%98%95_%EB%8D%B0%EC%9D%B4%ED%84%B0

반정형 데이터 

- https://ko.wikipedia.org/wiki/%EB%B0%98%EC%A0%95%ED%98%95_%EB%8D%B0%EC%9D%B4%ED%84%B0

1. 어댑터 패턴이란

1.1 어댑터 패턴의 정의

어댑터 패턴은 클라이언트가 요구하는 인터페이스와 호환되지 않는 인터페이스를 가져서 함께 동작 할 수 없는 클래스를 함께 동작 할 수 있게 해준다.

그리고 어댑터패턴은 오브젝트 어댑터(Object Adapter)와 클래스 어댑터(Class Adapter)로 구현방법이 나뉘어지는데,  클래스 어댑터가 가지는 몇 가지 단점 때문에 이 글에서는 오브젝트 어댑터를 주로 다루려고 한다.

1.2 어댑터 패턴에 대한 대략적 이해

A라는 클래스를 B라는 클래스와 함께 동작하게 하고 싶지만,  B 클래스와 함께 동작하려면 C 인터페이스 형태를 따르도록 구현되어야 한다.

하지만 기존 코드를 수정하는 것(A 클래스가 C 인터페이스를 상속하도록 수정하거나 B 클래스가 A 클래스와 함께 동작할 수 있도록 수정하는 것)은 비효율적이고 오류를 일으키는 원인이 되는 일이므로 A 클래스를 C 인터페이스에 맞게 변환해주는 Adapter를 중간에 추가하여 문제를 해결한다.

그러면 A 클래스가 B 클래스와 함께 동작 할 수 있다.

1.3 오브젝트 어댑터(Object Adapter)

오브젝트 어댑터는 구성(Composition)을 사용하여 어댑터 패턴을 구현한다. UML과 같이 보도록 하자.

Client - Target 인터페이스를 요구하는 요소를 지닌 클래스

Target - 어떤 인터페이스

Adaptee - Client의 Target 인터페이스를 요구하는 요소에 집어넣고 싶은 클래스. Target 인터페이스에 호환되지 않음.

Adapter - Adaptee 클래스를 Target 인터페이스에 맞춰주는 클래스

여기서 Adapter는 Target 인터페이스의 request() 메소드를 구현 하기 위해 Adaptee 클래스의 method1() 메소드를 사용 할 것이다.

그러면 Client는 Adapter 클래스를 통해 Adaptee를 Target 인터페이스의 구상 클래스처럼 사용할 수 있다.

1.4 클래스 어댑터(Class Adapter)

클래스 어댑터는 상속(Inheritance)를 사용하여 어댑터 패턴을 구현한다. 이것도 UML과 같이 보도록 하자.

Client - Target 인터페이스를 요구하는 요소를 지닌 클래스

Target - 어떤 인터페이스

Adaptee - Client의 Target 인터페이스를 요구하는 요소에 집어넣고 싶은 클래스. Target 인터페이스에 호환되지 않음.

Adapter - Adaptee 클래스를 Target 인터페이스에 맞춰주는 클래스

클래스 어댑터는 다중 상속을 사용한다.

클래스 어댑터 패턴에서는 Adapter가 Target 클래스와 Adaptee 클래스를 둘 다 상속하여 Target 클래스가 필요한 곳에서도 사용 될 수 있고 Adaptee 클래스가 필요한 곳에서도 사용 될 수  있게 한다.

2. 예제

게임을 개발했다고 생각 해 보자.

개발하려는 게임은 정말 간단해서, 몬스터와 액티브 아이템, 그리고 UI로만 구성된다.

몬스터와 액티브아이템, UI는 각각 다른 인터페이스로 구현된다.

개발 초기에 클래스 다이어그램은 다음과 같을 것이다.

유저 인터페이스 클래스에서는 setActiveItem() 메소드로 사용할 액티브아이템을 결정하고, useItem() 메소드를 실행하면 ActiveItem 인터페이스의 useItem() 메소드를 이용하여 액티브아이템의 효과를 사용한다.

몬스터는 grawl() 메소드를 사용하면 울부짖는 소리를 낸다. 울부짖을때는 grawlSound 어트리뷰트에 저장된 소리로 울부짖는다.

그런데 게임 기획자가 새로운 아이디어를 떠올렸다. 유저가 몬스터를 포획하여 액티브아이템처럼 몬스터를 사용할 수 있게 하자는 것이다.

몬스터를 포획하면 몬스터가 액티브아이템으로 등록되고, 이 아이템을 사용하면 유저에게 몬스터가 울부짖는 소리를 들려준다.

이를 구현하고자 할 때 문제는 유저 몬스터 클래스는 유저 인터페이스의 setActiveItem() 메소드에 호환되지 않는다는 것이다.

위에서 언급했듯이, UserInterface에 setItem(Monster) 메소드를 추가하거나, Monster 인터페이스가 ActiveItem 인터페이스를 상속하게 하는 등 기존 코드를 수정하는 것은 좋은 선택이 아니다.

각각의 몬스터별로 새로운 아이템 클래스를 만드는 것도 좋은 방법이지만 그러면 몬스터의 숫자만큼 클래스의 수가 늘어나게 되기 때문에 더 좋은 방법이 있었으면 한다.

더 좋은 방법으로서 어댑터 패턴을 적용해보자.

몬스터를 액티브아이템처럼 사용될 수 있도록 적절한 어댑터를 만들어 클래스 구조를 다음과 같이 만든다.

MonsterToActiveItemAdapter가 바로 Monster 인터페이스를 ActiveItem 인터페이스처럼 사용 될 수 있게 해주는 클래스다.

MonsterToActiveItemAdapter 클래스의 useItem() 메소드는 Monster 인터페이스의 grawl() 메소드를 호출하도록 구현된다.

그래서 붙잡은 몬스터를 액티브아이템 처럼 사용 할 수 있다.

구현된 프로젝트는 다음의 깃허브 페이지에서 확인 할 수 있다.

(https://github.com/InvincibleTyphoon/AdapterPatternExample/tree/master)

3. 어댑터 패턴의 장점

인터페이스가 호환되지 않는 문제가 발생해도 어댑터 패턴을 적용하면 기존의 코드를 수정하지 않고도 문제를 해결 할 수 있다.

Class Adapter에는 적용되지 않는 장점이지만, 상속이 아닌 구성을 사용하기 때문에 Adaptee의 모든 서브클래스에 대해 어댑터를 적용 할 수 있고, 실행중에 동적으로 Adaptee를 바꿀수도 있다.

4. 오브젝트 어댑터 VS 클래스 어댑터

위의 예제에서는 오브젝트 어댑터를 적용했다.

오브젝트 어댑터와 클래스 어댑터를 비교했을 때, 서로다른 장단점이 있는데 우선 그 차이점을 비교해보자.

Object Adapter는 상속이 아닌 구성을 사용하기 때문에 더 유연하다. 하지만 Adaptee 객체를 만들어야하기 때문에 Class Adapter에 비해 관리해야할 객체가 하나 늘어난다는 단점이 있다.

Class Adapter는 Adapter가 Adaptee의 서브클래스이기 때문에 Adaptee의 행동을 오버라이드하여 사용 할 수 있고. Adaptee 객체를 따로 만들지 않고 Adapter 객체를 만들어서 사용가능하다는 장점이 있다. 관리해야 할 객체가 하나 적다는 것이다.

하지만 Class Adapter는 상속을 사용하기 때문에 한 Adapter 클래스가 특정 Adaptee 클래스 하나에 대해서만 적용된다. 그 Adaptee클래스의 서브클래스에 대해서 적용 불가능하고, 실행 중간에 동적으로 변경도 불가능한 것이다.

그리고 이것은 치명적인 단점이라고 할 수 있는데, 자바처럼 다중상속이 지원되지 않는 언어에서는 사용이 불가능하다.

개인적인 견해로 말하자면 유연성 측면에서 Object Adapter의 장점이 Class Adapter의 장점보다 낫고, Object Adapter의 단점은 그다지 치명적이거나 하지 않다고 본다.

상황에 따라서 어떤 방법을 쓸 지 선택애햐겠지만, 이 두가지 방법 중 한가지를 선택해야하는 상황이라면 나는 Object Adapter를 사용할 것 같다.

Head First Design pattern에서 클래스 어댑터는 객체어댑터에 비해 Adaptee 전체를 다시 구현하지 않아도 된다는 장점을 가진다고 하는데, 이에 대해 객체 어댑터도 Adaptee에게 필요한 일을 시키는 코드만 구현하면 된다고 답하는 내용이 있는 걸로 봐서, 클래스 어댑터 패턴이 Adaptee에게 일을 시키는 코드를 구현하지 않다도 되는게 장점이라는 의미로 그렇게 언급하는 것 같다.

5. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- 위키피디아 Adapter Pattern(https://en.wikipedia.org/wiki/Adapter_pattern)

1. 커맨드 패턴이란

1.1 커맨드 패턴의 정의

이 정의에서 핵심은 요청을 캡슐화한다는 점이다.

요청이 캡슐화되기 떄문에 로그를 출력하거나 실행을 취소할 때 유용하게 사용 될 수 있다.

1.2 UML

위 다이어그램에서 클라이언트가 리시버와 커맨드 객체를 생산하고, 커맨드를 보낼 때는 인보커를 통해서 보내게 된다.

2. 적용 예제

Head First Desgin Pattern에 나오는 예제를 수정한 것이다.

주식회사 홈 오토메이션에서는 가정집의 전등, 차고문, 오디오, 선풍기 등을 조종할 수 있는 만능 리모컨을 개발하려고 한다.

만능 리모컨은 전자기기와 연결 할 수 있는 7개의 슬롯과 그 각각을 켜고 끄는 버튼, 그리고 하나의 취소버튼을 가진다.

그런데 문제는 전자기기들의 작동 방식이 서로 다르다는 것이다.

각 전자기기들을 클래스화한 클래스 다이어그램을 보면서 이야기 하도록 하겠다.

켜기/끄기 버튼만을 가진 리모컨으로 조종하기엔 작동 방식이 너무 제각각이다. 전등(Light)의 경우는 켜고 끄는게 다지만, 오디오(Stereo)는 작동시키기 위해 setCD() 메소드로 CD명을 입력하고, setVolume() 메소드로 볼륨도 조절해줘야하고, 선풍기는 high(), medium(), low() 메소드로 속도를 조절해야한다.

리모컨의 몇번 슬롯에 어느 전자기기가 연결될 지 알 수 없기 때문에 버튼이 눌렸을 때 if-else 문으로 슬롯과 연결된 클래스의 타입을 검사하여 실행하도록 구현되어야 할 것이다.

하지만 그렇게 구현하면 새로운 클래스가 추가될 때마다 리모컨에 있는 코드를 고쳐야 되고, 이는 버그 발생률을 높이는 원인이 된다.

이런 문제를 해결하기 위해 커맨드 패턴을 적용해보도록 하자.

2.1 커멘드 인터페이스 및 구상 클래스 정의

커맨드 패턴 적용을 위해 Command 인터페이스를 만들고 모든 커맨드 클래스들이 이 인터페이스를 구현하도록 한다.

Command 인터페이스는 다음과 같이 리시버에세 요청을 실행하라고 전달하는 execute() 메소드와 실행을 취소하라고 전달하는 undo() 메소드를 가진다.

이제 리모컨 클래스는 이 Command 인터페이스를 이용하여 execute(), undo()메소드가 어떻게 구현되었는지는 신경쓰지 않도록 구현한다.

LightOnCommand

//LightOnCommand.h
#pragma once
#include "Command.h"
#include "../HomeObejcets/Light.h"


//불 켜기 커맨드
//light의 name 어트리뷰트를 통해 어느 곳에 있는 전등인지 구별함
class LightOnCommand : public Command
{
public:
	LightOnCommand(Light* light);
	void execute();
	void undo();
private:
	Light * light = NULL;
};

//LightOnCommand.cpp
#include "LightOnCommand.h"

LightOnCommand::LightOnCommand(Light* light)
{
	this->light = light;
}

void LightOnCommand::execute()
{
	light->lightOn();
}

void LightOnCommand::undo()
{
	light->lightOff();
}

StereoOnCommand

//StereoOnCommand.h
#pragma once
#include "Command.h"
#include "../HomeObejcets/Stereo.h"

//노래 켜기 커맨드
class StereoOnCommand : public Command
{
public:
	StereoOnCommand(Stereo * stereo);
	void execute();
	void undo();
private:
	Stereo * stereo = NULL;
};

//StereoOnCommand.cpp
#include "StereoOnCommand.h"

StereoOnCommand::StereoOnCommand(Stereo * stereo)
{
	this->stereo = stereo;
}


void StereoOnCommand::execute()
{
	this->stereo->setCD(*new string("Sonyun Jump"));
	this->stereo->setVolume(13);
	this->stereo->stereoOn();
}

void StereoOnCommand::undo()
{
	this->stereo->stereoOff();
}

참고로 StereoOnCommand의 execute() 메소드에서 설정하는 CD와 볼륨 값은 임의로 넣은 값이다. 사용자 편의를 고려해서 커스텀하면 된다.

2.3.1 매크로 커맨드 구현

커맨드들 중 간혹 다수의 커맨드를 연속으로 수행해야하는 경우가 있다.

이런 커맨드를 매크로 커맨드라고 부르는데, 매크로 커맨드는 Command 인터페이스에 대한 레퍼런스를 리스트로 가지고, 그 각각의 excute() 메소드를 호출하는 것으로 execute() 메소드가 구현된다.

//MacroCommand.h
#pragma once
#include <vector>
#include <algorithm>
#include "Command.h"

using namespace std;

//다수의 커맨드를 실행하는 커맨드
class MacroCommand : public Command
{
public:
	MacroCommand(vector<Command*>& commands);
	void execute();
	void undo();
private:
	vector<Command*> commands;
};

//MacroCommand.cpp
#include "MacroCommand.h"

MacroCommand::MacroCommand(vector<Command*>& commands)
{
	this->commands = commands;
	//copy(commands.begin(), commands.end(), this->commands);
}

void MacroCommand::execute()
{
	int size = this->commands.size();
	for (int i = 0; i < size; i++)
		commands[i]->execute();
}

void MacroCommand::undo()
{
	int size = this->commands.size();
	for (int i = 0; i < size; i++)
		commands[i]->undo();
}

우리 프로젝트에서는 PartyMode이라는 커맨드를 지원한다. PartyMode는 파티를 위해서 모든 문을 열고, 모든 전등을 켜고, 오디오를 켜는 커맨드로, 매크로 커맨드 클래스로 정의된다.

//main.cpp
vector<Command*> partyOn = { kitchenLightOnCommand,bedroomLightOnCommand,garageDoorOpenCommand,stereoOnCommand };
vector<Command*> partyOff = { kitchenLightOffCommand,bedroomLightOffCommand,garageDoorCloseCommand,stereoOffCommand};
Command * partyOnCommand = new MacroCommand(partyOn);
Command * partyOffCommand = new MacroCommand(partyOff);

2.2 Invoker 역할의 RemoteController 정의

이제 위의 Command 인터페이스를 구현한 LightOnCommand, StereoOnCommand 클래스 코드를 예시로 어떻게 구현되는지 보도록 하자.

onCommands, offCommands는 각각 슬롯에 연결된 전자기기를 켜고 끄는 커맨드 클래스들을 저장한다.

각 슬롯에 커맨드를 할당하기 위해서 setCommand() 메소드로 i번 슬롯에 onCommand와 offCommand를 동시에 입력한다.

각 슬롯에 할당된 on/off 버튼을 누르기 위해서는 on/offButtonWasPushed() 메소드를 이용한다.

그리고 실행 취소를 위해서 unDoButtonWasPushed() 메소드를 사용한다.

다음은 구현된 RemoteController 클래스의 구현 코드다.

//RemoteController.h
#pragma once
#include <vector>
#include <stack>
#include <iostream>
#include "Commands/Command.h"
#include "Commands/NoCommand.h"

using namespace std;

//여러 커맨드를 묶어서 리모컨처럼 사용하는 클래스
class RemoteController
{
public:
	RemoteController();
	void setCommand(int slot, Command* onCommand, Command* offCommand);
	void onButtonClicked(int slot);
	void offButtonClicked(int slot);
	void undoButtonClicked();

private:
	//켜기 커맨드를 모은 벡터
	vector<Command*> onCommands;

	//끄기 커맨드를 모은 벡터
	vector<Command*> offCommands;

	//커맨드 실행 기록
	stack<Command*> commandStack;	
};

//RemoteController.cpp
#include "RemoteController.h"

RemoteController::RemoteController()
{
	this->offCommands.resize(7);
	this->onCommands.resize(7);

	Command * noCommand = new NoCommand();
	for (int i = 0; i < 7; i++)
	{
		this->offCommands[i] = noCommand;
		this->onCommands[i] = noCommand;
	}
}

void RemoteController::setCommand(int slot, Command* onCommand, Command* offCommand)
{
	this->onCommands[slot] = onCommand;
	this->offCommands[slot] = offCommand;
}

void RemoteController::onButtonClicked(int slot)
{
	this->onCommands[slot]->execute();
	this->commandStack.push(onCommands[slot]);
}

void RemoteController::offButtonClicked(int slot)
{
	this->offCommands[slot]->execute();
	this->commandStack.push(offCommands[slot]);
}

void RemoteController::undoButtonClicked()
{
	if (commandStack.empty())
	{
		cout << "Remote Controller Undo Caution : no command history" << endl;
		return;
	}
	cout << "undo : ";
	commandStack.top()->undo();
	commandStack.pop();
	cout << endl;
}

생성자에서 NoCommand 라는 클래스를 이용하는데, 이는 Command 인터페이스를 구현한, 아무런 기능을 하지 않는 클래스다.

슬롯이 비어있을 경우 if문을 이용하여 NULL인지 체크하는 것보다 일종의 NULL 객체인 NoCommand를 넣어 아무런 기능도 하지 않도록 구현했다.

이제 필요한 클래스들은 모두 구현되었다.

구현된 구조를 1.2절의 UML과 연관지어보면 다음과 같다.

이 시스템에서 클라이언트는 따로 클래스화 할 필요가 없어보여서 main() 함수가 클라이언트의 역할을 하도록 했다.

LightOnCommand, LightOffCommand는 Command 인터페이스를 구현한 구상 클래스다. 이 두 클래스를 이용해 전등을 켜고 끈다.

RemoteController는 Invoker의 역할이다. 7개의 슬롯에 각각의 커맨드를 할당하고 슬롯 번호로 사용한다.

이제 리모컨의 켜기/끄기 기능은 구현이 완료되었으니 undo 버튼 구현을 위한 내용들을 살펴보도록 하자.

2.3 UnDo 구현

UnDo 버튼은 직전에 실행했던 기능을 취소하는 기능이다.

우선 각 커맨드 구상 클래스에서 Undo 기능이 어떻게 구현되는지 살펴보겠다.

2.3.1 LightOn/OffCommand 클래스의 UnDo 구현

첫 번째는 가장 간단한 LightOnCommand 클래스다.

//LightOnCommand.cpp

void LightOnCommand::undo()
{
	light->lightOff();
}

LightOnCommand는 불을 켜는 커맨드이기 때문에 불을 꺼주는 것으로 Undo 기능이 구현된다.

LightOffCommand는 반대로 불을 켜주는 것으로 Undo 기능을 구현하면 된다.

//LightOffCommand.cpp

void LightOffCommand::undo()
{
	light->lightOn();
}

2.3.2 State와 Stack 이용한 FanSpeedChangeCommand, FanOffCommand 클래스의 Undo 구현

작업취소 기능을 구현할 때는 상태(State)를 저장해야하는 경우가 종종 있다.

선풍기의 경우도 그런데, Fan 클래스의 코드를 보면서 이야기해보도록 하겠다.

//Fan.h
#pragma once
#include <string>
#include <stack>
#include <iostream>

using namespace std;

//선풍기 클래스
//꺼짐, 느린속도, 중간속도, 빠른속도의 상태를 가짐
class Fan
{
public:
	enum FanStatus { Off, LowSpeed, MediumSpeed, HighSpeed };
public:
	Fan();

	/*********선풍기 속도 조절 메소드********/
	void high();
	void medium();
	void low();
	void off();	
	////////////////////////////////////////

	//선풍기의 속도를 받아옴
	FanStatus getSpeed();
	string toString();
private:
	//현재 선풍기의 상태
	FanStatus fanStatus;
};

Fan은 Off(꺼짐), LowSpeed(느리게), MediumSpeed(중간속도), HighSpeed(빠르게) 의 상태를 갖는다.

이제 커맨드 클래스에서 작업 취소 기능을 구현하는 방법을 살펴보자. 작업 취소 기능을 구현하려면 커맨드가 실행되기 이전 상태를 알아야 한다.

그러기 위해 커맨드 클래스에 Fan::FanStatus prevStatus; 필드를 추가하면 될 것 같지만, 이렇게 하면 작업 취소를 여러 번 수행 할 수 없다. 

Undo버튼을 여러번 눌렀을 때 처리 할 수가 없다는 것이다.

이 문제를 해결하기 위해 스택을 활용한다.

//FanSpeedChangeCommand.h
#pragma once
#include <stack>
#include "Command.h"
#include "../HomeObejcets/Fan.h"

//선풍기 속도 조절 커맨드
//execute 시 꺼짐->느림->보통->빠름->느림->보통... 순으로 변경됨
class FanSpeedChangeCommand : public Command
{
public:
	FanSpeedChangeCommand(Fan * fan);
	void execute();
	void undo();
private:
	Fan * fan = NULL;
	stack<Fan::FanStatus> fanStatusHistory;
};

스택을 활용하면 커맨드가 실행되기 이전 상태가 쌓이고, 작업 취소를 수행 할 때 이 스택에서 상태를 pop 하여 작업 취소에 이용하면 된다.

이제 이 스택을 활용해서 작업 취소가 어떻게 구현되는지 살펴보자.

//FanSpeedChangeCommand.cpp

void FanSpeedChangeCommand::undo()
{
	if (fanStatusHistory.empty())
	{
		cout << "FanSpeedChangeCommand undo caution : no previous Ssatus exists" << endl;
		return;
	}

	Fan::FanStatus prev = fanStatusHistory.top();
	fanStatusHistory.pop();

	cout << "fan undo : (" << fan->getSpeed() << ") -> (" << prev << ")" << endl;

	switch (prev)
	{
	case Fan::Off:
		fan->off();
		break;
	case Fan::LowSpeed:
		fan->low();
		break;
	case Fan::MediumSpeed:
		fan->medium();
		break;
	case Fan::HighSpeed:
		fan->high();
		break;
	default:
		break;
	}
}

FanOffCommand 클래스의 Undo 기능도 거의 유사하게 구현된다.

는지 살펴보자.

//FanOffCommand.cpp

void FanOffCommand::undo()
{
	if (fanStatusHistory.empty())
	{
		cout << "FanOffCommand undo caution : no previous Ssatus exists" << endl;
		return;
	}

	Fan::FanStatus prev = fanStatusHistory.top();
	fanStatusHistory.pop();

	cout << "fan undo : (" << fan->getSpeed() << ") -> (" << prev << ")" << endl;
	
	switch (prev)
	{
	case Fan::Off:
		fan->off();
		break;
	case Fan::LowSpeed:
		fan->low();
		break;
	case Fan::MediumSpeed:
		fan->medium();
		break;
	case Fan::HighSpeed:
		fan->high();
		break;
	default:
		break;
	}
}

2.3.3 Stack을 이용한 RemoteController의 Undo버튼 기능 구현

지금까지 각 커맨드 클래스에서 작업 취소 기능을 구현하는 방법을 살펴보았다.

이제는 RemoteController 클래스에서 실제로 Undo 버튼을 클릭했을 때 어떻게 처리되는지 살펴볼 차례다.

RemoteController에서는 Undo 버튼을 여러번 클릭했을 때 작업 취소가 연속적으로 실행되어야 한다.

이는 앞에서 살펴본 선풍기 관련 커맨드의 실행취소 기능의 구현과 유사해서 다시 스택을 이용해서 구현된다.

RemoteController 클래스의 정의는 위에서 기술되었으니 undoButtonClicked() 메소드만 살펴보자.

//RemoteController.cpp

void RemoteController::undoButtonClicked()
{
	if (commandStack.empty())
	{
		cout << "Remote Controller Undo Caution : no command history" << endl;
		return;
	}
	cout << "undo : ";
	commandStack.top()->undo();
	commandStack.pop();
	cout << endl;
}

commandStack은 stack<Command*>로 선언되었다.

구현된 프로젝트는 다음의 깃허브 페이지에서 확인할 수 있다.

(https://github.com/InvincibleTyphoon/CommandPatternExample/tree/master)

3. 커맨드 패턴의 장점

요구사항이 캡슐화되므로 요청을 보내는 내용의 코드 중복을 방지 할 수 있다.

작업 취소 기능을 지원하는 것은 앞서 살펴 본 바 있으니 넘어간다.

요청 내역을 큐에 저장하면 스레드 작업에 유용하다.

처리되는데 오래 걸리는 요청의 경우 스레드를 만들어 백그라운드에서 처리하는 것이 반응성을 높이는데 유용하다.

작업 큐에 다수의 커맨드 객체를 저장해두고 스레드를 여러개 만들면 각 스레드는 작업 큐에서 커맨드를 가져와 처리하면 된다. 그러면 어느 스레드가 먼저 작업을 마치든지 신경쓰지 않아도 된다.

어떤 어플리케이션에서는 모든 행동을 기록해놨다가 그 어플리케이션이 다운되었을 경우, 나중에 그 행동들을 다시 호출해서 복구 할 수 있도록 해야한다.

커맨드패턴에서는 로그를 디스크에 저장하는 store() 메소드와 로그를 읽어오는 load() 메소드를 추가하여 복구 기능을 구현 할 수 있다.

4. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- GoF의 디자인 패턴(Pearson Addison Wesley)

카라츠바의 빠른 곱셈

카라츠바의 빠른 곱셈 알고리즘은 수백, 수만자리나 되는 큰 두개의 정수를 곱하는 알고리즘이다.

필요성

카라츠바 알고리즘을 소개하기에 앞서, 두자릿수 이상의 두 수를 곱하는 과정은 다음과 같다.

이를 코드로 구현하면 다음과 같이 구현 할 수 있다.

//num[]의 자릿수를 올림을 처리한다.
void normalize(vector<int>& num) 
{
	num.push_back(0);

	//자릿수 올림을 처리한다.
	int size = num.size();
	for (int i = 0; i < size - 1; i++)
	{
		if (num[i] < 0)
		{
			int borrow = (abs(num[i]) + 9) / 10;
			num[i + 1] -= borrow;
			num[i] += borrow * 10;
		}
		else
		{
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
	}
	//앞에 남은 0을 제거한다.
	while (num.size() > 1 && num.back() == 0)
		num.pop_back();
}

//초등학교식 정수 곱셈
vector<int> multiply(const vector<int>& a, const vector<int>& b)
{
	vector<int> c(a.size() + b.size() + 1, 0);

	int aSize = a.size();
	int bSize = b.size();

	for (int i = 0; i < aSize; i++)
		for (int j = 0; j < bSize; j++)
			c[i + j] += a[i] * b[j];
	normalize(c);
	return c;
}

이 알고리즘의 시간복잡도는 두 정수의 길이가 모두 n이라고 할 때 O(n^2)이다. 2중 for문을 이용하고 있으니 이 점을 이해하기는 어렵지 않을 것이다.

카라츠바 알고리즘은 이 시간복잡도를 O(n^log(3)) 까지 낮춰주기 위해 사용된다.

log(3) = 1.585...이므로 O(n^2) 보다 훨씬 적은 곱셈을 필요로 한다.

만약 n이 10만이라고 하면 곱셈 횟수는 대략 100배 정도 차이가 난다.

아이디어

카라츠바 알고리즘이 어떻게 진행되는지 설명하기에 앞서 카라츠바 알고리즘이 시간복잡도를 O(log(3))으로 낮추기 위해 사용한 아이디어에 대해 설명하고자 한다.

자릿수가 n인 두개의 수 a,b를 단순히 곱하기 위해서는 O(n^2)이 소요되지만, 덧셈과 뺄셈을 하는데에는 O(n)시간만에 해결 할 수 있다.

카라츠바 알고리즘은 곱셈의 횟수를 줄이고, 덧셈과 뺄셈 횟수를 늘리는 방식으로 구현된다.

과정

이제 카라츠바 알고리즘이 어떻게 진행되는지 보도록 하자.

카라츠바 알고리즘은 곱하는 256자리의 두 정수 a,b를 다음과 같이 나눈다.

a1,b1은 각각 a,b의 첫 128자리, a0,b0는 각각 a,b의 뒷 128자리를 나타낸다.

이제 a * b의 계산 과정은 다음과 같이 나눌 수 있다.

이 상태에서는 n/2 크기의 두 정수의 곱셈이 총 4번 사용된다. 이 곱셈 횟수를 줄이기 위해 다음 수식을 이용한다.

이 수식을 수정하면 다음의 결과를 얻을 수 있다.

z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;

이렇게 수정하고 나면 a*b는 n/2 크기의 두 정수의 곱셈 3번, 덧셈 2번, 뺄셈 2번으로 수행 할 수 있다.

이를 재귀적으로 처리하여 a1*b1, a0*b0에 대해서도 적용하면 곱셈 결과를 얻을 수 있다.

구현

다음은 카라츠바 알고리즘을 구현한 코드다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//num[]의 자릿수를 올림을 처리한다.
void normalize(vector<int>& num) 
{
	num.push_back(0);

	//자릿수 올림을 처리한다.
	int size = num.size();
	for (int i = 0; i < size - 1; i++)
	{
		if (num[i] < 0)
		{
			int borrow = (abs(num[i]) + 9) / 10;
			num[i + 1] -= borrow;
			num[i] += borrow * 10;
		}
		else
		{
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
	}
	//앞에 남은 0을 제거한다.
	while (num.size() > 1 && num.back() == 0)
		num.pop_back();
}

//초등학교식 정수 곱셈
vector<int> multiply(const vector<int>& a, const vector<int>& b)
{
	vector<int> c(a.size() + b.size() + 1, 0);

	int aSize = a.size();
	int bSize = b.size();

	for (int i = 0; i < aSize; i++)
		for (int j = 0; j < bSize; j++)
			c[i + j] += a[i] * b[j];
	normalize(c);
	return c;
}

//a += b * (10^k)
void addTo(vector<int>& a, const vector<int>& b, int k)
{
	int originalASize = a.size();
	if (a.size() < b.size() + k)
		a.resize(b.size() + k);
	a.push_back(0);

	int aSize = a.size();
	for (int i = originalASize; i < aSize; i++)
		a[i] = 0;

	int bSize = b.size();

	for (int i = 0; i < bSize; i++)
		a[i + k] += b[i];

	normalize(a);
}

// a -= b
// a>= b인 경우에만 사용 가능하다.
void subFrom(vector<int>& a, const vector<int>& b)
{
	int bSize = b.size();

	for (int i = 0; i < bSize; i++)
		a[i] -= b[i];
	normalize(a);
}

vector<int> karatsuba(const vector<int>& a, const vector<int>& b)
{
	int an = a.size(), bn = b.size();

	//a가 b보다 짧을 경우 둘을 바꾼다.
	if (an < bn)
		return karatsuba(b, a);
	//기저 사례 : a나 b가 비어있는 경우
	if (an == 0 || bn == 0)
		return vector<int>();
	//기저 사례 : a가 비교적 짧은 경우, O(n^2) 곱셈으로 변경한다.(성능을 위함)
	if (an <= 50)
		return multiply(a, b);
	int half = an / 2;

	vector<int> a0(a.begin(), a.begin() + half);
	vector<int> a1(a.begin() + half, a.end());
	vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
	vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

	//z2 = a1 * b1
	vector<int> z2 = karatsuba(a1, b1);

	//z0 = a0 * b0
	vector<int> z0 = karatsuba(a0, b0);
	
	//z1 = ((a0 + a1) * (b0 + b1)) - z0 - z2
	addTo(a0, a1, 0);
	addTo(b0, b1, 0);
	vector<int> z1 = karatsuba(a0, b0);
	subFrom(z1, z0);
	subFrom(z1, z2);

	//병합 과정
	//ret = z0+z1*10^half + z2 * 10(half*2)
	vector<int> ret(z2.size() + half * 2, 0);
	addTo(ret, z0, 0);
	addTo(ret, z1, half);
	addTo(ret, z2, half * 2);
	return ret;
}

int main()
{
	vector<int> a;
	vector<int> b;
	for (int i = 0; i < 100; i++)
		a.push_back(i % 10);

	for (int i = 0; i < 73; i++)
		b.push_back(i % 10);
	vector<int> c = karatsuba(b, a);

	int cSize = c.size();
	for (int i = 0; i < cSize; i++)
		cout << c[i];

	return 0;
}

시간복잡도

이제 카라츠바 알고리즘의 시간복잡도를 따져볼 차례다.

위의 구현에서는 a의 길이가 50 이하이면 O(n^2) 곱셈 알고리즘을 이용하도록 했지만, 계산 편의를 위해서 시간복잡도 분석에서는 한 자리 숫자에 도달해야 O(n^2) 곱셈 알고리즘을 이용한다고 친다.

a,b의 자릿수 n이 2^k 이라고 할 때 재귀호출의 깊이는 k가 된다.

한번 쪼갤 때 마다 수행해야 할 곱셈이 3배(a1*b1, a0*b0, (a0+a1) * (b0+b1))로 늘어나기 때문에 마지막 단계에서는 3^k 개의 부분 문제가 있고, 마지막 단계에서는 두 수 모두 한자리 숫자니까 곱셈 한번이면 충분하다.

따라서 곱셈 횟수는 총 O(3^k)다.

여기서 n=2^k 라고 가정했으니 k=log(n)이고,

O(3^k) = O(3^log(n)) = O(n^log(3))

이다.

병합과정도 따져보자면, 병합과정은 더하기, 빼기만으로 구현된다. 더하기와 빼기는 O(n) 시간 안에 해결되고, 재귀 호출로 단계가 내려갈 때마다 숫자의 길이는 절반이 되고 문제의 개수는 3배가 되기 때문에, 깊이 i에서 병합에 필요한 연산 횟수는 ((3/2)^i) * n 이다.

따라서 병합을 위해 필요한 총 연산 수는

이 함수는 n^log(3)과 같은 속도로 증가한다.

따라서, 최종 시간복잡도는 O(n^log3)이 된다.

출처

알고리즘 문제 해결전략 - 인사이트

1. Singleton 패턴이란

1.1 정의

싱글톤 패턴은 일반적으로 클래스의 생성자를 private으로 선언하고, 클래스 안에 static으로 자기 자신에 대한 레퍼런스를 두어 그 레퍼런스를 참조하게 하는 식으로 구현된다.

1.2 UML

Singleton 클래스는 instance라는 이름으로 자기 자신에 대한 레퍼런스를 static으로 가지고 접근 제한자는 private이다. 그리고 Singleton 클래스의 외부에서 이 클래스에 접근할 때는 getInstance()라는 static메소드를 통해 이 레퍼런스에 접근한다.

1.3 구현예시

UML 보다는 구현 예시로 보는 것이 이해가 빠를 듯 하다.

class Singleton
{
public:	
	//싱글톤 객체를 받는다.
	static Singleton* getInstance()
{
if(instance == NULL)
instance = new Singleton();
return instance;
}
static Singleton* instance;
};

*C++에서 static Singleton* instance; 라고 선언만 해두면 instance가 정의되지 않았기 때문에 컴파일 오류가 난다. 원래라면 .cpp 파일에 Singleton::Singleton* instance; 라고 한 줄 적어주어야 오류가 안 나는데, 여기서는 이해를 위해서 해당 내용은 생략하였다.

getInstance() 메소드는 내부에 static으로 선언된 instance 변수가 NULL인지 확인하고, NULL이라면 새로운 Singleton 객체를 생성한 후 그 주소를 리턴하고, NULL이 아니라면 instance 변수에 있는 객체에 대한 주소를 리턴한다.

이런식으로 하면, 외부의 어떤 클래스에서든지 Singleton::getInstance()->method() 이런 식으로 Singleton 객체에 접근 할 수 있다.

1.4 싱글톤 패턴 적용시 고려사항

개인적인 경험으로, 싱글톤 패턴을 한번 사용해 보면 구현하기가 굉장히 편하고, 또 여기저기에 적용하기가 쉬워서 싱글톤 패턴을 남용하게 될 수도 있다.

싱글톤 패턴도 당연히 단점을 가지고 있기 때문에 싱글톤 패턴은 남용하지 않도록 다음의 원칙을 준수해야 한다.

싱글톤 패턴은 위의 두 가지가 모두 만족되는 경우에만 사용해야한다.

싱글톤 패턴을 적용한 클래스는 2개 이상의 인스턴스가 존재 할 수 있도록 설계를 변경하기 어렵다. 그렇기 때문에 싱글톤 패턴을 적용 할 때는 해당 클래스의 인스턴스가 하나여야함을 보장 할 수 있을 때에만 적용해야한다.

다른 모든 클래스들에서 접근 되는 것이 아니라면, 굳이 싱글톤 패턴을 적용할 필요가 없다.

2. 적용 예제

이 예제는 Head First Design Pattern의 예제를 가져온 것이다.

요즘은 거의 모든 초콜릿 공장에서 초콜릿을 끓이는 초콜릿 보일러를 컴퓨터로 제어한다. 초콜릿 보일러는 초콬릿을 채워 넣고, 끓이고, 보일러 안의 초콜릿을 비워내는 작업을 한다.

초콜릿 보일러는 한개만으로도 충분한 양의 초콜릿을 끓일 수 있고, 비싸기 떄문에 공장마다 단 하나의 초콜릿 보일러만을 가진다고 한다.

그리고 초콜릿 보일러는 다른 모든 클래스에서 접근 가능하게 구현되어야 한다. 초콜릿 보일러는 뜨거운 초콜릿을 관리하기 때문에 사고가 나게 하지 않기 위해 여러 안전장치들이 관리하고, 추후에 시스템에 이런 안전장치들을 클래스화하여 추가할 것이다.

그래서 초콜릿 보일러에 싱글톤 패턴을 적용하여 다음과 같이 구현한다.

<ChocolateBoiler.h>
#pragma once
#include <iostream>

using namespace std;

//초콜릿을 끓이는 초콜릿 보일러 클래스
//싱글톤 패턴을 적용하여 구현됨
class ChocolateBoiler
{
public:	
	//싱글톤 객체를 받는다.
	static ChocolateBoiler* getInstance();

	//보일러에 초콜릿을 채워 넣는다.
	void fill();

	//초콜릿을 끓인다.
	void boil();

	//보일러 안에 담긴 초콜릿을 비워낸다.
	void drain();

	bool isEmpty();	
	bool isBoiled();
private:
	bool empty;
	bool boiled;
	ChocolateBoiler();
};

<ChocolateBoiler.cpp>
#include "ChocolateBoiler.h"

ChocolateBoiler::ChocolateBoiler()
{
	empty = true;
	boiled = false;
}

ChocolateBoiler* ChocolateBoiler::getInstance()
{
	static ChocolateBoiler* instance;
	if (instance == NULL)
	{
		cout << "ChocolateBoiler 객체 생성!" << endl;
		instance = new ChocolateBoiler();
	}
	return instance;
}

void ChocolateBoiler::fill()
{
	if (!isEmpty())
		return;
	empty = false;
	boiled = false;
	cout << "Chocolate Boiler 채워짐" << endl;
}

void ChocolateBoiler::boil()
{
	if (isEmpty() || isBoiled())
		return;
	boiled = true;
	cout << "Chocolate Boiler 끓여짐" << endl;
}

void ChocolateBoiler::drain()
{
	if (isEmpty() || !isBoiled())
		return;
	empty = true;

	cout << "Chocolate Boiler 비워짐" << endl;
}

bool ChocolateBoiler::isEmpty()
{
	return empty;
}

bool ChocolateBoiler::isBoiled()
{
	return boiled;
}

이제 ChocoloateBoiler 객체에 접근할 때는 다음과 같이 사용하면 된다.

ChocolateBoiler::getInstance()->fill();
ChocolateBoiler::getInstance()->boil();
ChocolateBoiler::getInstance()->drain();

3. Singleton 패턴의 장점

위의 2가지 장점이 Singleton 패턴을 사용하는 주된 이유이자 Singleton 패턴 적용시 꼭 지켜야 할 점이다.

게으르게 생성할 수 있다는 것은, 프로그램 실행 중에 인스턴스를 생성 할 수 있다는 것이다.

이는 Singleton 패턴을 적용하지 않고 전역변수를 사용 했을때에 비해서 장점인데, 전역변수를 사용하면 프로그램 실행시에 인스턴스를 바로 생성해야한다.

이렇게 할 때 문제점은, 생성된 인스턴스가 프로그램이 실행 되는 동안 한번도 사용되지 않을 경우 자원이 낭비된다.

그렇기 때문에 게으르게 생성되는 것이 Singleton의 장점이라고 할 수 있다.

인스턴스의 개수를 변경하기가 자유롭다는 말이 참 혼란스럽다. 싱글톤 패턴은 클래스의 인스턴스가 유일함을 보장 할 때만 사용해야 하는데, GoF의 디자인 패턴 책에서는 인스턴스의 갯수 변경이 자유롭다는 것을 장점이라고 설명한다.

물론 싱글톤 인스턴스에 대한 레퍼런스를 배열이나 링크드 리스트 등을 사용해서 구현하면 여러개의 인스턴스를 가지는 싱글톤 클래스를 구현 할 수는 있다.

싱글톤 패턴은, 여러개의 인스턴스를 가지는 싱글톤 클래스를 구현 할 수 있긴 하지만, 기본적으로는 한개의 인스턴스만이 존재해야 할 때 적용해야한다고 생각하면 될 듯하다.

4. Singleton 패턴의 단점

단일 책임의 원칙은 모든 클래스가 하나의 책임만을 가져야 한다는 원칙이다.

싱글톤 클래스는 클래스의 작업을 처리하는 역할 뿐 아니라 자신의 인스턴스에 대한 접근을 관리하는 역할에 대해서도 책임을 져야한다.

이렇게 하는게 전체적인 설계를 간단하게 만들 수 있어서 장점이기도 하지만, 단일 책임의 원칙을 어긴다는 점도 고려해 봐야한다.

싱글톤 패턴을 적용하면 여러 클래스나 컴포넌트가 싱글톤 클래스에 의존하게 된다. 이는 시스템의 Coupling(결합도)를 높이는 결과를 가져오기 때문에 주의해야한다.

싱글톤 클래스는 생성자가 private으로 지정되기 때문에 상속이 불가능 한데, 이를 protected나 public으로 고치면 다른 클래스에서 인스턴스를 만들 수 있게 되서 더이상 싱글톤이라고 할 수 없게 된다.

생성자 문제 뿐만 아니라, 싱글톤 클래스는 static 변수를 바탕으로 하기 때문에 모든 서브클래스들이 그 변수를 공유하게 된다.

이를 해결하기 위해서는 '레지스트리'를 구현해두어야 한다.

멀티 스레드를 적용하면 여러 스레드에서 한개의 싱글톤 클래스에 접근하게 된다. 이는 동기화 문제를 발생시킬 수 있으니 volatile 키워드를 통해 Double Checking Locking을 적용하거나 getInstance() 메소드에 synchronized 키워드를 적용하여 동기화 해야한다.

그런데 synchronized 키워드를 적용하면 스레드에서 getInstance() 할 떄마다 속도가 느려지는 문제가 발생한다.

5. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- GoF의 디자인 패턴(Pearson Addison Wesley)

- 위키피디아 Lazy Initialization

https://en.wikipedia.org/wiki/Lazy_initialization

- Code Project Singleton Pattern – Positive and Negative Aspects

https://www.codeproject.com/Articles/307233/Singleton-Pattern-Positive-and-Negative-Aspects-2

- 위키피디아 단일 책임 원칙 

https://ko.wikipedia.org/wiki/%EB%8B%A8%EC%9D%BC_%EC%B1%85%EC%9E%84_%EC%9B%90%EC%B9%99