Algorithm

63. 不同路徑 II

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {
        return 0
    }
    results := make([][]int, m)
    for i := 0; i < m; i++ {
        results[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 {
                results[i][j] = 1
                continue
            }
            if j == 0 {
                if obstacleGrid[i][j] == 0 {
                    results[i][j] = results[i-1][j]
                } else {
                    results[i][j] = 0
                }
                continue
            }
            if i == 0 {
                if obstacleGrid[i][j] == 0 {
                    results[i][j] = results[i][j-1]
                } else {
                    results[i][j] = 0
                }
                continue
            }
            if obstacleGrid[i][j] == 0 {
                results[i][j] = results[i][j-1] + results[i-1][j]
            } else {
                results[i][j] = 0
            }
        }
    }
    return results[m-1][n-1]
}

Review

Concurrency in Go: Channels and WaitGroups

TIP

限流的幾種實(shí)現(xiàn)方式

1. 分布式限流，所有機(jī)器實(shí)例通過(guò)對(duì)同一個(gè)redis key進(jìn)行incres操作來(lái)達(dá)到分布式限流的目的。優(yōu)點(diǎn)是限流操作精準(zhǔn)，不會(huì)有誤限情況。缺點(diǎn)是當(dāng)限流qps偏高之后，redis的讀寫(xiě)將會(huì)成為瓶頸。
2. 本地限流，設(shè)置一個(gè)整體限流值/機(jī)器實(shí)例數(shù)，然后將這個(gè)平均得到的限流值分發(fā)到每個(gè)機(jī)器實(shí)例上，每個(gè)機(jī)器實(shí)例上通過(guò)滑動(dòng)窗口實(shí)現(xiàn)本地限流。優(yōu)點(diǎn)是適合大qps限流場(chǎng)景，操作簡(jiǎn)單性能好。缺點(diǎn)是容易產(chǎn)生誤限（機(jī)器實(shí)例之間并不能保障完全負(fù)載均衡）。

Share

學(xué)習(xí)“redis設(shè)計(jì)與實(shí)現(xiàn)”

Redis 數(shù)據(jù)類型

為了讓基于類型的操作更加方便地執(zhí)行，Redis 創(chuàng)建了自己的類型系統(tǒng)。

對(duì)象處理機(jī)制

1. redis對(duì)于鍵所保存的值的類型（后簡(jiǎn)稱“鍵的類型” ），鍵能執(zhí)行的命令又各不相同Redis 必須讓每個(gè)鍵都帶有類型信息，使得程序可以檢查鍵的類型，并為它選擇合適的處理方式。
2. Redis 的每一種數(shù)據(jù)類型，比如字符串、列表、有序集，它們都擁有不只一種底層實(shí)現(xiàn)（Redis 內(nèi)部稱之為編碼，encoding），所以redis需要根據(jù)數(shù)據(jù)類型的不同編碼進(jìn)行多態(tài)處理。
   為了解決以上問(wèn)題，Redis 構(gòu)建了自己的類型系統(tǒng)，這個(gè)系統(tǒng)的主要功能包括：
   ? redisObject 對(duì)象。
   ? 基于 redisObject 對(duì)象的類型檢查。
   ? 基于 redisObject 對(duì)象的顯式多態(tài)函數(shù)。
   ? 對(duì) redisObject 進(jìn)行分配、共享和銷毀的機(jī)制。

redisObject 數(shù)據(jù)結(jié)構(gòu)，以及 Redis 的數(shù)據(jù)類型

typedef struct redisObject {
  // 類型
  unsigned type:4;
  // 對(duì)齊位
  unsigned notused:2;
  // 編碼方式
  unsigned encoding:4;
  // LRU 時(shí)間（相對(duì)于 server.lruclock）
  unsigned lru:22;
  // 引用計(jì)數(shù)
  int refcount;
  // 指向?qū)ο蟮闹?  void *ptr;
} robj;
// type的枚舉
#define REDIS_STRING 0 // 字符串
#define REDIS_LIST 1 // 列表
#define REDIS_SET 2 // 集合
#define REDIS_ZSET 3 // 有序集
#define REDIS_HASH 4 // 哈希表
// encoding枚舉
#define REDIS_ENCODING_RAW 0 // 編碼為字符串
#define REDIS_ENCODING_INT 1 // 編碼為整數(shù)
#define REDIS_ENCODING_HT 2 // 編碼為哈希表
#define REDIS_ENCODING_ZIPMAP 3 // 編碼為 zipmap
#define REDIS_ENCODING_LINKEDLIST 4 // 編碼為雙端鏈表
#define REDIS_ENCODING_ZIPLIST 5 // 編碼為壓縮列表
#define REDIS_ENCODING_INTSET 6 // 編碼為整數(shù)集合
#define REDIS_ENCODING_SKIPLIST 7 // 編碼為跳躍表

redis所有的數(shù)據(jù)類型以及對(duì)應(yīng)的編碼類型

redis_type_and_encoding.png

命令的類型檢查和多態(tài)

當(dāng)執(zhí)行一個(gè)處理數(shù)據(jù)類型的命令時(shí)，Redis 執(zhí)行以下步驟：

1. 根據(jù)給定 key ，在數(shù)據(jù)庫(kù)字典中查找和它相對(duì)應(yīng)的 redisObject ，如果沒(méi)找到，就返回NULL 。
2. 檢查 redisObject 的 type 屬性和執(zhí)行命令所需的類型是否相符，如果不相符，返回類型錯(cuò)誤。
3. 根據(jù) redisObject 的 encoding 屬性所指定的編碼，選擇合適的操作函數(shù)來(lái)處理底層的數(shù)據(jù)結(jié)構(gòu)。
4. 返回?cái)?shù)據(jù)結(jié)構(gòu)的操作結(jié)果作為命令的返回值。

對(duì)象共享

有一些對(duì)象在 Redis 中非常常見(jiàn)，比如命令的返回值 OK 、ERROR 、WRONGTYPE 等字符，另外，一些小范圍的整數(shù)，比如個(gè)位、十位、百位的整數(shù)都非常常見(jiàn)。Redis 在內(nèi)部使用了一個(gè) Flyweight 模式 ：通過(guò)預(yù)分配一些常見(jiàn)的值對(duì)象，并在多個(gè)數(shù)據(jù)結(jié)構(gòu)之間共享這些對(duì)象，程序避免了重復(fù)分配的麻煩，也節(jié)約了一些 CPU時(shí)間。個(gè)人理解就是一個(gè)全局不可變的常量共享，并通過(guò)指針到需要的時(shí)候獲取到相對(duì)應(yīng)的值。

引用計(jì)數(shù)以及對(duì)象的銷毀

為了及時(shí)對(duì)redisObject所占用的內(nèi)存進(jìn)行回收，Redis 的對(duì)象系統(tǒng)使用了引用計(jì)數(shù)技術(shù)來(lái)負(fù)責(zé)維持和銷毀對(duì)象（就是自己實(shí)現(xiàn)了一套GC），它的運(yùn)作機(jī)制如下：
? 每個(gè) redisObject 結(jié)構(gòu)都帶有一個(gè) refcount 屬性，指示這個(gè)對(duì)象被引用了多少次。
? 當(dāng)新創(chuàng)建一個(gè)對(duì)象時(shí)，它的 refcount 屬性被設(shè)置為 1 。
? 當(dāng)對(duì)一個(gè)對(duì)象進(jìn)行共享時(shí)，Redis 將這個(gè)對(duì)象的 refcount 增一。
? 當(dāng)使用完一個(gè)對(duì)象之后，或者取消對(duì)共享對(duì)象的引用之后，程序?qū)?duì)象的 refcount 減一。
? 當(dāng)對(duì)象的 refcount 降至 0 時(shí)，這個(gè) redisObject 結(jié)構(gòu)，以及它所引用的數(shù)據(jù)結(jié)構(gòu)的內(nèi)存，都會(huì)被釋放。

字符串

字符串編碼

字符串類型分別使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 兩種編碼：
? REDIS_ENCODING_INT 使用 long 類型來(lái)保存 long 類型值。
? REDIS_ENCODING_RAW 則使用 sdshdr 結(jié)構(gòu)來(lái)保存 sds （也即是 char* )、long long 、double 和 long double 類型值。

換句話來(lái)說(shuō)，在 Redis 中，只有能表示為 long 類型的值，才會(huì)以整數(shù)的形式保存，其他類型的整數(shù)、小數(shù)和字符串，都是用 sdshdr 結(jié)構(gòu)來(lái)保存。
新創(chuàng)建的字符串默認(rèn)使用 REDIS_ENCODING_RAW 編碼，在將字符串作為鍵或者值保存進(jìn)數(shù)據(jù)庫(kù)時(shí)，程序會(huì)嘗試將字符串轉(zhuǎn)為 REDIS_ENCODING_INT 編碼。