如何不用 redis 设计一个排行榜

在通用排行榜采用 redis 的 sorted set 作为解决方案已经是通用方案了

但业务需求并不是单一需求, 比如玩家最近一关的破解时间来排定, 既鼓励准确率, 又鼓励速度. 换句话说, coin(金币)为第一排序因素, time(破解时间)为第二排序因素.

而 redis 的 sorted set 是单一维度, 只有一个 score 如何解决两个维度的数据排行呢?

很多常规思路是把多维转成一维, 然后将数据存入 score

另外一种思路是将两个因素并入一个因素, 很幸运 coin + time 可以并成一个 score 从而免除一些逻辑计算

当然这篇文章并不是介绍 redis 的

buntdb

BuntDB is an embeddable, in-memory key/value database for Go with custom indexing and geospatial support

直接上代码, 看下BuntDB解决方案, 天生支持多维索引, 厉害了

db, _ := buntdb.Open(":memory:")
db.CreateIndex("last_name_age", "*", buntdb.IndexJSON("name.last"), buntdb.IndexJSON("age"))
db.Update(func(tx *buntdb.Tx) error {
	tx.Set("1", `{"name":{"first":"Tom","last":"Johnson"},"age":38}`, nil)
	tx.Set("2", `{"name":{"first":"Janet","last":"Prichard"},"age":47}`, nil)
	tx.Set("3", `{"name":{"first":"Carol","last":"Anderson"},"age":52}`, nil)
	tx.Set("4", `{"name":{"first":"Alan","last":"Cooper"},"age":28}`, nil)
	tx.Set("5", `{"name":{"first":"Sam","last":"Anderson"},"age":51}`, nil)
	tx.Set("6", `{"name":{"first":"Melinda","last":"Prichard"},"age":44}`, nil)
	return nil
})
db.View(func(tx *buntdb.Tx) error {
	tx.Ascend("last_name_age", func(key, value string) bool {
		fmt.Printf("%s: %s\n", key, value)
		return true
	})
	return nil
})

// Output:
// 5: {"name":{"first":"Sam","last":"Anderson"},"age":51}
// 3: {"name":{"first":"Carol","last":"Anderson"},"age":52}
// 4: {"name":{"first":"Alan","last":"Cooper"},"age":28}
// 1: {"name":{"first":"Tom","last":"Johnson"},"age":38}
// 6: {"name":{"first":"Melinda","last":"Prichard"},"age":44}
// 2: {"name":{"first":"Janet","last":"Prichard"},"age":47}

排行榜数据多, 几个维度都没有问题, 值得注意的是排序字段, 如果是数字型, json 里面必须也是数字型, 字符型的数字排序会有问题

介绍 RSA 的文章很多, 这里打算写一点能看得懂的文章

基本知识

为什么可靠? 对极大整数做因数分解是很困难的。

秘钥: 公钥(长度,公因数1) 私钥(长度,公因数2)

甲乙加密数据:

甲方传递消息给乙, 获取乙方公钥加密数据, 把数据交给乙, 乙用秘钥解密 乙方传递消息给甲, 获取甲方公钥加密数据, 把数据交给甲, 甲用秘钥解密

举例:

  1. 随机选择互质数 p=7, q=32 (如果不选择互质数的话, 随便一个数字反推质数, 因数分解那就比较难了, 我们先选好互质数, 方便欧拉函数计算)
  2. 计算一下他们乘积 n = p*q = 224
  3. 计算乘积数下面的质数有几个: 满足第四种欧拉方式

    φ(n) = φ(p1p2) = φ(p1)φ(p2)
       
    φ(224) = φ(7)*φ(32) = (7-1) * φ(2^5) = 6 * 32(1-1/2) = 96
    
    解释下224的计算方法, 
    7为质数, 所以φ(7) =7-1
    32为质数2的5次方, 符合通用公式 φ(32) = 32 * (1-1/2)
    
    

互质

如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

关于互质关系,不难得到以下结论:

  1. 任意两个质数构成互质关系,比如13和61。
  2. 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10。
  3. 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57。
  4. 1和任意一个自然数是都是互质关系,比如1和99。
  5. p是大于1的整数,则p和p-1构成互质关系,比如57和56。
  6. p是大于1的奇数,则p和p-2构成互质关系,比如17和15。

欧拉函数(互质关系个数)

请思考以下问题:

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

欧拉函数就是计算个数的一个函数, 感兴趣的可以找下资料了解下

其中p1, p2……pn为x的所有质因数,x是不为0的整数。
φ(n) = n(1-1/p1)(1-1/p2)

解释一下:

  1. n 为质数,
     φ(n) = n - 1
    
  2. n 不为质数, 如21,
     φ(n) = φ(3*7)  3和7 都是质数, 参考第一条 φ(n) = (3-1)* (7-1) =12 
    
  3. 通用公式 φ(n) = n(1-1/p1)(1-1/p2)

     先知道质数情况下计算φ(n)
     37 * 7 = 259
     φ(259) = (37-1)(7-1) = 216
        
     不知道质数组成, 任意一个大于1的正整数,都可以写成一系列质数的积
     φ(1323) = φ(3^3*7^2) = 1323 * (1-1/3) * (1-1/7) = 756
        
     这个公式就比上面的复杂, 需要计算公因数(greatest common divisor)
        
    

golang 利用公因数 计算φ(n)个数

package main

import (
	"fmt"

)

// greatest common divisor (GCD) via Euclidean algorithm
func GCD(a, b uint) uint {
	for b != 0 {
		t := b
		
		b = a % b
		a = t
	}
	return a
}

// Eulers Totient Function
func Phi(n uint) uint {
	var result uint = 1
	var i uint
	for i = 2; i < n; i++ {
		if GCD(i, n) == 1 {
			result++
		}
	}
	return result
}

func main() {
	
	fmt.Println(Phi(uint(33)))
	
}

欧拉定理

如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:

a^φ(n) - 1 = mod(n)

解释一下:

a的φ(n)次方可以被 (n +1) 整除

模反元素

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

这时,b就叫做a的”模反元素”。

ab === 1 (mod n)

本文译自 Functional Options Pattern in Go 版权@归原文所有.

Golang 开发者遇到的许多问题之一是尝试将一个函数的参数设置为可选. 这是一个非常常见的用例, 有些对象应该使用一些基本的默认设置来开箱即用, 并且你偶尔可能需要提供一些更详细的配置.

在很多语言中这很容易; 在 C 族语言中, 可以使用不同数量的参数提供相同函数的多个版本; 在像 PHP 这样的语言中, 可以给参数一个默认值,并在调用方法时忽略它们. 但是在 Golang 中, 这两种方式你哪个也用不了. 那么你如何创建一个函数, 用户可以指定一些额外的配置?

有很多可能的方法可以做到这一点, 但是大多数都不能满足要求, 或者需要在服务端的代码中进行额外的检查和验证, 或者通过传递额外的客户端不关心的参数来为客户端做额外的工作.

我将介绍一些不同的方案, 并说明为什么每个都不是最理想的, 然后我们将建立我们自己的方式来作为最终干净的解决方案: 函数式选项模式 (Functional Options Pattern).

我们来看一个例子. 比方说, 我们有一些名为 StuffClient 的服务, 它有一些东西, 并有两个配置选项(timeout 和 retries):

type StuffClient interface {
    DoStuff() error
}
type stuffClient struct {
    conn    Connection
    timeout int
    retries int
}

结构体 stuffClient 是私有的, 所以我们应该为它提供一些构造器:

func NewStuffClient(conn Connection, timeout, retries int) StuffClient {
    return &stuffClient{
        conn:    conn,
        timeout: timeout,
        retries: retries,
    }
}

嗯, 但是现在我们每次调用 NewStuffClient 时都要提供 timeout 和 retries. 而大多数时候我们只想使用默认值. 我们不能用不同的参数数量来定义多个版本的 NewStuffClient, 否则我们会得到一个类似 “NewStuffClient redeclared in this blockt” 的编译错误.

一个方案是创建另一个不同名称的构造器:

func NewStuffClient(conn Connection) StuffClient {
    return &stuffClient{
        conn:    conn,
        timeout: DEFAULT_TIMEOUT,
        retries: DEFAULT_RETRIES,
    }
}
func NewStuffClientWithOptions(conn Connection, timeout, retries int) StuffClient {
    return &stuffClient{
        conn:    conn,
        timeout: timeout,
        retries: retries,
    }
}

但是, 这有点蹩脚. 我们可以做得比这更好. 如果我们传入了一个配置对象呢:

type StuffClientOptions struct {
    Retries int //number of times to retry the request before giving up
    Timeout int //connection timeout in seconds
}
func NewStuffClient(conn Connection, options StuffClientOptions) StuffClient {
    return &stuffClient{
        conn:    conn,
        timeout: options.Timeout,
        retries: options.Retries,
    }
}

但是, 这也不是很好. 现在我们总是需要创建 StuffClientOptions, 并且即使我们不想指定任何选项也要传递它. 而且我们也没有自动填充默认值, 除非我们在代码中添加了一堆检查, 或者我们可以传入一个 DefaultStuffClientOptions 变量 (也不好, 因为它可以在一个地方修改导致其他地方有问题).

那么解决方案是什么? 解决这个难题最好的方法是使用函数式选项模式, 利用 Go 对闭包的方便支持. 让我们继续我们上面定义的 StuffClientOptions, 但是我们会添加一些东西:

type StuffClientOption func(*StuffClientOptions)
type StuffClientOptions struct {
    Retries int //number of times to retry the request before giving up
    Timeout int //connection timeout in seconds
}
func WithRetries(r int) StuffClientOption {
    return func(o *StuffClientOptions) {
        o.Retries = r
    }
}
func WithTimeout(t int) StuffClientOption {
    return func(o *StuffClientOptions) {
        o.Timeout = t
    }
}

泥土般芬芳, 对吧? 究竟发生了什么? 基本上我们有我们的结构定义我们的 StuffClient 的可用选项. 另外现在我们定义了一个名为 StuffClientOption 的东东(这次是单数), 它只是一个接受我们的选项 struct 作为参数的函数. 我们已经定义了另外一些函数 WithRetries 和 WithTimeout, 它们返回一个闭包. 现在魔法降临:

var defaultStuffClientOptions = StuffClientOptions{
    Retries: 3,
    Timeout: 2,
}
func NewStuffClient(conn Connection, opts ...StuffClientOption) StuffClient {
    options := defaultStuffClientOptions
    for _, o := range opts {
        o(&options)
    }
    return &stuffClient{
        conn:    conn,
        timeout: options.Timeout,
        retries: options.Retries,
    }
}

我们已经定义了一个额外的未导出(unexposed)变量, 包含我们的默认选项, 我们现在调整了我们的构造函数, 而不是接受一个可变参数. 然后, 我们遍历 StuffClientOption (单数) 列表, 并对每一项应用返回的闭包到我们的选项变量.

现在我们要做的就是这样:

x := NewStuffClient(Connection{})
fmt.Println(x) 
x = NewStuffClient(
    Connection{},
    WithRetries(1),
)
fmt.Println(x) 
x = NewStuffClient(
    Connection{},
    WithRetries(1),
    WithTimeout(1),
)
fmt.Println(x) 

这看起来相当不错而且可用. 而关于它的好的部分是, 我们可以随时添加新的选项, 只需要对代码进行非常少量的更改. 把这些都组合起来就是这样:

var defaultStuffClientOptions = StuffClientOptions{
    Retries: 3,
    Timeout: 2,
}
type StuffClientOption func(*StuffClientOptions)
type StuffClientOptions struct {
    Retries int //number of times to retry the request before giving up
    Timeout int //connection timeout in seconds
}
func WithRetries(r int) StuffClientOption {
    return func(o *StuffClientOptions) {
        o.Retries = r
    }
}
func WithTimeout(t int) StuffClientOption {
    return func(o *StuffClientOptions) {
        o.Timeout = t
    }
}
type StuffClient interface {
    DoStuff() error
}
type stuffClient struct {
    conn    Connection
    timeout int
    retries int
}
type Connection struct {}
func NewStuffClient(conn Connection, opts ...StuffClientOption) StuffClient {
    options := defaultStuffClientOptions
    for _, o := range opts {
        o(&options)
    }
        return &stuffClient{
            conn:    conn,
            timeout: options.Timeout,
            retries: options.Retries,
        }
}
func (c stuffClient) DoStuff() error {
    return nil
}

但是可以通过删除 StuffClientOptions 结构并直接将选项应用到我们的 StuffClient 来进一步简化.

var defaultStuffClient = stuffClient{
    retries: 3,
    timeout: 2,
}
type StuffClientOption func(*stuffClient)
func WithRetries(r int) StuffClientOption {
    return func(o *stuffClient) {
        o.retries = r
    }
}
func WithTimeout(t int) StuffClientOption {
    return func(o *stuffClient) {
        o.timeout = t
    }
}
type StuffClient interface {
    DoStuff() error
}
type stuffClient struct {
    conn    Connection
    timeout int
    retries int
}
type Connection struct{}
func NewStuffClient(conn Connection, opts ...StuffClientOption) StuffClient {
    client := defaultStuffClient
    for _, o := range opts {
        o(&client)
    }

    client.conn = conn
    return client
}
func (c stuffClient) DoStuff() error {
    return nil
}

可以在这里尝试一下. 在我们的示例中, 我们只是直接将配置应用到我们的结构中, 在中间有一个额外的配置结构是没有意义的. 但是请注意, 在许多情况下, 您可能仍然想使用前面示例中的 config 结构体; 例如, 如果你的构造器使用配置选项来执行一些操作, 但不把它们存储到结构中, 或者传递到其他地方. 配置结构变体是更通用的实现.

感谢 Rob Pike 和 Dave Cheney 推广这种设计模式.

Cassandra

Cassandra 的数据模型是基于列族(Column Family)的四维或五维模型。

多维的概念是可以相互嵌套, 如: 三维可以包含多个二维, 简单来说就是迭代

Cassandra 写入数据流程:

1. 记录日志 CommitLog
2. 写入内存 Memtable
3. 写入磁盘 SSTable

安装

go to http://cassandra.apache.org/

建议 docker 安装:

docker pull cassandra

需求:

  1. 放大一张 PNG图片

方法: 利用 canvas

<html>

<head>
  <title>如何放大png图片</title>
</head>
<body>


<canvas id="canvas" width="128px" height="128px">
</canvas>


<select id="iselect">
  <option value="128" >128</option>
  <option value="48" >48</option>
  <option value="16" >16</option>
</select>


<!-- <a id="download" href="JavaScript:void(0);">点击下载</a> -->
<script type="text/javascript">

let flay = function(){
  var canvas = document.getElementById('canvas');
  var ctx = canvas.getContext('2d');

  var data = `<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 48 48" version="1.1">
<g id="surface1">
<path style=" fill:#FFC107;" d="M 22.976563 23 L 6 23 L 6 6 L 23 6 Z "></path>
<path style=" fill:#7CB342;" d="M 6 25 L 23 25 L 23 42 L 6 42 Z "></path>
<path style=" fill:#2196F3;" d="M 41.976563 23 L 25 23 L 25 6 L 42 6 Z "></path>
<path style=" fill:#1565C0;" d="M 25 25 L 42 25 L 42 42 L 25 42 Z "></path>
<path style=" fill:#FFF9C4;" d="M 17 11 C 17 12.105469 17.894531 13 18.996094 13 C 20.105469 13 21 12.105469 21 11 C 21 9.894531 20.105469 9 18.996094 9 C 17.894531 9 17 9.894531 17 11 "></path>
<path style=" fill:#D85700;" d="M 13 12 L 7 20 L 19 20 Z "></path>
<path style=" fill:#EF7E03;" d="M 18 15 L 13.875 20 L 22 20 Z "></path>
<path style=" fill:#FFFFFF;" d="M 12.488281 29.519531 C 12.488281 28.414063 13.386719 27.519531 14.5 27.519531 C 15.613281 27.519531 16.515625 28.414063 16.515625 29.519531 C 16.515625 30.625 14.5 33.519531 14.5 33.519531 C 14.5 33.519531 12.488281 30.625 12.488281 29.519531 "></path>
<path style=" fill:#FFFFFF;" d="M 16.515625 37.519531 C 16.515625 38.628906 15.613281 39.519531 14.5 39.519531 C 13.386719 39.519531 12.488281 38.628906 12.488281 37.519531 C 12.488281 36.414063 14.5 33.519531 14.5 33.519531 C 14.5 33.519531 16.515625 36.414063 16.515625 37.519531 "></path>
<path style=" fill:#FFFFFF;" d="M 10.007813 33.253906 C 9.046875 32.695313 8.714844 31.476563 9.269531 30.519531 C 9.824219 29.5625 11.058594 29.234375 12.019531 29.789063 C 12.984375 30.34375 14.5 33.519531 14.5 33.519531 C 14.5 33.519531 10.972656 33.804688 10.007813 33.253906 "></path>
<path style=" fill:#FFFFFF;" d="M 18.992188 33.785156 C 19.957031 34.339844 20.285156 35.5625 19.730469 36.515625 C 19.175781 37.476563 17.941406 37.804688 16.980469 37.25 C 16.015625 36.699219 14.5 33.519531 14.5 33.519531 C 14.5 33.519531 18.027344 33.234375 18.992188 33.785156 "></path>
<path style=" fill:#FFFFFF;" d="M 18.992188 33.253906 C 19.957031 32.695313 20.285156 31.476563 19.730469 30.519531 C 19.175781 29.5625 17.941406 29.234375 16.980469 29.789063 C 16.015625 30.339844 14.5 33.519531 14.5 33.519531 C 14.5 33.519531 18.027344 33.804688 18.992188 33.253906 "></path>
<path style=" fill:#FFFFFF;" d="M 10.007813 33.785156 C 9.046875 34.339844 8.714844 35.5625 9.269531 36.515625 C 9.824219 37.476563 11.058594 37.804688 12.019531 37.25 C 12.984375 36.695313 14.5 33.519531 14.5 33.519531 C 14.5 33.519531 10.972656 33.234375 10.007813 33.785156 "></path>
<path style=" fill:#FFC107;" d="M 16.5 33.597656 C 16.5 34.699219 15.605469 35.59375 14.5 35.59375 C 13.394531 35.59375 12.5 34.699219 12.5 33.597656 C 12.5 32.488281 13.394531 31.59375 14.5 31.59375 C 15.605469 31.59375 16.5 32.488281 16.5 33.597656 "></path>
<path style=" fill:#FFC107;" d="M 29 29 L 38 29 L 38 38 L 29 38 Z "></path>
<path style=" fill:#FFC107;" d="M 33.5 27.140625 L 39.863281 33.503906 L 33.5 39.867188 L 27.136719 33.503906 Z "></path>
<path style=" fill:#FFF8E1;" d="M 31 33.5 C 31 34.882813 32.121094 36 33.5 36 C 34.882813 36 36 34.882813 36 33.5 C 36 32.117188 34.882813 31 33.5 31 C 32.121094 31 31 32.117188 31 33.5 "></path>
<path style=" fill:#FFF59D;" d="M 27 10 C 27 11.105469 27.894531 12 29 12 C 30.105469 12 31 11.105469 31 10 C 31 8.894531 30.105469 8 29 8 C 27.894531 8 27 8.894531 27 10 "></path>
<path style=" fill:#E3F2FD;" d="M 39 15 C 39 16.65625 37.65625 18 36 18 C 34.34375 18 33 16.65625 33 15 C 33 13.34375 34.34375 12 36 12 C 37.65625 12 39 13.34375 39 15 Z "></path>
<path style=" fill:#E3F2FD;" d="M 34.5 16 C 34.5 17.378906 33.378906 18.5 32 18.5 C 30.621094 18.5 29.5 17.378906 29.5 16 C 29.5 14.621094 30.621094 13.5 32 13.5 C 33.378906 13.5 34.5 14.621094 34.5 16 Z "></path>
<path style=" fill:#E3F2FD;" d="M 34.398438 20 C 33.238281 20 36.738281 15.847656 37.898438 15.847656 C 39.058594 15.847656 40 16.777344 40 17.925781 C 40 19.070313 39.058594 20 37.898438 20 C 36.738281 20 35.800781 20 34.398438 20 Z "></path>
<path style=" fill:#E3F2FD;" d="M 26.964844 17.925781 C 26.964844 16.777344 27.90625 15.847656 29.066406 15.847656 C 32.566406 15.847656 33.726563 20 32.566406 20 C 31.164063 20 30.226563 20 29.066406 20 C 27.90625 20 26.964844 19.070313 26.964844 17.925781 Z "></path>
<path style=" fill:#E3F2FD;" d="M 37.398438 20 L 29 20 L 29 17.230469 L 37.398438 15.847656 Z "></path>
</g>
</svg>`;

  var DOMURL = window.URL || window.webkitURL || window;
  var img = new Image();
  var svg = new Blob([data], {type: 'image/svg+xml'});
  var url = DOMURL.createObjectURL(svg);

  img.onload = function () {
    ctx.drawImage(img, 0, 0);
    DOMURL.revokeObjectURL(url);
    var png_img = canvas.toDataURL("image/png");
  }

  img.src = url;
  console.log(url);
}

// 下拉事件
var sel = document.getElementById('iselect');
sel.value = 128;
sel.addEventListener("change", function(sel){
  let val = this.options[this.options.selectedIndex].value;
  console.log(val);
  document.getElementById("canvas").width = val;
  document.getElementById("canvas").height = val;
  flay();
}, false);


 flay();
</script>
</body>
<html>

给个链接 svg