Twitter Snowflake Algorithm [分布式自增ID算法Snowflake]
Snowflake算法是Twitter提出,为了快速生成全局唯一且总体有序的ID,且ID生成过程不依赖任何中间件,无网络通信[其性能每秒生成300w+]。
Snowflake算法是Twitter提出,为了快速生成全局唯一且总体有序的ID,且ID生成过程不依赖任何中间件,无网络通信[其性能每秒生成300w+]。
Write Amplification 写入放大,Write Amplification Factor写入放大系数。写放大系数的含义:当我们的host要求向ssd写入A大小的有效资料,而实际上由于flash的特性,我们真正写入flash的资料大小是B,那么B/A就是写放大系数。
数据库中的锁[lock]是用于并发控制[concurrency control]的重要机制,其本质是对特定数据的控制。一般来说,在应用了锁机制的数据库系统中,如果想要访问/修改任何一个数据,则一定是要先对该数据加锁,访问之后再释放锁。锁主要有两种形式,共享锁[shared lock]和排它锁[exclusive lock]。
数据库并发控制的一个重要概念就是Serializability[可串行化],先上两个教科书的解释
硬盘数据库就是数据库主体构建在硬盘上,相对的内存数据库是指数据库主体构建在内存中,两者各有优势。这里说的内存管理是指硬盘数据库的内存管理,因为内存数据库整个都在内存中其管理方式必然有着不同的设计。
Huffman code是由David Albert Huffman在MIT与其同学发明的一种用语数据压缩的编码方式。
除了最短路径[shortest path]问题,图的另一个经典问题是最小生成树。给定一个图[一般是无向图],有n个点及一些连接的边每个边上都有对应的权重[权重可以用来描述任何可以量化的因素],现在我们想要寻找一个子图能够将所有的点都链接起来[也就是说在这个子图内,任何两个节点可以直接或者间接连通],并且要求子图的权重最小。这个子图就是所谓的最小生成树,或者更准确的说最小权重生成数[最小生成树不是惟一的,一个图可能有多个不同的最小生成树,比如两条边的权重一样,选择任何一条都可以形成最小生成树]。