lkml.org 
[lkml]   [2013]   [Mar]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: zsmalloc limitations and related topics

On 03/14/2013 06:59 AM, Seth Jennings wrote:
> On 03/13/2013 03:02 PM, Dan Magenheimer wrote:
>>> From: Robert Jennings [mailto:rcj@linux.vnet.ibm.com]
>>> Subject: Re: zsmalloc limitations and related topics
>>
>> Hi Robert --
>>
>> Thanks for the well-considered reply!
>>
>>> * Dan Magenheimer (dan.magenheimer@oracle.com) wrote:
>>>> Hi all --
>>>>
>>>> I've been doing some experimentation on zsmalloc in preparation
>>>> for my topic proposed for LSFMM13 and have run across some
>>>> perplexing limitations. Those familiar with the intimate details
>>>> of zsmalloc might be well aware of these limitations, but they
>>>> aren't documented or immediately obvious, so I thought it would
>>>> be worthwhile to air them publicly. I've also included some
>>>> measurements from the experimentation and some related thoughts.
>>>>
>>>> (Some of the terms here are unusual and may be used inconsistently
>>>> by different developers so a glossary of definitions of the terms
>>>> used here is appended.)
>>>>
>>>> ZSMALLOC LIMITATIONS
>>>>
>>>> Zsmalloc is used for two zprojects: zram and the out-of-tree
>>>> zswap. Zsmalloc can achieve high density when "full". But:
>>>>
>>>> 1) Zsmalloc has a worst-case density of 0.25 (one zpage per
>>>> four pageframes).
>>>
>>> The design of the allocator results in a trade-off between best case
>>> density and the worst-case which is true for any allocator. For zsmalloc,
>>> the best case density with a 4K page size is 32.0, or 177.0 for a 64K page
>>> size, based on storing a set of zero-filled pages compressed by lzo1x-1.
>>
>> Right. Without a "representative workload", we have no idea
>> whether either my worst-case or your best-case will be relevant.
>>
>> (As an aside, I'm measuring zsize=28 bytes for a zero page...
>> Seth has repeatedly said 103 bytes and I think this is
>> reflected in your computation above. Maybe it is 103 for your
>> hardware compression engine? Else, I'm not sure why our
>> numbers would be different.)
>
> I rechecked this and found my measurement was flawed. It was based on
> compressing a zero-filled file with lzop -1. The file size is 107 but,
> as I recently discovered, contains LZO metadata as well. Using lzop -l,
> I got that the compressed size of the data (not the file), is 44 bytes.
> So still not what you are observing but closer.
>
> $ dd if=/dev/zero of=zero.page bs=4k count=1
> $ lzop -1 zero.page
> $ lzop -l zero.page.lzo
> method compressed uncompr. ratio uncompressed_name
> LZO1X-1(15) 44 4096 1.1% zero.page
>
>>
>>>> 2) When not full and especially when nearly-empty _after_
>>>> being full, density may fall below 1.0 as a result of
>>>> fragmentation.
>>>
>>> True and there are several ways to address this including
>>> defragmentation, fewer class sizes in zsmalloc, aging, and/or writeback
>>> of zpages in sparse zspages to free pageframes during normal writeback.
>>
>> Yes. And add pageframe-reclaim to this list of things that
>> zsmalloc should do but currently cannot do.
>
> The real question is why is pageframe-reclaim a requirement? What
> operation needs this feature?
>
> AFAICT, the pageframe-reclaim requirements is derived from the
> assumption that some external control path should be able to tell
> zswap/zcache to evacuate a page, like the shrinker interface. But this
> introduces a new and complex problem in designing a policy that doesn't
> shrink the zpage pool so aggressively that it is useless.
>
> Unless there is another reason for this functionality I'm missing.
>

Perhaps it's needed if the user want to enable/disable the memory
compression feature dynamically.
Eg, use it as a module instead of recompile the kernel or even reboot
the system.

>>
>>>> 3) Zsmalloc has a density of exactly 1.0 for any number of
>>>> zpages with zsize >= 0.8.
>>>
>>> For this reason zswap does not cache pages which in this range.
>>> It is not enforced in the allocator because some users may be forced to
>>> store these pages; users like zram.
>>
>> Again, without a "representative" workload, we don't know whether
>> or not it is important to manage pages with zsize >= 0.8. You are
>> simply dismissing it as unnecessary because zsmalloc can't handle
>> them and because they don't appear at any measurable frequency
>> in kernbench or SPECjbb. (Zbud _can_ efficiently handle these larger
>> pages under many circumstances... but without a "representative" workload,
>> we don't know whether or not those circumstances will occur.)
>
> The real question is not whether any workload would operate on pages
> that don't compress to 80%. Any workload that operates on pages of
> already compressed or encrypted data would do this. The question is, is
> it worth it to store those pages in the compressed cache since the
> effective reclaim efficiency approaches 0.
>

Hmm..
Yes, i'd prefer to skip those pages at first glance.

>>
>>>> 4) Zsmalloc contains several compile-time parameters;
>>>> the best value of these parameters may be very workload
>>>> dependent.
>>>
>>> The parameters fall into two major areas, handle computation and class
>>> size. The handle can be abstracted away, eliminating the compile-time
>>> parameters. The class-size tunable could be changed to a default value
>>> with the option for specifying an alternate value from the user during
>>> pool creation.
>>
>> Perhaps my point here wasn't clear so let me be more blunt:
>> There's no way in hell that even a very sophisticated user
>> will know how to set these values. I think we need to
>> ensure either that they are "always right" (which without
>> a "representative workload"...) or, preferably, have some way
>> so that they can dynamically adapt at runtime.
>
> I think you made the point that if this "representative workload" is
> completely undefined, then having tunables for zsmalloc that are "always
> right" is also not possible. The best we can hope for is "mostly right"
> which, of course, is difficult to get everyone to agree on and will be
> based on usage.
>
>>
>>>> If density == 1.0, that means we are paying the overhead of
>>>> compression+decompression for no space advantage. If
>>>> density < 1.0, that means using zsmalloc is detrimental,
>>>> resulting in worse memory pressure than if it were not used.
>>>>
>>>> WORKLOAD ANALYSIS
>>>>
>>>> These limitations emphasize that the workload used to evaluate
>>>> zsmalloc is very important. Benchmarks that measure data
>>>> throughput or CPU utilization are of questionable value because
>>>> it is the _content_ of the data that is particularly relevant
>>>> for compression. Even more precisely, it is the "entropy"
>>>> of the data that is relevant, because the amount of
>>>> compressibility in the data is related to the entropy:
>>>> I.e. an entirely random pagefull of bits will compress poorly
>>>> and a highly-regular pagefull of bits will compress well.
>>>> Since the zprojects manage a large number of zpages, both
>>>> the mean and distribution of zsize of the workload should
>>>> be "representative".
>>>>
>>>> The workload most widely used to publish results for
>>>> the various zprojects is a kernel-compile using "make -jN"
>>>> where N is artificially increased to impose memory pressure.
>>>> By adding some debug code to zswap, I was able to analyze
>>>> this workload and found the following:
>>>>
>>>> 1) The average page compressed by almost a factor of six
>>>> (mean zsize == 694, stddev == 474)
>>>> 2) Almost eleven percent of the pages were zero pages. A
>>>> zero page compresses to 28 bytes.
>>>> 3) On average, 77% of the bytes (3156) in the pages-to-be-
>>>> compressed contained a byte-value of zero.
>>>> 4) Despite the above, mean density of zsmalloc was measured at
>>>> 3.2 zpages/pageframe, presumably losing nearly half of
>>>> available space to fragmentation.
>>>>
>>>> I have no clue if these measurements are representative
>>>> of a wide range of workloads over the lifetime of a booted
>>>> machine, but I am suspicious that they are not. For example,
>>>> the lzo1x compression algorithm claims to compress data by
>>>> about a factor of two.
>>>
>>> I'm suspicious of the "factor of two" claim. The reference
>>> (http://www.oberhumer.com/opensource/lzo/lzodoc.php) for this would appear
>>> to be the results of compressing the Calgary Corpus. This is fine for
>>> comparing compression algorithms but I would be hesitant to apply that
>>> to this problem space. To illustrate the affect of input set, the newer
>>> Canterbury Corpus compresses to ~43% of the input size using LZO1X-1.
>>
>> Yes, agreed, we have no idea if the Corpus is representative of
>> this problem space... because we have no idea what would
>> be a "representative workload" for this problem space.
>>
>> But for how I was using "factor of two", a factor of 100/43=~2.3 is
>> close enough. I was only trying to say "factor of two" may be
>> more "representative" than the "factor of six" in kernbench.
>
> Again, this "representative workload" is undefined to the point of
> uselessness. At this point _any_ actual workload is more useful than
> this undefined representative.
>
>>
>> (As an aside, I like the data Nitin collected here:
>> http://code.google.com/p/compcache/wiki/CompressedLengthDistribution
>> as it shows how different workloads can result in dramatically
>> different zsize distributions. However, this data includes
>> all the pages in a running system, including both anonymous
>> and file pages, and doesn't include mean/stddev.)
>>
>>> In practice the average for LZO would be workload dependent, as you
>>> demonstrate with the kernel build. Swap page entropy for any given
>>> workload will not necessarily fit the distribution present in the
>>> Calgary Corpus. The high density allocation design in zsmalloc allows
>>> for workloads that can compress to factors greater than 2 to do so.
>>
>> Exactly. But at what cost on other workloads? And how do we evaluate
>> the cost/benefit of that high density? (... without a "representative
>> workload" ;-)
>>
>>>> I would welcome ideas on how to evaluate workloads for
>>>> "representativeness". Personally I don't believe we should
>>>> be making decisions about selecting the "best" algorithms
>>>> or merging code without an agreement on workloads.
>>>
>>> I'd argue that there is no such thing as a "representative workload".
>>> Instead, we try different workloads to validate the design and illustrate
>>> the performance characteristics and impacts.
>>
>> Sorry for repeatedly hammering my point in the above, but
>> there have been many design choices driven by what was presumed
>> to be representative (kernbench and now SPECjbb) workload
>> that may be entirely wrong for a different workload (as
>> Seth once pointed out using the text of Moby Dick as a source
>> data stream).
>
> The reality we are going to have to face with the feature of memory
> compression is that not every workload can benefit. The objective
> should be to improve known workloads that are able to benefit. Then
> make improvements that grow that set of workloads.
>
>>
>> Further, the value of different designs can't be measured here just
>> by the workload because the pages chosen to swap may be completely
>> independent of the intended workload-driver... i.e. if you track
>> the pid of the pages intended for swap, the pages can be mostly
>> pages from long-running or periodic system services, not pages
>> generated by kernbench or SPECjbb. So it is the workload PLUS the
>> environment that is being measured and evaluated. That makes
>> the problem especially tough.
>>
>> Just to clarify, I'm not suggesting that there is any single
>> workload that can be called representative, just that we may
>> need both a broad set of workloads (not silly benchmarks) AND
>> some theoretical analysis to drive design decisions. And, without
>> this, arguing about whether zsmalloc is better than zbud or not
>> is silly. Both zbud and zsmalloc have strengths and weaknesses.
>>
>> That said, it should also be pointed out that the stream of
>> pages-to-compress from cleancache ("file pages") may be dramatically
>> different than for frontswap ("anonymous pages"), so unless you
>> and Seth are going to argue upfront that cleancache pages should
>> NEVER be candidates for compression, the evaluation criteria
>> to drive design decisions needs to encompass both anonymous
>> and file pages. It is currently impossible to evaluate that
>> with zswap.
>>
>>>> PAGEFRAME EVACUATION AND RECLAIM
>>>>
>>>> I've repeatedly stated the opinion that managing the number of
>>>> pageframes containing compressed pages will be valuable for
>>>> managing MM interaction/policy when compression is used in
>>>> the kernel. After the experimentation above and some brainstorming,
>>>> I still do not see an effective method for zsmalloc evacuating and
>>>> reclaiming pageframes, because both are complicated by high density
>>>> and page-crossing. In other words, zsmalloc's strengths may
>>>> also be its Achilles heels. For zram, as far as I can see,
>>>> pageframe evacuation/reclaim is irrelevant except perhaps
>>>> as part of mass defragmentation. For zcache and zswap, where
>>>> writethrough is used, pageframe evacuation/reclaim is very relevant.
>>>> (Note: The writeback implemented in zswap does _zpage_ evacuation
>>>> without pageframe reclaim.)
>>>
>>> zswap writeback without guaranteed pageframe reclaim can occur during
>>> swap activity. Reclaim, even if it doesn't free a physical page, makes
>>> room in the page for incoming swap. With zswap the writeback mechanism
>>> is driven by swap activity, so a zpage freed through writeback can be
>>> back-filled by a newly compressed zpage. Fragmentation is an issue when
>>> processes exit and block zpages are invalidated and becomes an issue when
>>> zswap is idle. Otherwise the holes provide elasticity to accommodate
>>> incoming pages to zswap. This is the case for both zswap and zcache.
>>>
>>> At idle we would want defragmentation or aging, either of which has
>>> the end result of shrinking the cache and returning pages to the
>>> memory manager. The former only reduces fragmentation while the
>>> later has the additional benefit of returning memory for other uses.
>>> By adding aging, through periodic writeback, zswap becomes a true cache,
>>> it eliminates long-held allocations, and addresses fragmentation for
>>> long-held allocations.
>>
>> We are definitely on different pages here. You are still trying to
>> push zswap as a separate subsystem that can independently decide how
>> to size itself. I see zcache (and zswap) as a "helper" for the MM
>> subsystem which allow MM to store more anonymous/pagecache pages in
>> memory than otherwise possible.
>
> IIUC from this and your "Better integration of compression with the
> broader linux-mm" thread, you are wanting to allow the MM to tell a
> compressed-MM subsystem to free up pages. There are a few problems I
> see here, mostly policy related. How does the MM know whether is should
> reclaim compressed page space or pages from the inactive list? In the
> case of frontswap, the policies feedback on one another in that the
> reclaim of an anonymous page from the inactive list via swap results in
> an increase in the number of pages on the anonymous zspage list.
>

From the top level, i agree with Dan's opinion that we should integrate
compression into the MM core system more tightly.
But yes there will be complicated and i think it's hard to eliminate the
effect to people who don't need any compression.

> I'm not saying I have the solution. The ideal sizing of the compressed
> pool is a complex issue and, like so many other elements of compressed
> memory design, depends on the workload.
>
> That being said, just because an ideal policy for every workload doesn't
> exist doesn't mean you can't choose one policy (hopefully a simple one)
> and improve it as measurable deficiencies are identified.
>

Regards,
-Bob



\
 
 \ /
  Last update: 2013-03-14 13:21    [W:0.114 / U:0.204 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site