Google이 어떻게 그렇게 빠를 수 있습니까?

Google이 어떻게 그렇게 빠를 수 있습니까?

---

Google이 쿼리를 빠르게 처리 할 수있게하는 기술과 프로그래밍 결정은 무엇입니까?

내가 무언가를 검색 할 때마다 (하루에 여러 번 중 하나) 결과를 1 초에 가깝거나 미만으로 제공하는 방법은 항상 나를 놀라게합니다. 이를 수행하기 위해 어떤 종류의 구성 및 알고리즘을 사용할 수 있습니까?

참고 : 데스크톱 애플리케이션을 설치하여 내 컴퓨터에서 사용하더라도 Google만큼 빠르지 않을 것이라고 생각하는 것은 압도적입니다. 내가 말하는 것을 계속 배우십시오.

---

다음은 몇 가지 훌륭한 답변과 조언입니다.

• Google 플랫폼
• 지도 축소
• 신중하게 만들어진 알고리즘
• 하드웨어-클러스터 팜 및 대량의 저렴한 컴퓨터
• 캐싱 및로드 밸런싱
• Google 파일 시스템

---

지연 시간은 디스크 액세스로 인해 중단됩니다. 따라서 쿼리에 응답하는 데 사용되는 모든 데이터가 메모리에 유지된다고 믿는 것이 합리적입니다. 이는 수천 대의 서버를 의미하며 각 서버는 여러 샤드 중 하나를 복제합니다. 따라서 검색의 핵심 경로는 자사의 주력 분산 시스템 기술인 GFS, MapReduce 또는 BigTable에 도달하지 않을 것입니다. 이들은 크롤러 결과를 대략적으로 처리하는 데 사용됩니다.

검색의 편리한 점은 강력하게 일관된 결과 나 완전히 최신 데이터를 가질 필요가 없기 때문에 더 최신 검색 결과를 사용할 수있게 되었기 때문에 Google이 쿼리에 응답 할 수 없다는 것입니다.

따라서 가능한 아키텍처는 매우 간단합니다. 프런트 엔드 서버가 쿼리를 처리하고이를 정규화 (불용어 등을 제거하여 가능) 한 다음 쿼리 공간의 해당 부분을 소유하는 복제본의 하위 집합에 배포합니다 (대체 아키텍처는 모든 복제 세트 중 하나가 모든 쿼리에 연결되어야 함). 많은 복제본이 쿼리되고 가장 빠른 응답이 이깁니다. 각 복제본에는 메모리에서 결과를 매우 빠르게 조회하는 데 사용할 수있는 문서에 대한 인덱스 매핑 쿼리 (또는 개별 쿼리 용어)가 있습니다. 다른 소스에서 다른 결과가 반환되는 경우 프런트 엔드 서버는 html을 뱉어 내면서 순위를 매길 수 있습니다.

이것은 아마도 구글이 실제로하는 것과는 먼 차이가있을 것입니다. 그들은이 시스템의 수명을 설계했을 것이므로 이상한 영역에 더 많은 캐시, 이상한 인덱스, 그리고 다른 가능한 차이점들 사이에 일종의 펑키 한로드 밸런싱 체계가있을 수 있습니다. .

---

하나의 답변에 넣는 것은 너무 많습니다. http://en.wikipedia.org/wiki/Google_platform

---

내가 웃긴 사실을 발견 한 한 가지 사실은 Google이 실제로 생물 정보학에 의해 운영된다는 것입니다 ( '좋아요, 내가 생물 인 자라서 재미 있다고 생각합니다. 설명하겠습니다.

생물 정보학은 초기에 거대한 문자열의 작은 텍스트를 매우 빠르게 검색하는 데 어려움을 겪었습니다. 우리에게“거대한 끈”은 당연히 DNA입니다. 종종 단일 DNA가 아니라 다른 종 / 개체의 여러 DNA 데이터베이스입니다. 작은 텍스트는 단백질이거나 그에 상응하는 유전자 인 유전자입니다. 컴퓨터 생물학 자의 첫 번째 작업의 대부분은 유전자 간의 상 동성을 찾는 것으로 제한되었습니다. 이것은 이미 알려진 유전자와의 유사성을 주목함으로써 새로 발견 된 유전자의 기능을 확립하기 위해 수행됩니다.

이제 이러한 DNA 문자열은 실제로 매우 커지고 (손실이 있습니다!) 검색을 매우 효율적으로 수행해야합니다. 따라서 현대의 문자열 조회 이론의 대부분은 계산 생물학의 맥락에서 개발되었습니다.

그러나 꽤 오래 전부터 기존의 텍스트 검색이 소진되었습니다. 즉, 각 단일 문자를 보지 않고도 부 선형 시간에 큰 문자열을 검색 할 수있는 새로운 접근 방식이 필요했습니다. 이것은 큰 문자열을 전처리하고 그 위에 특별한 인덱스 데이터 구조를 구축함으로써 해결할 수 있음을 발견했습니다. 많은 다른 데이터 구조가 제안되었습니다. 각각 강점과 약점이 있지만 일정한 시간에 조회가 가능하기 때문에 특히 주목할만한 점이 있습니다. 이제 Google이 운영하는 규모에서 이것은 더 이상 엄격하게 사실이 아닙니다. 서버 간 부하 분산, 전처리 및 기타 정교한 작업을 고려해야하기 때문입니다.

But in the essence, the so-called q-gram index allows a lookup in constant time. The only disadvantage: The data structure gets ridiculously big. Essentially, to allow for a lookup of strings with up to q characters (hence the name), it requires a table that has one field for each possible combination of q letters (that is, q^S, where S is the size of the alphabet, say 36 (= 26 + 10)). Additionally, there has to be one field for each letter position in the string that was indexed (or in the case of google, for each web site).

To mitigate the sheer size, Google will probably use multiple indices (in fact, they do, to offer services like spelling correction). The topmost ones won't work on character level but on word level instead. This reduces q but it makes S infinitely bigger so they will have to use hashing and collision tables to cope with the infinite number of different words.

On the next level, these hashed words will point to other index data structures which, in turn, will hash characters pointing to websites.

Long story short, these q-gram index data structures are arguably the most central part of Google's search algorithm. Unfortunately, there are no good non-technical papers explaining how q-gram indices work. The only publication that I know that contains a description of how such an index works is … alas, my bachelor thesis.

---

Here are some of the great answers and pointers provided:

• Google Platform
• Map Reduce
• Algorithms carefully crafted
• Hardware - cluster farms and massive number of cheap computers
• Caching and Load Balancing
• Google File System

---

They have implemented good, distributed, algorithms running on a vast amount of hardware.

---

One of the most important delays is webservers is getting your query to the webserver, and the response back. THis latency is bound by the speed of light, which even Google has to obey. However, they have datacenters all over the world. As a result, the average distance to any one of them is lower. This keeps the latency down. Sure, the difference is measured in milliseconds, but it matters if the response has to arrive within 1000 milliseconds.

---

Everyone knows it's because they use pigeons, of course!

Oh yeah, that and Mapreduce.

---

They pretty much have a local copy of the internet cached on thousands of PC's on custom filesystems.

---

Google hires the best of the best. Some of the smartest people in IT work at google. They have virtually infinite money to throw at hardware and engineers.

They use highly optimized storage mechanisms for the tasks that they are performing.

They have geographically located server farms.

---

An attempt at a generalized list (that does not depend on you having access to Google's internal tools):

1. Parellelize requests (e.g. break up a single request in to smaller sets)
2. Async (make as much asynchronious as possible, e.g. won't block the user's request)
3. Memory/cache (Disk I/O is slow, keep as much as possible in memory)
4. Pre-compute (Do as much work as possible before hand, don't wait for a user to ask for data/processing)
5. Care about your front-end HTML (see Yslow and friends)

---

You can find in the google research homepage some pointers about the research papers written by some of the google guys. You should start with the explanatio of the google file system and the map/reduce algorithm to try and understand what's going on behind the google pages.

---

This link it also very informative Behind the scenes of a google query

---

Hardware.

Lots and lots of hardware. They use massive clusters of commodity PCs as their server farm.

---

TraumaPony is right. Tons of servers and smart architecture for load balancing/caching and voila you can run query in under 1 second. There was a lot of articles on the net describing google services architecture. I'm sure you can find them via Google :)

---

HenryR is probably correct.

Map Reduce does not play a role for the search itself, but is only used for indexing. Check this video interview with the Map Reduce inventors.

---

An additional reason appears to be that they cheat on the TCP slow start algorithm.

http://blog.benstrong.com/2010/11/google-and-microsoft-cheat-on-slow.html

---

And algorithms that can harness that hardware power. Like mapreduce for instance.

---

If you are interested in more details about how the google cluster works, I'll suggest this open source implementation of their HDFS.

It's based on Mapreduce by google.

---

1. Multi staged data storage, processing and retrieval

2. EFFICIENT Distribution (100's of 1000's of machines) of the above tasks

3. Good framework to store the raw data and the processed results

4. Good framework to retrieve the results

How exactly all these are done is summarized by all the links that you have in the question summary

참고URL : https://stackoverflow.com/questions/132359/how-can-google-be-so-fast