16 min to read

URL Shortener 서버 만들기 1편

Base62와 춤을

Featured image

URL Shortener 서버 만들기 1편 : Base62와 춤을

오랜만에 실용적인 글을 써볼까해요

URL 단축 기능을 구현하는 과정과 오픈소스로 공개하는 과정을 짤막하게 다뤄보려해요. 이번글은 Shoten URL을 만드는 과정을 다룰예정이에요.

URL 단축 (URL shortening) : URL 단축은 월드 와이드 웹 상의 긴 URL을 짧게 만들어 주는 기술이다. URL 단축 기능을 제공하는 서버는 HTTP 넘겨주기를 이용해 클라이언트를 긴 URL로 넘겨준다. 위키백과

예를 들어 주위 사람들에게 URL를 공유해야 할 때, 공유하고 싶은 URL이 길면 보기가 싫죠. 아래와 같이 사람이 읽고 내용을 추론할 수 있다면 크게 불편함을 느끼지는 않아요.

다만 아래와 사용자가 알 수 없는 a01626108등의 식별자로 인해서 URL이 길어지는 경우, 공유하는 사람도, 공유받는 사람도 보기 싫어요.

이런것들을 bitly.com 등의 서비스를 이용해서 아주 짧게 줄일 수 있죠.

https://bit.ly/3tut6x1 링크를 접속했더니 변환된 페이지 https://i.guim.co.uk/img/media/ec27f69b7e4ac14838e8f71842a4cc6db3b8d69c/112_4_1179_708/master/1179.jpg 가 잘 열리네요.

어떻게 된 것 일까요?

HTTP 301

curl을 통해서 줄여진 URL경로로 http 요청을 해봅니다. -i 옵션을 추가하여 헤더값까지 확인을 합니다.

cURL은 다양한 통신 프로토콜을 이용하여 데이터를 전송하기 위한 라이브러리와 명령 줄 도구를 제공하는 컴퓨터 소프트웨어 프로젝트이다.

응답으로 HTTP/2 301 이 왔습니다. 301은 URL이 옮겨졌다는 상태코드입니다. 어디로 옮겨졌는지는 location 에 잘 나와있군요. 그외에 cache-control에서 브라우저에서 요청 리소스에대한 캐시 정책등에 대한 내용도 포함이 되어있구요. (Toss에서 관련된 글을 잘 정리해 두셨네요. https://toss.tech/article/smart-web-service-cache)

HTTP 301 Moved Permanently 리다이렉트 상태 응답 코드는 요청한 리소스가 헤더에 주어진 URL로 완전히 옮겨졌다는 것을 나타낸다. 브라우저는 이 페이지로 리다이렉트하고, 검색 엔진은 해당 리소스로 연결되는 링크를 갱신한다. https://developer.mozilla.org/ko/docs/Web/HTTP/Status/301

정리하면, 만들어진 짧은 URL을 요청받으면 HTTP 301로 응답을 주면 될 것 같아요.

그럼 URL을 짧게 어떻게 만들까요?

Shorten URL 만들기

밀러의 법칙

사람이 느낄때 얼마나 짧아야, 짧다고 생각이 들까요? 1956년 하버드 대학의 인지심리학자 George A. Miller 의 논문 ‘The Magical Number Seven, Plus or Minus Two Some Limits on Our Capacity for Processing Information’ 에 따르면 7개(+-2) 내외의 단어를 사람이 기억 할 수 있다고 해요. 이를 흔히 밀러의 법칙이라고도 불러요.

물론 60년도 이전의 연구기도 하고, 그동안 많은 연구에서는 반드시 7개인 이유는 없다고도 해요. 입으로 읽었을때 2초의 분량으로 정해진다는 연구나, 7개가 아닌 3~5개 사이라는 연구도 있구요. (100 Things Every Designer Needs to Konw About People - Susan M. Weinschenk)

그렇다면 Shorten URL은 어느정도의 길이로 만들면 좋을까요? 우선 7개를 기준으로 만들어보려고 해요. 적어도 제 기준에는 너무 짧으면 표현 할 수 있는 URL의 수가 적어져 구현하기가 어려울것 같았어요. bitly도 밀러의 법칙을 생각한건지, 7자리로 답을 주고 있네요!

도메인을 제외하고 3GvqLoV 총 7자리로 응답

리소스 식별자

요청 URL에 대응하는 식별자를 만들어야 해요. 우리는 위에서 살펴본 밀러의 법칙과 같이 7자리를 최대한 이용해 보려고 하구요. 아래와 같이 두가지의 요구사항으로 정리되네요.

CRC(cyclic redundancy check) 는 어떨까요? 흔히 네트워크 전송시에 에러감지에 사용되는 알고리즘이에요.

Data를 bit로 표기하고 사전에 정의된 Divisor로 나눈 나머지 값을 Databit 후미에 붙혀서 전송후 확인하는 과정이죠.

CRC(cyclic redundancy check)의 경우에는 전송과정에서의 무결성만을 보장하고, 구조적으로 데이터 무결성을 보장하지 않기에 URL 데이터를 다루기에는 적절하지 않다고 하네요.

CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터 무결성 을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다. https://ko.wikipedia.org/wiki/순환_중복_검사

위 조건을 만족시키는 해시 알고리즘이 있을까 하고 찾아봤어요. MD5, SHA-1등은 길이가 맞지 않아요.

NanoId, UUID 등도 길이가 7자리보다는 훨씬 길어서 Shorten URL에 어울리지 않죠.

import { nanoid } from 'nanoid'
model.id = nanoid() //=> "V1StGXR8_Z5jdHi6B-myT"

import { v4 as uuidv4 } from 'uuid';
uuidv4(); // ⇨ '9b1deb4d-3b7d-4bad-9bdd-2b0d7b3dcb6d'

그렇다면, 어쩔수 없네요.

아래와 같이 DB를 사용해야겠어요.

인코딩

Number System

DB 시퀀스를 사용하여 식별자를 만들어서 사용하면 좋을 것 같아요. 그런데 문제가 있네요. 만약 7자리를 넘어가면 어떻하죠? 사실 1,000,000개 정도라서 괜찮을것 같기도 한데요. 천만이 넘어가는 더 큰시스템을 생각하면 식별자는 더 많이 필요할것 같아요.

1000000 은 10진수로 표현되었으니, 16진수로 표현하면 어떨까요?

총 268,435,455 개를 만들 수 있고. 268배 더 만들 수 있어요.

그럼 64진수로 표현하면 더욱 많이 표현 할 수 있겠죠? 여기서 문득 떠오르는 생각이 Base64를 쓰면 될 것 같아요.

여기서 질문!

BASE 64 기초

폰노이만 구조의 컴퓨터는 바이너리 형태로 데이터를 주고 받았으며, 문자는 사용하면 아래와 같은 사전에 정의된 문자열 테이블을 기준으로 사람이 읽을 수 있도록 표현하고 있어요. ASCII(아스키코드)의 경우에는 128개로 이뤄져 있어요. 7bit로 처리 표현이 가능하죠.

그런데 예전에는 네트워크 통신으로 6bit를 요구했었어요. 왜냐하면 문자를 처리할때 각 기기별로 특수문자, 제어문자의 처리방식이 달라서 만국 공통인 알파벳과 숫자만 원했던것 같아요. 그래서 알파벳과 숫자 총 62개와 두가자 특수문자 +,/ 를 담아서 64 진수로 표현을 요구했어요. 각 자리수당 표현의 범위가 128개에서 64개로 줄어들어버리니 총 자리수는 증가하여 원본보다 대략 4/3 정도 크기가 늘어나게 되죠.

이때 사용된 방법이 Base64 인코딩과 디코딩이에요.

Base64의 경우에는 아래 표로 치환이 되요.

ASCII 방식의 문자 MAN을 보낸다고 했을때, ASCII (1bit + 7bit) 그대로 보내게 되면 L1(OSI 7Layer) 물리단계에서 01001101, 01100001, 01101110 세개의 청크로 보낼 수 있을 텐데

통신규격이 6bit를 원하니 Base64를 이용해서 쪼개서 보낼 수 있게 되는거죠.

세개의 청크를 쭉 펼쳐서 010011010110000101101110 로 만들고 이를 6bit씩 4개의 청크로 분리합니다.

그러면 010011, 010110, 000101, 101110 네개로 나눠지죠. 이 수를 문자로 치환하면 TWFu가 나오게 되요.

만약에 6bit로 쪼개다가 자릿수가 부족하면 그부분은 0으로 채우고, 부족한 부분의 청크는 = 로 채웁니다. 이를 패딩이라고 해요.

만약 한글자만 있다면 ? 아래처럼 되죠.

퀴즈! ASCII ManM은 base64로 어떻게 문자로 표현될까요?

이렇게 base64로 인코딩된 문자열은 L7에서는 사람에게 TWFuTQ== 와같이 보이고 다뤄지며, 이후 필요에 따라 상호 정의된 Character Set으로 변환하게 됩니다.

결론으로는 조금 더 안전한 방식 혹은 권장하는 방식으로 상호 전달이 가능하다는 것이죠. (특히 이기종간 통신에서 그렇습니다. 더 궁금하면 RFC1341에 관련 내용이 있습니다.)

아스키 포맷에서 숫자 1의경우 Base 64로 MQ==로 인코딩되어 표현됩니다. 그렇지만 패딩값을 제외하고 변환하여도 그 값은 확인 할 수 있습니다.

이걸 역으로 표현하면 001100010000이고 8bit로 끊어서 계산하면 00110001 + 00000000 이 됩니다. 이를 10진수로 변경하면 49입니다. 49는 ASCII에서 1입니다.

그렇다면 패딩은 왜 필요할까요?

왜냐면 RFC4648 표준이기 때문이죠. base64는 4개의 청크로 분리하여 항상 padding 값을 추가 하여 표현합니다. https://datatracker.ietf.org/doc/html/rfc4648#section-4

또한 생각해보면 일정한 길이의 문자로 구분된 데이터를 전달 받아야 파싱을 쉽게 할 수 있을 것 같습니다. 또한 끝까지 인코딩된 문자열이 전송됬는지도 알 수 있구요. 아래 base64 라이브러리의 소스코드를 봐도 decoding시 길이 4개로 분리하여 취급하고 있네요.

var decode = function(input) {
		input = String(input)
			.replace(REGEX_SPACE_CHARACTERS, '');
		var length = input.length;
		if (length % 4 == 0) {
			input = input.replace(/==?$/, '');
			length = input.length;
		}
		if (
			length % 4 == 1 ||
			// http://whatwg.org/C#alphanumeric-ascii-characters
			/[^+a-zA-Z0-9/]/.test(input)
		) {
			error(
				'Invalid character: the string to be decoded is not correctly encoded.'
			);
		}
		var bitCounter = 0;
		var bitStorage;
		var buffer;
		var output = '';
		var position = -1;
		while (++position < length) {
			buffer = TABLE.indexOf(input.charAt(position));
			bitStorage = bitCounter % 4 ? bitStorage * 64 + buffer : buffer;
			// Unless this is the first of a group of 4 characters…
			if (bitCounter++ % 4) {
				// …convert the first 8 bits to a single ASCII character.
				output += String.fromCharCode(
					0xFF & bitStorage >> (-2 * bitCounter & 6)
				);
			}
		}
		return output;
	};

더 많은 논의는 아래 스택오버플로우를 확인하세요.

본론으로 돌아와서.

그래서, Shorten URL하고 무슨 관련이 있나요?

Base62와 춤을

아, 멀리왔습니다. 진법에 맞는 형태로 인코딩을 하여 표현하는 것을 보여주고 싶었어요. Base 64는 64진수처리를 생각했는데, 일반적으로는 RFC4648 표준의 문자열 처리방식이었죠. 패딩값도 붙고 좀더 표현이 길어지는 특징을 나타냈어요.

여기서 중요한것이 우리는 URL을 만드는것이 핵심이에요. 만약 Base64를 사용한다면 = 가 예약어라서 사용 할 수 없을 꺼에요. 또한 62(+), 63(/) 도 사용하기 어렵구요. 그래서 등장한 URL Safe Base 64는 기존 62를 (-)로, 63을 (_) 로 표현해요. 그래도 결국 패딩은 = 로 표현하죠.

그래서 URL에서는 특수문자 2개를 제외한 표현인 62진법이 흔히 사용되는 것으로 보여요. 굳이 추가하자면 허용된 특수문자11개 $-_.+!*’(),를 포함한 73진법까지 가능할것 같은데 가독성이나 짧다고 느끼기에는 발음이 길어져서 효용성이 떨어져서 보이기도 하구요.

강제사항은 아니지만 저는 Base64는 URL 예약어와 패딩 문자 = 의 중복사용과 ux 디자인을 고려해서 선택을 안했어요. 알파벳과 숫자만 쓰는게 더 나은 선택으로 생각되어서요. 글 말미에 언급하겠지만 충분히 많은양을 짧게 표현가능하구요.

If the character corresponding to an octet is reserved in a scheme, the octet must be encoded. The characters “;”, “/”, “?”, “:”, “@”, “=” and “&” are the characters which may be reserved for special meaning within a scheme.

Thus, only alphanumerics, the special characters “$-_.+!*’(),”, and reserved characters used for their reserved purposes may be used unencoded within a URL.

Base62는 RFC4648 표준에는 없어요.

Base 62의 경우 ISO 10646, UTF-62로 ‘A base62 transformation format of ISO 10646 for multilingual identifiers’ 에서 소개되고 있어요. 논문을 읽어보면 UCS-4 code를 UTF-62 코드로 변환하여 인코딩하는 내용이 있는데, 본 글에서는 다루지는 않을게요.

그럼 한번 10진수에서 64진수로 표현되는 Base62를 구현해볼까요?

2진수부터 시작해보죠.

2진수

const bi = (number) => {
    let quotient = number;
    let reminder = [];

    while (quotient >= 2){
        reminder.push(quotient % 2);
        quotient = Math.floor(quotient / 2);
    }
    quotient = quotient + '';

    while (reminder.length > 0) {
        quotient = quotient + reminder.pop();
    }

    return quotient;
}

10을 넣었더니 1010으로 변환되었고, 12^3 + 12^1 = 10으로 잘 동작 하네요.

여기서 기수 2를 16으로 변경하여 16진수를 만들어보죠

16진수

const hex = (number) => {
    let quotient = number;
    let reminder = [];

    while (quotient >= 16){
        reminder.push(quotient % 16);
        quotient = Math.floor(quotient / 16);
    }
    quotient = quotient + '';

    while (reminder.length > 0) {
        quotient = quotient + reminder.pop();
    }

     return quotient;
}

값을 1000을 넣었더니 3148이 출력되었어요. 316^2 + 1416^1 + 8*16^0으로 잘 나왔네요. 다만 표현 할 수 있는 문자가 아라비아 숫자 0~9로 되어서 처음보는 사람은 각 자리수를 알 수가 없어요.

14를 표현하기 위해서 알파벳 문자표를 대응 해주도록 해요. 14는 알파벳 e로 하면 되겠죠?

아래 코드로 하면 잘 되요.

const hex = (number) => {
    let quotient = number;
    let reminder = [];
    let codes = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'];

    while (quotient >= 16){
        reminder.push(quotient % 16);
        quotient = Math.floor(quotient / 16);
    }

    quotient = codes[quotient];

    while (reminder.length > 0) {
        quotient = quotient + codes[reminder.pop()];
    }

     return quotient;
}

이제 62진수는 쉽겠죠?

62진수 (Base62)

const base62 = (number) => {
    let quotient = number;
    let reminder = [];
    let codes = [
        '0','1','2','3','4','5','6','7','8','9',
        'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
        'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
    ];

    while (quotient >= 62){
        reminder.push(quotient % 62);
        quotient = Math.floor(quotient / 62);
    }

    quotient = codes[quotient];

    while (reminder.length > 0) {
        quotient = quotient + codes[reminder.pop()];
    }

     return quotient;
}

10진수 1000을 넣었더니 g8이 나왔어요.

62진수로 표현한 7자리 최대값은 zzzzzzz에요. 이건 10진수로 3521614606207이나 되죠.

이제 총 7자리의 문자를 사용하여, 총 3조 5천개 정도의 URL을 매핑 할 수 있어요.

System Architecture

우선 필요한 내용을 대략 생각하면 아래와 같아요.

우선 짧아진 도메인주소를 본래의 긴 주소로 치환해서 응답해줄 URL Mapping 서비스와 Base62를 이용하여 짧은 식별자를 생성하여 짧은 URL을 생성 해줄 Key Generation 서비스가 필요해요. 이 서비스들은 Application 안에서 동작하겠죠.

두번째로 URL 주소들과 관련 데이터가 저장될 공간이 필요해요. DBMS를 사용 할 것이에요.

세번째로는 시스템 성능과 관련된 것들이에요. DBMS에서 모든 URL 매핑 요청마다 매핑정보 처리를 담당하게되면 부하가 걸리게 될것은 분명해요. 그래서 Load Balancer (Rate Limiter)를 넣어서 요청량을 조절하고, 인메모리 형태의 K-V DB를 이용 할 것이에요.

마지막으로 위에서 봤듯이 3조 5천개 정도의 URL을 매핑 해 줄 수는 있지만, 사용 시나리오상 모든 데이터를 가지고 있는 것은 서버 유지 비용이 너무 많이 들어요. 그래서 주기적으로 정리해주는 cleanup 서비스가 필요해요.

자 이제 만들어볼까요?

→ 2편에서 계속.

참고

main picture