구글의 MapReduce의 간략한 이해

정보검색 2008. 4. 29. 22:56 Posted by 지민아빠
구글에게 MapReduce가 없었다면 현재의 구글은 없었을 찌도 모릅니다. 구글이 대단한 것은 세계에서 가장 많다고 자부할 수 있는 그 방대한 데이터를 유지하고 있는 능력 인 것 같습니다. 이 대단한 능력을 가능하게 하는 것은 바로 구글의 MapReduce가 있기 때문이죠.

구글의 MapReduce는 대용량 병렬처리를 가능하게 합니다. 엄청난 크기의 데이터를 짧은 시간안에 슈퍼컴퓨터가 없어도 처리가 가능 합니다. 하지만 MapReduce도 만능은 아니라서 여기에는 몇가지 조건이 붙습니다.

사용자 삽입 이미지

대표적으로 MapReduce는 key/value pair로 표시할 수 있는 데이터를 병렬처리 할 수 있습니다. key를 표시할 수 없는 데이터는 병렬처리로 나눌수 있는 기준이 없기 때문에 안됩니다. 그리고 batch 형태의 작업만 처리가 가능 합니다. 즉 하나의 작업에 시작과 끝이 존재하여야 나누어서 처리 할 수 있습니다.

사용자 삽입 이미지

MapReduce를 간단히 이해하여 보면 key 형식으로 표현될 수 있는 많은 양의 data 집합을 MapReduce Application이 정한 적당한 기준으로 key를 나누어서 처리한 다음 역시 MapReduce Application이 정한 적당한 기준으로 결과값을 나누어서 모으는 처리방법이 되겠습니다.

사용자 삽입 이미지


구글의 MapReduce를 실제로 사용해 볼 수는 없습니다. 하지만 고맙게도 구글의 논문을 통해서 MapReduce와 같은 동작을 할 수 있는 Hadoop이 오픈소스로 만들어 졌습니다. 현재는 Yahoo의 지원을 받으며 Apache Project로 안정적으로 진행되고 있습니다. Hadoop을 이용하면 구글의 MapReduce를 사용할 수 있습니다.

참고자료

,

해외 유명 블로그 TechCrunch 에 구글 관련 내용이 올라왔습니다. 이 소식을 발빠르게 전해 주시는 여러 블로거님들 덕분에 금방 소식을 접하게 되었습니다. (참 좋은 세상입니다. ^^)

Google Processing 20,000 Terabytes A Day, And Growing (TechCrunch)
구글, 하루에 20000 테라바이트(TB)의 자료를 처리한다고? (학주니닷컴)
구글이 20 petabyte의 데이터를 얼마만에 처리할까?

사용자 삽입 이미지
그럼 이게 실제 얼마나 되는 양일까요? 20PB(페타바이트)는 실제로 감이 잘 안 올만큼 커다란 값이긴 합니다.
이 값은 데이터를 처리할 수 있는 양을 나타내는 것 뿐이고 실제 몇개의 웹페이지를 처리하는 지는 직접적으로 나타내지 않습니다. 하지만 원문글 중간의 표에 나와있는 데이터로 약간 유추해 볼 수 있을 것 같습니다.

2007년 9월을 기준으로 구글의 map input data 가 403,152 TB(테라바이트)라고 합니다. 이걸 웹페이지 기준으로 볼때 웹페이지 한장을 평균 10 KB 라고 가정하면 하루에 약  1조4천5백억개의 웹페이지가 됩니다. map output data 는 34,774 TB, 하루 1천2백억 페이지 정도 됩니다. 구글이 인덱스 하고 있는 페이지가 120억개 라고 가정해 볼 경우, 한페이지당 하루에 10번 다녀갈 수 있는 양입니다. 여러분의 블로그에 구글에서 인덱스 하고 있는 페이지가 1,000개 라면 10,000번 다녀간다는 이야기가 되는 군요. 뭐 실제로 그런지는 모르는 거고, 그렇게 할 수도 있는 능력이라는 것 입니다.

구글에 인덱스 되어 있는 제 블로그 글을 검색해 보면 대충 1,660개 라고 나오던데요. 구글봇이 하루에 얼마나 다녀가는 걸까요? 대단한 능력 인 것 만은 틀림없는 사실 입니다.

출처가 되는 논문은 여기 있습니다. ACL이 걸려 있어서 귀찮으므로 고감자 님이 받아주신 PDF 파일도 첨부 합니다. 저도 아직 자세히 읽어 보지는 못 했습니다. ^^

업데이트: 구글의 Map Reduce 는 gmail 스펨 필터 처리에도 쓰인다고 합니다. 그러니까 저기 논문에 나온 map input data의 데이터 량은 메일 데이터 까지 전부 합친 용량이라고 할 수 있겠습니다.
,

구글 이름의 유래 - googol

정보검색 2007. 11. 19. 16:17 Posted by 지민아빠
The name "Google" originated from a misspelling of "googol", which refers to 10100 (the number represented by a 1 followed by one-hundred zeros).
"Google"이라는 이름은 "googol"을 잘못 표기한데서 유래 한다고 합니다.  1 googol 은 '1'에 '0'이 100개 붙은 숫자 입니다.
1 googol
= 10100
= 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
사용자 삽입 이미지

구글 본사의 이름은 "Googleplex" 입니다.  그리고 "Googolplex"는 10의 googol승을 나타냅니다.

10googol = 1010100

즉 '1'에 '0'이 'googol'개 붙은 숫자 입니다. "Google"의 목표가 전세계의 모든 데이터를 담는 것이라고 하던데, 숫자로 표현한다면 딱 알맞은 이름 인 것 같습니다. :-)

참고자료:
Koller, David. "Origin of the name, "Google." Stanford University. January, 2004.
Hanley, Rachael. "From Googol to Google: Co-founder returns." The Stanford Daily. February 12, 2003. Retrieved on July 14, 2006.

'정보검색' 카테고리의 다른 글

웹 크롤러 Mercator 구조  (6) 2007.11.21
초기 구글 검색엔진의 구조  (0) 2007.11.01
공개 검색엔진 Nutch의 구조  (2) 2007.11.01
,

초기 구글 검색엔진의 구조

정보검색 2007. 11. 1. 14:42 Posted by 지민아빠

현재 구글에서 사용하고 있는 검색엔진의 구조에 대해서 공개되어 있는 정보는 별로 없지만 몇가지 논문을 통해서 공개된 내용이 약간 있다고 합니다.

대부분은 웹검색 시스템의 구조에 관한 설명이고, 블로그 검색이나, Gmail 검색에 사용되는 시스템도 아마 비슷하지 않을까.. 합니다만.. ^^ (구글은 반영속도가 아주 느려도 되는 웹검색 시스템과, 반영속도가 빨라야 하는 블로그 검색을 다른 시스템으로 돌린다고 합니다. GMail 처럼 실시간 반영되어야 하는 검색의 경우 아예 웹검색 엔진과 다른 엔진을 사용한다고 합니다.)

 
여기에서 잠깐, 간단히 살펴 볼 구글 검색엔진 이라는 것은.. 구글의 창시자 인 "Sergey Brin" 과 "Lawrence Page" 가 1997년 인가 1998년에 "Stanford University" 에 있을때 쓴 "The Anatomy of a Large-Scale Hypertextual Web Search Engine" 이라는 논문의 내용을 바탕으로 합니다. 97년 당시의 내용을 바탕으로 하기 때문에 현재의 구조와는 많이 다를거라고 생각 됩니다만, 기본 구조를 살짝 살펴 볼 수 있다는데 의의가 있는 것 같습니다. ^^ 여기에는 "2.1 Page Rank"의 (간단한 개념적 수학공식) 소개나 "4.1 Google Architecture Overview"와 같은 내용이 들어 있습니다.

사용자 삽입 이미지

Figure 1. High Level Google Architecture


설계된 시스템의 목표는 초당 100~1000개의 쿼리를 처리하는 것 이였으며 (1.2절)

논문에서는 이 시스템으로 2400만 건의 페이지를 모아서, 2억5천900만개 이상의 Anchor를 인덱스 하였다고 합니다. (2.2절)

 
그림1의 개괄적인 구조로 보았을때 이때의 시스템은 크게 2개 이상의 스텝으로 나뉘어 동작하여야 하기 때문에 배치작업으로 이루어 졌을 것 같습니다.

그리고 일반적인 Crawler, Indexer, Searcher 와 같은 구조들이 보이고, Nutch 구조와 비교해 보시면 Crawler -> Indexer -> Searcher 로 가는 구조도 거의 똑같아 보입니다. 여기서 crawl 된 페이지에서 추출된 link 를 다시 crawler로 보낼때 DocIndex 부분에서 보낸 다는 것이 제 눈에는 약간 신기해 보였습니다. ^^


이 글은 얼마전에 주워들은 내용을 복습하는 의미에서 논문을 다시한번 살펴보고 정리하는 중에 올리는 글입니다. ^^


참고문헌:
The Anatomy of a Search Engine

2007/11/01 - 공개 검색엔진 Nutch의 구조
,

공개 검색엔진 Nutch의 구조

정보검색 2007. 11. 1. 01:03 Posted by 지민아빠

Nutch는 자바로 구현된 오픈소스 검색엔진 입니다. Lucene이 Indexer 와 Searcher로 구성되어 있고, Nutch는 Lucene에 없는 웹검색에 필요한 모든 기본요소를 전부 갖추어서 웹검색 용으로 확장 한 것이라고 보면 될 것 같습니다. 그래서 Nutch Lucene 기반의 공개 웹검색 엔진입니다. Nutch는 많은 부분 구글 검색 엔진 구조를 목표로 하고 있습니다.

전체적인 구조는 일반적인 웹검색 시스템의 구조와 비슷한 것 같습니다.

사용자 삽입 이미지

Nutch의 구조는 그림과 같은데, 이걸 지금 제가 알고 있는 웹검색 시스템의 구조로 이해하기 위해서 대충 나누어 보면 아래처럼 나눌 수 있을 것 같습니다.

  1. Crawler
    • Nutch는 웹데이터 들을 효과적으로 가져올 수 있는 fetcher 들을 가지고 있습니다. 이를 통해서 목표로 하는 URL 들의 데이터를 수집하고, 이 작업은 목표로 하는 깊이까지 도착하면 멈춥니다.
  2. Repository
    • 수집된 웹 데이터 들은 Repository에 저장됩니다. Nutch에서는 특별히 Repository 라는 명칭을 사용하지는 않지만, WebDB와 Segment들이 여기에 해당 한다고 볼 수 있을 것 같습니다.
  3. Indexer
    • 수집된 데이터는 Lucene에서 사용 가능한 Index 형식으로 구성되어야 합니다.
  4. Searcher
    • 구성된 Index는 Lucene Searcher 에서 사용됩니다.

몇일 뒤에 어떤 고마운 분이 Nutch의 구조나 특징에 대하여 조사 한것을 설명 해 주실텐데 Nutch가 어떻게 생긴건지 전혀 몰라서 간단히 살펴 보았습니다. 이제 어느정도 설명을 들을 만한 최소한의 기본 준비는 한 것 같으니 이제 기다려야 겠군요. ^^


참고문헌:

Introduction to Nutch, Part 1: Crawling by Tom White 2006/01/10 번역본

Introduction to Nutch, Part 2: Searching by Tom White 2006/02/16

Nutch: Open-Source Web Search Software by Doug Cutting(doug@nutch.org) 2004/11/26

Open Source Search by Doug Cutting(cutting@apache.org) 2005/12/05

,

구글 페이지 랭크의 이해를 위한 간단설명

정보검색 2007. 10. 30. 14:57 Posted by 지민아빠
사용자 삽입 이미지
요즘 구글에서 페이지 랭크를 업데이트 하고 있다고, 소식이 들리고 있습니다. 들리는 소식에 의하면 블로그 쪽에 특화된 변화가 있다고 합니다만 아직 정확히 밝혀진 내용은 접해보지 못했습니다.

얼마전에 회사에서 Google's PageRank and Beyond 라는 책을 스터디 한 적이 있습니다. 역시 PageRank의 내용은 수학적인 내용이 거의 전부이기 때문에 수학에 취약한 본인은 다른분들의 도움을 받아서 겨우겨우 쫓아가는 것이 전부 였지만, PageRank의 개념을 이해하고 특성을 이해하는 데는 많은 도움이 되어 나름 뿌듯한 스터디 였습니다. ㅜ.ㅜ

구글의 PageRank라는 개념은 쉽게 이야기 해서 "사람들이 Link를 많이 거는 URL은 사람들이 많이 찾아가는 곳일 테고, 그 만큼 정확한 정보가 있는 곳일테니 URL의 랭킹값을 높게 주자." 라는 이론입니다. 이 것은 사람들이 실제로 어디를 얼마나 찾아가는지 모르기 때문에 이것을 계산하기 위하여 구글에서 개발한 방법입니다. 아마 실제로 사람들이 어디를 돌아다니는지 알 수 있으면 PageRank 보다 더 정확한 랭킹값을 계산 할 수 있을 거라고 생각 합니다.

실제로 구글에서 PageRank 를 어떤 값을 가지고 어떻게 계산하는지 전부 다 공개되어 있지는 않지만 추상적으로 보면 아래 그림과 같은 방법으로 계산 될 겁니다.
사용자 삽입 이미지
출처: How PageRank Works

이렇게 계산 된 값은 이론상 원래 하나의 URL당 하나의 상수값을 가지고 전체의 URL이 일렬로 주욱 순위별로 서 있는 형태를 가지게 됩니다. 그러므로 여러분의 블로그에 여러개의 글들은 전부다 PageRank 값을 가지고 있습니다. 다만 대부분 Top URL을 링크로 거는 경우가 많으므로 가장 널리 알려진 Top URL이 PageRank 값이 가장 높을 확률이 높습니다.
이 값을 보기 쉽게 0부터 10까지의 레벨로 표시한 값이 보통 '3'이네 '7'이네 하고 부르는 값이 됩니다. 레벨별로 분포는 보통 아래그림과 같다고 합니다.
사용자 삽입 이미지
분포를 보면 6레벨 이하의 값은 전세계 웹페이지 중에서 밑바닥 이군요. ㅜ.ㅜ (하지만 그래도 3.5 이상의 값을 가지면 Average에 속할 수 있습니다!!!)

여기까지 구글의 PageRank를 이해하기 위한 간단 설명이였습니다.
자아 마지막으로 Rank 9를 먹는 그날까지!! 고고~~
,
BLOG main image
지민아빠의 해처리

카테고리

분류 전체보기 (68)
블라블라 (16)
정보검색 (15)
우주전쟁 (37)

최근에 올라온 글

지민아빠의 해처리

지민아빠's Blog is powered by Tattertools
Copyright by 지민아빠 [ http://www.ringblog.com ]. All rights reserved.

Tattertools DesignMyself!
지민아빠's Blog is powered by Textcube. Designed by Qwer999.