第十四章 持久化

原文:Chapter 14 Persistence

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

在接下来的几个练习中,我们将返回到网页搜索引擎的构建。为了回顾,搜索引擎的组件是:

  • 抓取:我们需要一个程序,可以下载一个网页,解析它,并提取文本和任何其他页面的链接。
  • 索引:我们需要一个索引,可以查找检索项并找到包含它的页面。
  • 检索:我们需要一种方法,从索引中收集结果,并识别与检索项最相关的页面。

如果你做了练习 8.3,你使用 Java 映射实现了一个索引。在本练习中,我们将重新审视索引器,并创建一个新版本,将结果存储在数据库中。

如果你做了练习 7.4,你创建了一个爬虫,它跟踪它找到的第一个链接。在下一个练习中,我们将制作一个更通用的版本,将其查找到的每个链接存储在队列中,并对其进行排序。

然后,最后,你将处理检索问题。

在这些练习中,我提供较少的起始代码,你将做出更多的设计决策。这些练习也更加开放。我会提出一些最低限度的目标,你应该尝试实现它们,但如果你想挑战自己,有很多方法可以让你更深入。

现在,让我们开始编写一个新版本的索引器。

14.1 Redis

索引器的之前版本,将索引存储在两个数据结构中:TermCounter将检索词映射为网页上显示的次数,以及Index将检索词映射为出现的页面集合。

这些数据结构存储在正在运行的 Java 程序的内存中,这意味着当程序停止运行时,索引会丢失。仅在运行程序的内存中存储的数据称为“易失的”,因为程序结束时会消失。

在创建它的程序结束后,仍然存在的数据称为“持久的”。通常,存储在文件系统中的文件,以及存储在数据库中的数据是持久的。

使数据持久化的一种简单方法是,将其存储在文件中。在程序结束之前,它可以将其数据结构转换为 JSON 格式(http://thinkdast.com/json),然后将它们写入文件。当它再次启动时,它可以读取文件并重建数据结构。

但这个解决方案有几个问题:

  • 读取和写入大型数据结构(如 Web 索引)会很慢。
  • 整个数据结构可能不适合单个运行程序的内存。
  • 如果程序意外结束(例如,由于断电),则自程序上次启动以来所做的任何更改都将丢失。

一个更好的选择是提供持久存储的数据库,并且能够读取和写入数据库的部分,而无需读取和写入整个数据。

有多种数据库管理系统(DBMS)提供不同的功能。你可以在 http://thinkdast.com/database 阅读概述。

我为这个练习推荐的数据库是 Redis,它提供了类似于 Java 数据结构的持久数据结构。具体来说,它提供:

字符串列表,与 Java 的List类似。
哈希,类似于 Java 的Map
字符串集合,类似于 Java 的Set

译者注:另外还有类似于 Java 的LinkedHashSet的有序集合。

Redis 是一个“键值数据库”,这意味着它包含的数据结构(值)由唯一的字符串(键)标识。Redis 中的键与 Java 中的引用相同:它标识一个对象。我们稍后会看到一些例子。

14.2 Redis 客户端和服务端

Redis 通常运行为远程服务;其实它的名字代表“REmote DIctionary Server”(远程字典服务,字典其实就是映射)。为了使用 Redis,你必须在某处运行 Redis 服务器,然后使用 Redis 客户端连接到 Redis 服务器。有很多方法可用于设置服务器,也有许多你可以使用的客户端。对于这个练习,我建议:

不要自己安装和运行服务器,请考虑使用像 RedisToGo(http://thinkdast.com/redistogo)这样的服务,它在云主机运行 Redis。他们提供了一个免费的计划(配置),有足够的资源用于练习。
对于客户端,我推荐 Jedis,它是一个 Java 库,提供了使用 Redis 的类和方法。

以下是更详细的说明,以帮助你开始使用:

  • 在 RedisToGo 上创建一个帐号,网址为 http://thinkdast.com/redissign ,并选择所需的计划(可能是免费的起始计划)。
  • 创建一个“实例”,它是运行 Redis 服务器的虚拟机。如果你单击“实例”选项卡,你将看到你的新实例,由主机名和端口号标识。例如,我有一个名为dory-10534的实例。
  • 单击实例名称来访问配置页面。记下页面顶部附近的网址,如下所示:
    1. redis://redistogo:1234567feedfacebeefa1e1234567@dory.redistogo.com:10534

这个 URL 包含服务器的主机名称dory.redistogo.com,端口号10534和连接到服务器所需的密码,它是中间较长的字母数字的字符串。你将需要此信息进行下一步。

14.3 制作基于 Redis 的索引

在本书的仓库中,你将找到此练习的源文件:

  • JedisMaker.java包含连接到 Redis 服务器并运行几个 Jedis 方法的示例代码。
  • JedisIndex.java包含此练习的起始代码。
  • JedisIndexTest.java包含JedisIndex的测试代码。
  • WikiFetcher.java包含我们在以前的练习中看到的代码,用于阅读网页并使用jsoup进行解析。

你还将需要这些文件,你在以前的练习中碰到过:

Index.java使用 Java 数据结构实现索引。
TermCounter.java表示从检索项到其频率的映射。
WikiNodeIterable.java迭代jsoup生成的 DOM 树中的节点。

如果你有这些文件的有效版本,你可以使用它们进行此练习。如果你没有进行以前的练习,或者你对你的解决方案毫无信心,则可以从solutions文件夹复制我的解决方案。

第一步是使用 Jedis 连接到你的 Redis 服务器。JedisMaker.java展示了如何实现。它从文件读取你的 Redis 服务器的信息,连接到它并使用你的密码登录,然后返回一个可用于执行 Redis 操作的 Jedis 对象。

如果你打开JedisMaker.java,你应该看到JedisMaker类,它是一个帮助类,它提供静态方法make,它创建一个 Jedis 对象。一旦该对象认证完毕,你可以使用它来与你的 Redis 数据库进行通信。

JedisMaker从名为redis_url.txt的文件读取你的 Redis 服务器信息,你应该放在目录src/resources中:

  • 使用文本编辑器创建并编辑ThinkDataStructures/code/src/resources/redis_url.txt
  • 粘贴服务器的 URL。如果你使用的是 RedisToGo,则 URL 将如下所示:
    1. redis://redistogo:1234567feedfacebeefa1e1234567@dory.redistogo.com:10534

因为此文件包含你的 Redis 服务器的密码,你不应将此文件放在公共仓库中。为了帮助你避免意外避免这种情况,仓库包含.gitignore文件,使文件难以(但不是不可能)放入你的仓库。

现在运行ant build来编译源文件,以及ant JedisMaker来运行main中的示例代码:

  1. public static void main(String[] args) {
  2. Jedis jedis = make();
  3. // String
  4. jedis.set("mykey", "myvalue");
  5. String value = jedis.get("mykey");
  6. System.out.println("Got value: " + value);
  7. // Set
  8. jedis.sadd("myset", "element1", "element2", "element3");
  9. System.out.println("element2 is member: " +
  10. jedis.sismember("myset", "element2"));
  11. // List
  12. jedis.rpush("mylist", "element1", "element2", "element3");
  13. System.out.println("element at index 1: " +
  14. jedis.lindex("mylist", 1));
  15. // Hash
  16. jedis.hset("myhash", "word1", Integer.toString(2));
  17. jedis.hincrBy("myhash", "word2", 1);
  18. System.out.println("frequency of word1: " +
  19. jedis.hget("myhash", "word1"));
  20. System.out.println("frequency of word1: " +
  21. jedis.hget("myhash", "word2"));
  22. jedis.close();
  23. }

这个示例展示了数据类型和方法,你在这个练习中最可能使用它们。当你运行它时,输出应该是:

  1. Got value: myvalue
  2. element2 is member: true
  3. element at index 1: element2
  4. frequency of word1: 2
  5. frequency of word2: 1

下一节中我会解释代码的工作原理。

14.4 Redis 数据类型

Redis 基本上是一个从键到值的映射,键是字符串,值可以是字符串,也可以是几种数据类型之一。最基本的 Redis 数据类型是字符串。我将用斜体书写 Redis 类型,来区别于 Java 类型。

为了向数据库添加一个字符串,请使用jedis.set,类似于Map.put; 参数是新的键和相应的值。为了查找一个键并获取其值,请使用jedis.get

  1. jedis.set("mykey", "myvalue");
  2. String value = jedis.get("mykey");

在这个例子中,键是"mykey",值是"myvalue"

Redis 提供了一个集合结构,类似于 Java 的Set<String>。为了向 Redis 集合添加元素,你可以选择一个键来标识集合,然后使用jedis.sadd

  1. jedis.sadd("myset", "element1", "element2", "element3");
  2. boolean flag = jedis.sismember("myset", "element2");

你不必用单独的步骤来创建集合。如果不存在,Redis 会创建它。在这种情况下,它会创建一个名为myset的集合,包含三个元素。

jedis.sismember方法检查元素是否在一个集合中。添加元素和检查成员是常数时间的操作。

Redis 还提供了一个列表结构,类似于 Java 的List<String>jedis.rpush方法在末尾(右端)向列表添加元素:

  1. jedis.rpush("mylist", "element1", "element2", "element3");
  2. String element = jedis.lindex("mylist", 1);

同样,你不必在开始添加元素之前创建结构。此示例创建了一个名为mylist的列表,其中包含三个元素。

jedis.lindex方法使用整数索引,并返回列表中指定的元素。添加和访问元素是常数时间的操作。

最后,Redis 提供了一个哈希结构,类似于 Java 的Map<String, String>jedis.hset方法为哈希表添加新条目:

  1. jedis.hset("myhash", "word1", Integer.toString(2));
  2. String value = jedis.hget("myhash", "word1");

此示例创建一个名为的myhash哈希表,其中包含一个条目,该条目从将键word1映射到值"2"

键和值都是字符串,所以如果我们要存储Integer,在我们调用hset之前,我们必须将它转换为String。当我们使用hget查找值时,结果是String,所以我们可能必须将其转换回Integer

使用 Redis 的哈希表可能会令人困惑,因为我们使用一个键来标识我们想要的哈希表,然后用另一个键标识哈希表中的值。在 Redis 的上下文中,第二个键被称为“字段”,这可能有助于保持清晰。所以类似myhash的“键”标志一个特定的哈希表,然后类似word1的“字段”标识一个哈希表中的值。

对于许多应用程序,Redis 哈希表中的值是整数,所以 Redis 提供了一些特殊的方法,比如hincrby将值作为数字来处理:

  1. jedis.hincrBy("myhash", "word2", 1);

这个方法访问myhash,获取word2的当前值(如果不存在则为0),将其递增1,并将结果写回哈希表。

在哈希表中,设置,获取和递增条目是常数时间的操作。

你可以在 http://thinkdast.com/redistypes 上阅读 Redis 数据类型的更多信息。

14.5 练习 11

这个时候,你可以获取一些信息,你需要使用它们来创建搜索引擎的索引,它将结果储存在 Redis 数据库中。

现在运行ant JedisIndexTest。它应该失败,因为你有一些工作要做!

JedisIndexTest测试了这些方法:

  • JedisIndex,这是构造器,它接受Jedis对象作为参数。
  • indexPage,它将一个网页添加到索引中;它需要一个StringURL和一个jsoup Elements对象,该对象包含应该建立索引的页面元素。
  • getCounts,它接收检索词,并返回Map<String, Integer>,包含检索词到它在页面上的出现次数的映射。

以下是如何使用这些方法的示例:

  1. WikiFetcher wf = new WikiFetcher();
  2. String url1 =
  3. "http://en.wikipedia.org/wiki/Java_(programming_language)";
  4. Elements paragraphs = wf.readWikipedia(url1);
  5. Jedis jedis = JedisMaker.make();
  6. JedisIndex index = new JedisIndex(jedis);
  7. index.indexPage(url1, paragraphs);
  8. Map<String, Integer> map = index.getCounts("the");

如果我们在结果map中查看url1,我们应该得到339,这是 Java 维基百科页面(即我们保存的版本)中,the出现的次数。

如果我们再次索引相同的页面,新的结果将替换旧的结果。

将数据结构从 Java 翻译成 Redis 的一个建议是:记住 Redis 数据库中的每个对象都以唯一的键标识,它是一个字符串。如果同一数据库中有两种对象,则可能需要向键添加前缀来区分它们。例如,在我们的解决方案中,我们有两种对象:

  • 我们将URLSet定义为 Redis 集合,它包含URLURL又包含给定检索词。每个URLSet的键的起始是"URLSet:",所以要获取包含单词the的 URL,我们使用键"URLSet:the"来访问该集合。
  • 我们将TermCounter定义为 Redis 哈希表,将出现在页面上的每个检索词映射到它的出现次数。TermCounter每个键的开头都以"TermCounter:"开头,以我们正在查找的页面的 URL 结尾。

在我的实现中,每个检索词都有一个URLSet,每个索引页面都有一个TermCounter。我提供两个辅助方法,urlSetKeytermCounterKey来组装这些键。

14.6 更多建议(如果你需要的话)

到了这里,你拥有了完成练习所需的所有信息,所以如果准备好了就可以开始了。但是我有几个建议,你可能想先阅读它:

  • 对于这个练习,我提供的指导比以前的练习少。你必须做出一些设计决策;特别是,你将必须弄清楚如何将问题分解成,你可以一次性测试的部分,然后将这些部分组合成一个完整的解决方案。如果你尝试一次写出整个项目,而不测试较小的部分,调试可能需要很长时间。
  • 使用持久性数据的挑战之一是它是持久的。存储在数据库中的结构可能会在每次运行程序时发生更改。如果你弄乱了数据库,你将不得不修复它或重新开始,然后才能继续。为了帮助你控制住自己,我提供的方法叫deleteURLSetsdeleteTermCountersdeleteAllKeys,你可以用它来清理数据库,并重新开始。你也可以使用printIndex来打印索引的内容。
  • 每次调用 Jedis 的方法时,你的客户端会向服务器发送一条消息,然后服务器执行你请求的操作并发回消息。如果执行许多小操作,可能需要很长时间。你可以通过将一系列操作分组为一个Transaction,来提高性能。

例如,这是一个简单的deleteAllKeys版本:

  1. public void deleteAllKeys() {
  2. Set<String> keys = jedis.keys("*");
  3. for (String key: keys) {
  4. jedis.del(key);
  5. }
  6. }

每次调用del时,都需要从客户端到服务器的双向通信。如果索引包含多个页面,则该方法需要很长时间来执行。我们可以使用Transaction对象来加速:

  1. public void deleteAllKeys() {
  2. Set<String> keys = jedis.keys("*");
  3. Transaction t = jedis.multi();
  4. for (String key: keys) {
  5. t.del(key);
  6. }
  7. t.exec();
  8. }

jedis.multi返回一个Transaction对象,它提供Jedis对象的所有方法。但是当你调用Transaction的方法时,它不会立即执行该操作,并且不与服务器通信。在你调用exec之前,它会保存一批操作。然后它将所有保存的操作同时发送到服务器,这通常要快得多。

14.7 几个设计提示

现在你真的拥有了你需要的所有信息;你应该开始完成练习。但是如果你卡住了,或者如果你真的不知道如何开始,你可以再来一些提示。

在运行测试代码之前,不要阅读以下内容,尝试一些基本的 Redis 命令,并在JedisIndex.java中编写几个方法。

好的,如果你真的卡住了,这里有一些你可能想要处理的方法:

  1. /**
  2. * 向检索词相关的集合中添加 URL
  3. */
  4. public void add(String term, TermCounter tc) {}
  5. /**
  6. * 查找检索词并返回 URL 集合
  7. */
  8. public Set<String> getURLs(String term) {}
  9. /**
  10. * 返回检索词出现在给定 URL 中的次数
  11. */
  12. public Integer getCount(String url, String term) {}
  13. /**
  14. * 将 TermCounter 的内容存入 Redis
  15. */
  16. public List<Object> pushTermCounterToRedis(TermCounter tc) {}

这些是我在解决方案中使用的方法,但它们绝对不是将项目分解的唯一方法。所以如果他们有帮助,请接受这些建议,但是如果没有,请忽略它们。

对于每种方法,请考虑首先编写测试。当你弄清楚如何测试一个方法时,你经常会了解如何编写它。

祝你好运!