웹로봇에 대해서 질문드립니다.
글쓴이: silveracy / 작성시간: 목, 2011/04/07 - 12:37오후
요즘 제가 웹 크롤러를 만들고 있습니다.
물론 학교 과제로 만들고 있는건데요
제가 제작한 크롤러는 정말 간단합니다.
URL->파일분석->URL추출->URL 큐에 삽입 ->큐에서 다시 URL POP->URL->처음부터 반복
보통 한페이지를 읽어오면 URL이 200~300개쯤 있습니다.
그럼 중복검사를 거쳐도 100개쯤은 새로운 URL이 포함되게 되어 있습니다.
다 유용한 URL이 되게 되는것입니다.
근데 여기서 문제점... 큐가 줄어들지 않습니다. 교수님께서는 페이지 20만개 쯤은 가져왔으면 좋겠다고 생각하십니다.
근데 7~8만개쯤 되면.. 큐에 삼백만개 쯤 들어가게 되고, 메모리가 800메가쯤 할당했음에도 불구하고 800메가를 넘겨 뻗어버립니다.
현재 프로그램을 php로 짜서 쉘스크립트 처럼 돌리고 있는데요...
프로세스를 나누는 방법에 대해서 좀 알려 주실 수 있으신가요?
Queue가 무한 증가하지 않게 할 수 있는 방법에 대해서요;;
*참고로 DBMS에 Queue를 넣어서 작업하는 방법도 있을 것 같은데... 일단 DB에 접근하면 효율성이... 너무 떨어질 것 같아서.. 대신 쓰레드나 프로세스를 많이 돌릴 수는 있을 것 같습니다.
Forums:
20만개만 보고 싶다면, 큐에 20만개 이상 넣지
20만개만 보고 싶다면, 큐에 20만*번* 이상 넣지 않으면 되잖습니까 ?
음.. 저도 그렇게 할까 했는데요...
과제는 그렇게 해서 내면 되는데...
그래도... 좀더 일반해를 찾고 싶어서 이런 글을 올리게 되었습니다.
주기억장치에 대한 일반해라면, 메모리 사용량과
주기억장치에 대한 일반해라면, 메모리 사용량과 성능사이의 trade-off 를 벗어나실 수 없을 겁니다.
예를들어,
어떤 페이지를 완전히 파싱해서 얻어진 모든 url 을 큐에 집어넣으면 그 페이지를 다시 파싱할 필요가 없으니 성능은 좋지만 메모리 사용량이 증가합니다.
어떤 페이지를 파싱한 결과 중 n 번째 url 을 사용하도록 한다면, 그 페이지의 모든 url 대신 그 페이지에 대한 n 만 기억하고 있으면 되니 메모리 사용량이 줄어들겠지만 필요할 때 마다 매번 페이지를 가져와서 파싱한다음 n+1 번째 url 을 얻어내야하므로 성능이 떨어집니다.
감사합니다~
과제용은 큐의 제한을 5만개로 해놓고 작업하고 있습니다.
감사합니다~!!!
Thread를 사용해서 미리 불러올 수만 있다면, 좋은 해결 방법중 하나가 되지 않을까 싶습니다만, 이건 나중에 해봐야겠습니다
아니면, 제가 이해를 잘못한것일까요??
....
제가 제대로 이해한거 같진 않습니다만, 그냥 딱 드는 생각이 이겁니다.
아무리 프로세스를 나눈다 하더라도 언젠간 고아 페이지들 말고는 웹상에 있는 모든 주소들을 스캔 하게 될겁니다.
웹상의 모든 주소를 저장할수 있는 메모리 공간이 있는 시스템이 있을까요?
주소의 새로운 주소의 새로운 주소의 새로운 주소의 ..... 새로운 주소로 간다면 queue가 계속 증가하는건 당연한거 같아 보이네요....
제가 설명을 잘못드린것 같습니다.
말씀하신데로 없습니다.
전 다만 pop을 좀더 빨리 할 수 없을까? 라는 고민을 해보았는데 논리상 맞지 않는 부분이네요...
답변 감사합니다~
..
큐가 안줄어드는건 당연해 보이네요... 그래도 더 많은 결과를 처리하고 싶으시다면 메모리에 넣지 말고 파일로 저장하던지 DB를 쓰던지 하시는게 옳은것 같아요.
그방법이 제일.. 괜찮을 것 같습니다.
아무래도 DB에 저장하는것이 제일 좋을 것 같은데;;
혹시 DB를 잘 사용 하신다면
한 table이 커지면 알아서 물리적 계층(HDD에서 FILE)을 분리하는 그런 옵션이 있는지만 확인해 주실 수 있으신가요?
죄송합니다.
답변 감사합니다~
breath-first search를 쓰시는 것
breath-first search를 쓰시는 것 같은데, depth-first search를 쓰면 되지 않을까요?
각 페이지마다 최종적으로 읽은 위치만 추가적으로 기억하고 있다면, 메모리 사용량이 훨씬 줄어들겠지요.
단, 백트래킹할때마다 페이지를 다시 읽어야하고, 페이지 내용이 그 짧은 시간내에 바뀌었으면 난감하다는 문제도 있겠지만요.
그리고 프로세스를 나눈다고 하더라도, 나누는 방법도 큰 문제가 되고, 합치는 것 또한 쉬운 문제가 아닙니다.
------------------------------
How many legs does a dog have?
저도 이방법을 생각을 안해본것은 아니었는데요;;;
depth-first search의 경우에 탐색의 기본 조건은 끝이 있어야 하는 것이라고 생각하는데요(아니면 깊어지기만 하기 때문입니다.)
웹페이지에 있는 URL을 따오는 형식이라 웹을 타고타고 끝까지 갔을때...
끝을 예상하기 어려워서 이방법을 쓰지 않았습니다...
혹시 DFS를 다른 방식으로 사용할 수 있는건가요??
저도 쉬운문제가 아니라고 생각하여 질문을 올려보았습니다...
답변 감사합니다~
끝이야 원하는 페이지 갯수를 채우거나 이전에 들렸던
끝이야 원하는 페이지 갯수를 채우거나 이전에 들렸던 페이지 다시 가는 거겠죠 또는 더이상 링크가 없거나
옆으로 가나 밑으로가나 숫자만 채우면 되는거 아닌가요
느리기는 하겠지만 가장 단순한 구현이라 생각하는데 말이죠
db쓰는건 배보다 배꼽이 더 큰 것 같아서 말이죠
------------------------------
How many legs does a dog have?
...
DFS는 웹을 긁어오는 데 적합한 방법이 아닐 것 같습니다.
재수없게 링크를 몇 번 타다가 성인사이트로 빠지면 그 이후 링크 백만개를 포르노만 긁는 바람직한(?) 결과가 발생할 수도...
Sideeffect죠 긍정적인 ㅎㅎ
Sideeffect죠 긍정적인 ㅎㅎ
------------------------------
How many legs does a dog have?
중복검사를 해야 하고 자료의 수가
중복검사를 해야 하고 자료의 수가 적지않으므로
DBMS에 넣는게 더 효율적입니다
중복검사를 하는 방법은 어이 없지만...
해시트리를 만들기도 짜증나고 해시는 SAH-1을 사용했습니다.
SHA-1이 겹칠확률도 거의 없다고 해서
그냥 파일이름을 SHA-1해시로 해서 파일저장할때 중복이 있으면 error를 찍게 했습니다만,
생각해보니 DBMS가 훨씬 편하겠군요...
답변 감사합니다~
로봇이 돌다가 죽으면 Queue가 날아가나요 ?
제 생각에도 가장 좋은 해결책은 DBMS 라고 생각합니다.
DBMS가 무거울 거라고 생각하신다면,
실제로 긁어보셔서 알겠지만 대부분의 시간은 긁고 분석하는데 사용됩니다.
큐가 줄어든지 않는다면
큐가 줄어들지 않게 코딩되어 있기 때문입니다. ^^
다른 이유로 큐가 줄어들지는 않습니다.
url pop 하면 큐가 삭제되는 건가요?
"URL->파일분석->URL추출->URL 큐에 삽입 ->큐에서 다시 URL POP->URL->처음부터 반복"
에서 url pop 밖에는 큐가 줄어들지 않을 것 같은데요.
7~8만개 페이지를 읽어오면 800만개 url 정도가 큐에 쌓이는게 맞네요.
이미 사용한(참조한) url은 파일등으로 저장해서 큐를 간소화해보는 걸 생각해 보세요.
댓글 달기