세상을 바꾼 아홉가지 알고리즘 기억 남기기

세상을 바꾼 아홉 가지 알고리즘 리뷰

세상을 바꾼 아홉 가지 알고리즘을 읽으면서 내가 지금까지 누리던 편리함이 누군가의 노력으로 만들어진 것이라는 것과 생각 이상으로 알고리즘은 나의 삶에 밀접한 관련이 있고 매일 사용된다는 알게 되었다. 하나의 기능을 만들 때 어떤 식으로 알고리즘을 구현되었을까?라는 궁금증이 자연스럽게 생겨난 후 그 궁금증을 차근차근 풀어주는 책이 세상을 바꾼 아홉 가지 알고리즘이라고 생각한다. 이 책을 읽으면서 알고리즘에 대해 더 생각해 볼 수 있었고 알고리즘에 대한 친밀감을 높일 수 있었다. 아래는 내가 흥미 있게 보았던 부분들을 짧게 정리해 보았다.

 

 

1. 검색엔진 인덱싱

검색 단어의 찾기 위해 페이지마다 검색한 단어를 포함하는지 여부를 확인하는 것이 아니라 각 페이지에서 모든 단어에 인덱스를 부여하고 해당 단어가 검색된다며 페이지(인덱스)를 찾아가는 방식이다. 이 방법으로  검색을 한다면 페이지 안에 전체의 글을 파악하지 않아도 검색하는 단어를 포함되어있는지를 에 대한 여부만으로 검색을 진행할 수 있다. 그러나 이런 방식의 검색에는 한계점이 분명하여 near 인덱스와 랭킹, 메타 워드 트릭을 사용하여 한계점을 극복하려고 노력했고 이후 다양한 방식의 알고리즘을 통해 검색 속도와 정확성을 높여왔다.

 

2. 하이퍼링크 트릭과 권위 트릭 

하이퍼링크 인덱싱 방식은 해당 페이지에 인커밍 링크의 수에 따라서 순위를 수동으로 결정하는 방법이다. 단 하이퍼링크가 대다수가 긍정적으로 링크를 걸지만, 부정적인 의미로 링크를 걸기 도하는 문제점이 있다.

권위 트릭은 해당 인커밍 링크를 사용한 사용자의 권위를 파악한다. (요리책이라면 요리사에게 더 가산점을 부여한다.) 그러나 여기서도 문제가 있다. 해당 사용자의 권위를 컴퓨터가 무슨 근거로 파악하는가? (컴퓨터가 해당 사용자가 어떤 사용자인지 아는 방법은 매우 어렵다.)

이런 문제가 있어 하이퍼링크와 권위 트릭을 결합하여 사용하는 방식이 생겨났다. 이 두 가지 결합 방식은 사용자의 한 페이지의 인커밍 링크만을 계산하는 것이 아니라 인커밍 한 사용자의 인커밍 링크까지 계산하여 인커밍 링크의 개수가 많은 사용자에게 더 많은 권위를 부여하는 방식이다. 

 

3. 공개 엽서에 비밀을 적어 아무도 모르게 보내는 방법

페인트 혼합 트릭은 비밀을 주고받을 2명의 사용자 A와 B가 모두에게 공개할 키 X를 설정한다. X를 설정 후 A(키 Y)와 B(키 Z)의 각 개인키(비밀키)와 공개키 X를 섞는다. (여기서 섞은 값은 다시 돌릴 수 없다.) A가 가진 혼합 값은 XY, B가 가진 값은 XZ가 된다. 섞은 값을 모두에게 공개(개인 둘만의 통신 이어도 해킹이나 외부에 노출될 위험이 있기 때문에 모두 공개라고 여긴다.)한 다음 A와 B는 상대가 공개한 섞은 값을 가져온다. 그 후 섞인 값에 자신의 개인키를 섞는다. 그럼 놀랍게도 A와 B는 같은 값을 가지게 된다. 이런 방식으로 공개 엽서에 비밀을 적어 아무도 모르게 보내는 방식이 성립된다.  

 

 

4. 데이터베이스 일관성

데이터베이스의 일관성을 유지하기 위한 노력은 끊임없이 지속되어왔다. 일관성에 집착하는 이유는 데이터베이스의 모순이 있다면 데이터베이스 관리자에게 끔찍한 악몽이 시작되기 때문이다. ex) A와 B가 결혼했다면 B도 A와 결혼해야 한다. 하지만 일관성에서 모순이 발생하여  B는 C와 결혼했다고 기록되어 있다면 많은 문제가 생길 거라는 것을 모두 알고 있을 것이다. 이런 데이터베이스 일관성을 찾기 갖기 위해서 여러 기법을 사용한다.

 

할 일 목록 트릭 - 미리 쓰기 로그로 데이터베이스 테이블은 건드리지 않고 트랜잭션의 할 일 목록을 로그에 쓰고 영구 저장장치(디스크)에 저장 후 데이터베이스에 변화를 준다. 데이터베이스를 수정하는 단계에서 충돌이 발생하더라도 로그에 정보가 남아있기 때문에 데이터베이스를 원하는 결과로 변경할 수 있다. 

 

준비 후 커밋 트릭 - 마스터 복제본 A는 두 개의 다른 복제본 B, C를 조정하여 새로운 데이터를 추가한다. 이 과정에서 모든 복제본이 트랜잭션이 완료되었는지 확인하고 모두 완료되었다면 마스터는 이 데이터를 완료하고 보관하라는 명령을 모든 복제본에 전달하고 오류가 발생했다면 해당 부분을 제외한다. 이런 방식으로 문제가 없는 방식만을 선택하여 동시에 접속한 수천 명의 고객을 데이터베이스 중복이나 불일치, 데이터 손실 가능성이 전혀 없는 상태에서 서비스를 제공하는 것이 준비 후 커밋이다.

 

관계형 데이터베이스와 가상 테이블 트릭 - 관계형 데이터베이스는 중복이 많은 테이블 1개를 2개로 나누어 나타내는 방식으로 많은 반복을 적은 반복으로 바꾸는 것이고 데이터가 많을수록 저장공간 절약의 효과가 막대해질 것이다. 가상 테이블 트릭은 모든 데이터베이스의 모든 고정된 테이블에 저장되지만, 데이터베이스는 필요할 때마다 완전히 새로운 테이블을 일시적으로 생성하는 것이다. 이렇게 일시적으로 생성된 테이블은 실제로 생성만 되고 저장되진 않기 때문에 가상 테이블이라고 불린다.