MyBatis 란 객체지향 언어인 Java 와 SQL Based 인 관계형 데이터베이스(RDBMS) 사이의 데이터를 다루는 방식의 괴리를 해결하기 위해 만들어진 Persistence Framework 의 일종이다.


 Java 에서 DB와의 Connection 을 위해 제공하는 JDBC 를 Wrapping 한 구조로 되어 있으며, 기존의 JDBC 에 비해 많은 장점들을 갖고 있다.


무엇보다 사용이 간단하고, 60% 정도의 생산성 향상이 있다고 한다.

또한 JDBC 사용시 매번 Query Statement 를 생성하는 구문을 작성해야 했던 것과 다르게 쿼리의 재사용과, 코드와의 분리가 좀 더 수월해졌기 때문에 유지 보수 측면에서도 이점을 갖는다.


 주로 mybatis-config.xml 과 같이 별도의 파일에 환경 설정을 분리시키며, 변수 형태로 DB 연결정보들을 관리한다.

간단한 설정 방법은 다음과 같다.



/* 설정 <pom.xml> */
<dependency>
<groupId>org.mybatis</groupId>
<artifactId>mybatis-spring</artifactId>
<version>1.3.2</version>
</dependency>



 Maven 을 사용한다면 위와 같이 먼저 pom.xml 에 MyBatis Dependency 를 기입해주어야 한다. 이후 다음과 같이 프로젝트별로 관리하는 개별 설정 파일에 내용을 기입해주면 된다.



/* 설정 <설정파일.xml> */

//Property 설정 분리
<properties resource="mybatis/config.properties">
<property name="username" value="jinsp"/>
<property name="password" value="epD@kef0"/>
</properties>


//커넥션 풀 사용
<dataSource type="POOLED">
//Database Driver
<property name="driver" value="${driver}"/>
//Database Url
<property name="url" value="${url}"/>
//Database UserName
<property name="username" value="${username}"/>
//Database Password
<property name="password" value="${password}"/>
</dataSource>



 이렇게 설정해준다면 MyBatis 의 SqlSessionFactory 를 통해 Connection 을 연결할 수 있다. MyBatis 의 사용을 위해서는 매퍼 파일(Mapper File) 이라 불리는 Xml 설정이 추가로 필요하다. 이는 다음과 같은 형태로 구성이 되어 있다.




<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<mapper namespace="StudentRepository">
<select id="selectStudentList" resultType="student">
SELECT
`id` AS "studentId",
`name` AS "studentName"
FROM
student
</select>
</mapper>



 위의 Mapper 설정에 대한 설명을 간단히 하자면, 설정들이 StudentRepository 라는 @Repository 로 명시된 클래스에 매핑되며, 그 안에 학생들의 리스트를 조회하는 쿼리문인 selectStudentList 를 사용할 수 있게 설정되어있다는 뜻이다. selectStudentList 라는 Id 를 가진 SQL 문은 쿼리문의 결과(ResultType)를 Student 형태의 객체의 형태로 반환하며, 요소가 여러개일 경우 List 형태의 Collection 으로 반환한다.


위와 같이 설정을 하고, 위에 명시된 쿼리의 ID 를 SessionFactory 를 통해 불러와서 실행시켜주면 연동이 간단하게 끝난다.



* AWS 의 Cloud 서비스 관련해서는 사실 AWS 공식 홈페이지가 제공하는 Document 가 워낙 잘 설명이 되어있기 때문에, 본 포스팅과 더불어 참조하는 것이 좋습니다.



 아마존 클라우드를 사용하는 대부분의 기업에서 S3 와 더불어 CDN 을 목적으로 사용하는 솔루션이 Cloudfront 이다.


 Cloudfront 는 .html, .css, .js 및 이미지 파일 등의 정적 및 동적 컨텐츠를 사용자에게 더 빨리 배포할 수 있도록 지원하는 웹서비스이다.


사용자가 서비스하는 콘텐츠를 요청하면 엣지 로케이션에 있는 자원을 이용할 수 있도록 Contents Delivery 도 수행하는 역할을 한다. 이처럼 Cloudfront는 컨텐츠를 가장 적은 Hop으로 접근할 수 있는 위치로 라우팅시켜줌으로써 지연속도를 줄이고 빠른 로딩을 제공한다.


전형적인 CDN 으로써의 역할을 하지만, S3 가 일반적으로 "REST API 로 접근할 수 있는 리소스 저장소" 의 역할에 충실한 반면 Cloudfront 는 이를 직접 CDN 을 구성하게끔 만들어주는 Bridge 와 같은 역할을 하며 AWS 의 Lambda 와 같은 서비스와도 연계가 될 수 있고, 비용적인 측면에서도 좀 더 저렴한 부분이 있다.


 Nginx를 사용해서 이런 식의 Proxy를 구현할 수도 있다. NginX 서버에서 요청을 받아 가까운 Edge Location 으로 라우팅을 해주고 컨텐츠 자체를 Dynamic Caching 해주면 비슷한 역할을 하는 서버 인스턴스로 구현이 가능하다. (개인적인 생각으로는 아마 Cloudfront 도 이렇게 내부적으로 동작할 가능성이 커보인다.)





 가비지컬렉터 의 동작을 이해하는 건 Java 개발자의 가장 필수적인 요건이다. 나름 Java 를 할 줄 안다고 자만하고 있었는데, 이 부분을 공부하면서 깊이 반성하였다.


 C/C++ 개발자의 경우 객체를 관리하는데 있어서 메모리는 순전히 개발자의 몫이다. 필요한 시점에 생성하고 불필요한 시점에 반환해야 하며 올바른 메모리 주소를 참조할 수 있도록 관리해주어야 한다. 

반면 Java 의 경우 개발자는 이 부분에 있어서 신경을 덜 써도 되며 이는 Java 언어가 제공하는 Garbage Collector 가 이 일을 해주기 때문이다. Garbage Collector 는 항상 background 에서 데몬 쓰레드로 돌아가면서 접근 불가능한(Unreachable) 상태가 된 객체들의 메모리를 정리해준다.



 먼저 Garbage Collectors (이하 GC) 의 동작을 이해하기 위해서는 JVM 의 메모리 관리에 대해 알아야 한다. JVM에는 일반적으로 Young Generation / Old Generation 이라는 두가지의 물리적 공간이 존재한다.


 GC는 2가지 전제를 갖고 있다. 대부분의 객체가 금방 Unreachable 한 상태가 된다는 것과 Old 객체에서 Young 객체로의 참조가 적다는 점이다. 다음은 각 물리 공간에 GC 가 어떻게 동작하는지를 설명한다.


- Young Generation 영역 : 새롭게 생성한 객체가 위치한다. 많은 객체가 이 영역에 생성되었다 사라지며 이를 Minor GC라고 한다.


- Old Generation 영역 : 접근불가능한 상태가 되지않아 Young 영역에서 살아남은 객체가 이 영역으로 복사된다. Young 영역보다 크게 할당되며 GC는 적게 발생한다. 이 영역에서 객체가 사라질 때 Major GC 또는 Full GC 가 발생한다. 

Old 영역에서는 Card table이라는 512 byte의 Chunk 가 존재하며 Old영역의 객체 중 Young 영역의 객체를 참조하는 객체의 정보들을 저장한다.


 Young 영역은 Eden 영역과 2개의 Survivor 영역으로나뉜다. New 를 이용해서 객체를 생성하면 이는 Eden 영역에 위치하게 된다. Eden 영역에서 GC가 한번 발생 후 살아남은 객체는 Survivor 영역 중 하나로 이동한다. 이 때 객체가 Eden 영역에서 Survivor1, Survivor2 영역으로 이동할 때 Minor GC 가 수행된다.


지속적인 Eden 영역에서의 GC 이후 Survivor 영역으로 객체가 계속 쌓이고 Survivor 영역 내 빈곳으로 살아남은 객체들이 이동한다. 이러한 과정을 계속 반복 후 Survivor 영역들이 가득차게 되면, 남은 객체가 Old 영역으로 이동한다.


 2개의 Survivor 영역에 모두 데이터가 존재하거나 모두 사용량이 0이면 시스템은 비정상이다. Old 영역은 기본적으로 데이터가 가득차면 GC를 수행하며 GC 방식은 JDK 7 기준으로 5가지가 있다.


(1) Serial GC : Mark-sweep-compact 알고리즘이 사용된다. Old 영역에 살아있는 객체를 Mark 하고 Heap의 앞부분부터 살아있는 객체를 Sweep한 뒤, 힙의 앞부분부터 객체를 쌓는다.(Compact) 메모리와 CPU 코어수가 적을 때 좋다.


(2) Parallel GC : Serial GC와 기본적인 알고리즘은 같지만, GC를 처리하는 Thread의 개수가 여러 개다. 메모리와 CPU 코어 수가 많을수록 좋다.


(3) Parallel Old GC : Parallel GC와 같지만 Old 영역의 GC 알고리즘만 다르다. Mark-Summary-Compact 알고리즘이며 조금 더 복잡하다.


(4) CMS GC : Stop-the-world 이후 Initial marking 시 살아있는 객체만 찾는다. 이후 concurrent mark 단계에서 참조를 따라가며 새로 추가되거나 참조가 끊긴 객체들을 remark 한다. 모든 작업이 멀티스레드 환경에서 동시진행되기 때문에 stop-the-world 시간이 매우 짧은 대신 memory와 CPU 를 많이 사용하고 compaction 단계가 제공되지 않는다.


(5) GI GC : Young 영역과 Old 영역이 없이 매우 빠르게 객체를 할당하고 GC한다.



 GC가 실행되기 전 JVM은 Application의 실행을 멈춘다. 이를 Stop-the-World 라 하며 GC 쓰레드 이외의 쓰레드들의 작업이 멈춘다. 이 때 이 Stop the world 를 줄이는 작업을 GC 튜닝이라 한다.


GC 튜닝이 모든 Java Application 에 필수적인 것은 아니지만, 크리티컬한 요청을 담당하는 서버나 코어 엔진의 경우 GC 튜닝이 필요하다. GC 튜닝을 위해 지켜야할 기본적인 원칙은 GC 튜닝이 로직에 영향을 미치지 않도록 가능한 늦게 수행하고, 객체 생성을 최소화하는 것이다.


 즉, GC 튜닝은 Java 코드 최적화와 맞물려 있는 영역이라고도 할 수 있다. 가령 String 의 append 시, + 연산으로 2개 이상의 String 을 더하는 대신, StringBuilder 등을 쓰는 것도 일종의 메모리 튜닝이라고 할 수 있다. 그 외에는 설정적인 부분으로 JVM 옵션으로 메모리 크기를 조절하고 GC 방식을 옵션으로 지정해주는 등이 있다.


(1) 메모리 관련 GC 튜닝을 위한 JVM 옵션

 -Xms : JVM 시작 시 힙 영역의 크기

 -Xmx : 최대 힙 영역 크기

 -XX:NewRatio : New 영역과 Old 영역의 비율. (New 영역의 비율을 전달한다.)

 -XX:NewSize : New 영역의 크기

 -XX:SurvivorRatio : Eden 영역과 Survivor 영역의 비율 (Survivor 영역의 비율을 전달한다.)


(2) GC 방식 관련 GC 튜닝을 위한 JVM 옵션

 - Serial GC :

-XX:+UseSerialGC 


 - Parallel GC : 

-XX:+UseParallelGC

-XX:ParallelGCThreads=value


 - Parallel Compacting GC : 

-XX:+UseParallelOldGC


 - CMS GC :   

-XX:+UseConcMarkSweepGC 

-XX:+UseParNewGC

-XX:+CMSParallelRemarkEnabled

-XX:CMSInitiatingOccupancyFraction=value 

-XX:+UseCMSInitiatingOccupancyOnly

 - G1 : 

-XX:+UnlockExperimentalVMOptions

-XX:+UseG1GC


위와 같은 옵션을 적용한다고 해도 GC 의 튜닝이 비약적인 시스템의 성능 향상을 가져오게 되리라고 보장할 수는 없다. 결국 GC 튜닝은 계속적인 모니터링을 통해서 이루어지는 것으로, 복잡한 시스템의 메모리 구조를 공식처럼 맞춰서 설정하기 보다는 지속적인 모니터링과 성능 향상을 위한 노력이 필요하다.




 첫 회사에 입사해서 배운 개념이다. 글로벌 서비스를 하는 회사였기 때문에 필수적인 용어였고, 마침 OJT 첫 과제가 내부에서 사용할 수 있도록 CDN 을 구축해보는 것이었다.


 CDN컨텐츠를 효율적으로 전달하기 위해 여러 노드를 가진 네트워크에 데이터를 저장하여 제공하는 시스템이다

CDN 의 사용 목적은 거리가 멀어 물리적으로 네트워크 비용이 많이 요구되는 곳에도 데이터를 효과적으로 전달하기 위한 목적으로 구성된다.


주로 ISP에 직접 연결되어 데이터를 전송하여 컨텐츠 병목을 피할 수 있는 장점이 있다. CP들은 CDN 측에는 사용료를, CDN ISP 측에 호스팅 비용을 지불한다. 최신 트랜드는 P2P 기술을 서버와 같이 이용하는 하이브리드 모델을 사용하는 것이다.


 주로 웹요소(텍스트, 그래픽, 스크립트), 다운로드 가능한 파일들, 어플리케이션들이 주로 사용되며, 갱신과 전달이 빈번한 메시지 형태의 데이터나 로그성 데이터가 사용되는 경우도 있다.


사용자와 지리적으로 가까운 노드에 서버를 두는데 있어 주로 Content 캐싱 방식을 이용하며 Static caching 은 사용자의 요청이 없어도 리소스를 저장해 놓는 방식이고 Dynamic caching 은 사용자의 요청을 받으면 Origin server로부터 컨텐츠를 받아서(Cache fill) 캐시에 저장한다. 

주로 저장하는데 있어 TTL(Time To Live) 이 정의되어 있고 이는 상황에 따라 삭제되거나 계속 유지될 수도 있다.


 특히 회사에서 글로벌 서비스를 진행한다면 CDN 의 사용은 필수적이다. 많은 웹 기반 서비스들이 대용량의 리소스를 서버 자체에서 핸들링 하는 경우는 드물며, 지리적 이점 & 네트워크 효율성 및 안정성을 이유로 CDN 을 사용한다.

솔루션으로써 가장 훌륭한 평가를 받는건 Akamai 의 솔루션으로 생각된다.




 Binary Indexed Tree(이하 BIT) 는 알고리즘이라기 보다는 자료구조에 가깝지만, 흔히 기본 자료 구조라고 할 수 있는 스택, 큐와 같은 자료구조보다는 고급의 자료구조이다. 사촌 격인 Segment Tree 도 있으나 조금 더 설명하기가 어렵기 때문에 본 포스팅에서는 Binary Indexed Tree 만 소개한다.


BIT의 원래 명칭은 Fenwick Tree 이며, 구현 상 Binary Tree 를 이용하기 때문에 BIT(Binary Indexed Tree) 라고 부른다. 


이 이진트리 형태의 자료구조는 효과적으로 부분 요소의 갱신(Update) 와 조회(Select) 를 하기 위하여 만들어진 자료구조로, 많은 변경과 많은 데이터의 조회가 빈번하게 일어날 때 한번에 처리할 수 있는 간단하면서도 유용한 자료구조이다.


특히, 데이터의 일부분이 갱신되었을 때 데이터 전체의 값이 변하는 경우, 가령 데이터 전체의 총합을 구하거나 최댓값을 구하는 일 등을 가장 효과적으로 수행할 수 있는 자료구조이다.


설명을 위해 다음 배열을 준비해보았다.



준비한 배열은 음... 온라인 게임의 유저들의 점수를 나타낸 랭킹 Database라고 해보자. 6명의 유저들이지만 엎치락 뒤치락하고 있는 것을 볼 수 있다. 

이 데이터베이스에서 가장 점수가 높은 유저는 맨 앞에 있는 10점을 획득한 유저이고, 최고점은 10점이다. 최고점을 우리는 DB를 모두 뒤져 시간복잡도 O(N) 만에 최댓값을 찾아내었다. 그런데 10분뒤 상황이 바뀌었다.


갑자기 몇몇 유저의 약진에 힘입어 10점을 획득한 유저는 3등이 되었다. 이런.. 당신은 다시 최고점을 구하기 위하여 DB를 모두 뒤져 최댓값 15를 찾아내기에 이른다. 시간복잡도는 O(N)


이 구조는 효과적일까? 전혀 그렇지 않다. 심지어 실시간 게임이라면 이런식으로 관리했다간 100만명의 유저에 대해 매 Tick 마다 100만명을 전부 검사해야 한다. 물론 알고리즘의 적용 대상을 이런 종류의 실시간 서비스를 예시로 드는건 적절하지 않아보이지만, 더 최적화할 수 있는 방안은 분명히 있다.


<BIT 가 적용된 새로운 자료구조>


위의 그림은 BIT 가 적용된 새로운 자료구조를 보여준다. 위에 보이는 것 처럼 Binary Tree 를 이용한 구조는 추가적인 메모리를 사용하지만, 토너먼트 형태로 최댓값을 구해내고 있다. 또한 보면 알 수 있겠지만 범위별로 최댓값을 구하는 것도 가능하다. 토너먼트를 해당 범위에 대해서만 열면 그만이다.


 눈치챌 수 있겠지만 이 자료구조는 토너먼트 형식을 이용해서 비교해야할 대상과만 비교한다. 가령, A가 B보다 크다는게 보장이 되었을 때, C가 B보다 크다면 A와 C는 서로 비교할 필요가 없다. 전부 비교할 필요 없이 두번만에 최댓값 C를 구할 수 있는 것이다.


다음 코드는 이를 좀 더 명확히 나타내며 C로 작성된 코드지만 이해하기 어렵지 않을 것이다.



#define max(a,b) ((a)>(b)) ? (a):(b)

const int BMAX = 100000;

int bit[2*BMAX+1] = {0, };
void set(int a, int v)
{
a+=BMAX, bit[a] = v;
while(a/=2)
bit[a] = max(bit[2*a], bit[2*a+1]);
}
int get(int l, int r)
{
l+=BMAX, r+=BMAX;
int ans = 0;
while(l<=r)
{
if(l%2==1)
ans = max(ans, bit[l]), l++;
if(r%2==0)
ans = max(ans, bit[r]), r--;
l/=2, r/=2;
}
return ans;
}



 코드를 보면 추가적인 공간을 할당해, 그부분 부터 값을 채우면서 루트 노드에 최댓값을 갱신하고 있는 모습이다.

위의 코드를 이용하면 set 을 통해 인덱스 a에 값 v를 저장하여 펜윅트리를 구성할 수 있고, get 함수를 통해 l 부터 r 까지 범위 내에 있는 최댓값을 어렵지 않게 구해낼 수 있다.


물론 시간복잡도는 set 하는 부분에서 O(logN) 이 소모되지만 get 하는 부분에서 O(logN) 의 효율성을 보인다.

기존에 최댓값을 구하려면 범위 내 모든 요소를 검사해야 했던 O(N) 의 자료구조보다 향상된 범위 검색(Select) 퍼포먼스를 낼 수 있는 것이다. 물론 이를 위해 값의 갱신(Update) 에 O(1) 이 아닌 O(logN) 의 비용을 지불하지만 이는 어떤 종류의 데이터들에 대해 훨씬 효율적일 수 있다.


이번에 포스팅 한 BIT의 경우 Single Update (포인트 갱신) & Range Query (범위 검색) 이지만, 이를 좀 더 수학적으로 개선하면 Range Update (범위 갱신) & Range Query (범위 조회) 에 있어서도 구현이 가능한 막강한 자료구조를 만들어 낼 수도 있다. 이는 Segment Tree 포스팅 이후에 별도로 포스팅을 할 예정이다. (내용이 어렵다 ㅜ)






 데드 레커닝이란 특히 게임서버에서 게임 클라이언트와 실시간 동기화를 위한 알고리즘이다.


 가령 캐릭터의 이동에 대해 동기화를 하는 가장 완벽한 방법은 매 프레임마다 통신을 하는 것이지만, 이건 엄청난 네트워크 양을 소모하게 된다.


특히 캐릭터의 이동을 통신해야 한다는 건 다른 유저가 이를 알아야하거나 서버의 판정에 크게 의존한다는 얘기이므로, 이는 퍼포먼스 뿐 아니라 신뢰성도 중요한 이슈가 된다.


 이러한 문제를 해결하기 위해서 보다 효율적인 방법은 클라이언트에서 방향을 전환할 때만 추가 패킷을 보내고 서버는 그 사이에서 클라이언트의 게임 캐릭터 위치를 예측하여 동기화를 맞추는 기법이다.


 그리고 이 때 각 엔티티들의 행동을 예측하는 종류의 알고리즘을 서로 맞추는 일종의 약속을 데드 레커닝이라 한다.


 이 때 사용하는 알고리즘은 특정지을 수는 없으나 주로, regression 형태와 유사한 종류의 공식으로 유도한다. 가장 간단한 방법은 위치로부터 속도와 시간 을 조합하여 평균을 내고 해당 방향으로 전진시키는 방향이다. 가능한 알고리즘이 정교하고 게임에 최적화되어있을 수록 효과는 극대화된다.


검증은 서버와 클라이언트가 모두 수행할 수 있으나 게임 종류에 따라서 서버만 수행하거나 클라이언트만 수행하는 경우가 있다. (주로 클라이언트가 처리하는 경우가 많다.)


 송수신에 있어서 지연시간이 발생하고 서버쪽 데이터 처리 로직 혹은 다른 유저에게 브로드캐스팅하는데 걸리는 시간 등이 있기 때문에 종종 오차가 발생하고, 특히 일시적 통신 오류가 발생할 경우에는 동기화 이후 캐릭터의 위치가 워프하는 등 상황이 발생하게 된다.


 당연히 이를 완벽하게 해결하는 방안은 없으며, 어느정도 운영 상의 도움이나 상호 약속된 정해진 알고리즘을 통해 조절하곤 한다.

이런면에서 어느정도 트레이드 오프를 가져가느냐가 사용자 경험에 있어서 핵심적인 영향을 미칠 수 있다.





 힙(Heap)은 특정 연산을 빠르게 수행하기 위한 이진 트리 자료 구조로 부모 노드와 자식 노드간의 일련의 규칙을 통해 일관성있는 결과를 도출해내기 위한 자료구조이다. 


 가령 Min Heap 이라함은 부모가 자식보다 작은 이진 트리를 구성하며 루트노드가 즉 전체 데이터의 최솟값이 된다. 반대로 Max Heap 은 부모가 자식보다 큰 자료구조이기 때문에 루트노드는 전체 데이터의 최댓값을 나타낸다.


 Binary Heap 을 구현할 경우 이진 트리의 Root 노드부터 단일 Leaf 노드까지의 순회비용만 가질 뿐이므로 Insert 와 Delete 연산이 모두 O(logN) 의 복잡도를 갖으며 Min Heap / Max Heap 과 같은 기능적 힙을 구현하는 경우 (아마 대부분의 경우), 조회(Peek) 의 시간 복잡도는 O(1) 로 아주 효율적이다.


다음은 Binary Heap 의 배열을 이용한 예시의 그림이다. 


<Binary Heap 에서 Push 의 Work flow>


 Binary Heap 에서 새로운 값을 Push 할 때에는 Heap 의 마지막 위치(Leaf Node)에 값을 넣고, 루트 노드(Root Node) 까지 올라오면서 맞는 위치를 찾는다.

Min Heap 이냐 Max Heap 이냐에 따라서 조건에 만족한다면 해당 위치에 멈추고, 더 위쪽 노드로 가야한다면 부모노드와 Swap 해준다. 자매 노드(Siblings) 를 고려하지 않아도 되기 때문에 구현은 편안하다.


<Binary Heap 에서 Pop 의 Work flow>


 Pop 연산은 이와 반대로 구현된다. 특성상 무조건 Root Node 에 원하는 값이 있다. Min Heap 의 경우 데이터 전체의 최솟값이, Max Heap 의 경우 데이터 전체의 최댓값이 있다.

따라서 꺼내오는 시간은 O(1) 이며, 대신 꺼낸 자리에 Leaf Node 로 보낼 값을 집어넣는다. Min Heap의 경우 최댓값을 넣어 무조건 맨 끝으로 보낼 수 있게 한다. 그리고 나서는 왼쪽 자식(Left) 과 오른쪽 자식(Right) 을 비교하여 더 작거나(Min) 더 큰(Max) 값과 부모의 값을 교환하면서 내려간다.


이에 대한 자세한 구현은 다음 코드를 참조하자. C 로 구현되어있으나 어렵진 않을 것이다.



int h[1501] = {0, };
int hn=0;
void push(int x)
{
int cur = hn;
h[hn++] = x;
while(cur > 0)
{
int parent = (cur-1)/2;
if(h[parent] > h[cur]) {
swap(h[parent], h[cur]);
} else {
break;
}
cur = parent;
}
}
int pop()
{
int ret = h[0];
h[0] = 1e8;
swap(h[0], h[--hn]);
int cur = 0;
while(2*cur+2 <= hn)
{
int l=2*cur+1, r=2*cur+2;
int nxt = h[l] < h[r] ? l : r;
if(h[nxt] < h[cur])
{
swap(h[nxt], h[cur]);
cur = nxt;
}
else
{
break;
}
}
return ret;
}




이처럼 힙은 데이터를 다루고 관리하는 유용한 자료구조이며 이 자료구조를 응용한 대표적인 사례가 우선순위큐(Priority Queue) 이다. 가령 각 노드별로 우선순위를 기록하고, 모든 노드의 우선순위(1~N) 대로 Min Heap 을 구성한다면 우선순위의 Ordering 이 낮은 순서대로 데이터를 뽑아낼 수 있다.


우선순위큐는 우선순위를 순차적으로 뽑아낼 수 있는 Push / Pop 이 가능한 자료구조일 뿐 그 구현이 Heap 일 필요는 없지만, 보통 Heap 을 이용해서 구현할 경우 Push 와 Pop 에 O(logN) 이라는 저렴한 시간복잡도가 들기 때문에 주로 Heap으로 구현이 된다.


즉, Priority Queue 를 Heap 을 이용해 만들 수 있지만 Heap 과 Priority Queue 간에는 직접적인 연관은 없으며 다만 구현에 있어서도, 기능에 있어서도 Heap 을 이용해 만드는 것이 효과적이므로 거의 동일어나 다름없이 혼용되고 있을 뿐이다.



각종 기업 면접과 테스트에서 코딩 테스트라 불리는 알고리즘 역량이 상당히 중요해진 만큼, 연습하는데 있어서 정말 유용한 자료구조이니, 위의 코드는 외워두고 써도 좋다.




 Maven 설정은 처음 배우기에 쉽지않고 진입장벽이 높지만, 어느정도 규모 있는 프로젝트를 하다보면 매우 유용하다. 최근에는 Gradle 이 떠오르고 있으나 기존의 많은 프로젝트들이 Maven 을 이용하고 있기 때문에 알아두는 것도 중요하다.


 큰 단위의 Java 프로젝트는 보통 복잡하며 여러 개의 모듈이 한 프로젝트를 구성하게 되는 경우도 많다.

여러 프로젝트 간의 설정 및 환경을 일치시키고 유지하는건 상당히 복잡한 일이 될 수 있는데, Maven 을 활용하면 이를 굉장히 편리하게 구성할 수 있다.

 예를들어 중복된 설정을 상위 프로젝트에서 Global 하게 관리함으로써 프로젝트의 구성을 단단하게 유지시켜 줄 수 있는 것이다.


 이를 위해 Maven은 POM 상속이라는 개념을 제공하여 설정의 중복을 줄이고 해당 모듈에 필요한 설정만을 갖출 수 있게 한다. 이 때 실제 프로젝트 자체는 완전히 개별적인 형태를 취하지만 단지 하나의 POM 파일로 묶어줄 뿐이다. 

아래의 예시를 참고해보자.



<!-- 부모 프로젝트(project) 에서의 설정(pom.xml) -->

    <groupId>com.demo.project</groupId>
    <artifactId>project</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <packaging>pom</packaging>

    <modules>
        <module>project-module</module>
        <module>project_api</module>
    </modules>



 최상위 POM.xml 파일의 <packaging> 태그는 반드시 pom 으로 설정되어 있어야 하고, 하위 모듈들은 <modules> 태그 하의 <module> 로 묶여서 설정되어 있어야 한다. 


그리고, 이 설정 순으로 dependency 가 생기게 된다. 정확히는 메이븐의 빌드 순서가 된다. (만약 상위 모듈에 dependency 를 갖고있다면 하위 모듈이 먼저 빌드되어선 안된다.) 하위 프로젝트들은 다음과 같이 상위 프로젝트를 <parent> 태그를 통해 기술하고 있어야 한다.




<!-- 자식 프로젝트(project-module, project-api) 에서의 설정(module/pom.xml, api/pom.xml) -->

    <parent>
        <groupId>com.demo.project</groupId>
        <artifactId>project</artifactId>
        <version>0.0.1-SNAPSHOT</version>
    </parent>



 하위 프로젝트들은 상위 프로젝트의 POM에서 기술된 설정들을 자유롭게 이용할 수 있고, 상위 프로젝트의 dependency 정보가 기본적으로 include 되어 진다. 이는 Effective POM 을 보면 확인해볼 수 있다.


 구성이 끝나면 최상위 프로젝트의 POM 을 빌드함으로써 전체 프로젝트를 빌드할 수 있다. 메이븐에서 다중 모듈 빌드는 각 하위 모듈들의 빌드 결과물이 의존관계에 있는 모듈에서 그대로 쓰이게 된다.





 Sharding 이란 RDB에서 대량의 데이터를 처리하기 위해 분산 서버에 데이터를 나누어 파티셔닝하는 기술로, 근래에 탄생하는 웹서비스의 경우 필수적으로 고려해야하는 기술이다. 


 샤딩은 DBMS레벨에서 데이터를 나누는 것이 아니라 데이터베이스 자체의 Access Routing 을 분할하기 때문에 Application 레벨에서 처리되어야 하는 문제이다. 최근에는 이를 공통화시키고 그 자체로 서비스화를 위해 미들웨어로 이식하는 추세에 있다.


 샤딩에는 Partition 기법에 따라 주로 쓰이는 몇가지 기법이 있다.


(1) Horizontal Partitioning


 Schema 가 같은 데이터를 두개 이상의 DB에 나눠 처리하는 방법이다. 가장 간단한 방식의 분할 법이고, Partitioning 정책으로 range based 방법을 사용한다면 단순한 구조로 시스템을 구축할 수 있다. 단, 여러 DB에 대해 파티셔닝을 적용 시, 데이터베이스 JOIN 문제나 Consistency, Replication 등 복잡한 문제가 많이 생기게 된다. 따라서 적용시 가능한 DB를 단순하게 설계한다.



(2) Vertical Partitioning


 테이블 별로 서버를 분할하는 방식이다. 예를들어 프로필 관리용, 사진 관리용 서버 등으로 나누어 데이터를 용도에 맞게 분할하며 구현이 간단하고 전체 시스템에 큰 변화를 주지 않아도 된다. 단 서버의 데이터가 점점 거대해지면 추가 샤딩이 필요하므로 구조를 잘 잡아놓아야 한다.



(3) Range Based Partitioning


 하나의 feature 또는 테이블이 점점 거대해지는 경우 서버를 분리한다. 범위에 따라 데이터를 나누기 때문에 단순하지만 데이터를 분할하는 기준이 예측 가능하고 명확해야 한다.



(4) Key / Hash Based Partitioning


 엔티티를 해쉬 함수에 넣어서 나오는 값을 키로 데이터를 샤딩하는 기법이다. Modular 함수가 주로 사용되며 데이터가 균등하게 분포될 수 있도록 해쉬함수를 정해야 한다. 이 방법의 단점은 Scale out 시 해쉬 함수를 변경하는 작업이 매우 비싸다는 것이다.



(5) Directory Based Partitioning


 DB와 별개로 추상화된 룩업테이블을 만들어 샤드 키에 해당하는 데이터를 Cache해서 찾는 식으로 구현된다.



 샤딩 적용시에는 몇가지 고려할 점이 있다.


- 데이터 재분배(Rebalancing) : 서비스 정지 없이 Scale out 이 가능한지를 고려해야 한다.


- 데이터 조인 : Sharding DB 간의 조인이 불가능하므로 역정규화를 감안하여 설계해야 한다. 데이터 중복은 대용량처리에 대한 tradeoff이다.


- Partitioning 기법 : 어떤 식으로 Data를 나눌 건지를 고민해야 한다. 이는 Scalable 한 아키텍처를 위한 중요한 요소이다.


- Global Unique Key : DB간 사용하는 키의 Uniqueness 를 고려해야 한다.


- Compact Table : 테이블의 단위를 가능한 작게 유지해야 한다.





 많은 경우 조인과 서브쿼리를 통해 복잡한 쿼리 연산을 수행할 수 있으나 쿼리만으로 두 테이블의 다른 항목들을 열거하는 작업은 UNION 을 사용하면 아주 간단해진다.


 다음과 같은 규칙만 만족한다면 N개의 다양한 테이블을 하나의 쿼리로 연결한 SELECT 결과를 받을 수 있다. UNION은 다음과 같이 사용가능하다.


* SELECT name from professor UNION select name from girl_group


 위의 쿼리에서 우리는 Professor 테이블의 존재하는 name 들과 girl_group 테이블 내에 존재하는 name 들을 얻을 수 있다. 교수들의 이름과 걸그룹의 이름을 같이 얻을 수 있겠다.(;;)


(1) UNION 내에서 쿼리들은 하나의 ORDER BY만 사용한다. UNION 으로 감싸는 쿼리들을 각각 정렬하는건 허용되지 않는다.


(2) 각 SELECT의 열수, 표현식이 같아야 한다.


(3) SELECT 문들끼리의 순서는 상관없다.


(4) 결과가 중복되면 DEFAULT 설정으로는 하나만 나온다.


(5) 열의 타입은 같거나 반환 가능한 형태여야 한다.


(6) 중복값을 나타내고 싶다면 UNION ALL을 사용한다.


 물론 UNION 내의 쿼리들을 각각 정리하는 편법은 존재한다. 바로 서브쿼리를 이용하면 가능한데 예를들어 다음과 같이 하면 된다.


SELECT * from (select name from professor order by reg_date)

UNION ...

SELECT * from (select name from girl_group order by reg_date)


위의 예시는 교수의 이름들을 등록 시간 별로 정렬해서 name 을 묶고, 걸그룹의 이름들을 등록 시간 별로 정렬해서 묶는 쿼리의 모습이다.

+ Recent posts