//SDS的定义如下（sds.h/sdshdr）：
struct sdshdr {
    int len;         // 记录buf数组中已使用字节的数量
    int free;        // 记录buf数组中未使用字节的数量
    char buf[];      // 字节数组，用于保存实际字符串
}

//每个链表节点使用一个listNode结构来表示，具体定义如(adlist.h/listNode)：
typedef struct listNode {
    struct listNode *prev;              // 前置节点
    struct listNode *next;              // 后置节点
    void *value;                        // 节点的值
} listNode;

//redis另外还使用了list结构来管理链表，以方便操作，具体定义如下(adlist.h/list)：

typedef struct list {
    listNode *head;                             // 表头节点
    listNode *tail;                             // 表尾结点
    void *(*dup)(void *ptr);                    // 节点值复制函数
    void (*free)(void *ptr);                    // 节点值释放函数
    int (*match)(void *ptr, void *key);         // 节点值对比函数
    unsigned int len;                           // 链表所包含的节点数量
} list;

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

下面进一步解释上表所述的不同之处：

开发方面 - 在这两种体系结构中，可以使用不同的编程语言和工具开发服务，从而将技术多样性带入开发团队。开发可以在多个团队中组织，但是在SOA中，每个团队都需要了解常见的通信机制。另一方面，使用微服务，服务可以独立于其他服务运行和部署。因此，频繁部署新版本的微服务或独立扩展服务会更容易。您可以在这里进一步阅读有关微服务的这些好处。

“上下文边界” - SOA鼓励组件的共享，而微服务尝试通过“上下文边界”来最小化共享。上下文边界是指以最小的依赖关系将组件及其数据耦合为单个单元。由于SOA依靠多个服务来完成业务请求，构建在SOA上的系统可能比微服务要慢。

通信 - 在SOA中，ESB可能成为影响整个系统的单一故障点。由于每个服务都通过ESB进行通信，如果其中一个服务变慢，可能会阻塞ESB并请求该服务。另一方面，微服务在容错方面要好得多。例如，如果一个微服务存在内存错误，那么只有该微服务会受到影响。所有其他微服务将继续定期处理请求。

互操作性 - SOA通过消息中间件组件促进了多种异构协议的使用。微服务试图通过减少集成选择的数量来简化架构模式。因此，如果您想要在异构环境中使用不同协议来集成多个系统，则需要考虑SOA。如果您的所有服务都可以通过相同的远程访问协议访问，那么微服务对您来说是一个更好的选择。

大小Size - 最后一点但并非最不重要的一点，SOA和微服务的主要区别在于规模和范围。微服务架构中的前缀“微”是指内部组件的粒度，意味着它们必须比SOA架构的服务往往要小得多。微服务中的服务组件通常有一个单一的目的，他们做得很好。另一方面，在SOA服务中通​​常包含更多的业务功能，并且通常将它们实现为完整的子系统。

长连接的适用场景也非常的广泛：
监控系统：后台硬件热插拔、LED、温度、电压发生变化等；
IM 应用：收发消息的操作；
即时报价系统：例如股市行情 push 等；
推送服务：各种 App 内置的 push 提醒服务；

SETNX key value

将 key 的值设为 value ，当且仅当 key 不存在。

若给定的 key 已经存在，则 SETNX 不做任何动作。

SETNX 是『SET if Not eXists』(如果不存在，则 SET)的简写。

可用版本：
>= 1.0.0
时间复杂度：
O(1)
返回值：
设置成功，返回 1 。
设置失败，返回 0 。

<?php
class DistributeLock {
	private $redis;
	
	public function __construct() {
		$this->redis = new Redis(); 
   		$this->redis->connect('127.0.0.1', 6379); 
   }
   
   /**
   	 * @param $key string 锁的key
   	 * @param $expire int 锁定的时长，单位秒
   	 * @return bool true：锁定成功；false：锁定失败
   	 */
	function lock($key, $expire) {
		try {
			if ($this->redis->setnx($key, 1) {
				$this->redis->expire($key, $expire);
				return true;
			}
		} catch (Exception $e) {
			$this->redis->del($key);
		}
		return false;
	}
	
	function unlock($key) {
		$this->redis->del($key);
	}
}

1. 获取开始时间
2. 去各个节点获取锁
3. 再次获取时间。
4. 计算获取锁的时间，检查获取锁的时间是否小于获取锁的时间。
5. 持有锁。

1. 分布式的锁具有一个自动释放的功能。锁的互斥性，只在过期时间之内有效，锁过期释放以后就会造成多个Client 持有锁。

2. RedLock 整个系统是建立在，一个在实际系统无法保证的系统模型上的。在这个例子中就是系统假设时间是同步且可信的。

首先在实际的系统中，从两个方面来看：

1. 系统暂停，网络延迟。
2. 系统的时间发生阶跃。
对于第一个问题。上文已经提到了，RedLock做了一些微小的工作，但是没办法完全避免。其他带有自动释放的分布式锁也没有办法。

第二个问题，Martin认为系统时间的阶跃主要来自两个方面：

1. 人为修改。
2. 从NTP服务收到了一个跳跃时时钟更新。

对于人为修改，能说啥呢？人要搞破坏没办法避免。

NTP受到一个阶跃时钟更新，对于这个问题，需要通过运维来保证。需要将阶跃的时间更新到服务器的时候，应当采取小步快跑的方式。多次修改，每次更新时间尽量小。

1. 锁即Zookeeper上的一个节点
2. 客户端A发起一个加锁请求，先会在你要加锁的node下搞一个临时顺序节点。
3. 如果创建的几点序号是1，则获得锁
4. 序号不是1，则监听上一个序号释放锁。
5. 释放锁即删除临时节点。

class Solution {
    private $list_path = [];
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        if(count($nums) == 0) {
            return [];
        }
        $this->backtrace($nums, 0);
        return $this->list_path;
    }

    function backtrace($nums, $start) {
        if ($start == count($nums)) {
                $this->list_path[] = $nums;
        }
        for($i=$start;$i<count($nums);$i++) {
            $this->swap($nums[$start], $nums[$i]);
            $this->backtrace($nums, $start+1);
            $this->swap($nums[$start], $nums[$i]);
        }
    }
    function swap(&$i, &$j) {
        $t = $i;
        $i = $j;
        $j = $t;
    }
}

class Solution {
    public $path = [];
    public $sums = [];
    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        $length = count($candidates);
        if ($length == 0) {
            return [];
        }
        sort($candidates);
        $this->dfs($candidates, 0, $target);
        return $this->sums;
    }

    function dfs($candidates, $start, $target) {
        if ($target == 0) {
            $this->sums[] = $this->path;
        }
        for($i = $start;$i<count($candidates) && ($target-$candidates[$i]>=0);$i++) {
            $this->path[] = $candidates[$i];
            $this->dfs($candidates, $i, $target-$candidates[$i]);
            array_pop($this->path);
        }
    }
}

class Solution {

    const ALPHA = [
        2 => 'abc',
        3 => 'def',
        4 => 'ghi',
        5 => 'jkl',
        6 => 'mno',
        7 => 'pqrs',
        8 => 'tuv',
        9 => 'wxyz',
    ];
    private $output = [];
    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
        if (strlen($digits) == 0) {
            return [];
        }
        $len = strlen($digits);
        $this->combine("", $digits);
        return $this->output;
    }

    function combine($combine, $digits) {
        if (strlen($digits) == 0) {
            array_push($this->output, $combine);
            return;
        }

        for($i=0;$i<strlen(self::ALPHA[$digits[0]]);$i++) {
            $letter = self::ALPHA[$digits[0]][$i];
            $this->combine($combine.$letter, substr($digits, 1));
        }
    }
   
}

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        $length = count($nums);
        $i = 0;
        for($j = 1;$j<$length;$j++) {
            if ($nums[$j] != $nums[$i]) {
                $i++;
                $nums[$i] = $nums[$j];
            }
        }
        return $i + 1;
    }
}

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n) {
        $slow = $fast = $head;
        while ($n>0) {
            $n--;
            $fast = $fast->next;
        }
        while($fast != null && $fast->next != null) {
            $fast = $fast->next;
            $slow = $slow->next;
        }
        if ($slow == $head && $fast == null) {
            return $head->next;
        }
        $slow->next = $slow->next->next;
        return $head;
    }
}

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        if (count($nums) < 3) {
            return [];
        }
        $res = [];
        sort($nums);
        $length = count($nums);
        
        for ($i = 0; $i < $length-2;$i++) {
            $start = $i+1;
            $end   = $length-1;
            if ($i>0&&$nums[$i]==$nums[$i-1]) {
                continue;
            }
            while ($start < $end) {
                if (($nums[$i] + $nums[$start] + $nums[$end]) == 0) {
                    $res[] = [$nums[$i], $nums[$start], $nums[$end]];
                    while($start<$end && $nums[$start] == $nums[$start+1]) {
                        $start++;
                    }
                    while($start<$end && $nums[$end] == $nums[$end-1]) {
                        $end--;
                    }
                    $start++;
                    $end--;
                } elseif (($nums[$i] + $nums[$start] + $nums[$end]) > 0) {
                    $end--;
                } else {
                    $start++;
                }
            } 
        }
        return $res;
    }

}

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

<?php
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target) {
        if ($nums == null || count($nums) == 0) {
            return -1;
        }
        $length = count($nums);
        $start = 0;
        $end = $length-1;        
        while ($start <= $end) {
            $mid = $start + round(($end-$start)/2);
            if ($nums[$end] == $target) {
                return $end;
            }
            if ($nums[$start] == $target) {
                return $start;
            }
            if ($nums[$mid] == $target) {
                return $mid;
            }
            if ($nums[$mid] > $nums[$end]) {
                if ($nums[$mid] > $target) {
                    if ($target > $nums[$end]) {
                        $end = $mid - 1;
                    } else {
                        $start = $mid + 1;
                    }
                } else {
                    $start = $mid + 1;
                }
            } else {
               if ($nums[$mid] > $target) {
                   $end = $mid - 1;
               } else {
                   if ($target < $nums[$end]) {
                       $start = $mid + 1;
                   } else {
                       $end = $mid - 1;
                   }
               }
            }
        }
        return -1;
    }
}

红黑树的五个性质：
一般的，红黑树(一棵自平衡的排序二叉树)，满足以下性质，即只有满足以下性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

一个m阶的B+树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

一个m阶的B树具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

struct _zend_array {
	zend_refcounted_h gc;
	union {
		struct {
			ZEND_ENDIAN_LOHI_4(
				zend_uchar    flags,
				zend_uchar    _unused,
				zend_uchar    nIteratorsCount,
				zend_uchar    _unused2)
		} v;
		uint32_t flags;
	} u;
	uint32_t          nTableMask;
	Bucket           *arData;
	uint32_t          nNumUsed;
	uint32_t          nNumOfElements;
	uint32_t          nTableSize;
	uint32_t          nInternalPointer;
	zend_long         nNextFreeElement;
	dtor_func_t       pDestructor;
};

/*
 * HashTable Data Layout
 * =====================
 *
 *                 +=============================+
 *                 | HT_HASH(ht, ht->nTableMask) |
 *                 | ...                         |
 *                 | HT_HASH(ht, -1)             |
 *                 +-----------------------------+
 * ht->arData ---> | Bucket[0]                   |
 *                 | ...                         |
 *                 | Bucket[ht->nTableSize-1]    |
 *                 +=============================+
 */

(Zend/zend.h)
#define IS_NULL		0
#define IS_LONG		1
#define IS_DOUBLE	2
#define IS_BOOL		3
#define IS_ARRAY	4
#define IS_OBJECT	5
#define IS_STRING	6
#define IS_RESOURCE	7
#define IS_CONSTANT	8
#define IS_CONSTANT_ARRAY	9