<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">
<div><br class="webkit-block-placeholder"></div><div><div><div>On Nov 5, 2007, at 3:24 , K J wrote:</div><blockquote type="cite"><span class="Apple-style-span" style="color: rgb(0, 0, 0); "><div>The problem is, this membership list will also be displayed when users request it. So would it be best to cache the entire list somehow?</div></span></blockquote><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Yes, but I wouldn't try to think of that as something related to your membership check.</div><br class="webkit-block-placeholder"></div><br><div><div>On Nov 5, 2007, at 3:34 , K J wrote:</div><div><br class="webkit-block-placeholder"></div><blockquote type="cite"> <div>I had thought of doing a bloom filter on it as well. The problem here is, the membership list might change sometimes, and reading info on bloom filters, it's not really well-suited for dynamically changing lists?</div></blockquote><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Well, bloom filters are fine as long as you're only adding to them. I wasn't suggesting actually using a bloom filter, though. Just to think of it more like a bloom filter in that you can only get an answer that is either possibly present or definitely not present (it's a set representation, not a map representation).<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>It was late, though, so I guess I was more typing whatever I was thinking than describing what was a best fit for your question.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>memcached is a map, so you can actually store a yes or no, but the absence of either is a ``possibly.''</div><div><br class="webkit-block-placeholder"></div><blockquote type="cite"> <div>Suppose I cache 10,000 recently-logged in members. Also, suppose 50% of traffic actually come from these users. Then, this cache would have a high hit ratio when testing for membership.</div></blockquote><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>The 10,000 is just a preload. You can certainly cache the rest of them as they actually come in.<br class="webkit-block-placeholder"></div><br><blockquote type="cite"> <div>However, what about the non-members? For instance let's say 40% of the traffic come from non-members. This would mean there'd need to be a full listing of members to check?</div></blockquote><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>You have that in your primary data store. It just means you'd have to go ask it and cache it.<br class="webkit-block-placeholder"></div><br><blockquote type="cite"> <div>Hmmm an interesting thought did just come across my mind. Let me hear your thoughts:</div> <ul> <li>Cache 10,000 most recently logged-in members</li> <li>Bloom filter on the entire list</li></ul> <div>This way, you can test for negatives (bloom filter), and if there's a positive, check the 10,000 most recently logged-in users. If that still yields nothing, then do a database query. In effect, only a small minority of checks would require a trip to the DB.</div></blockquote><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>The bloom filter will not help you unless you have too many active users to fit into a memcached cluster (and you don't).<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Quick review of what went through my head:<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>1) You want set operations (particularly ∈)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>2) Thinking of memcached as a normal set falls apart because of evictions, so how about ∉</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>3) There *is* a value that will be stored at roughly no cost, so we can do both.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>#2 is the bloom filter. After realizing you'd have to go really far out of your way to get any savings out of a 0 byte value vs. a 1 byte value, I figured you might as well store a boolean. Unlike a bloom filter, this means:<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>1) You can check for presence in a single operation.<br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>2) You can further confirm whether the value indicates presence or absence.<br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>3) You can both add items *and* remove items after going to the source.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>So, I apologize for the confusion, but I'd recommend something like this:<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div>def is_special_user(uid):</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>val=memcache.get(uid)<br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if val is not None:<br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>val=query_to_get_special_flag_for(uid)<br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>memcache.set(uid, val)<br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>return val<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>You could preload some if you felt you needed to do so. Adding or removing membership can specifically update the cache.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>As I mentioned above, your listing problem should be considered a different one. I'd suspect it could be done more lazily than the membership check, but if not, you could always invalidate the list when adding or removing membership.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><blockquote type="cite"> <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid"> <div></div> <div class="Wj3C7c"><br>On Nov 4, 2007, at 23:32, J A wrote:<br><br>> I have a fairly large members list that I want to keep in memcache.<br>> What I do with this list is query it against particular user IDs to<br> > see if they are a member of that list or not. If they are they get<br>> certain priviledges.<br>><br>> The problem is, this list has gotten to the point of saturating the<br>> PHP's memory when fetching the MySQL query the first time. <br>><br>> Is there a way to do this more effectively, for instance,<br>> partitioning the list into separate smaller lists, grouped by time<br>> of login? I'm thinking of this, as users who have logged in in the <br>> past 3 months are more likely to be in the list anyway.<br><br><br></div> It'd be easier to not think of it as a list if you're just testing<br>for membership. All you want to know is if a particular object is an <br>element of a particular set. You could do this by key convention if<br>you batch populate the records.<br><br> However, memcached semantics don't quite give you what you want.<br>Depending on whether you can reasonably get a configuration to do what <br>you want, it might be easier to think of memcached as a bloom filter<br>than as a set in this case. That is, if you negatively cache things<br>that *aren't* part of your list, then the presence of a key will tell <br>you for certain that a particular key is not a member, but the absence<br>of a key would mean that you don't know (or perhaps memcached *did*<br>know, but had since forgotten).<br><br> You could, of course, record the status either way so as to tell the <br>difference between not knowing and knowing whether it's a member or<br>not. This is probably best suited to your needs.<br><br> You could optionally preload objects that are likely to be used if<br>you think the natural population wouldn't do it effectively (you can <br>measure this with stats).<br><br>--<br><font color="#888888">Dustin Sallings<br><br><br><br></font></blockquote><br></blockquote></div><br><div> <span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div>-- </div><div>Dustin Sallings</div><br class="Apple-interchange-newline"></span> </div><br></body></html>