Python Django "Killed"

Question

New commit, works locally but not in production. The messages are strange.

With uwsgi everything starts as usual. But on the first hit I send the server, everything freezes (I mean everything, even the SSH session stops responding). Eventually one of the workers die and the server starts responding again. With ./manage.py runserver this happens:

$ ./manage.py runserver
Performing system checks...

Killed

That's it. The only line in the commit is at the beginning of views.py

import my_module

Again, this works locally but not in production. I can't give you too much detail about my_module, but it's basically a very long list inside a class with a method that does a binary search.

My suspicion is that it has to do with how big the thing is. The my_module.py file is 62MB.

How can I find out what's happening?

EDIT: Tried ./manage.py runserver and then dmesg, twice:

[  372.911491] python[1692]: segfault at 24 ip 0000000000558077 sp 00007f6624b70880 error 6 in python2.7[400000+2bc000]
[  414.833167] python[1729]: segfault at 24 ip 0000000000558077 sp 00007f9f17cbc880 error 6 in python2.7[400000+2bc000]
[  414.837098] Core dump to |/usr/share/apport/apport 1726 11 0 1726 pipe failed

@LegoStormtroopr I'm not, I'm using `uwsgi` + nginx. I just used `runserver` because I want to make it closer to dev, since I know that commit works perfectly in dev. — , Feb 02 '17 at 23:32
Try run `dmesg` and see what the last line says, it may say something about running out of memory? — davidejones, Feb 03 '17 at 00:04
The most likely contender (in my experience) is the OOM (out of memory) killer. Are you sure you have enough memory available? — Wolph, Feb 03 '17 at 01:21
I think in the past when there have been segfaults I've used this to determine why `python -m pdb manage.py runserver` but yea sounds like a memory issue, you might want to increase the memory amount of the server/vm/container or maybe think about having the my_module data separated somehow and using generators to yield a result at a time instead of storing the giant list all in memory. — davidejones, Feb 03 '17 at 01:36
@Wolph I'm not sure, no. I don't understand these low level details very well. What I can tell you with certainty is that my laptop has 4gb ram and it works. Production was a t2.nano (0.5GB) which I then upgraded to t2.micro (1GB) and then t2.small (2GB). Same thing is still happening. — , Feb 03 '17 at 01:37
@davidejones I don't understand that command. I just gives me a prompt that reads `(Pdb)` and just stays there. — , Feb 03 '17 at 01:54
A segfault is a whole different issue, that helps a bit more. So it's probably not an out of memory issue but some code issue. With a 62MB python file I can imagine that something inside of uwsgi is running out of space. I personally think you should solve that issue, if anything is that large it should be put in an external file or something and not in the code. — Wolph, Feb 03 '17 at 15:35
@Wolph what external tool do you suggest that I use to do what is effectively a binary search on a list? Actually, more precisely it's a binary search on a list that has ranges. Example `big_list = [(1,2,'some string'),(4,5,'other string'),....]` were the zeroth entry of the tuple is the lower bound of the range and the first entry is the upper bound, and so doing a binary search for `1.6` would return `some string`. Just "an external file" doesn't work, because then I can't do binary search. — , Feb 03 '17 at 18:16
In that case even a simple database server such as sqlite could do the trick. But binary search within a file is fairly easy to do as well. Simply jumping to half of the filesize initially and jumping to half of that in either direction is effectively a binary search as well. — Wolph, Feb 04 '17 at 00:51
@oneloop question offers a few options for binary search: http://stackoverflow.com/questions/5217650/how-do-i-perform-binary-search-on-a-text-file-to-search-a-keyword-in-python — Wolph, Feb 05 '17 at 00:31
@Wolph re file, are you sure that's true? Because I believe that doing a seek for a specific line number is linear in the line number. For the search to be an actual binary search (i.e. log N) the "jumping to a line number" step would have to be order 1. — , Feb 05 '17 at 18:14
@Wolph the link that you sent me is not relevant. Belonging to a set or dict in python is order 1 (meaning, it's even better than binary search's log N) but does not allow search by comparison operators like `<` meaning that I can't solve the problem I want, read my comment above with example `big_list = [(1,2,'some string'),(4,5,'other string'),....]` — , Feb 05 '17 at 18:17
@oneloop a `seek()` in a file is `O(1)` and doing a binary search in that manner would be `O(log(N))` assuming your lines have a fixed size. If you're not using a fixed line size it would technically still be `O(log(N))` but you would have to search for the line bounds every time. As for the linked question, some of the answer are indeed simple hash lookups but the `bisect` based answer is actually using binary search: http://stackoverflow.com/a/5219275/54017 — Wolph, Feb 05 '17 at 22:19
Still, instead of reinventing the wheel a solution such as sqlite is probably a better solution. Simply create a table, add an index and you can easily do indexed lookups in the table with the added advantage that adding/removing rows is trivial as well. — Wolph, Feb 05 '17 at 22:25
@Wolph line size is not fixed, so doesn't work. Regarding sqlite, how do I use sqllite to do interval searches? From what I understand, `BTREE` is for point searches. — , Feb 06 '17 at 16:32
@oneloop I've added an example. A regular sqlite index can easily do ranged searches. As for the `BTREE` option, that's a sorted tree so ranged searches are easily possible using a standard binary search. — Wolph, Feb 10 '17 at 01:44

Wolph · Answer 1 · 2017-02-10T10:27:42.547

Here's an example on how to use sqlite to solve your problem. The searches are indexed so they're about as fast as you can get them:

import os
import random
import sqlite3
import contextlib
from datetime import datetime


@contextlib.contextmanager
def get_connection():
    connection = sqlite3.connect('database.db')
    try:
        yield connection
        connection.commit()
    finally:
        connection.close()


@contextlib.contextmanager
def get_cursor():
    with get_connection() as connection:
        cursor = connection.cursor()
        try:
            yield cursor
        finally:
            cursor.close()


def initial_create():
    # read your giant array from a file here

    with get_cursor() as cursor:
        cursor.executescript('''
        BEGIN;
        CREATE TABLE big_list (
            a int,
            b int,
            value text
        );

        CREATE INDEX big_list__a_b_idx ON big_list (a, b);
        COMMIT;
        ''')

        for i in range(1000):
            a = random.randint(0, 1000000)
            inserts = []

            for j in range(1000):
                b = random.randint(0, 1000000)

                inserts.append((
                    a,
                    b,
                    'some string (%d,%d)' % (a, b),
                ))

            cursor.executemany('INSERT INTO big_list VALUES (?,?,?)', inserts)


def test():
    with get_cursor() as cursor:
        print 'Total rows: %d' % (
            cursor.execute('SELECT COUNT(*) FROM big_list').fetchone())

        print 'Exact searches:'
        for i in range(10):
            start = datetime.now()

            result = cursor.execute('''
            SELECT *
            FROM big_list
            WHERE a = %d
            AND b = %d
            ''' % (i * 1000, i * 10000))
            print 'Got results: %r in' % result.fetchall(),
            print datetime.now() - start

        print 'Ranged searches:'
        for i in range(10):
            start = datetime.now()

            result = cursor.execute('''
            SELECT *
            FROM big_list
            WHERE a BETWEEN %d AND %d
            AND b BETWEEN %d AND %d
            ''' % (i * 1000, (i + 1) * 1000, i * 1000, (i + 1) * 1000))
            print 'Got results: %r in' % result.fetchall(),
            print datetime.now() - start


if __name__ == '__main__':
    if not os.path.isfile('database.db'):
        print 'Creating database, this should only be needed once'
        initial_create()

    test()

Example output:

Total rows: 1000000
Exact searches:
Got results: [] in 0:00:00.000113
Got results: [] in 0:00:00.000055
Got results: [] in 0:00:00.000044
Got results: [] in 0:00:00.000044
Got results: [] in 0:00:00.000043
Got results: [] in 0:00:00.000045
Got results: [] in 0:00:00.000043
Got results: [] in 0:00:00.000041
Got results: [] in 0:00:00.000044
Got results: [] in 0:00:00.000041
Ranged searches:
Got results: [(604, 31, u'some string (604,31)'), (604, 386, u'some string (604,386)')] in 0:00:00.000889
Got results: [(1142, 1856, u'some string (1142,1856)')] in 0:00:00.000538
Got results: [] in 0:00:00.000056
Got results: [(3802, 3983, u'some string (3802,3983)')] in 0:00:00.000482
Got results: [] in 0:00:00.000165
Got results: [] in 0:00:00.000047
Got results: [] in 0:00:00.000164
Got results: [(7446, 7938, u'some string (7446,7938)'), (7947, 7381, u'some string (7947,7381)')] in 0:00:00.000867
Got results: [(8003, 8174, u'some string (8003,8174)')] in 0:00:00.000501

Hi Wolph, thanks for this. These aren't exactly the queries I was describing though. Forget about the exact searches now. Your ranged searches are `WHERE a BETWEEN %d AND %d AND b BETWEEN %d AND %d`. What I described would be something like `WHERE %d BETWEEN a AND b`. Does this syntax do what's expected? If so I'll try it in MySQL (which I'm using) and then mark your answer correct. — , Feb 15 '17 at 10:27
Hi again. I just tried it, it works. I've also re-read my question and noticed that actually I didn't describe any of it well (I was thinking about our discussion in the comments). Should I open a new question which asks what I asked in the comments and you'll post this answer there, additionally replacing `WHERE a BETWEEN %d AND %d AND b BETWEEN %d AND %d` with `WHERE %d BETWEEN a AND b`? — , Feb 15 '17 at 11:16
I've just tested my query and it's not good enough. With `a` and `b` being 32bit ints and 700k rows, each query like `WHERE %d BETWEEN a AND b` takes half a second. It's not obvious how indexes on `a` and `b` would even be used for that query, right? I suspect that the DB is using the index on `a` to find a few thousands results and then just scroll row by row for matches on `b`... — , Feb 15 '17 at 13:53
To me the above is reinforced by the fact that if I pick a very small or very big int, the queries are super fast, but if I pick one in the middle of the 32bit range they take about half a second. — , Feb 15 '17 at 13:56
BTW Wolph what I ended up doing was follow your initial suggestion. I put it all in one file, forced line size to be constant by padding at the end with spaces, and did a binary search. If I remember correctly my tests at the time showed that it would take 1.5 secs to do 10k searches. — , Feb 15 '17 at 14:06
@oneloop: glad you found a solution :) How smart the database will execute this depends greatly on the database. I would suspect that PostgreSQL might perform better here but it needs testing to be certain. — Wolph, Feb 15 '17 at 17:24
it's a half-hacked solution. It assumes that there are no overlapping intervals. In my case it's mostly true, but not absolutely true. I also don't have a good way to do that search and at the same time to searches for "point intervals", so I actually have to do two searches one after the other. `WHERE %d BETWEEN a AND b` solves these two issues, but it takes too long. At least until I can look into postgresql, as you suggested. — , Feb 15 '17 at 19:08

Python Django "Killed"

1 Answers1