زمان اعجاب‌آور جست‌و‌جو در گوگل از کجا ناشی می‌شود؟

[Best Programmer]

نویسنده : آزاد کمالی روستا
http://www.systemgroup.net/admin/images/attachs/BA122.JPG
همه‌ی شما دست کم یک‌بار تجربه‌ی جست و جو در سایت Google™ را داشته‌اید و بی‌گمان متوجه زمانی که "با افتخار" در بالای نتایج جست‌و‌جو و در کنار تعداد صفحات پیدا شده نوشته می‌شود گشته‌اید. پیدا کردن صدها هزار صفحه در کسری از ثانیه واقعاً افتخار هم دارد. اما چه گونه چنین کاری ممکن است؟

در مقاله‌ی "Serverها باهم چه تفاوتی دارند"[1] به برخی از تجهیزات سخت‌افزاری و تکنولوژی‌هایی که در انجام این کار به کمک چنین سازمان‌هایی می‌آیند اشاره کردیم. حال در این مقاله به جزئیات بیشتری (و البته تنها به بحث درباره‌ی گوگل) می‌پردازیم.

بیایید ابتدا مشکل را پیدا کنیم: متوسط زمان پویش داده‌ها[2] در بهترین دیسک‌های سخت موجود حدود 4میلی ثانیه است. زمانی که انسان به عنوان "لحظه" درنظر دارد حدود 50میلی ثانیه است. حال اگر شما فقط به یک پویش برای هر درخواست کاربران احتیاج داشته باشید، قبل از این‌که کاربری اعلام کندی سرعت کند، تنها12 درخواست را می‌توانید جواب‌گو باشید. اگر برنامه‌ی مدیریت پرونده‌ها[3] و بانک اطلاعاتی را نیز اضافه کنید، این مقدار به یک سوم کاهش می‌یابد. درضمن نگه‌داری اطلاعات درخواستی در حافظه‌ی نهانگاهی[4] نیز کمکی نمی‌کند، چرا که تنها به درد نفر دوم می‌خورد و وقتی که با میلیون‌ها نفر در روز که هرکدام درخواست مخصوص خود را دارند سرکار دارید، کاربردی ندارد.

و اما راه‌حل: شاید باورکردن آن مشکل باشد اما.... همان گونه که سرویس "پیام فوری" شرکت AOL®[5] تمام پیام‌ها را در حافظه‌‌ی اصلی(RAM) "خدمات‌رسان"یا Server های خود نگه می‌دارد، گوگل نیز از دیسک‌های سخت خود فقط برای اجراشدن سیستم‌عامل و برنامه‌های مورد نیاز(به اصطلاح برای Bootشدن) استفاده می‌کند و تمام اطلاعات مربوط به جست‌و‌جو را در حافظه‌ی اصلی(RAM) نگه می‌دارد!!

اگر دقت کرده باشید، وقتی گوگل سایتی را که با شرایط جست‌و‌جوی شما همخوانی دارد پیدا می‌کند، بخش‌هایی از سایت که دارای کلمات مورد نظرهستند را نیز نمایش می‌دهد. این درحالی است که سایر موتورهای جست‌و‌جو تنها چند جمله از اول صفحه‌ی مورد نظر را نشان می‌دهند.

برای انجام چنین کاری، گوگل باید یک ( و حداقل یک) کپی از آن صفحه را دراختیار داشته باشد. این بدان معنی است که گوگل چندین[6] کپی از تمام وب در حافظه‌ی Serverهای خود دارد[7].



گوگل غیر از جست‌و‌جوی سریع چه دارد؟

قدرت موتور جست‌و‌جوی گوگل نه تنها در زمان پایین جست‌و‌جوهای آن، بلکه در تعداد صفحاتی است که به عنوان نتیجه بر می‌گرداند.

گوگل وب را به دنبال صفحات جدید می‌گردد و یک کپی از آن‌ها را به بانک خود اضافه می‌کند[8]. پس اگر هنگامی که به دنبال موضوعی بودید و سایت خود را در لیست سایت‌های نتیجه‌ی جست‌و‌جو یافتید، درحالی که آن را بصورت دستی به بانک گوگل اضافه نکرده بودید، تعجب نکنید (البته تعجب کنید چون جای تعجب دارد ولی دلیلش را بدانید).

سرویس جست‌و‌جوی باور نکردنی گوگل با سرویس پست الکترونیکی جدیدش باورنکردنی‌تر می‌شود. با راه‌اندازی این سرویس بنظر می‌رسد گوگل نه‌تنها قصد از راه به در کردن، بلکه شاید "له کردن" رقبا را در سر می‌پروراند. درحالی که Yahoo® با کاهش حجم جعبه‌های پستی[9] رایگان از 6مگابایت به 4مگابایت و خارج کردن سرویس POP3 از لیست سرویس‌های رایگان، کاربران اش را به سمت سرویس‌های غیر رایگان سوق می‌دهد، گوگل با دست و دلبازی تمام، درنظر دارد به هر جعبه پستی 1.000مگابایت فضا اختصاص دهد. البته درمورد سرویس POP3 اعلام کرده که هنوز برای راه‌اندازی‌اش تصمیمی نگرفته است.

برای نگه‌داری این اطلاعات، گوگل از یک تیم خبره‌ِی برنامه نویس برای ابداع یک File System مخصوص بهره گرفته است. این تیم، نتیجه‌ی تحقیقات 10سال اخیر دانشگاه‌ها را در زمینه‌ی نرم‌افزار به‌خدمت گرفتند تا یک روش نگه‌داری، بازیابی و پردازش اطلاعات غیرمتمرکز را به وجود بیاورند.

Hot Mail™، 60میلیون کاربر دارد. گوگل را باید برای 100میلیون کاربر درنظر بگیریم (هرچند کم‌کم به این مقدار برسد). واضح‌ترین مسئله این است که شما نمی‌توانید اطلاعات کاربران‌تان را از دست بدهید، در ضمن نمی‌خواهید که هیچ‌گاه در دسترس نباشید، پس باید اطلاعات را Replicateکنید. RAID هم پیشنهاد خوبی نیست، اگر یک دیسک خراب شود، به یک نفر برای تعویض آن نیاز دارید و اگر بیش از یک دیسک خراب شود احتمال از دست دادن اطلاعات را خواهید داشت. درضمن به سخت‌افزارهای گرانی نیز احتیاج دارد. مهم‌تر از همه‌ی این‌ها RAID دردسترس بودن را در سطح Server تضمین نمی‌کند(در سطح دیسک سخت تضمین می‌کند).



گوگل به کمک File System ابداعی خود، اطلاعات را در 3 محل نگه‌داری می‌کند. اگر یکی از Serverها(یا دیسک‌ها) از کار بیافتند، آن را به همان حال رها می‌کنند تا در دوره‌های بازدیدی، تعمیر/تعویض شود. درعوض این از کارافتادگی را از طریق نرم‌افزاری و بصورت خودکار جبران می‌کنند. با از کار افتادن یکی از 3بخش نگه‌داری اطلاعات، یک کپی از دوبخش باقی مانده گرفته شده و پس از فشرده سازی 3به1، در محل جدیدی نگه‌داری می‌گردد.



مشکل Serverهای گوگل تنها ظرفیت دیسک‌های نیست، بلکه پردازنده‌های آن‌ها نیز بصورت دایم مشغول فهرست گذاری(Indexing) اطلاعات هستند. هر واحد از Serverهای گوگل تنها 1یا2 دیسک سخت دارد(بدون هیچ RAID Controllerای).



بخاطر این ابعاد گسترده و با توجه به نرم‌افزار مخصوص تهیه شده، هزینه‌ی هر گیگابایت فضا برای کاربران حدود 2دلار برآورد می‌شود.



با تمام حرف‌ها و حدیث‌هایی که درباره‌ی توقف یا به مرحله‌ی اجرا رسیدن این پروژه وجود دارد، بنظر نگارنده هیچ‌چیز نمی‌تواند قدرت چنین فناوری را زیر سئوال ببرد.





برگرفته از:

www.Google.com

www.Allteq.com.au

Blog.topix.net

The secret source of Google’s power. (2004-04-04)

Memory Resident

Miscoranda.com

GMail Beta Testing. Posted by Sean B. Palmer, (2004-04-06)





--------------------------------------------------------------------------------

1 جالب است بدانید که گوگل خیلی به استفاده از آن Serverهای گرانقیمت اعتقاد ندارد و از آن‌ها چندان بهره نمی‌گیرد!!

2 Data Seek Time

3 File System Manager

4 Caching

5 AIM™: AOL® Instant Messages

6 اطلاعات در چندین محل نگه‌داری می‌شوند سپس بکمک سرویس‌هایی موسوم به سرویس‌های "خوشه‌ای"(Clustering) تمام این چند محل، بصورت یک واحد نمایان می‌شوند.

7 This means that Google™ is currently storing multiple copies of web in RAM

8 We add and update new sites to our index each time we crawl the web.

9 Mailbox

[nematia]

عالی بود. ادامه بده. شاید ما هم یاد گرفتیم از این کارها کردیم.

[SoheilKH]

گوگل نیز از دیسک‌های سخت خود فقط برای اجراشدن سیستم‌عامل و برنامه‌های مورد نیاز(به اصطلاح برای Bootشدن) استفاده می‌کند و تمام اطلاعات مربوط به جست‌و‌جو را در حافظه‌ی اصلی(RAM) نگه می‌دارد!!

:خیلی متعجب: :متفکر:

[Hidarneh]

گوگل نیز از دیسک‌های سخت خود فقط برای اجراشدن سیستم‌عامل و برنامه‌های مورد نیاز(به اصطلاح برای Bootشدن) استفاده می‌کند و تمام اطلاعات مربوط به جست‌و‌جو را در حافظه‌ی اصلی(RAM) نگه می‌دارد!!

ببخشید این خیلی خیلی خیلی متعجب ( یعنی همون کف کرده ) نداره؟ ولی جدای از شوخی مگه چقدر RAM دارن اون سرورهاش ؟

[nematia]

چیز واقعا جالبیه.
Wade smacked me on the head (gently) and asked why I was even thinking about disk anymore. Disk is dead; just put the whole thing in RAM and forget about it, he said.
ولی مثل اینکه موضوع هنوز کاملا برای بعضی ها روشن نیست:
Not necessarely, Google does not have to keep the WHOLE WWW in RAM...that would be silly, you need to apply some statistics to that, there's a very good chance that 60% of queries are about Sex and computers, MP3 and so on, so you would keep those queries in RAM and dynamiclly update the query list on a weekly basis (for surges in demand such as news related items) And then you would only keep the first 20 results in RAM because you KNOW that 70% of surfers never go pass the 20th result page.

For all the rest you send the request to the disk and log the number of hits in order to update the system later on...easy !

یه مقاله بسیار جالب هم پیداکردم :
http://backrub.nerisoft.com/May1998/anatomy.htm
The Anatomy of a Large-Scale Hypertextual Web Search Engine

یه عکس از این مقاله ضمیمه میکنم.

[Best Programmer]

نویسنده : محمد حسین آشفته و آزاد کمالی روستا
هرگاه صحبت از شبکه‌های رایانه‌ای به میان می‌آید، اولین دسته‌بندی بین رایانه‌های موجود که به اذهان خطور می‌کند به صورت رایانه‌های Server و Client است.

شاید تا نام Server را بشنویم به یاد یک رایانه با تراشه Pentium IV یا نهایتاً رایانه‌های تک مارک(Brand) با 2 یا 4 تراشه اصلی بیافتیم. آیا واقعاً Server همین است؟ آیا شرکت هایی با تعداد کاربران زیاد و انواع سرویس‌ها از همین رایانه‌ها به عنوان Server استفاده می‌کنند؟ آیا شرکت‌هایی مانند AOL[1]،Yahoo، Microsoft[2]، CNet(حتماً Download.com رو دیدین؟) و ... از چنین رایانه‌هایی به عنوان Serverهای خود استفاده می‌کنند؟ آیا مجموعه‌هایی مانند US Navy از برد اصلی P4s500 شرکت Asus (از همان‌ها که در بازار رضا می‌فروشند!) به عنوان برد Server خود استفاده می‌کند؟



همواره وقتی در یک زمینه، کار به جاهای تخصصی می‌رسد، ابزارها نیز با ابزارهای عادی متفاوت شده و به سمت ابزارهای تخصصی می‌روند. در زمینه‌ی استفاده از رایانه‌ها نیز چنین است. ممکن است هنگامی که نیاز به دادن سرویس "بانک‌های اطلاعاتی" به 200 یا 500 کاربر دارید، بتوانید از یک Server ساده با 2یا 4 پردازنده و حافظه‌های سخت‌افزاری با فناوری RAID[3] استفاده کنید. اما آیا برای دادن انواع سرویس‌هایی که حتی یک لحظه هم نباید قطع شوند نیز، می‌توان از چنین امکاناتی استفاده کرد؟ بنا بر تحقیقات صورت گرفته در سال 1999، بیش از نیمی از Serverها نیاز دارند به صورت 7 روز در هفته و 24 ساعت در روز سرویس دهند- به یقین این آمار برای Serverهای شبکه‌ی اینترنت بیش‌تر از " نیمی" می‌شود- و به طور متوسط هر ساعت قطعی سرویس آن‌ها بیش از 10.000 دلار برای شرکت‌شان ضرر دارد (شاید برای اطلاعات بیشتر درمورد ارزش زمان قطعی Serverها بعدا مقاله‌ای تهیه کردیم).



نیاز مجموعه‌های بزرگ به Serverها، علاوه بر در دسترس بودن همیشگی، در سرعت بالای انجام عملیات در واحد زمان،در حجم اطلاعاتی که باید نگه‌داری شود و در حجم اطلاعاتی که در لحظه درخواست می‌شود نیز خواهد بود.



یک راه برای پاسخ‌گویی به نیازهای بالا، استفاده از رایانه‌هایی در رده‌ی رایانه‌های معمولی است(با تراشه‌های سازگار با تراشه‌های Intel®) که درآن‌ها برای رفع مشکلات گفته شده، افزون بر استفاده از قدرتمند ترین قطعات در کلاس قطعلات عادی، تعداد آن قطعه‌ها را نیز بیشتر می‌کنند. مثلاً تعداد کارت‌های شبکه 1Gbprs را به 2 یا 4 افزایش می‌دهند، از RAMهای DDR266Mhz (یا حتی RD800Mhz) و آخرین تراشه‌های سازگار با Inter® در تعدادزیاد استفاده می‌کنند. برای نگه‌داری اطلاعات، در کنار استفاده از چندین دیسک سخت[4] SCSI ، از سیستم‌های RAID استفاده می‌کنند. این سیستم‌ها امکان بهره‌گیری از چند دیسک سخت به صورت یک دیسک سخت واحد را می‌دهند. این کار علاوه بر بالارفتن سرعت، امکان دسترسی به اطلاعات حتی هنگامی که یکی از دیسک‌ها از دست رفته‌اند را ممکن می‌سازد. نکته‌ی جالب در مورد برخی از این رایانه‌ها، قابلیت تعویض دیسک‌های سخت‌ِ خراب حتی درحالی که سیستم درحال سرویس دادن است و کاربران مشغول کارند می‌باشد(قابلیت " تعویض داغ" یا تعویض در حین کارکرد)[5].

سیستم‌های عامل این رایانه‌ها معمولا سیستم‌عامل Windows®(نسخه‌های معمولی و یا خاص) و یا Linux® هستند.

اما درحالت تخصصی‌تر، افزایش قطعات به صورت دسته جمعی انجام می‌شود، یعنی به جای این‌که حافظه یا دیسک سخت Server را افزایش دهند(یا در کنار افزایش آن‌ها)، یک رایانه‌ی دیگر به آن اضافه می‌کنند! یکی از بزرگ‌ترین مزایای این کار این است که همچنان که به منابع بیشتری احتیاج پیدا می‌کنید، می‌توانید آن‌ها را قوی‌تر سازید (در مقیاس بزرگتری نسبت به روش قبل حرکت می‌کنید).

به عنوان مثال از محصولات IBM® می‌توان به سری X(XSeries®)، اشاره کرد. اگر یک X445™ برای شرکت خود بخرید، یک رایانه با نهایتاً 4 تراشه(می‌توانید فقط 2 تراشه داخلش داشته باشید)، 32گیگابایت حافظه(RAM) و 293.6گیگابایت دیسک سخت دراختیار دارید. اما شما می‌توانید تا 8 عدد از این نوع Server را در کنارهم به خدمت بگیرید.(32پردازنده، 256گیگابایت حافظه و بیش از 1ترابایت دیسک سخت!!) شرکت IBM با یک اصطلاح زیبا از این گونه رایانه‌ها یاد می‌کند: رایانه‌هایی که بابت آن‌ها "، هزینه می‌کنید، درحالی که که بزرگ می‌شوید[6]( و به منابع بیشتری احتیاج پیدا می‌کنید)".

در این حالت برای هر یک از این واحدها می‌توان یک سیستم‌عامل داشت یا برای هرچند واحد یک سیستم‌عامل و یا حتی برای یک واحد بیش از یک سیستم‌عامل. سیستم‌عامل این Serverها می‌تواند تمام سیستم‌های عامل متداول برای یک Serverمعمولی (مانند Windows® 2003,2000Server/Advanced Server، Novel® Netware®، Linux® و ...) باشد. البته دقت کنید که این نرم‌افزارها خود نیز محدودیت‌هایی دارند. مثلا نسخه‌ی 64بیتی سیستم عامل Windows 2003 Server تعداد 64 پردازنده و 512گیگابایت RAM را پشتیبانی می‌کند. معمولاً حافظه‌های این رایانه‌ها نیز قابلیت " تعویض داغ" را دارند.




در همین راستا می‌توان به فناوری Serverهای تیغه‌ای نیز اشاره کرد. در این فناوری بسیار جالب و جدید، مکان‌هایی که برای قرارگیری رایانه‌ها قرار گرفته، افزون بر این‌که امکان برقراری ارتباط پرسرعت را برای استفاده از مزایای بالا به آن‌ها می‌دهد، منابعی چون: خنک کننده‌ها، درایو‌های لوح فشرده(CD or DVD Drives)، درایو‌های دیسکت و فراهم کنندگان توان(Power suppliers) را برای آن‌ها به اشتراک می‌گذارد. در این‌صورت علاوه بر اشغال فضای کمتر، مجبور به پراخت هزینه‌ی کمتری نیز هستیم.

رایانه‌ی HS40®، محصول IBM از این دسته است که می‌توان تا 14 عدد از آن‌ها را داخل یک محفظه‌ مخصوص قرار داد. هر یک از این رایانه‌ها دارای 2تاچهار پردازنده، 16گیگابایت حافظه، 2(یا بیشتر) کارت شبکه‌ی 1گیگابیت در ثانیه و بیش از 293گیگابایت دیسک سخت‌اند.





رایانه‌ی Sun® Fire® 15K نیز جزو ابرقدرت‌های این دسته‌بندی‌ست. این رایانه که از تخته[7]‌های "تراشه/حافظه"[8] استفاده می‌کند قابلیت به کارگیری تراشه‌های سازگار با X86 و تراشه‌های SPARC® را (به صورت همزمان!!) دارد. مطمئن هستیم که تصویر این رایانه شما را به اشتباه انداخته و اصلا نمی‌توانید حدس بزنید که این رایانه 192سانتی‌متر ارتفاع، 85سانتی‌مترعرض و 166سانتی‌متر عمق دارد. اگر این‌ها را نیز درست حدس زدید، نظرتان درباره‌ی وزن یک تنی آن چیست؟ (البته با تمام تجهیزات)

این Server قابلیت داشتن 18تخته‌ی پردازنده/حافظه هرکدام با 4پردازنده و 32گیگابایت حافظه و 17تخته‌ی اضافه‌ی 2پردازنده‌ای(مجموع 106پردازنده‌ی 1.2گیگاهرتزی[9] و نیم ترابایت حافظه)و دیسک سخت‌ای با بیش از 250ترابایت را دارد. نکته‌ی بسیار قابل توجه درباره‌ی این رایانه داشتن قابلیت "تعویض داغ" برای تمام قطعات، شامل خک‌کننده‌ها، فراهم کننده‌های توان، دیسک سخت‌ها، حافظه‌ها و حتی پردازنده‌های آن است. هر تخته‌ی پردازنده/حافظه را می‌توانید از آن جدا کنید درحالی‌که باقی تخته‌ها درحال کارند. سیستم‌عامل این رایانه (مانند اکثر محصولات شرکت SUN) سیستم‌عامل Solaris® است.

قیمت این رایانه بیشتر از PCهای معمولی است! البته بنا به مشخصاتی که انتخاب می‌کنید(به عنوان مثال تعداد تخته‌های پردازنده/حافظه) تغییر می‌کند اما اگر تمام تجهیزات و نرم‌افزارها را بخواهید باید حدود 4میلیون و 350هزار دلار هزینه کنید(این رایانه به هیچ‌وجه گران‌ترین Server این شرکت نیست[10] !).



شرکت Hewlett Packard® (یا به اختصار همان HP) نیز محصولات متعددی در این زمینه ارایه کرده، اما محصولی که هم‌اکنون قصد تشریح آن را داریم جزو این رده به حساب نمی‌آید:

رایانه‌ی HP 9000 Superdome، از رده‌ی رایانه‌های Nonstop Servers از محصولات HP است. این Server با 128 پردازنده!! و یک ترابایت حافظه بطور یقین انتخاب خوبی برای موسسات کوچک و متوسط نیست!(احتمالا هزینه‌ی مصرف برق یک دوره‌ی این رایانه از هزینه‌ِ Server ای که آن‌ها احتیاج دارند بیشتر است!!!) حافظه‌های این رایانه با سرعت 256گیگابایت در ثانیه اطلاعات را رد و بدل می‌کنند[11]. سیستم‌عامل این رایانه بر پایه‌ی سیستم عامل Unix بنا شده و به صورت اختصاصی توسط HP ارایه گردیده است.

ابعاد آن 196*152*122 سانتی‌متر است و 1196کیلوگرم وزن دارد. این رایانه در ارتفاع بالاتر از 4600متر از سطح دریا کار نمی‌کند!! (ارتفاع کاری آن 3100 گزارش شده).



با وجود تمام مسائل گفته شده، بنظر شما آیا بازهم یکی از این رایانه‌ها برای سازمانی مانند Google® کافی است؟

موسسات بزرگ علاوه بر استفاده از رایانه‌های قدرت‌مند، از سرویس‌های ویژه‌ای با عنوان Clustering برای پخش کردن وزن پردازش‌ها[12] و نیز "تحمل خطا[13]" استفاده می‌کنند.

مثلا جالب است بدانید که Google® حدود 100.000 رایانه‌ی Server در سراسر دنیا دارد.



متن کامل مقاله به همراه تصاویر را در قالب PDF دریافت فرمایید.





منابع:



The Secret Source of Google's Power_ By Skrenta at April 4, 2004 02:11 PM.

Designing SQL Server 2000 Databases for .Net Enterprise Servers_ By Robert Patton.

Why X? Making the Case for IBM eServer xSeries Servers_ ZDNet 2003_IT Business Case Series.

WWW.HP.Com

WWW.Sun.Com

WWW.IBM.Com



--------------------------------------------------------------------------------

1 به عنوان مثال فراهم کننده‌ی اینترنت(ISP) AOL® بیش از 24میلیون کاربر در ایالات متحده دارد.

2 Homail به تنهایی 60 میلیون کاربر دارد

3 Redundant Array of Independent(/Inexpensive) Disks

4 Storage

5 Hot swappable RAMs

6 "Pay as you grow" یا XPand on Demand

7 Board

8 CPU/Memory

9 هیچگاه 1.2گیگاهرتز را با 2.6گیگاهرتز رایانه‌ی منزل خود مقایسه نکنید. این تراشه‌ها از نوع SPARC™ و ساخت شرکت Texas Instruments®هستند و با تراشه‌های شرکت Intel® کاملا متفاوتند.

10 برخی از زمینه‌‌های پیشنهادی شرکت SUN® برای بهره‌گیری از این Server عبارت اند از:

Business Financial
Customer Management Solutions
Decision Support Data Warehouse
E-commerce
Enterprise Resource Planning
ISV Solutions
Software Development
Technical Applications


11 برای این‌که دید مناسبی پیدا کنید باید بگویم که یک حافظه‌ی معمولی از نوع DDR، می‌تواند اطلاعات را با سرعت کمی بیشتر از 2گیگابایت در ثانیه انتقال دهد.

12 Loud Balancing

13 Fault tolerance


-----------------------------------------------------------------------------------------------------------
البته در اینجا باید از دوست عزیز اقای علی مشاطان تشکر کنم که این مقالات را در اختیار این حقیر قرار دادند.[/img]

[Best Programmer]

البته اینم بحث هایی است که در این ضمیته در یک وبلاگ شده .البته چند تن از دوستان بنده نیز حرف های سطح پایینی زده اند چون هنوز فکر SERVER ی ندارند و در حد همین PC های معمولی فکر میکنند :سکوت:


Memory resident
A while ago I was chatting with my old boss Wade about a nifty algorithm I found for incremental search engines, which piggybacked queued writes onto reads that the front end requests were issuing anyway, to minimize excess disk head seeks. I thought it was pretty cool.

Wade smacked me on the head (gently) and asked why I was even thinking about disk anymore. Disk is dead; just put the whole thing in RAM and forget about it, he said.

Orkut is wicked fast; Friendster isn't. How do you reliably make a scalable web service wicked fast? Easy: the whole thing has to be in memory, and user requests must never wait for disk.

A disk head seek is about 9ms, and the human perceptual threshold for what seems "instant" is around 50ms. So if you have just one head seek per user request, you can support at most 5 hits/second on that server before users start to notice latency. If you have a typical filesystem with a little database on top, you may be up to 3+ seeks per hit already. Forget caching; caching helps the second user, and doesn't work on systems with a "long tail" of zillions of seldom-accessed queries, like search.

It doesn't help that a lot of the scheduling algorithms found in standard OS and database software were developed when memory was scarce, and so are stingy about their use of it.

The hugely scalable AIM service stores everything in memory across a distributed cluster, with the relational database stuck off to the side, relegated to making backups of what's live in memory. Another example is Google itself; the full index is stored in memory. Servers mmap their state when they boot; no disk is involved in user requests after everything has been paged in.


The biggest RAM database of all...

An overlooked feature that made Google really cool in the beginning was their snippets. This is the excerpt of text that shows a few sample sentences from each web page matching your search. Google's snippets show just the part of the web page that have your search terms in them; other search engines before always showed the same couple of sentences from the start of the web page, no matter what you had searched for.

Consider the insane cost to implement this simple feature. Google has to keep a copy of every web page on the Internet on their servers in order to show you the piece of the web page where your search terms hit. Everything is served from RAM, only booted from disk. And they have multiple separate search clusters at their co-locations. This means that Google is currently storing multiple copies of the entire web in RAM. My napkin is hard to read with all these zeroes on it, but that's a lot of memory. Talk about barrier to entry.

Posted by skrenta at February 2, 2004 10:48 PM | TrackBack

Comments
This also means that the snippet service will be costing Google more and more to maintain as the web grows exponentially...

Posted by: Ben at February 25, 2004 10:23 AM
The point about the perception of latency vs. disk seek time is an interesting one. But I think your maths is a little off. ISTM you could support over 100 hits per second if you take a minumum of 9ms per hit. However, more than five hits within a 50ms period will put you outside the "window", which I think is what you were getting at.

Posted by: Mark Allerton at February 25, 2004 11:58 AM
Here's what someone who deals with big databases for my employer says:

"This was the holy grail in database administration a few years ago: 'keep it all in ram!'. While the performance of such systems is astounding, the paradigm is very difficult to implement on anything besides a data mine. (Search engines are good examples of data mines.)

"The reason? Data mines aren't updated in realtime -- they use a point-in-time snapshot of their data. Because it is just a copy of the 'real' db, there is no risk of data loss if the system goes down. The drawback to data mines is that data is not being updated in realtime.

"While I'm at it...

"The other end of the database spectrum is ruled by transactional systems. Electronic banking is a classic example -- lots of data, all interdependent, and all changing in real-time. Our systems are transactional. We keep our customer's data current to the millisecond, with a deliberate focus on accuracy and security. In this regard, we kick google's bu**, because there is notihing real-time about google! ;)"

"I hope this info is useful!"

Posted by: Derek at February 27, 2004 09:29 AM
A friend of mine sent me the link to this entry and I find it pretty interesting as we are working on an abstract data schema and are in the process of doing some unscientific tests with it. What intrigues me here is that our schema doesn't really support reporting and because of that we came up with a way to support 2 databases, one for reporting (i.e. unnormalized and such) and the 'real' data. They would be in sync by using messaging, via JMS in our case, but the same thing could be applied to an in-memory database as well.

The idea would be that a single transaction for updates would be executed across the two databases thereby keeping them in sync, but the in-memory database would be used for reads and thus pretty darn quick.

Definately something for us to try out.

Posted by: Robert at March 10, 2004 06:46 AM
I've been wondering lately about something between the Google case and the Bank case.

Say you have a large database that gets updated fairly regularly but gets queried a huge amount.

It seems like a logical solution to have one machine with the database in RAM and replication to another machine that has it in disk.

In fact this seems quite obvious to me, so I'm curious - anybody have experience with it?

I'd especially like to do this with Postgres, since I can't afford a big fancy Oracle (or similar) license at the moment.

Posted by: frosty at March 10, 2004 11:05 AM
please go look up the elevator algorithm.

The number of seeks/sec that a disk can do cannot be calculated from the disk's average seek time.

The average seek time is the time you expect it to take to access to a *random* location on the disk. Now, in a web service with lots of queries, you would expect the disk accesses to be random. But think about it: if you have to go shopping at a 10-floor department store, and you need things from floors 4, 2, 8, 5, 1, and 9, do you visit the floors in that order? Hell no. You visit the floors in ascending order.

Now, let's say the elevator in the department store takes 2 minutes to get from floor 1 to floor 10. That means the average seek time of the elevator is 60 seconds - to go from a random floor to a random floor will (on average) mean you have to go 5 floors - that takes 60 seconds.

However, the speed of the elevator also implies that you can go from floor N to floor N+1 in 12 seconds. So, your visit to floors 1, 2, 4, 5, 8,
and 9 will take 12 + 24 + 12 + 36 + 12 = 96 seconds. If you were limited by the average seek time, then you'd expect to take 5*60 = 300 seconds.

Posted by: mark at April 4, 2004 10:57 PM
At 250M searches/day, with a 2X peak-to-ave ratio, we're looking at a peak rate of about 6000 searches/second. Each Google result page fetches 10 snippets; that's a peak request rate of 60,000 snippets/second.

Disk+caching could be used to serve the seldomly-fetched snippets, but they'd have to be spread over somewhere between 500-5000 drives (1ms ave. access - 10ms ave access).

Posted by: Rich Skrenta at April 4, 2004 11:18 PM
60,000 requests per second on over 100,000 machines. Hmmm. Nope, doesn't seem that difficult to me. That's an average of what .6 snippets per second per machine ... peak.

Spreadin gout to 500-5000 machines in a 100,000 machine farm does not in itself seem to be much of a problem. Segregating the data to span drives/machines would be an interesting study in real time data restructuring.

If each machine could handle 5 snippets per second, that's half a million snippets per second capacity. According to the guess above, that would mean they are handling 12% of their capacity at peak rates. Somehow, I don't think snippets are causing them much grief hardware/serving-wise.

Posted by: Bill Anderson at April 11, 2004 11:57 PM
All this sounds cool and... some frightening. Golbal Supercomputer -> Cyberpank, Corporations and Opposition in canalization...

Posted by: Jerry at April 15, 2004 03:54 AM
According to the following document, Google's snippets are retrieved from disk.

WEB SEARCH FOR A PLANET: THE GOOGLE CLUSTER ARCHITECTURE
http://www.computer.org/micro/mi2003/m2022.pdf

Posted by: Trance at April 20, 2004 03:03 PM
I feel a little out of my depth here, but Google *could* get snippets from disk quickly if they all came from multiple machines in their huge distributed cluster. Each machine would fetch the snippet in parallel.

I find this discussion fascinating, if a little bewildering.

Posted by: John Harris at April 20, 2004 04:40 PM
"Orkut is wicked fast; Friendster isn't. How do you reliably make a scalable web service wicked fast? Easy: the whole thing has to be in memory, and user requests must never wait for disk."

Orkut is running ASPX. Are you sure it uses the same Linux based mega-cluster as the rest of Google?

Posted by: Just Visitor at April 20, 2004 05:22 PM
just a thought

you don't need to cache the entire web in ram
but: you will need to cache the "best" answers to common requests in ram, because the 2383874st page for the term "internet" won't show up, err, first. it will do later
so speed is sometimes to guess the right answer in advance

Posted by: Sebastian Moericke at April 20, 2004 06:46 PM
"At 250M searches/day, with a 2X peak-to-ave ratio, we're looking at a peak rate of about 6000 searches/second. Each Google result page fetches 10 snippets; that's a peak request rate of 60,000 snippets/second.

Disk+caching could be used to serve the seldomly-fetched snippets, but they'd have to be spread over somewhere between 500-5000 drives (1ms ave. access - 10ms ave access)."

I have my Google set to display 100 results per page. It isnt fast, you have to wait for it before the whole page loads, the snippits are ovbioulsy held on disk.

Posted by: Agret at April 20, 2004 11:48 PM
Not necessarely, Google does not have to keep the WHOLE WWW in RAM...that would be silly, you need to apply some statistics to that, there's a very good chance that 60% of queries are about Sex and computers, MP3 and so on, so you would keep those queries in RAM and dynamiclly update the query list on a weekly basis (for surges in demand such as news related items) And then you would only keep the first 20 results in RAM because you KNOW that 70% of surfers never go pass the 20th result page.

For all the rest you send the request to the disk and log the number of hits in order to update the system later on...easy !

Posted by: Iknow at April 21, 2004 06:48 AM
Something interesting about Google is that the number of fetched records is never exact!

Search for something, for instance it says there are 182 records for this query (9 pages with 10 records per page), but usually when you click on the 9th page, you'll see that there are no more than 6 pages!

I think Google guesses the record count based on some algorithms, and not the real record count.

Posted by: Sina Ahmadian at April 23, 2004 01:04 AM
Wowwwwwwwwwwwwww I Love Google You Say Google is currently storing multiple copies of the entire web in RAM But If Google Server Crash How Can They Do Lost All ........ I Think they Use Scsi H.D.D