awk的统计

a.txt

20130912 shijingbo 123
20130912 shijingbo 124
20130923 hackers365 123
20130912 hackers365 123
20130926 shijingbo 127

统计上边这些内容

1. 每天有多少人投票
cat a.txt|sort -k1|awk -F’ ‘ ‘{a[$1]++;}END{for(i in a){print $i,a[$i]}}’
2. 每天某个人投了多少票(这里要用过二维数组了)
cat a.txt|sort -k1|awk -F’ ‘ ‘{a[$1,$2]++}END{for(i in a){lens=split(i,arr,SUBSEP);print arr[1],arr[2],a[i]}}’

struct的大小

这个问题。以前在大学的时候是比较熟悉的。。近几年工作没有接触过C。导致遗忘了。。

/**
 * Structure for storing items within memcached.
 */
typedef struct _stritem {
    struct _stritem *next;      //8 bytes
    struct _stritem *prev;      //8 bytes
    struct _stritem *h_next;    //8 bytes /* hash chain next */
    rel_time_t      time;       //4 bytes /* least recent access */
    rel_time_t      exptime;    //4 /* expire time */
    int             nbytes;     //4 /* size of data */
    unsigned short  refcount;   //2
    uint8_t         nsuffix;    //1 /* length of flags-and-length string */
    uint8_t         it_flags;   //1 /* ITEM_* above */
    uint8_t         slabs_clsid;//1 /* which slab class we're in */
    uint8_t         nkey;       //1 /* key length, w/terminating null and padding */

    //42 bytes
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas;       //8
        char end;           //1
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

我在计算这个结构体大小的时候总是跟程序算的不一样。最后一个元素是空数组元素。这里不讨论。

加起来是42个字节。但程序给出的是48字节大小。。这是由于struct的大小以边界对齐导致的。但是到底是怎么个以边界对齐呢?

遵循两个原则:
1. 每个成员的偏移量必须以这个成员边界对齐
2. 结构体的大小必须在所有成员的边界上

struct {
int a;
char b;
int c;
}ha;
a的偏移量为0,b的偏移量为4,c的偏移量为5,但是5没有以c边界对齐。所以只好以0补齐,所以c的偏移量为8,大小为4,所以这个结构体的大小为12个字节也满足第二个原则

struct {
int a;
char b;
}ha;
a的偏移量为0,b的偏移量为4,满足第一个原则,结构总大小为5,不满足第二个条件,5没有以成员a的边界对齐。需要补0对齐。结构体最后的大小为8个字节

复习一下几年前的知识。。。

memcached的内存分配

朋友问到我一个问题。如果往memcached中存入100w条6字节大小的字节。。大约占用多少内存。。。于是有了下文。

memcached使用slab Alloction策略来管理内存,实现了自己的内存池。

将分配的内存分割成不同大小的chunk。把尺寸相同的chunk分成组,每个chunk集合称为slab

memcached以page为单位来分配内存,默认page的大小为1M

3d879c0f-7cff-382c-846d-cb221a866226图片来自:http://kenby.iteye.com/blog/1423989

看几个结构体:

 

/* powers-of-N allocation structures */

typedef struct {
    unsigned int size; /* sizes of items */
    unsigned int perslab; /* how many items per slab */

    void *slots; /* list of item ptrs */
    unsigned int sl_curr; /* total free items in list */

    unsigned int slabs; /* how many slabs were allocated for this class */

    void **slab_list; /* array of slab pointers */
    unsigned int list_size; /* size of prev array */

    unsigned int killing; /* index+1 of dying slab, or zero if none */
    size_t requested; /* The number of requested bytes */
} slabclass_t;

static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];

最后一句。memcached初始会分配一个MAX_NUMBER_OF_SLAB_CLASSES大小的slabclass数组。
#define POWER_LARGEST 200
#define MAX_NUMBER_OF_SLAB_CLASSES POWER_LARGEST + 1

也就是分配201个slabclass的数组。

内存的初始化是在slab.c文件中的slabs_init方法中进行的。

/**
 * Determines the chunk sizes and initializes the slab class descriptors
 * accordingly.
 */
void slabs_init(const size_t limit, const double factor, const bool prealloc) {
    int i = POWER_SMALLEST - 1;     //i初始为0
    
    //item的数据结构大小为48字节(下边会做详细解释) + 初始的chunk_sie也为48字节
    unsigned int size = sizeof(item) + settings.chunk_size;     

    mem_limit = limit;

    if (prealloc) {
        /* Allocate everything in a big chunk with malloc */
        mem_base = malloc(mem_limit);
        if (mem_base != NULL) {
            mem_current = mem_base;
            mem_avail = mem_limit;
        } else {
            fprintf(stderr, "Warning: Failed to allocate requested memory in"
                    " one large chunk.\nWill allocate in smaller chunks\n");
        }
    }

    memset(slabclass, 0, sizeof(slabclass));
    
    //POWER_LARGEST: 200
    //item_size_max: 1024 * 1024
    //factor: 1.25
    //CHUNK_ALIGN_BYTES: 8
    while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {
        /* Make sure items are always n-byte aligned */
        if (settings.verbose > 1)            fprintf(stderr, "orig size: %3d\n", size);
        if (size % CHUNK_ALIGN_BYTES)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);

        slabclass[i].size = size;
        slabclass[i].perslab = settings.item_size_max / slabclass[i].size;
        size *= factor;
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }
    }
    //上边这段代码就是用来初始化slabclass这个结构体的,确定了每个slab的大小size(以8字节边界对齐),最多不能超过POWER_LARGEST(200)或1M的大小,factor即是增长因子,以8字节为边界对齐的size,然后下一个slab大小就是这个size * factor,依然以8字节为边界对齐。填充了slabclass的perslab字段,这个字段是指每个slab能容纳的item数量

    power_largest = i;
    slabclass[power_largest].size = settings.item_size_max;
    slabclass[power_largest].perslab = 1;
    if (settings.verbose > 1) {
        fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                i, slabclass[i].size, slabclass[i].perslab);
    }

    /* for the test suite:  faking of how much we've already malloc'd */
    {
        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
        if (t_initial_malloc) {
            mem_malloced = (size_t)atol(t_initial_malloc);
        }
    }

    if (prealloc) {
        slabs_preallocate(power_largest);
    }
}

最后就是分配内存了。。。下面我们让memcached在前台且输出详细的记录来进行看看结果

slab class 1: chunk size 96 perslab 10922
slab class 2: chunk size 120 perslab 8738
slab class 3: chunk size 152 perslab 6898
slab class 4: chunk size 192 perslab 5461
slab class 5: chunk size 240 perslab 4369
slab class 6: chunk size 304 perslab 3449
slab class 7: chunk size 384 perslab 2730
slab class 8: chunk size 480 perslab 2184
………
slab class 39: chunk size 493552 perslab 2
slab class 40: chunk size 616944 perslab 1
slab class 41: chunk size 771184 perslab 1
slab class 42: chunk size 1048576 perslab 1

分配第一个slab的时候,sizeof(item) + settings.chunk_size等于96个字节。即chunk可以存储48个字节
分配第二个slab的时候, 上次的96 * 1.25(factor) = 120
分配第二个slab的时候, 上次的120 * 1.25(factor) = 150,但是这里为了保证8字段边界对齐,需要增加到152个字节
…….其他同理

在计算item数组大小的时候。走了很多弯路。明明加起来是42个字段。为啥会是48字节?
查过资料后。明白这里是c语言基础,struct结构体需要对齐到所有成员的整数倍。。请看<<struct的大小>> 来探讨这个问题.

至此,只搞清楚了,memcached的slab初始化分配方案了。。但是还没有搞清楚一个48字节的chunk可以存储多少个字符,还有文章的目的100w条6字节的到底占用多少内存。。

2014.6.8

接着讨论的“100w个6字节的数据到底占用memcached多少内存“

看item这个结构体

/**
* Structure for storing items within memcached.
*/
typedef struct _stritem {
    struct _stritem *next; //8 bytes
    struct _stritem *prev; //8 bytes
    struct _stritem *h_next; //8 bytes /* hash chain next */
    rel_time_t time; //4 bytes /* least recent access */
    rel_time_t exptime; //4 /* expire time */
    int nbytes; //4 /* size of data */
    unsigned short refcount; //2
    uint8_t nsuffix; //1 /* length of flags-and-length string */
    uint8_t it_flags; //1 /* ITEM_* above */
    uint8_t slabs_clsid;//1 /* which slab class we're in */
    uint8_t nkey; //1 /* key length, w/terminating null and padding */

    //42 bytes
    /* this odd type prevents type-punning issues when we do
    * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas; //8
        char end; //1
    } data[];
    /* if it_flags &amp; ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

注意最后的0个元素的数组,这是一个柔性数组,柔性数组在结构体的最后,然后程序就要可以根据需要重新分配结构体的大小了。

数据总是存储在item结构体之后的(因为它是一个柔性数组)

item结构体 + 数据

这里的数据要存储的东西如下:

key flags nbytes\r\n
data\r\n

即总大小为item结构体的大小加上后边的这些数据的大小了。。
item结构体的大小为48(如果开启cas,则为48 + 8 = 56,默认即是开启的),数据的大小为’key的长度’ + ‘flags的大小(2)’ + ‘用户存储的value的大小nbytes’构成,看item.c中的item_make_header函数

/**
 * Generates the variable-sized part of the header for an object.
 *
 * key     - The key
 * nkey    - The length of the key
 * flags   - key flags
 * nbytes  - Number of bytes to hold value and addition CRLF terminator
 * suffix  - Buffer for the "VALUE" line suffix (flags, size).
 * nsuffix - The length of the suffix is stored here.
 *
 * Returns the total size of the header.
 */
static size_t item_make_header(const uint8_t nkey, const int flags, const int nbytes,
                     char *suffix, uint8_t *nsuffix) {
    /* suffix is defined at 40 chars elsewhere.. */
    int total_size = 0;
    *nsuffix = (uint8_t) snprintf(suffix, 40, " %d %d\r\n", flags, nbytes - 2);
    total_size = sizeof(item) + nkey + *nsuffix + nbytes;
    if (settings.verbose) {
        fprintf(stderr, "flags: %d, nbytes:%d", flags, nbytes - 2);
        fprintf(stderr, "item_size: %ld, nkey:%d, nsuffix: %d, nbytes: %d,total_size: %d\n", sizeof(item), nkey, *nsuffix, nbytes, total_size);
    }
    return total_size;
}

其中的nsuffix是除了key+1以外的第一行的数据

假设你存了一个key为’a’,value为’hacker’的数据,则total_size计算如下:

48(item结构体) + 2(key的长度加1即算是空格) + 6(flags+nbytes+\r\n占用的空间即代码中的suffix的大小) + 8(真正数据的大小+\r\n)

总大小为64个字节. 这里没有计算cas的大小。。还需要加上8个字节。。

所以总大小为 64 + 8 = 72个字节。

至此为止我们就可以解释文章一开始提出的问题了。不过这个问题不太严密。没有算上key的大小。。

假设key的大小为6个字节,value也为6个字节, 每条数据占用77bytes

77 * 1000000 = 77000000byte = 73.43M

这个数据是理想状态下的。。在文章的开头说了。memcached以slab alloction来分配内存。默认情况下。最小的slab大小为96个字节。即使你只需要77个字节。实际也会占用96个字节。。。。

96 * 1000000 = 96000000byte = 91.55M

上边这个数据还是理想状态下的。。因为。没有计算memcached本身数据结构所占内存。。。好了。。到此为止吧。。