Mnesia——针对电信应用的健壮分布式DBMS

摘要：Mnesia DBMS是和持有数据的应用程序运行于同一个地址空间中，然而应用程序却不会破坏数据库的内容。这同时实现了快速访问和有效的容错性，而这两个要求通常是冲突的。这些是基于Mnesia所嵌入的Erlang编程语言的特性来实现的。

简介

电信系统中数据的管理有某些但不是所有的方面可以通过传统的DBMS（数据库管理系统）来解决。然而，在很多无间断系统中所必须的非常高容错性的要求之上，再结合DBMS必须运行于和应用程序一样的地址空间这个要求，以至我们又实现了一个全新的DBMS。本论文将描述这种叫做Mnesia的新DBMS的产生动机和他的设计思路。Mnesia是由编程语言Erlang来实现的，并与之密切相关，Erlang为实现可容错电信系统提供了必要的功能。Mnesia是一个特别为工业电信应用而打造的多用户分布式DBMS，使用了符号编程语言Erlang1进行编写，这门语言也是为同样目的而诞生。Mnesia尝试解决典型的电信系统中必需的所有数据管理问题——其中相当一部分特性一般在传统数据库中是找不到的。

在电信应用中，有一些和传统DBMS所提供的特性不同的需求。我们现在看到的用Erlang语言实现的应用需要混合很多由传统DBMS所不能满足的需求。我们在设计Mnesia的时候一直在考虑以下需求：

  1. 快速实时的键/值查找。
  2. 主要用于操作和维护的复杂非实时查询。
  3. 由于分布式应用而产生的分布的数据。
  4. 高度容错性。
  5. 可动态配置。
  6. 处理复杂的对象。

令Mnesia不同于其他DBMS的地方就在于它在设计时就是针对电信应用中出现的典型问题。因此，Mnesia结合了传统数据库的很多概念（如事务和查询）以及电信应用中数据管理的一些概念，如非常快的实时操作、可配置的容错级别（通过复制，Replication的方式）以及不停止或挂起系统的情况下就能重新配置系统。Mnesia还因为它和编程语言Erlang的紧密耦合而非常有意思，这样就相当于将Erlang变成了一种数据库编程语言。这带来了很多好处，首先就是完全消除了DBMS使用的数据格式和编程语言用于处理数据的格式两者之间的不匹配阻碍2。

当前Mnesia被用于Ericsson内部几乎所有基于Erlang的项目中，从小规模的原型项目到主流的交换机产品项目。

本论文剩下的部分如下组织：第二节是该DBMS的简明概述；第三节罗列了典型的DBMS的功能，并从电信的角度讨论了这些功能以及Mnesia是如何提供这些功能的；第四节包括一些性能测试；最后第五节作出总结。

Mnesia简要概述

Mnesia既是编程语言Erlang的扩展，也是一个Erlang应用程序。DBMS的组件如锁管理器、事务管理器、复制管理器、日志、主存储和二级内存存储、备份系统等等，这些都是由普通的Erlang程序实现的。然而，查询语言则被实现为Erlang实际语法的一部分，同时优化查询的编译器和求值器也都是普通的Erlang程序。Mnesia的数据模型是混合的类型：数据按“记录”（record）的表进行组织，类似关系数据库的表，但是记录的属性（包括键）可以是任意复杂的组合数据结构，如树、函数、闭包、代码等等。从这点上来说，Mnesia也可以定性为所谓的对象关系DBMS。比如，定义一个人员的记录：

-record(person, {name,            %% 原子，唯一键
                 data,            %% 未指定的组合结构数据
                 married_to,      %% 配偶的名字或未定义（undefined）
                 children}).      %% 孩子的列表

有了这个定义，就可以用以下的Erlang语法创建人员记录的实例：

X = #person{name = klacke,
            data = {male, 36, 971191},
            married_to = eva,
            children = [marten, maja, klara]}.

它将变量X绑定到一个新记录。数据字段绑定到一个有三部分的元组{male, 36, 971191}。这便是复杂对象的一个例子，Mnesia对属性的复杂性没有任何限制，我们甚至可以将函数对象作为属性值。变量X只是一个纯粹的Erlang值（term），若要把它插入到数据库中，必须写成：

mnesia:write(X)

一系列Mnesia操作可以作为一个原子事务一起执行。要让Mnesia执行一个事务，程序员必须首先构建一个函数对象，然后将其传送给Mnesia系统——类似于3。举一个例子来解释，假设我们想写一个Erlang函数divorce(Name)，它接受一个人名，从数据库中找出这个人，并将这个人和这个人的配偶的married_to字段设为未定义undefined：

divorce(Name) ->
    F = fun() ->
        case mnesia:read(Name) of
            [] ->
                mnesia:abort(no_such_person);
            Pers ->
                Partner = mnesia:read(Pers#person.married_to),
                mnesia:write(Pers#person{married_to = undefined}),
                mnesia:write(Partner#person{married_to = undefined})
            end
        end,
    mnesia:transaction(F).

divorce/1 函数由两条语句组成，第一条语句F = ...用于创建一个函数对象，它并没有执行什么东西，仅仅是构造了一个匿名函数。第二条语句将这个函数交给Mnesia系统，让其在一个事务的上下文中执行此函数，这遵循传统的事务语义。

实际的函数F首先执行一个读操作，用于查找给定名字Name的人，然后它执行第二个读操作以找到前者的配偶，最后执行两个写操作，将两条married_to都已设为undefined的新记录写入到数据库中。这两个写操作将覆盖旧值。函数divorce/1将事务的值作为返回值，要么是{aborted, Reason} 、要么是{atomic, Value} ，取决于事务是是否被终止。

Mnesia中的查询由列表理解（list comprehension）语法表达4。用于查找所有生了超过X个孩子的人的名字的查询可以如下所示：

query [P.name || P < table(person),
                length(P.children) > X]
end

这段话要这样读：构造一个P.name的列表，其中P从人表中得到，而且每个P的孩子列表的长度必须超过X。甚至可以将用户定义的谓词混合到查询中，这样也很自然。假设有这样一个函数：

maturep({Sex, Age, Phone}) when Age > 30 ->
     true;
maturep({Sex, Age, Phone}) ->
     false;

然后这个查询

query [P.name || P <- table(person),
                    maturep(P.data),
                    length(P.children) > X]
end

它将提取出所有有超过X个小孩并且data字段的第二个元素的值大于30的所有的人的名字。还可以用类似Datalog5这样的嵌入式逻辑语言的方式定义规则。如果我们定义规则：

oldies(Name) :-
    P <- table(person),
    maturep(P.data),
    Name = P.name.

这样就定义了一个规则，它就可以起到一个虚拟的表的作用，然后应用程序就可以存取虚拟表oldies。虚拟的oldies表包含一个实际的人员表的子集。这类似于关系数据库中视图的概念，但是功能更为强大。查询语句由查询优化编译器负责编译，该编译器已经集成到普通的Erlang编译器中了。

表可以被复制到多个站点（或者节点）上。节点网络可以是异构网络。通过复制（Replication）机制，我们可以构建出容错性系统。对数据库表的访问是位置透明的，也就是说，程序无需了解数据确切的位置。一张表有一个唯一的名称和相关的属性，每张表附属的特性如下表所示:

  • type 控制表是否包含set或者bag语义。set中键值是唯一的，而bag可以包含有着相同的键值的多个对象。
  • ram_copies 仅将表副本保持在内存中的Mnesia节点的列表。
  • disc_copies Mnesia节点的列表，其中的表副本完全保持在内存中，但对表的所有更新操作将都记录到磁盘中。
  • disc_only_copies 仅将表副本保持在磁盘上的Mnesia节点的列表。显然这些副本要比内存中的副本慢很多。
  • index 一个列表，用于指定记录中哪些属性需要做索引。所有的记录总是自动按照主键建立索引。
  • snmp 控制是否可以通过SNMP（Simple Network Management Protocol）协议6操作该表。

所有表的描述信息都被存在数据库结构（schema）中，Mnesia提供了多种用于动态的操作结构的函数：对表的创建、移动、复制、改变、销毁等等。并且，所有这些系统活动都在后台执行，这样，即使系统本身正在进行改变，也允许应用程序照常利用系统。

备份可以由整个分布式系统来构造，这些备份将作为应急备份（fallback）。这意味着，一旦系统要崩溃了，数据库可以从应急备份中自动重建。

DBMS特性讨论

不同的DBMS有着不同的特性和特征。本节列出了不同的DBMS特点，以及讨论这些性质在我们的目标应用领域中的重要性和必要性。

复杂值

在DBMS中有效并自然地操作复杂值（如列表、集合、树等）的能力可能是对电信DBMS而言最重要的特性了。用于处理通信量的电信应用通常由到达系统的外部刺激(stimuli)所驱动。当这样一个刺激以PDU（Protocol Data Unit，协议数据单元）的形式到达系统时，对该PDU进行解码，必须进行一系列相应的操作。当PDU被解码后，系统通常需要获取一些数据对象，可能是某个用户记录，用于决定应该执行哪些操作以响应收到的PDU。许多电信系统中，数据管理系统的最重要特性就是这种查找要非常高效。同时DBMS还要能让数据以一种只要一次查找操作就能访问到相关数据的方式进行结构化和储存。这让使用传统关系数据库对电信系统的建模更加困难。以第三范式（甚至第一范式）组织电信数据通常不太可能。

这也是为何电信产业更多地关注于面向对象数据库系统的原因之一，相对于关系数据库，面向对象数据库允许数据以更灵活的方式进行组织。因而Mnesia允许用户在数据库中使用任意复杂的对象作为属性值和键值。

数据格式和地址空间

很多数据库使用一种内部的、语言独立的格式存储数据。由于前面提到的快速查找的需求，这对于电信系统来说是最不幸的事。很多面向对象DBMS与某种编程语言如C++或Smalltalk紧密耦合。这种在数据库中操作常规编程语言对象的能力，消除了不匹配带来的开销。这不仅使得DBMS的操作更加容易，而且还带来了实现非常高效查找的机会，因为依靠使用的程序语言，一个查找操作便能立即返回一个对象的指针。比如说，我们想通过数据库表的形式实现一个路由表，对要传递的包每次都将路由数据从外部DBMS格式来回转换是不现实的。此外，执行任何上下文切换并在为每个包在另一个地址空间的进程中搜索相关数据，也是不现实的。这就直接排除了所有不能直接链接到应用系统地址空间的DBMS，以及虽然链接到应用系统地址空间却使用一种语言独立的格式存储数据的所有DBMS。

让应用系统与DBMS运行在同一地址空间的最大缺点是，如果应用系统由于程序的错误崩溃了，DBMS可能来不及在终止之前将重要数据存储到二级存储器中。这意味着整个DBMS必须在再次启动之前进行恢复。这通常是一个非常耗时的过程，而在电信系统中宕机时间必须尽可能短。我们却避免了这个问题，因为应用系统以及DBMS都是由Erlang实现的。一个Erlang应用系统不会因为崩溃而影响DBMS。虽然应用系统和DBMS运行在同一地址空间内，但是Erlang自身让应用程序的崩溃不可能影响到另一个应用程序。Erlang进程有着运行在同一地址空间的效率优势，同时它们完全没有直接读写其它进程内存的可能性。

容错性

许多电信应用系统都是不间断系统。即便某些硬件或软件发生错误，这种系统也必须能持续提供服务。这个不仅对DBMS，也对电信应用系统自身提出了新的要求。它影响到了整个应用系统的设计，DBMS必须为应用系统设计者提供一种能设计足够容错性系统的机制。Mnesia所提供的这种机制是将一张数据库表复制到多个节点上。一张Mnesia表的所有副本都是等同的，所以在DBMS这一级别上没有主表和备用副本的概念。如果对某张表进行复制，每个事务中的所有的写操作都会被应用到所有副本上。如果某些副本不可访问，写操作仍能成功执行，而那些漏掉的副本将在它们恢复后进行更新。这一机制使得我们可以设计一种通过在不同地理位置上的系统之间协作提供一个连续运行的不间断系统。许多其它的高容错性系统如ClustRa7，也通过这种复制的方式来提供容错能力。然而，它们并没有和应用系统在同一地址空间内执行的能力。

Mnesia也能从完全的灾难中进行部分恢复。所有写入磁盘的对象能使用一种能够安全地与垃圾区分开来的方式进行了编码。这就能通过扫描一个受损的或者崩溃了的磁盘或文件系统并从中获取数据。

分布与位置透明

Mnesia是一个真正的分布式DBMS，数据能被复制和远程存储。在这样的一个环境中，DBMS程序员无需确切了解数据的位置就能对其访问是非常重要的。也就是说，数据的位置透明是非常重要的。另一方面，因为毫无疑问远程访问数据非常昂贵，所以也需要应用系统程序员能明确的找到位置信息，这样才能在数据所在的位置执行程序。因此，我们需要能同时提供位置透明和明确定位数据位置的能力。不同的应用有着不同的需求。

仅使用数据库表的名字的Mnesia应用系统，无需考虑表的位置也能运作。系统记录了数据都复制到了哪里。然而，它也能让Mnesia程序员通过系统查询到表的位置，然后远程执行代码。将代码发送到远程站点上或者确保代码已经在远端被加载都能达到目的。

事务和ACID

DBMS都有ACID特性，原子性、一致性、隔离性和持久性（Atomicity, Consistency, Isolation and Durability）。这些特性通过Mnesia中的事务、预写日志（write-ahead logging）和恢复（recovery）实现。大部分Mnesia事务包含了一系列仅在内存中（可以是复制的）的数据表上的操作。这些事务完全不与磁盘存储系统打交道，这样对这些事务来说持久性特性没有实现。在电信系统中事务语义是必须的，一个例子就是当我们给系统添加一个新用户。当进行此操作时，系统中会对一些资源进行分配，同时将一些数据对象会写入到系统内存中，所有这些操作必须作为一个原子动作执行，这是非常重要的。否则这个系统最后就会出现不一致的情况，同时可能某些资源没有被释放。

绕过事务管理器的能力

事务的开销相当高，对通信量处理系统的某些部分来说，通过事务系统访问数据是绝对不可行的。因此，一个适合电信系统的DBMS必须能够同时支持：1.由一系列数据库操作组成的原子事务；2.以及对同一数据的非常轻量级的锁定。通信量处理系统包含一定数量的表。其中很多表很少被写但经常被读。例如处理一个单独的呼叫比添加一个用户更常见，传递一个PDU包比修改路由表更常见。

当执行性能要求高的关键代码时，我们不想仅为了读个数据就将某个完整事务的开销强加上去。反过来说，比如，如果包传递代码从一个路由表中读取路由信息的时候，路由表同时正在被更新，某些数据包由于访问冲突而丢失了，这也是可以接受的。这里所需的只是非常轻量级的锁定保护，这样应用系统进程可以访问数据表并确保每个读取了的数据对象不会由于并发的写操作而被篡改。 Mnesia通过所谓的脏接口（dirty interface）来支持这一特性。这就可以在没有事务保护的情况下对Mnesia表进行读、写和搜索操作。这些脏操作则是真正的实时DBMS操作：不管数据库有多大，这些操作都能在可预期的时间内完成。

查询

除了通信量的处理之外，电信系统还包含大量操作维护(O&M)代码。例如，当从交换机系统中删除一个用户时，我们需要在好几张表中搜索与该用户相关的数据，这就需要一个查询语言。操作和维护代码往往有如下特征：

  1. 它没有实时性要求或者要求非常低的。
  2. 它对大部分的通信量数据进行读取、搜索和操作。
  3. 在系统的代码量上这些代码占了很大的比例。
  4. 它难得被执行，这样就易受软件腐败影响因此容易错。

这样，(3)让O&M代码变小和(4)以声明方式以及可以自动适应表格布局或者网络拓扑的变化，就能成为在目标系统上执行并可以访问所有通信表的一个强大的查询语言。因为使用了一个编译优化器决定查询的执行顺序，O&M代码变得更高效了。

Mnesia查询语言基于列表理解。这个想法已经用在好几个其它的函数式DBMS中了，如8。列表理解的语法与Erlang语言完美的结合在了一起。

结构变更

Erlang语言对无须停止进程就能变更执行中的进程代码这方面有着丰富的支持。这使得无须停止系统而修改Erlang数据的布局和组织形式成为可能。这样，它能在运行时修改Mnesia的数据库结构而不必停止系统。由于Mnesia是打算用于不间断系统的，所有的系统活动如备份、更改结构、转储数据表到二级存储器以及拷贝副本都可以在后台运行，同时还能让应用系统依然能像平常一样访问和修改数据表。

一些实现细节

Mnesia完全由Erlang实现。Erlang编程环境被证明是实现分布式DBMS的理想工具，整个Mnesia的实现包括从底层存储管理到查询优化编译器的系统的各个方面，都很精炼，仅由大概2万行Erlang代码组成。

持久存储实现于底下操作系统的文件系统之上。这样的实现的坏处是磁盘操作的性能低，同时主要的好处是移植性好。由于Mnesia主要是作为一个内存DBMS，我们觉得移植性方面更重要。主内存中的表和索引采用线性散列列表（linear hash list）实现9，次存储表由具名文件实现。每个文件被组织成一个线性散列列表，他的散列桶的平均链长设得比较小。线性散列列表在查找操作上非常高效，插入操作的效率也不错。文件和表的大小可以动态地增长和收缩。每个文件的空间管理由伙伴算法（buddy algorithm）实现。

Mnesia锁管理器用到了许多传统技术。锁定是动态的，事务在需要时会请求一个锁。用了常规的两阶段锁定（twophase locking），防止死锁是通过传统的waitdie10。waitdie算法的时间戳通过由事物管理器在各个节点上维护的兰伯特时钟（Lamport clock）11得到。当一个事务重启后，就会维护它的兰伯特时钟会，这也让Mnesia可以与锁无关。锁管理器还实现了多粒度的锁定。当一个事务被提交时，事务管理器会采用传统的两阶段提交。

通过关系数据库技术的操作器12可以计算简单的查询，而递归的查询可以通过SLG13进行计算。因为Mnesia运行在分布式Erlang上，其实现被极大简化了。在分布式应用系统中，有许多彼此隔离的Erlang节点运行在（通常是）不同的机器上。分布式Eralng负责运行在不同节点上的进程间的通信。Erlang可以让分开的节点上的不同进程之间透明地进行通信。分布式Erlang还可以透明地跨越有着不同字节序（endianism）的不同机器，这样一个Mnesia系统就可以由一组异构的计算机系统组成。进程和节点很容易被其它节点上的进程启动、监视和停止。这消除了Mnesia中许多通信实现中的困难，也包括应用系统。

性能讨论

我们在本节提供了一些Mnesia系统上的测量，数据清楚的显示了：

  • 相对于脏接口，使用事务系统的代价是相当大的。我们认为这一现象的正确解释是：脏接口更快但不是说事务系统慢。
  • 复制的代价有点高。这是在预料之中的，因为测试中的计算机使用的局域网是由普通的共享介质 10 Mbit/sec以太网连接的。

测试中的计算机是三台运行了Solaris 2.5的Sun UltraSparcs。所有的事务是由一台167Mhz的UltraSparc负责初始化的，其它两台是143Mhz。

副本数量 1 2 3
divorce/1 1877 5009 13372
使用wread的divorce/1 1225 4703 12185
dirty divorce/1 181 592 1121
表1: 不同配置执行divorce/1函数的运行时间，单位：微秒（microseconds）

第一行的数据是第2节中的divorce/1函数运行的结果，第二行是我们用Mnesia函数wread/1取代函数中的read/1后的运行结果。该函数读取数据是通过设置一个写锁而不是读锁。如果我们预先知道接下来的操作是要将同一个对象写入的话，此函数更高效。这样锁就不必从读锁更新成写锁。最后一行的数据来自用脏函数读写复制表，这样就绕过了事务系统并使用了轻量级锁。

结论

如今有大量的DBMS可供选择，包括许多有效的商业系统以及无数的研究系统。貌似使用一个商业的DBMS会是更好的解决方案，但是如果考虑到第三节中提到的方方面面，还没有一个合适的商业DBMS可用。我们觉得我们的主要贡献在于：

  • 通过组合大量熟知的技术，实现了一个完整的分布式DBMS。许多研究组织只研究DBMS的某些方面，而我们实现了一个完全的分布式DBMS。很少有这样的系统。
  • 我们向大家展示了Erlang不仅适合电信系统而且也非常适合实现像Mnesia这样的DBMS系统。就我们了解，这是第一次在一门符号编程语言中实现了一个分布式DBMS。
  • 我们提供了一个全面的DBMS解决方案，涵盖了电信系统数据管理的所有——或至少很多——方面。

目前Mnesia系统已在Ericsson中被用于构建实际的软件产品，这说明Mnesia已经不再只是一个单纯的原型系统，它已经足够成熟可以贴上产品的标签了。该系统可在http://www.ericsson.se/erlang获取。

参考资料

  1. Armstrong, J. L., Williams, M. C., Wikstrom, C. and Virding, S. R., Con current Programming in Erlang, 2:nd ed. Prentice Hall (1995) ↩

  2. Copeland, G., Maier, D. Making Smalltalk a database system Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. pp. 316325. Boston 1984. ↩

  3. Faehndrich, M., Morrisett, G., Nettles, S., Wing, J. Extensions to Standard ML to Support Transactions ACM SIGPLAN Workshop on ML and its Applications, June 2021, 1992. ↩

  4. Trinder, P.W. and Wadler, P. List comprehensions and the Relational Cal culus Proceedings of the Glasgow 1988 Workshop on functional programming, Rothesay , August 1988, pp 115123. ↩

  5. Ullman, J. Principles of Database and KnowledgeBase Systems, vol 2. Computer Science press, 1989. ↩

  6. Case, K. McCloghrie, M. Rose, S. Waldbusser. Management Information Base for Version 2 of the Simple Network Management Protocol (SNMPv2), Jan, 1996. ↩

  7. Hvasshovd, SO., Torbjornsen, O., Bratsberg, S.E., Holager, P. The ClustRa telecom database: High availability, high throughput, and realtime response Proceedings of the 21st International Conference on Very Large Databases, Zurich, Switzerland, pp. 469477, September 1995. ↩

  8. Trinder, P.W. and Wadler, P. List comprehensions and the Relational Cal culus Proceedings of the Glasgow 1988 Workshop on functional programming, Rothesay , August 1988, pp 115123. ↩

  9. Larsson, PA Larsson. Dynamic Hash tables Communications of the ACM, 31(4), 1988 ↩

  10. Rosenkrantz, D.J., Stearns, R.E. and Lewis, P.M. System Level Concurrency Control for Distributed Databases ACM Transactions on Database Systems, 3(2):178198, June 1978. ↩

  11. Lamport, L. Time, clocks and the ordering of events i a distributed system ACM Transactions on Programming Languages and Systems, 21(1):558565, July 1878. ↩

  12. Goetz, G. Query Evaluation Techniques for Large Databases ACMCS 2(25):73170, June 1993. ↩

  13. Chen, A.W., Warren, D.S. Query Evaluation under the WellFounded Se mantics Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Sys. Whashington, 1993. ↩