pagination with grouped index, just proof of concept, should use uuid instead of mutex

pager.rb

require "mongo"

class Pager

  db = Mongo::Connection.new.db 'pager'
  DOCS  = db.collection 'docs'
  INDEX = db.collection 'index'
  STATE = db.collection 'state'
  THRESHOLD = 1000
  STATE_LOCK = Mutex.new

  def initialize 
    @state = STATE.find_one
    if !@state or @state.empty?
      id = STATE.insert 'counter' => 0
      @state = STATE.find_one
      DOCS.create_index([['index', Mongo::DESCENDING]])
      INDEX.create_index 'index'
    end
  end

  def insert i, doc
    STATE_LOCK.synchronize do
      DOCS.insert 'doc' => doc, 'index' => i
      add_counter i
    end
  end

  def find page
    start, skip = query_index page
    criteria = start == -1 ? {} : {'index' => {'$lte' => start}}
    DOCS.find(criteria, :sort => ['index', :desc]).skip(skip).limit(20)
  end

  private

  def add_counter doc_id
    c = @state['counter']
    c += 1
    overflow = (c >= THRESHOLD)
    @state['counter'] = overflow ? 0 : c
    STATE.save @state
    if overflow
      INDEX.insert 'doc_id' => doc_id, 'index' => INDEX.size
    end
  end

  def query_index page
    # pseudo_id, not real
    first_id = (DOCS.size - 1) - (page - 1) * 20
    i, offset = first_id.divmod THRESHOLD
    index = (INDEX.find_one 'index' => i) || {}
    start_id = index['doc_id']
    if start_id
      puts [first_id, start_id, offset]
      [start_id, (THRESHOLD - offset - 1)]
    else
      [-1, ((page - 1) * 20)]
    end
  end

end

# p = Pager.new
# # care: maybe very long !
# 1000_000.times {|i| p.insert i, "you are fucking genius" }
# p.find(1).to_a       # page 1
# p.find(500_000).to_a # page 500_000. not slow !