|
KNews, the program Robert presents, takes advantage of QNX features to more efficiently handle news articles. Under KNews, one program gets and stores articles, while another program implements a "virtual filesystem" to keep track of them.
May 01, 1996
URL:http://www.drdobbs.com/web-development/improving-usenet-news-performance/184409883
Robert is a principal with PARSE Software Devices. He can be contacted at [email protected].
Usenet is a worldwide network of computers that allows users to post and read messages (articles) categorized hierarchically into topical groups (newsgroups); for instance, comp.os.qnx refers to the newsgroup "computer science," subgroup "operating systems," thread "qnx."
In this article, I'll examine how Usenet news works on existing UNIX systems. I'll then describe how the speed and efficiency of this arrangement can be improved under the QNX operating system.
People from around the world post articles to various newsgroups. News servers then distribute these articles to neighboring machines. Neighboring machines distribute the articles to other machines until the article has been propagated around the world. Machines check incoming articles to see if they already have a copy, and delete the incoming article if they do. I won't detail the machines' methods of getting articles, except to say there is a program on the user's system that is responsible for getting articles from other machines and storing them.
For instance, a typical system accepts articles for about 4000 newsgroups (this is by no means a huge system, either!). As each article comes in, the article's header is scanned, and the news software determines which newsgroup the article should be stored in.
Before news traffic escalated, it seemed like a good idea to store one article per file. Consequently, newsgroup names were simply converted into pathnames. For example, the 1143rd article in the newsgroup comp.os.qnx might be stored in a file called "/usr/spool/news/comp/os/qnx/1143." The next article that came in for that newsgroup would go into /usr/spool/news/ comp/os/qnx/1144 and so on.
There are a number of reasons why this approach is no longer ideal. For one thing, articles can arrive in any order: We're not always going to get all of the articles for comp.os.qnx, then all of the articles for comp.os.rsx11, and then comp.os.svr4. This means that as articles arrive, the news storage program is creating files in an ad hoc manner all over the disk. Additionally, it creates anywhere from a few-thousand to several-hundred-thousand files per day, depending on the size of the feed!
Given the volume of news these days, disks can fill up quickly. Consequently, most news systems have an "expiry policy." How long do you retain articles before deleting them? This usually depends upon two factors--how much disk space you have and which newsgroups you value. In the unlikely case that the disk will never overflow, the volume of news coming in must equal the volume of news being expired. On a typical news system, the expiry processing is done by a batch file that runs periodically, say, once or twice a day. With current implementations, expiry processing can take a few hours. Not only are there many files being created in random places on the disk each second, there also are roughly equal numbers of files being deleted from different random places each second. This is suboptimal.
Once the files are in their appropriate places, it is hoped that a large number of users will read a large percentage of the articles that have been stored. Sadly, the vast majority of news articles are never read. They simply expire.
To make matters worse, the news systems in common use end up copying each article many times over before placing it in its final resting place. Then, when it comes time to expire the article, an additional read of the article takes place; see Figure 1.
Rather than using a general-purpose file system to (suboptimally) manage a news system, you can use your knowledge of how these files are created, read, and deleted to create a file system uniquely tailored to handling this information. However, the drawback of a "new" filing strategy is that a huge body of free software available on the Internet is oriented toward the current organization (the /usr/spool/news structure, for instance).
Still, there are situations when you can leverage operating-system features to improve things. KNews, the program I present here, takes advantage of some features of the QNX operating system to more efficiently handle news articles. Under KNews, one or more programs get and store articles, while a different program implements a "virtual file system" to keep track of the articles.
The first program (the newsfeeder) knows how to get articles from other machines. (There actually are two main variants of the newsfeeder: one that knows how to get articles from NNTP-based hosts, and another that knows how to get articles from UUCP/rnews feeds.) When the newsfeeder gets an article, it looks at the header. In conjunction with the local expiration policy file, the newsfeeder program immediately determines when the article will expire. The article is then appended to a file that has other articles that expire at that same time. When the article is placed into the file, the article's position and its length are noted.
For example, assume you were examining article 677, posted to ott.forsale on January 15, 1996, at 10:34 GMT. The expiration period for that particular newsgroup is four days. Consequently, you know that the article will expire on January 19, 1996, at 10:34 GMT. Therefore, you store the article at the end of a file called 960119.10 (ignore the :34 because you've defined the expiry granularity to be one hour). You then make a note of the article's position within the storage file, along with its length and number: ott.forsale, art#677, exp 1996 01 19 10:00, pos 36554, len 495.
By the time you received a day's worth of news, you would have created a number of files, each containing collections of articles. The number of files created is a function of the expiration policy and the expiration granularity. For example, with a maximum expiration of ten days and expiration granularity of six hours, you would create 40 files (10*24/6). This is between 3- and 4-orders-of-magnitude fewer files than conventional means!
Okay, so now all the articles are in a few big files--which I call expiry-ordered heap (EOH) files--stored in a directory. By convention, this directory is /usr/spool/ knews. What you really want to do is have the operating system present a /usr/spool/ news directory structure to all applications. This way, none of the applications have to be modified to work with KNews. What this means, in effect, is that you map files under /usr/spool/news into portions of your EOH files; see Figure 2.
The newsfeeder program already provides the information you need: the newsgroup name, article number, EOH file name, position within the file, and length of the article.
Under most operating systems, creating a virtual file system that does this kind of mapping is a major undertaking. Under the QNX operating system, it simply involves writing a few hundred lines of code.
The first step to implementing a virtual file system is to fake the /usr/spool/news directory structure. To applications programs, it must appear that the directory exists and operates just like a disk-based file system would.
Our virtual file system (VFsys.knews) should export the illusion of two main object types--subdirectories and files-- and it should support read-only attempts to access these objects; see Example 1. Since it is a read-only file system, you'll also need some method of telling VFsys.knews about new articles, by giving it the article number, expiry date, offset, and length.
QNX is a microkernel, message-passing operating system with most services implemented via a message. For example, when an application (client) opens a file, the application's C library open code places the arguments passed to the open() call into a message, then sends this message to the process that is managing the file system, Fsys (server).
Fsys decides if the open should succeed or not (based on permissions, existence of the file, or whatever) and returns a status. Sometime later, the client might request a read of 200 bytes. Again, the client's library composes a message, which it then sends out to the server, requesting that a read be performed. The server will go out to disk, then return the data to the client.
Fsys isn't the only program that is allowed to receive and process open and read calls, though. Under QNX there is no sacred attribute associated with programs like Fsys versus user-written programs. However, you can do a neat trick under QNX that you can't easily do under other operating systems: You can write a program that assumes responsibility for a portion of the pathname space. This functionality is a subset of what is generally termed a "resource manager" under QNX.
To successfully take over /usr/spool/news, you have to:
In order to implement step 1, the function resmgrInit in resmgr.c (available electronically; see "Availability," page 3) calls qnx_prefix_attach to associate the program with a particular pathname prefix; in this case, /usr/spool/news. This causes any process opening files and directories in this portion of the pathname space to send its messages to our process instead of the process managing the actual disk drive.
To implement steps 2 and 3, the function serve in resmgr.c waits for messages from clients (the Receive function call). This is a blocking call: The program does not continue past Receive until a message has been received. Once you get a message, you call the appropriate routine from the jump table. You can receive a whole range of messages, each corresponding to either some C-function call that a client can execute, or some of the special newsfeeder messages. In terms of regular messages, you receive messages corresponding to the open, read, write, readdir, and stat calls. To implement the virtual file system, you just have to handle these calls.
The open call specifies which file is being opened. Because you can get requests from multiple clients (for example, three different terminal sessions can all do an ls on some portion of /usr/spool/news at the same time), you have to track processing based upon who is sending the message. So, in the open handler you will notice an open control block (OCB) associated with the particular request, via map_ocb. This OCB holds the state information associated with a particular client's use of the virtual file system.
There are really two types of requests that you can handle: file requests and directory requests. File requests deal with the functions in Table 1(a). Directory requests are similar; see Table 1(b). Once you have associated the context with the open call, you can then expect that you will receive a read request, followed by a close request. The close request is where you disassociate the context from the request.
The real work is done in the open (in the case of files) or read (in the case of directories) functions. For a file, open has to verify that the file actually exists, then it has to initialize the context for that file.
To determine if the file exists, you look at some internal data structures that VFsys.knews maintains (in database.c, available electronically). This data is a network of directories and files, similar to what a file-system manager would actually maintain on disk; see Figure 3. By following the chain of directories (shown as circles in Figure 3), you eventually get to a file entry (shown as a rectangle in the figure). The file entry tells us the article number, EOH filename, position, and length.
You then open the EOH file, seek to the article's starting position, and store the file descriptor in the context block. Then, whenever the client performs a read, your server just reads bytes from the file descriptor and transfers them back to the client.
There is a similar flow for directories. The directory path is evaluated against the internal database structure and checked for validity. If invalid, an error status is returned to the client. If valid, an OK status is returned, and you can expect that the client will send the server io_readdir messages to get the directory entries. Again, you make use of the context block, but this time, you drive the processing by a finite-state machine. The context block's state variable, ocb --> state, can have one of these state values: OCBState_Initial, OCBState_GetFiles, OCBState_GetDirectories, or OCBState_Done.
OCBState_Initial generates the virtual directory entries "." and ".." (each directory must have these), then transits to either the OCBState_GetFiles or OCBState_ GetDirectories state, depending upon what is contained in the internal database structure. OCBState_GetFiles returns directory entries for files, one-by-one, from the internal database structure. OCBState_ GetDirectories does the same thing for subdirectories.
I use functions like io_stat (for the client's stat function call), io_chdir, and so on. Their operation is analogous to the operation of the simple open/ read/close and handle/readdir/close messages.
Apart from the standard resource manager messages, there also are a number of messages that deal specifically with VFsys.knews itself; for example, messages that tell VFsys.knews about a new article that's just become available, or tell VFsys.knews to expire articles.
When a client sends the expiry message, the Receive in procedure serve (resmgr.c) gets the message and the newsmsgsJT jump table ends up calling the procedure newsExpire. The procedure newsExpire calls journalExpire and databaseExpire, which do the work. databaseExpire runs through all of the internal database elements, finds the articles that have expired, and removes them. I optimized for speed here by having the database entries sorted by expiration. On my system, a 486/33 with about 10 KB of articles being expired, this took under one second. You could run expire once per minute if you wanted to, although a practical limit would be once per hour. I run mine every three hours.
VFsys.knews is an ongoing project. In addition to the work I've described here, other developers around the world are working on source code for configuration, newsfeeders, and management software. If you are interested in participating in the project, send me e-mail at [email protected]. I'm particularly interested in hearing from anyone who would like to port this architecture to other operating systems. It might not be as simple as under QNX, but if we keep the same basic functionality, we can save a lot of grief for system administrators on other operating systems.
QNX Software Systems Ltd.
175 Terence Matthews Crescent
Kanata, ON Canada, K2M 1W8
613-591-0931
http://www.qnx.com
File Request resmgr.c Procedure (a) Open a file. io_open Read that file. io_read Close that file. io_close (b) Open a directory. io_handle Read entries out of that directory. io_readdir Close that directory. io_close
$ cd /usr/spool/news/comp/os/qnx $ ls 1134 1136 1137 1142 $ cat 1134 <contents of article 1134 show up> $ cd ../vms $ pwd /usr/spool/news/comp/os/vms
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.
