SLENDER ANKLES's 개발블로그

서블릿을 시작하기 전에 웹 어플리케이션 및 기초적 용어와 과정에 대해서 공부를 시작해보고자 한다.

웹 애플리케이션을 개발하다보면 다음과 같은 용어에 대해서 정리할 필요가 있게된다.

SOAP(Simple Object Access Protocol)과 RESTful(REpresentational State Transfer)에 대해서 아는가?

 SOAP  

일반적으로 널리 알려진 HTTP, HTTPS, SMTP 등을 통해 XML 기반의 메시지를 컴퓨터 네트워크 상에서 교환하는 프로토콜. SOAP은 프로그래밍 언어마다 지원해주는 것이 필요하다.

 REST  

기본 HTTP 프로토콜의 메소드 GET/PUT/POST/DELETE를 이용하여 서비스 제공자에게 서비스를 요청하여 JSON, XML, RSS 등으로 리소스를 반환하는 것을 말한다. 프로그래밍 언어에 독립적이다.

프록시서버(Proxy Server)란 무엇인가?

클라이언트와 서버 사이에서 통신을 중계해 주는 컴퓨터나 프로그램을 말한다.

 프록시 서버는 두는 이유 

1) 빠른 전송을 위하여 서버의 응답 결과를 캐시해 두는 것

예를 들어 클라이언트의 요청이 이전에 프록시 서버에 캐시되어있다면 서버에 요청을 생략하고 바로 응답해 줄 수 있게 된다.

2) 보안상의 이유로 프록시 서버를 둔다.

외부로 전달되는 데이터를 검사하여 특정 단어가 포함된 자료의 송, 수신을 차단하거나 보안 팀에 경고메시지를 전달 할 수 있게 된다.

웹 환경에서의 Server-Client 구조의 장점

이전의 서버 - 클라이언트 구조는 비즈니스 로직이 클라이언트에 있었기 때문에 

변경이 필요하게 되면 클라이언트의 프로그램을 다시 깔아야 한다. 

하지만 웹 환경에서의 서버 클라이언트의 구조에서는 클라이언트는 UI의 역할만 하게 된다. 

변경이 필요하더라도 서버에서만 바꾸어주면 된다. 

배치하는 즉시, 사용자는 재설치 없이 추가된 기능이나 변경된 기능을 이용할 수 있게 된다. 

단점 : 다만 웹을 사용 할 때마다 UI를 계속 다운받는 형식이기 때문에 네트워크 오버헤드가 큰 편이다.

전통적인 서버-클라이언트 구조의 단점을 내세우며, 

웹 환경의 서버 클라이언트 구조에 대해서 설명해본다면...

웹 환경에서의 서버 클라이언트의 구조(CS) 역시 단점 존재. 매번 클릭할때마다 UI를 다운 받아야한다. 

하지만, 이러한 단점을 보완하고자 AJAX(Asynchronous Javascript And Xml) 등장

AJAX는 페이지를 전체를 갱신하는 것이 아니라 부분, 부분 갱신할 수 있게 해준다.

HTTP 프로토콜 이란?

HTTP 프로토콜은 웹 브라우저와 웹 서버 사이의 데이터 통신 규칙을 말한다.

즉 HTTP 통신 규약에 맞추어서 요청한다면

HTML파일을 요청하면 HTML파일을 보내주고, 이미지 파일을 요청하면 이미지 파일을 보내준다는 것이다.

http요청 응답에 대한 내부적으로 어떻게 동작하고 있는가?

요청과정(Request)

요청라인, 요청헤더, 공백라인과 요청 데이터로 구성

요청 라인(Request-Line)

요청헤더

  * 요청이나 응답 모두에 적용 할 수 있는 "일반헤더(General Header)"

  * 요청 또는 응답 둘 중에 하나에만 적용 할 수 있는 "요청 헤더 또는 응답 헤더(Request Header / Response Header)"

  * 보내거나 받는 본문 데이터를 설명하는 "엔티티 헤더(Entity-Header)"

HTTP헤더들

GET요청 

공백 라인으로 끝납니다. 서버에 보낼 데이터가 있다면 URL주소에 붙여 보냅니다.

POST요청

그에 비해 로그인이나 게시글을 등록하는 경우 POST를 사용하는데, POST요청은 공백 라인 다음에 메시지 본문이 들어갑니다.

응답과정(Response)

GET과 POST 요청 방식의 차이는 무엇인가?

URL에 데이터가 있는 것은 GET방식, URL에 데이터가 없고 메시지 본문에 있는 것은 POST방식

GET요청의 특징

- URL에 데이터를 포함 - 데이터 조회에 적합

- 바이너리 및 대용량 데이터 전송 불가

- 요청라인과 헤드 필드의 최대 크기

  * HTTP 사양에는 제한사항 없음

  * 대용량 URL로 인한 문제 발생 => 웹 서버에 따라 최대 크기 제한

  * 마이크로소프트 IIS 6.0 16KB

  * APACHE 웹 서버 8KB

GET요청의 데이터 전달 형식은 어떻게 되는가?

서비스 주소 ? V1 = 23 & V2 = 15

서비스주소와 데이터를 ? 라는 문자를 이용해서 구분한다.

예) http://www.naver.com?v1=23&v2=15

GET 요청의 장점은 무엇인가?

URL에 데이터가 섞여 있기 때문에 결과 화면을 다른 사람들과 공유 할 수 있다. 

링크를 클릭하게 되면 바로 결과화면을 볼 수 있다.

GET 요청의 문제점은 무엇인가?

(1) 보안에 좋지 않다.

주소에 데이터가 섞여있기 때문에 사용자의 로그인이나 중요 정보 요청에서 데이터가 밖으로 보인다.

그렇기 때문에 보안상의 이슈가 발생 할 수 있다. 

(2) 바이너리 데이터를 전송 할 수 없다.

파일의 데이터는 URL에 붙여서 전송 할 수 없다.

BASE 64라는 인코딩 방식을 통해 바이너리 데이터를 문자화해서 보낼 수도 있지만, URI나 헤더 정보가 너무 크면

웹 서버에서 처리 할 수 없다.

이런 것은 POST를 통해 전송해야 한다.

POST요청의 특징

- URL에 데이터가 포함되지 않음 => 외부 노출 방지

- 메시지본문에 데이터 포함 => 실행 결과 공유 불가

- 바이너리 및 대용량 데이터 전송 가능

POST요청의 요청은 어떻게 이루어지는가?

요청라인과 요청헤더 다음에 공백라인이 있고 그 다음에 메시지 본문(Message Body)라 불리는 부분에 데이터가 위치해서 전송된다.

POST요청의 장점은 무엇인가?

입력값을 URL에 노출 시키지 않는다. 당연히 보안상으로 GET에 비해 좋다.

폼 태그를 통해 보내진 POST데이터는 Content-Length 와 Content-Type 등으로 구분한다.

Content-Type은 기본적으로 application/x-www-form-urlencoded형식으로 인코딩되어 보내진다.

POST요청의 문제점은 무엇인가?

(1) 요청 결과를  공유 할 수 없다.

즐겨찾기, 메일 등으로 그 결과값을 공유 할 수 없다.

POST요청은 데이터를 메시지 본문에 붙여서 전송하기 때문이다.

(2) GET방식과 마찬가지로 POST도 데이터를 전달 할 때 '이름=값&이름=값'형태로 보내진다.

결국 문자데이터를 보낼 때는 상관없지만 바이너리 데이터 등을 전송할 때는 이러한 '='이나 '&'값이 섞여 있을 수 있기 때문에 문제가 발생할 수 있다.

그래서 바이너리 데이터 등을 보낼 때는 멀티 파트 인코딩 방식을 통해 보내야 한다.

멀티 파트 인코딩 방식은 어떨때 사용하며 그렇게 사용하는 이유는 무엇인가?

POST형식 역시 데시지 본문에 '이름=값&이름=값'형태로 보내지기 때문에 

바이너리 데이터에 혹시 = 이나 &가 섞여있으면 문제가 발생 할 수 있다.

그래서 멀티 파트 인코딩 방식을 사용하여 요청정보와 데이터를 확실히 구분 할 수 있게 한다.

예를들어 <form>태그의 enctype 속성을 'multipart/form-data'로 지정해서 file 전송을 할 수 있게 합니다.

싱글톤 패턴이란?

인스턴스를 하나만 만들어 사용하기 위한 패턴이다.

이유?

커넥션 풀, 스레드 풀, 디바이스 설정 객체 등과 같은 경우에 인스턴스를 여러 개 만들게 되면 불필요한 자원을 사용하게 되고,

또 프로그램이 예상치 못한 결과를 낼 수 있다. 

싱글톤 패턴은 의미상 두 개의 객체(인스턴스)를 가질 수 없다. 

이를 구현하려면, 객체 생성을 위한 new 제약을 걸어야 하고, 만들어진 단일 객체를 반환 할 수 있는 메서드가 필요하다.

따라서 필요한 요소를 생각하면 다음의 세 가지가 있다.

- new를 실행 할 수 없도록 생성자에 private 접근 제어자를 지정한다.

- 유일한 단일 객체를 반환할 수 있는 정적 메서드가 필요하다.

- 유일한 단일 객체를 참조할 정적 참조 변수가 필요하다.

클라이언트 코드

해시라는 것은 DB를 공부할 때 많이 들었다. 테이블 구조에서 성능을 끌어올 때 해시구조로 변형시키는 튜닝방법이 있었다. 

또 암호화 할 때 해시라는 것을 많이 들었는데, 정확히 무엇이다 규정을 내릴 수 없는 상태였다. 해시라는 것을 정리해보겠다.

해시(Hash)

-주어진 키를 이용해서 실제 레코드의 주소를 직접적으로 계산해내는 것을 해시라고 한다. 

-임의의 데이터를 고정 길이의 데이터로 변화한 값을 해시값, 이 과정을 해시라고 한다. 

(쫌 어렵다)

해시에 대한 정의도 중요하지만 어디에 해시가 사용하는지를 알아야 한다.

해시의 궁극적인 목표

데이터 개수 N개와 무관하게 단번에 찾겠다는 것, 탐색효율이 logN도 아니라 O(1)을 지향한다!

어떻게?

키를 입력하면 해시함수를 통해서 해시테이블의 인덱스로 바로 접근한다!

해시함수(Hash Function)란?

해시함수(Hash Function)란 탐색키를 입력으로 받아 해시주소(Hash Address)를 생성하고 

이 해시 주소가 배열로 구현된 해시 테이블(Hash Table)의 인덱스가 된다.

ex) 영어 사전에서는 단어(탐색키)를 이용하여 해싱 함수를 통과하면 적절한 정수 i가 도출되는데 

이를 통해 ht[i]에 접근하면 단어에 대한 내용을 볼 수 있게 되는 것이다.

해시테이블(Hash Table)의 구조?

-해시테이블은 M개의 버켓(bucket)과 S개의 슬롯(Slot)으로 구성된다. 

-하나의 버켓은 여러 개의 슬롯을 가질 수 있다.

해시(Hash)의 방법?

1) 제산법

나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방법

레코드 키 값을 수치 자료로 간주하여 어떤 양의 정수(대개 해시 테이블의 크기)로 나눈 나머지를 홈 주소로 결정하는 간단한 방법

ex) 버킷 주소 = 키 값 % 해쉬 테이블의 크기

12 = 512 % 100

2) 제곱법

- 제곱법은 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용

- 제곱된 결과의 중간 비트는 대개 레코드의 모든 문자에 의존하므로, 레코드를 구성하는 몇 개의 문자가 같은 지라도 서로 다른 레코드 키는 다른 홈 주소를 갖게 될 확률이 높다

- 홈 주소를 얻기 위해 사용되는 비트 수는 테이블의 크기에 따라 달라지는데, 중간 부분의 자릿수를 n이라 하면 각 레코드 값들이 가지는 범위인 해시 테이블의 크기는 2n 이 된다.

- 키 값 제곱 => 해시 테이블 크기에 따라 주소 값 산출

ex) 레코드 키 값이 K = 512이고, 해시테이블의 크기가 100일 때 제곱법에 의한 레코드 주소는?

512제곱 = 262144

====> 중간 2자리 "21"최종 주소값이 됨

3) 숫자 분석법

- 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법

ex) 해시 테이블의 크기 = 1000, 홈 주소 : 0 ~ 999까지(3자리 필요) 레코드 키 값이 다음의 (a)와 같을 때 숫자 분석법을 이용하여 각 키들에 대한 홈 주소를 결정하시오.

012 - 452 - 0236   =>     426

012 - 153 - 0530   =>     150

015 - 342 - 0935   =>     395

012 - 752 - 1032   =>     702

012 - 852 - 0470   =>     840

012 - 543 - 0231   =>     512

     (레코드 키값)         (각 키의 홈 주소)

(1) (a)에서 왼쪽 3자리는 거의 같으므로 제거

(2) 왼쪽 5열, 6열, 7열, 9열 역시 동일 숫자가 많이 분포하였으므로 무시

(3) 비교적 고른 숫자 분포를 가진 4열, 8열, 10열을 선택하여 주소로  사용

4) 폴딩법

- 폴딩법은 레코드의 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더 하거나 배타적 논리합(XOR)을 취하여, 해시 테이블의 홈 주소로 이용하는 방법으로 두 가지 방법이 사용 된다.

(1) 이동 폴딩(shift Folding)

(2) 경계 폴딩(Boundary Folding)

이동폴딩 => 

P1 + P2 + P3 + P4 + P5 

= 301 + 230 + 123 + 213 + 30 = 897

897 = 홈주소

경계폴딩 => 

P1 + P2(역) + P3 + P4(역) + P5

= 301 + 032 + 123 + 312 + 30 = 798

798 = 홈주소

5) 기수변환법

- 기수 변환법은 어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방법으로, 어떤 키 값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키 값을 변환하여 해당 레코드의 홈 주소를 구한다.

- 해시 테이블의 크기가 10의 멱승으로 표현되어 변환된 해당 레코드의 주소 값이 테이블의 크기를 초과할 때는 주소 값의 최하위 자리부터 해시 테이블의 크기가 허용하는 멱승수만큼 취하여 해당 레코드의 홈 주소로 사용한다.

ex) 해시 테이블의 크기 = 10000()

- 십진수로 입력된 키 값(B2538)10을 16진수로 간주하여 그 값을 다시 10진수로 계산하는 기수 변환법을 이용하여 홈 주소를 구하시오. 

(풀이) (1 * 165) + (3 * 164) + (2 * 163) + (5 * 163) + (4 * 161) + (8 * 160)

= 1048576 + 196608 + 8192 + 1280 + 64 + 8

= (1254728)10

홈 주소 = 4728

- 레코드의 주소값 (1254728)10에서 해시 테이블이 허용하는 하위 4자리를 선택한다.

6) 무작위방법

- 난수 발생 프로그램을 이용하여 난수(random number)를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방법으로, 보통 난수는 1보다 작은 양의 실수를 산출하므로,

- 해시 테이블의 크기인 n을 산출된 난수에 곱하여 0~(n-1)까지의 범위 값으로 변환하여 사용하며, 만일 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로 사용한다.

해시충돌(Hash Collision)이란?

- 서로 다른 두 개의 탐색키와 k1과 k2에 대하여

- h(k1) = h(k2)인 경우에는 충돌이 일어난다.

- 이러한 충돌이 버켓이 할당된 슬롯 수보다 많이 발생하게 되면 

버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로우(Overflow)가 발생한다.

해시충돌을 해결하는 방법?

- 선형 검색법

- 2차 검색법

- 무작위 검색법

- 체인 이용법

* 해시 함수에 의해 같은 기억공간에 할당되어 충돌이 발생한 레코드들을 연결 리스트(Linked List)로 연결하는 방법으로

해시 테이블 자체는 포인터의 배열로 만들고, 같은 버켓에 할당되는 레코드들을 체인으로 만들어 연결한다.

=> 해시 연쇄법은 연결 리스트를 사용하므로 해시 테이블에서의 삽입이나 삭제 연산이 용이하며, 충돌의 횟수를 감소시키지는 못하지만 다른 충돌 해결 방법에 의해 해시 테이블을 검색 할 때 발생하는 소요시간을 감소 시킬 수 있다.

* 장점 

=> 충돌이 발생한 명칭들만 연결 리스트에서 검색해 주면 되므로 속도가 빠르다.

=> 삽입 가능한 명칭의 수가 해시 테이블 크기에 영향을 받지 않는다.

* 단점

=> 구조가 복잡하고 기억 장소 소모량이 많다.

검색트리가 디스크에 있는 상태로 사용되면 외부검색트리라고 함

분기(자식노드)의 수가 2개를 넘으면 다진검색트리라고 함

B-트리는 디스크 환경에서 사용하기에 적합한 외부 다진검색 트리이다.

이진트리와 B-Tree는 차이는?

이진트리와 B-Tree는 비슷하다. 

하지만 이진트리는 편향된 트리 구조가 발생할 수 있는데 반해 

1) B-Tree는 트리의 균형을 유지해주는 성질을 가지고 있어 응답속도를 보장해준다.

2) 또한 하나의 노드에 여러개의 값을 가질 수 있는 성질을 가지고 있다. 이러한 성질은 하나의 노드에 여러개의 값을 가질 수 있으므로 당연히 트리의 높이도 낮아지므로 검색의 성능이 좋아질 수 있다.

하나의 노드에 많은 데이터를 가질 수 있는 점 

=> 대량의 데이터를 처리해야 하는 검색 구조에서 큰 장점

=> 대량의 데이터는 메모리보다는 하드디스크 혹은 SSD에 저장

(이러한 보조 기억 장치는 블럭 단위로 입출력을 하기 때문에 Disk I/O단위로 노드의 크기를 정할 수 있는 B-Tree가 유리)

(예를 들어 1024바이트 블럭이라면, 2바이트를 읽으나 1024바이트를 읽으나 입출력에 대한 비용은 동일하다)

이러한 장점 때문에 B트리는 데이터베이스에 이용되는 자료구조이다. 

이러한 B-Tree에 대해서 알아보자!

Balanced Tree(B-Tree)

* 이진 검색 트리의 문제점은

  - 좌우 균형이 맞지 않으면 비효율적이다. 보통 O(logN)이지만 O(N)까지 갈 수 있다.

* Balanced Tree

  - 삽입과 삭제시 필요하면 스스로 균형을 유지함

  - AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree....

  - 항상 O(logN)의 검색성능

* B-Tree란?

  - 하나의 노드에 여러자료가 배치되는 자료구조

  - 한 노드에 M개의 자료가 배치되면 M차 B-Tree

    * M이 짝수냐 홀수냐에 따라 알고리즘이 다르다.

* B-Tree의 규칙

  규칙1)

  - 노드의 자료수가 N이라면, 자식의 수는 N+1 이어야 한다.

  - 각 노드의 자료는 정렬된 상태여야 한다. 

  - 노드이 자료 Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고, Dk의 오른쪽 서브리는 Dk보다 큰 값들이어야 한다. 

  규칙2)

  - Root노드는 적어도 2개이상의 자식을 가져야 한다. 

  - Root노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다. 

  - 외부노드로 가는 경로의 길이는 모두 같다. (외부노드는 모두 같은 레벨에 있다.)

  - 입력자료는 중복될 수 없다.

* B-Tree의 검색

노드내에서는 순차검색

전체적으로 트리검색

* B-Tree의 삽입 알고리즘1

* B-Tree의 삽입 알고리즘

  - 자료는 항상 Leaf노드에 추가된다. 

    * Leaf노드의 선택은 삽입될 키의 하향 탐색에 의해 결정

  - 추가될 Leaf노드에 여유가 있다면 그냥 삽입

  - 추가될 Leaf노드에 여유가 없다면 "분할"하기

  - 분할을 위해서는 키 하나를 부모로 올려야 함

    * 부모가 꽉 차 있다면 문제!

  - 삽입을 위한 하향탐색을 하면서 꽉찬 노드는 분할해 주어야 함

* B-Tree의 삭제 알고리즘

  - 삭제하고자 하는 자료가 있는 노드가

     * 삭제 후 자료수가 M/2 이상이 되도록 보장해야 함!

  - 형제에게서 빌리기 vs 형제와 결합하기

     * 빌리기 : 형제가 M/2보다 많은 자료를 가지고 있다면

     * 결합하기 : 형제에게서 빌릴 수 없다면

  - 삭제키가 있는 노드가 내부노드인 경우

     * 대체키를 찾아 대체해야 한다. (Right Subtree중 가장 큰값으로)(이진트리와 동일)

  - 삭제를 위한 하향탐색을 하면서 자료수가 M/2이하인 노드는 형제에게 빌리든지 결합해야 함

분석과 특성

* B-Tree는 외부검색에 적합함

  - 하나의 노드크기를 Disk I/O단위의 크기로!

  - 순차검색과 트리검색의 잇점을 취함

    * B-트리는 Balanced Tree로 최악의 경우가 없음

    * 퀵정렬에서 소구간에 대한 삽입정렬이 성능이 좋았다.

    * 노드내에서 순차검색 대신 이분검색은?

Index(색인)이 가져야 할 특성

1. 일반적으로 보조 기억 장치에서의 탐색은 시간적인 부하가 많이 걸리기 때문에 탐색을 쉽게 하기 위해

file과는 별도로 index를 만들어 사용한다.

2. Index가 커질 경우 index 역시 보조 기억 장치에 저장하는데 보조 기억 장치는 상대적으로 느리므로 

보조 기억 장치의 access 횟수를 최대한 억제시켜야 한다. 

3. Index에의 access회수를 줄이기 위해서는 최대 탐색 길이 즉, 트리의 높이를 줄여야 한다. 

4. 높이를 낮추기 위해서는 하나의 노드에서 나가는 branch의 개수를 증가한다. 

=> B-Tree를 데이터베이스의 인덱스 자료구조로 사용하는 이유!