English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
ملاحظات خبرة
النص الأساسي
مقدمة
أولاً، من الناحية العامة، ننظر إلى هيكل ziplist، كما في الشكل التالي:
شكل ziplist
من الواضح أن هناك العديد من الحقول، وأن حجم الأbytes يختلف أيضًا، ولكن هذا هو روح ziplist المضغوط، وسنقوم بالتجميع بشكل متتابع.
| الحقل | المعنى |
|---|---|
| zlbytes | هذا الحقل هو أول حقل في قائمة الحلقات المضغوطة، وهو عدد صحيح غير سالب، يستخدم أربعة bytes. يستخدم لتمثيل عدد الأbytes التي يستخدمها القائمة الحلقات المضغوطة بأكملها (بما في ذلك نفسها). |
| zltail | عدد صحيح غير سالب، يستخدم أربعة أbytes. يستخدم لتحديد النسبة المئوية من القائمة الحلقات المضغوطة إلى آخر entry (ليس عنصر zlend) في سيناريوهات التحرك بسرعة إلى نهاية القائمة. |
| zllen | عدد صحيح غير سالب، يستخدم بايتين. يستخدم لتحديد عدد entryات القائمة الحلقات المضغوطة. |
| zlend | entry خاص يستخدم لتمثيل نهاية قائمة الحلقات المضغوطة. يستخدم بايت واحد، ويكون القيمة دائمًا 255. |
التفسير كرأس وذيل ziplist، سنتطرق أيضًا إلى أهمية الحقل entry.
عادةً، يتكون entry من ثلاثة حقول هي prevlen،encoding وentry-data، ولكن عندما يكون entry عدد صغيرًا جدًا، يتم تجاهل حقل entry-data بناءً على الترميز. سنتطرق إلى التلخيص بشكل متتابع:
首先是字段prevlen：表示前一个entry的长度，有两种编码方式。
然后是字段encoding：它会根据当前元素内容的不同会采用不同的编码方式，如下：
1、如果元素内容为字符串，encoding的值分别为：
00xx xxxx ：00开头表示该字符串的长度用6个bit表示。
01xx xxxx | xxxx xxxx ：01开头表示字符串的长度由14bit表示，这14个bit采用大端存储。
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10开头表示后续的四个字节为字符串长度，这32个bit采用大端存储。
2、如果元素内容为数字，encoding的值分别为：
1100 0000：表示数字占用后面2个字节。
1101 0000：表示数字占用后面4个字节。
1110 0000：表示数字占用后面8个字节。
1111 0000 ：表示数字占用后面3个字节。
1111 1110 ：表示数字占用后面1个字节。
1111 1111 ：表示压缩链表中最后一个元素（特殊编码）。
1111 xxxx ：表示只用后4位表示0~12的整数，由于0000，1110跟1111三种已经被占用，也就是说这里的xxxx四位只能表示0001~1101，转换成十进制就是数字1~13，但是redis规定它用来表示0~12，因此当遇到这个编码时，我们需要取出后四位然后减1来得到正确的值。
最后是字段entry-data：如果元素的值为字符串，则保存元素本身的值。如果元素的值为很小的数字（按上面编码规则即0~12），则没有该字段。
压缩链表的编码非常复杂，但这也正是该数据结构的精髓所在，一起来看一个例子吧：
注：这个例子是redis源码中提到的
//由元素2，5组成的压缩链表 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end // محتوى الترميز بعد ترميز النص "Hello World" [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
الآن هذا هو جزء من قائمة التكوين المضغوطة المكونة من عناصر 2 و 5 متمثلة باستخدام شق.
الآن سنقوم بإدراج عنصر نصي Hello World في نهاية قائمة التكوين المضغوطة، دعونا أولاً نرى كيف يمكن ترميز هذا النص، وفقًا للقواعد المسبقة للترميز، يجب أولاً استخدام البايتات لتمثيل طول العنصر السابق، حيث يكون العنصر السابق هو 5، ويستخدم ذلك مجموعًا اثنين من البايتات، لذا يتم استخدام بايت واحد لتمثيل طول العنصر السابق 02، ثم يتبعه ترميز النص، يجب علينا إضافة طول النص الذي نريد إضافته 11 (الفراغ أيضًا يُعتبر نصًا)، وتحويله إلى ثنائي هو 1011، وفقًا للقواعد لترميز النص، يتم استخدام 0000 1011 لتمثيله، وتحويله إلى شق هو 0b، ثم يتم إضافة ASCII للنص نفسه، وبهذا يتم الحصول على ترميز النص: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64].
في هذه اللحظة، قائمة التكوين المضغوطة تصبح:
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 48 65 6c 6c 6f 20 57 6f 72 6c 64] [ff] | | | | | | | zlbytes zltail entries "2" "5" "Hello World" end
ثانيًا، تحليل مصدر أوامر قائمة المضغوطة ziplist
بعد فهم قواعد الترميز المذكورة أعلاه، نرى أداء العمليات في جزء القائمة المضغوطة ziplist، حيث نلخص مبادئ القائمة المضغوطة من خلال عمليات إنشاء القائمة المضغوطة، إدراج العنصر، حذف العنصر، البحث عن العنصر أربعة عمليات.
أولاً، إنشاء:
// تعريف حجم رأس القائمة المضغوطة الذي يتكون من zlbytes،zltail،zllen
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
// إنشاء قائمة مضغوطة وإرجاع إشارة إلى هذه القائمة
unsigned char *ziplistNew(void) {
// لماذا +1 هو أن العنصر النهائي يستخدم بايتًا واحدًا، وهو أيضًا أقل حجم للقائمة المضغوطة
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
// تخصيص ذاكرة
unsigned char *zl = zmalloc(bytes);
// إعداد حجم القائمة
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
// إعداد إزاحة العنصر الأخير
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
// إعداد عدد العناصر
ZIPLIST_LENGTH(zl) = 0;
// إعداد العنصر النهائي (في الأعلى فقط تم طلب المساحة)
zl[bytes-1] = ZIP_END;
return zl;
}
بسيطة جدًا هي لógica إنشاء القائمة المضغوطة، وهي طلب مساحة ثابتة تحتوي على العناصر الرباعية والخلفية، ثم بدء تسيير سياق القائمة.
على عكس إنشاء، يتمدد رمز إدراج العنصر بشكل كبير، من أجل الفهم البسيط، نحن نرتب منطق إدراج العنصر قبل النظر في الرمز.
الخطوات الثلاثة الأولى هي الخطوات الأساسية، بالإضافة إلى ذلك هناك عمليات مثل تحديث تعديل إزاحة النهاية، تعديل عدد عناصر القائمة وغيرها. بالطبع، نظرًا لأن القائمة المضغوطة تستند إلى تنفيذ الأعدادات، فإن نسخ ذاكرة الذاكرة عند إدراج أو حذف العناصر ضروري أيضًا.
النتيجة بعد جمع الخطوات المذكورة أعلاه، نبدأ بتحليل الشيفرة المصدرية خطوة بخطوة، الطول كبير، نرى ببطء:
//四个参数依次是：压缩链表，插入位置（新元素插入p元素后面），元素值，元素长度
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//这里是保存当前链表的长度
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int التغييرالتالي = 0;
unsigned char encoding = 0;
long long value = 123456789;
zlentry tail;
//1. 这段逻辑目的就是获取前置元素的长度
إذا (p[0] != ZIP_END) {
//如果插入位置的元素不是尾元素,则获取该元素的长度
//这里为了后面使用方便进行了拆分，prevlensize保存encoding字段的长度，prevlen保存元素本身的长度
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//如果插入位置的元素是尾元素，那么需要把新元素插入链表尾端
//获取到链表最后一个元素（注：最后一个元素不等于尾元素）
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
//如果最后一个元素不是尾元素，则该元素为新元素的前置元素，获取该元素长度
prevlen = zipRawEntryLength(ptail);
}
//否则说明链表还没有任何元素，即新元素的前置元素长度为0
}
//2. 对新元素进行编码，获取新元素的总大小
if (zipTryEncoding(s,slen,&value,&encoding)) {
//如果是数字，则按数字进行编码
reqlen = zipIntSize(encoding);
} else {
//元素长度即为字符串长度
reqlen = slen;
}
//طول العنصر الجديد الإجمالي هو طول القيمة بالإضافة إلى طول العنصر المسبق وlength العنصر الت编码
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//إذا لم يكن موقع الإدراج ليس في نهاية القائمة، يجب التحقق من حقل prevlen للعناصر المتتابعة الجديدة
//حسب قواعد الت编码 المذكورة أعلاه، قد تحتاج هذه الحقل إلى توسيع
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
//توسيع الحجم بناءً على حجم المصفوفة الجديد المحسوب، نظرًا لأن عنوان المصفوفة الجديد قد يتغير، لذا يتم تسجيل التأثير القديم هنا
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//حساب موقع الإدراج في المصفوفة الجديدة
p = zl+offset;
//إذا لم يكن العنصر المدرج الجديد في نهاية القائمة
إذا (p[0] != ZIP_END) {
//نسخ العنصر المتوالي الجديد إلى مصفوفة جديدة،-1 هو العنصر الأخير
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//حقل prevlen للعنصر المتوالي الجديد
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//تحديث تأثير آخر العنصر
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//عندما يكون متوالي العنصر الجديد ليس له متواليات فقط، يجب إضافة nextdiff إلى تأثير نهاية العنصر الجديد
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
//جديد العنصر يتم إدراجه في نهاية القائمة، وتحديث تأثير نهاية القائمة
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//إذا كان التغييرالتالي != 0، فإن هذا يعني أن طول العناصر التالية قد تغير، لذا يجب تحديث العناصر التالية بشكل متتابع
إذا (التغييرالتالي != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
//كتابة العنصر الجديد في القائمة
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
//زيادة عدد العناصر المخزنة في قائمة التسلسل المضغوطة بـ1
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
بعد تحليل منطق إضافة العناصر، استنشق الهواء بعمق، إنه طويل جدًا، والتفاصيل كثيرة.
الآن، بعد النظر في عملية حذف العناصر، وهي بسيطة نسبيًا مقارنة بإضافة العناصر، بعد إفراغ العنصر الحالي، يجب نسخ العناصر التالية واحدة تلو الأخرى (وهذا هو الفرق بين هيكل البيانات المصفوفة والقائمة)
//المتغيرات المقدمة بالترتيب هي: قائمة التسلسل المضغوطة، موقع البداية للعنصر الذي سيتم حذفه، عدد العناصر التي سيتم حذفها
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
unsigned int i, totlen, deleted = 0;
size_t offset;
int التغييرالتالي = 0;
zlentry first, tail;
//قراءة العنصر الذي يشير إليه p وتخزينه في first
zipEntry(p, &first);
لـ (i = 0; p[0] != ZIP_END && i < num; i++) {
//إحصاء الطول الإجمالي للإزالات
p += zipRawEntryLength(p);
//إحصاء عدد العناصر التي تم حذفها فعليًا
deleted++;
}
//عدد البايتات التي يجب حذفها
totlen = p-first.p;
إذا (totlen > 0) {
إذا (p[0] != ZIP_END) {
//تحقق من ما إذا كان حجم العنصر قد تغير
التغييرالتالي = zipPrevLenByteDiff(p,first.prevrawlen);
//修改删除元素之后的元素的prevlen字段
p -= nextdiff;
zipStorePrevEntryLength(p,first.prevrawlen);
//更新末尾元素的偏移量
ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//当删除元素的后继元素不止有一个时，新的末尾元素偏移量需要加上nextdiff
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//把后面剩余的元素移动至前面
memmove(first.p,p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
} else {
//直接删除到链表末尾，因此不需要内存拷贝，只需修改最后一个元素的偏移量
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//resize数组大小
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//修改链表元素个数
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0表示元素大小发生变化，需要进行级联更新
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl,p);
}
return zl;
}
最后我们看下元素的查找操作：
//参数依次为：compressed list，要查找元素的值，要查找元素的长度，每次比较之间跳过的元素个数
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
int skipcnt = 0;
unsigned char vencoding = 0;
long long vll = 0;
//只要还没到尾元素就不断循环
while (p[0] != ZIP_END) {
unsigned int prevlensize, encoding, lensize, len;
unsigned char *q;
//查询链表当前元素的prevlen字段
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//查询链表当前元素的encoding字段
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
//已到达需要比较的元素位置
if (skipcnt == 0) {
//如果链表中的当前元素时字符串
if (ZIP_IS_STR(encoding)) {
//跟要查找的字符串进行比较
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
//匹配成功，则要查找元素的指针
عدد p;
}
} else {
//如果当前元素为数字且vencoding为0
if (vencoding == 0) {
//尝试对要查找的值进行数字编码
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
//如果编码失败，则说明要查找的元素根本不是数字
//然后把vencoding设置为最大值，起一个标记作用
//也就是说后面就不用尝试把要查找的值编码成数字了
vencoding = UCHAR_MAX;
}
assert(vencoding);
}
//如果vencoding != UCHAR_MAX，则说明要查找的元素成功编码为数字
if (vencoding != UCHAR_MAX) {
//按数字取出当前链表中的元素
long long ll = zipLoadInteger(q, encoding);
إذا كان ll == vll {
//إذا كانت الرقمين متساويين، فعدد العنصر
عدد p;
}
}
}
//إعادة تعيين عدد العناصر التي يجب تخطيها
skipcnt = skip;
} else {
//تخطي العنصر
skipcnt--;
}
//مرور إلى العنصر التالي
p = q + len;
}
//مرور كامل على السلسلة، لم يتم العثور على العنصر
عدد NULL;
}
إلى هنا، تم تلخيص مبادئ إنشاء، إضافة، حذف، البحث في الأربعة عمليات الأساسية لـ ziplist المضغوط.
ثالثًا، تلخيص هيكل البيانات المضغوط ziplist
استخدام ziplist المضغوط في redis واسع جدًا، يعتبر هذا هيكل البيانات الأكثر تميزًا في redis. روح هذا الهيكل في الواقع هو قواعد الترميز المذكورة في الجزء الأول من التلخيص، بعد فهم هذا الجزء، يمكنك بسهولة مراجعة المصدر لزيادة فهمك.
لا يمكن说不 جزء المصدر طويل جدًا، بالفعل يتطلب صبرًا، وقد كان لدي مشاكل كبيرة أثناء قراءتي. إذا كنت مهتمًا بالمصدر، فأوصي بكتابة طريقتي، أولاً قم بتبسيط عملية معينة (مثل العناصر المضافة المذكورة أعلاه) ما يجب القيام به، ثم راقب الكود قد يكون أفضل لفهمه.
في النهاية، دعني أترك سؤالًا صغيرًا، إذا كان ziplist في redis يستخدم كفاءة في الذاكرة إلى هذا الحد، لماذا يزال يقدم بنية البيانات العادية للعديد من المستخدمين؟
لا يوجد إجابة معيارية لهذا السؤال، إنه يعتمد على رأي كل شخص، فمن يرى الإنسانية يرى، ومن يرى الحكمة يرى.
الخلاصة
هذا هو نهاية محتوى هذا المقال، نأمل أن يكون محتوى هذا المقال له قيمة مرجعية تعليمية أو مهنية، إذا كان لديك أي أسئلة، يمكنك ترك تعليق للتفاعل، شكرًا لدعمك لتعليمات النفخ.
بيان: محتوى هذا المقال تم جمعه من الإنترنت، ملكية حقوق النشر لصاحبها، تم جمع المحتوى من قبل المستخدمين عبر الإنترنت الذين قدموه بذاتهم، ويحمل هذا الموقع حقوق الملكية، لم يتم تعديل المحتوى بشكل يدوي، ولا يتحمل هذا الموقع أي مسؤولية قانونية تتعلق بذلك. إذا كنت قد وجدت محتوى يشتبه في انتهاك حقوق النسخ، فيرجى إرسال بريد إلكتروني إلى: notice#oldtoolbag.com (عند إرسال البريد الإلكتروني، يرجى استبدال '#' ب '@') للإبلاغ، وتقديم الدليل، وإذا تم التحقق من ذلك، فإن هذا الموقع سيرفع المحتوى المزعوم فورًا.