首页
精选文章LSM查看全文2006年，google发表论文《Bigtable: A Distributed Storage System for Structured Data》，文中提到了该存储的文件组织方式，日志结构合并树（Log Structured-Merge Tree）,后被简称为LSM。LSM因为写入的高性能和良好的适配性，目前在文件存储中广泛应用，例如Hbase，Cassandra, LevelDB, SQLite等。 LSM的重要组件有MemTable，SST文件，WAL等。 内存结构 不同于传统的面向页面的关系性数据库，LSM是日志结构型的存储引擎。 作为KV存储，根据Key快速定位Value数据的位置是至关重要的，解决检索问题有两个手段，一个是建立索引，一个是直接排序，LSM采用的是在内存排序的方式将数据变得有序，从而可以快速定位数据。内存中的数据称为Memtable。 在内存排序还有一个作用是可以将内存作为写操作的Buffer，定期刷新到持久化存储，从而减少对持久化存储的随机写压力，随机写因为涉及到磁盘寻址等问题，所以速度比较慢，通过在内存中提前排序把随机写转为顺序写，顺序写的情况下，可以充分利用磁盘的写入能力。 文件结构 内存的数据dump到硬盘上，dump出来的文件在LSM中称为sst文件，因为dump到文件系统的数据是在内存中排好顺序的，所以具有良好的检索能力。 但是这种批量写的问题随着时间的迁移也会出现问题，sst之间是没有顺序的，所以查询数据需要遍历所有的sst文件，随着sst文件的增加，查询性能会下降，LSM采用的解决方案是定期将sst合并的方式减少sst的数量。 WAL 因为LSM的数据是先写入缓存…Kafka查看全文消息队列中间件是分布式系统中重要的组件，主要解决应用耦合，异步消息，流量削锋等问题。实现高性能，高可用，可伸缩和最终一致性架构，是大型分布式系统不可缺少的中间件。kafka是apache旗下一款著名的消息队列。其最早由LinkedIn公司采用Scala语言开发，支持多分区，多副本，kafka以高吞吐，可水平扩展，支持流式数据处理等多种特性而被广泛使用。 kafka的体系概念有几个重要的术语。 Producer，生产者，也就是消息的发送方。 Consumer，消费者，连接kafka集群，接受消息，并进行业务逻辑处理。 Broker，服务节点，可以看作一个kafka实例。 Topic，是一个逻辑概念，Producer和Consumer都会关联特定的主题进行发送和消费。一个Topic还可以分为若干个分区，称为Partition，每个Partition对应不同的物理存储和日志文件。 存储设计 kafka的因为顺序写的特点，所以存储使用日志。每个分区副本下的日志文件会分为多个分段，LogSegment，每个LogSegment有一个日志文件和两个索引文件构成，两个索引文件分别是对偏移量和时间戳的索引。 延迟消息 kafka存在大量的延时操作，例如延时生产，延时消费，延时拉取等，kafka基于时间轮的概念实现此类需求。 时间轮是一个存储定时任务的环形队列，队列中每一项代表了该时间范围内需要触发的任务。 时间轮是可以复用的，因为定时任务可能延时较久，所以时间轮有多个级别。比如最小粒度的时间轮间隔时间为1ms，时间轮的格子为20个，则该时间轮可以表示的时间跨度为20ms，那么其上级时间轮的每个格子代表的时间跨度就是20ms…红黑树查看全文红黑树是一种含有红黑节点并能自平衡的二叉查找树，其具有良好的效率，查找、增加、删除等操作都可以在 O(logN) 时间内完成。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 都是用了红黑树。红黑树的特征如下： 每个节点要么是黑色，要么是红色。 根节点是黑色。 每个叶子节点（NIL）是黑色。 每个红色结点的两个子结点一定都是黑色。 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。该特征可以推出如果一个结点存在黑子结点，那么该结点肯定有两个子结点。 有序 如果树结构要实现查询功能，那么树结构一定是要求有序的。 二叉查找树（BST，binary search tree），就是在二叉树的基础上增加有序性，有序的二叉树可以用来快速的查找、删除、插入元素。 二叉树实现有序的方式是左子树节点的值都小于根节点的值，右子树节点的值都大于根节点值，这里的根节点不只特指树的根节点，包括所有的非叶子结点。 但是二叉查找树的缺点是数据可能会出现倾斜，例如构建树的过程中，结点是从小到大顺序传入的，树会退变为一个链表，查找元素的事件复杂度会从左右子树的高等相等时候的O（log(n)）变为O（n）。 平衡 如果树结构需要满足查找高效稳定，要求树结构一定是平衡的。平衡性是指对任意非叶子结点而言，其左子树和右子树的高度基本相同，最多相差一。 二叉平衡树（AVL），就是二叉查找树的基础上增加了平衡性。 二叉平衡树在插入或者删除节点的时候，需要维持树的平衡，实现的复杂度较高。 稳定 如果要满足树结构的增删效率，要求树结构在变化的时候尽量只影响局部… |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库精选内容 |
