Motivation
개인적으로 만들고 있는 서비스가 하나 있습니다. 서비스의 기능 중 일부는 웹 페이지의 내용을 가져와 페이지에 담긴 내용을 파싱해 DB에 저장하는 것 입니다. 그 DB에 저장된 값은 계산을 통해, 계산된 결과 값을 보여주는 기능으로 이어지게 됩니다. DB의 값이 변경되지 않는 한, 계산 값은 변하지 않게 되므로 수집된 웹페이지가 변경되었는냐를 인지하는 것이 중요합니다. 웹 페이지의 내용은 매일 혹은, 매주 같이 일정한 주기로 변경되면 좋겠지만, 최대 3개월까지 변경되지 않을 수 있고, 그런 수집 대상 페이지는 약 2천개가 넘습니다.
Action
웹페이지가 변경될 때에, 계산된 결과도 변경되도록 하기 위한 선택지를 4가지 정도 떠올렸습니다. ( 수집하는 웹 페이지의 용량은 평균적으로 140Kb 입니다 )
1. 매일 변경되었다고 가정하고, 매일 데이터를 갱신.
제일 먼저 떠올린 방법입니다. 그리고, 제일 먼저 제외한 방법입니다. 별도로 개발할 필요가 없었기에, 개발 면에서는 별도로 고려할 없으며, 데이터는 항상 최신을 유지한다는 취지에는 부합하지만, 데이터가 수집된 이후 계산되는 과정이 의미 없이 매일 수행되어야 하고, 그럼으로써 어떤 데이터가 최근에 변경된 것인지 알 수 없다는 단점이 있었습니다. 서비스의 특성상, 최신의 데이터를 유지해야 하지만, 최근에 변경된 데이터를 아는 것도 중요하기 때문입니다.
2. 웹페이지를 처음부터 끝까지 비교.
수집된 웹페이지는 문자열이니 처음부터 끝까지 비교하는 것을 생각했습니다. 가장 확실한 방법이라고 생각하지만, 몇가지 추가로 고려해야 할 점이 생각났습니다. 메모리가 여유가 있다면, if new_page == old_page 와 같이 비교하면 되겠지만, 서비스가 구동되는 서버는, 메모리가 그렇게 넉넉한 상황이 아닙니다. 그래서 문자열을 조금씩 잘라서 비교하는 것을 반복해야 했고, 예전 데이터를 고스란히 DB에 저장해야 했습니다. 파싱된 데이터와 함께 원본을 보관해야 하는 상황이니, 결과적으로는 중복된 데이터를 가지고 있어야 하는 것어야 했습니다.
3. 웹페이지를 파싱하여, 저장된 데이터를 비교.
2번의 경우에서 비교에 필요한 연산 시간은 시분초를 다툴 정도의 서비스는 아니기에, ( 그래도 수초의 연산시각은 사용자에게 짜증을 유발하기엔 충분한 시각... ) 넘어 가더라도 중복으로 데이터를 보관해야 한다는 것이 별로 맘에 들지 않았습니다. 그래서 파싱된 값을 비교하면 어떨까 생각했습니다. 문서의 파싱에 소요되는 시간은 웹페이지를 처음부터 끝까지 비교하는 시간과 비슷하게 걸릴 것이라 가정한다면, 데이터를 저장할 공간을 낭비하지 않는 장점이 있는 방법으로 생각했습니다. ( 데이터 베이스에서 이전 값을 읽어 올때도 시간이 필요하지만, 실제 조회하는 쿼리는 실행시간이 오래 걸리지 않기에 무시했습니다. )
4. 문서를 해시로 변경하고, 해싱된 값을 비교.
3번에서 중복된 데이터 문제는 해결했지만, 여전시 비교하는 데 걸리는 시간이 맘에 들지 않았습니다. 파싱하면서 동시에 비교를 시작한다면 파싱에 소요되는 시간과 비슷하겠지만, 문제는 모든 수집된 웹페이지를 파싱해야 한다는 점이었습니다. 만약 처음부터 이문서는 변경된 것이다라고 판단할 수 있다면, 그런 시간 조차 필요 없이 이미 저장된 데이터로 연산하여, 또는 저장된 연산 결과를 화면에 뿌려 줌으로써 더 빠르게 결과를 보여줄 수 있을 테니까요. 그걸 피하고 싶었습니다. 그래서 문장을 압축해서 비교하면 어떨까 싶었습니다. Run Length Conding과 같이 압축한 스트링을 비교하면 변화를 알 수 있지 않을까 생각하다. Hashing 하는 방법을 떠올렸습니다. 문자열을 MD5로 해싱하면 항상 32개의 문자로된 결과를 얻을 수 있으니 32byte의 저장공간만 사용하면, 파싱에 필요한 시간은 아낄 수 있겠다 싶었습니다. 그래서 수집된 웹페이지를 MD5로 Hashing한 다음 그 결과를 DB에 넣고 다음 부터는 웹 페이지의 변경 여부를 판단하기로 결정했습니다.
Crisis
4번의 방법을 사용하겠다라고 결론을 내고, 구현을 하는 중에, hash 값이 같은 경우는 없을까? 라는 생각이 들면서, 예전에 MD5 해시를 사용하면 안된다는 글을 본 기억이났습니다. 그래서 찾아보니 MD5 Hashing Collision이라는 문제가 있는 것을 발견했습니다. 이미 20년 전 쯤에 제기된 문제였는데, 그래서 중요한 서명 같은 것을 비교하는 경우에는 MD5를 사용하지 말라는 글을 다수 발견했습니다. 발생할 확률은 생일 문제의 확률과 같다고 하는데, 생일 문제란, 한반에 같은 생일을 가지는 사람이 1사람 이상인 확률을 말하며, 만약 한반에 366명이 있다면 확률은 1이 됩니다. 그러면 생일이 같은 사람이 있을 확률이 0.5가 넘을 때 한반의 인원 수는 183일까요? 아닙니다. 한 반에 23명이 있을 때 같인 생일을 가진 사람이 있을 확률이 0.5를 넘게 됩니다.
즉, MD5도 동일한 방식으로 동일한 Hash 값을 가지는 다른 문자열이 존재할 수 있고, 서로 다른 문서가 약 1/2^64 의 확률로 같은 Hash 값을 가질 수 있다고 합니다.
Conclusion
MD5 Hash를 생성하더라도, 사용하는 데이터가 중복이 발생할 확률 보다는 작기 때문에, 생일 문제 같은 것은 거의 발생하지 않을 것이다라고 판단되었습니다. 하지만, 만에 하나 잘못된 결과를 도출하는 경우를 줄이기 위해(Hash를 사용하는 한 생일문제는 피할 수 없을 것 같습니다) 사용하기로 한 것은 MD5보다 2배의 길이로 HASH를 생성하는 SHA256을 사용하기로 했습니다. SHA256으로 해싱할 경우, 중복이 발생할 확률은 거의 0( 약 1/2^128 )에 가까웠습니다. 따라서 저는 파일의 변경 여부를 판단하기 위해, SHA256 해시를 사용하는 것으로 결론 지었습니다.
참고 :
MD5 : https://ko.wikipedia.org/wiki/MD5
해시 생성기 : https://emn178.github.io/online-tools/index.html
생일 문제 : https://ko.wikipedia.org/wiki/%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C