Caching Is Key, and SIEVE Is Better Than LRU

USENIX, the long-running OS/networking research group, also publishes a magazine called ;login:. Today the magazine’s editor — security consultant Rik Farrow — stopped by Slashdot to share some new research. rikfarrow writes:
Caching means using faster memory to store frequently requested data, and the most commonly used algorithm for determining which items to discard when the cache is full is Least Recently Used [or “LRU”]. These researchers have come up with a more efficient and scalable method that uses just a few lines of code to convert LRU to SIEVE.
Just like a sieve, it sifts through objects (using a pointer called a “hand”) to “filter out unpopular objects and retain the popular ones,” with popularity based on a single bit that tracks whether a cached object has been visited:

As the “hand” moves from the tail (the oldest object) to the head (the newest object), objects that have not been visited are evicted… During the subsequent rounds of sifting, if objects that survived previous rounds remain popular, they will stay in the cache. In such a case, since most old objects are not evicted, the eviction hand quickly moves past the old popular objects to the queue positions close to the head. This allows newly inserted objects to be quickly assessed and evicted, putting greater eviction pressure on unpopular items (such as “one-hit wonders”) than LRU-based eviction algorithms.
It’s an example of “lazy promotion and quick demotion”. Popular objects get retained with minimal effort, with quick demotion “critical because most objects are not reused before eviction.”

After 1559 traces (of 247,017 million requests to 14,852 million objects), they found SIEVE reduces the miss ratio (when needed data isn’t in the cache) by more than 42% on 10% of the traces with a mean of 21%, when compared to FIFO. (And it was also faster and more scalable than LRU.)

“SIEVE not only achieves better efficiency, higher throughput, and better scalability, but it is also very simple.”

Read more of this story at Slashdot.

Boeing Fraud Violated Fatal MAX Crash Settlement, Says Justice Department, Seeking Guilty Plea on Criminal Charges

America’s Justice Department “is pushing for Boeing to plead guilty to a criminal charge,” reports Reuters, “after finding the planemaker violated a settlement over fatal 737 MAX crashes in 2018 and 2019 that killed 346 people, two people familiar with the matter said on Sunday.”

Boeing previously paid $2.5 billion as part of the deal with prosecutors that granted the company immunity from criminal prosecution over a fraud conspiracy charge related to the 737 MAX’s flawed design. Boeing had to abide by the terms of the deferred prosecution agreement for a three-year period that ended on Jan. 7. Prosecutors would then have been poised to ask a judge to dismiss the fraud conspiracy charge. But in May, the Justice Department found Boeing breached the agreement, exposing the company to prosecution.
A guilty plea could “carry implications for Boeing’s ability to enter into government contracts,” the article points out, “such as those with the U.S. military that make up a significant portion of its revenue…”

The proposal would require Boeing to plead guilty to conspiring to defraud the U.S. Federal Aviation Administration in connection with the fatal crashes, the sources said. The proposed agreement also includes a $487.2 million financial penalty, only half of which Boeing would be required to pay, they added. That is because prosecutors are giving the company credit for a payment it made as part of the previous settlement related to the fatal crashes of the Lion Air and Ethiopian Airlines flights. Boeing could also likely be forced to pay restitution under the proposal’s terms, the amount of which will be at a judge’s discretion, the sources said.

The offer also contemplates subjecting Boeing to three years of probation, the people said. The plea deal would also require Boeing’s board to meet with victims’ relatives and impose an independent monitor to audit the company’s safety and compliance practices for three years, they said.
“Should Boeing refuse to plead guilty, prosecutors plan to take the company to trial, they said…” the article points out.

“Justice Department officials revealed their decision to victims’ family members during a call earlier on Sunday.”

Read more of this story at Slashdot.