Pinkerton, B. 1994. Finding What People Want: Experiences with the WebCrawler

이 논문은 1994년 10월, Chicago에서 열린 두번째 WWW 컨퍼런스에서 발표된 논문이다. WebCrawler 역시 웹의 resource discovery 문제 해결을 위해 웹 크롤러를 사용하는 검색엔진에 해당한다. 불과 5개월 간격이지만 첫번째 WWW 컨퍼런스에 등장한 검색엔진에 비해서 꽤 완성도 면에 있어서 나아진 면을 보인다.

WebCrawler의 디자인에 대한 설명은 웹에 대해서 잘 모르는 사람들도 이해할 수 있을 정도로 자세하고 쉽게 되어있어서, 웹 크롤러에 대한 설명이 필요하다면 참고할 만하다. WebCrawler의 architecture는 크게 Search Engine, Agents, Database, Query Server로 이루어진다. Search Engine은 크롤과 인덱싱 작업을 담당하며, 여러 프로세스 (15개)로 동시에 동작하는 Agents는 실제로 웹 페이지를 다운로드 받는 역할을 한다. Database는 문서의 메타데이터나 링크, full-text 인덱스를 저장한다. 특이한 점은 방문한 server들에 대한 정보를 가지고 있어서, 방문하지 않은 서버나 least recently visited 서버를 먼저 방문함으로써, 가능한 한 여러 서버들을 공평하게 방문하려고 시도한다는 것이다. Query Server는 사용자의 검색엔진 질의를 담당한다.

WebCrawler의 성능은 486 PC에서 1시간에 1000개의 문서를 인덱싱하는 정도라고 한다. 현재의 기계로는 1초에 그 정도 이상의 문서를 처리할 수 있음을 생각하면, 1000~10000배 이상의 성능 차이가 난다는 것을 알 수 있다. 게다가, 이러한 성능 차이는 웹 크롤러 – 검색엔진의 디자인에 많은 영향을 줄 것임에 틀림없다.

인덱싱은 IndexingKit이라는 라이브러리를 사용하는 것으로 보이고, lexical anlyzer, stop list, inverted index, vector-space model에 관한 언급들이 보인다.

이 논문에서 저자는 6개월 간의 WebCrawler 운영을 통한 교훈을 정리해놓았는데, 다음과 같다.

• Full-text indexing is necessary
• 당시에도 20% 가량의 웹 페이지들은 title을 가지고 있지 않았으며, title의 유효성을 인정하기 어렵기 때문에, full-text 인덱싱이 필수적이라는 견해를 보인다. 그리고 실제로 사람들이 원하는 것은 title이 아닌 내용에 대한 좀 더 나은 쿼리 기능을 원하고 있다는 면에서 full-text 인덱싱의 중요성을 설명하고 있다.
• Precison is the limiting factor in finding documents
• WebCrawler는 Recall을 적절히 만족시키고 있지만(adequate), Precison의 면에서 만족스럽지 못하다고 얘기하고 있다. 문서의 weighting이 도움이 되지만 false positive (irrelevant documents)를 제거하고 있지는 못했다고 한다. (이 문제는 랭킹의 문제로 보인다.) 또다른 문제는 사용자가 well-focused query를 던지지 못하는 문제를 언급하고 있으며, 사용자 쿼리의 평균 단어 수가 1.5이었다고 한다. 검색엔진이 보편화된 현재도 사용자들은 여전히 단순한 쿼리를 던지고 있다.
• Breadth-first searching at the server level builds a useful index
• 어떤 정보를 가지고 있는 서버만 발견할 수 있다면, 사용자들은 그 서버 내에서 좀 더 쉽게 navigate할 수 있기 때문에, Breadth-first searching이 사용자들을 만족시켜준다고 한다. navigational search라는 검색엔진의 용도라고 볼 수 있을 듯 하다. 또한, 크롤 전략 – 순서가 검색 결과에 영향을 미칠 수 있다는 인식이 보인다. 한편, BFS 크롤 전략의 다른 이익으로 politeness를 언급하고 있기도 하다.
• Robot-like behavior is necessary now
• 크롤러가 웹 트래픽을 낭비한다는 비판에 대해서 크롤러를 통해 오히려 웹 트래픽을 절감할 수 있다고 주장하고 있다. ALIWEB과 같이 사이트 별 인덱스를 사용하는 것이 아니라, 실제 문서를 인덱싱에 사용함으로써, 좀 더 나은 인덱싱 방법을 사용할 수 있음을 지적하고 있다.
• Widespread client-based searching is not yet practical
• 클라이언트에서 크롤러를 동작시켜 문서를 찾아내는 방법은 하나의 서버에서 인덱스를 만드는 방법에 비해 효율적이지 않음을 지적하고 있다. Future Work에서 클라이언트 기반 검색을 하더라도 이 결과를 사용자들이 공유하는 인덱스에 추가하는 방법을 제안하고 있다.

Future Work에서 좀 더 강력한 full-text 엔진의 기능으로, proximity searching과 query expansion & refinement를 제안하고 있다.

결론에서 크롤러에 기반한 검색엔진을 분산된 웹의 특성에 비유하고 있다. 크롤러에 기반한 검색엔진은, 웹 사이트들로부터 (아마도 인덱스 생성과 같은) 특별한 참여를 필요로 하지도 않고, 웹 프로토콜을 그대로 사용함으로써, 동작 방식과 정책의 분리가 가능해졌고, 여러 검색엔진이 여러가지 정책을 채용함으로써, 사용자는 자신의 필요에 적합한 검색엔진을 선택할 것이며, 기술은 좀 더 빠르게 성숙될 것이라고 저자는 예견하고 있다.

Eichmann D. 1994. The RBSE Spider – Balancing Effective Search Against Web Load

1993년은 여러가지 목적을 가진 웹 크롤러들이 출현하기 시작한 해였다. 예를 들어, 최초의 크롤러로 기록되고 있는 World Wide Web Wanderer는 웹의 크기와 성장를 측정하기 위한 용도로 만들어졌다. 한편, RBSE Spider는 웹 검색엔진을 위한 크롤러로 만들어졌으며, 제목과 헤더들만 인덱싱하던 JumpStation과 달리 Full-text 인덱싱하는 검색 엔진의 일부분이었다. (이 때는 아직 검색 엔진과 크롤러의 구분이 모호했다.) 따라서, RBSE Spider는 웹 크롤러를 사용하는 최초의 Full-Text 검색 엔진이라고 볼 수 있다.

크롤러와 인덱서의 분리

크롤러의 architecture면에서 RBSE Spider는 크롤러를 인덱서로부터 분리했다. 크롤러와 인덱서를 분리함으로써 separation of concern의 효과를 얻을 뿐만 아니라, 각각의 컴포넌트를 다른 용도로도 사용할 수 있게 되었다. 하지만, RBSE Spider는 크롤러가 웹 페이지의 발견(discovery)만을 수행할 뿐, 저장하지 않았기 때문에, 크롤러가 발견한 웹 페이지를 받아오기 위해서 인덱서가 다시 방문해야 했다.

Incremental Crawler

크롤러와 인덱서를 분리하지 않을 수 없었던 또다른 이유는 incremental한 크롤러를 만들기 위한 것이었고, 크롤러가 incremental해야만 했던 이유는 robust한 (그러니까 잘 죽지 않는) 크롤러를 만들기가 어려웠기 때문이라고 한다. 그들의 이유는 조금 우습지만, 현재는 웹의 크기가 커지면서 incremental한 크롤러는 필수적인 것이 되었다.

Politeness

당시에 여러 목적의 크롤러들이 늘어나면서 크롤러가 유발하는 웹서버의 로드에 대한 우려가 생기기 시작했고, 이는 Koster의 Guidelines for Robot Writers라는 문서의 제안으로 이어졌다. RBSE Spider는 User-Agent 필드를 이용한 identification 등 Robot exclusion protocol을 따르며, 웹 서버에 로드를 주지 않기 위해 주의하고 있다.

상세한 구현

RBSE Spider의 크롤러 부분은 두개의 프로그램으로 이루어져 있다. 그 하나는 mite라는 프로그램인데, 주어진 URL의 문서를 다운로드한 후, 문서 내에 포함된 URL들을 출력해주는 것이다. 다른 프로그램은 특정 패턴을 가진 URL들에 대한 링크를 mite를 이용해서 추출한 다음 source-target pair들을 Oracle 데이터베이스에 저장하는 역할을 한다. 데이터베이스에는 다시 방문하는 것을 방지하기 위해, 다운로드에 실패하거나 링크가 없는 경우의 로그가 있다. Robot exclusion protocol에 따라 받아서는 안되는 URL들의 패턴들의 리스트도 있다.

페이지의 텍스트를 저장하지 않는 것을 제외하고는 기초적인 크롤러의 기능들을 갖추고 있다고 볼 수 있다.

인덱서 부분은 좀 더 단순하다. 데이터베이스로부터 URL들을 가져온다음 이들을 waisindexer라는 프로그램에 집어넣으면, waisindexer는 다시 mite를 사용해서 URL에 해당하는 페이지를 다운로드한 다음 이들을 인덱싱한다. 인덱싱 부분은 거의 WAIS의 인프라를 활용함으로써 relevance feedback도 활용할 수 있다고 한다.

검색 엔진의 역할

이 paper는 크롤러에 대한 Rationale로서 크롤러가 마치 지도와 같은 역할로, 사용자가 원하는 페이지에 바로 찾아갈 수 있도록 함으로써, 네트워크 트래픽을 감소시킬 수 있다고 주장하고 있다. 이는 당시에 클라이언트 기반의 검색엔진 등이 있었다는 것을 감안하면 옳은 주장이라고 생각되나 사실 현재에는 별로 의미가 없다.

당시에 증가하고 있던, 데이터베이스로부터  동적으로 생성된 페이지들을 인덱싱하지 말아야 한다는 주장은 지금 생각하면 완전히 잘못된 것이다. 당시엔 아마도 각 사이트에서 제대로 인덱싱 되고 있는 페이지들을 따로 인덱싱하는 것은 낭비라고 생각했을 것이다.

한편, 크롤러의 역할로서 내용 유사도(semantic similarity)에 따른 가상적인 이웃 (virtual neighborhoods) 정보를 생성할 수 있다고 얘기하고 있다. 당시에는 아마도 하나의 사이트는 특정한 주제를 취급하는 사이트였을테고 그런 사이트 몇개만 알면 특정 주제에 대한 검색이 가능했겠지만, 그 때까지 그 사이트들 사이의 내용 유사성에 기초한 어떤 서비스는 없었을 것이다. 현재의 일반적인 검색 엔진에서 제공하는 유사 페이지 검색이라든가 버티컬 검색 엔진 등을 생각하면 일리가 있다. 이제는 특정 사이트 몇몇이 특정 주제에 대한 포탈이 되기 힘들고, 검색 엔진의 쿼리를 통해서 또는 버티컬 검색 엔진을 통해서 그러한 서비스를 하고 있다.

Koster, M. 1994. ALIWEB – Archie-Like Indexing in the WEB.

첫번째 WWW 컨퍼런스인 WWW ’94에 발표된 paper.

1990년 11월에 첫번째 웹서버가 생긴 이후로, 웹의 사용자와 정보의 크기는 점점 늘어나고 있었고, 1993년에는 200개 이상의 웹서버가 있다고 알려지게 되었다. 이렇게 되자, 웹에서 어떤 정보를 찾는 것은 점점 힘들어지게 되었고, 이 문제를 해결하기 위한 여러 노력들이 1993년부터 나타나기 시작했다. 그 결과로 나타난 첫번째 웹 검색엔진이 바로 ALIWEB이었다.

도입 부분에서, 웹의 resource discovery 방법이 진화한 과정을 Browsing – Listing – Searching (Catalogue) – Automatic Collection (from Catalogue) – Automatic Discovery의 단계로 설명하고 있는데 흥미롭다. 현재의 검색엔진에서 Automatic Discovery를 당연시하고 있는 것을 생각하면, 마치 FORTRAN Compiler가 탄생했을 때, 이를 Automatic Programming이라고 부르던 느낌이랄까.

한편, Archie란 여러 Anonymous FTP 사이트가 가지고 있는 파일들을 인덱싱하여 검색할 수 있도록 해주는 Anonymous FTP의 검색 엔진이었다. Archie의 동작 방식은 각 Anonymous FTP 사이트에서 파일 리스팅에 해당하는 파일을 받아서 사용자가 검색 가능하도록 해주는 것이었다. 이 paper에서 Archie-Like라고 부르는 것도 그러한 동작 방식을 사용했다는 것을 의미한다.

ALIWEB의 동작 방식은 다음과 같다.

1. 웹사이트 관리자가 정해진 포맷으로 각 사이트에 대한 인덱스 파일을 만들고 이를 ALIWEB의 웹 인터페이스를 통해 등록한다.
2. ALIWEB은 등록된 웹사이트들의 인덱스 파일들을 자동으로 받아와서 이를 검색 가능하도록 인덱싱한다.
3. 검색을 원하는 사용자는 오늘날의 검색엔진 인터페이스와 거의 같은 모습의 ALIWEB의 웹 인터페이스를 통해서 쿼리를 보내고 결과를 볼 수 있다.

이 paper에서 밝히고 있는 ALIWEB의 문제점은 역시

• 사이트별 인덱스 생성 과정의 어려움, 그리고
• scalability

이다.

사실, 사이트 관리자에 의한 사이트별 인덱스 생성은, 사이트 관리자가 그 사이트에서 어떤 것이 인덱싱 되어야하는가를 가장 잘 알고 있을 것이라는 합리적인 의도를 가지고 있고, Koster는 이러한 방식이 적어도 medium term에서는 잘 동작할 것이라고 예상했지만, 실제로 이는 실패했다. 물론, 사이트 관리자에 의한 사이트별 인덱스 생성이라는 개념은 현재에도 Google Sitemap과 같은 형태로 존재하지만, 적어도 이러한 메커니즘이 Automatic Discovery의 주요한 역할을 맡고 있는 것은 아니다.

어쩌면, 텍스트를 위주로 한 현재의 웹에 대한 Automatic Discovery가 정점에 이르면, 오히려 장기적인 관점에서, 사이트 관리자에 의한 사이트별 인덱스 생성이라는 개념이 유효해질 가능성도 있다. Semantic Web이나 Web Services와 같은 웹을 구조화된 형태로 만드려는 노력이 어떤 방향으로 진행될지는 아직 미지수다.

Scalability의 문제는 프로토타입의 성격을 지닌 ALIWEB에서 해결되리라고 기대할만한 문제는 아니지만, 사이트별 인덱스를 사이트 내의 상위 레벨 서비스에 대해서만 생성한다든가, 특정 분류나 도메인에 한정된  ALIWEB 사이트를 만들어서 해결한다는 생각은 현재 시점에서 바라볼 때는 실망스럽다.

현재의 웹을 바라보면, 상위 레벨 서비스만 검색되면 되는 것이 아니라, 하위 레벨 페이지들이 실제로 사용자들에게 가장 흥미로운 내용을 포함하고 있고, 검색의 결과로서 적합한 경우도 많다. 한편, 특정 분류나 도메인에 한정된 검색도 물론 유용하지만, 이것이 Scalability 부족의 대안으로 나오는 것은 현재 웹의 크기를 고려할 때 바람직하지 못하다.

소스 파일(이하, 파일)도 모듈의 일종이다.

어떤 프로그래밍 언어에서는 파일을 언어 자체가 정의하는 개념(예를 들어, C++의 ‘컴파일 단위’)으로 본다. 어떤 프레임워크에서는 특정한 파일은 어떤 특별한 역할을 하는 코드의 집합으로 본다. (예를 들어, RoR의 파일 구성) 마찬가지로, 어떤 프로젝트에서는 정해진 독특한 규칙에 따라 특정 파일에 특별한 역할을 부여할 수 있다.

이런 면에서, 소스 파일의 구성(File Organization)은 소프트웨어 품질에 영향을 미치는 디자인 결정 중의 하나다.

파일이라는 OS라는 낡고 거추장스러운 곳으로부터 나온 (어떤 면에서) 언어 외적인 요소를, 고매하고 청명한 정신으로부터 태어난 자신의 코드와 결부시키는 것이 불편하게 느껴질지도 모르겠다. 언어 자체가 파일 개념에 의존하지 않는다면, 한 프로젝트의 모든 코드가 한 파일에 들어있든, 1억개의 파일에 들어있든 무슨 상관이 있겠는가.

하지만, 아직은 프로그래밍 세계는 파일이라는 요소에 의존하는 편이다. 그럴 듯한 IDE를 사용하지 않는 프로그래머들도 너무나 많다. (당신이 vim을 IDE라고 주장하더라도 notepad는 어떤가?!) 그들에게 파일은 Readability에 직접 영향을 미치는 단위가 된다. 너무 긴 파일은 너무 긴 클래스나 너무 긴 함수의 문제점과 동일한 문제를 유발한다. 읽기 힘들다. 파악하기 힘들다. 소위, 스크롤의 압박이란거다.

한편, 현재의 IDE들은 언어가 파일에 의존하지만 않는다면, 파일이라는 요소를 배제할 수 있는 포텐셜을 가지고 있으나, 단순하게도, 그렇게 하지 않는다! 그나마 우리를 행복하게 해주기 위해 IDE를 제작하는 분들에게 뭔가를 추궁하지는 않겠다. 아직은 우리는 파일이라는 개념에 너무나 익숙하다. 정말로 파일이 싫은가 하면 그렇지도 않단 말이다.

어쨌든, 파일은 모듈이고 다시 말해, decomposition의 단위다. 이것은 파일이라는 모듈에도 높은 cohesion과 낮은 coupling이 요구된다는 것이다.

Java와 같은 언어에서는 (Top-level) 클래스 각각은 그 클래스의 이름을 가진 독립된 하나의 파일을 점유하는 것이 일종의 컨벤션이다.

얼마전에 코드 리뷰를 한 적이 있는데, Top-level 클래스 5-7개 정도가 하나의 파일에 들어가 있는 경우를 발견했다. 이것을 발견하자 내 직관은 뭔가 잘못된 것이라는 알려주었다. 도대체 이 클래스의 범위는 어디까지인거지? 왜 이렇게 길어? 이 클래스로 이동하려면? (난 이클립스를 사용하고 있고, 코드 navigation 기능은 숙지하고 있으니, 친절하게 알려주지 않아도 된다.) 혼자만의 생각이지만, 다른 개발자가 이런 코드를 보더라도 분명 나와 비슷한 느낌을 받으리라고 생각한다. (무슨 소리?)

자, 그럼 직관이 아니라, 뭔가 납득할만한 설명을 필요한 것 같다. 대체 왜 그  클래스들은 한 파일에 있어야만 할까? 클래스들을 자세히 들여다보면, 1) A와 B는 Use 관계에 있으나, 그 역할은 충분히 다르고, 특히 A와 B는 그 파일 밖에 있는 클래스 P와 Q에 의해서 사용되고 있었다. 2) D는 C의 구현이 되어야할 부분을 다시 모듈화한 것이었다.

1) A와 B는 충분하게 cohesive하지 않을 뿐만 아니라 파일 외부의 클래스에 의해서도 사용되므로 다른 클래스들과 동등한 자격으로 – 즉, 파일로 노출될 필요가 있다. 2) D는 C의 구현에 해당하고 외부로 노출될 필요가 없으므로 Top-level 클래스가 될 필요가 없다. 즉, D는 C의 임베디드 클래스가 되면 훌륭하다.

이런 식으로 리팩토링을 하고 나니, 하나의 파일에는 하나의 Top-level 클래스만이 남아있었다.

물론 하나의 파일에 무조건 하나의 Top-level 클래스만 써야만 하는 법은 없을 것이다. 내가 알지 못하는 문맥에서의 필요성이 있을 수도 있고, Top-level 클래스를 하나의 파일에 모아두는 것에 페티쉬를 가진 경우도 있을 것이다. 물론, 파일 개념의 철폐를 부르짖는 해방주의자도 빼놓을 수는 없다. 하지만, 대부분의 경우에는 별 생각 없이 한 파일에는 하나의 Top-level 클래스를 두는 것으로 생각하면 별 탈 없을 것이고, 어쩌면 칭찬을 들을지도 모른다.

오늘의 Rule of Thumb: Java 프로그래밍에 있어서 하나의 파일에는 하나의 Top-level class를 두자. 땅땅땅.

소프트웨어가 해결하려는 문제가 복잡하다면 그 해결책 즉, 소프트웨어도 복잡해진다. 즉, 소프트웨어의 복잡성은 부정적인 효과를 가지지만, 항상 잘못된 것이고 거절할 수 있는 것은 아니다.

따라서, 소프트웨어의 복잡성 문제를 해결하려고 할 때는 불필요한 소프트웨어의 복잡성(Unnecessary Software Complexity)라는 개념을 가지고 얘기해야한다.

한편, 소프트웨어의 복잡성이 문제의 복잡성에 의존하기 때문에, 문제가 달라지면 불필요한 소프트웨어의 복잡성도 달라진다. 다르게 말하면, 문제가 달라지면, 소프트웨어를 평가하는 기준도 달라질 수 있다는 것이다.

이야기를 하나 해보자. 어떤 소프트웨어 팀은 실제로 많은 문제가 있다고 생각해서, 또는 의욕적이어서 많은 문제를 해결하는 소프트웨어를 만든다. 시간이 지나고, 그런 문제를 해결할 필요가 없어졌고, 사람들은 그런 사실을 잊어버렸다고 해보자. 남아있는 소프트웨어는 그 시점에서 불필요한 소프트웨어의 복잡성이 높은 소프트웨어일테고, 그 소프트웨어의 개발자는 비난을 받는다. 이것은 공평하지 못하다. 소프트웨어 엔지니어링에서 얘기하는 것처럼 문제의 합의에 대한 계약서라도 써놓는 것이 이러한 문제를 해결할까? 그렇지는 않다고 생각한다. 사람들은 ‘문제가 변화한다’는 사실에 대한 명확한 인식을 가지고 있어야할 뿐만 아니라 ‘문제를 알고있다’라는 생각에 대해 좀 더 보수적일 필요가 있다.

문제가 언제 변화하냐고? 문제는 항상 변화한다.

web_crawler_20070223.pdf

올해 초에 신입 팀원들을 대상으로 발표한 자료로, Web Crawler의 기본적인 설계와 구현시 신경써야할 기초적인 사항들을 언급하고 있습니다. 대단한 내용이 있는 것은 아니고 단순히 Mining the Web의 Web Crawler chapter를 정리한 내용입니다.

Web Crawler 개발에 있어서 가장 중요한 것은 무엇이냐고 제게 묻는다면 저는 이 발표자료의 Closing에 적혀있는 한 줄로 대신 답하겠습니다.

Understand status quo of Web

사실 어느 정도 숙련된 개발자라면 Web Crawler의 기초적인 기능들은 대단히 단순하기 때문에 별로 어렵지 않다고 느끼실 겁니다. 저도 물론 처음엔 그렇게 생각했구요. 하지만 현재는 약간 생각이 달라졌습니다. 훌륭한 Web Crawler를 만들 수 있는 능력은 바로 웹의 현재 상태에 관한 지식을 얼마나 가지고 있는가 또는 얻을 수 있는가에 달려있다고 생각합니다. 이 발표자료를 쓸 때보다 이러한 생각이 더욱 강하게 드는 요즈음입니다.