مدیریت حافظه در sql server
در يک پايگاه داده مبتني بر حافظه اصلي، رابطه ها در حافظه قرار مي گيرند،بنابراين،نيازي نخواهد بود که شاخص، مقادير واقي صفات را ذخيره کند، در عوض مي توان از اشاره گر هايي به tupleها استقاده نمود و با استفاده از اين اشاره گرها ، مقادير واقعي صفات را در هنگام لازم ، بازيابي نمود.
چنين روشي جندين مزيت دارد:
با استقاده از اشاره گرِ tuple،شاخص، هم به مقادير صفات آن tuple دسترسي دارد و هم به خود tuple ،بنابراين اندازه شاخص کاهش مي يابد.
اين روش ، سبب کاهش پيچيدگي در سازماندهيِ رکوردهايي با اندازه هاي زياد و متغير،و روشهاي فشرده سازي در شاخص ها مي شود.
با انجام عمليات بهنگام سازي،شاخص ها نيز بايد بهنگام شوند، در اين حالت، جابجايي اشاره گرها بسيار ارزان تر از جابحايي مقادير صقاتِ (معمولاً) طولاني تر مي باشد.
يک اشاره گر شاخص، امکان دستيابي به کليه فيلدهاي يک tuple را فراهم مي سازد،بنابراين در حالتهاي خاص نيز، نياز کمتري به شاخص هاي چندصفتي، وجود خواهد داشت.
ساختار T-Tree ، يک ساختار درختي با حفظ ترتيب مي باشد که اساساً به منظور استفاده در حافظه اصلي طراحي شده است و در ادامه به شرح آن مي پردازيم.
ساختار T-Tree
اين ساختار جديد، از ترکيب ساختارهاي AVL و B-Tree بدست آمده است: T-Tree يک درخت باينري است با چندين عنصر در هر گره.در شکل زير، ساختار يک T-Tree و يک گره از آن را – به نام T-Node- مشاهده مي کنيد. T-Treeيک درخت باينري است بنابراين خصوصيت Binary Search را از درختان AVL، به طور ذاتي به همراه دارد.همچنين، هر T-Node شامل چندين عنصر مي باشد بنابراين T-Tree ، خصوصيات مثبتِ بهنگام سازي و ذخيره سازي B-Tree را به همراه دارد.جابجايي داده ها که عموماً پس از حذف و درج لازم مي شود نيز، معمولا تنها در يک گره بايد صورت بگيرد.Rebalancing نيز با استفاده از چرخشهايي مشابه با درختهاي AVL ، انجام مي شود با اين تفاوت که با توجه به امکان جابحايي داده در داخل يک گره، تناوب انجام آن خيلي کمتر خواهد بود.
سه گونه متفاوت از T-Node ها وجود دارند:
Internal Node: (گره داخلي):T-Node ايي که دو زير درخت دارد.
Half-leaf node : T-Node ايي که يک اشاره گرِ فرزند تهي و يک اشاره گرِ فرزند غير تهي دارد.
Leaf Node :T-Node ايي که هر دو اشاره گرِ فرزند آن، تهي مي باشند.
به ازاي هر گره داخليA، يک leaf (و يا half-leaf ) متناظر با آن وجود دارد که شامل مفدار داده ايي است که ،"جد "(predecessor) ِ کمترين مقدار داده در A ، محسوب مي شود.همچنين، يک leaf (ويا half-leaf) ،شامل مفدار داده ايي که ،successor ِ بيشترين مقدار داده در A ، محسوب مي شود،نيز وجودخواهد داشت.به predecessor، بزرگترين حد پائين A و به successor کوچکترين حد بالاي A ، گفته مي شود،مطابق با شکل زير:
به ازاي هر گره N و هر مفدار X ، اگر مقدار X مابين مقاديرکمترين عنصر و بيشترين عنصردرA ، قرار بگيرد، مي گوئيم که A ، X را "مي پوشاند". توجه کنيد که داده ها در يک T-Node به صورت مرتب شده قرار مي گيرند، بنابراين،سمت چپ ترين عنصر داراي کوچکترين مقدار و سمت راست ترين عنصر ، داراي بزرگترين مقدار خواهند بود.
هر T-Tree داراي يک حدِ حداقل و يک حدِ حداکثر مي باشد که معمولا به ميزان اندکي با هم تفاوت دارند، گره هاي داخلي ظرفيتشان - يعني : تعداد مقاديرداده در هر گره - را در داخل بازه اين حدود،نگه مي دارند، بدين ترتيب در تلفيقي از عمليات حدف و درج،مقدار داده ايي که بايد به علت سربارحاصل از درج به leafها منتقل شده و يا به علت پاريز (underflow) حاصل ازحذف ،از leafها قرض گرفته شود،کاهش يافته و نتيجتاً از چرخشهاي اضافي در درخت، جلوگيري خواهد شد. داشتن چنين انعطافي در ظرفيت گره هاي داخلي، تا حدودي سبب حفظ تعادل ميان بهبود ِ ذخيره سازي و زمانِ حذف/درج خواهد شد. گره هاي leaf و half-leaf نيز،ظرفيتي متغير ميان صفرو حد ِحداکثر خواهند داشت.
1. الگوريتم جستجو
جستجو در T-Tree مانند جستجو در Binary Tree صورت مي گيرد با اين تفاوت که به جاي مقايسه با يک مقدار،مانند B-Tree، مقايسه با مقادير حداقل وحداکثرِ آن گره صورت مي گيرد.مراحل اين الگوريتم عبارتند از:
1. جستجو هميشه از ريشه درخت آغاز مي شود.
2. اگر مقدار مورد جستجو کمتر از کمترين مقدار در آن گره باشد،جستجو در زير درختي ادامه خواهد يافت که اشاره گرِ فرزند چپ، به آن اشاره مي کند.
3. در غير اين صورت، اگر مقدار مورد جستجو، بيشتر ازبزرگترين مقدار در آن گره باشد،جستجو در زير درختي ادامه خواهد يافت که اشاره گرِ فرزند راست،به آن اشاره مي کند.
4. در غير اين صورت، گره فعلي جستجو خواهد شد.
5. جستجو هنگامي نا موفق خواهد بود که گره ايي جستجو شود ولي داده مورد نظر در آن يافت نشود و يا هنگامي که گره ايي که مقدار ِمورد جستجو را بپوشاند، پيدا نشود.
2 . الگوريتم درج
عمليات درج با جستجو براي گره پوشاننده ،آغاز مي شود، مفدار جديد در اين گره درج شده و سپس درخت به منظور Rebalancing بررسي مي شود.اگر توازن درخت در اثر درج (و يا حذف)، به هم خورده باشد، پروسه Rebalancing ِ مناسب، گرههايي که در مسير ريشه تا leaf آيي که در آن حذف/ درج صورت گرفته است، را بررسي خواهد کرد. مراحل اين الگوريتم عبارتند از:
1. جستجو براي يافتن گره پوشاننده
2. اگر چنين گره ايي پيدا شد و براي اضافه کردن آيتم جديد، جا داشت، مقدار جديد به اين گره اضافه شده و الگوريتم متوقف مي شود.در غير اين صورت،کمترين عنصر از گره بر داشته شده و مقداري که بايد درج شود ، به آن اضافه شده و به عنوان کمترين عنصرقرار داده مي شود.سپس به سراغ leafي که بزرگترين حدِ پائين را براي گره در بر گيرنده عنصر درج شونده، دارا مي باشد، رفته و آن کمترين عنصر را که از گره پوشا برداشته بوديم ، به آن اضافه مي کنيم،که از اين پس به عنوان بزرگترين حد پائين براي گره پوشا، محسوب خواهد شد.
3. اگر در جستجوي درخت، چنين گره ايي پيدا نشد، مقدار درج شونده، به آخرين گره در مسير جسنجو- که يا leaf است و يا half-leaf - اضافه خواهد شد،اگر در آن جا شود که به عنوان عنصر حداقل/حداکثر جديد براي آن گره محسوب خواهد شد،در غير اين صورت،leaf جديدي ساخته و عنصر درج شونده به عنوان اولين عنصر ِ آن، به آن اضافه خواهد شد.
4. اگر leaf جديدي به درخت اضافه شود، توارن درخت بايد مورد بررسي قرار بگيرد بدين نحو که: در مسير جستجو از leaf تا ريشه، هر گره بررسي شده و اگر تفاوت عمقِ دو زير درخت آن، بيش از يک سطح بود، بايد چرخش صورت بگيرد.با انجام يک چرخش، توازن درخت تصحيح شده و عمليات متوقف مي شود.
در اينجا ذکر اين نکته ضروري است که ، هنگامي که يک گره داخلي سرريز مي کند و در نتيجه، عنصر حداقل آن برداشته شده و به يک leaf منتقل مي شود، اين درج در leaf ، منجر به جابجايي هيچ گونه داده نخواهد شد چرا که مقدار جديد به عنوان سمت راست ترين آيتم، در leaf قرار خواهد گرفت در حالي که اگر مي بايست، عنصر حداکثر برداشته شود، در leaf به عنوان سمت چپ ترين آيتم وارد شده و در نتيجه جابجايي داده در داخل گره (leaf) ، بايد صورت بگيرد.به همين دليل،با برداشتن عنصر حداقل به جاي عنصر حداکثراز گره ، از اين جابجايي جلوگيري خواهد شد.
3. الگوريتم حذف
الگوريتم حذف مشابه الگوريتم درج مي باشد، بدين ترتيب که: عنصري که بايد حذف شود، جستجو شده،عمليات انجام مي شود و در صورت نياز Rebalancing صورت مي گيرد. مراحل اين الگوريتم عبارتند از:
1. گره پو شاننده ِ مقدار حذف شونده، جستجو شده، مقداري که بايدحذف شود در داخل اين گره، جستجو شده و در صورت عدم وجود اين مقدار، اعلام خطا شده و الگوريتم متوقف مي شود.
2. اگر عمل حذف منجر به پاريز نشود( يعني: اگر گره تا پيش از حذف،بيش از کمترين مفدار مجاز،داده دارد) ، عنصري که بايد حذف شود را حذف کرده و الگوريتم متوقف مي شود.در غير اين صورت، اگر گره پوشاننده يک گره داخلي است، عنصر حذف شونده را حذف کرده و به منظور رساندن تعداد عناصر گره به حداقل مجاز، برزگترين حد پايين را براي آن از يک leaf و ياhalf-leaf ، قرض مي گيريم.در غير اين صورت( گره پوشاننده يا leaf است و يا half-leaf)،تنها عنصر حذف شونده را حذف مي کنيم( leafها مجاز به پاريز هستند ودر گام 3 ، بهhalf-leaf ها مي پردازيم)
3. اگر گره ، يک half-leafاست و ميتواند در يک leaf ، ادغام شود،دو گره را به يکي (leaf) تبديل کرده و آن يکي گره را پاک مي کنيم.ادامه در گام 5
4. اگر گره جاري(leaf)، خالي است ؛ آن را آزاد کرده و به گام 5 مي رويم به منظور Rebalancing ِ درخت.در غير اين صورت،الگوريتم متوقف مي شود.
5. در مسيرِ از leaf تا ريشه، هر گره بررسي شده و اگر تفاوت ارتقاعِ دو زير درخت آن، بيش از يک بود، بايد چرخش صورت بگيرد، از آن جايي که چرخش در يک گره، ممکن است موجب ايجاد عدم توارن در گره ايي در مکاني بالاتر در درخت شود،بررسي توازن در عمل حذف، بايد بر روي تمام گره ها در مسير جستجو صورت بگيرد، تا جايي که گره ايي با توازنِ برابر، يافت شود.
کنترل همزماني( Concurrency Control)
دسترسي به حافظه اصلي بسيار سريعتر از دسترسي به ديسک مي باشد، بنابراين مي توان انتظار داشت که در يک سيستم حافظه اصلي ، تراکنشها بسيار زودتر انجام شوند.در سيستمهايي که از روشهاي کنترل همزماني، مبتني بر lock ، بهره مي برند،اين بدين معنا مي باشد که lock ها مدت زمان زيادي نگه داشته نخواهند شد و بنابراين، تداخل در lock ها به اندازه وقتي که داده ها بر روي ديسک قرار دارند؛ اهميت نخواهد داشت.به همين دليل در سيستمهايي که از پيمانه هاي (granules)کوچک ِ داده (مانند field ها يا record ها ) به منظور کاهش تداخل استفاده مي کنند،در صورتي که داده ها در حافظه اصلي قرار گرفته باشند، فلسفه اصلي اين کار از بين رفته و پيشنهاد مي شود که در چنين حالتي از پيمانه هاي خيلي بزرگ (مانند relation ها ) استفاده شود.
در سيستمهاي locking متداول، lock ها از طريق يک hash table پياده سازي مي شوند که اطلاعات مربوط به آيتم هايي را دارا مي باشد که در حال حاضر lock شده اند و خود داده ها (بر روي ديسک) ، هيچ گونه اطلاعاتي در مورد lock را در بر ندارند.اگر داده ها در حافظه اصلي قرار گرفته باشند، مي توان با اضافه کردن چند بيت به آنها، وضيعت ِ lock شان را نيز ذخيره نمود، بدين ترتيب که : اگر اولين بيت سِت شده باشد، آن داده lock شده و در غير اين صورت، آزاد است.اگر داده، lock شده و دومين بيت نيز سِت شده است، بدين معنا مي باشد که دو يا بيشتر تراکنش ِ منتظر نيز وجود دارند.شناسه اين تراکنشهاي منتظر نيز در يک hash lock table معمولي ذخيره خواهند شد.اگر تراکنشي بخواهد که داده ايي را lock کند، ابتدا وضعيت lock bit آن را بررسي مي کند و اگر سِت نشده بود، آن را سِت کرده و فرايند locking تمام مي شود.اگر داده قبلاً lock شده بود نيز،دومين بيت را سِت کرده و خودش را به ليست تراکنشهاي منتظر در lock table اضافه مي کند.هنگامي که تراکنش اوليه lock اش را آزاد مي کند،بررسي مي کند که آيا دومين بيت سِت شده است يا خير،اگر سِت نشده بود که کار تمام است و در غير اين صورت نيز بايد روال معمول به منظور صدا زدنِ يکي از تراکنشهاي منتظر، طي شود.
Commit Processing
براي جلوگيري ازfailure هايي که ممکن است در سيستم پيش بيايند، لازم است که يک نسخه پشتيبان(backup) و يک log از فعاليتهاي تراکنشها داشته باشيم و از آن جائيکه حافظه اصلي معمولاvolatile است، اين log بايد در يک حافظه ماندگار قرار بگيرد.
پيش از آن که تراکنشي بتواند commit کند، بايد فعاليت هايش در log درج شده باشند.عمليات log کردن مي تواند بر روي " زمان پاسخ" (response time) تاثير بگذارد، زيرا هر تراکنش ،قبل از commit شدن، بايد حداقل براي يک write ِ ماندگار، منتظر بماند.همچنين در صورتي که log به bottleneck تبديل شود،عمليات log کردن ممکن است برروي کارايي نيز تاثير بگذارد.اگر چه اين مشکلات در سيستمهاي مبتني بر ديسک نيز وجود دارند، ولي در سيستمهاي حافظه اصلي ، جدي تر مي باشند زيرا که در اين حالت،log کردن تنها عمليات مبتني بر ديسکي است که يک تراکنش لازم دارد.براي حل اين مشکل، چندين راه حل پيشنهاد شده است به شرح زير:
مي توان از بخش کوچکي از حافظه ماندگار استفاده نمود به منظور نگه داري قسمتي از log .پروسه و يا پردازنده خاصي نيز مسوؤل کپي کردن داده ها از حافظه ماندگار به روي ديسکهاي log خواهد بود.اگر چه اين روش ، مشکل bottleneck شدن ِ log را برطرف نخواهد کرد ولي با حذف زمان انتظار تراکنشها براي عمليات مبتني بر ديسک ،سبب از بين رفتن مشکل " زمان پاسخ" خواهد شد.
در صورتي که حافظه ماندگار در دسترس نباشد، تراکنشها مي توانند از روش Pre-committing استفاده نمايند،بدين ترتيب که به محض آن که فعاليتهاي تراکنش در log ثبت شد، مي تواند lock هايش را آزاد کند، بدون آنکه منتظر بماند تا اين اطلاعات به ديسک منتقل شوند.
براي حل مشکل bottleneck شدن ِ log مي توان از روش Group Committing استفاده نمود، در اين روش،اطلاعات log يک تراکنش ، به محض آن که commit کرد، به ديسک log فرستاده نمي شوند،بلکه با جمع شدن تعداد زيادي از log ها (مثلاً به اندازه يک page) ،همگي با هم در يک عمل، به روي ديسک منتقل مي شوند،بدين ترتيب در هر عمليات ،چندين تراکنش commit شده و تعداد کل عمليات لازم، کاهش مي يابد.