Canvas性能优化小结

简介

H5中引入了对canvas的支持,使得网页的表达能力更加丰富了。程序员可以通过canvas来绘制复杂的图形,甚至是游戏。因为工作中的需求,需要使用canvas在网页上绘制家谱。具体的算法可以看之前的一篇总结:树的可视化以及家谱绘制的算法
。当家谱中的数据量变大之后,整个绘制过程会变的很卡(800左右人物的家谱1000次绘制居然需要25s左右)。但是在做完优化后,1000次绘制只需要0.15s左右。

家谱示例

目前的家谱绘制共有两部分。一个是家谱的主体,用户可以通过鼠标、滚轮去任意的浏览;一个是左上角的小地图功能,帮助用户了解到当前浏览的位置,小地图中的有色方块就是用户整个屏幕显示的内容。

优化措施一:缓存

缓存是在绝大多数系统中经常用到的提升性能的方法,典型的以空间换时间。在canvas中当然也可以使用缓存。在家谱的每一次绘制中,都要遍历所有的人物,然后计算他们的位置大小,然后绘制到界面上,然后还要遍历所有的路径再次进行绘制。而使用缓存的目的就是避免这一部分的计算。因此,在任何复杂计算后的绘制,都能使用缓存来提升性能。

在canvas中有这样一个方法,CanvasRenderingContext2D.drawImage(image, dx, dy)image参数代表要绘制的图片源,不仅仅可以是一个image对象,还可以是一个canvas对象。所以如果我们将一个复杂的图形作为canvas对象缓存起来,然后直接使用drawImage方法去绘制到画面上,就能减少很多的重复计算,来提升性能。

例如以下的伪代码

function paintPerson() {
    // paint 
}

function paintFamilyTree() {
    for(var i = 0; i < 10000; i++) {
        paintPerson()
    }
}

// 用户移动鼠标就需要重绘族谱
dom.addEventListener("mousemove", function() {
    paintFamilyTree()
}

用户每一次移动鼠标,都需要10000次的循环去画。所以我们使用下面的方法,使得只需要计算一次

function paintPerson() {
    // paint 
}

function paintFamilyTree() {
    for(var i = 0; i < 10000; i++) {
        paintPerson()
    }
}

var canvasObj = cache(paintFamilyTree) // 缓存这次绘制的结果。

dom.addEventListener("mousemove", function() {
    ctx.drawImage(canvasObj,0,0)
}

那么如何去缓存这个 canvas 对象呢?可以使用document.createElement('canvas')来创建一个不在页面上显示的 canvas 对象,一般也称它为离屏画布,这里用变量 offScreenCanvas 来称呼。然后将绘制的图形画在这个 canvas 上,之后调用 ctx.drawImage(offScreenCanvas,0,0) 即可。

在创建这个离屏画布的时候,我们也要设置合适的宽高,这样也有助于提升性能。

可以参考这个例子来感受一下性能差距:
离屏画布缓存来提升页面性能
例子代码如下:

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>离屏canvas实例</title>
        <style>
            .main-wrapper {
                width: 800px;
                margin: 10px auto;
            }
        </style>
    </head>

    <body onload="init()">
        <div class="main-wrapper">
            <canvas width="800" height="600" style="border: 1px solid #ccc" id="canvas">
                你的浏览器不支持canvas
            </canvas>
            <br><br><br><br><br><br><br><br><br>
            <div id="result"></div>
            <br>
            渲染次数:<input type="number" id="times" value="1000">,共耗时(ms)<span id="time_used">0</span><br>
            <button onclick="doTest(false,false)">不使用离屏canvas</button>
            <button onclick="doTest(true,false)">使用离屏canvas</button>
            <button onclick="doTest(true,true)">使用离屏canvas并设置正确的高度</button>
        </div>
        <script>
            /**
             * 离屏缓存,num为缓存canvas的数量
             */
            var OffScreenCache = function (num) {
                this.canvases = [];
                for (i = 0; i < num; i++) {
                    this.canvases.push(document.createElement("canvas"));
                }
            }
            OffScreenCache.prototype = {
                pop: function() {
                    return this.canvases.pop();
                },
                push: function(canvas) {
                    this.canvases.push(canvas);
                },
                destroy: function() {
                    this.canvases = null;
                }
            }
            var Ball = function (color) {
                this.radius = 50;
                this.lineWidth = 4;
                this.cache = null;
                this.color = color;
            }
            Ball.prototype = {
                paint: function(ctx, x, y) {
                    ctx.save();
                    ctx.lineWidth = this.lineWidth;
                    ctx.strokeStyle = this.color;
                    for (i = 1; i < this.radius; i+= this.lineWidth) {
                        ctx.beginPath();
                        ctx.arc(x, y, i, 0, Math.PI*2,true); // 绘制
                        ctx.stroke();
                    }
                    ctx.restore();
                },
                useCache: function (cacheCanvas, autoSet) {
                    if (autoSet) {
                        cacheCanvas.width = this.radius * 2;
                        cacheCanvas.height = this.radius * 2;
                    }
                    cacheCtx = cacheCanvas.getContext('2d')
                    this.paint(cacheCtx, cacheCanvas.width / 2, cacheCanvas.height / 2)
                    this.cache = cacheCanvas
                }
            }
            /******************** 下面是执行代码 **************************/
            var g_canvas, g_ctx;
            var g_width = 800;
            var g_height = 600;
            function init() {
                g_canvas = document.getElementById("canvas");
                g_ctx = g_canvas.getContext('2d');
            }
            function getRandomPos() {
                var x = Math.random() * g_width
                var y = Math.random() * g_height
                return {x:x, y:y}
            }
            function showResult(ballCount) {
                var dom = document.getElementById("result");
                dom.innerHTML = "";
                var str = "";
                for (var key of Object.keys(ballCount)) {
                    str += "<span>" + key + "ball:" + ballCount[key] + "</span>    "
                }
                dom.innerHTML = str;
            }
            function doTest(useCache, autoSet) {
                g_ctx.clearRect(0, 0, g_width, g_height)
                var startTime = Date.now();
                var times = document.getElementById("times").value
                var colorArray = ['red', 'blue', 'green', 'black', 'pink']   // 共绘制5种颜色
                var ballCount = {};
                colorArray.forEach(function(color) {
                    ballCount[color] = 0;
                })
                if (useCache) {
                    var colorBall = [];
                    var cacheCanvases = new OffScreenCache(colorArray.length);
                    for (var i = 0; i < colorArray.length; i++) {
                        var ball = new Ball(colorArray[i]);
                        var cacheCanvas = cacheCanvases.pop();
                        ball.useCache(cacheCanvas, autoSet)
                        colorBall.push(ball)
                    }
                    for (var i = 0; i < times; i++) {
                        ball = colorBall[i % 5]
                        ballCount[ball.color]++;
                        var pos = getRandomPos()
                        g_ctx.drawImage(ball.cache, pos.x, pos.y)       // 开始画
                    }
                } else {
                    for (var i = 0; i < times; i++) {
                        var color = colorArray[i % 5];
                        var ball = new Ball(color)
                        var pos = getRandomPos()
                        ball.paint(g_ctx, pos.x, pos.y)               // 开始画
                        ballCount[color]++;
                    }
                }
                var endTime = Date.now();
                document.getElementById("time_used").innerText = endTime - startTime;
                showResult(ballCount)
            }
        </script>
    </body>
</html>

优化措施二:分层

在上述的族谱图片中,左上角的小地图其实是有两个canvas重叠而成。底层的canvas绘制族谱的缩略图,上层的canvas绘制小方框。这样在小方框移动时,只需清空上层canvas的局部画布重绘小方框即可,不需要重绘底层的缩略图。

接口请求速率(接口防刷)限制方案

1.场景

当前业务中接口防刷的场景有:

  • 1.短信/邮件接口。这个接口不做好防刷策略,损失是很大的。
  • 2.涉及到安全问题的接口调用。比如注册接口,登录接口等等。过于频繁的请求可能代表着用户的批量注册,用户密码的暴力破解(需要考虑到可能是用户忘记密码了)等等。

2.要求

  • 1.与当前业务系统解耦合
  • 2.可以很方便的对不同的接口设置不同的请求频率限制
  • 3.具有较好的性能。在大并发的情况下,需要有正确的结果

3.方案提出

3.1 token bucket(令牌桶)

token bucket算法的如下图:

token_bucket

描述如下:

1.假设有一个桶,不断的向桶中投放token,并且我们也可以从桶中取出token。
2.投放token的速率是恒定的r1,桶满了token数量则不会再增长。
3.取出的速率是随机的r2。如果桶是空的,则无法取出token。
4.所有的请求都必须从桶中取出token才是有效的。否则该请求会被拒绝。

举个例子,假设桶的容量是10,每秒放2个token进去。

  • 如果现在每秒2个请求,那么所有这样的请求都是没有问题的,都会拿到token。
  • 如果现在每秒4个请求,10 + 2x = 4x。也就是x=5秒后请求就没法及时拿到token,被丢弃。

总结出以下特点:
– 如果请求速率过快,到一段时间后会受到限制
– 允许突发请求

3.2 redis数据库

使用redis数据库完全是因为方便以及速度。只要注意这其中存在的CAS问题即可

4.具体实现

首先,为了解决redis中检查和存储数据存在的CAS问题,我们需要使用lua脚本。因此,对于token bucket的主要实现是用lua脚本实现,然后通过php调用。

local function mysplit(inputstr, sep)
    if sep == nil then
            sep = "%s"
    end
    local t={} ; 
    local i=1
    for str in string.gmatch(inputstr, "([^"..sep.."]+)") do
            t[i] = str
            i = i + 1
    end
    return t
end

local res = redis.pcall('get',KEYS[1])

if (res == false) then
    -- bucket不存在,初始化为capacity - 1
    local str = string.format("%d %d",ARGV[1] - 1,ARGV[2])  
    return redis.pcall('set',KEYS[1],str)
end

local arr_str = mysplit(res, " ")

local num = arr_str[1]
local timestamp = arr_str[2]

-- 根据时间戳来计算num,这里一秒2个令牌
num = num + (ARGV[2] - timestamp) * ARGV[3]
-- 不超过10个令牌
if num > 10 then
    num = 10
end

if (tonumber(num) > 0) then
    -- 拿到token并减一
    local str = string.format("%d %d",num - 1,ARGV[2])
    return redis.pcall('set', KEYS[1], str)
else 
    -- 没有拿到token
    return false
end
<?php

sha = '2ff7ad2d1b49da8430e5adc8675e';

/**
 * 初始化lua脚本
 */
function initScript(redis) {
    global sha;
    //不存在脚本,load进去script = file_get_contents('check_and_set.lua');
    sha =redis->script('load', script);
    if(redis->getLastError() !== NULL){
        echo "出错了:".redis->getLastError().'\n';
    }
    echo "初始化的脚本sha:".sha.PHP_EOL;
}

function getTokenFromBucket(redis,bucket) {
    global sha;capacity = 10;
    time = time();inputRate = 2;     //一秒2个token
    params = array(bucket, capacity,time, inputRate);result = redis->evalSha(sha, params, 1);
    if(redis->getLastError() !== NULL){
        echo "出错了:".redis->getLastError().'\n';
    }
    returnresult;
}

redis = new Redis();redis->pconnect("127.0.0.1");

initScript(redis);start = microtime(true) * 1000;

while(true) {
    result =  getTokenFromBucket(redis, 'bucket1');
    if (!result) {
        break;
    } else {
        echo time()."--拿到令牌".PHP_EOL;
        usleep(250000);    //每秒请求4次,10 + 2x = 4x, x = 5。5秒左右无法拿到令牌
    }
}end = microtime(true) * 1000;

echo "共耗时:".(end -start)."毫秒".PHP_EOL.PHP_EOL;

start = microtime(true) * 1000;

while(true) {result =  getTokenFromBucket(redis, 'bucket2');
    if (!result) {
        break;
    } else {
        echo "拿到令牌".PHP_EOL;
        usleep(500000);    //每秒请求2次,永远可以拿到令牌
    }
}

end = microtime(true) * 1000;

echo "共耗时:".(end - $start)."毫秒".PHP_EOL.PHP_EOL;

代码中主要部分概括如下:

  • 检查redis中是否存在桶bucket1
  • 如果不存在,那么默认的容量是10,将bucket1设为9 timestamp(timestamp为当前的时间戳)。返回true
  • 如果存在,则获取该bucket1的值,解析出实际token数量为num,以及上一次存储时时间戳为pre。如果rate为token的生成速率,那么现在的token数量应该是:num = num + (time() – pre) * rate。num最大为默认容量10。如果num大于0,则减一后重新设置,返回true。否则返回false。

代码的运行结果如下:

运行结果演示

5.扩展知识

与token bucket相似的算法还有leaky bucket(漏桶)。leaky bucket 就像是 token bucket的镜像一样。leaky bucket 一般用于Traffic shaping和Traffic policing等问题,与下面的两张图对应。

leaky bucket

leaky bucket

可以描述如下:

  • 1.有一个桶,其上方水龙头以变化的速率r1向里面滴水,桶底的水龙头则以恒定的速率向下漏水
  • 2.水桶装满后,上方水龙头的滴水就会溢出
  • 3.水桶空后,下方水龙头则不会滴水

这里举一个异步任务处理(任务队列的容量是有限的)的例子。

  • 上方水龙头相当于任务投递系统,下方水龙头相当于任务处理系统。
  • 任务投递的速率是变化的,因为不同时间段的系统负载可能不同。
  • 任务处理系统的速率是恒定的,因为机器的处理能力是恒定的。
  • 当任务投递的速率大于处理速率,填充满任务队列后,后面的任务都会被丢弃。

可以看出leaky bucket可以将不规则的抖动的请求序列变成规则的平滑的请求序列。leaky bucket通常有两个版本:作为一个评判的仪器(meter)或者是生成一个合法请求队列(queue)。

虽然在使用中leaky bucket和token bucket是不同的,但实际上他们是同一种思路。leaky bucket的变化的输入相当于token bucket的变化的输出,leaky bucket的恒定的输出相当于token bucket的恒定的输出。

参考文献

token bucket
leaky bucket

redis中的事务与锁

这篇文章是我在查找如何对redis中的值做原子操作时的一系列笔记,虽然最初的目的只是研究有哪些方式可以实现事务(transaction)操作,但是后来的延伸很多,所以我认为有必要做一些笔记防止忘记。

1.redis中的事务

redis中的事务其实并不满足数据库事务的四个特性:原子性(Atomicity)、一致性(Consistency)、隔离型(Isolation)、持久性(Durability),简称ACID。redis只能在一致性和隔离性上提供保证,而原子性和持久性是无法保证的。因为redis的事务操作如果中断,无法回滚,满足不了原子性,并且redis的持久化策略有很多中,比如在纯内存模式下是无法持久化数据库更改的,满足不了持久性。

所以下面针对与redis事务的讨论都是有局限性的。仅仅是指对redis数据进行操作时,不会受到其他客户端的干扰。举例来说:客户端A读取keyA,修改keyA中间,不会受到客户端B的影响。

    //客户端A执行以下代码
    //获取user1的性别,如果性别是男,头像设置为男性角色
    //否则头像设置为女性角色
    gender =redis->get('user1_gender');
    if(gender === 'male'){redis->set('user1_photo','male.png');
    }else{
        $redis->set('user1_photo','female.png');
    }
    //客户端B执行以下代码
    //更改user1的性别,如果是男则改为女,如果是女则改为男
    //并根据性别设置头像
    gender =redis->get('user1_gender');
    if(gender === 'male'){redis->set('user1_gender','female');
        redis->set('user1_photo','female.png');
    }else{redis->set('user1_gender','male');
        $redis->set('user1_photo','male.png');
    }

如果客户端A、B同时只有一个执行,那么性别和头像一定是对应的。但是A、B同时执行,并且执行顺序如下:
时序图

那么执行结果就是user1性别为女,但头像为男性角色。

所以针对于这种情况,我们需要一定的措施去预防。

redis的事务实现方式有多种。据我所知有三种方式:

  • 1.MULTI/EXEC
  • 2.WATCH/UNWATCH
  • 3.lua脚本

1.1 MULTI/EXEC

MULTI/EXEC是成对出现的指令。大家都知道,redis执行指令是单线程的,也就是说所有指令都处于一个队列,一个一个执行。MULTI/EXEC可以保证所有的指令都会被同时放松到redis中,中间不会掺杂来自其他客户端的指令。

但是这个针对于上述情况并不适用。因为我们需要在GET到数据之后,才能做下面的更新操作。

1.2 WATCH/UNWATCH

在redis中我们可以使用watch来监视一个值。

redis> WATCH name
OK

redis> MULTI
OK

redis> SET name peter
QUEUED

redis> EXEC
(nil)

比如这段代码,在我们WATCH name后,如果另外一个客户端修改了name的值,那么这个客户端再次修改name则无法成功。这其实就是乐观锁的一种实现。它保证了代码的执行结果不会错乱。用一开始的例子来说,就是不会出现性别和头像不对应的情况。

1.3 lua脚本
redis中可以执行lua脚本来完成事务操作。lua脚本和MULTI/EXEC很像,也就是说在lua脚本执行的过程中,redis是不执行其他客户端的指令的。

但是lua脚本的不同之处在于,你可以使用GET操作来获取数据并判断,再执行后来的操作。

2.在redis操作中使用锁

在多线程环境中,为了防止资源出现race condition,需要借助锁来互斥的访问资源。在这里也是一样的,user1_gender就是我们要互斥访问的资源。

还是上述那个例子,如果我们使用悲观锁,只有获得锁的客户端才能读取和修改user1的的值,也可以很好的解决这个问题。

伪代码如下:

$can_lock = lock('user1_gender'); //得到锁
if($can_lock){
    do_something();
    $release_lock('user1_gender');  //释放锁
}

不同于多线程环境下的是,我们这里的锁的范围是针对于不同的客户端。因此没法使用基于系统的、或者基于语言的锁,而是得使用分布式的锁。这样的分布式锁我们同样可以借助于redis来实现。

整个分布式锁的实现可以概括为以下几个步骤:

    1. 获得锁。得到要锁的资源的唯一hash:lockname,以及一个随机字符串:identifier,设置expire:20s,这个expire就是锁的有效期,在有效期后锁会自动释放,防止出现死锁。在redis中使用setnx(lockname,identifier,expire)。这句代码的意思是:如果redis中不存在lockname,则存入lockname,值为identifier,过期时间是expire。
    1. 第一步我们就得到了一个锁,这一步我们开始执行获得锁之后的代码
    1. 释放锁。我们根据lockname来从redis中查找。如果get(lockname) identifier,则表示我们仍然持有这把锁,使用delete(lockname)来释放锁。如果不等于,说明我们已经不持有这把锁了,则什么也不做。

那么lock函数可以用以下代码来描述:

function lock(lockname,identifier,expire = 20){acquire_timeout = 10;      //花费10秒去获得锁,否则就放弃
    end = time() +acquire_timeout
    while (time() < end){can_lock = redis->setnx(lockname,identifier,expire);
        if($can_lock){
            return true;
        }
        sleep(0.1);
    }

    return false;
}
    function release_lock(lockname,identifier){
        redis->watch(lockname);
        try{
            if(redis->get(lockname) === identifier){
                //锁仍然持有,释放锁redis->delete(lockname);
                return true;
            }redis->unwatch();
        }catch(Exception $e){

        }

        return false;
    }

这样我们就很轻松的得到了借助于redis实现的分布式锁。但是这样的实现方式依然是有问题的。

问题1:如果在某个客户端获得锁后,redis主服务器宕机了,那么即使我们使用了主从备份,从属服务器被提升为主服务器,因为redis备份是异步的原因,这里的锁是没法及时同步到从属服务器的。

问题2:如果一个客户端在获得锁后,执行的操作超过了锁的有效期,锁被自动释放了。那么后续的操作是没法受到锁的保护的。

问题2的解决方案可以是watch,在获取锁后,可以立刻watch资源,然后再执行余下操作。

问题1的解决方案则是接下来要介绍的redlock算法

3.redlock

redlock算法是Redis的作者antirez提出来的。
可以被概述为以下几个步骤:

  • 1.获取当前时间(毫秒数):start_time。

  • 2.按顺序获得N个Redis节点的锁(使用相同的key和identifier,并设置初始有效时间:init_validity_time)。在获得每个redis结点的锁的时候,都要设置一个timeout参数,这个timeout要远小于锁的自动释放时间。例如:如果锁的自动释放时间是10s,timeout应该为~5-55ms(还得视网络情况决定)。这样可以防止在获取锁时,节点宕机,导致耗时过长锁被释放了。如果获取锁失败则立刻获取下一个redis节点的锁

  • 3.client计算为了获取锁花了多长时间:used_time = current_time – start_time。当且仅当client可以获取大多数实例的时候(至少N / 2 + 1个),所花费的时间小于锁的有效时间,才认为获得了锁。

  • 4.如果获得了锁,重新计算锁的有效时间:validity_time = init_validity_time – used_time

  • 5.如果锁获取失败(无法获取N/2 + 1个节点的锁,或者有效时间validity_time是负数),则释放所有实例的锁(即使获得锁的时候失败了,这主要是考虑到有的时候锁获得成功了,但是告知客户端时网络异常)。

这很好的解决了上述的问题1,通过多个redis节点了来保证分布式锁服务的可靠性。

参考文章

Distributed locks with Redis

基于Redis的分布式锁到底安全吗(上)?

基于Redis的分布式锁到底安全吗(下)?

redis事务

6.2.3 Building a lock in Redis