آمازون یک پلتفرم تجارت الکترونیک جهانی است که در زمان های اوج به ده ها میلیون کاربر با کمک ده ها هزار سرور در دیتاسنتر هایی در سرتاسر دنیا خدمت رسانی می کند. این پلتفرم همواره در حال توسعه و رشد است بنابراین نیاز است تا همواره مقیاس پذیر باشد. همچنین این پلتفرم نیازمندی های عملیاتی سخت گیرانه ی زیادی بر روی کارایی، قابلیت اطمینان و بهره وری دارد که باید محقق شود.
این پلتفرم دارای ساختاری به شدت توزیع شده، غیر منسجم و سرویس گراست که از صد ها سرویس تشکیل شده است. در این محیط نیاز مبرمی به تکنولوژی های ذخیره سازی ای است که همواره قابل استفاده و در دسترس باشند یعنی در هر شرایطی بتوانیم از این انبار داده اطلاعات را بخوانیم و یا در آن اطلاعات را بنویسیم. مثلا مشتریان همواره باید بتوانند اقلام مختلف را مشاهده و به سبد خرید خود اضافه کنند حتی اگر دیسک ها از کار بیفتند، مسیر ها در شبکه مختل شوند و یا دیتاسنتر ها تحت هجوم طوفان باشند!
راه حل آمازون با توجه به ویژگی ها و نیازهایی که این پلتفرم دارد، از Dynamo استفاده می کند که در ادامه آن را بررسی می کنیم.
این سیستم یک پایگاه داده ی NoSQL و کلید-مقدار به شدت دردسترس است. برای دست یابی به این مقدار دردسترس بودن، Dynamo سازگاری را در بعضی سناریوهای خاص شکست، قربانی می کند. این سیستم از ترکیبی از روش های شناخته شده برای دست یابی به دسترسی پذیری و مقیاس پذیری استفاده می کند. داده با استفاده از روش هش سازگار قسمت بندی شده و کپی می شود. سازگاری داده در یک نسخه با کمک نسخه گذاری و سازگاری بین کپی های مختلف یک داده با کمک الگوریتمی بر اساس حد نصاب برقرار می شود. Dynamo برای کشف خطا و عضویت گره های جدید از پروتکلی بر اساس شایعه استفاده می کند. این سیستم کاملا توزیع شده است و خیلی کم به مدیریت دستی احتیاج دارد. مثلا گره های ذخیره سازی بدون نیاز به انجام عملیات دستی می توانند از سیستم حذف و یا به آن اضافه شوند. این سیستم هیچ مکانیزمی برای حفظ امنیت و یا درستی داده ها ندارد و در صورت نیاز این موارد باید در لایه های دیگر سیستم پیاده سازی شوند. از ویژگی های اصلی Dynamo می توان موارد زیر را نام برد:
· کاملا توزیع شده و غیر متمرکز
· به شدت دردسترس
· به شدت مقیاس پذیر
· در نهایت سازگار (در هر لحظه سازگاری را تامین نمی کند.)
· نیاز کم به مدیریت دستی
· متقارن، از این جهت که تمام گره ها در سیستم از یک جنس اند و هیچ گره ای مسئولیت اضافه یا متفاوتی ندارد.
· ناهمگون، از این جهت که گره ها در قدرت می توانند متفاوت باشند و در حقیقت توزیع کار برای هر گره باید متناسب با قدرت آن باشد. این نکته از این جهت سودمند است که برای اضافه کردن گره ی جدید با قدرت بالاتر، نیازی به بالاتر بردن قدرت گره های قبلی موجود در سیستم نداریم.
رابط این سیستم از دو عملیات put() و get() تشکیل شده است. عملیات get(key) به وسیله ی کلید، کپی های مختلف از یک شی را پیدا می کند و یک شی و یا لیستی از اشیا در صورتیکه نسخه های متناقضی داشته باشیم، همراه با context هایشان بر می گرداند.
عملیات put(key, context, object) با توجه به کلید مکان کپی ها را مشخص می کند و شی را در مکان های مشخص شده می نویسد. Context متادیتای شی است و اطلاعاتی مانند نسخه ی شی را در بر دارد.
یکی از نکات مهم در Dynamo قابلیت مقیاس پذیری افزایشی است. یعنی باید بتوانیم گره های موجود در سیستم را بدون سربار زیاد به سیستم اضافه کنیم. برای این کار لازم است داده به صورت داینامیک بر روی گره ها تقسیم شود. Dynamo از الگوریتم هش سازگار[1] برای این کار استفاده می کند. در این تکنیک هش، هش یا مکان گره ها، به تعداد کل گره ها بستگی ندارد و این ویژگی پراهمیتی در این مسئله است. در این الگوریتم فضای حلقه مانندی را در نظر می گیریم و گره ها و داده ها را روی آن می گذاریم. در حقیقت هش هر گره یا هر داده، مکان آن را بر روی این حلقه مشخص می کند. در Dynamo بر روی کلید داده ها یک هش MD5 اعمال کرده و مقدار به دست آمده مکان داده را روی حلقه مشخص می کند و مکان گره ها با انتساب عددی تصادفی به آن ها به دست می آید (شکل1).
سپس هر داده به نزدیک ترین گره در جهت عقربه های ساعت منتسب می شود. یعنی هر گره، مسئول داده هایی است که بین خود و گره ی عقبی اش قرار دارد، می شود و این داده ها در آن گره ذخیره می شوند (شکل 2)
ویژگی مهم در این تکنیک این است که حذف یا اضافه شدن یک گره فقط همسایه ی عقبی یک گره را تحت تاثیر قرار می دهد. به این صورت که اگر گره ای حذف شود، داده های آن گره، روی گره ی عقبی ذخیره می شوند و اگر گره ای اضافه شود، مقداری از داده ها گره ی عقبی (با توجه به مکان گره ی جدید) بر روی گره ی جدید ذخیره شده و از گره ی عقبی حذف می شوند.
البته این روش به همین صورتی که تا به اینجا توضیح داده شد، دچار نواقص متعددی است، مثلا انتساب مکان به گره ها به صورت تصادفی ممکن است باری نا متوازن را در حلقه ایجاد کند. همچنین ممکن است توجهی به ناهمگونی قدرت در گره ها نشود، یعنی اینگونه نباشد که به گره های قوی تر داده های بیشتری برای ذخیره بدهیم و به گره های کمتر، داده های کمتر. برای حل این مشکلات به جای آن که هر گره را به یک مکان در حلقه منتسب کنیم، هر گره را با توجه به قدرتش به مکان های بیشتری منتسب می کنیم. یعنی هر چه گره قدرت بیشتری داشته باشد، گره های مجازی بیشتری برای آن می سازیم (شکل 3)
برای دسترسی به دسترس پذیری بالا و همچنین ماندگاری در داده ها Dynamo داده ها را نه تنها در یک گره بلکه در چند گره کپی می کند تا در صورت از کار افتادن هر کدام از گره ها بتوانیم به داده ی موردنظر دسترسی داشته باشیم. هر داده در N گره ذخیره می شود که N متغیری است که برای هر سیستم متفاوت است. هر کلید داده به یک گره ی ناظر (با مکانیزمی که در بخش قبل توضیح داده شد) منتسب می شود. هر گره ی ناظر، علاوه بر ذخیره کردن داده ی مربوطه در حافظه ی محلی خودش، داده را در N-1 گره ی بعدی در جهت عقربه های ساعت هم کپی می کند. برای مثال در شکل 4، گره ی ناظر همه ی داده های بین A و B، گره ی B است و در صورتی که N=3 باشد، گره ی B هر داده را هم در حافظه ی محلی خود ذخیره می کند و هم در گره های C و D کپی می کند. به این لیست از گره ها که مسئولیت ذخیره و نگهداری داده با کلید خاصی را دارند، لیست اولویت آن کلید گفته می شود. Dynamo به گونه ای طراحی شده است که هر گره می تواند لیست اولویت هر کلیدی را تشخیص دهد. توجه کنید برای اینکه بتوانیم در صورت از کار افتادن گره ها، همچنان به همه ی داده ها دسترسی داشته باشیم، فقط گره های متمایز را (گره های مجازی که در حقیقت متعلق به یک گره ی فیزیکی هستند، نامتمایز در نظر گرفته می شود) در لیست اولویت حساب می کنیم، در نتیجه منظور از N گره، N گره ی متمایز است و تعداد واقعی این گره های ممکن است بیشتر از N باشد.
با توجه به اینکه Dynamo نهایتا-سازگار است و به روزرسانی در داده ها به صورت غیر متقارن به گره ها می رسد، ممکن است وقتی درخواستی برای دریافت داده get() می دهیم، نسخه های متفاوتی از داده دریافت کنیم چرا که ممکن است به روزرسانی قبلی به همه ی گره ها نرسیده باشد. برای اینکه Dynamo بتواند ویژگی نهایتا-سازگاری را برقرار کند، نتیجه ی هر تغییر در داده را به عنوان یک نسخه ی جدید و غیرقابل تغییر در نظر می گیرد. بنابراین ممکن است در یک سیستم در یک زمان، نسخه های متفاوتی از یک داده موجود باشد. در بسیاری از مواقع، نسخه های قبلی، زیرگروهی از نسخه ی جدید هستند و خود سیستم می تواند نسخه ی معتبر (که نسخه ی جدیدتر است) را تشخیص دهد (تلفیق ترکیبی). اما در بعضی مواقع ممکن است نسخه هایی ناسازگار از یک داده موجود باشد که سیستم نتواند نسخه ی معتبر را تشخیص دهد. در این مواقع لازم است کاربر نسخه های مختلف از داده را تلفیق کرده و شاخه های متعدد از یک داده را تبدیل به یک شاخه و یک نسخه ی واحد کند(تلفیق معنایی). Dynamo برای اینکه بتواند رابطه ی علی بین نسخه های متفاوت از یک داده را مشخص کند، از ساعت های برداری استفاده می کند. این ساعت ها بردارهایی به طول تعداد نسخه ها هستند و هر نسخه دارای یک ساعت برداری است. عنصر موجود در سطر i ام ساعت، ساعت نسخه ی i ام را نشان می دهد. در صورتی که ساعت های برداری دو نسخه نه کوچک تر و نه بزرگ تر باشد، آن دو نسخه موازی بوده و ناسازگار هستند. برای مثال استفاده از ساعت های برداری در شکل 5 نمایش داده شده است.
برای برقراری سازگاری بین کپی های مختلف از یک داده در گره های مختلف، Dynamo از پروتکلی بر اساس حد نصاب استفاده می کند. این پروتکل دارای دو پارامتر R و W است. R کمترین تعداد گره هاست که باید در یک عملیات read موفق شرکت کنند و W کمترین تعداد گره هایی است که باید در یک عملیات write موفق شرکت کنند. W و R طوری تعیین می شوند که R+W> N باشد. در این مدل، تاخیر یک عملیات get، برابر با کندترین کپی از بین R کپی است و تاخیر یک عملیات put، برابر با کندترین کپی از بین w کپی. بنابراین برای پایین آوردن تاخیر، w و R را کوچک تر از N انتخاب می کنند. در سیستمی که W=1 است، عملیات put خیلی مهم است و حتی با وجود یک گره ی سالم هم عملیات انجام می شود.
در هنگام دریافت درخواست put، گره ی ناظر ساعت برداری را برای نسخه ی جدید ساخته و نسخه ی جدید را به صورت محلی ذخیره می کند، سپس نسخه ی جدید را به اولین N گره ی سالم در لیست اولویت ارسال می کند. اگر حداقل W-1 گره پاسخ بدهند، این عملیات موفقیت آمیز است.
همچنین درمورد عملیات get، گره ی ناظر تمام نسخه های موجود کلید موردنظر را از اولین N گره ی سالم درخواست می کند، سپس منتظر R پاسخ می شود. اگر گره ی ناظر نسخه های متفاوتی دریافت کند که قابل تلفیق نباشند، همه ی آن ها را به کاربر بر می گرداند و پس از تلفیق، نسخه ی آخر در سیستم ثبت می شود.
برای شناسایی عضویت در این سیستم از الگوریتم های مبتنی بر شایعه استفاده می شود، برای مثال با اضافه شدن یا حذف شدن گره در سیستم، گره ها همسایه، که از این خبر مطلع می شوند، تغییرات را به طور تدریجی به گره های دیگر ارسال کرده و در کل شبکه منتشر می کنند، به این وسیله تمام گره ها در نهایت به دید سازگار و مشترکی از اعضای موجود در شبکه می رسند.
در صورتی که گره ی A به گره ی B پیامی ارسال کند و جوابی دریافت نکند، گره ی B را معیوب در نظر می گیرد. هر چند ممکن است گره ی B به گره های دیگر پاسخ داده باشد. سپس گره ی A از گره های جایگزین B برای انجام درخواستش استفاده می کند. گره ی A هر چند وقت یک بار گره ی B را برای دریافت جواب بررسی می کند تا وقتی که B پاسخ را برگرداند.
در Dynamo همه ی عملیات های خواندن و نوشتن بر روی اولین N گره ی سالم انجام می شود و ممکن است این N گره، لزوما اولین N گره بر روی حلقه ی هش سازگار نباشد. شکل 4 را در نظر بگیرید. اگر در این شکل گره ی A معیوب شود، کپی ای که باید در این گره ذخیره شود، در گره ی D ذخیره می شود. اما کپی ارسال شده به گره ی D در متادیتای خود اطلاعاتی دارد که نشان می دهد که این کپی قرار بوده برای گره ی A ارسال شود. گره ی D این متادیتا را در دیتابیسی محلی ذخیره کرده و هر چند وقت یک بار چک می کند تا ببیند گره ی A به کار افتاده است یا خیر. در صورتی که گره A به کار بیفتد، گره ی D داده ی مربوطه را به A ارسال کرده و متادیتای مربوطه را از دیتابیس خود پاک می کند.
با استفاده از این روش، Dynamo تضمین می کند که عملیات های خواندن و نوشتن به علت خرابی های موقتی از کار نخواهند افتاد و همچنان در دسترس خواهند بود.
در صورتی که بعضی گره ها به طور دائمی از سیستم حذف شود، لازم است بین همه ی گره ها مقایسه ای انجام شود و داده ها مورد نیاز منتقل شود تا سازگاری در سیستم حفظ شود. برای مقایسه ی گره ها از ساختمان داده ی درخت مرکل استفاده می شود. درخت مرکل یک درخت هش است که در آن هر برگ، هش یک کلید است. گره های سطح های بالاتر هم هر کدام برابر هش فرزندانشان هستند. مزیت اصلی درخت مرکل در آن است که هر شاخه بدون چک کردن کل درخت، می تواند بررسی شود. هر گره برای هر گستره ای از کلید ها که تحت نظر آن هستند، درخت مرکل جداگانه ای تشکیل می دهد. گره هایی که دارای گستره های مشترک هستند، درخت های مرکل متناظر را مقایسه کرده و در صورت مغایرت پیام هایی را برای همگام سازی به هم ارسال می کنند. ساختمان داده ی درخت مرکل موجب می شود تا مقایسه ها سریع تر انجام شود و برای همگام سازی داده های کمتری ارسال شود. برای مثال اگر مقدار هش موجود در ریشه ی دو درخت مرکل یکسان باشد، یعنی هر دو درخت یکسان هستند و نیازی به همگام سازی نیست. در غیر این صورت، یعنی بعضی کپی ها در دو گره مقدار متفاوتی دارند، در این شرایط گره ها مقدار هش فرزندان خود را مبادله می کنند تا کلید های غیرهمگام مشخص شده و همگام سازی صورت گیرد. نمونه ای از یک درخت مرکل در شکل 6 موجود است.
· https://www.toptal.com/big-data/consistent-hashing
· Dynamo: amazon's highly available key-value store
