Shard (database architecture)

A database shard, or simply a shard, is a horizontal partition of data in a database or search engine. Each shard is held on a separate database server instance, to spread load.

Some data within a database remains present in all shards, but some appears only in a single shard. Each shard (or server) acts as the single source for this subset of data.

Database architecture

Horizontal partitioning is a database design principle whereby rows of a database table are held separately, rather than being split into columns (which is what normalization and vertical partitioning do, to differing extents). Each partition forms part of a shard, which may in turn be located on a separate database server or physical location.

There are numerous advantages to the horizontal partitioning approach. Since the tables are divided and distributed into multiple servers, the total number of rows in each table in each database is reduced. This reduces index size, which generally improves search performance. A database shard can be placed on separate hardware, and multiple shards can be placed on multiple machines. This enables a distribution of the database over a large number of machines, greatly improving performance. In addition, if the database shard is based on some real-world segmentation of the data (e.g., European customers v. American customers) then it may be possible to infer the appropriate shard membership easily and automatically, and query only the relevant shard.

Disadvantages include:

Main section: Disadvantages

  • A heavier reliance on the interconnection between servers.
  • Increased latency when querying, especially where more than one shard must be searched.
  • Data or indexes are often only sharded one way, so that some searches are optimal, and others are slow or impossible.
  • Issues of consistency and durability due to the more complex failure modes of a set of servers, which often result in systems making no guarantees about cross-shard consistency or durability.

In practice, sharding is complex. Although it has been done for a long time by hand-coding (especially where rows have an obvious grouping, as per the example above), this is often inflexible. There is a desire to support sharding automatically, both in terms of adding code support for it, and for identifying candidates to be sharded separately. Consistent hashing is a technique used in sharding to spread large loads across multiple smaller services and servers.

Where distributed computing is used to separate load between multiple servers (either for performance or reliability reasons), a shard approach may also be useful. Continue reading “Shard (database architecture)”

Cache synchronization strategies

Introduction

A system of record is the authoritative data source when information is scattered among various data providers. When we introduce a caching solution, we automatically duplicate our data. To avoid inconsistent reads and data integrity issues, it’s very important to synchronize the database and the cache (whenever a change occurs in the system).

There are various ways to keep the cache and the underlying database in sync and this article will present some of the most common cache synchronization strategies.

Cache-aside

The application code can manually manage both the database and the cache information. The application logic inspects the cache before hitting the database and it updates the cache after any database modification.

Cache Aside

Mixing caching management and application is not very appealing, especially if we have to repeat these steps in every data retrieval method. Leveraging an Aspect-Oriented caching interceptor can mitigate the cache leaking into the application code, but it doesn’t exonerate us from making sure that both the database and the cache are properly synchronized.

Read-through

Instead of managing both the database and the cache, we can simply delegate the database synchronization to the cache provider. All data interaction is, therefore, done through the cache abstraction layer. Continue reading “Cache synchronization strategies”

Cache-Aside pattern

Load data on demand into a cache from a data store. This can improve performance and also helps to maintain consistency between data held in the cache and data in the underlying data store.

Context and problem

Applications use a cache to improve repeated access to information held in a data store. However, it’s impractical to expect that cached data will always be completely consistent with the data in the data store. Applications should implement a strategy that helps to ensure that the data in the cache is as up-to-date as possible, but can also detect and handle situations that arise when the data in the cache has become stale.

Solution

Many commercial caching systems provide read-through and write-through/write-behind operations. In these systems, an application retrieves data by referencing the cache. If the data isn’t in the cache, it’s retrieved from the data store and added to the cache. Any modifications to data held in the cache are automatically written back to the data store as well.

For caches that don’t provide this functionality, it’s the responsibility of the applications that use the cache to maintain the data.

An application can emulate the functionality of read-through caching by implementing the cache-aside strategy. This strategy loads data into the cache on demand. The figure illustrates using the Cache-Aside pattern to store data in the cache.

Using the Cache-Aside pattern to store data in the cache

If an application updates information, it can follow the write-through strategy by making the modification to the data store, and by invalidating the corresponding item in the cache.

When the item is next required, using the cache-aside strategy will cause the updated data to be retrieved from the data store and added back into the cache. Continue reading “Cache-Aside pattern”

缓存和DB一致性问题

以下是从网络上摘取的一些缓存一致性方案,供参考。

产生原因

主要有两种情况,会导致缓存和 DB 的一致性问题:

  1. 并发的场景下,导致读取老的 DB 数据,更新到缓存中。
  2. 缓存和 DB 的操作,不在一个事务中,可能只有一个操作成功,而另一个操作失败,导致不一致。

当然,有一点我们要注意,缓存和 DB 的一致性,我们指的更多的是最终一致性。我们使用缓存只要是提高读操作的性能,真正在写操作的业务逻辑,还是以数据库为准。例如说,我们可能缓存用户钱包的余额在缓存中,在前端查询钱包余额时,读取缓存,在使用钱包余额时,读取数据库。

更新缓存的设计模式

1.Cache Aside Pattern(旁路缓存)

这是最常用最常用的pattern了。其具体逻辑如下:

  • 失效:应用程序先从cache取数据,没有得到,则从数据库中取数据,成功后,放到缓存中。
  • 命中:应用程序从cache中取数据,取到后返回。
  • 更新:先把数据存到数据库中,成功后,再让缓存失效。

一个是查询操作,一个是更新操作的并发,首先,没有了删除cache数据的操作了,而是先更新了数据库中的数据,此时,缓存依然有效,所以,并发的查询操作拿的是没有更新的数据,但是,更新操作马上让缓存的失效了,后续的查询操作再把数据从数据库中拉出来。而不会像文章开头的那个逻辑产生的问题,后续的查询操作一直都在取老的数据。

要么通过2PC或是Paxos协议保证一致性,要么就是拼命的降低并发时脏数据的概率,而Facebook使用了这个降低概率的玩法,因为2PC太慢,而Paxos太复杂。当然,最好还是为缓存设置上过期时间。

2.Read/Write Through Pattern

在上面的Cache Aside套路中,我们的应用代码需要维护两个数据存储,一个是缓存(Cache),一个是数据库(Repository)。所以,应用程序比较啰嗦。而Read/Write Through套路是把更新数据库(Repository)的操作由缓存自己代理了,所以,对于应用层来说,就简单很多了。可以理解为,应用认为后端就是一个单一的存储,而存储自己维护自己的Cache。

Read Through

Read Through 套路就是在查询操作中更新缓存,也就是说,当缓存失效的时候(过期或LRU换出),Cache Aside是由调用方负责把数据加载入缓存,而Read Through则用缓存服务自己来加载,从而对应用方是透明的。

Write Through

Write Through 套路和Read Through相仿,不过是在更新数据时发生。当有数据更新的时候,如果没有命中缓存,直接更新数据库,然后返回。如果命中了缓存,则更新缓存,然后再由Cache自己更新数据库(这是一个同步操作)

下图自来Wikipedia的Cache词条。其中的Memory你可以理解为就是我们例子里的数据库。

3.Write Behind Caching Pattern

Write Behind 又叫 Write Back。write back就是Linux文件系统的Page Cache的算法

Write Back套路,一句说就是,在更新数据的时候,只更新缓存,不更新数据库,而我们的缓存会异步地批量更新数据库。

这个设计的好处就是让数据的I/O操作飞快无比(因为直接操作内存嘛 ),因为异步,write back还可以合并对同一个数据的多次操作,所以性能的提高是相当可观的。

但是,其带来的问题是,数据不是强一致性的,而且可能会丢失(我们知道Unix/Linux非正常关机会导致数据丢失,就是因为这个事)。在软件设计上,我们基本上不可能做出一个没有缺陷的设计,就像算法设计中的时间换空间,空间换时间一个道理,有时候,强一致性和高性能,高可用和高性性是有冲突的。软件设计从来都是取舍Trade-Off。

另外,Write Back实现逻辑比较复杂,因为他需要track有哪数据是被更新了的,需要刷到持久层上。操作系统的write back会在仅当这个cache需要失效的时候,才会被真正持久起来,比如,内存不够了,或是进程退出了等情况,这又叫lazy write。

在wikipedia上有一张write back的流程图,基本逻辑如下:

参照:左耳朵耗子《缓存更新的套路》 Continue reading “缓存和DB一致性问题”

代理模式 (Proxy Pattern)-结构型模式第四篇

过去的大半年时间,日子过的忙忙碌碌!今天奉献一篇设计模式系列的新文章,挑选再三,始终觉得Proxy模式是很好的选择,Let’s Go!

定义:

Proxy模式,简言之,它像一个代理人,或者说像一个包装盒,它用来封装、控制背后真实的对象,自己可以独立提供被外界访问的能力,它与背后真实的对象派生于相同的接口,但代理人通常会将对真实对象的调用更加简单化,以便外界更加容易的使用。在客户端看来,自己似乎是直接在操作被代理的真实对象,但事实是,所有的操作都经过代理人的封装、控制、包装,而这些额外的操作,对于客户端来说,似乎是透明的。

应用:

Proxy模式,透明了对原始真实对象的调用,使我们有能力在调用真实对象的前后执行额外的动作,所以我们可以将一些与业务无关的软件基础功能添加在前后的额外动作中。比如Exception Handling, Logging, Caching等。

倘若再结合一些DI/IoC容器、编译器,有能力动态或静态地创建真实对象的代理,便无须手动去编写代理类,此时若配合一些编程语言的语法元数据(比如Java 中的@Attribute,C#中的[Attribute]),便可以在调用真实对象的方法前后执行额外的动作(通常可以称之为Interceptor 或Filter),这便初步实现了AOP编程。

UML:

Proxy UML
UML

Continue reading “代理模式 (Proxy Pattern)-结构型模式第四篇”

适配器模式 (Adapter Pattern)-结构型模式第三篇

祖国母亲生病了,一场突如其来的新冠病毒让这个古老的中华民族正在经历一场全民参与、没有硝烟、却生离死别的战争。每每看到抖音里的那些感人场景虽然不至于声泪俱下,却也是感慨万千、悲愤不已。大家现在都蛰伏在家,等待时机成熟破茧化蝶。相信这个春节在很多人的记忆里永远再也无法抹去,只希望所有人都安好!岁岁平安!

想起抖音里某位才人拍摄的一段视频,视频里这位仁兄使用女用卫生巾夹在普通一次性口罩中混合使用,以提高过滤功效。感叹一句,此乃神人也,有才,不得不佩服!笑归笑,这里不禁想起了设计模式中一个称之谓适配器(Adapter)的模式,所谓Adapter模式简言之,适配器能够使原本两个不兼容的接口能够协同工作。这位才人他没有将卫生巾直接戴在嘴上、卡在脸上(那可不适配),而是通过一个一次性口罩进行了转换、隐藏、适配,然后交由一次性口罩来担负起对外的形象任务,抽象一点的说其实这也算是一个适配器模式的应用:)

好吧,让我们来正式认识一下Adapter模式吧! Continue reading “适配器模式 (Adapter Pattern)-结构型模式第三篇”

组合模式 (Composite Pattern)-结构型模式第二篇

静悄悄中时间飞逝,感叹一句最近TMD真忙真累,好在天生坚强性格阳光,不吹不黑,下面开始讲结构型模式(Structural patterns)的第2篇,Composite Pattern,中文称之为组合或复合模式。

定义:

Composite模式,能够灵活地实现循环、递归、部分-整体类的结构,使外部世界能够以一致的方式处理单体或集合。

解决的问题:

  1. 就像定义中所提及的那样,如何使客户端能够以一致的方式去访问某个单体或者集合,以使结构更加简洁
  2. 如何优雅的表达一个树形结构

怎么去解决(包含叶子Leaf的实现方式):

  1. 通过定义一个接口代表集合与个体所拥有的相同属性与行为,如IComponent
  2. 通过定义一个类Composite,它继承自IComponent,同时通过组合的方式它拥有一个名称为Components的属性,它代表着一个IComponent集合
  3. Composite有能力将一个实现了IComponent接口的对象加入到Components中
  4. 对于Composite的任何请求,都会被重定向到属性Components中的每个个体分别去执行
  5. 通过定义一个类Leaf,它继承自IComponent,代表着不可再分割的个体

举个栗子,在一个树状结构中,树杆、树枝、树叉皆由Composite来表示,而Leaf代表的是末端的每片树叶。

怎么去解决(进一步抽象):

通过分析我们能够发现在上面的解决方式中,如果有能力分辨一个IComponent是树杆还是树叶,便可以将Composite和Leaf合并为一个类型,于是我们为IComponent引入一个新的属性HasChild,并且给它换一个更贴切的名字INode,如果HasChild为True,则代表它是Composite,反之则代表它是Leaf Continue reading “组合模式 (Composite Pattern)-结构型模式第二篇”

装饰者模式 (Decorator Pattern)-结构型模式第一篇

本篇是结构型模式(Structural patterns)的第一篇,之所以选择Decorator模式第一个出场,是由于抓揪随机的结果。Decorator模式能够为行为带来灵活的组合,减少子类的数量,希望文章能够给大家带来一点帮助。

定义:

Decorator模式,能够将行为动态地添加到一个类型实例,而不会影响其它的实例。

解决的问题:

  1. 如何在运行时给一个对象添加新的行为
  2. 如何减少子类的数量
    1. 我们知道通过新建一个子类,也能够为类型添加新的行为,但是它存在一个明显的缺陷:随着新行为数目的不断增加,需要增加更多数目的子类,并且行为之间无法组合使用

怎么去解决:

  1. 通过定义一个接口代表原始对象本身,如IComponent
  2. 通过定义一个接口IDecorator,它继承自IComponent,同时通过组合的方式它拥有IComponent
  3. 对于IDecorator的任何请求,都会被重定向到IComponent,并且在重定向前后我们有能力添加新的行为

UML:


Continue reading “装饰者模式 (Decorator Pattern)-结构型模式第一篇”

原型模式(Prototype Pattern)-创建型模式第五篇

距离发布上篇软件设计模式文章《建造者模式》稍稍地已经过去两个多月,今天来谈一下第五个创建型模式,这也将是最后一个创建型模式——原型模式(Prototype Pattern)。

定义:

Prototype模式,通过将对象自身进行复制来创建新的对象。多么简单的定义,该模式也很简单。

解决的问题:

  1. 在运行时如何动态创建一个对象的副本

怎么去解决:

  1. 通过定义一个含有Clone方法的Prototype接口
  2. 具体的实现类通过继承Prototype接口来创建自身的复制品

UML:

Continue reading “原型模式(Prototype Pattern)-创建型模式第五篇”

建造者模式(Builder Pattern)-创建型模式第四篇

也许得写一个段落放在文章的开头才会显得整篇没那么单调,我想写些什么,但指头落下的那一刻便忘了。简言之,设计模式犹如人生。好吧,也许这就算一个简单的开头,请让我们来看今天的主角,建造者模式(Builder Pattern),我不确定中文称它建造者模式是否准确,偶尔也会看到有人称其构建者或生成器模式。

定义:

Builder模式,通过将对象的构造过程与其本身分离开来,以简化复杂对象的创建过程,并且能够实现相同的构造过程可以创建不同的对象。

解决的问题:

  1. 如何通过简单的方式创建一个复杂的对象
  2. 如何通过相同的过程来创建类的不同实例

怎么去解决:

  1. 在一个独立的Builder对象中去创建和组装复杂对象的各个部分
  2. 通过对Builder的抽象,在创建复杂对象的过程中委托给具有相同接口的不同Builder实现,以达到相同的过程创建不同的对象

UML:

Continue reading “建造者模式(Builder Pattern)-创建型模式第四篇”