장안동베짱e's LoG# 머리 복잡할 때 보면 더 복잡해지는 블로그 RSS FEED

서문

이 글의 주소는 http://www.kippler.com/doc/jpeg2000_vs_jpegxr/ 입니다. 이 문서의 글을 다른곳으로 복사하거나 스크랩 하지 마시기 바랍니다. 이 글을 참고하고자 할 경우는 이 글에 대한 링크만을 제공하시기 바랍니다.

문서 수정 기록

- 2007/12/15 최초 작성

서론

이미지 포맷에 대한 이해

BMP

마이크로 소프트에서 만든 이미지 저장 포맷. 비손실 기반의 이미지 포맷이며, 8비트 영상 포맷은 RLE압축을 지원하지만, 파일 포맷 자체가 영상의 크기를 줄이기 위해서 만든 포맷이 아니라, 영상을 손쉽고 빠르게 처리하기 위해서 만든 포맷이므로 압축하지 않은채 사용하는 경우가 많다. (RLE압축의 경우도 압축율이 매우 낮다)

파일을 만들거나 사용하기가 매우 쉽기 때문에, 크지 않은 이미지 파일을 처리하거나 간단한 이미지 파일 처리에 많이 사용된다.

GIF

비손실 압축으로 이미지를 저장하기 위하서 만든 포맷. 8비트 컬러(256컬러)만을 지원하므로 자연스러운 영상을 표현하기는 힘들지만, 비교적 비손실 압축이 잘 지원되고, 역사가 오래된 포맷이라서 웹에서 많이 쓰이는 포맷이다. 팔레트에 의한 투명 컬러를 지원하며, 애니메이션 포맷을 지원하기 때문에 웹상에서 간단한 애니메이션을 보여줄 때에는 이만한 포맷이 없다.

예전에는 특허문제로 사용에 문제가 많았으나 특허도 만료가 되어서 이제는 자유롭게 사용이 가능한 포맷이다.

PNG

GIF포맷의 256컬러 한계와, 특허 문제로 사용하기 힘들자 이를 극복하고자 만든 포맷. GIF보다 훨씬 나중에 만들어 졌기 때문에 압축율, 기능등 모든점이 뛰어나다. GIF와 마찬가지로 비손실 압축을 지원하며, 3비트/24비트/32비트 컬러 포맷을 지원한다. 특히 32비트 포맷은 RGB에 알파 채널이 추가된 포맷이기 때문에, 반투명 이미지를 구현하기에 매우 좋다.. 하지만 아직까지 PNG알파 채널을 지원하는 브라우저나 프로그램이 많지 않으며, 애니메이션 포맷인 MNG포맷도 거의 쓰이지 않고 있다. 원래의 목적인 GIF 포맷의 대치는 아직까지 달성하지 못하고 있다.

하지만, BMP/GIF 등에 비해서 장점이 워낙 많은 관계로 차세대 비손실 압축 영상 포맷의 표준이라고 봐도 좋을듯 하다.

JPG

위의 비손실 압축 포맷과는 달리 손실 압축을 지원하는 대표적인 이미지 포맷이다. 영상의 중요하지 않은 가시정보를 제거하는 방법으로 압축을 하기 때문에, 1/10정도로 영상의 크기를 줄여도 인간의 눈으로는 그 차이를 크게 구분하지 못하게 된다. 압축 방법은 DCT 알고리즘을 사용한다.

비손실 압축

데이터를 압축할때 원본의 정보를 버리지 않는 압축 방법. 예를 들어 BMP 파일을 PNG파일로 바꾸면 그 크기가 줄어들지만 원래의 정보는 그대로 남아 있기 때문에 PNG파일을 가지고 원래의 BMP파일을 그대로 복원해서 다시 만드는 것이 가능하다.

손실 압축

원본의 데이터 정보중 중요한 부분만을 남겨두고 나머지는 버리고 압축하는 방식. 이미지 파일을 JPG파일로 변환하면 인간의 눈이 차이를 잘 못느끼는 정보를 제거후 압축을 하므로 압축율을 크게 늘리는 것이 가능하지만, 원본의 정보가 손상이 되었으므로 100% 복원하는것이 불가능 하다. 하지만 압축율이 뛰어나므로, 저장공간이나 전송 수단이 제한되어 있는 경우 비손실 압축 방식에 비해서 더 많은 정보를 전달하는것이 가능해 지기 때문에 손실 압축을 많이 사용한다.

본론

Jpeg2000 소개

JPEG2000은 손실압축의 대표적인 JPEG포맷의 단점을 극복하고자 대충 2000년 전후로 만든 포맷인가 보다.(잘 모른다)

JPEG2000에 관련된 정보를 보면 이것저것 비교점을 나열하고 이런게 좋다고 써 있는데, 결국 제일 중요한건 "기존의 DCT 방식의 압축방식이 아닌 웨이블릿 변환을 이용한 압축방식을 사용해서 JPG보다 두배는 더 좋은 압축 효율을 얻을 수 있다" 가 관건이다.

즉, 기존의 JPG는 보통 1/10 정도로 파일을 압축해서 사용하는데(JPG는 손실압축이기 때문에 1/2 도 가능하고, 1/100도 가능하지만 보통 1/10정도가 많이 쓰이는 압축율이다) JPEG2000은 1/20으로 줄여도 JPG의 1/10로 압축한 영상과 비슷한 영상을 얻을 수 있다는 의미이다.

그러다 보니, 병원같이 X-RAY 사진을 고화질로 오래보관해야 되는 곳에서는 저장공간이 절반으로 줄어드는것은 경비 절감에 큰 효과가 있기 때문에 많이 쓰이고 있으며, 극장용 디지털 영화도 JPEG2000을 영상 압축 포맷으로 사용하고 있다.

그럼에도 불구하고..... 왜 이렇게 JPEG2000은 나온지 오래되었는데 아직도 JPEG을 대치하지 못하고 있는 것일까? 여기에는 여러가지 의견이 있지만, 나 자신의 개인적인 의견은 "압축율이 문제가 아니라 속도가 문제" 라는 것이다. 대표적인 무료 JPEG2000 라이브러리에는 OpenJpeg이나 Jasper 같은 라이브러리들이 있는데, 이 라이브러리들은 기존 jpeg라이브러리에 비하면 정말 극악한 속도를 자랑한다. ID 소프트에서 만든 문서를 참고해 보면, 이들 라이브러리는 최적화된 JPEG라이브러리에 비해서 100배정도 느리니, 겨우 저장 용량 절반 아끼자고 디카로 찍은 사진 파일을 JPEG2000으로 저장했다가는 나중에 이미지 뷰어로 원하는 사진을 찾지도 못할정도이다. 실제로 2004년쯤 꿀뷰2에서 jpeg2000을 지원하려고 해당 라이브러리를 테스트 해보았다가 그 속도에 놀라서 지원을 포기한 적도 있다.

그러던 중 최근 Kakadu라는 상용 JPEG2000 라이브러리를 테스트 해 보고 다른 무료 JPEG2000 라이브러리보다 10배 가까이 빨라진것을 보고, 이제는 JPEG2000도 쓸만해 졌구나 싶어서 꿀뷰3에서는 JPEG2000을 지원하기 시작하였다. 결론은, 이제는 컴퓨터도 빨라졌으니 좋은 라이브러리를 사용하면 JPEG2000도 쓸만한 포맷이 되었다는 것이다.

JPEG2000 이미지 파일의 확장자는 .jp2 와 .j2k 가 보통 쓰인다. .j2k 파일은 JPEG2000의 로우 이미지 스트림 포맷이고, jp2는 로우 이미지 스트림에 이미지에 대한 추가 정보를 덧씌운 컨테이너 포맷이다.

JPEG XR 소개

2006년 마이크로 소프트가 새로운 이미지 포맷을 만들어서 발표를 했으며, 마이크로 소프트가 이 포맷으로 JPEG 포맷을 대치하려 한다는 기사가 여기저기 나왔던 적이 있었다. 링크: zdnet 기사

포맷은 만들었지만, 아직 지원하는 프로그램도 없고 지원하는 기기도 없어서 좀 조용히 지나간다 했었는데, 어느순간 마소는 Windows Media Photo 라는 MS적인 이름을 버리고, HD Photo라는 이름으로 포맷이름을 바꾸어서 이 포맷을 차세대 영상 표준 포맷으로 바꾸는 작업을 진행하고 있었다. 링크: HD PHOTO 홈페이지

그러더니 몇달전 드디어 HD Photo 라는 이름마저도 버리고 JPEG XR이라는 이름으로 JPEG 그룹에서 표준화 검토를 한다는 소식이 들려오기 시작했다. 관련 기사를 보면, 2007년 검토 작업에 들어갔으며, 별 문제가 없는한 2008년 HD Photo는 JPEG XR이라는 이름으로 JPEG2000 과 더불어JPEG의 뒤를 이을 차세대 영상 포맷이 될꺼라는 거다.

위에서 언급한 JPEG2000처럼 JPEG XR은 JPEG 보다 2배 정도의 압축 효율을 보여준다. 즉 100KB의 JPEG파일과 동일한 화질을 JPEG2000과 JPEG XR파일은 50KB의 파일로 만들 수 있다는 것이다.

사실 압축 효율만으로 따지면 JPEG XR은 JPEG2000보다 그다지 우수하지 않다. MSU 에서 비교한 자료를 보면 JPEG2000이 훨씬 나중에 만들어진 JPEG XR보다 동일 용량대비 화질이 더 우수다하고 평가를 내리고 있다. (JPEG XR을 만들고 있는 BILL CROW는 자신의 블로그에서 그렇지 않다고 반박하고 있다.) MSU 와 BILL CROW의 내용을 살펴보면, 결론은 JPEG2000이나 JPEG XR이나 JPEG보다는 우수하지만, 결국 압축율은 고만고만 하다는 것이 내 결론이다. 직접 몇가지 테스트도 해 보았지만, 서로 압축방식이 달라서 어떤 경우는 JPEG2000이, 어떤 경우는 JPEG XR이 더 보기 좋았다.(SNR 테스트는 안해 봤다는 의미)

그렇다면, JPEG XR의 존재 의미는 무엇일까? 테스트를 위해서 HD Photo Device Porting Kit 1.0을 다운로드 받아서 JPEG XR 디코더를 만들고 속도를 테스트 해 보았다. 얼래? 속도가 빨랐다. 다운로드 받은 소스는 MMX, SSE 와는 거리가 먼 C로 된 소스였음에도 불구하고, JPEG2000의 KAKADU와 비슷한 속도를 내는 것이아닌가? 윗글에서 JPEG2000이 성공하지 못한 이유를 그놈의 속도 때문이라고 정의를 내렸는데, JPEG XR은 단순히 C로 된 소스가 최적화한 상용 라이브러리인 KAKADU 보다도 빠른것 이었다. 더군다나 JPEG XR은 부동소수점 연산을 사용하지 않고, 정수연산만으로 만들어 졌기 때문에 PC이외의 휴대용 기기에 포팅이 무척 쉽다는 설명도 얻을 수 있었다. 즉, 디카에서 찍은 사진을 JPEG2000으로 저장하는건 무척 힘들지만 JPEG XR로 만드는것은 조만간 가능해 질것이라는 것이다.

공개된 소스를 살펴보고, 관련 글을 보면서 JPEG XR의 장점은 명확해져 갔다. 기존의 이미지 포맷은 RGB를 8비트(256단계)나 12비트로만 저장하였지만 JPEG XR은 32BIT까지 지원 가능하다라고 하는데, 사실 이거는 하이엔드급 디카에나 바랄 사항이니까 뭐 그런가 보다 했는데, JPEG XR은 알파 채널을 지원해서 저장하는것도 가능하고, 비손실 압축도 지원한다는 것이다. 특히 비손실 압축을 할 경우 압축율이 기존 비손실 압축 포맷의 최강자였던 PNG포맷보다도 좋다는 것이다.

JPEG XR의 장점을 열거해 보자면

MS가 특허권에 대한 권리 행사를 하지 않기로 약속했기 때문에 완전 무료 사용이 가능한 포맷이다.

손실압축을 사용할 경우, 효율이 JPEG보다 두배정도 뛰어나다.

JPEG 보다 훨씬 정밀도가 높은 데이터 포맷의 저장이 가능하다.

JPEG2000 보다 영상 처리 속도가 빠르다. PC뿐만 아니라 정수연산만 가능한 휴대용 기기로의 포팅이 쉽다.

비손실 압축을 지원한다. 비손실 압축 저장시 PNG보다 압축 효율이 뛰어나다. 즉, 디카에서 RAW포맷 저장시 비손실 압축 저장용 포맷으로 사용한다던가 하는것이 가능하다.

알파 채널을 지원한다. 반투명한 이미지를 처리할 수 있다는 의미이다. 기존에는 PNG포맷이 이 용도로 많이 쓰였다.

애니메이션 GIF처럼, 하나의 파일에 여러장의 이미지를 저장하는것이 가능하다. 즉, 웹상에서 ANIMATION GIF보다 훨씬 높은 압축 효율로 에니메이션을 구현하는것이 가능하다.

즉, 기존에 존재하는 모든 이미지 포맷의 장점을 하나의 포맷에 담아버린것이다. 헉쓰...

JPEG XR은 Windows Vista에서는 Windows Media Photo라는 이름으로 지원되고 있으며 확장자는 .wdp 를 사용하고 있다. 하지만, 포맷의 이름이 HD Photo로 바뀌면서 앞으로는 .hdp 라는 확장자를 표준 확장자 포맷으로 사용할 예정이다. 현재 JPEG XR 이라는 이름으로 표준화 작업이 진행되고 있지만, HD Photo라는 이름이 아마도 계속 사용될 듯 하다.

결론

- JPEG XR(혹은 HD PHOTO) 킹왕짱~ 굿!용

 http://www.kippler.com/doc/jpeg2000_vs_jpegxr/

Java HashMap은 어떻게 동작하는가?

이 글은 Java 7과 Java 8을 기준으로 HashMap이 어떻게 구현되어 있는지 설명합니다. HashMap 자체의 소스 코드는 Oracle JDK나 OpenJDK나 같기 때문에, 이 글이 설명하는 HashMap 구현 방식은 Oracle JDK와 OpenJDK 둘 모두에 해당한다고 할 수 있습니다. Java가 아닌 다른 언어를 주로 사용하는 개발자라 하더라도, Java의 HashMap이 현재 어떻게 구현되어 있고, 어떻게 발전되었는지 알면 라이브러리나 프레임워크 구현에 대한 혜안을 얻을 수 있을 것이라고 기대합니다.

HashMap은 Java Collections Framework에 속한 구현체 클래스입니다. Java Collections Framework는 1998년 12월에 발표한 Java 2에서 정식으로 선보였습니다. Map 인터페이스 자체는 Java 5에서 Generic이 적용된 것 외에 처음 선보인 이후 변화가 없지만, HashMap 구현체는 성능을 향상시키기 위해 지속적으로 변화해 왔습니다.

이 글에서는 어떤 방식으로 HashMap 구현체의 성능을 향상시켰는지 소개합니다. 구체적으로 다루는 내용은 Amortized Constant Time을 위하여 어떻게 해시 충돌(hash collision) 가능성을 줄이고 있는가에 대한 것입니다.

HashMap과 HashTable

이 글에서 말하는 HashMap과 HashTable은 Java의 API 이름이다. HashTable이란 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java 2에서 처음 선보인 Java Collections Framework에 속한 API다. HashTable 또한 Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable이 제공하는 기능은 같다. 다만 HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대으로 성능상 이점이 있다. 보조 해시 함수가 아니더라도, HashTable 구현에는 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있다. HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기 때문에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다고 할 수 있다.

HashMap과 HashTable을 정의한다면, '키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array'라고 할 수 있다. 이 associate array를 지칭하는 다른 용어가 있는데, 대표적으로 Map, Dictionary, Symbol Table 등이다.

예제 1 HashTable과 HashMap의 선언부

public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

associative array를 지칭하기 위하여 HashTable에서는 Dictionary라는 이름을 사용하고, HashMap에서는 그 명칭이 그대로 말하듯이 Map이라는 용어를 사용하고 있다.

map(또는 mapping)은 원래 수학 함수에서의 대응 관계를 지칭하는 용어로, 경우에 따라서는 함수 자체를 의미하기도 한다. 즉 HashMap이란 이름에서 알 수 있듯이, HashMap은 키 집합인 정의역과 값 집합인 공역의 대응에 해시 함수를 이용한다.

그림 1 함수에서의 사상(map)

해시 분포와 해시 충돌

동일하지 않은 어떤 객체 X와 Y가 있을 때, 즉 X.equals(Y)가 '거짓'일 때 X.hashCode() != Y.hashCode()가 같지 않다면, 이때 사용하는 해시 함수는 완전한 해시 함수(perfect hash functions)라고 한다(: S는 모든 객체의 집합, h는 해시 함수).

Boolean같이 서로 구별되는 객체의 종류가 적거나, Integer, Long, Double 같은 Number 객체는 객체가 나타내려는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있다. 하지만 String이나 POJO(plain old java object)에 대하여 완전한 해시 함수를 제작하는 것은 사실상 불가능하다.

적은 연산만으로 빠르게 동작할 수 있는 완전한 해시 함수가 있다고 하더라도, 그것을 HashMap에서 사용할 수 있는 것은 아니다. HashMap은 기본적으로 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는 데, 결과 자료형은 int다. 32비트 정수 자료형으로는 완전한 자료 해시 함수를 만들 수 없다. 논리적으로 생성 가능한 객체의 수가 2³²보다 많을 수 있기 때문이며, 또한 모든 HashMap 객체에서 O(1)을 보장하기 위해 랜덤 접근이 가능하게 하려면 원소가 2³²인 배열을 모든 HashMap이 가지고 있어야 하기 때문이다.

따라서 HashMap을 비롯한 많은 해시 함수를 이용하는 associative array 구현체에서는 메모리를 절약하기 위하여 실제 해시 함수의 표현 정수 범위 보다 작은 M개의 원소가 있는 배열만을 사용한다. 따라서 다음과 같이 객체에 대한 해시 코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.

예제 2 해시를 사용하는 associative array 구현체에서 저장/조회할 해시 버킷을 계산하는 방법

int index = X.hashCode() % M;

이 코드와 같은 방식을 사용하면, 서로 다른 해시 코드를 가지는 서로 다른 객체가 1/M의 확률로 같은 해시 버킷을 사용하게 된다. 이는 해시 함수가 얼마나 해시 충돌을 회피하도록 잘 구현되었느냐에 상관없이 발생할 수 있는 또 다른 종류의 해시 충돌이다. 이렇게 해시 충돌이 발생하더라도 키-값 쌍 데이터를 잘 저장하고 조회할 수 있게 하는 방식에는 대표적으로 두 가지가 있는데, 하나는 Open Addressing이고, 다른 하나는 Separate Chaining이다. 이 둘 외에도 해시 충돌을 해결하기 위한 다양한 자료 구조가 있지만, 거의 모두 이 둘을 응용한 것이라고 할 수 있다.

그림 2 Open Addressing과 Separate Chaining 구조

Open Addressing은 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다. 데이터를 저장/조회할 해시 버킷을 찾을 때에는 Linear Probing, Quadratic Probing 등의 방법을 사용한다.

Separate Chaining에서 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분(head)이다.

둘 모두 Worst Case O(M)이다. 하지만 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비하여 캐시 효율이 높다. 따라서 데이터 개수가 충분히 적다면 Open Addressing이 Separate Chaining보다 더 성능이 좋다. 하지만 배열의 크기가 커질수록(M 값이 커질수록) 캐시 효율이라는 Open Addressing의 장점은 사라진다. 배열의 크기가 커지면, L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문이다.

Java HashMap에서 사용하는 방식은 Separate Channing이다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문이다. 게다가 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다(여기에 대해서는 "보조 해시 함수"에서 설명하겠다).

예제 3 Java 7에서의 해시 버킷 관련 구현

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// transient로 선언된 이유는 직렬화(serializ)할 때 전체, table 배열 자체를 직렬화하는 것보다
// 키-값 쌍을 차례로 기록하는 것이 더 효율적이기 때문이다.


static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() { … }
public final V getValue() { …}
        public final V setValue(V newValue) { … }
        public final boolean equals(Object o) { … }
        public final int hashCode() {…}
        public final String toString() { …}

void recordAccess(HashMap<K,V> m) {… }

void recordRemoval(HashMap<K,V> m) {…}
}

Separate Chaining 방식을 사용하기 때문에, Java 7에서의 put() 메서드 구현은 예제 4에서 보는 것과 같다.

예제 4 put() 메서드 구현

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {  
            inflateTable(threshold); // table 배열 생성
        }

        // HashMap에서는 null을 키로 사용할 수 있다.
        if (key == null)
            return putForNullKey(value);
        // value.hashCode() 메서드를 사용하는 것이 아니라, 보조 해시 함수를 이용하여 
        // 변형된 해시 함수를 사용한다. "보조 해시 함수" 단락에서 설명한다.
        int hash = hash(key);

        // i 값이 해시 버킷의 인덱스이다.
        // indexFor() 메서드는 hash % table.length와 같은 의도의 메서드다.
        int i = indexFor(hash, table.length);

				

        // 해시 버킷에 있는 링크드 리스트를 순회한다.
        // 만약 같은 키가 이미 저장되어 있다면 교체한다.
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        // 삽입, 삭제 등으로 이 HashMap 객체가 몇 번이나 변경(modification)되었는지
        // 관리하기 위한 코드다.
        // ConcurrentModificationException를 발생시켜야 하는지 판단할 때 사용한다.
        modCount++;

				
        // 아직 해당 키-값 쌍 데이터가 삽입된 적이 없다면 새로 Entry를 생성한다. 
        addEntry(hash, key, value, i);
        return null;
    }

그러나 Java 8에서는 예제 4에서 볼 수 있는 것보다 더 발전된 방식을 사용한다.

Java 8 HashMap에서의 

Separate Chaining

Java 2부터 Java 7까지의 HashMap에서 Separate Chaining 구현 코드는 조금씩 다르지만, 구현 알고리즘 자체는 같았다. 만약 객체의 해시 함수 값이 균등 분포(uniform distribution) 상태라고 할 때, get() 메서드 호출에 대한 기댓값은 이다. 그러나 Java 8에서는 이보다 더 나은 을 보장한다. 데이터의 개수가 많아지면, Separate Chaining에서 링크드 리스트 대신 트리를 사용하기 때문이다.

데이터의 개수가 많아지면 과 의 차이는 무시할 수 없다. 게다가 실제 해시 값은 균등 분포가 아닐뿐더러, 설사 균등 분포를 따른다고 하더라도 birthday problem이 설명하듯 일부 해시 버킷 몇 개에 데이터가 집중될 수 있다. 그래서 데이터의 개수가 일정 이상일 때에는 링크드 리스트 대신 트리를 사용하는 것이 성능상 이점이 있다.

링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다. 예제 5에서 보듯 Java 8 HashMap에서는 상수 형태로 기준을 정하고 있다. 즉 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경한다. 트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문이다. 8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.

예제 5 Java 8 HashMap의 TREEIFY_THRESHOLD와 UNTREEIFY_THRESHOLD

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

Java 8 HashMap에서는 Entry 클래스 대신 Node 클래스를 사용한다. Node 클래스 자체는 사실상 Java 7의 Entry 클래스와 내용이 같지만, 링크드 리스트 대신 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 것이 Java 7 HashMap과 다르다.

이때 사용하는 트리는 Red-Black Tree인데, Java Collections Framework의 TreeMap과 구현이 거의 같다. 트리 순회 시 사용하는 대소 판단 기준은 해시 함수 값이다. 해시 값을 대소 판단 기준으로 사용하면 Total Ordering에 문제가 생기는데, Java 8 HashMap에서는 이를 tieBreakOrder() 메서드로 해결한다.

예제 6 Java 8 HashMap의 Node 클래스

transient Node<K,V>[] table;


static class Node<K,V> implements Map.Entry<K,V> {
  // 클래스 이름은 다르지만, Java 7의 Entry 클래스와 구현 내용은 같다. 
}


// LinkedHashMap.Entry는 HashMap.Node를 상속한 클래스다.
// 따라서 TreeNode 객체를 table 배열에 저장할 수 있다.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

				
        TreeNode<K,V> parent;  
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;   

        // Red Black Tree에서 노드는 Red이거나 Black이다.
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        final TreeNode<K,V> root() {
        // Tree 노드의 root를 반환한다. 
        }

        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        // 해시 버킷에 트리를 저장할 때에는, root 노드에 가장 먼저 접근해야 한다.
        }


        // 순회하며 트리 노드 조회 
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
        final TreeNode<K,V> getTreeNode(int h, Object k) {}


        static int tieBreakOrder(Object a, Object b) {
         // TreeNode에서 어떤 두 키의comparator 값이 같다면 서로 동등하게 취급된다.
         // 그런데 어떤 두 개의 키의 hash 값이 서로 같아도 이 둘은 서로 동등하지 
         // 않을 수 있다. 따라서 어떤 두 개의 키에 대한 해시 함수 값이 같을 경우, 
         // 임의로 대소 관계를 지정할 필요가 있는 경우가 있다. 
        }


        final void treeify(Node<K,V>[] tab) {
          // 링크드 리스트를 트리로 변환한다.
        }


				
        final Node<K,V> untreeify(HashMap<K,V> map) {
          // 트리를 링크드 리스트로 변환한다.
        }

        // 다음 두 개 메서드의 역할은 메서드 이름만 읽어도 알 수 있다.
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {}
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {}


        // Red Black 구성 규칙에 따라 균형을 유지하기 위한 것이다.
        final void split (…)
        static <K,V> TreeNode<K,V> rotateLeft(…)
        static <K,V> TreeNode<K,V> rotateRight(…)
        static <K,V> TreeNode<K,V> balanceInsertion(…)
        static <K,V> TreeNode<K,V> balanceDeletion(…)


				
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
        // Tree가 규칙에 맞게 잘 생성된 것인지 판단하는 메서드다.
        }
    }

해시 버킷 동적 확장

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다. 이렇게 해시 버킷 개수를 늘리면  값도 작아져, 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.

해시 버킷 개수의 기본값은 16이고, 데이터의 개수가 임계점에 이를 때마다 해시 버킷 개수의 크기를 두 배씩 증가시킨다. 버킷의 최대 개수는 2³⁰개다. 그런데 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다. HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않게 할 수 있다.

예제 7 Java 7 HashMap에서의 해시 버킷 확장

  // 인자로 사용하는 newCapacity는 언제나 2a이다.
void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;

        // MAXIMIM_CAPACITY는 230이다.
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];

				
        // 새 해시 버킷을 생성한 다음 기존의 모든 키-값 데이터들을
        // 새 해시 버킷에 저장한다.
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }


    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        // 모든 해시 버킷을 순회하면서
        for (Entry<K,V> e : table) {
            // 각 해시 버킷에 있는 링크드 리스트를 순회하면서
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 해시 버킷 개수가 변경되었기 때문에
                // index 값(hashCode % M)을 다시 계산해야 한다. 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

해시 버킷 크기를 두 배로 확장하는 임계점은 현재의 데이터 개수가 'load factor * 현재의 해시 버킷 개수'에 이를 때이다. 이 load factor는 0.75 즉 3/4이다. 이 load factor 또한 HashMap의 생성자에서 지정할 수 있다.

임계점에 이르면 항상 해시 버킷 크기를 두 배로 확장하기 때문에, N개의 데이터를 삽입했을 때의 키-값 쌍 접근 횟수는 다음과 같이 분석할 수 있다.

즉 기본 생성자로로 생성한 HashMap을 이용하여 많은 양의 데이터를 삽입할 때에는, 최적의 해시 버킷 개수를 지정한 것보다 약 2.5배 많이 키-값 쌍 데이터에 접근해야 한다. 이는 곧 수행 시간이 2.5배 길어진다고 할 수 있다. 따라서 성능을 높이려면, HashMap 객체를 생성할 때 적정한 해시 버킷 개수를 지정해야 한다.

그런데 이렇게 해시 버킷 크기를 두 배로 확장하는 것에는 결정적인 문제가 있다. 해시 버킷의 개수 M이 2^a 형태가 되기 때문에, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다는 것이다. 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.

이 때문에 보조 해시 함수가 필요하다.

보조 해시 함수

index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있다. 그러나 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 해야 한다.

보조 해시 함수(supplement hash function)의 목적은 '키'의 해시 값을 변형하여, 해시 충돌 가능성을 줄이는 것이다. 이 보조 해시 함수는 JDK 1.4에 처음 등장했다. Java 5 ~ Java 7은 같은 방식의 보조 해시 함수를 사용하고, Java 8부터는 다시 새로운 방식의 보조 해시 함수를 사용하고 있다.

예제 8 Java 7 HashMap에서의 보조 해시 함수

final int hash(Object k) {
        // Java 7부터는 JRE를 실행할 때, 데이터 개수가 일정 이상이면
        // String 객체에 대해서 JVM에서 제공하는 별도의 옵션으로
        // 해시 함수를 사용하도록 할 수 있다.
        // 만약 이 옵션을 사용하지 않으면 hashSeed의 값은 0이다.
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        // 해시 버킷의 개수가 2a이기 때문에 해시 값의 a비트 값만을 
        // 해시 버킷의 인덱스로 사용한다. 따라서 상위 비트의 값이 
        // 해시 버킷의 인덱스 값을 결정할 때 반영될 수 있도록
        // shift 연산과 XOR 연산을 사용하여, 원래의 해시 값이 a비트 내에서 
        // 최대한 값이 겹치지 않고 구별되게 한다.
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

그런데 Java 8에서는 Java 7보다 훨씬 더 단순한 형태의 보조 해시 함수를 사용한다.

예제 9 Java 8 HashMap에서의 보조 해시 함수

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

예제 9에서 볼 수 있는 것처럼, Java 8 HashMap 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용한다. 이유로는 두 가지가 있는데, 첫 번째는 Java 8에서는 해시 충돌이 많이 발생하면 링크드 리스트 대신 트리를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화되었기 때문이다. 두 번째로는 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다. 두 번째 이유가 좀 더 결정적인 원인이 되어 Java 8에서는 보조 해시 함수의 구현을 바꾸었다.

개념상 해시 버킷 인덱스를 계산할 때에는 index = X.hashCode() % M처럼 나머지 연산을 사용하는 것이 맞지만, M값이 2^a일 때는 해시 함수의 하위 a비트 만을 취한 것과 값이 같다. 따라서 나머지 연산 대신 '1 << a – 1' 와 비트 논리곱(AND, &) 연산을 사용하면 수행이 훨씬 더 빠르다.

String 객체에 대한 해시 함수

String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례한다.

때문에 JDK 1.1에서는 String 객체에 대해서 빠르게 해시 함수를 수행하기 위해, 일정 간격의 문자에 대한 해시를 누적한 값을 문자열에 대한 해시 함수로 사용했다.

예제 10 JDK 1.1에서의 String 클래스 해시 함수

public int hashCode() {
    int hash = 0;
     int skip = Math.max(1, length() / 8);
     for (int i = 0; i < length(): i+= skip) 
           hash = s[i] + (37 * hash);
    return hash;
}

예제 10에서 볼 수 있듯이 모든 문자에 대한 해시 함수를 계산하는 게 아니라, 문자열의 길이가 16을 넘으면 최소 하나의 문자를 건너가며 해시 함수를 계산했다.

그러나 이런 방식은 심각한 문제를 야기했다. 웹상의 URL은 길이가 수십 글자에 이르면서 앞 부분은 동일하게 구성되는 경우가 많다. 이 경우 서로 다른 URL의 해시 값이 같아지는 빈도가 매우 높아질 수 있다는 문제가 있다. 따라서 이런 방식은 곧 폐기되었고, 예제 11에서 보는 방식을 현재의 Java 8까지도 계속 사용하고 있다.

예제 11 Java String 클래스 해시 함수

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

예제 11은 Horner's method를 구현한 것이다. Horner's method는 다항식을 계산하기 쉽도록 단항식으로 이루어진 식으로 표현하는 것이다. 즉 예제 11에서 계산하고자 하는 해시 값 h는 다음과 같다.

이렇게 단항식을 재귀적으로 사용하여 다항식 연산을 표현할 수 있다.

String 객체 해시 함수에서 31을 사용하는 이유는, 31이 소수이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다. 31N=32N-N인데, 32는 2⁵이니 어떤 수에 대한 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은, (N << 5) – N과 같다. 31을 곱하는 연산은 이렇게 최적화된 머신 코드로 생성할 수 있기 때문에, String 클래스에서 해시 값을 계산할 때에는 31을 승수로 사용한다.

Java 7에서 String 객체에 대한 별도의 해시 함수

JDK 7u6부터 JDK 7u25까지는 HashMap에 저장된 키-값 쌍이 일정 개수 이상이면 String 객체에 한하여 별도의 해시 함수를 사용할 수 있게 하는 기능이 있다. 이 기능은 JDK 7u40부터는 삭제되었고, 당연히 Java 8에도 해당 기능은 없다. 여기서 말하는 '일정 개수 이상'이나 '별도의 해시 함수 사용 여부 지정'은 JVM을 가동할 때 옵션으로 지정할 수 있다.

예제 12 Java 7의 String에 대한 hash32() 메서드

hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;

….

int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }


….

// String 클래스에 있는 hash32() 메서드
int hash32() {
        int h = hash32;
        if (0 == h) {
           h = sun.misc.Hashing.murmur3_32(HASHING_SEED, value, 0, value.length);
           h = (0 != h) ? h : 1;
           hash32 = h;
        }
        return h;
    }

JDK 7u6부터 JDK 7u25까지는 jdk.map.althashing.threshold 옵션을 지정하면, HashMap에 저장된 키-값 쌍이 일정 개수 이상일 때 String 객체에 String 클래스의 hashCode() 메서드 대신 sun.misc.Hashing.stringHash32() 메서드를 사용할 수 있게 했다. sun.misc.Hashing.stringHash32() 메서드는 String 클래스의 hash32() 메서드를 호출하게 한 것이고, hash32() 메서드는 MurMur 해시를 구현한 것이다. 이 MurMur 해시를 이용하여 String 객체에 대한 해시 충돌을 매우 낮출 수 있었다고 한다.

그러나 부작용도 있다. MurMur 해시는 hash seed를 필요로 하는데, 이를 위한 것이 sun.misc.Hashing.randomHashSeed() 메서드다. 이 메서드에서는 Random.nextInt() 메서드를 사용한다. Random.nextInt() 메서드는 compare and swap 연산(이하 CAS 연산)을 사용하는 AtomicLong을 사용하는데, CAS 연산은 코어가 많을수록 성능이 떨어진다. 즉 JDK 7u6부터 등장한 String 객체에 대한 별도의 해시 함수는 멀티 코어 환경에서는 성능이 하락했고, 이런 문제로 인해 JDK 7u40부터는 해당 기능을 사용하지 않는다. 당연히 Java 8도 사용하지 않는다.

마치며

지금까지 설명한 내용을 요약하면, Java HashMap에서는 해시 충돌을 방지하기 위하여 Separate Chaining과 보조 해시 함수를 사용한다는 것, Java 8에서는 Separate Chaining에서 링크드 리스트 대신 트리를 사용하기도 한다는 것, 그리고 String 클래스의 hashCode() 메서드에서 31을 승수로 사용하는 이유는 성능 향상 도모를 위한 것이라고 정리할 수 있다.

HashMap은 첫 등장 이후, 성능 향상을 위하여 꾸준하게 개선되어 왔다. JDK 1.4에서 처음 등장한 보조 해시 함수와 Java 8의 트리 노드가 대표적인 예다.

그러나 Java 7의 일부 버전에서 사용했던 MurMur 해시처럼 성능 향상을 위하여 시도했던 것이, 결과적으로 좋지 않아 결국에는 삭제되기도 하고, 많은 해시 함수가 균등 분포 결과 값을 내도록 잘 작성됨에 따라 기존보다 더 단순한 형태의 보조 해시 함수를 사용하도록 변화하기도 했다.

웹 애플리케이션 서버의 경우에는 HTTPRequest가 생성될 때마다, 여러 개의 HashMap이 생성된다. 수많은 HashMap 객체가 1초도 안 되는 시간에 생성되고 또 GC(garbage collection) 대상이 된다. 컴퓨터 메모리 크기가 보편적으로 증가하게 됨에 따라, 메모리 중심적인 애플리케이션 제작도 늘었다. 따라서 갈수록 HashMap에 더 많은 데이터를 저장하고 있다고 할 수 있다.

Java 9, Java 10의 HashMap이 어떤 모습일지 지금은 알 수 없지만, 컴퓨팅 환경은 계속 변하고 그에 맞춰 HashMap 구현도 계속 변할 수밖에 없다는 것은 자명하다.

용용

 http://javafactory.tistory.com/734

애플 iOS 디바이스로 서버가 푸쉬를 보내고자 할때는, APNS 서비스를 거쳐야 한다.

푸쉬 메시지를 보내고자 하는 Provider 서버가 APNS로 푸쉬 요청을 보내면, APNS 서버가 디바이스로 푸쉬를 보내는 구조이다.

이때 APNS 서버와 Provider 서버를 어떻게 신뢰하는 지를 알아보자.

APNS 서버 입장에서는 Provider 서버가 해커가 아냐? 진짜 Provider 맞아? 하는 의문을 가질 수 있고, Provider 서버도APNS 서버가 진짜 APNS 서버가 맞는지를 확인할 수 있어야 한다.

이를 양방향 SSL(TLS:Transport Level Security)를 이용해서 해결 한다.

먼저 SSL 메커니즘에 대해서 알아보자 SSL 을 비대칭 (PKI) 키 구조의 암호화를 이용하는데, Public Key 와 Private Key두개를 가지고 있다. Public Key로 암호화를 할 수 있지만, 반대로 암호를 푸는 복호화는 Private Key를 통해서만 가능하다.

그래서 서버가 SSL 연결을 보낼 때, Public Key를 클라이언트에 내려 보내면, 클라이언트는 그 Public Key를 사용해서 메시지를 암호화 해서 서버에 전송하고, Private Key를 가지고 있는 서버만이 그 메시지를 해석할 수 있는 구조이다.

Man In The Middle attack

그런데 이 과정에서 취약점이 발생하는데, 서버가 Public Key를 내려보낼 때 중간에 해커가 서버서부터 온 Public Key를 낚아채고, 자신이 새로운 Public Key A1과 Private Key A2 페어를 만든 후, 새롭게 만든 Public Key A1을 클라이언트로 내려보낸다. 그러면 클라이언트는 이 Public Key A1을 가지고 암호화를 해서 중간에 해커에게 보내고, 해커는 이 메시지를 자신의 Private Key A2로 열어서 본후에, 다시 원래 서버가 준 Public Key로 메시지를 암호화 해서 서버에 보낸다.

이 때 클라이언트와 서버는 Public Key와 Private Key로 안전하게 통신하는 것 처럼 보이지만, 사실은 사실은 중간에 해커에 의해서 메시지가 도청되고 있는 상황이 된다. 이런 Attack 방식을 Man In The Middle attack (MITM)

Signing

이러한 Public Key가로채기를 막을려면 Public Key를 받는 클라이언트 쪽에서 이 Public Key가 APNS에서 온 것이 맞는지를 확인하면 되는데, 보통 이 Public Key는 인증서(Certificate)안에 넣어서 클라이언트에게로 배달된다. 이 때 메시지 변조를 막기 위해서 Certificate는 안에 들어 있는 메시지로 생성된 일종의 해쉬값과 같은 signature 값을 가지고 있어서,만약에 내부 메시지가 변경이 되면 원래 signature와 비교하여 메시지가 변경되었는지를 확인할 수 있다.이를 생성하는 것을 싸이닝(Signing) 이라고 하는데, 이 Signing은 Private 키로 생성되고, 이에 대한 비교는 Public Key를 통해서 할 수 있다. (Sign을 확인하기 위해서는 Sign에 사용된 Private Key에 대한 페어 Public Key를 가진 인증서를 가지고 있어야 한다. 이 Public Key를 통해서 싸이닝을 확인할 수 있다.)

Channing

이 signature를 통해서 전달되는 메시지가 변조되는 것을 막을 수 는 있지만 위의 MITM attack 처럼 인증서 자체를 통째로 바꿔칠 수 있기 때문에, 이 인증서가 믿을만한 인증서인지를 확인해야 한다. 인증서에는 인증서를 발급한 기관 (CA : Certificate Authority)정보가 들어 있는데, “XXX에서 인증서를 발급함” 이라는 정보가 들어 있다.

그런데 문제는 이 인증서를 발급한 기관을 믿을 수 있냐는 거다. 구멍가게가 될 수 도 있고

은행과 같은 인증된 기관이 될 수 도 있다. 그래서 사용하는 기법에 인증서 Channing 기법인데, 인증서를 발급한 사람이 이 인증서를 신뢰된 기관에 가서 인증을 받은 후, 그 인증 정보를 인증서에 추가하는 방식이다.

아래 그림을 보자, 맨 아래의 Engineering CA는 자체 적으로 인증서를 발급하였다. 이 인증서를 USA CA certificate에 보내서 추가 인증을 받는다. 그런데, 이 USA CA certificate 인증서는 이미 신뢰된 기관으로부터 인증을 받은 인증서이기 때문에, 이 신뢰된 기관의 인증 정보가 추가되게 된다. (신뢰된 인증 기관으로부터 인증서에 서명을 받으려면 회사 정보,신상 정보 등을 받은 후에 신원 확인 절차를 거쳐야만이 서명을 받을 수 있다.)

(출처 : https://developer.mozilla.org/en-US/docs/Introduction_to_Public-Key_Cryptography)

그래서 최종 인증서 모양은

이러한 형태가 되고, 클라이언트는 이 인증서 chain을 통해서 Root CA가 신뢰된 인증서인지를 확인하면 이 전체 인증서가 신뢰된 인증서임을 확인할 수 있다. (네트워크를 통해서 Root CA가 맞는지를 확인하게 되고, 만약에 Root CA라도 외부로 노출이 되었을 경우에 Revoked List라는 유출된 인증서 목록을 유지함으로써 인증서가 문제가 없는 인증서인지를 확인할 수 있다.)

이러한 절차를 거치면 MITM Attack을 통한 감청을 막을 수 있다.

다음 문제는 클라이언트 입장에서는 서버가 신뢰할 수 있는 서버인지를 알 수 있다. (Provider는 이 Root CA를 통해서 서버가 APNS 서버임을 알 수 있다.)

=> 추가 : RootCA에 대해서는 인증해줄 기관이 없으므로 Self Signning을 함 (참고 : http://lesstif.com/pages/viewpage.action?pageId=6979614 )

Mutual SSL

그러나 서버 입장에서는 클라이언트가 Provider서버가 맞는지? 를 확인할 필요가 있다. 이것이 인증 (authentication) 과정인데, TLS(SSL) 연결이 안전하게 설정된 후에, 사용자 ID,PASSWD를 넣어서 클라이언트(Provider)를 확인하는 방법도 있지만, 조금 더 확실한 방법으로, 클라이언트가 발급한 인증서를 사용하는 방식을 사용한다.

이 방식이 양방향 SSL 방식 (Mutual SSL) 인데, SSL 연결이 될 때 서버가 클라이언트에게 Public Key 를 내려 보내는 방식과 마찬가지로 클라이언트가 서버에게 Public Key를 전송하고 메시지를 클라이언트의 Private Key를 이용해서 암호화 해서 보내는 방법이다.

이 때 클라이언트에서 서버로 전송하는 Public Key는 인증서를 통해서 전달이 되게 되고, 인증서에는 인증서 발급 기관등의 정보가 들어가 있기 때문에, 이를 통해서 클라이언트를 인증을 할 수 있다.

APNS의 CSR

그래서 APNS의 경우에는 Service Provider가 Private/Public Key pair 를 생성한 후에, Public Key만을 담은 인증서를 생성하여, 웹사이트를 통해서 Service Provider 업체에 대한 정보와 함께, 싸인을 요청한다.

싸인을 진행할 때 애플은 인증서에 대한 고유 ID등을 통해서 이 인증서를 통한 호출이 어느 기관(업체)에서 들어오는지를 맵핑 해놓고, 향후 양방향 SSL 연결시에 이 정보를 가지고 클라이언트를 판독할 수 있다.

이를 기반으로 전체 서버간의 플로우를 보면

1.  Provider는 Private Key를 생성한다

2.  이 Private Key를 기반으로 *.csr 파일(인증서 싸인 요청 파일)을 만든다. 이 파일에는 Public key가 들어 있는 인증서와 싸이닝을 요청하는 Provider의 업체 정보들이 들어가 있다.

3.  Provider는 애플 포탈에 들어가서 이 csr 파일을 업로드 한다.

4.  애플 포탈은 csr 파일을 기반으로 인증서(certificate)를 생성한후에, 애플의 인증서를 이용해서 싸인을 추가해서Provider에게 돌려준다.

5.  Provider는 4에서 받은 인증서(public key가 들어 있는)와 1에서 생성된 Private Key를 Provider 서버내에 설치 한다.

6.  이때 1에서 생성한 Private Key,그리고 애플이 싸이닝하여 추가된 Public Key 가 들어 있는 인증서, 인증서 체인에 사용된 모든 인증서를 추가해서 한 파일(*.p12)에 넣는다.(*.p12 파일 포맷은 X.509를 지원하는 파일 포맷중에 유일하게 Private Key를 같이 넣을 수 있는 포맷이다.)

APNS와 Provider간의 Trust

다음 통신이 이루어지게 되면, 아래 그림과 같이

1.  Provider Server가 TLS 연결을 요청한다.

2.  APNS 서버는 certificate(인증서)에 public key를 넣어서 내려 보낸다.

3.  Provider는 이 인증서의 Root CA를 확인하여, 이 인증서가 애플에서 온 정상적인 인증서임을 확인한다. (Provider가 상대편이 APNS임을 확인함)

4.  Provider는 앞의 CSR에 의해 생성된 인증서를 APNS에 보낸다.

5.  APNS는 4에서 온 인증서에 애플의 인증서로 Sign 이 되어 있는 것을 확인하고, 클라이언트가 (Provider) 합법적인 클라이언트임을 확인하고,어떤 사용자인지를 판독한다. (APNS가 Provider가 누구인지를 확인하였다.)

6.  마지막으로 양 서버간의 신뢰된 TLS(SSL)연결이 성립되었다.

 http://bcho.tistory.com/960