data/blob/atime_darwin.go | 12 ++++++++++++
 data/blob/atime_linux.go  | 12 ++++++++++++
 data/blob/store.go        | 41 ++++++++++++++++++++++++++++++++++++-----

diff --git a/data/blob/atime_darwin.go b/data/blob/atime_darwin.go
new file mode 100644
index 0000000000000000000000000000000000000000..33091d590161c13e62ce003d56728ef09af20a99
--- /dev/null
+++ b/data/blob/atime_darwin.go
@@ -0,0 +1,12 @@
+package blob
+
+import (
+	"os"
+	"syscall"
+	"time"
+)
+
+func accessTime(fi os.FileInfo) time.Time {
+	ts := fi.Sys().(*syscall.Stat_t).Atimespec
+	return time.Unix(ts.Sec, ts.Nano())
+}
diff --git a/data/blob/atime_linux.go b/data/blob/atime_linux.go
new file mode 100644
index 0000000000000000000000000000000000000000..3bcc0548abebf11d44e4b9045226badb129d1a43
--- /dev/null
+++ b/data/blob/atime_linux.go
@@ -0,0 +1,12 @@
+package blob
+
+import (
+	"os"
+	"syscall"
+	"time"
+)
+
+func accessTime(fi os.FileInfo) time.Time {
+	ts := fi.Sys().(*syscall.Stat_t).Atim
+	return time.Unix(ts.Sec, ts.Nano())
+}
diff --git a/data/blob/store.go b/data/blob/store.go
index 766129f35b8bc6412bb394761a8c037d97310b41..cb8f2aa81784d03564e7c48e63d926803b80e0c6 100644
--- a/data/blob/store.go
+++ b/data/blob/store.go
@@ -10,6 +10,8 @@ 	"io"
 	"math/rand"
 	"os"
 	"path/filepath"
+	"sort"
+	"time"
 
 	dataPkg "bitbucket.org/anacrolix/go.torrent/data"
 	"github.com/anacrolix/libtorgo/metainfo"
@@ -133,6 +135,36 @@ 	delete(me.completed, name)
 	return
 }
 
+type fileInfoSorter struct {
+	fis []os.FileInfo
+}
+
+func (me fileInfoSorter) Len() int {
+	return len(me.fis)
+}
+
+func lastTime(fi os.FileInfo) (ret time.Time) {
+	ret = fi.ModTime()
+	atime := accessTime(fi)
+	if atime.After(ret) {
+		ret = atime
+	}
+	return
+}
+
+func (me fileInfoSorter) Less(i, j int) bool {
+	return lastTime(me.fis[i]).Before(lastTime(me.fis[j]))
+}
+
+func (me fileInfoSorter) Swap(i, j int) {
+	me.fis[i], me.fis[j] = me.fis[j], me.fis[i]
+}
+
+func sortFileInfos(fis []os.FileInfo) {
+	sorter := fileInfoSorter{fis}
+	sort.Sort(sorter)
+}
+
 func (me *store) makeSpace(space int64) error {
 	if me.capacity < 0 {
 		return nil
@@ -148,12 +180,11 @@ 	var size int64
 	for _, fi := range fis {
 		size += fi.Size()
 	}
+	sortFileInfos(fis)
 	for size > me.capacity-space {
-		i := rand.Intn(len(fis))
-		me.removeCompleted(fis[i].Name())
-		size -= fis[i].Size()
-		fis[i] = fis[len(fis)-1]
-		fis = fis[:len(fis)-1]
+		me.removeCompleted(fis[0].Name())
+		size -= fis[0].Size()
+		fis = fis[1:]
 	}
 	return nil
 }