s/pagging/padding/. gah.
On Fri, 11 Apr 2014, dormando wrote:
>
>
> On Fri, 11 Apr 2014, Slawomir Pryczek wrote:
>
> > Hi Dormando, more about the behaviour... when we're using "normal"
> > memcached 1.4.13 16GB of memory gets exhausted in ~1h, then we start to have
> > almost instant evictions of needed items (again these items aren't really
> > "needed" individually, just when many of them gets evicted it's
> > unacceptable because of how badly it affects the system)
>
> Almost instant evictions; so an item is stored, into a 16GB instance, and
> < 120 seconds later is bumped out of the LRU?
>
> You'll probably just ignore me again, but isn't this just slab imbalance?
> Once your instance fills up there're probably a few slab classes with way
> too little memory in them.
>
> 'stats slabs' shows you per-slab eviction rates, along with the last
> accessed time of an item when it was evicted. What does this look like on
> one of your full instances?
>
> The slab rebalance system lets you plug in your own algorithm by running
> the page reassignment commands manually. Then you can smooth out the pages
> to where you think they should be.
>
> You mention long and short TTL, but what are they exactly? 120s and an
> hour? A week?
>
> I understand your desire to hack up something to solve this, but as you've
> already seen scanning memory to remove expired items is problematic:
> you're either going to do long walks from the tail, use a background
> thread and walk a "probe" item through, or walk through random slab pages
> looking for expired memory. None of these are very efficient and tend to
> rely on luck.
>
> A better way to do this is to bucket the memory by TTL. You have lots of
> pretty decent options for this (and someone else already suggested one):
>
> - In your client, use different memcached pools for major TTL buckets (ie;
> one instance only gets long items, one only short). Make sure the slabs
> aren't imbalanced via the slab rebalancer.
>
> - Are the sizes of the items correlated with their TTL? Are 120s items
> always in a ~300 byte range and longer items tend to be in a different
> byte range? You could use length pagging to shunt them into specific slab
> classes, separating them internally at the cost of some ram efficiency.
>
> - A storage engine (god I wish we'd made 1.6 work...) which allows
> bucketing by TTL ranges. You'd want a smaller set of slab classes to not
> waste too much memory here, but the idea is the same as running multiple
> individual instances, except internally splitting the storage engine
> instead and storing everything in the same hash table.
>
> Those three options completely avoid latency problems, the first one
> requires no code modifications and will work very well. The third is the
> most work (and will be tricky due to things like slab rebalance, and none
> of the slab class identification code will work). I would avoid it unless
> I were really bored and wanted to maintain my own fork forever.
>
> > ~2 years ago i created another version based on that 1.4.13, than does
> > garbage collection using custom stats handler. That version is able to be
> > running on half of the memory for like 2 weeks, with 0 evictions. But we
> > gave it full 16G and just restart it each week to be sure memory usage is
> > kept in check, and we're not throwing away good data. Actually after
> > changing -f1.25 to -f1.041 the slabs are filling with bad items much slower,
> > because items are distributed better and this custom eviction function is
> > able to catch more expired data. We have like 200GB of data evicted this
> > way, daily. Because of volume (~40k req/s peak, much of it are writes) and
> > differences in expire time LRU isn't able to reclaim items efficiently.
> >
> > Maybe people don't even realize the problem, but when we done some testing
> > and turned off that "custom" eviction we had like 100% memory used with
> > 10% of waste reported by memcached admin. But then we run that custom
> > eviction algorithm it turned out that 90% of memory is occupied by garbage.
> > Waste reported grew to 80% instantly after running unlimited "reclaim
> > expired" on all items in the cache. So in "standard" client when people will
> > be using different expire times for items (we have it like 1minute minimum,
> > 6h max)... they even won't be able to see how much memory they're
> > wasting in some specific cases, when they'll have many items that won't be
> > hit after expiration, like we have.
> >
> > When using memcached as a buffer for mysql writes, we know exactly what to
> > hit and when. Short TTL expired items, pile up near the head... long TTL
> > "live" items pile up near the tail and it's creating a barrier that
> > prevents the LRU algo to reclaim almost anything, if im getting how it
> > currently works, correctly...
> >
> > >You made it sound like you had some data which never expired? Is this
> > >true?
> > Yes, i think because of how evictions are made (to be clear we're not
> > setting non-expiring items). These short expiring items pile up in the front
> > of linked list, something that is supposed to live for eg. 120 or 180
> > seconds is lingering in memory forever, untill we restart the cache... and
> > new items are killed almost instantly because there are no expired items on
> > head.
> >
> > It's a special case, because after processing memory list, aggregating data
> > and putting it in mysql these items are no longer touched. The list for
> > new time period will have completely different set of keys. As we use a
> > prefix to generate all items in the list.
> >
> > $time_slice = floor( self::$time / 60) - $time_slices_back;
> > $prefix = ")ML){$list_id}-{$time_slice}";
> >
> > Again, not saying current implementation is bad... because it's fast and
> > doesn't trash CPU cache when expire times are ~equal, that was probably
> > the idea... but we have not typical use case, which LRU isn't able to
> > manage...
> >
> > Now im making ~same changes i made for .13... but for .17 and i want to
> > make it working a little better ;)
> >
> >
> >
> > W dniu piątek, 11 kwietnia 2014 05:12:10 UTC+2 użytkownik Dormando napisał:
> >
> > > Hey Dormando, thanks again for some comments... appreciate the help.
> > >
> > > Maybe i wasn't clear enough. I need only 1 minute persistence, and
> > i can lose data sometimes, just i can't keep loosing data every
> > minute due to
> > > constant evictions caused by LRU. Actually i have just wrote that
> > in my previous post. We're loosing about 1 minute of
> > non-meaningfull data every
> > > week because of restart that we do when memory starts to fill up
> > (even with our patch reclaiming using linked list, we limit
> > reclaiming to keep
> > > speed better)... so the memory fills up after a week, not 30
> > minutes...
> >
> > Can you explain what you're seeing in more detail? Your data only
> > needs to
> > persist for 1 minute, but it's being evicted before 1 minute is up?
> >
> > You made it sound like you had some data which never expired? Is this
> > true?
> >
> > If your instance is 16GB, takes a week to fill up, but data only
> > needs to
> > persist for a minute but isn't, something else is very broken? Or am I
> > still misunderstanding you?
> >
> > > Now im creating better solution, to limit locking as linked list is
> > getting bigger.
> > >
> > > I explained what was worst implications of unwanted evictions (or
> > loosing all data in cache) in my use case:
> > > 1. loosing ~1 minute of non-significant data that's about to be
> > stored in sql
> > > 2. "flat" distribution of load to workers (not taking response
> > times into account because stats reset).
> > > 3. resorting to alternative targeting algorithm (with global, not
> > local statistics).
> > >
> > > I never, ever said im going to write data that have to be
> > persistent permanently. It's actually same idea as delayed write. If power
> > fails you
> > > loose 5s of data, but you can do 100x more writes. So you need the
> > data to be persistent in memory, between writes the data **can't
> > be lost**.
> > > However you can lose it sometimes, that's the tradeoff that some
> > people can make and some not. Obviously I can't keep loosing this
> > data each
> > > minute, because if i loose much it'll become meaningfull.
> > >
> > > Maybe i wasn't clear in that matter. I can loose all data even 20
> > times a day. Sensitive data is stored using bulk update or
> > transactions,
> > > bypassing that "delayed write" layer. "0 evictions", that's the
> > kind of "persistence" im going for. So items are persistent for some
> > very short
> > > periods of time (1-5 minutes) without being killed. It's just
> > different use case. Running in production since 2 years, based on
> > 1.4.13, tested for
> > > corectness, monitored so we have enough memory and 0 evictions
> > (just reclaims)
> > >
> > > When i came here with same idea ~2 years ago you just said it's
> > very stupid, now you even made me look like a moron :) And i can
> > understand why you
> > > don't want features that are not ~O(1) perfectly, but please don't
> > get so personal about different ideas to do things and use cases,
> > just because
> > > these won't work for you.
> > >
> > >
> > >
> > >
> > >
> > > W dniu czwartek, 10 kwietnia 2014 20:53:12 UTC+2 użytkownik
> > Dormando napisał:
> > > You really really really really really *must* not put data in
> > memcached
> > > which you can't lose.
> > >
> > > Seriously, really don't do it. If you need persistence, try
> > using a redis
> > > instance for the persistent stuff, and use memcached for your
> > cache stuff.
> > > I don't see why you feel like you need to write your own
> > thing, there're a
> > > lot of persistent key/value stores (kyotocabinet/etc?). They
> > have a much
> > > lower request ceiling and don't handle the LRU/cache pattern
> > as well, but
> > > that's why you can use both.
> > >
> > > Again, please please don't do it. You are damaging your
> > company. You are a
> > > *danger* to your company.
> > >
> > > On Thu, 10 Apr 2014, Slawomir Pryczek wrote:
> > >
> > > > Hi Dormando, thanks for suggestions, background thread
> > would be nice...
> > > > The idea is actually that with 2-3GB i get plenty of
> > evictions of items that need to be fetched later. And with 16GB i still
> > get
> > > evictions,
> > > > actually probably i could throw more memory than 16G and
> > it'd only result in more expired items sitting in the middle of
> > slabs,
> > > forever... Now im
> > > > going for persistence. Sounds probably crazy, but we're
> > having some data that we can't loose:
> > > > 1. statistics, we aggregate writes to DB using memcached
> > (+list implementation). If these items get evicted we're loosing
> > rows in db.
> > > Loosing data
> > > > sometimes isn't a big problem. Eg. we restart memcached
> > once a week so we're loosing 1 minute of data every week. But if we
> > have
> > > evictions we're
> > > > loosing data constantly (which we can't have)
> > > > 2. we drive load balancer using data in memcached for
> > statistics, again, not nice to loose data often because workers can get
> > > incorrect amount of
> > > > traffic.
> > > > 3. we're doing some adserving optimizations, eg. counting
> > per-domain ad priority, for one domain it takes about 10 seconds to
> > analyze
> > > all data and
> > > > create list of ads, so can't be done online... we put
> > result of this in memcached, if we loose too much of this the system
> > will start
> > > to serve
> > > > suboptimal ads (because it'll need to switch to more
> > general data or much simpler algorithm that can be done instantly)
> > > >
> > > > Probably would be best to rewrite all this using C or
> > golang, and use memcached just for caching, but it'd take too much time
> > which
> > > we don't have
> > > > currently...
> > > >
> > > > I have seen twitter and nk implementations that seem to do
> > what i need, but they seem old (based on old code), so I prefer to
> > modify
> > > code of recent
> > > > "official" memcached, to not be stuck with old code or
> > abandonware. Actually there are many topics about limitations of
> > currrent
> > > eviction algo and
> > > > option to enable some background thread to do scraping
> > based on statistics of most filled slabs (with some parameter to
> > specify if it
> > > should take
> > > > light or aggressive approach) would be nice...
> > > >
> > > > As for the code... is that slab_rebalance_move function in
> > slab.c? It seems a little difficult to gasp without some DOCs of
> > how
> > > things are
> > > > working... can you please write a very short description of
> > how this "angry birds" more workd?
> > >
> > > Look at doc/protocol.txt for explanations of the slab move
> > options. the
> > > names are greppable back to the source.
> > >
> > > > I have quick question about this above... linked is item
> > that's placed on linked list, but what other flags means, and why 2
> > last are
> > > 2 of them
> > > > temporary?
> > > > #define ITEM_LINKED 1
> > > > #define ITEM_CAS 2
> > > >
> > > > /* temp */
> > > > #define ITEM_SLABBED 4
> > > > #define ITEM_FETCHED 8
> > > >
> > > > This from slab_rebalance_move seems interesting:
> > > > refcount = refcount_incr(&it->refcount);
> > > > ...
> > > > if (refcount == 1) { /* item is unlinked, unused */
> > > > ...
> > > > } else if (refcount == 2) { /* item is linked but not busy
> > */
> > > >
> > > > Is there some docs about refcounts, locks and item states?
> > Basically why item with refcount 2 is not busy? You're increasing
> > refcount
> > > by 1 on
> > > > select, then again when reading data? Can refcount ever be
> > higher than 2 (3 in above case), meaning 2 threads can access same
> > item?
> > >
> > > The comment on the same line is explaining exactly what it
> > means.
> > >
> > > Unfortunately it's a bit of a crap shoot. I think I wrote a
> > threads
> > > explanation somewhnere (some release notes, or in a file in
> > there, I can't
> > > quite remember offhand). Since scaling the thread code it got
> > a lot more
> > > complicated. You have to be extremely careful under what
> > circumstances you
> > > access items (you must hold an item lock + the refcount must
> > be 2 if you
> > > want to unlink it).
> > >
> > > You'll just have to study it a bit, sorry. Grep around to see
> > where the
> > > flags are used.
> > >
> > > > Thanks.
> > > >
> > > > W dniu czwartek, 10 kwietnia 2014 06:05:30 UTC+2 użytkownik
> > Dormando napisał:
> > > > > Hi Guys,
> > > > > im running a specific case where i don't want
> > (actually can't have) to have evicted items (evictions = 0 ideally)...
> > now i
> > > have
> > > > created some simple
> > > > > algo that lock the cache, goes through linked list
> > and evicts items... it makes some problems, like 10-20ms cache
> > locks on
> > > some
> > > > cases.
> > > > >
> > > > > Now im thinking about going through each slab
> > memory (slabs keep a list of allocated memory regions) ... looking for
> > items,
> > > if
> > > > expired item is
> > > > > found, evict it... this way i can go eg. 10k items
> > or 1MB of memory at a time + pick slabs with high utilization and
> > run this
> > > > "additional" eviction
> > > > > only on them... so it'll prevent allocating memory
> > just because unneded data with short TTL is occupying HEAD of the
> > list.
> > > > >
> > > > > With this linked list eviction im able to run on
> > 2-3GB of memory... without it 16GB of memory is exhausted in 1-2h
> > and then
> > > memcached
> > > > starts to
> > > > > kill "good" items (leaving expired ones wasting
> > memory)...
> > > > >
> > > > > Any comments?
> > > > > Thanks.
> > > >
> > > > you're going a bit against the base algorithm. if
> > stuff is falling out of
> > > > 16GB of memory without ever being utilized again, why
> > is that critical?
> > > > Sounds like you're optimizing the numbers instead of
> > actually tuning
> > > > anything useful.
> > > >
> > > > That said, you can probably just extend the slab
> > rebalance code. There's a
> > > > hook in there (which I called "Angry birds mode")
> > that drives a slab
> > > > rebalance when it'd otherwise run an eviction. That
> > code already safely
> > > > walks the slab page for unlocked memory and frees it;
> > you could edit it
> > > > slightly to check for expiration and then freelist it
> > into the slab class
> > > > instead.
> > > >
> > > > Since it's already a background thread you could
> > further modify it to just
> > > > wake up and walk pages for stuff to evict.
> > > >
> > > > --
> > > >
> > > > ---
> > > > You received this message because you are subscribed to the
> > Google Groups "memcached" group.
> > > > To unsubscribe from this group and stop receiving emails
> > from it, send an email to memcached+...@googlegroups.com.
> > > > For more options, visit https://groups.google.com/d/optout.
> > > >
> > > >
> > >
> > > --
> > >
> > > ---
> > > You received this message because you are subscribed to the Google
> > Groups "memcached" group.
> > > To unsubscribe from this group and stop receiving emails from it,
> > send an email to memcached+...@googlegroups.com.
> > > For more options, visit https://groups.google.com/d/optout.
> > >
> > >
> >
> > --
> >
> > ---
> > You received this message because you are subscribed to the Google Groups
> > "memcached" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to memcached+unsubscr...@googlegroups.com.
> > For more options, visit https://groups.google.com/d/optout.
> >
> >
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "memcached" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to memcached+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
--
---
You received this message because you are subscribed to the Google Groups
"memcached" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to memcached+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
