skynet任务调度分析 -

spartan1

浏览: 365877 次
性别:
来自: 深圳

最近访客更多访客>>

青岚-雪时晴

huaiao_chen

晓岚莲花

wangyi03

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

skynet任务调度分析

博客分类：

并发
lua
skynet

云风同学开源的skynet，当前规模是8K+ C代码和2K+ lua代码，实现了一个多线程高并发的在线游戏后台服务框架，提供定时器、并发调度、服务扩展框架、异步消息队列、命名服务等基础能力，支持lua脚本。单服务器支持10K+客户端接入和处理。

我个人比较关注高性能和并发调度这块，这两天分析了一下skynet的代码，简单总结一下。

1. 总体架构

一图胜千言，去掉监控、服务扩展、定时器等功能，skynet服务处理的简化框架如下图所示：

每个在线客户的客户端，在skynet server上都对应有一个socket与其连接。一个socket在skynet内部对应一个lua虚拟机和一个”客户特定消息队列“(per client mq)。当客户特定消息队列中有消息时，该队列就会挂载到全局队列（global message queue）上，供工作线程（worker threads）进行调度处理。

skynet的服务处理主流程比较简单：一个socket线程轮询所有的socket，收到客户端请求后将请求打包成一个消息，发送到该socket对应的客户特定消息队列中，然后将该消息队列挂到全局队列队尾；N个工作线程从全局队列头部获取client特定的消息队列，从客户特定消息队列中取出一个消息进行处理，处理完后将该消息队列重新挂到全局队列队尾。

实际代码要更复杂一些：定时器线程会周期性检查一下设置的定时器，将到期的定时器消息发送到client消息队列中；每个lua vm在运行过程中也会向其他lua vm（或自己）的客户特定消息队列发送消息；monitor线程监控各个客户端状态，看是否有死循环的消息等等。本文重点关注消息的调度，因为消息调度的任何细微调整都可能对服务端性能产生很大影响。

另外可以看出，每个客户处理消息时，都是按照消息到达的顺序进行处理。同一时刻，一个客户的消息只会被一个工作线程调度，因此客户处理逻辑无需考虑多线程并发，基本不需要加锁。

2. 并发任务调度方式

lua支持non-preemptive的coroutine，一个lua虚拟机中可以支持海量并发的协作任务，coroutine主要的问题是不支持多核，无法充分利用当前服务器普遍提供的多核能力。所以目前有很多项目为lua添加OS thread支持，比如Lua Lanes，LuaProc等，这些项目都要解决的一个问题就是并发任务的组成以及调度问题。

并发任务可以使用coroutine表示：每个OS线程上创建一个lua虚拟机(lua_State)，虚拟机上可以创建海量的coroutine，这种调度如下图所示：

这种OS线程与lua vm 1:1的调度方式有很多优点：

每个OS线程都有私有的消息队列，该队列有多个写入者，但只有一个读取者，可以实现读端免锁设计。
OS线程可以与lua vm绑定，也可以不绑定。由于现代OS都会尽量将CPU core和OS线程绑定，所以如果OS线程与lua vm绑定的话，可以大大减少cpu cache的刷新，提高cache命中率
lua vm与OS线程个数相当，与任务数无关。大量任务可以共用同一个lua vm，共享其lua bytecode，字符串常量等信息，极大减少每个任务的内存占用。

但该方式也有比较严重的缺陷：

不支持任务跨lua vm迁移。每个任务是一个coroutine，而coroutine是lua vm内部的数据结构，执行中其stack引用了lua vm内部的大量共享数据，无法迁移到另一个lua vm上执行。当一个lua vm上的多个任务都比较繁忙时，只能由一个OS线程串行执行，无法通过work stealing等方式交给其他OS线程并行处理。我以前参与的一个电信项目中就是这种业务和线程绑定的处理方式，对于业务逻辑比较固定的电信业务，各个客户请求的处理工作量类似，因为绑定后CPU使用比较均衡。由于cache locality比较好的原因，这种处理方式性能极高。但对于一些工作量不固定甚至经常变动的客户请求，这种方式很容易造成某些线程很忙，另外一些线程很闲，无法有效利用多核能力。
在同一个lua vm内的多个任务，共享lua vm的内存空间。一个任务出现问题时，很容易影响到其他任务。简单说就是任务间的隔离性不好。

另一种处理方式是每个lua vm表示一个任务，系统中的海量并发任务由海量lua vm处理。skynet就是采用的这种方式。这种方式有效解决了上一种处理方式的两个缺陷，每个任务完全独立，可以交给任意一个OS线程处理；同时任务不会共享lua vm内存空间，隔离性非常好，一个任务的问题不会影响其他任务的执行。这种方式的主要问题就是存在大量内存浪费。每个lua vm都要加载大量相同的lua字节码和常量，对内存需求量非常高。这也造成每个任务执行时无法重用cpu cache，导致cache命中率降低很多。云风对这一问题的解决方案是修改lua vm的代码加载机制，同一进程内部的多个lua vm共享字节码。具体实现上，有一个独立的lua vm专门负责加载字节码，并负责字节码的垃圾回收。同一进程中的其他lua vm共享该独立lua vm加载的字节码。这种方式无法解决字符串常量共享的问题，仅仅解决了字节码共享的问题。不过即使这样，每个在线用户也节省了1M的内存。

3. 全局消息队列

skynet中有一个”全局消息队列“和在线用户特定的”任务特定消息队列“。与go语言1.1版本之前runtime对goroutine的调度类似，所有工作线程使用了一个公共的全局队列。skynet全局队列是一个循环队列，使用数组实现。使用全局队列不是一种很高效的消息调度方式，每个消息的出队入队一般都需要加全局锁。go1.1中，优化了调度器算法，每个线程使用局部队列，性能提高很多（据称有些应用性能提升近40%）。

skynet全局队列有多个并发生产者和并发消费者，通常情况下访问该全局队列时是需要加锁的。但skynet居然采用了一种wait-free的队列实现方式，看如下代码：

消息入队列：

static void
skynet_globalmq_push(struct message_queue * queue) {
    struct global_queue *q= Q;

    uint32_t tail = GP(__sync_fetch_and_add(&q->tail,1));
    q->queue[tail] = queue;
    __sync_synchronize();
    q->flag[tail] = true;
}

消息出队列：

struct message_queue *
skynet_globalmq_pop() {
    struct global_queue *q = Q;
    uint32_t head =  q->head;
    uint32_t head_ptr = GP(head);
    if (head_ptr == GP(q->tail)) {
        return NULL;
    }

    if(!q->flag[head_ptr]) {
        return NULL;
    }

    __sync_synchronize();

    struct message_queue * mq = q->queue[head_ptr];
    if (!__sync_bool_compare_and_swap(&q->head, head, head+1)) {
        return NULL;
    }
    q->flag[head_ptr] = false;

    return mq;
}

可以看到，不管是入队列还是出队列，skynet仅使用了gcc提供的几个原子操作，没有任何加锁解锁处理。

在入队列时，直接将任务特定队列添加到全局队列队尾，没有任何判断队列满的处理，这里假定全局队列永远都不会满。全局队列在初始化时直接为其分配了65536个slot的队列空间，后续不会增长。一台服务器并发客户端一般不会超过10000，每个客户端对应一个任务特定消息队列，每个任务特定消息队列最多添加到全局队列中一次。根据这些信息，同时在线客户小于65535时队列不会满。正是基于这种假定，skynet让多个线程并发入队列实现了wait-free。这里对任务特定消息队列的访问代码提出了比较严格的要求：这些消息队列的访问必须加锁，以防止一个消息队列多次添加到全局队列中。

实际上，虽然全局队列入队时实现了wait-free，但q->tail在通过原子操作加1后，原先tail指向的位置q->queue[tail]中的内容并没有同步设置。正因如此，全局队列中除了队列数组外，还有一个flag数组，用以标记q->queue[tail]中的值是否设置。同时为了防止cpu乱序执行导致flag先设置，必须通过__sync_synchronize()在设置flag为true前添加内存barrier，保证flag的设置在q->queue[tail]赋值之后执行。

在出队列时，有对全局队列进行判空处理（if (head_ptr == GP(q->tail))），但当发生多个线程同时取同一个消息时，通过原子操作虽然保证了只有一个线程取到消息，但没有取到消息的线程不会继续取后续消息，而是直接假装队列已空，回家idle去了。参考如下代码：

static void *
_worker(void *p) {
    struct worker_parm *wp = p;
    int id = wp->id;
    struct monitor *m = wp->m;
    struct skynet_monitor *sm = m->m[id];
    for (;;) {
        if (skynet_context_message_dispatch(sm)) {  
            //没有取到消息时，会进入这里进行wait，线程挂起
            CHECK_ABORT
            if (pthread_mutex_lock(&m->mutex) == 0) {
                ++ m->sleep;
                pthread_cond_wait(&m->cond, &m->mutex);
                -- m->sleep;
                if (pthread_mutex_unlock(&m->mutex)) {
                    fprintf(stderr, "unlock mutex error");
                    exit(1);
                }
            }
        }
    }
    return NULL;
}

当大量客户端并发请求时，出队列的这种碰撞应该是比较频繁的，这种处理方式会导致线程频繁挂起。而为了减少线程的频繁唤醒，skynet只有在所有worker都idle后，再收到新的socket请求时才会唤醒一个挂起的线程：

static void
wakeup(struct monitor *m, int busy) {
    if (m->sleep >= m->count - busy) {
        //busy=0，意味着只有挂起线程数sleep=工作线程数count时才会唤醒线程
        pthread_cond_signal(&m->cond);
    }
}

static void *
_socket(void *p) {
    struct monitor * m = p;
    for (;;) {
        int r = skynet_socket_poll();
        if (r==0)
            break;
        if (r<0) {
            CHECK_ABORT
            continue;
        }
        wakeup(m,0); // 参数busy为0
    }
    return NULL;
}

可以看出，当由于从全局队列取消息发生碰撞，部分线程被挂起后，只要有一个线程仍然在工作，这些挂起的线程就不会被唤醒（即使全局队列中仍然有大量需要处理的消息）。这样并不能非常有效地使用多核能力。

解决方案可以参考go1.1运行时goroutine调度器的实现方案，将全局队列划分为每个线程一个的线程特定队列，同一线程特定队列中的任务特定队列都由该线程处理。这样线程特定队列只有一个消费者线程，可以很容易实现无锁出队操作，同时不会出现上述问题。另外为了防止出现各个线程间不均衡的情况，一个线程在处理完一个消息后，根据当前自身线程特定队列的负载情况（比如队列长度和消息滞留时间），可以决定将任务特定队列push到其他线程特定队列的队尾，还是自己线程特定队列的队尾。在自己线程特定队列为空时，可以直接从任务特定队列中取出下一个消息继续处理，减少一次入队和出队操作。这种方案在不使用复杂的work stealing方案的情况下，仍能保持线程间的负载均衡，不会出现线程饿死的情况。

4. 任务特定消息队列

每个任务特定消息队列都是针对一个在线客户，对应有一个socket和一个lua vm。这个队列有多个并发生产者，但只有一个并发消费者。对于这种队列，一般我们可以在入队列中使用spin lock，在出队列时免锁（但需要使用内存屏障保证cpu不会乱序执行内存访问指令）。不过skynet中，在入队列和出队列时都加了spin lock：

#define LOCK(q) while (__sync_lock_test_and_set(&(q)->lock,1)) {}
#define UNLOCK(q) __sync_lock_release(&(q)->lock);

int
skynet_mq_pop(struct message_queue *q, struct skynet_message *message) {
    int ret = 1;
    LOCK(q)

    if (q->head != q->tail) {
        *message = q->queue[q->head];
        ret = 0;
        if ( ++ q->head >= q->cap) {
            q->head = 0;
        }
    }

    if (ret) {
        q->in_global = 0;
    }

    UNLOCK(q)

    return ret;
}

入队列：

void
skynet_mq_push(struct message_queue *q, struct skynet_message *message) {
    assert(message);
    LOCK(q)

    if (q->lock_session !=0 && message->session == q->lock_session) {
        _pushhead(q,message);
    } else {
        q->queue[q->tail] = *message;
        if (++ q->tail >= q->cap) {
            q->tail = 0;
        }

        if (q->head == q->tail) {
            expand_queue(q);
        }

        if (q->lock_session == 0) {
            if (q->in_global == 0) {
                q->in_global = MQ_IN_GLOBAL;
                skynet_globalmq_push(q);
            }
        }
    }

    UNLOCK(q)
}

很奇怪的设计。仔细分析入队列的代码，原来skynet并不是把任务特定队列当做一个FIFO队列来使用，而是当做同时支持FIFO和LIFO的deque来使用。究其原因，是为了支持lua中的skynet.blockcall才这样做的。为了支持skynet.blockcall，任务特定队列数据结构中添加了一个lock_session成员：

struct message_queue {
    uint32_t handle;
    int cap;
    int head;
    int tail;
    int lock;
    int release;
    int lock_session;
    int in_global;
    struct skynet_message *queue;
};

skynet.blockcall实现代码如下：

function skynet.blockcall(addr, typename , ...)
    local p = proto[typename]
    c.command("LOCK")
    local session = c.send(addr, p.id , nil , p.pack(...))
    if session == nil then
        c.command("UNLOCK")
        error("call to invalid address " .. skynet.address(addr))
    end
    return p.unpack(yield_call(addr, session))
end

c.command("LOCK")命令执行时会设置消息队列的lock_session为context的下一个session值，c.send发送请求时返回的session就是这个session值。响应消息回来时，skynet_mq_push发现响应消息中的session值与队列中的lock_session一致，就会通过_pushhead函数将响应消息放到队列头部，从而让skynet尽快处理。_pushhead实现如下：

static void
_pushhead(struct message_queue *q, struct skynet_message *message) {
    int head = q->head - 1;
    if (head < 0) {
        head = q->cap - 1;
    }
    if (head == q->tail) {
        expand_queue(q);
        --q->tail;
        head = q->cap - 1;
    }

    q->queue[head] = *message;
    q->head = head;

    _unlock(q);
}

static void
_unlock(struct message_queue *q) {
    // this api use in push a unlock message, so the in_global flags must not be 0 ,
    // but the q is not exist in global queue.
    if (q->in_global == MQ_LOCKED) {
        skynet_globalmq_push(q);
        q->in_global = MQ_IN_GLOBAL;
    } else {
        assert(q->in_global == MQ_DISPATCHING);
    }
    q->lock_session = 0;
}

实际上在我看来，deque的使用完全没有必要。skynet.blockcall使用了新的session，因此可以对应使用新的coroutine。此时即使将响应消息放到队列尾部，该响应也会正常处理。使用lock_session的唯一好处就是提高了响应消息的优先级，当响应消息过来时，优先处理响应消息。但这种做法完全可以通过另外一个高优先级队列来实现，就像erlang调度器中做的那样。为每个任务增加一个高优先级队列后，可以达到与当前deque相同的效果，同时又可以免锁从队列中取消息，应该会提高一点性能。

5. 总结

没有做过游戏开发，凭着自己多年做电信服务器软件的经验和一些个人兴趣爱好瞎扯了一些。电信服务器软件和游戏后台服务器软件有很多相似之处，但两个领域也有很多重大差异，可能很多在我看来很重要的问题在游戏开发中实际上无所谓。skynet已经实际应用了一段时间，具体设计和实现应该都有特定的需求。还是那句话，软件开发中可以争论对错，不过最终是好是坏还是由实际运行效果决定。正因为没看到具体的应用场景，这里的总结只是拿一些服务器软件通用的原理姑且推之。

skynet代码中，handle的存取使用了读写锁，任务特定队列的访问使用了自旋锁，全局队列的访问使用了wait-free的免锁设计。除了handle存取时多读少写，使用读写锁比较合适之外，任务特定队列和全局队列的调度设计都有待改进。系统中每处理一个消息时会涉及全局队列的一次出队列和一次入队列，全局队列的使用非常频繁，因此看起来wait-free的设计没什么问题。但仔细分析后会发现，在系统比较繁忙时，wait-free设计会导致部分冲突线程出现没必要的等待。将全局队列改为线程特定队列，入队列使用自旋锁而出队列不加锁，会提高多核使用效率。任务特定队列只有一个并发消费者，使用FIFO的队列后，出队列不需要加锁。