愿星光伴随你左右


  • 首页

  • todo

  • 思考

  • life

  • food

  • OS

  • lua

  • redis

  • Golang

  • C

  • TCP/IP

  • ebpf

  • p4

  • OpenVPN

  • IPSec

  • L2TP

  • DNS

  • distributed

  • web

  • OpenWRT

  • 运维

  • Git

  • 鸟哥的私房菜

  • IT杂谈

  • 投资

  • About Me

  • 友情链接

  • FTP

  • 搜索
close

redis基础数据结构-zipmap简介

时间: 2021-08-10   |   分类: redis     |   阅读: 1265 字 ~3分钟

数据结构

--------------------------------------------------------------------------------------------------------------------------------------------------
cnt |key1.len|key1.context|val1.len|free1.len|val1.context|null1.context|key2.len|key2.context|val2.len|free2.len|val2.context|null2.context|0xFF| 
--------------------------------------------------------------------------------------------------------------------------------------------------
  • cnt:一个字节,如果<ZIPMAP_BIGLEN(254),则是key-val对的数量,否则==ZIPMAP_BIGLEN时需要循环遍历zip来确定实时的数量
  • key.len: 头字节若<ZIPMAP_BIGLEN则存储的是key的长度,否则==ZIPMAP_BIGLEN时,key的长度存在后续4个字节中
  • key.context:可包含二进制数据的的key
  • val.len:同key.len
  • free.len:固定一个字节,理论上能给val预留不超过255个byte,但实际代码中不能超过 超过ZIPMAP_VALUE_MAX_FREE(4),否则会被回收(不太明白作者为何不将此值扩大点)
  • OXFF:标志位,zip的尽头

特点

  • 给val预留了free,避免频繁的系统调用
  • len采用非固定格式,尽量的避免浪费MEM

主要接口函数

  • 构建zipmap
/* Create a new empty zipmap. */
unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);

    zm[0] = 0; /* Length */
    zm[1] = ZIPMAP_END;
    return zm;
}
  • 计算key.len和val.len的实际代表的长度
/* Decode the encoded length pointed by 'p' */
static unsigned int zipmapDecodeLength(unsigned char *p) {
    unsigned int len = *p;

    if (len < ZIPMAP_BIGLEN) return len;
    memcpy(&len,p+1,sizeof(unsigned int));
    return len;
}
  • 设置一对key.val
/* Set key to value, creating the key if it does not already exist.
 * If 'update' is not NULL, *update is set to 1 if the key was
 * already preset, otherwise to 0. */
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
    unsigned int zmlen, offset;
    unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
    unsigned int empty, vempty;
    unsigned char *p;
   
    freelen = reqlen;
    if (update) *update = 0;
    p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p == NULL) {
        /* Key not found: enlarge */
        zm = zipmapResize(zm, zmlen+reqlen);
        p = zm+zmlen-1;
        zmlen = zmlen+reqlen;	/* 新的总长 */

        /* Increase zipmap length (this is an insert) */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
    } else {
        /* Key found. Is there enough space for the new value? */
        /* Compute the total length: */
        if (update) *update = 1;	/* key已存在,则更新key对应的val */
        freelen = zipmapRawEntryLength(p);
        if (freelen < reqlen) {	/* 现存的空间不够用 */
            /* Store the offset of this key within the current zipmap, so
             * it can be resized. Then, move the tail backwards so this
             * pair fits at the current position. */
            offset = p-zm;
            zm = zipmapResize(zm, zmlen-freelen+reqlen);
            p = zm+offset;

            /* The +1 in the number of bytes to be moved is caused by the
             * end-of-zipmap byte. Note: the *original* zmlen is used. 
             * void *memmove(void *dest, const void *src, size_t n) */
            memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
            zmlen = zmlen-freelen+reqlen;
            freelen = reqlen;
        }
    }

    /* We now have a suitable block where the key/value entry can
     * be written. If there is too much free space, move the tail
     * of the zipmap a few bytes to the front and shrink the zipmap,
     * as we want zipmaps to be very space efficient. */
    empty = freelen-reqlen;
    if (empty >= ZIPMAP_VALUE_MAX_FREE) {
        /* First, move the tail <empty> bytes to the front, then resize
         * the zipmap to be <empty> bytes smaller. */
        offset = p-zm;
        memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
        zmlen -= empty;
        zm = zipmapResize(zm, zmlen);
        p = zm+offset;
        vempty = 0;
    } else {
        vempty = empty;
    }

    /* Just write the key + value and we are done. */
    /* Key: */
    p += zipmapEncodeLength(p,klen);
    memcpy(p,key,klen);
    p += klen;
    /* Value: */
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;
    memcpy(p,val,vlen);
    return zm;
}
  • 删除一对key.val
/* Remove the specified key. If 'deleted' is not NULL the pointed integer is
 * set to 0 if the key was not found, to 1 if it was found and deleted. */
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
    unsigned int zmlen, freelen;
    unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p) {
        freelen = zipmapRawEntryLength(p);
        memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));
        zm = zipmapResize(zm, zmlen-freelen);

        /* Decrease zipmap length */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;

        if (deleted) *deleted = 1;
    } else {
        if (deleted) *deleted = 0;
    }
    return zm;
}
  • 读取指定的val值
/* Search a key and retrieve the pointer and len of the associated value.
 * If the key is found the function returns 1, otherwise 0. */
int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {
    unsigned char *p;

    if ((p = zipmapLookupRaw(zm,key,klen,NULL)) == NULL) return 0;
    p += zipmapRawKeyLength(p);
    *vlen = zipmapDecodeLength(p);
    *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1;
    return 1;
}
  • 迭代遍历zipmap
/* Call it before to iterate trought elements via zipmapNext() */
unsigned char *zipmapRewind(unsigned char *zm) {
    return zm+1;
}

/* This function is used to iterate through all the zipmap elements.
 * In the first call the first argument is the pointer to the zipmap + 1.
 * In the next calls what zipmapNext returns is used as first argument.
 * Example:
 *
 * unsigned char *i = zipmapRewind(my_zipmap);
 * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
 *     printf("%d bytes key at $p\n", klen, key);
 *     printf("%d bytes value at $p\n", vlen, value);
 * }
 */
unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) {
    if (zm[0] == ZIPMAP_END) return NULL;
    if (key) {
        *key = zm;
        *klen = zipmapDecodeLength(zm);
        *key += ZIPMAP_LEN_BYTES(*klen);
    }
    zm += zipmapRawKeyLength(zm);
    if (value) {
        *value = zm+1;	/* +1是free.len.head格式占用的一个字节空间 */
        *vlen = zipmapDecodeLength(zm);
        *value += ZIPMAP_LEN_BYTES(*vlen);
    }
    zm += zipmapRawValueLength(zm);
    return zm;
}

Golang知识小结

时间: 2021-08-10   |   分类: go     |   阅读: 706 字 ~2分钟

string

  • string类型采用UTF-8编码,且不可修的,len返回byte数量而不是字符数量,eg(len(你好)==6

数组和slice

  • 数组在函数调用的参数传递模式是独立复制一份数据给被调用函数
  • slice以及map,chan对应的的函数传参知识参考这里Golang函数参数传递

map

  • 初始化: h := map[int]string{} 显示构造,或者 h = make(map[int]string),
  • 空值 h := map[int]string 将构造一个nil的map,可以调用range, len, 读,但不能写值
  • map是指针数据结构,即当作函数参数传递时,函数内部修改了其值,会影响函数外部原始的map
  • var = map[k],若对应的k不存在,则返回零值,故而要判断时候存在,需引入第二个参数eg: val, exist := map[k]
  • 不可对map中的元素取地址eg:&tbl[k]是非法的(map的大小可能随时调整故取地址无意义)。
  • 可以采用range风格对其轮询,顺序是随机的(设计如此)。如果需要按照一定的规则读取map,一个办法是先把key排好序,再用map[key]的的方法读写

struct

  • 导出规则与模块一样
  • 一般而言一行定义一个成员
  • 不能递归定义自己,但可以在内部使用自己类型的指针
  • 其零值是每个成员的零值,如果内部有(map,chan),还需要在struct{}构造后,显式的对其初始化
type  sh struct {
	m map[int]int
}
var st = sh{}
st.m = make(map[int]int)

function

  • 参数是传值模式,没有默认值,数量可以是可变模式
  • 可以递归调用自己
  • 函数名是第一类值,可以和nil比较,但不能作为map的key
  • 支持闭包(closures),这点和lua中的函数一致,与之对应,C语言不支持闭包

方法

变量类型

  • 七个小矮人(slice,map,func,channel,pointer, string, interface),自带魔法绳(指针), 所以没必要将它定义成引用类型

redis基础数据结构-dict简介

时间: 2021-08-09   |   分类: cs   redis     |   阅读: 522 字 ~2分钟

数据结构

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

typedef struct dictIterator {
    dict *d;
    int table;
    int index;
    dictEntry *entry, *nextEntry;
} dictIterator;

特点

  • 2个ht,用于循环渐进式的rehash,避免ht过大的情况下一次性rehash而卡住程序
  • 底层实现为哈希桶
  • fingerprint:指纹值方法用于粗略判断两个时间戳之间ht是否有被修改
  • rehash的条件考虑到了存档RDB时的linux操作系统的写时复制策略

主要接口实现

  • 插入节点
/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    int index;
    dictEntry *entry;
    dictht *ht;

	/* 执行一次rehash */
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key)) == -1)
        return DICT_ERR;

    /* Allocates the memory and stores key
	 * 正在rehash则存入ht[0]
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = _dictAlloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetHashKey(d, entry, key);
    dictSetHashVal(d, entry, val);
    return DICT_OK;
}
  • rehash
int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        if (d->ht[0].used == 0) {
            _dictFree(d->ht[0].table);
            d->ht[0] = d->ht[1];
            _dictReset(&d->ht[1]);
            d->rehashidx = -1;
            return 0;
        }

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 
         * 因为上面used的判断,这里可以确定不会溢出 */
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
		
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
		
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    return 1;
}

redis基础数据结构-list简介

时间: 2021-08-06   |   分类: redis     |   阅读: 342 字 ~1分钟

数据结构

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned int len;
} list;

特点

  • 可以转载任何类型的数据
  • 可以定制dup,free,match方法,自由度大
  • 可以从头、尾分别插入链表
  • 提供迭代器,方便遍历整个链表

重要接口实现

  • 构建/释放list
list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

void listRelease(list *list)
{
    unsigned int len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value);
        zfree(current);
        current = next;
    }
    zfree(list);
}
  • 遍历和复制list
listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;
    
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next;
        else
            iter->next = current->prev;
    }
    return current;
}

list *listDup(list *orig)
{
    list *copy;
    listIter *iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
        return NULL;
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        void *value;

        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                listReleaseIterator(iter);
                return NULL;
            }
        } else
            value = node->value;
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            listReleaseIterator(iter);
            return NULL;
        }
    }
    listReleaseIterator(iter);
    return copy;
}

redis基础数据结构-sds简介

时间: 2021-08-06   |   分类: redis     |   阅读: 571 字 ~2分钟

数据结构

/* context 	= "hello"
 * len 		= 5 不包含redis自动添加的'\0'
 * free 	= 0 预分配和惰性释放
 * buf[5]	= '\0' 自动添加一个'\0'在末尾,'\0'对外透明  */
struct sdshdr {
    long len;
    long free;
    char buf[];
};

特点

  • 空间预分配和惰性释放
    • 避免频繁的系统调用造成的CPU耗时
    • 减少内存碎片
  • 二进制安全和兼容部分C的string函数
    • 尾部自动添加’\0’,以及len字段 实现了装载二进制数据的能力和兼容部分C的string函数
    • 明确的len和free避免了缓冲区的溢出
  • 降低获取len的复杂度
    • 相比C原始风格的字符串风格,sds可以直接读取len字段来获得len,从而将复杂度从0(n)优化为0(1)

重要接口实现

  • 构建指定长度的sds
sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    sh = zmalloc(sizeof(struct sdshdr)+initlen+0+1);	// initlen:len 0:free 1:'\0'
    if (sh == NULL) sdsOomAbort();
    sh->len = initlen;
    sh->free = 0;
    if (initlen) {
        if (init) memcpy(sh->buf, init, initlen);
        else memset(sh->buf,0,initlen);	// 空指针则填充'\0'
    }
    sh->buf[initlen] = '\0';		// 添加哨兵'\0'
    return (char*)sh->buf;		// NOTE: 这里返回的是buf
}
- 初始化时没有预分配MEM,因为一般而言sds是只读的,未修改则先不预分配空间
  • 修改sds的长度
static sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s);
    size_t len, newlen;

    if (free >= addlen) return s;
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen)*2;	// 直接预分配一倍
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) sdsOomAbort();
    newsh->free = newlen - len;
    return newsh->buf;
}
- 这里可以看到作者的思路,既然此sds被修改,那么很有可能再次修改,所以为了频繁系统调用,这里预分配一部分内存

redis源码阅读计划

时间: 2021-08-06   |   分类: redis     |   阅读: 155 字 ~1分钟

整体思路

        鉴于在DB和分布式方面没有啥知识储备,以及空闲时间的不确定,整体思路:从简到繁,从基础到单机再到分布式

内容计划

  • 阅读0.0.1版本,了解大致的数据结构,事件系统,网络模块等主模块的逻辑(已完成)

阅读全文 »

Go学习建议

时间: 2021-08-04   |   分类: go     |   阅读: 759 字 ~2分钟

如果学习 Go

整理了目前市面上的各类图书,特别是开源的图书,阅读学习建议分享给你

入门建议

Go 语言入门图书挺多的,根据我的了解和大家的反馈、讨论,比较推荐如下图书,选择一本认真看即可,没必要那么多。

阅读全文 »

彻底弄懂TCP协议:从三次握手说起

时间: 2021-07-30   |   分类: cs   tcpip     |   阅读: 19976 字 ~40分钟

作者:morganhuang,腾讯 IEG 后台开发工程师

说到 TCP 协议,相信大家都比较熟悉了,对于 TCP 协议总能说个一二三来,但是 TCP 协议又是一个非常复杂的协议,其中有不少细节点让人头疼点。本文就是来说说这些头疼点的,浅谈一些 TCP 的疑难杂症。那么从哪说起呢?当然是从三次握手和四次挥手说起啦,可能大家都知道 TCP 是三次交互完成连接的建立,四次交互来断开一个连接,那为什么是三次握手和四次挥手呢?反过来不行吗?

阅读全文 »
54 55 56 57 58 59 60 61 62

日志
分类
标签
RSS 订阅
GitHub
© 2009 - 2025
粤ICP备2021068940号-1 粤公网安备44011302003059
0%