第十四章 持久化
译者:飞龙
自豪地采用谷歌翻译
在接下来的几个练习中,我们将返回到网页搜索引擎的构建。为了回顾,搜索引擎的组件是:
- 抓取:我们需要一个程序,可以下载一个网页,解析它,并提取文本和任何其他页面的链接。
- 索引:我们需要一个索引,可以查找检索项并找到包含它的页面。
- 检索:我们需要一种方法,从索引中收集结果,并识别与检索项最相关的页面。
如果你做了练习 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
的实例。 - 单击实例名称来访问配置页面。记下页面顶部附近的网址,如下所示:
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 将如下所示:
redis://redistogo:1234567feedfacebeefa1e1234567@dory.redistogo.com:10534
因为此文件包含你的 Redis 服务器的密码,你不应将此文件放在公共仓库中。为了帮助你避免意外避免这种情况,仓库包含.gitignore
文件,使文件难以(但不是不可能)放入你的仓库。
现在运行ant build
来编译源文件,以及ant JedisMaker
来运行main
中的示例代码:
public static void main(String[] args) {
Jedis jedis = make();
// String
jedis.set("mykey", "myvalue");
String value = jedis.get("mykey");
System.out.println("Got value: " + value);
// Set
jedis.sadd("myset", "element1", "element2", "element3");
System.out.println("element2 is member: " +
jedis.sismember("myset", "element2"));
// List
jedis.rpush("mylist", "element1", "element2", "element3");
System.out.println("element at index 1: " +
jedis.lindex("mylist", 1));
// Hash
jedis.hset("myhash", "word1", Integer.toString(2));
jedis.hincrBy("myhash", "word2", 1);
System.out.println("frequency of word1: " +
jedis.hget("myhash", "word1"));
System.out.println("frequency of word1: " +
jedis.hget("myhash", "word2"));
jedis.close();
}
这个示例展示了数据类型和方法,你在这个练习中最可能使用它们。当你运行它时,输出应该是:
Got value: myvalue
element2 is member: true
element at index 1: element2
frequency of word1: 2
frequency of word2: 1
下一节中我会解释代码的工作原理。
14.4 Redis 数据类型
Redis 基本上是一个从键到值的映射,键是字符串,值可以是字符串,也可以是几种数据类型之一。最基本的 Redis 数据类型是字符串。我将用斜体书写 Redis 类型,来区别于 Java 类型。
为了向数据库添加一个字符串,请使用jedis.set
,类似于Map.put
; 参数是新的键和相应的值。为了查找一个键并获取其值,请使用jedis.get
:
jedis.set("mykey", "myvalue");
String value = jedis.get("mykey");
在这个例子中,键是"mykey"
,值是"myvalue"
。
Redis 提供了一个集合结构,类似于 Java 的Set<String>
。为了向 Redis 集合添加元素,你可以选择一个键来标识集合,然后使用jedis.sadd
:
jedis.sadd("myset", "element1", "element2", "element3");
boolean flag = jedis.sismember("myset", "element2");
你不必用单独的步骤来创建集合。如果不存在,Redis 会创建它。在这种情况下,它会创建一个名为myset
的集合,包含三个元素。
jedis.sismember
方法检查元素是否在一个集合中。添加元素和检查成员是常数时间的操作。
Redis 还提供了一个列表结构,类似于 Java 的List<String>
。jedis.rpush
方法在末尾(右端)向列表添加元素:
jedis.rpush("mylist", "element1", "element2", "element3");
String element = jedis.lindex("mylist", 1);
同样,你不必在开始添加元素之前创建结构。此示例创建了一个名为mylist
的列表,其中包含三个元素。
jedis.lindex
方法使用整数索引,并返回列表中指定的元素。添加和访问元素是常数时间的操作。
最后,Redis 提供了一个哈希结构,类似于 Java 的Map<String, String>
。jedis.hset
方法为哈希表添加新条目:
jedis.hset("myhash", "word1", Integer.toString(2));
String value = jedis.hget("myhash", "word1");
此示例创建一个名为的myhash
哈希表,其中包含一个条目,该条目从将键word1
映射到值"2"
。
键和值都是字符串,所以如果我们要存储Integer
,在我们调用hset
之前,我们必须将它转换为String
。当我们使用hget
查找值时,结果是String
,所以我们可能必须将其转换回Integer
。
使用 Redis 的哈希表可能会令人困惑,因为我们使用一个键来标识我们想要的哈希表,然后用另一个键标识哈希表中的值。在 Redis 的上下文中,第二个键被称为“字段”,这可能有助于保持清晰。所以类似myhash
的“键”标志一个特定的哈希表,然后类似word1
的“字段”标识一个哈希表中的值。
对于许多应用程序,Redis 哈希表中的值是整数,所以 Redis 提供了一些特殊的方法,比如hincrby
将值作为数字来处理:
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>
,包含检索词到它在页面上的出现次数的映射。
以下是如何使用这些方法的示例:
WikiFetcher wf = new WikiFetcher();
String url1 =
"http://en.wikipedia.org/wiki/Java_(programming_language)";
Elements paragraphs = wf.readWikipedia(url1);
Jedis jedis = JedisMaker.make();
JedisIndex index = new JedisIndex(jedis);
index.indexPage(url1, paragraphs);
Map<String, Integer> map = index.getCounts("the");
如果我们在结果map
中查看url1
,我们应该得到339
,这是 Java 维基百科页面(即我们保存的版本)中,the
出现的次数。
如果我们再次索引相同的页面,新的结果将替换旧的结果。
将数据结构从 Java 翻译成 Redis 的一个建议是:记住 Redis 数据库中的每个对象都以唯一的键标识,它是一个字符串。如果同一数据库中有两种对象,则可能需要向键添加前缀来区分它们。例如,在我们的解决方案中,我们有两种对象:
- 我们将
URLSet
定义为 Redis 集合,它包含URL
,URL
又包含给定检索词。每个URLSet
的键的起始是"URLSet:"
,所以要获取包含单词the
的 URL,我们使用键"URLSet:the"
来访问该集合。 - 我们将
TermCounter
定义为 Redis 哈希表,将出现在页面上的每个检索词映射到它的出现次数。TermCounter
每个键的开头都以"TermCounter:"
开头,以我们正在查找的页面的 URL 结尾。
在我的实现中,每个术语都有一个URLSet
,每个索引页面都有一个TermCounter
。我提供两个辅助方法,urlSetKey
和termCounterKey
来组装这些键。
14.6 更多建议(如果你需要的话)
到了这里,你拥有了完成练习所需的所有信息,所以如果准备好了就可以开始了。但是我有几个建议,你可能想先阅读它:
- 对于这个练习,我提供的指导比以前的练习少。你必须做出一些设计决策;特别是,你将必须弄清楚如何将问题分解成,你可以一次性测试的部分,然后将这些部分组合成一个完整的解决方案。如果你尝试一次写出整个项目,而不测试较小的部分,调试可能需要很长时间。
- 使用持久性数据的挑战之一是它是持久的。存储在数据库中的结构可能会在每次运行程序时发生更改。如果你弄乱了数据库,你将不得不修复它或重新开始,然后才能继续。为了帮助你控制住自己,我提供的方法叫
deleteURLSets
,deleteTermCounters
和deleteAllKeys
,你可以用它来清理数据库,并重新开始。你也可以使用printIndex
来打印索引的内容。 - 每次调用 Jedis 的方法时,你的客户端会向服务器发送一条消息,然后服务器执行你请求的操作并发回消息。如果执行许多小操作,可能需要很长时间。你可以通过将一系列操作分组为一个
Transaction
,来提高性能。
例如,这是一个简单的deleteAllKeys
版本:
public void deleteAllKeys() {
Set<String> keys = jedis.keys("*");
for (String key: keys) {
jedis.del(key);
}
}
每次调用del
时,都需要从客户端到服务器的双向通信。如果索引包含多个页面,则该方法需要很长时间来执行。我们可以使用Transaction
对象来加速:
public void deleteAllKeys() {
Set<String> keys = jedis.keys("*");
Transaction t = jedis.multi();
for (String key: keys) {
t.del(key);
}
t.exec();
}
jedis.multi
返回一个Transaction
对象,它提供Jedis
对象的所有方法。但是当你调用Transaction
的方法时,它不会立即执行该操作,并且不与服务器通信。在你调用exec
之前,它会保存一批操作。然后它将所有保存的操作同时发送到服务器,这通常要快得多。
14.7 几个设计提示
现在你真的拥有了你需要的所有信息;你应该开始完成练习。但是如果你卡住了,或者如果你真的不知道如何开始,你可以再来一些提示。
在运行测试代码之前,不要阅读以下内容,尝试一些基本的 Redis 命令,并在JedisIndex.java
中编写几个方法。
好的,如果你真的卡住了,这里有一些你可能想要处理的方法:
/**
* 向检索词相关的集合中添加 URL
*/
public void add(String term, TermCounter tc) {}
/**
* 查找检索词并返回 URL 集合
*/
public Set<String> getURLs(String term) {}
/**
* 返回检索词出现在给定 URL 中的次数
*/
public Integer getCount(String url, String term) {}
/**
* 将 TermCounter 的内容存入 Redis
*/
public List<Object> pushTermCounterToRedis(TermCounter tc) {}
这些是我在解决方案中使用的方法,但它们绝对不是将项目分解的唯一方法。所以如果他们有帮助,请接受这些建议,但是如果没有,请忽略它们。
对于每种方法,请考虑首先编写测试。当你弄清楚如何测试一个方法时,你经常会了解如何编写它。
祝你好运!