【讨论】腾讯2012笔试题你有更好的办法吗？

标签：腾讯 | 发表时间：2011-10-14 14:39 | 作者：地精工程师 Bloger

出处：http://www.cnblogs.com/

腾讯2012笔试题你有更好的办法吗。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

问题描述：例如手机朋友网有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。已有的做法是根据ServerIPIndex[QQNUM % n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[QQNUM % n]与ServerIPIndex[QQNUM %（n-1）]基本上都不一样了，所以大多数用户的请求都会转到其他服务器，这样会发生大量访问错误。

问：如何改进或者换一种方法，使得：（1）一台服务器死掉后，不会造成大面积的访问错误，（2）原有的访问基本还是停留在同一台服务器上；（3）尽量考虑负载均衡。

想了个算法，在将用户分配到服务器时，做一层映射，映射与服务器一对一对应，当服务器异常时，对应的映射表项执行顺序在其它服务器中选路，简单有效。呵呵。。。示例代码如下：

#include <iostream>
#include <time.h>

#define MAX_SERVER    200

int server_ip[MAX_SERVER]   = {0};
typedef struct 
{
    int state;    // 1-work
    int server;

    int index;    
}SI_MAP;

SI_MAP si_map[MAX_SERVER] = {0};

void init()
{
    // 初始化服务IP表
    for(int i= 0;i< MAX_SERVER;i++)
    {
    server_ip[i]        = i+1;

    si_map[i].state        = 1;
    si_map[i].server    = i;
    si_map[i].index        = 0;
    }
}

int GetServer(int index)
{
    if( si_map[index].state == 0 )
    {
    si_map[index].index = (si_map[index].index+1)%MAX_SERVER;
    if( si_map[index].index == index ) 
        si_map[index].index = (si_map[index].index+1)%MAX_SERVER;

    return si_map[index].index;
    }

    return si_map[index].server;
}

int change(char c,int old)
{
    // 恢复原有的坏服务器
    si_map[old].state = 1; 
    // 选定个坏的服务器
    int bad = rand()%MAX_SERVER;
    si_map[bad].state = 0; 

    printf("\nthe server %d is bad~!\n", bad);

    return bad;
}

void work()
{
    int n   = 0;
    int index    = 0;
    int ip    = 0;
    char c    = 0;
    int bad    = 0;
    while(c != 'e' && c != 'E')
    {
    srand(time(NULL));
    for(int i= 0;i< MAX_SERVER;i++)
    {
        n    = rand()%MAX_SERVER;
        ip    = GetServer(n);

        printf( "map:<%d,%d>", n, ip );
        if( i%4 == 0 )
        printf("\n");
        else
        printf("\t");
    }
    c=getchar();
    // 随机改变坏的服务器
    if( c == 's' || c == 'S' )
    {
        bad = change(c,bad);
        for( int j= 0;j<100;j++ )
        {
        ip  = GetServer(bad);
        printf( "map:<%d,%d>", bad, ip );
        if( j%4 == 0 )
            printf("\n");
        else
            printf("\t");
        }
    }
    }
}

void main()
{
    init();
    work();
}