#LyX 1.6.4 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\use_default_options true
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\paperfontsize default
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author "" 
\author "" 
\end_header

\begin_body

\begin_layout Title
New Readahead in CLIO (bug 20294)
\end_layout

\begin_layout Date
2010.1.13
\end_layout

\begin_layout Author
Jay
\end_layout

\begin_layout Section
Introduction
\end_layout

\begin_layout Standard
There're many drawbacks in the current implementation of readahead which
 is ported from b1_8.
 It doesn't work well under some scenarios as follows:
\end_layout

\begin_layout Itemize
No stripe boundary detecting, this causes small RPCs to be sent
\end_layout

\begin_layout Itemize
it detects read pattern at ->readpage, this is not good because it's easy
 to get wrong idea of read pattern
\end_layout

\begin_layout Itemize
too agreesive if the application consumes the data slowly, this causes readahead
 pages evicted in vain under memory pressure
\end_layout

\begin_layout Itemize
readahead is dependent on application, but it does not allow applications
 to have their own readahead module, even doesn't have an interface to disable
 lustre readahead
\end_layout

\begin_layout Standard
In this document, a new readahead scheme is proposed under CLIO, which is
 hopeful to address the above issues.
\end_layout

\begin_layout Section
Requirements
\end_layout

\begin_layout Itemize
optimizing RPC size
\end_layout

\begin_layout Itemize
adapative readahead window based on the consuming speed of applications
\end_layout

\begin_layout Itemize
more precise read pattern detecting
\end_layout

\begin_layout Itemize
plugin module support so that customers' can have their own readahead
\end_layout

\begin_layout Itemize
WNC support
\end_layout

\begin_layout Itemize
Improve read performance
\end_layout

\begin_layout Section
Definitions
\end_layout

\begin_layout Itemize
readahead window
\end_layout

\begin_layout Standard
Readahead window is purely determined by read pattern, it can only be updated
 in ll_file_read and ll_nopage.
 But there is an exception, if miss_in_window event occurs, the window len
 will set to half size in ll_readpage.
 It's defined in ll_readahead_state{}.
\end_layout

\begin_layout Itemize
readahead size
\end_layout

\begin_layout Standard
Because of many restrictions, we can't issue as many pages as readahead
 window described.
 So readahead size is used to describe the size we issued once.
 readhead size is defined in ra_io_arg{}.
\end_layout

\begin_layout Itemize
lazy readahead
\end_layout

\begin_layout Standard
If applications consume data slower than the speed of reading data from
 OSTs, we don't need to bring in too much data in memory.
 In this case, lazy readahead can be enabled.
 That is to say, though the read pattern is quite good, we just read ahead
 the data by the speed of consuming data by applications.
 
\end_layout

\begin_layout Itemize
lazy window size
\end_layout

\begin_layout Standard
If lazy readahead is enabled, we know that the read(from OSTs) speed is
 faster than the consume speed.
 But it might as well has a reasonable size of page-in-cache region, so
 that in case the application happens to read more data, we are still able
 to provide enough data.
 This region is described as lazy_window_size, it's defined in ll_readahead_stat
e{}.
\end_layout

\begin_layout Section
Functional specification
\end_layout

\begin_layout Standard
I'm going to cover what we will do in this section.
\end_layout

\begin_layout Subsection
Read pattern detect
\end_layout

\begin_layout Standard
In order to get precise read pattern, we should detect it near the syscalls.
 So we're going to detect the readahead window in ll_file_read and ll_nopage.
 Also, we'll store multiple seek histories so that it's easier to know the
 pattern of seeks.
\end_layout

\begin_layout Standard
Because read pattern is tightly coupled with applications, it's impossible
 to know every kinds of read patterns(only applications know).
 We'll only have sequential read pattern supported internal(probably have
 reverse sequential read supported).
 For other kinds of read pattern, we just provide some interfaces so that
 customizing application-specific readahead is easy.
\end_layout

\begin_layout Subsection
layered readahead size detect
\end_layout

\begin_layout Standard
In lustre, because of dlm lock coverage, ptlrpc congestion and optimizing
 RPC size, it may not issue as many pages as readahead window to OSTs.
 Instead it has to determine thee readahead size by asking each layer.
\end_layout

\begin_layout Standard
In the new readahead implementation, we're going to pass on readahead window
 to lov and osc to get a suitable read size.
 For example, in LOV layer, it detects if the read ahead window is aligned
 to stripe boundary, and in OSC layer, it detects the dlm lock coverage
 and if the ptlrpc is in congestion.
\end_layout

\begin_layout Standard
There'll be sync and async readahead request.
 If the page is missed in readahead window, apparently we have to read that
 page as soon as possible - we call this kind of requests `sync readahead
 request'.
 For those requests used to streamline the read, we call them `async readahead
 request'.
 We do not issue an async request if we can't compose a full size RPC.
\end_layout

\begin_layout Subsection
Lazy readahead
\end_layout

\begin_layout Standard
The essence of readahead is that when the application needs to read the
 next page, the page has already been in memory, so it makes no sense to
 bring in as many pages as poosibe to memory, if applications consume data
 slowly.
 Obviously we shouldn't read ahead too aggressive in this case, because
 the readahead pages would be evicted in vain if the memory is under pressure.
 We need to invent an algorithm to detect this case, and then adjust the
 readahead size accordingly.
\end_layout

\begin_layout Standard
We'll detect this case by measuring the speed of application consuming the
 data, says consume_speed, and the speed of reading the pages from OSTs,
 says read_speed.
 If read_speed is larger than consume_speed, and if we have already had
 enough pages after read position, we do not need to read far too much.
\end_layout

\begin_layout Subsection
Plugin readahead module
\end_layout

\begin_layout Standard
Detecting actual read patterns is proven to be difficult, only applications
 themselves know the exact read pattern.
 It's good to have an interface to allow customers to implement their own
 readahead algorithm.
 At lease, we have to provide an interface to disable per file readahead
 so that they can do it in user space.
\end_layout

\begin_layout Standard
As I mentioned, we're going to have only one system internal read pattern
 detector - sequential read.
 For stride IO pattern, we're going to implement it as an external module.
\end_layout

\begin_layout Subsection
WNC support
\end_layout

\begin_layout Standard
This may not be easy.
 We probably have to revise ll_file_read to not call system specific routines
 to read data.
 For example, in Linux, we depend on generic_file_read and then readpage
 to read data, we have to revise it so as to issue the read request in ll_file_r
ead directly.
 This is open to discuss.
\end_layout

\begin_layout Subsection
Lock ahead
\end_layout

\begin_layout Standard
If the read pattern is really good, it makes sense to lock file priorly.
 But this has many aspects to be considered, for example, what if the objects
 on OSTs were quite busy, we can't disturb the application on other clients;
 what if the lock ahead missed, we then need a punlishment mechanism.
 This is open to discuss.
\end_layout

\begin_layout Section
Use cases
\end_layout

\begin_layout Standard
We'll generate the following read patterns, and investigate the readahead
 behavior.
\end_layout

\begin_layout Subsection
Small sequential read
\end_layout

\begin_layout Subsection
Large sequential read
\end_layout

\begin_layout Subsection
Application consumes data slowly
\end_layout

\begin_layout Subsection
Application consumes data quickly
\end_layout

\begin_layout Subsection
OST is quite busy
\end_layout

\begin_layout Subsection
random read
\end_layout

\begin_layout Section
Logic specification
\end_layout

\begin_layout Subsection
Prototypes
\end_layout

\begin_layout Subsubsection
ll_readahead_state
\end_layout

\begin_layout LyX-Code
struct ll_readahead_state {
\end_layout

\begin_layout LyX-Code
    /** The data to remember the last continuous read, by pages */
\end_layout

\begin_layout LyX-Code
    pgoff_t       ras_prev_off;
\end_layout

\begin_layout LyX-Code
    unsigned long ras_prev_count;
\end_layout

\begin_layout LyX-Code
    /** historical seeks, last 4 times.
 Negative # means seek backward */
\end_layout

\begin_layout LyX-Code
    int64_t       ras_seeks[4];
\end_layout

\begin_layout LyX-Code
    /** curpos of ras_seeks */
\end_layout

\begin_layout LyX-Code
    int           ras_seek_pos;
\end_layout

\begin_layout LyX-Code
    /** number of read requests after the last seek.
 */
\end_layout

\begin_layout LyX-Code
    unsigned long ras_consecutive_requests;
\end_layout

\begin_layout LyX-Code
    /** Readahead window start and length */
\end_layout

\begin_layout LyX-Code
    unsigned long ras_window_start, ras_window_len;
\end_layout

\begin_layout LyX-Code
    /** Where the last read-ahead ended, so it's the start point of next
 read */
\end_layout

\begin_layout LyX-Code
    unsigned long ras_next_readahead;
\end_layout

\begin_layout LyX-Code
    /** lazy readahead is enabled if the speed of consuming data is slower
 then speed of reading,
\end_layout

\begin_layout LyX-Code
     * and has this # of pages in cache */
\end_layout

\begin_layout LyX-Code
    unsigned long ras_lazy_window;
\end_layout

\begin_layout LyX-Code
    /** lazy readahead marker point */
\end_layout

\begin_layout LyX-Code
    unsigned long ras_lazy_marker;
\end_layout

\begin_layout LyX-Code
    unsigned long ras_lazy_mark_page;
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Subsubsection
ra_io_arg
\end_layout

\begin_layout LyX-Code
/**  cl_io_ra_arg is a container which includes the readpage and readahead
\end_layout

\begin_layout LyX-Code
 * parameters.
 This data structure is passed onto <vvp, lov, osc> layer
\end_layout

\begin_layout LyX-Code
 * to determine the read size.
  */
\end_layout

\begin_layout LyX-Code
struct ra_io_arg {
\end_layout

\begin_layout LyX-Code
    /** start page index of readahead window */
\end_layout

\begin_layout LyX-Code
    unsigned long ria_start;
\end_layout

\begin_layout LyX-Code
    /** end page index of readahead window */
\end_layout

\begin_layout LyX-Code
    unsigned long ria_end;
\end_layout

\begin_layout LyX-Code
    /** # of page slots reserved in global readahead cache control.
 */
\end_layout

\begin_layout LyX-Code
    long ria_reserved;
\end_layout

\begin_layout LyX-Code
    /** set if the reading page was evicted because of memory pressure.
 */
\end_layout

\begin_layout LyX-Code
    int ria_miss_in_window;
\end_layout

\begin_layout LyX-Code
    /** a point to weigh how busy is the ptlrpc.
 */
\end_layout

\begin_layout LyX-Code
    int ria_congestion;
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Subsubsection
ll_readahead_update
\end_layout

\begin_layout Standard
This function records the read history data, and analyze the read pattern.
 If plugin module is supported, it scans the read pattern module list and
 calls each detectors.
 It also runs Lazy readahead detecting algorithm.
\end_layout

\begin_layout LyX-Code
void ll_readahead_update(struct file *file, pgoff_t pgidx, ulong pgcnt,
 int vfs_or_mmap)
\end_layout

\begin_layout LyX-Code
{
\end_layout

\begin_layout LyX-Code
    if (readahead is disabled for this file)
\end_layout

\begin_layout LyX-Code
        return;
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code
    if (pgidx is sequential to <ras_prev_off, ras_prev_count>) {
\end_layout

\begin_layout LyX-Code
        ras_prev_count <- ras_prev_count + pgcnt;
\end_layout

\begin_layout LyX-Code
    } else {
\end_layout

\begin_layout LyX-Code
        ras_seeks[ras_seek_pos] <- pgidx - ras_pref_off;
\end_layout

\begin_layout LyX-Code
        ras_seek_pos <- next pos;
\end_layout

\begin_layout LyX-Code
    }
\end_layout

\begin_layout LyX-Code
    /* Run lazy readahead algorithm */
\end_layout

\begin_layout LyX-Code
    ...
\end_layout

\begin_layout LyX-Code
    /* Adjust readahead window */
\end_layout

\begin_layout LyX-Code
    if (sequential) {
\end_layout

\begin_layout LyX-Code
        increase the readahead window by RAS_INCREASE_STEP;
\end_layout

\begin_layout LyX-Code
    } else {
\end_layout

\begin_layout LyX-Code
        reset the readahead window, set readahead window to <pgidx, pgcnt>
\end_layout

\begin_layout LyX-Code
    }
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Subsubsection
ll_readahead
\end_layout

\begin_layout Standard
This function is used to create pages by ra_io_arg, then add them into read
 queue.
 Before creating pages, it checks if the page is covered by a dlm lock via
 ->cpo_is_under_lock().
\end_layout

\begin_layout Subsubsection
ll_io_readpage
\end_layout

\begin_layout Standard
ll_io_readpage is called by ll_readpage to read a page into memory.
 It calls cl_io_read_page which then calls each layer's ->cio_readpage method
 to determine the suitable readahead size.
 Finally ll_io_readpage then creates pages by the readahead size, and submit
 the IO.
\end_layout

\begin_layout LyX-Code
/* @page is the page being read.
 */
\end_layout

\begin_layout LyX-Code
int ll_io_readpage(..., struct cl_io *io, struct cl_page *page, struct file
 *file)
\end_layout

\begin_layout LyX-Code
{
\end_layout

\begin_layout LyX-Code
    initializes ra_io_arg @ra;
\end_layout

\begin_layout LyX-Code
    add the @page into read queue;
\end_layout

\begin_layout LyX-Code
    call cl_io_readpage(..., io, page, ra);
\end_layout

\begin_layout LyX-Code
    call ll_readahead to create pages by @ra and add them into read queue;
\end_layout

\begin_layout LyX-Code
    revoke unused budget; /* reserved in vvp_io_readpage */
\end_layout

\begin_layout LyX-Code
    submit read queue;
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Subsubsection
cl_io_readpage
\end_layout

\begin_layout LyX-Code
int cl_io_readpage(struct lu_env *env, struct cl_io *io, struct cl_page
 *page, strucr ra_io_arg *ra);
\end_layout

\begin_layout Subsubsection
vvp_io_readpage
\end_layout

\begin_layout Standard
vvp_io_readpage first checks if the reading page has defer-uptodate marked,
 if this is the case, it means the page is already in cache; then it determines
 the readahead size by ll_readahead_state, also, it reserves the budget
 from ra in sbi.
\end_layout

\begin_layout LyX-Code
int vvp_io_readpage(..., struct page *page, struct ra_io_arg *ra)
\end_layout

\begin_layout LyX-Code
{
\end_layout

\begin_layout LyX-Code
    get ccc_page from @page;
\end_layout

\begin_layout LyX-Code
    if (!ccc_page->cp_defer_uptodate) {
\end_layout

\begin_layout LyX-Code
        ra->ria_miss_in_window = 1;
\end_layout

\begin_layout LyX-Code
    }
\end_layout

\begin_layout LyX-Code
    /* Get the readahead size */
\end_layout

\begin_layout LyX-Code
    ra->ria_start = ras_next_readahead;
\end_layout

\begin_layout LyX-Code
    ra->ria_end   = ras_window_start + ras_window_len - 1;
\end_layout

\begin_layout LyX-Code
    reserve budget;
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Subsubsection
lov_io_readpage
\end_layout

\begin_layout Standard
If the request will be an async request(ria_miss_in_window is false), lov_io_rea
dpage makes sure that the readahead size is aligned to stripe boundary.
 lov_io_readpage will be complex.
\end_layout

\begin_layout LyX-Code
int lov_io_readpage(..., struct cl_page *page, struct ra_io_arg *ra)
\end_layout

\begin_layout LyX-Code
{
\end_layout

\begin_layout LyX-Code
    for (each stripe covered by @ra) {
\end_layout

\begin_layout LyX-Code
        compose stripe ra, says stripe_ra;
\end_layout

\begin_layout LyX-Code
        call cl_io_readpage against the stripe;
\end_layout

\begin_layout LyX-Code
        if (stripe_ra->ria_end is not on the stripe boundary) {
\end_layout

\begin_layout LyX-Code
            adjust @ra accordingly;
\end_layout

\begin_layout LyX-Code
            break;
\end_layout

\begin_layout LyX-Code
        }
\end_layout

\begin_layout LyX-Code
    }
\end_layout

\begin_layout LyX-Code
    if (async readahead request && @ra size is less then a full RPC size)
 {
\end_layout

\begin_layout LyX-Code
        /* Do not send RPC */
\end_layout

\begin_layout LyX-Code
        ra->ria_end = ra->ria_start - 1;
\end_layout

\begin_layout LyX-Code
    }
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Subsubsection
osc_io_readpage
\end_layout

\begin_layout Standard
osc_io_readpage checks the dlm lock coverage of <ria_start, ria_end>, and
 shrink this region accordingly.
 Also, it checks if the ptlrpc is in congestion, it adjusts the size by
 policy as well.
\end_layout

\begin_layout LyX-Code
int osc_io_readpage(..., struct cl_page *page, struct ra_io_arg *ra)
\end_layout

\begin_layout LyX-Code
{
\end_layout

\begin_layout LyX-Code
    /* adjust @ra by the coverage of dlm lock; */
\end_layout

\begin_layout LyX-Code
    if (@ra is not fully covered by dlm lock) {
\end_layout

\begin_layout LyX-Code
        adjust @ra accordingly;
\end_layout

\begin_layout LyX-Code
    }
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code
    /* set ra->ria_congestion by ptlrpc queue status */
\end_layout

\begin_layout LyX-Code
    if (ptlrpc->in_flights < 8) {
\end_layout

\begin_layout LyX-Code
        ra->ria_ptlrpc_congestion = Green;
\end_layout

\begin_layout LyX-Code
    } else if (ptlrpc->in_flights < 16) {
\end_layout

\begin_layout LyX-Code
        ra->ria_ptlrpc_congestion = Yellow;
\end_layout

\begin_layout LyX-Code
        ra->ria_end = ra->ria_start + ...;
\end_layout

\begin_layout LyX-Code
    } else {
\end_layout

\begin_layout LyX-Code
        ra->ria_ptlrpc_congestion = Red;
\end_layout

\begin_layout LyX-Code
        ra->ria_end = ria_start - 1;
\end_layout

\begin_layout LyX-Code
    }
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Subsection
Flow chart
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename readahead-flowchart-1.jpg

\end_inset


\end_layout

\begin_layout Subsection
An algorithm of lazy readahead
\end_layout

\begin_layout Standard
Here is a way to estimate the speed of consuming data by application as
 follows:
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename lazy-readahead-1.jpg

\end_inset


\end_layout

\begin_layout Standard
As the picture shows:
\end_layout

\begin_layout Enumerate
Have a lazy_marker and lazy_mark_page;
\end_layout

\begin_layout Enumerate
when readahead happens, assuming it issued readahead_size pages, then lazy_mark_
page is used to remember the last page just issued, and lazy_marker is used
 to remember the distance of (read_pos + read_len + readahead_size);
\end_layout

\begin_layout Enumerate
when the read_pos reaches lazy_marker, we can then check if the lazy_mark_page
 is ready.
 If it's ready, we can say that the read speed if a bit faster then consuming
 speed, and vice versa;
\end_layout

\begin_layout Enumerate
Set lazy_window to be the distance between next_readahead and read_pos(we
 can consider the previous lazy_window to avoid waving too much).
 If the lazy_window is reasonable big, and read_speed is larger then consume_spe
ed, we can start lazy_readahead;
\end_layout

\begin_layout Enumerate
For lazy readahead, bascially we issue one RPC unless the application has
 consumed one-full-RPC size of data.
\end_layout

\begin_layout Subsection
Plugin module support
\end_layout

\begin_layout Standard
T.B.D
\end_layout

\begin_layout Section
State management
\end_layout

\begin_layout Section
Alternatives
\end_layout

\begin_layout Subsection
Readahead thread per file
\end_layout

\begin_layout Standard
To address the problem that we issue the readahead RPC in the reading process,
 this is considered to time consuming.
 We have an idea to spawn a per file readahead thread for each process,
 and this thread can be used to issue the readahead RPC async.
\end_layout

\begin_layout Standard
However, it has some problems about this scheme:
\end_layout

\begin_layout Itemize
context switch is expensive
\end_layout

\begin_layout Itemize
if the client is busy, we can't issue the RPCs in time.
 This causes readahead is actually not usable.
\end_layout

\begin_layout Itemize
faireness - it'd not be reasonable to have two threads for serving read
 request.
 This is unfair to other processes in system.
\end_layout

\begin_layout Section
Focus for inspections
\end_layout

\end_body
\end_document
